×

Finding collisions in interactive protocols – tight lower bounds on the round and communication complexities of statistically hiding commitments. (English) Zbl 1397.94068

Summary: We study the round and communication complexities of various cryptographic protocols. We give tight lower bounds on the round and communication complexities of any fully black-box reduction of a statistically hiding commitment scheme from one-way permutations and from trapdoor permutations. As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to D. R. Simon [Eurocrypt 1998, Lect. Notes Comput. Sci. 1403, 334–345 (1998; Zbl 0919.94032)] to the setting of interactive protocols and the reconstruction paradigm of R. Gennaro and L. Trevisan [Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), IEEE Press, Piscataway, NJ, 2000, p. 305–313].

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)

Citations:

Zbl 0919.94032
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] W. Aiello, Y. Ishai, and O. Reingold, {\it Priced oblivious transfer: How to sell digital goods}, in Advances in Cryptology–EUROCRYPT 2001, Lecture Notes in Comput. Sci. 2045, Springer, Berlin, 2001, pp. 119-135. · Zbl 0981.94042
[2] A. Beimel, Y. Ishai, E. Kushilevitz, and T. Malkin, {\it One-way functions are essential for single-server private information retrieval}, in Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1999, pp. 89-98. · Zbl 1346.68081
[3] M. Blum and S. Micali, {\it How to generate cryptographically strong sequences of pseudo-random bits}, SIAM J. Comput., 13 (1984), pp. 850-864. · Zbl 0547.68046
[4] J. Boyar, S. A. Kurtz, and M. W. Krentel, {\it A discrete logarithm implementation of perfect zero-knowledge blobs}, J. Cryptology, 2 (1990), pp. 63-76. · Zbl 0699.68035
[5] Z. Brakerski, J. Katz, G. Segev, and A. Yerukhimovich, {\it Limits on the power of zero-knowledge proofs in cryptographic constructions}, in Proceedings of the 8th Theory of Cryptography Conference, Lecture Notes in Comput. Sci. 6597, Springer, Berlin, 2011, pp. 559-578. · Zbl 1290.94049
[6] G. Brassard, D. Chaum, and C. Crépeau, {\it Minimum disclosure proofs of knowledge}, J. Comput. System Sci., 37 (1988), pp. 156-189. · Zbl 0656.68109
[7] C. Cachin, S. Micali, and M. Stadler, {\it Computationally private information retrieval with polylogarithmic communication}, in Advances in Cryptology–EUROCRYPT ’99, Lecture Notes in Comput. Sci. 1592, Springer, Berlin, 1999, pp. 402-414. · Zbl 0932.68042
[8] R. Canetti, J. Kilian, E. Petrank, and A. Rosen, {\it Black-box concurrent zero-knowledge requires (almost) logarithmically many rounds}, SIAM J. Comput., 32 (2002), pp. 1-47. · Zbl 1037.94004
[9] Y.-C. Chang, {\it Single database private information retrieval with logarithmic communication}, in Proceedings of the 9th Australasian Conference on Information Security and Privacy, 2004, pp. 50-61. · Zbl 1098.68038
[10] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, {\it Private information retrieval}, in Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 1995, pp. 41-50. · Zbl 0938.68625
[11] I. Damg\aard, T. P. Pedersen, and B. Pfitzmann, {\it On the existence of statistically hiding bit-commitment schemes and fail-stop signatures}, J. Cryptology, 10 (1997), pp. 163-194. · Zbl 0899.94011
[12] Y. Dodis, I. Haitner, and A. Tentes, {\it On the instantiability of hash-and-sign RSA signatures}, in Proceedings of the Ninth Theory of Cryptography Conference, Lecture Notes in Comput. Sci. 7194, Springer, Berlin, 2012, pp. 112-132. · Zbl 1303.94078
[13] C. Dwork, M. Naor, and A. Sahai, {\it Concurrent zero-knowledge}, J. ACM, 51 (2004), pp. 851-898. · Zbl 1125.94031
[14] S. Even, O. Goldreich, and A. Lempel, {\it A randomized protocol for signing contracts}, Comm. ACM, 28 (1985), pp. 637-647. · Zbl 0538.94011
[15] M. Fischlin, {\it On the impossibility of constructing non-interactive statistically-secret protocols from any trapdoor one-way function}, in Topics in Cryptology–The Cryptographers’ Track at the RSA Conference, Lecture Notes in Comput. Sci. 2271, Springer, Berlin, 2002, pp. 79-95. · Zbl 1048.94505
[16] R. Gennaro and L. Trevisan, {\it Lower bounds on the efficiency of generic cryptographic constructions}, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2000, pp. 305-313.
[17] R. Gennaro, Y. Gertner, and J. Katz, {\it Lower bounds on the efficiency of encryption and digital signature schemes}, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2003, pp. 417-425. · Zbl 1192.94095
[18] R. Gennaro, Y. Gertner, J. Katz, and L. Trevisan, {\it Bounds on the efficiency of generic cryptographic constructions}, SIAM J. Comput., 35 (2005), pp. 217-246. · Zbl 1087.94019
[19] C. Gentry and Z. Ramzan, {\it Single-database private information retrieval with constant communication rate}, in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 3580, Springer, Berlin, 2005, pp. 803-815. · Zbl 1084.68043
[20] Y. Gertner, S. Kannan, T. Malkin, O. Reingold, and M. Viswanathan, {\it The relationship between public key encryption and oblivious transfer}, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2000, pp. 325-335.
[21] O. Goldreich, {\it Foundations of Cryptography–Volume 1: Basic Tools}, Cambridge University Press, Cambridge, UK, 2001. · Zbl 1007.94016
[22] O. Goldreich, {\it Foundations of Cryptography–Volume 2: Basic Applications}, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1068.94011
[23] O. Goldreich and A. Kahan, {\it How to construct constant-round zero-knowledge proof systems for NP}, J. Cryptology, 9 (1996), pp. 167-190. · Zbl 0855.68085
[24] O. Goldreich and H. Krawczyk, {\it On the composition of zero-knowledge proof systems}, SIAM J. Comput., 25 (1996), pp. 169-192. · Zbl 0841.68112
[25] O. Goldreich, S. Goldwasser, and S. Micali, {\it On the cryptographic applications of random functions}, in Advances in Cryptology–CRYPTO ’84, Lecture Notes in Comput. Sci. 196, Springer, Berlin, 1984, pp. 276-288. · Zbl 1359.94599
[26] O. Goldreich, S. Goldwasser, and S. Micali, {\it How to construct random functions}, J. ACM, 33 (1986), pp. 792-807. · Zbl 0596.65002
[27] O. Goldreich, S. Micali, and A. Wigderson, {\it How to play any mental game or a completeness theorem for protocols with honest majority}, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1987, pp. 218-229.
[28] S. Goldwasser, S. Micali, and R. L. Rivest, {\it A digital signature scheme secure against adaptive chosen-message attacks}, SIAM J. Comput., 17 (1988), pp. 281-308. · Zbl 0644.94012
[29] S. D. Gordon, H. Wee, D. Xiao, and A. Yerukhimovich, {\it On the round complexity of zero-knowledge proofs based on one-way permutations}, in Progress in Cryptography–LATINCRYPT, Lecture Notes in Comput. Sci. 6212, Springer, Berlin, 2010, pp. 189-204. · Zbl 1285.94064
[30] S. Hada and T. Tanaka, {\it On the existence of 3-round zero-knowledge protocols}, in Advances in Cryptology–CRYPTO ’98, Lecture Notes in Comput Sci. 1462, Springer, Berlin, 1998, pp. 408-423. · Zbl 0931.94009
[31] I. Haitner, {\it Implementing oblivious transfer using collection of dense trapdoor permutations}, in Theory of Cryptography, First Theory of Cryptography Conference (TCC 2004), Lecture Notes in Comput. Sci. 2951, Springer, Berlin, 2004, pp. 394-409. · Zbl 1197.94189
[32] I. Haitner and T. Holenstein, {\it On the (im)possibility of key dependent encryption}, in Theory of Cryptography, Sixth Theory of Cryptography Conference (TCC 2009), Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 220-237. · Zbl 1213.94105
[33] I. Haitner and O. Reingold, {\it A new interactive hashing theorem}, J. Cryptology, 27 (2014), pp. 109-138. · Zbl 1350.94036
[34] I. Haitner and O. Reingold, {\it A new interactive hashing theorem}, in Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, IEEE Press, Piscataway, NJ, 2007, pp. 319-332. · Zbl 1350.94036
[35] I. Haitner, O. Horvitz, J. Katz, C.-Y. Koo, R. Morselli, and R. Shaltiel, {\it Reducing complexity assumptions for statistically-hiding commitment}, in Advances in Cryptology–EUROCRYPT 2005, Lecture Notes in Comput. Sci. 3494, Springer, Berlin, 2005, pp. 58-77. · Zbl 1137.94345
[36] I. Haitner, J. J. Hoch, O. Reingold, and G. Segev, {\it Finding collisions in interactive protocols–A tight lower bound on the round complexity of statistically hiding commitments}, in Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2007, pp. 669-679. · Zbl 1397.94068
[37] I. Haitner, J. J. Hoch, and G. Segev, {\it A linear lower bound on the communication complexity of single-server private information retrieval}, in Theory of Cryptography, Fifth Theory of Cryptography Conference (TCC 2008), Lecture Notes in Comput. Sci. 4948, Springer, Berlin, 2008, pp. 445-464. · Zbl 1162.94363
[38] I. Haitner, M.-H. Nguyen, S. J. Ong, O. Reingold, and S. Vadhan, {\it Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function}, SIAM J. Comput., 39 (2009), pp. 1153-1218\natexlaba. · Zbl 1195.94057
[39] I. Haitner, O. Reingold, S. Vadhan, and H. Wee, {\it Inaccessible entropy}, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2009, pp. 611-620\natexlabb. · Zbl 1304.94014
[40] I. Haitner, M. Mahmoody-Ghidary, and D. Xiao, {\it On basing constant-round statistically hiding commitments on np-hardness}, in Proceedings of the 24th Annual IEEE Conference on Computational Complexity, IEEE Press, Piscataway, NJ, 2010, pp. 76-87.
[41] J. H\aastad, R. Impagliazzo, L. A. Levin, and M. Luby, {\it A pseudorandom generator from any one-way function}, SIAM J. Comput., 28 (1999), pp. 1364-1396. · Zbl 0940.68048
[42] O. Horvitz and J. Katz, {\it Bounds on the efficiency of “black-box” commitment schemes}, in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 3580, Springer, Berlin, 2005, pp. 128-139. · Zbl 1081.94028
[43] R. Impagliazzo and S. Rudich, {\it Limits on the provable consequences of one-way permutations}, in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), 1989, pp. 44-61. · Zbl 0718.68042
[44] J. Kilian, {\it Founding cryptography on oblivious transfer}, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1988, pp. 20-31.
[45] J. Kilian, C. Rackoff, and E. Petrank, {\it Lower bounds for concurrent zero knowledge}, Combinatorica, 25 (2005), pp. 217-249. · Zbl 1084.68052
[46] J. H. Kim, D. R. Simon, and P. Tetali, {\it Limits on the efficiency of one-way permutation-based hash functions}, in Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 1999, pp. 535-542.
[47] T. Koshiba and Y. Seri, {\it Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme}, Reprot TR06-093, Electronic Colloquium on Computational Complexity, 2006. Available online at http://eccc.hpi-web.de/report/2006/093/
[48] E. Kushilevitz and R. Ostrovsky, {\it Replication is NOT needed: SINGLE database, computationally-private information retrieval}, in Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 1997, pp. 364-373.
[49] E. Kushilevitz and R. Ostrovsky, {\it One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval}, in Advances in Cryptology–EUROCRYPT 2000, Lecture Notes in Comput. Sci. 1807, Springer, Berlin, 2000, pp. 104-121. · Zbl 1082.68567
[50] Y. Lindell, {\it Parallel coin-tossing and constant-round secure two-party computation}, J. Cryptology, 16 (2003), pp. 143-184. · Zbl 1027.94011
[51] H. Lipmaa, {\it An oblivious transfer protocol with log-squared communication}, in Proceedings of the 8th International Conference on Information Security, Lecture Notes in Comput. Sci. 3650, Springer, Berlin, 2005, pp. 314-328. · Zbl 1159.68444
[52] M. Luby, {\it Pseudorandomness and Cryptographic Applications}, Princeton University Press, Princeton, NJ, 1996. · Zbl 0849.94017
[53] M. Luby and C. Rackoff, {\it How to construct pseudorandom permutations from pseudorandom functions}, SIAM J. Comput., 17 (1988), pp. 373-386. · Zbl 0644.94018
[54] M. Naor, {\it Bit commitment using pseudorandomness}, J. Cryptology, 4 (1991), pp. 151-158. · Zbl 0731.68033
[55] M. Naor and B. Pinkas, {\it Efficient oblivious transfer protocols}, in Proceedings of the 12th Annual Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2001, pp. 448-457. · Zbl 0991.94045
[56] M. Naor and M. Yung, {\it Universal one-way hash functions and their cryptographic applications}, in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1989, pp. 33-43.
[57] M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung, {\it Perfect zero-knowledge arguments for NP using any one-way permutation}, J. Cryptology, 11 (1998), pp. 87-108. · Zbl 0960.94016
[58] M.-H. Nguyen, S. J. Ong, and S. P. Vadhan, {\it Statistical zero-knowledge arguments for NP from any one-way function}, in Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2006, pp. 3-14.
[59] R. Ostrovsky and W. E. Skeith, {\it A Survey of Single Database PIR: Techniques and Applications}, Cryptology ePrint Archive, Report 2007/059, 2007. Available online from https://eprint.iacr.org/2007/059.pdf.
[60] R. Pass and M. Venkitasubramaniam, {\it Private coins versus public coins in zero-knowledge proof systems}, in Theory of Cryptography, Seventh Theory of Cryptography Conference (TCC 2010), Lecture Notes in Comput. Sci. 5978, Springer, Berlin, 2010, pp. 588-605. · Zbl 1274.94104
[61] K. Pietrzak, {\it Compression from collisions, or why CRHF combiners have a long output}, in Advances in Cryptology–CRYPTO 2008, Lecture Notes in Comput. Sci. 5157, Springer, Berlin, 2008, pp. 413-432. · Zbl 1183.68277
[62] K. Pietrzak, A. Rosen, and G. Segev, {\it Lossy functions do not amplify well}, in Theory of Cryptography, Ninth Theory of Cryptography Conference (TCC 2012), Lecture Notes in Comput. Sci. 7194, Springer, Berlin, 2012, pp. 458-475. · Zbl 1303.94098
[63] M. O. Rabin, {\it How to Exchange Secret by Oblivious Transfer}, Technical Report TR-81, Harvard University, Cambridge, MA, 1981.
[64] O. Reingold, L. Trevisan, and S. P. Vadhan, {\it Notions of reducibility between cryptographic primitives}, in Theory of Cryptography, First Theory of Cryptography Conference (TCC 2004), Lecture Notes in Comput. Sci. 2951, Springer, Berlin, 2004, pp. 1-20. · Zbl 1197.94202
[65] J. Rompel, {\it One-way functions are necessary and sufficient for secure signatures}, in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 387-394.
[66] A. Rosen, {\it A note on constant-round zero-knowledge proofs for NP}, in Theory of Cryptography, First Theory of Cryptography Conference (TCC 2004), Lecture Notes in Comput. Sci. 2951, Springer, Berlin, 2004, pp. 191-202. · Zbl 1197.94204
[67] A. Rosen and G. Segev, {\it Chosen-ciphertext security via correlated products}, in Theory of Cryptography, Sixth Theory of Cryptography Conference (TCC 2009), Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 419-436. · Zbl 1213.94130
[68] A. Rosen and G. Segev, {\it Chosen-ciphertext security via correlated products}, SIAM J. Comput., 39 (2010), pp. 3058-3088. · Zbl 1227.94063
[69] S. Rudich, {\it Limits on the Provable Consequences of One-Way Functions}, Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 1988. · Zbl 0718.68042
[70] A. Sahai and S. P. Vadhan, {\it A complete problem for statistical zero knowledge}, J. ACM, 50 (2003), pp. 196-249. · Zbl 1326.68165
[71] D. R. Simon, {\it Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?}, in Advances in Cryptology–EUROCRYPT ’98, Lecture Notes in Comput. Sci. 1403, Springer, Berlin, 1998, pp. 334-345. · Zbl 0919.94032
[72] A. Srinivasan and D. Zuckerman, {\it Computing with very weak random sources}, SIAM J. Comput., 28 (1999), pp. 1433-1459. · Zbl 0932.60008
[73] H. Wee, {\it One-way permutations, interactive hashing and statistically hiding commitments}, in Theory of Cryptography, Fourth Theory of Cryptography Conference (TCC 2007), Lecture Notes in Comput. Sci. 4392, Springer, Berlin, 2007, pp. 419-433. · Zbl 1129.94039
[74] S. Wolf and J. Wullschleger, {\it Oblivious transfer is symmetric}, in Advances in Cryptology —EUROCRYPT 2006, Lecture Notes in Comput. Sci. 4004, Springer, Berlin, 2006, pp. 222-232. · Zbl 1140.94372
[75] A. C. Yao, {\it How to generate and exchange secrets}, in Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 1986, pp. 162-167.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.