Weak zero-knowledge beyond the black-box barrier. (English) Zbl 1537.94045
Zero-knowledge protocols have posed a persistent challenge in cryptographic research, particularly concerning their round complexity. Despite concerted efforts, resolving this issue under standard assumptions has remained elusive, extending to related relaxations such as weak zero-knowledge and witness hiding.
In this paper, the authors introduce a novel non-black-box technique that surmounts the long-standing barrier associated with round complexity. Their contributions represent a significant leap forward in the field, offering the first protocols capable of transcending this threshold under standard assumptions.
The key findings of this work can be summarized as follows:
These core contributions can be summarized in the following theorems:
The paper is well structured, comprising four sections that comprehensively explore their findings. Beginning with an introductory section presenting fundamental concepts, the subsequent sections delve into specific aspects such as weak zero-knowledge against explainable verifiers, witness hiding with public verification, and considerations regarding explainable and malicious verifiers.
In summary, this paper marks an advancement in resolving the round complexity challenge in zero-knowledge protocols. The authors provide a substantial contribution by introducing innovative non-black-box techniques and achieving unprecedented results under standard assumptions.
In this paper, the authors introduce a novel non-black-box technique that surmounts the long-standing barrier associated with round complexity. Their contributions represent a significant leap forward in the field, offering the first protocols capable of transcending this threshold under standard assumptions.
The key findings of this work can be summarized as follows:
- 1.
- Weak zero-knowledge for NP in two messages: By leveraging quasi-polynomially secure fully homomorphic encryption alongside other standard primitives, the authors achieve a breakthrough in weak zero-knowledge protocols, reducing the communication to just two messages. This achievement underscores the efficacy of their non-black-box approach, complemented by the utilization of subexponentially secure one-way functions.
- 2.
- Weak zero-knowledge for NP in three messages: Building upon their two-message protocol, the authors extend their framework to encompass weak zero-knowledge in three messages under standard polynomial assumptions. This extension, facilitated by fully homomorphic encryption and factoring, underscores the robustness and versatility of their methodology.
- 3.
- Two-message witness-hiding protocol: Introducing a novel homomorphic trapdoor paradigm, the authors present a two-message witness-hiding protocol for languages in NP, featuring public verifiability. This achievement represents a non-black-box analogue of established trapdoor paradigms, showcasing the innovative nature of their approach.
These core contributions can be summarized in the following theorems:
- 1.
- Theorem 1: There exists a two-message weak-zero-knowledge argument for NP assuming subexponentially secure one-way functions and quasi-polynomially secure fully homomorphic encryption, random-self-reducible encryption, two-message witness-indistinguishable arguments, oblivious transfer, non-interactive commitments, and compute-and-compare obfuscation.
- 2.
- Theorem 2: Assuming polynomial hardness of the primitives in Theorem 1, as well as dense commitments, there exists a three-message weak-zero-knowledge argument for NP.
- 3.
- Theorem 3: There exists a two-message publicly verifiable witness-hiding argument for any language L in NP under the same (polynomial) assumptions as in Theorem 2 and witness encryption for L.
- 4.
- Theorem 4: Under the assumptions in Theorem 1 (respectively, Theorem 2), there exists a two-message (respectively, three-message) weak-zero-knowledge argument for NP against explainable verifiers.
The paper is well structured, comprising four sections that comprehensively explore their findings. Beginning with an introductory section presenting fundamental concepts, the subsequent sections delve into specific aspects such as weak zero-knowledge against explainable verifiers, witness hiding with public verification, and considerations regarding explainable and malicious verifiers.
In summary, this paper marks an advancement in resolving the round complexity challenge in zero-knowledge protocols. The authors provide a substantial contribution by introducing innovative non-black-box techniques and achieving unprecedented results under standard assumptions.
Reviewer: Ramsès Fernàndez-València (Barcelona)
MSC:
| 94A60 | Cryptography |
References:
| [1] | W. Aiello and J. H\aastad, Statistical zero-knowledge languages can be recognized in two rounds, J. Comput. Syst. Sci., 42 (1991), pp. 327-345, https://doi.org/10.1016/0022-0000(91)90006-Q. · Zbl 0732.68038 |
| [2] | W. Aiello, Y. Ishai, and O. Reingold, Priced oblivious transfer: How to sell digital goods, in EUROCRYPT, Lecture Notes in Comput. Sci. 2045, Springer, 2001, pp. 119-135. · Zbl 0981.94042 |
| [3] | P. Ananth and A. Jain, On secure two-party computation in three rounds, in Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, Proceedings, Part I, Springer, 2017, pp. 612-644, https://doi.org/10.1007/978-3-319-70500-2_21. · Zbl 1410.94040 |
| [4] | S. Badrinarayanan, S. Garg, Y. Ishai, A. Sahai, and A. Wadia, Two-message witness indistinguishability and secure computation in the plain model from new assumptions, in Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, Proceedings, Part III, Springer, 2017, pp. 275-303, https://doi.org/10.1007/978-3-319-70700-6_10. · Zbl 1417.94040 |
| [5] | B. Barak, How to go beyond the black-box simulation barrier, in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2001, Newport Beach, CA, 2001, pp. 106-115, https://doi.org/10.1109/SFCS.2001.959885. |
| [6] | B. Barak, S. J. Ong, and S. Vadhan, Derandomization in cryptography, SIAM J. Comput., 37 (2007), pp. 380-400, https://doi.org/10.1137/050641958. · Zbl 1141.94008 |
| [7] | B. Barak and R. Pass, On the possibility of one-message weak zero-knowledge, in Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, Proceedings, Springer, 2004, pp. 121-132, https://doi.org/10.1007/978-3-540-24638-1_7. · Zbl 1197.94175 |
| [8] | M. Bellare, M. Jakobsson, and M. Yung, Round-optimal zero-knowledge arguments based on any one-way function, in Advances in Cryptology - EUROCRYPT ’97, International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, Proceedings, Springer, 1997, pp. 280-305, https://doi.org/10.1007/3-540-69053-0_20. |
| [9] | M. Bellare and A. Palacio, Towards plaintext-aware public-key encryption without random oracles, in Advances in Cryptology - ASIACRYPT, Lecture Notes in Comput. Sci. 3329, Springer, 2004, pp. 48-62. · Zbl 1094.94506 |
| [10] | M. Bellare, I. Stepanovs, and S. Tessaro, Contention in cryptoland: Obfuscation, leakage and UCE, in Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, Proceedings, Part II, Springer, 2016, pp. 542-564, https://doi.org/10.1007/978-3-662-49099-0_20. · Zbl 1382.94062 |
| [11] | F. Benhamouda and H. Lin, MR NISC: Multiparty reusable non-interactive secure computation, in Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, Proceedings, Part II, R. Pass and K. Pietrzak, eds., Lecture Notes in Computer Science 12551, Springer, 2020, pp. 349-378, https://doi.org/10.1007/978-3-030-64378-2_13. · Zbl 07496585 |
| [12] | N. Bitansky, Z. Brakerski, Y. T. Kalai, O. Paneth, and V. Vaikuntanathan, \(3\)-message zero knowledge against human ignorance, in Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, Proceedings, Part I, Springer, 2016, pp. 57-83, https://doi.org/10.1007/978-3-662-53641-4_3. · Zbl 1351.94027 |
| [13] | N. Bitansky, R. Canetti, A. Chiesa, S. Goldwasser, H. Lin, A. Rubinstein, and E. Tromer, The hunting of the SNARK, J. Cryptology, 30 (2017), pp. 989-1066, https://doi.org/10.1007/s00145-016-9241-9. · Zbl 1386.94066 |
| [14] | N. Bitansky, R. Canetti, O. Paneth, and A. Rosen, On the existence of extractable one-way functions, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 2014, New York, NY, 2014, pp. 505-514, https://doi.org/10.1145/2591796.2591859. · Zbl 1315.94059 |
| [15] | N. Bitansky, Y. T. Kalai, and O. Paneth, Multi-collision resistance: A paradigm for keyless hash functions, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, 2018, pp. 671-684, https://doi.org/10.1145/3188745.3188870. · Zbl 1427.94076 |
| [16] | N. Bitansky and H. Lin, One-message zero knowledge and non-malleable commitments, in Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, Proceedings, A. Beimel and S. Dziembowski, eds., Lecture Notes in Comput. Sci. 11240, Springer, 2018, pp. 209-234. · Zbl 1443.94047 |
| [17] | N. Bitansky and O. Paneth, Point obfuscation and 3-round zero-knowledge, in Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, Proceedings, Springer, 2012, pp. 190-208, https://doi.org/10.1007/978-3-642-28914-9_11. · Zbl 1303.94068 |
| [18] | N. Bitansky and O. Paneth, On non-black-box simulation and the impossibility of approximate obfuscation, SIAM J. Comput., 44 (2015), pp. 1325-1383, https://doi.org/10.1137/130928236. · Zbl 1380.94075 |
| [19] | N. Bitansky and O. Paneth, Zaps and non-interactive witness indistinguishability from indistinguishability obfuscation, in Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, Proceedings, Part II, Springer, 2015, pp. 401-427, https://doi.org/10.1007/978-3-662-46497-7_16. · Zbl 1319.94053 |
| [20] | M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. Comput., 13 (1984), pp. 850-864, https://doi.org/10.1137/0213053. · Zbl 0547.68046 |
| [21] | E. Boyle, S. Garg, A. Jain, Y. T. Kalai, and A. Sahai, Secure computation against adaptive auxiliary information, in Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, Proceedings, Part I, Springer, 2013, pp. 316-334, https://doi.org/10.1007/978-3-642-40041-4_18. · Zbl 1310.94132 |
| [22] | E. Boyle and R. Pass, Limits of extractability assumptions with distributional auxiliary input, in Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, Proceedings, Part II, Springer, 2015, pp. 236-261, https://doi.org/10.1007/978-3-662-48800-3_10. · Zbl 1375.94106 |
| [23] | Z. Brakerski and N. Döttling, Two-message statistically sender-private OT from LWE, in Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, Proceedings, Part II, A. Beimel and S. Dziembowski, eds., Lecture Notes in Comput. Sci. 11240, Springer, 2018, pp. 370-390, https://doi.org/10.1007/978-3-030-03810-6_14. · Zbl 1430.94060 |
| [24] | Z. Brakerski and V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, SIAM J. Comput., 43 (2014), pp. 831-871, https://doi.org/10.1137/120868669. · Zbl 1302.94037 |
| [25] | C. Brzuska and A. Mittelbach, Indistinguishability obfuscation versus multi-bit point obfuscation with auxiliary input, in Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., Proceedings, Part II, Springer, 2014, pp. 142-161, https://doi.org/10.1007/978-3-662-45608-8_8. · Zbl 1317.94093 |
| [26] | R. Canetti, O. Goldreich, S. Goldwasser, and S. Micali, Resettable zero-knowledge (extended abstract), in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC, ACM, 2000, pp. 235-244. · Zbl 1296.94093 |
| [27] | Y. Chen, V. Vaikuntanathan, and H. Wee, GGH15 beyond permutation branching programs: Proofs, attacks, and candidates, in Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, Proceedings, Part II, Springer, 2018, pp. 577-607, https://doi.org/10.1007/978-3-319-96881-0_20. · Zbl 1436.94046 |
| [28] | K. Chung, H. Lin, and R. Pass, Constant-round concurrent zero knowledge from P-certificates, in Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, 2013, pp. 50-59, https://doi.org/10.1109/FOCS.2013.14. |
| [29] | K.-M. Chung, E. Lui, and R. Pass, From weak to strong zero-knowledge and applications, in Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, Proceedings, Part I, Springer, 2015, pp. 66-92, https://doi.org/10.1007/978-3-662-46494-6_4. · Zbl 1354.94026 |
| [30] | K.-M. Chung, R. Pass, and K. Seth, Non-black-box simulation from one-way functions and applications to resettable security, SIAM J. Comput., 45 (2016), pp. 415-458, https://doi.org/10.1137/130946083. · Zbl 1384.94045 |
| [31] | R. Cramer and V. Shoup, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, in Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, Proceedings, Springer, 2002, pp. 45-64, https://doi.org/10.1007/3-540-46035-7_4. · Zbl 1055.94011 |
| [32] | Y. Deng, V. Goyal, and A. Sahai, 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, FOCS 2009, Atlanta, GA, 2009, pp. 251-260, https://doi.org/10.1109/FOCS.2009.59. · Zbl 1292.94054 |
| [33] | C. Dwork and M. Naor, Zaps and their applications, SIAM J. Comput., 36 (2007), pp. 1513-1543, https://doi.org/10.1137/S0097539703426817. · Zbl 1125.94019 |
| [34] | C. Dwork, M. Naor, O. Reingold, and L. J. Stockmeyer, Magic functions, J. ACM, 50 (2003), pp. 852-921, https://doi.org/10.1145/950620.950623. · Zbl 1325.68034 |
| [35] | U. Feige, D. Lapidot, and A. Shamir, Multiple non-interactive zero knowledge proofs under general assumptions, SIAM J. Comput., 29 (1999), pp. 1-28, https://doi.org/10.1137/S0097539792230010. · Zbl 1018.94015 |
| [36] | U. Feige and A. Shamir, Witness indistinguishable and witness hiding protocols, in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, 1990, pp. 416-426, https://doi.org/10.1145/100216.100272. |
| [37] | N. Fleischhacker, V. Goyal, and A. Jain, On the existence of three round zero-knowledge proofs, in Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, Proceedings, Part III, 2018, pp. 3-33, https://doi.org/10.1007/978-3-319-78372-7_1. · Zbl 1415.94430 |
| [38] | T. E. Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory, 31 (1985), pp. 469-472, https://doi.org/10.1109/TIT.1985.1057074. · Zbl 0571.94014 |
| [39] | S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits, SIAM J. Comput., 45 (2016), pp. 882-929, https://doi.org/10.1137/14095772X. · Zbl 1348.94048 |
| [40] | S. Garg, C. Gentry, A. Sahai, and B. Waters, Witness encryption and its applications, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC’13, Palo Alto, CA, 2013, pp. 467-476, https://doi.org/10.1145/2488608.2488667. · Zbl 1293.94066 |
| [41] | S. Garg and A. Srinivasan, Garbled protocols and two-round MPC from bilinear maps, in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, C. Umans, ed., IEEE Computer Society, 2017, pp. 588-599, https://doi.org/10.1109/FOCS.2017.60. |
| [42] | C. Gentry, A Fully Homomorphic Encryption Scheme, Ph.D. thesis, Stanford University, 2009, crypto.stanford.edu/craig. · Zbl 1304.94059 |
| [43] | C. Gentry, Fully homomorphic encryption using ideal lattices, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, 2009, pp. 169-178, https://doi.org/10.1145/1536414.1536440. · Zbl 1304.94059 |
| [44] | O. Goldreich and H. Krawczyk, On the composition of zero-knowledge proof systems, SIAM J. Comput., 25 (1996), pp. 169-192, https://doi.org/10.1137/S0097539791220688. · Zbl 0841.68112 |
| [45] | O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems, J. ACM, 38 (1991), pp. 691-728, https://doi.org/10.1145/116825.116852. · Zbl 0799.68101 |
| [46] | O. Goldreich and Y. Oren, Definitions and properties of zero-knowledge proof systems, J. Cryptology, 7 (1994), pp. 1-32, https://doi.org/10.1007/BF00195207. · Zbl 0791.94010 |
| [47] | S. Goldwasser and S. Micali, Probabilistic encryption, J. Comput. Syst. Sci., 28 (1984), pp. 270-299, https://doi.org/10.1016/0022-0000(84)90070-9. · Zbl 0563.94013 |
| [48] | S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof systems, SIAM J. Comput., 18 (1989), pp. 186-208, https://doi.org/10.1137/0218012. · Zbl 0677.68062 |
| [49] | R. Goyal, S. Hohenberger, V. Koppula, and B. Waters, A generic approach to constructing and proving verifiable random functions, in Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, Proceedings, Part II, Springer, 2017, pp. 537-566, https://doi.org/10.1007/978-3-319-70503-3_18. · Zbl 1412.94178 |
| [50] | R. Goyal, V. Koppula, and B. Waters, Lockable obfuscation, in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, 2017, pp. 612-621, https://doi.org/10.1109/FOCS.2017.62. · Zbl 1479.94321 |
| [51] | V. Goyal, Non-black-box simulation in the fully concurrent setting, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC’13, Palo Alto, CA, 2013, pp. 221-230, https://doi.org/10.1145/2488608.2488637. · Zbl 1293.94068 |
| [52] | J. Groth, R. Ostrovsky, and A. Sahai, New techniques for non-interactive zero-knowledge, J. ACM, 59 (2012), 11, https://doi.org/10.1145/2220357.2220358. · Zbl 1281.68102 |
| [53] | S. Hada and T. Tanaka, On the existence of 3-round zero-knowledge protocols, in Proceedings of the 18th Annual International Cryptology Conference, Lecture Notes in Comput. Sci. 1462, Springer, 1998, pp. 408-423. · Zbl 0931.94009 |
| [54] | I. Haitner, Y. Ishai, E. Kushilevitz, Y. Lindell, and E. Petrank, Black-box constructions of protocols for secure computation, SIAM J. Comput., 40 (2011), pp. 225-266, https://doi.org/10.1137/100790537. · Zbl 1236.94056 |
| [55] | I. Haitner, A. Rosen, and R. Shaltiel, On the (im)possibility of Arthur-Merlin witness hiding protocols, in Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, Proceedings, Springer, 2009, pp. 220-237, https://doi.org/10.1007/978-3-642-00457-5_14. · Zbl 1213.94106 |
| [56] | S. Halevi and Y. T. Kalai, Smooth projective hashing and two-message oblivious transfer, J. Cryptology, 25 (2012), pp. 158-193, https://doi.org/10.1007/s00145-010-9092-8. · Zbl 1272.94033 |
| [57] | J. H\aastad, R. Impagliazzo, L. A. Levin, and M. Luby, A pseudorandom generator from any one-way function, SIAM J. Comput., 28 (1999), pp. 1364-1396, https://doi.org/10.1137/S0097539793244708. · Zbl 0940.68048 |
| [58] | A. Jain, Y. T. Kalai, D. Khurana, and R. Rothblum, Distinguisher-dependent simulation in two rounds and its applications, in Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, Proceedings, Part II, J. Katz and H. Shacham, eds., Lecture Notes in Comput. Sci. 10402, Springer, 2017, pp. 158-189, https://doi.org/10.1007/978-3-319-63715-0_6. · Zbl 1409.94880 |
| [59] | Y. T. Kalai, G. N. Rothblum, and R. D. Rothblum, From obfuscation to the security of Fiat-Shamir for proofs, in Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, Proceedings, Part II, J. Katz and H. Shacham, eds., Lecture Notes in Comput. Sci. 10402, Springer, 2017, pp. 224-251, https://doi.org/10.1007/978-3-319-63715-0_8. · Zbl 1409.94881 |
| [60] | J. Katz, Which languages have 4-round zero-knowledge proofs?, J. Cryptology, 25 (2012), pp. 41-56, https://doi.org/10.1007/s00145-010-9081-y. · Zbl 1276.94016 |
| [61] | J. Katz and H. Shacham, eds., Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, Proceedings, Part II, Lecture Notes in Comput. Sci. 10402, Springer, 2017, https://doi.org/10.1007/978-3-319-63715-0. · Zbl 1369.94004 |
| [62] | A. Lombardi and L. Schaeffer, A Note on Key Agreement and Non-Interactive Commitments, Report 2019/279, Cryptology ePrint Archive, 2019, https://eprint.iacr.org/2019/279. |
| [63] | M. Naor, Bit commitment using pseudorandomness, J. Cryptology, 4 (1991), pp. 151-158. · Zbl 0731.68033 |
| [64] | M. Naor and B. Pinkas, Efficient oblivious transfer protocols, in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, S. R. Kosaraju, ed., ACM, SIAM, 2001, pp. 448-457, http://dl.acm.org/citation.cfm?id=365411.365502. · Zbl 0991.94045 |
| [65] | R. Ostrovsky, One-way functions, hard on average problems, and statistical zero-knowledge proofs, in Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, IL, IEEE Computer Society, 1991, pp. 133-138, https://doi.org/10.1109/SCT.1991.160253. |
| [66] | R. Ostrovsky and A. Wigderson, One-way functions are essential for non-trivial zero-knowledge, in Proceedings of the Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, IEEE Computer Society, 1993, pp. 3-17, https://doi.org/10.1109/ISTCS.1993.253489. · Zbl 0850.68165 |
| [67] | P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in Advances in Cryptology - EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, Proceedings, 1999, pp. 223-238, https://doi.org/10.1007/3-540-48910-X_16. · Zbl 0933.94027 |
| [68] | R. Pass, Simulation in quasi-polynomial time, and its application to protocol composition, in Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, Proceedings, 2003, pp. 160-176, https://doi.org/10.1007/3-540-39200-9_10. · Zbl 1037.68536 |
| [69] | M. Prabhakaran, A. Rosen, and A. Sahai, Concurrent zero knowledge with logarithmic round-complexity, in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2002, Vancouver, BC, Canada, 2002, pp. 366-375, https://doi.org/10.1109/SFCS.2002.1181961. |
| [70] | O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM, 56 (2009), 34, https://doi.org/10.1145/1568318.1568324. · Zbl 1325.68101 |
| [71] | A. Sahai and S. P. Vadhan, A complete promise problem for statistical zero-knowledge, in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, FL, 1997, pp. 448-457, https://doi.org/10.1109/SFCS.1997.646133. |
| [72] | D. Wichs and G. Zirdelis, Obfuscating compute-and-compare programs under LWE, in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, 2017, pp. 600-611, https://doi.org/10.1109/FOCS.2017.61. |
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.
