Certifying Permutations: Noninteractive zero-knowledge based on any trapdoor permutation
Tóm tắt
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 noninteractive zero-knowledge. We point out that the elegant recent protocol of Feige, Lapidot, and Shamir for proving NP statements in noninteractive zero-knowledge requires an additional certification of the underlying trapdoor permutation, and suggest a method for certifying permutations which fills this gap.
Tài liệu tham khảo
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 Proceedings, Lecture Notes in Computer Science, Vol. 435, G. Brassard, ed., Springer-Verlag, Berlin, 1989.
M. Bellare and S. Micali. How To Sign Given any Trapdoor Permutation. Journal of the Association for Computing Machinery, Vol. 39, No. 1, January 1992, pp. 214–233.
M. Bellare, S. Micali, and R. Ostrovsky. The True Complexity of Statistical Zero-Knowledge. Proceedings of the 22nd ACM Annual Symposium on 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 ACM Annual Symposium on Theory of Computing, 1988.
G. Brassard and C. Crépeau. Non-Transitive Transfer of Confidence: a perfect Zero-Knowledge Interactive Protocol for SAT and Beyond. Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, 1986.
A. De Santis and M. Yung. Cryptographic Applications of the Metaproof and Many-prover Systems. Advances in Cryptology—Crypto 90 Proceedings, Lecture Notes in Computer Science, Vol. 537, A. J. Menezes and S. Vanstone, eds., Springer-Verlag, Berlin, 1990.
U. Feige, D. Lapidot, and A. Shamir. Multiple Non-Interactive Zero-Knowledge Based on a Single Random String. Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, 1990.
O. Goldreich and L. Levin. A Hard-Core Predicate for All One-Way Functions. Proceedings of the 21 st ACM Annual Symposium on 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.
O. Goldreich, S. Micali, and A. Wigderson. Proofs that Yield Nothing but Their Validity and a Methodology of Cryptographic Design. Journal of the Association for Computing Machinery, Vol. 38, No. 1, July 1991, pp. 691–729.
M. Naor and M. Yung. Public-Key Cryptosystems Secure Against Chosen-Ciphertext Attacks. Proceedings of the 22nd ACM Annual Symposium on 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.