Non-black-box simulation from one-way functions and applications to resettable security. (English) Zbl 1384.94045
Summary: The simulation paradigm, introduced by Goldwasser, Micali, and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, B. Barak [42nd IEEE symposium on foundations of computer science. FOCS 2001, Los Alamitos, CA: IEEE Computer Society, 106–115 (2001), see Zbl 1017.68001 for the entire collection] introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by N. Bitansky and O. Paneth [FOCS 2012, Piscataway, NJ, IEEE, 2012, pp. 223–232; see also SIAM J. Comput. 44, No. 5, 1325–1383 (2015; Zbl 1380.94075)] instead requires the existence of an oblivious transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge arguments.
MSC:
| 94A60 | Cryptography |
References:
| [1] | B. Barak, {\it How to go beyond the black-box simulation barrier}, in FOCS 2001, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 106-115. |
| [2] | B. Barak and O. Goldreich, {\it Universal arguments and their applications}, in Computational Complexity, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 162-171. |
| [3] | B. Barak, O. Goldreich, S. Goldwasser, and Y. Lindell, {\it Resettably sound zero-knowledge and its applications}, in FOCS 2002 IEEE Computer Society, Los Alamitos, CA, 2002, pp. 116-125. |
| [4] | B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang, {\it On the (im)possibility of obfuscating programs. J. ACM}, 59 (2012), 6. · Zbl 1281.68118 |
| [5] | M. Blum, {\it How to prove a theorem so no one else can claim it}, in Proceedings of the International Congress of Mathematicians, International Congress of Mathematicians, Berkely, CA, 1986, pp. 1444-1451. · Zbl 0672.94005 |
| [6] | N. Bitansky and Omer Paneth, {\it From the impossibility of obfuscation to a new non-black-box simulation technique}, in FOCS, 2012, IEEE, Piscataway, NJ, 2012, pp. 223-232. · Zbl 1303.94068 |
| [7] | N. Bitansky and Omer Paneth, {\it On the impossibility of approximate obfuscation and applications to resettable cryptography}, in STOC 2013, ACM, New York, 2013, pp. 241-250. · Zbl 1293.94055 |
| [8] | R. Canetti, O. Goldreich, S. Goldwasser, and S. Micali, {\it Resettable zero-knowledge} (extended abstract), in STOC 2000, ACM, New York, 2000, pp. 235-244. · Zbl 1296.94093 |
| [9] | R. Canetti, O. Goldreich, and S. Halevi, {\it On the random-oracle methodology as applied to length-restricted signature schemes}, in Theory of Cryptography, Lecture Notes in Comput. Sci. 2951, Springer, New York, 2004, pp. 40-57. · Zbl 1197.94215 |
| [10] | R. Canetti, J. Kilian, E. Petrank, and A. Rosen, {\it Black-box concurrent zero-knowledge requires \(\tildeω(\log n)\) rounds}, in STOC 2001, ACM, New York, 2001, pp. 570-579. · Zbl 1317.68064 |
| [11] | K.-M. Chung, R. Ostrovsky, R. Pass, and I. Visconti, {\it Simultaneous resettability from one-way functions}, in FOCS 2013, IEEE, Piscataway, NJ, 2013, pp. 60-69. |
| [12] | K.-M. Chung, R. Pass, and K. Seth, {\it Non-black-box simulation from one-way functions and applications to resettable security}, in Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 231-240. · Zbl 1293.94059 |
| [13] | Y. Deng, V. Goyal, and A. Sahai, {\it Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy}, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 251-260. · Zbl 1292.94054 |
| [14] | U. Feige and A. Shamir, {\it Witness indistinguishable and witness hiding protocols}, in STOC 1990, ACM, New York, 1990, pp. 416-426. |
| [15] | 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 |
| [16] | S. Goldwasser and S. Micali, {\it Probabilistic encryption}, J. Comput. Syst. Sci., 28 (1984), pp. 270-299. · Zbl 0563.94013 |
| [17] | S. Goldwasser, S. Micali, and C. Rackoff, {\it The knowledge complexity of interactive proof systems}, SIAM J. Comput., 18 (1989), pp. 186-208. · Zbl 0677.68062 |
| [18] | O. Goldreich, S. Micali, and A. Wigderson, {\it Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems}, J. ACM, 38 (1991), pp. 691-729. · Zbl 0799.68101 |
| [19] | O. Goldreich and Y. Oren, {\it Definitions and properties of zero-knowledge proof systems}, J. Cryptology, 7 (1994), pp. 1-32. · Zbl 0791.94010 |
| [20] | O. Goldreich, {\it Foundations of Cryptography}, Cambridge University Press, Cambridge, 2001. · Zbl 1007.94016 |
| [21] | 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 |
| [22] | J. Kilian, {\it A note on efficient zero-knowledge proofs and arguments}, in Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing ACM, New York, 1992, pp. 723-732. |
| [23] | Y. Lindell, {\it Lower bounds for concurrent self composition}, in Theory of Cryptography, Lecutre Notes in comput. Sci. 2951, Springer, New York, 2004, pp. 203-222. · Zbl 1176.94069 |
| [24] | H. Lin and R. Pass, {\it Constant-round non-malleable commitments from any one-way function}, in STOC 2011, ACM, New York, 2011, pp. 705-714. · Zbl 1288.68022 |
| [25] | R. C. Merkle, {\it Digital Signature System and Method Based on a Conventional Encryption Function}, November 14, 1989. U.S. Patent 4,881,264. |
| [26] | S. Micali, {\it Computationally sound proofs}, SIAM J. Comput., 30 (2000), pp. 1253-1298. · Zbl 1009.68053 |
| [27] | M. Naor, {\it Bit commitment using pseudorandomness}, J. Cryptology, 4 (1991), pp. 151-158. · Zbl 0731.68033 |
| [28] | M. Naor and M. Yung, {\it Universal one-way hash functions and their cryptographic applications}, in STOC 1989, ACM, New York, 1989, pp. 33-43. |
| [29] | R. Ostrovsky and A. Wigderson, {\it One-way functions are essential for non-trivial zero-knowledge}, in Theory and Computing Systems, 1993, IEEE Computer Society, Los Alamitos, CA, 2002, 1993, pp. 3-17. |
| [30] | R. Pass, {\it Bounded-concurrent secure multi-party computation with a dishonest majority}, in STOC 2004, ACM, New York, 2004, pp. 232-241. · Zbl 1192.68077 |
| [31] | R. Pass and A. Rosen, {\it New and improved constructions of non-malleable cryptographic protocols}, in STOC 2005, ACM, New York, 2005, pp. 533-542. · Zbl 1192.94104 |
| [32] | M. Prabhakaran, A. Rosen, and A. Sahai, {\it Concurrent zero knowledge with logarithmic round-complexity}, in FOCS 2002, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 366-375. |
| [33] | R. Pass, W.-L. D. Tseng, and D. Wikström, {\it On the composition of public-coin zero-knowledge protocols}, in CRYPTO 2009, Springer, Berlin, 2009, pp. 160-176. · Zbl 1252.94092 |
| [34] | R. Pass, W.-L. D. Tseng, and D. Wikström, {\it On the composition of public-coin zero-knowledge protocols}, SIAM J. Comput., 40 (2011), pp. 1529-1553. · Zbl 1235.68077 |
| [35] | J. Rompel, {\it One-way functions are necessary and sufficient for secure signatures}, 1990 STOC 1990, ACM, New York, pp. 387-394. |
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.
