Enhancements of Trapdoor Permutations
Tóm tắt
We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich, Foundation of Cryptography: Basic Applications, 2004) and doubly enhanced trapdoor permutation (Goldreich, Computational Complexity: A Conceptual Perspective, 2011) as well as intermediate notions (Rothblum, A Taxonomy of Enhanced Trapdoor Permutations, 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, but they address natural concerns that may arise also in other applications of trapdoor permutations. We clarify why these enhancements are needed in such applications, and show that they actually suffice for these needs.
Tài liệu tham khảo
W. Alexi, B. Chor, O. Goldreich, C.P. Schnorr, RSA/Rabin functions: certain parts are as hard as the whole. SIAM J. Comput. 17, 194–209 (1988). Preliminary version in 25th FOCS, 1984
M. Bellare, M. Yung, Certifying permutations: noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptol. 9, 149–166 (1996)
M. Blum, A. De Santis, S. Micali, G. Persiano, Non-interactive zero-knowledge proof systems. SIAM J. Comput. 20(6), 1084–1118 (1991). (Considered the journal version of [4])
M. Blum, P. Feldman, S. Micali, Non-interactive zero-knowledge and its applications, in 20th ACM Symposium on the Theory of Computing (1988), pp. 103–112. See [3]
M. Blum, S. Goldwasser, An efficient probabilistic public-key encryption scheme which hides all partial information, in Crypto84. Lecture Notes in Computer Science, vol. 196 (Springer, Berlin, 1984), pp. 289–302
M. Blum, S. Micali, How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13, 850–864 (1984). Preliminary version in 23rd FOCS, 1982
W. Diffie, M.E. Hellman, New directions in cryptography. IEEE Trans. Inf. Theory IT-22, 644–654 (1976)
S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985). Extended abstract in Crypto’82
U. Feige, D. Lapidot, A. Shamir, Multiple non-interactive zero-knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (1999). Preliminary version in 31st FOCS, 1990
Y. Gertner, S. Kannan, T. Malkin, O. Reingold, M. Viswanathan, The relationship between public key encryption and oblivious transfer, in Proceedings of the 41st annual symposium on foundations of computer science (FOCS) (2000)
O. Goldreich, A uniform complexity treatment of encryption and zero-knowledge. J. Cryptol. 6(1), 21–53 (1993)
O. Goldreich, Secure Multi-party Computation. Available from the author’s homepage, 1998 (revised 2001)
O. Goldreich, Foundation of Cryptography: Basic Tools (Cambridge University Press, Cambridge, 2001)
O. Goldreich, Foundation of Cryptography: Basic Applications (Cambridge University Press, Cambridge, 2004)
O. Goldreich, Computational Complexity: A Conceptual Perspective (Cambridge University Press, Cambridge, 2008)
O. Goldreich, Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: the state of the art, in Lecture Notes in Computer Science, vol. 6650 (Springer, Berlin, 2011), pp. 406–421
O. Goldreich, L.A. Levin, Hard-core predicates for any one-way function, in 21st ACM Symposium on the Theory of Computing (1989), pp. 25–32
O. Goldreich, S. Micali, A. Wigderson, How to play any mental game—a completeness theorem for protocols with honest majority, in 19th ACM Symposium on the Theory of Computing (1987), pp. 218–229
S. Goldwasser, S. Micali. Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984). Preliminary version in 14th STOC, 1982
S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 186–208 (1989). Preliminary version in 17th STOC, 1985
I. Haitner, Implementing oblivious transfer using a collection of dense trapdoor permutations, in 1st theory of cryptography conference. Lecture Notes in Computer Science, vol. 2951 (Springer, Berlin, 2004)
M.O. Rabin, Digitalized signatures and public key functions as intractable as factoring. MIT/LCS/TR-212 (1979)
R. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public key cryptosystems. Commun. ACM 21, 120–126 (1978)
R. Rothblum, A taxonomy of enhanced trapdoor permutations. ECCC, TR10-145, 2010
A.C. Yao, Theory and application of trapdoor functions, in 23rd IEEE Symposium on Foundations of Computer Science (1982), pp. 80–91