Security of the Extended Fiat-Shamir Schemes

Kazuo OHTA  Tatsuaki OKAMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.1   pp.65-71
Publication Date: 1998/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
the Fiat-Shamir scheme,  zero-knowledge proof,  identification,  no-transferable information,  digital signatures,  

Full Text: PDF(673.4KB)>>
Buy this Article

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 theL-th roots modn (e. g.L=2 1020) when the factors ofnare unknown. We prove that the sequential version of our scheme is a zero knowledge interactive proof system and our parallel version reveals no transferable information if the factoring is difficult. 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.