Abstract
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.
Chapter PDF
Similar content being viewed by others
References
Brickell, E., Lee, P. and Yacobi, Y.: “Secure Audio Teleconference,” Advances in Cryptology-Crypto’87, Lecture Notes in Computer Science 293, 1988, pp.429–433
Fiat, A. and Shamir, A.: “How to Prove Yourself: Practical Solution to Identification and Signature Problems,” Advances in Cryptology-Crypto’86, Lecture Notes in Computer Science 263, 1987, pp.186–199
Feige, U., Fiat, A. and Shamir, A.: “Zero Knowledge Proofs of Identity,” Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp.210–217
Goldwasser, S., Micali, S. and Rackoff, C.: “Knowledge Complexity of Interactive Proof Systems,” Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp.291–304
Goldreich, O., Micali, S. and Wigderson, A.: “Proofs that Yield Nothing but Their Validity and a Methdology of Cryptographic Protocol Design,” Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986, pp.174–197
Guillou, L.C., and Quisquater, J.J.: “A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory,” Eurocrypt’88 Abstracts, 1988, pp.71–75
Guillou, L.C., and Quisquater, J.J.: “A Paradoxical Identity-Based Signature Scheme Resulting from Zero-Knowledge,” These Proceedings, 1988
Ohta, K. and Okamoto, T.: “Practical Extension of Fiat-Shamir Scheme,” Electron.Lett., 24, No. 15, 1988, pp. 955–956
Hardy, G.H. and Wright, E.M.: “An Introduction to the Theory of Numbers,” Fifth edition, Oxford University Press, New York, 1978
Rivest, R.L., Shamir, A. and Adleman, L.: “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communication of the ACM, Vol. 21, No. 2, 1978, pp.120–126
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ohta, K., Okamoto, T. (1990). A Modification of the Fiat-Shamir Scheme. In: Goldwasser, S. (eds) Advances in Cryptology — CRYPTO’ 88. CRYPTO 1988. Lecture Notes in Computer Science, vol 403. Springer, New York, NY. https://doi.org/10.1007/0-387-34799-2_17
Download citation
DOI: https://doi.org/10.1007/0-387-34799-2_17
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-97196-4
Online ISBN: 978-0-387-34799-8
eBook Packages: Springer Book Archive