Inaccessible Entropy II: IE Functions and Universal One-Way Hashing

by Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil Vadhan, and Hoeteck Wee

Theory of Computing, Volume 16(8), pp. 1-55, 2020

Bibliography with links to cited articles

[1]   Scott Ames, Rosario Gennaro, and Muthuramakrishnan Venkitasubramaniam: The generalized randomized iterate and its application to new efficient constructions of UOWHFs from regular one-way functions. In Proc. 18th Internat. Conf. Theory Appl. of Cryptology and Inform. Security (ASIACRYPT’12), pp. 154–171. Springer, 2012. [doi:10.1007/978-3-642-34961-4_11]

[2]   Kfir Barhum and Ueli Maurer: UOWHFs from OWFs: Trading regularity for efficiency. In Progress in Cryptology (LATINCRYPT’12), pp. 234–253. Springer, 2012. [doi:10.1007/978-3-642-33481-8_13]

[3]   Mihir Bellare and Phillip Rogaway: Collision-resistant hashing: Towards making UOWHFs practical. In Proc. 17th Ann. Internat. Cryptology Conf. (CRYPTO’97), pp. 470–484. Springer, 1997. [doi:10.1007/BFb0052256]

[4]   Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby: On the theory of average case complexity. J. Comput. System Sci., 44(2):193–219, 1992. Preliminary version in SCT’89. [doi:10.1016/0022-0000(92)90019-F]

[5]   Andrej Bogdanov and Luca Trevisan: Average-case complexity. Found. and Trends in Theoret. Comp. Sci., 2(1):1–106, 2006. [doi:10.1561/0400000004, arXiv:cs/0606037]

[6]   Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, and Hoeteck Wee: Amplifying collision resistance: A complexity-theoretic treatment. In Proc. 27th Ann. Internat. Cryptology Conf. (CRYPTO’07), pp. 264–283. Springer, 2007. [doi:10.1007/978-3-540-74143-5_15]

[7]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Wiley-Interscience, 2006. [doi:10.1002/047174882X]

[8]   Ronald Cramer and Victor Shoup: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput., 33(1):167–226, 2003. Preliminary version in CRYPTO’98. [doi:10.1137/S0097539702403773]

[9]   Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil Vadhan, and Hoeteck Wee: Universal one-way hash functions via inaccessible entropy. In Proc. 39th Ann. Internat. Conf. on Theory Appl. of Cryptographic Techniques (EUROCRYPT’10), pp. 616–637. Springer, 2010. [doi:10.1007/978-3-642-13190-5_31]

[10]   Iftach Haitner, Minh Nguyen, Shien Jin Ong, Omer Reingold, and Salil Vadhan: Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput., 39(3):1153–1218, 2009. [doi:10.1137/080725404]

[11]   Iftach Haitner, Omer Reingold, and Salil Vadhan: Efficiency improvements in constructing pseudorandom generators from one-way functions. SIAM J. Comput., 42(3):1405–1430, 2013. Preliminary version in STOC’10. [doi:10.1137/100814421]

[12]   Iftach Haitner, Omer Reingold, Salil Vadhan, and Hoeteck Wee: Inaccessible entropy. In Proc. 41st STOC, pp. 611–620. ACM Press, 2009. [doi:10.1145/1536414.1536497]

[13]   Iftach Haitner, Omer Reingold, Salil Vadhan, and Hoeteck Wee: Inaccessible entropy I: Inaccessible entropy generators and statistically hiding commitments from one-way functions, 2017. Preliminary version in STOC’09. [arXiv:2010.05586]

[14]   Iftach Haitner and Salil P. Vadhan: The many entropies in one-way functions. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography — Dedicated to Oded Goldreich, pp. 159–217. Springer, 2017. [doi:10.1007/978-3-319-57048-8_4, ECCC:TR17-084]

[15]   Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby: A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. Preliminary versions in STOC’89 and STOC’90. [doi:10.1137/S0097539793244708]

[16]   Thomas Holenstein and Renato Renner: On the randomness of independent experiments. IEEE Trans. Inform. Theory, 57(4):1865–1871, 2011. [doi:10.1109/TIT.2011.2110230, arXiv:cs/0608007]

[17]   Pavel Hubáček, Moni Naor, and Eylon Yogev: The journey from NP to TFNP hardness. In Proc. 8th Innovations in Theoret. Comp. Sci. (ITCS’17), pp. 60:1–60:21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.60]

[18]   Russell Impagliazzo and Leonid Levin: No better ways to generate hard NP instances than picking uniformly at random. In Proc. 31st FOCS, pp. 812–821. IEEE Comp. Soc., 1990. [doi:10.1109/FSCS.1990.89604]

[19]   Russell Impagliazzo and Michael Luby: One-way functions are essential for complexity based cryptography. In Proc. 30th FOCS, pp. 230–235. IEEE Comp. Soc., 1989. [doi:10.1109/SFCS.1989.63483]

[20]   Jonathan Katz and Chiu-Yuen Koo: On constructing universal one-way hash functions from arbitrary one-way functions. Cryptology ePrint Archive, Report 2005/328, 2005.

[21]   Leonid A. Levin: Average case complete problems. SIAM J. Comput., 15(1):285–286, 1986. Preliminary version in STOC’84. [doi:10.1137/0215020]

[22]   Ming Li and Paul M. B. Vitányi: Average case complexity under the universal distribution equals worst-case complexity. Inform. Process. Lett., 42(3):145–149, 1992. [doi:10.1016/0020-0190(92)90138-L]

[23]   Moni Naor and Moti Yung: Universal one-way hash functions and their cryptographic applications. In Proc. 21st STOC, pp. 33–43. ACM Press, 1989. [doi:10.1145/73007.73011]

[24]   Noam Nisan and David Zuckerman: Randomness is linear in space. J. Comput. System Sci., 52(1):43–52, 1996. [doi:10.1006/jcss.1996.0004]

[25]   Renato Renner and Stefan Wolf: Smooth Rényi entropy and applications. In Internat. Symp. Inform. Theory (ISIT’04), p. 233. IEEE Comp. Soc., 2004. [doi:10.1109/ISIT.2004.1365269]

[26]   John T. Rompel: One-way functions are necessary and sufficient for secure signatures. In Proc. 22nd STOC, pp. 387–394. ACM Press, 1990. [doi:10.1145/100216.100269]

[27]   John T. Rompel: Techniques for Computing With Low-Independence Randomness. Ph. D. thesis, Massachusetts Institute of Technology, 1990. ACM DL.

[28]   Alfredo De Santis and Moti Yung: On the design of provably secure cryptographic hash functions. In Proc. 19th Ann. Internat. Conf. on Theory Appl. of Cryptographic Techniques (EUROCRYPT’90), pp. 412–431. Springer, 1990. [doi:10.1007/3-540-46877-3_37]

[29]   Victor Shoup: A composition theorem for universal one-way hash functions. In Proc. 29th Ann. Internat. Conf. on Theory Appl. of Cryptographic Techniques (EUROCRYPT’00), pp. 445–452. Springer, 2000. [doi:10.1007/3-540-45539-6_32]

[30]   Salil Vadhan: Computational entropy. In Oded Goldreich, editor, Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 693–726. ACM Press, 2019. [doi:10.1145/3335741.3335767]

[31]   Leslie G. Valiant and Vijay V. Vazirani: NP is as easy as detecting unique solutions. Theoret. Comput. Sci., 47(1):85–93, 1986. Preliminary version in STOC’85. [doi:10.1016/0304-3975(86)90135-0]

[32]   Yu Yu, Dawu Gu, Xiangxue Li, and Jian Weng: (Almost) optimal constructions of UOWHFs from 1-to-1, regular one-way functions and beyond. In Proc. 35th Ann. Internat. Cryptology Conf. (CRYPTO’15), pp. 209–229. Springer, 2015. [doi:10.1007/978-3-662-48000-7_11]