Abstract
In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it controls a predetermined subset of the parties) or adaptive (meaning that it can choose to corrupt parties during the protocol execution and based on what it sees). In this paper, we study two fundamental questions relating to the basic zero-knowledge and oblivious transfer protocol problems:
-
Adaptive zero-knowledge proofs: We ask whether it is possible to construct adaptive zero-knowledge proofs (with unconditional soundness) for all of \(\mathcal{NP}\). Beaver (STOC [1996]) showed that known zero-knowledge proofs are not adaptively secure, and in addition showed how to construct zero-knowledge arguments (with computational soundness).
-
Adaptively secure oblivious transfer: All known protocols for adaptively secure oblivious transfer rely on seemingly stronger hardness assumptions than for the case of static adversaries. We ask whether this is inherent, and in particular, whether it is possible to construct adaptively secure oblivious transfer from enhanced trapdoor permutations alone.
We provide surprising answers to the above questions, showing that achieving adaptive security is sometimes harder than achieving static security, and sometimes not. First, we show that assuming the existence of one-way functions only, there exist adaptive zero-knowledge proofs for all languages in \(\mathcal{NP}\). In order to prove this, we overcome the problem that all adaptive zero-knowledge protocols known until now used equivocal commitments (which would enable an all-powerful prover to cheat). Second, we prove a black-box separation between adaptively secure oblivious transfer and enhanced trapdoor permutations. As a corollary, we derive a black-box separation between adaptively and statically secure oblivious transfer. This is the first black-box separation to relate to adaptive security and thus the first evidence that it is indeed harder to achieve security in the presence of adaptive adversaries than in the presence of static adversaries.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
D. Beaver, Adaptive zero knowledge and computational equivocation, in 28th STOC (1996), pp. 629–638
D. Beaver, Plug and play encryption, in Advances in Cryptology—Crypto ’97 (1997), pp. 75–89
D. Beaver, Adaptively secure oblivious transfer, in ASIACRYPT’98. LNCS, vol. 1514 (Springer, Berlin, 1998), pp. 300–314
M. Bellare, S. Micali, R. Ostrovsky, Perfect zero-knowledge in constant rounds, in 22nd STOC (1990), pp. 482–493
M. Blum, How to prove a theorem so no one else can claim it, in Proceedings of the International Congress of Mathematicians, USA, pp. 1444–1451
R. Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)
R. Canetti, M. Fischlin, Universally composable commitments, in CRYPTO 2001. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 19–40
R. Canetti, U. Feige, O. Goldreich, M. Naor, Adaptively secure multiparty computation, in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (1996), pp. 639–648
R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party computation, in 34th STOC (2002), pp. 494–503. Full version available at http://eprint.iacr.org/2002/140
Y. Chang, C. Hsiao, C. Lu, On the impossibilities of basing one-way permutations on central cryptographic primitives, in ASIACRYPT 2002 (2002), pp. 110–124
J.S. Coron, J. Patarin, Y. Seurin, The random oracle model and the ideal cipher model are equivalent, in CRYPTO 2008. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 1–20
I. Damgård, On the existence of bit commitment schemes and zero-knowledge proofs, in Proc. CRYPTO ’89 (1989), pp. 17–27
I. Damgård, Interactive hashing can simplify zero-knowledge protocol design without computational assumptions, in Proc. CRYPTO ’93 (1993), pp. 100–109
I. Damgård, J.B. Nielsen, Improved non-committing encryption schemes based on a general complexity assumption, in CRYPTO ’00 (2000), pp. 432–450
S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)
U. Feige, A. Shamir, Zero knowledge proofs of knowledge in two rounds, in CRYPTO’89. LNCS, vol. 435 (Springer, Berlin, 1989), pp. 526–544
M. Fischlin, On the impossibility of constructing NonInteractive StatisticallySecret protocols from any trapdoor OneWay function, in Cryptographers’ Track—RSA 2002. LNCS, vol. 2271 (Springer, Berlin, 2002), pp. 79–95
R. Gennaro, Y. Gertner, J. Katz, L. Trevisan, Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005)
Y. Gertner, S. Kannan, T. Malkin, O. Reingold, M. Viswanathan, The relationship between public key encryption and oblivious transfer, in The 41st FOCS (2000), pp. 325–335
Y. Gertner, T. Malkin, O. Reingold, On the impossibility of basing trapdoor functions on trapdoor predicates, in The 42nd FOCS (2001), pp. 126–135
Y. Gertner, T. Malkin, S. Myers, Towards a separation of semantic and CCA security for public key encryption, in The 4th TCC. LNCS, vol. 4392 (Springer, Berlin, 2007), pp. 434–455
O. Goldreich, Kahan, How to construct constant-round zero-knowledge proof systems for NP. J. Cryptol. 9(3), 167–190 (1996)
O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications (Cambridge University Press, Cambridge, 2004)
O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(1), 691–729 (1991)
C. Hazay, Y. Lindell, Efficient Secure Two-Party Protocols (Springer, Berlin, 2010)
R. Impagliazzo, M. Luby, One-way functions are essential for complexity based cryptography, in The 30th FOCS (1989), pp. 230–235
R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way permutations, in 21st STOC (1989), pp. 44–61
T. Itoh, Y. Ohta, H. Shizuya, A language-dependent cryptographic primitive. J. Cryptol. 10(1), 37–49 (1997)
B. Kapron, L. Malka, V. Srinivasan, A characterization of non-interactive instance-dependent commitment-schemes (NIC), in Proc. ICALP 2007 (2007), pp. 328–339
J. Kahn, M. Saks, C. Smyth, A dual version of Reimer’s inequality and a proof of Rudich’s conjecture, in Proceedings of the 15th Annual IEEE Conference on Computational Complexity, July 04–07, 2000, p. 98
J.H. Kim, D.R. Simon, P. Tetali, Limits on the efficiency of one-way permutation-based hash functions, in The 40th FOCS (1999), pp. 535–542
M. Luby, C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)
D. Micciancio, S. Vadhan, Statistical zero-knowledge proofs with efficient provers: lattice problems and more, in CRYPTO 2003. LNCS, vol. 2729 (Springer, Berlin, 2003), pp. 282–298
D. Micciancio, S.J. Ong, A. Sahai, S. Vadhan, Concurrent zero knowledge without complexity assumptions, in TCC 2006. LNCS, vol. 3876 (Springer, Berlin, 2006), pp. 1–20
M. Naor, Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991)
M.H. Nguyen, S. Vadhan, Zero knowledge with ecient provers, in Proc. 38th STOC (2006), pp. 287–295
S.J. Ong, S. Vadhan, An equivalence between zero knowledge and commitments, in The 5th TCC. LNCS, vol. 4948 (Springer, Berlin, 2008), pp. 482–500
S. Rudich, The use of interaction in public cryptosystems (Extended Abstract), in CRYPTO 91 (1991), pp. 242–251
O. Reingold, L. Trevisan, S.P. Vadhan, Notions of reducibility between cryptographic primitives, in The 1st TCC. LNCS, vol. 2951 (Springer, Berlin, 2004), pp. 1–20
D.R. Simon, Finding collisions on a one-way street: Can secure Hash functions be based on general assumptions? in EUROCRYPT 1998. LNCS, vol. 1403 (Springer, Berlin, 1998), pp. 334–345
S.P. Vadhan, An unconditional study of computational zero knowledge, in The 45th FOCS (2004), pp. 176–185
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Ran Canetti
This research was supported by the israel science foundation (grant No. 781/07).
Rights and permissions
About this article
Cite this article
Lindell, Y., Zarosim, H. Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer. J Cryptol 24, 761–799 (2011). https://doi.org/10.1007/s00145-010-9072-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-010-9072-z