Multi-collision resistance: a paradigm for keyless hash functions. (English) Zbl 1427.94076
Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 671-684 (2018).
MSC:
| 94A60 | Cryptography |
References:
| [1] | Benny Applebaum. 2016. Cryptographic Hardness of Random Local Functions - Survey. Computational Complexity 25, 3 (2016), 667-722. s00037- 015- 0121- 8 10.1007/s00037-015-0121-8 · Zbl 1360.94293 |
| [2] | Benny Applebaum and Yoni Moses. 2013. |
| [3] | Locally Computable UOWHF with Linear Shrinkage. In Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings. 486-502. 3- 642- 38348- 9_29 · Zbl 1306.94022 |
| [4] | Boaz Barak. 2001. How to Go Beyond the Black-Box Simulation Barrier. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. 106-115. |
| [5] | Boaz Barak and Oded Goldreich. 2008. Universal Arguments and their Applications. SIAM J. Comput. 38, 5 (2008), 1661-1694. 10.1137/070709244 · Zbl 1180.94047 |
| [6] | Boaz Barak, Yehuda Lindell, and Salil P. Vadhan. 2003. Lower Bounds for Non-Black-Box Zero Knowledge. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings. 384- 393. · Zbl 1094.68024 |
| [7] | Mihir Bellare, Markus Jakobsson, and Moti Yung. 1997. 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, May 11-15, 1997, Proceeding. 280-305. |
| [8] | Mihir Bellare and Adriana Palacio. 2004. The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols. In Proceedings of the 24th Annual International Cryptology Conference. 273-289. · Zbl 1104.94043 |
| [9] | Mihir Bellare and Phillip Rogaway. 1993. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In CCS ’93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 3-5, 1993. 62-73. 10.1145/168588.168596 · Zbl 0968.90527 |
| [10] | Itay Berman, Akshay Degwekar, Ron D. Rothblum, and Prashant Nalini Vasudevan. 2017. Multi Collision Resistant Hash Functions and their Applications. Cryptology ePrint Archive, Report 2017/489. (2017). http://eprint.iacr.org/2017/489. · Zbl 1423.94050 |
| [11] | Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai, Omer Paneth, and Vinod Vaikuntanathan. 2016. 3-Message Zero Knowledge Against Human Ignorance. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I. 57-83. 10.1007/978-3-662-53641-4_3 · Zbl 1351.94027 |
| [12] | Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, and Eran Tromer. 2014. The Hunting of the SNARK. IACR Cryptology ePrint Archive 2014 (2014), 580. http://eprint.iacr.org/2014/580 · Zbl 1386.94066 |
| [13] | Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. 2013. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In STOC. 111-120. 10.1145/2488608.2488623 · Zbl 1293.68264 |
| [14] | Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen. 2014. On the existence of extractable one-way functions. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 505-514. 10.1145/2591796.2591859 · Zbl 1315.94059 |
| [15] | John Black, Phillip Rogaway, and Thomas Shrimpton. 2002. Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In Advances STOC’18, June 25-29, 2018, Los Angeles, CA, USA Nir Bitansky, Yael Tauman Kalai, and Omer Paneth in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings. 320-335. 540- 45708- 9_21 · Zbl 1026.94522 |
| [16] | Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, and Moni Naor. 1994. Checking the Correctness of Memories. Algorithmica 12, 2/3 (1994), 225-244. 10.1007/BF01185212 · Zbl 1323.68200 |
| [17] | Ran Canetti and Ronny Ramzi Dakdouk. 2009. Towards a Theory of Extractable Functions. In TCC. 595-613. 10.1007/978-3-642-00457-5_35 · Zbl 1213.94089 |
| [18] | Ran Canetti, Oded Goldreich, and Shai Halevi. 2004. The random oracle methodology, revisited. J. ACM 51, 4 (2004), 557-594. 10.1145/1008731.1008734 · Zbl 1204.94063 |
| [19] | 1008734 |
| [20] | Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, and Ran Raz. 2011. Memory Delegation. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings. 151-168. 3- 642- 22792- 9_9 · Zbl 1288.68005 |
| [21] | Joan Daemen and Vincent Rijmen. 2002. · Zbl 1065.94005 |
| [22] | The Design of Rijndael: AES - The Advanced Encryption Standard. Springer. · Zbl 1065.94005 |
| [23] | 3- 662- 04722- 4 |
| [24] | Ivan Damgård. 1989. |
| [25] | A Design Principle for Hash Functions. In Advances in Cryptology - CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. 416-427. org/10.1007/0- 387- 34805- 0_39 · Zbl 0724.68029 |
| [26] | Ivan Damgård, Torben P. Pedersen, and Birgit Pfitzmann. 1993. On the Existence of Statistically Hiding Bit Commitment Schemes and Fail-Stop Signatures. In Advances in Cryptology - CRYPTO ’93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings. 250- 265. 540- 48329- 2_22 · Zbl 0873.94017 |
| [27] | Giovanni Di Crescenzo and Helger Lipmaa. 2008. Succinct NP Proofs from an Extractability Assumption. In Proceedings of the 4th Conference on Computability in Europe. 175-185. 10.1007/978-3-540-69407-6_21 · Zbl 1142.68370 |
| [28] | Yevgeniy Dodis and John P. Steinberger. 2011. |
| [29] | Domain Extension for MACs Beyond the Birthday Barrier. In Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings. 323-342. org/10.1007/978- 3- 642- 20465- 4_19 · Zbl 1281.94022 |
| [30] | Cynthia Dwork and Moni Naor. 2007. |
| [31] | Zaps and Their Applications. SIAM J. Comput. 36, 6 (2007), 1513-1543. 10.1137/S0097539703426817 · Zbl 1125.94019 |
| [32] | Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer. 2003. Magic Functions. J. ACM 50, 6 (2003), 852-921. 10.1145/950620.950623 · Zbl 1325.68034 |
| [33] | Uriel Feige and Adi Shamir. 1989. Zero Knowledge Proofs of Knowledge in Two Rounds. In CRYPTO. 526-544. · Zbl 0722.68045 |
| [34] | Nils Fleischhacker, Vipul Goyal, and Abhishek Jain. 2018. On the Existence of Three Round Zero-Knowledge Proofs. IACR Cryptology ePrint Archive 2018 (2018), 167. http://eprint.iacr.org/2018/167 · Zbl 1415.94430 |
| [35] | Oded Goldreich and Ariel Kahan. 1996. |
| [36] | How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptology 9, 3 (1996), 167-190. 10.1007/BF00208001 · Zbl 0855.68085 |
| [37] | Oded Goldreich and Hugo Krawczyk. 1996. |
| [38] | On the Composition of Zero-Knowledge Proof Systems. SIAM J. Comput. 25, 1 (1996), 169-192. 10.1137/S0097539791220688 · Zbl 0841.68112 |
| [39] | Oded Goldreich, Silvio Micali, and Avi Wigderson. 1991. Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM 38, 3 (1991), 691-729. 10.1145/116825.116852 · Zbl 0799.68101 |
| [40] | Oded Goldreich and Yair Oren. 1994. |
| [41] | Definitions and properties of zeroknowledge proof systems. Journal of Cryptology 7, 1 (December 1994), 1-32. 10.1007/BF00195207 · Zbl 0791.94010 |
| [42] | Venkatesan Guruswami and Piotr Indyk. 2001. Expander-Based Constructions of Efficiently Decodable Codes. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. 658-667. |
| [43] | Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. 2009. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM 56, 4 (2009), 20:1-20:34. 10.1145/1538902.1538904 · Zbl 1325.68169 |
| [44] | Satoshi Hada and Toshiaki Tanaka. 1998. |
| [45] | On the Existence of 3-Round Zero-Knowledge Protocols. In Proceedings of the 18th Annual International Cryptology Conference. 408-423. · Zbl 0931.94009 |
| [46] | Iftach Haitner, Yuval Ishai, Eran Omri, and Ronen Shaltiel. 2015. Parallel Hashing via List Recoverability. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II. 173-190. 3- 662- 48000- 7_9 · Zbl 1351.94050 |
| [47] | Iftach Haitner, Omer Reingold, Salil P. Vadhan, and Hoeteck Wee. 2009. Inaccessible entropy. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009. 611-620. 10.1145/1536414.1536497 · Zbl 1304.94014 |
| [48] | Shai Halevi and Silvio Micali. 1996. Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing. In Advances in Cryptology - CRYPTO ’96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings. 201-215. 540- 68697- 5_16 · Zbl 1329.94061 |
| [49] | Russell Impagliazzo and Michael Luby. 1989. One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract). In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989. 230-235. 10.1109/SFCS.1989.63483 |
| [50] | Antoine Joux. 2004. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. In Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings. 306-316. 3- 540- 28628- 8_19 · Zbl 1104.68043 |
| [51] | Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. 2014. |
| [52] | How to delegate computations: the power of no-signaling proofs. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 485-494. 10.1145/2591796.2591809 · Zbl 1315.68135 |
| [53] | Yael Tauman Kalai, Guy N. Rothblum, and Ron D. Rothblum. 2017. |
| [54] | From Obfuscation to the Security of Fiat-Shamir for Proofs. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part II. 224-251. 3- 319- 63715- 0_8 · Zbl 1409.94881 |
| [55] | Jonathan Katz. 2012. Which Languages Have 4-Round Zero-Knowledge Proofs? J. Cryptology 25, 1 (2012), 41-56. 010- 9081y 10.1007/s00145-010-9081-y · Zbl 1276.94016 |
| [56] | Joe Kilian. 1992. |
| [57] | A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada. 723-732. 10.1145/129712.129782 |
| [58] | Joe Kilian. 1994. On the complexity of Bounded-Interaction and Noninteractive Zero-Knowledge Proofs. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994. 466-477. org/10.1109/SFCS.1994.365744 10.1109/SFCS.1994.365744 |
| [59] | Ilan Komargodski, Moni Naor, and Eylon Yogev. 2017. Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions. Cryptology ePrint Archive, Report 2017/486. (2017). http://eprint.iacr.org/2017/486. · Zbl 1423.94079 |
| [60] | Ilan Komargodski, Moni Naor, and Eylon Yogev. 2017. White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. Electronic Colloquium on Computational Complexity (ECCC) 24 (2017), 15. https://eccc. weizmann.ac.il/report/2017/015 · Zbl 1473.68096 |
| [61] | Leonid A. Levin. 1987. One-way functions and pseudorandom generators. Combinatorica 7, 4 (1987), 357-363. 10.1007/BF02579323 · Zbl 0641.68061 |
| [62] | Ueli M. Maurer and Stefano Tessaro. 2007. Domain Extension of Public Random Functions: Beyond the Birthday Barrier. In Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings. 187-204. 3- 540- 74143- 5_11 · Zbl 1215.94063 |
| [63] | Nimrod Megiddo and Christos H. Papadimitriou. 1991. |
| [64] | On Total Functions, Existence Theorems and Computational Complexity. Theor. Comput. Sci. 81, 2 (1991), 317-324. 3975(91)90200-L 10.1016/0304-3975(91)90200-L · Zbl 0731.68036 |
| [65] | Ralph C. Merkle. 1989. A Certified Digital Signature. In Advances in Cryptology - CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. 218-238. 1007/0- 387- 34805- 0_21 |
| [66] | Silvio Micali. 2000. Computationally Sound Proofs. SIAM J. Comput. 30, 4 (2000), 1253-1298. 10.1137/S0097539795284959 · Zbl 1009.68053 |
| [67] | Moni Naor. 2003. On Cryptographic Assumptions and Challenges. In Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. 96-109. 3- 540- 45146- 4_6 · Zbl 1122.94391 |
| [68] | Rafail Ostrovsky and Ivan Visconti. 2012. Simultaneous Resettability from Collision Resistance. Electronic Colloquium on Computational Complexity (ECCC) 19 (2012), 164. http://eccc.hpiweb.de/report/2012/164 |
| [69] | Rafael Pass. 2003. Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition. In EUROCRYPT. 160-176. · Zbl 1037.68536 |
| [70] | Phillip Rogaway. 2006. Formalizing Human Ignorance. In Progressin Cryptology - VIETCRYPT 2006, First International Conferenceon Cryptology in Vietnam, Hanoi, Vietnam, September 25-28, 2006, Revised Selected Papers. 211-228. 10.1007/11958239_14 · Zbl 1295.94138 |
| [71] | Dominique Unruh. 2007. |
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.
