For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Security of the Extended Fiat-Shamir Schemes
Kazuo OHTA Tatsuaki OKAMOTO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/01/25
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)>>
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.