A Modification of the Fiat-Shamir Scheme

Fiat-Shamir’s identification and signature scheme is efficient as well as provably secure, but it has a problem in that the transmitted information size and memory size cannot simultaneously be small. This paper proposes an identification and signature scheme which overcomes this problem. Our scheme is based on the difficulty of extracting the L-th roots mod n (e.g., L = 2 ∼ 1020) when the factors of n are unknown. We define some variations of no transferable information and prove that the sequential version of our scheme is a zero knowledge interactive proof system and our parallel version satisfies these variations of no transferable information under some conditions. The speed of our scheme’s typical implementation is at least one order of magnitude faster than that of the RSA scheme and is relatively slow in comparison with that of the Fiat-Shamir scheme.