Document Open Access Logo

Correlation-Intractable Hash Functions via Shift-Hiding

Authors Alex Lombardi, Vinod Vaikuntanathan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.102.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Alex Lombardi
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Vinod Vaikuntanathan
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Lombardi, Alex: Research supported in part by an NDSEG Fellowship, by a Charles M. Vest Fellowship, and by the grants of the second author.
  • Vaikuntanathan, Vinod: Supported in part by NSF Grants CNS-1350619, CNS-1414119 and CNS-1718161, by DARPA under Agreement No. HR00112020023, by a Microsoft Faculty Fellowship, and by an MIT/IBM grant.

Acknowledgements

We thank an anonymous reviewer for pointing out that the [Chris Peikert and Sina Shiehian, 2019] hash function can likely also be shown to satisfy multi-input CI for shifted sum relations.

Cite As Get BibTex

Alex Lombardi and Vinod Vaikuntanathan. Correlation-Intractable Hash Functions via Shift-Hiding. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 102:1-102:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.102

Abstract

A hash function family ℋ is correlation intractable for a t-input relation ℛ if, given a random function h chosen from ℋ, it is hard to find x_1,…,x_t such that ℛ(x_1,…,x_t,h(x₁),…,h(x_t)) is true. Among other applications, such hash functions are a crucial tool for instantiating the Fiat-Shamir heuristic in the plain model, including the only known NIZK for NP based on the learning with errors (LWE) problem (Peikert and Shiehian, CRYPTO 2019).
We give a conceptually simple and generic construction of single-input CI hash functions from shift-hiding shiftable functions (Peikert and Shiehian, PKC 2018) satisfying an additional one-wayness property. This results in a clean abstract framework for instantiating CI, and also shows that a previously existing function family (PKC 2018) was already CI under the LWE assumption.
In addition, our framework transparently generalizes to other settings, yielding new results:
- We show how to instantiate certain forms of multi-input CI under the LWE assumption. Prior constructions either relied on a very strong "brute-force-is-best" type of hardness assumption (Holmgren and Lombardi, FOCS 2018) or were restricted to "output-only" relations (Zhandry, CRYPTO 2016). 
- We construct single-input CI hash functions from indistinguishability obfuscation (iO) and one-way permutations. Prior constructions relied essentially on variants of fully homomorphic encryption that are impossible to construct from such primitives. This result also generalizes to more expressive variants of multi-input CI under iO and additional standard assumptions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
Keywords
  • Cryptographic hash functions
  • correlation intractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Gilad Asharov and Gil Segev. Limits on the power of indistinguishability obfuscation and functional encryption. In Venkatesan Guruswami, editor, 56th FOCS, pages 191-209. IEEE Computer Society Press, October 2015. URL: https://doi.org/10.1109/FOCS.2015.21.
  2. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 1-18. Springer, Heidelberg, August 2001. URL: https://doi.org/10.1007/3-540-44647-8_1.
  3. Boaz Barak, Yehuda Lindell, and Salil P. Vadhan. Lower bounds for non-black-box zero knowledge. In 44th FOCS, pages 384-393. IEEE Computer Society Press, October 2003. URL: https://doi.org/10.1109/SFCS.2003.1238212.
  4. Mihir Bellare and Phillip Rogaway. Entity authentication and key distribution. In Douglas R. Stinson, editor, CRYPTO'93, volume 773 of LNCS, pages 232-249. Springer, Heidelberg, August 1994. URL: https://doi.org/10.1007/3-540-48329-2_21.
  5. Nir Bitansky, Omer Paneth, and Daniel Wichs. Perfect structure on the edge of chaos - trapdoor permutations from indistinguishability obfuscation. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part I, volume 9562 of LNCS, pages 474-502. Springer, Heidelberg, January 2016. URL: https://doi.org/10.1007/978-3-662-49096-9_20.
  6. Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 533-556. Springer, Heidelberg, May 2014. URL: https://doi.org/10.1007/978-3-642-55220-5_30.
  7. Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, pages 280-300. Springer, Heidelberg, December 2013. URL: https://doi.org/10.1007/978-3-642-42045-0_15.
  8. Elette Boyle, Shafi Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In Hugo Krawczyk, editor, PKC 2014, volume 8383 of LNCS, pages 501-519. Springer, Heidelberg, March 2014. URL: https://doi.org/10.1007/978-3-642-54631-0_29.
  9. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Factoring and pairings are not necessary for io: Circular-secure lwe suffices. IACR Cryptology ePrint Archive, 2020:1024, 2020. Google Scholar
  10. Zvika Brakerski, Venkata Koppula, and Tamer Mour. NIZK from LPN and trapdoor hash via correlation intractability for approximable relations. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 738-767. Springer, Heidelberg, August 2020. URL: https://doi.org/10.1007/978-3-030-56877-1_26.
  11. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Rafail Ostrovsky, editor, 52nd FOCS, pages 97-106. IEEE Computer Society Press, October 2011. URL: https://doi.org/10.1109/FOCS.2011.12.
  12. Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs. Fiat-Shamir: from practice to theory. In Moses Charikar and Edith Cohen, editors, 51st ACM STOC, pages 1082-1090. ACM Press, June 2019. URL: https://doi.org/10.1145/3313276.3316380.
  13. Ran Canetti, Yilei Chen, and Leonid Reyzin. On the correlation intractability of obfuscated pseudorandom functions. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part I, volume 9562 of LNCS, pages 389-415. Springer, Heidelberg, January 2016. URL: https://doi.org/10.1007/978-3-662-49096-9_17.
  14. Ran Canetti, Yilei Chen, Leonid Reyzin, and Ron D. Rothblum. Fiat-Shamir and correlation intractability from strong KDM-secure encryption. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 91-122. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78381-9_4.
  15. Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited (preliminary version). In 30th ACM STOC, pages 209-218. ACM Press, May 1998. URL: https://doi.org/10.1145/276698.276741.
  16. Ran Canetti, Daniele Micciancio, and Omer Reingold. Perfectly one-way probabilistic hash functions (preliminary version). In 30th ACM STOC, pages 131-140. ACM Press, May 1998. URL: https://doi.org/10.1145/276698.276721.
  17. Aloni Cohen and Saleet Klein. The GGM function family is a weakly one-way family of functions. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part I, volume 9985 of LNCS, pages 84-107. Springer, Heidelberg, October / November 2016. URL: https://doi.org/10.1007/978-3-662-53641-4_4.
  18. Yevgeniy Dodis, Vinod Vaikuntanathan, and Daniel Wichs. Extracting randomness from extractor-dependent sources. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 313-342. Springer, Heidelberg, May 2020. URL: https://doi.org/10.1007/978-3-030-45721-1_12.
  19. Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer. Magic functions. In 40th FOCS, pages 523-534. IEEE Computer Society Press, October 1999. URL: https://doi.org/10.1109/SFFCS.1999.814626.
  20. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 186-194. Springer, Heidelberg, August 1987. URL: https://doi.org/10.1007/3-540-47721-7_12.
  21. Romain Gay and Rafael Pass. Indistinguishability obfuscation from circular security. Proceedings of STOC 2021, 2021. URL: https://eprint.iacr.org/2020/1010.
  22. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, 41st ACM STOC, pages 169-178. ACM Press, May / June 2009. URL: https://doi.org/10.1145/1536414.1536440.
  23. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 75-92. Springer, Heidelberg, August 2013. URL: https://doi.org/10.1007/978-3-642-40041-4_5.
  24. Oded Goldreich and Ron D. Rothblum. Enhancements of trapdoor permutations. Journal of Cryptology, 26(3):484-512, July 2013. URL: https://doi.org/10.1007/s00145-012-9131-8.
  25. Dennis Hofheinz and Bogdan Ursu. Dual-mode NIZKs from obfuscation. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, pages 311-341. Springer, Heidelberg, December 2019. URL: https://doi.org/10.1007/978-3-030-34578-5_12.
  26. Justin Holmgren and Alex Lombardi. Cryptographic hashing from strong one-way functions (or: One-way product functions and their applications). In Mikkel Thorup, editor, 59th FOCS, pages 850-858. IEEE Computer Society Press, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00085.
  27. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. Proceedings of STOC 2021, 2021. URL: https://eprint.iacr.org/2020/1003.
  28. Yael Tauman Kalai, Guy N. Rothblum, and Ron D. Rothblum. From obfuscation to the security of Fiat-Shamir for proofs. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, pages 224-251. Springer, Heidelberg, August 2017. URL: https://doi.org/10.1007/978-3-319-63715-0_8.
  29. Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 669-684. ACM Press, November 2013. URL: https://doi.org/10.1145/2508859.2516668.
  30. Alex Lombardi and Vinod Vaikuntanathan. Fiat-shamir for repeated squaring with applications to PPAD-hardness and VDFs. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 632-651. Springer, Heidelberg, August 2020. URL: https://doi.org/10.1007/978-3-030-56877-1_22.
  31. Alex Lombardi and Vinod Vaikuntanathan. Multi-input correlation-intractable hash functions via shift-hiding. IACR Cryptol. ePrint Arch., 2020:1378, 2020. Google Scholar
  32. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Technical report, Manubot, 2008. URL: https://git.dhimmel.com/bitcoin-whitepaper/.
  33. Chris Peikert and Sina Shiehian. Privately constraining and programming PRFs, the LWE way. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part II, volume 10770 of LNCS, pages 675-701. Springer, Heidelberg, March 2018. URL: https://doi.org/10.1007/978-3-319-76581-5_23.
  34. Chris Peikert and Sina Shiehian. Noninteractive zero knowledge for NP from (plain) learning with errors. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 89-114. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26948-7_4.
  35. Chris Peikert and Sina Shiehian. Constraining and watermarking PRFs from milder assumptions. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020, Part I, volume 12110 of LNCS, pages 431-461. Springer, Heidelberg, May 2020. URL: https://doi.org/10.1007/978-3-030-45374-9_15.
  36. Chris Peikert and Brent Waters. Lossy trapdoor functions and their applications. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 187-196. ACM Press, May 2008. URL: https://doi.org/10.1145/1374376.1374406.
  37. Hoeteck Wee and Daniel Wichs. Candidate obfuscation via oblivious LWE sampling. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part III, volume 12698 of LNCS, pages 127-156. Springer, Heidelberg, October 2021. URL: https://doi.org/10.1007/978-3-030-77883-5_5.
  38. Mark Zhandry. The magic of ELFs. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, pages 479-508. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53018-4_18.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact