Abstract
In cryptographic protocols it is often necessary to verify/certify the “tools” in use. This work demonstrates certain subtleties in treating a family of trapdoor permutations in this context, noting the necessity to “check” certain properties of these functions. The particular case we illustrate is that of non-interactive zero-knowledge. We point out that the elegant recent protocol of Feige, Lapidot and Shamir for proving NP statements in non-interactive zero-knowledge requires an additional certification of the underlying trapdoor permutation, and suggest a certification method to fill this gap.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Bellare and S. Goldwasser. New Paradigms for Digital Signatures and Message Authentication Based on Non-Interactive Zero-Knowledge Proofs. Advances in Cryptology — CRYPTO 89. Lecture Notes in Computer Science, Vol. 435, Springer Verlag.
M. Bellare and S. Micali. How to Sign Given any Trapdoor Permutation. JACM, Vol. 39, No. 1, January 1992, pp. 214–233. (Preliminary version in Proceedings of the 20th STOC, 1988).
M. Bellare, S. Micali and R. Ostrovsky. The True Complexity of Statistical Zero-Knowledge. Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, 1990.
L. Blum, M. Blum, and M. Shub. A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing, Vol. 15, No. 2, May 1986, pp. 364–383.
M. Blum, A. De Santis, S. Micali, and G. Persiano, Non-Interactive Zero-Knowledge Proof Systems, SIAM Journal on Computing, Vol. 20, No. 6, December 1991, pp. 1084–1118.
M. Blum, P. Feldman, and S. Micali, Non-Interactive Zero-Knowledge Proof Systems and Applications, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988.
A. De Santis and M. Yung. Cryptographic Applications of the Metaproof and Many-prover Systems. Advances in Cryptology — CRYPTO 90. Lecture Notes in Computer Science, Vol. 537, Springer-Verlag.
U. Feige, D. Lapidot, and A. Shamir. Multiple Non-Interactive Zero-Knowledge based on a Single Random String. Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 1990.
O. Goldreich, S. Micali, and A. Wigderson. Proofs that Yield Nothing but their Validity and a Methodology of Cryptographic Design. JACM, July 1991. (Preliminary version in the 27th FOCS, 1986).
O. Goldreich and L. Levin. A Hard-Core Predicate for all One-Way Functions. Proceedings of the 21st Annual ACM Symposium on the Theory of Computing, 1989.
S. Goldwasser, S. Micali, and R. Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM Journal on Computing, Vol. 17, No. 2, April 1988, pp. 281–308.
M. Naor and M. Yung. Public Key Cryptosystems secure against chosen-ciphertext attacks. Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, 1990.
R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21, No. 2, February 1978, pp. 120–26.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Yung, M. (1993). Certifying Cryptographic Tools: The Case of Trapdoor Permutations. In: Brickell, E.F. (eds) Advances in Cryptology — CRYPTO’ 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48071-4_31
Download citation
DOI: https://doi.org/10.1007/3-540-48071-4_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57340-1
Online ISBN: 978-3-540-48071-6
eBook Packages: Springer Book Archive