Progress in Cryptology — INDOCRYPT 2001

In 1999, Poupard and Stern proposed on the fly signature scheme (PS-scheme), which aims at minimizing the on-line computational work for a signer. In this paper, we propose more efficient on the fly signature schemes by improving the PS-scheme. In PS-scheme, the size of secret-key is fixed by modulus n, so that this feature leads to some drawbacks in terms of both the computational work and the communication load. The main idea of our schemes is to reduce the size of secret-key in PS-scheme by using a public element g which has a specific structure. Consequently, our schemes are improved with respect to the computational work (which means the computational cost for "precomputation", "(on-line) signature generation" and "verification") and the data size such as a secret-key and a signature.Progress in cryptology - INDOCRYPT 2001 : Second International Conference on Cryptology in India, Chennai, India, December 16-20, 2001 : proceedings / C. Pandu Rangan, Cunsheng Ding (eds.)