New Constructions of Collapsing Hashes | SpringerLink
Skip to main content
Springer Nature Link
Log in

New Constructions of Collapsing Hashes

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2022 (CRYPTO 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13509))

Included in the following conference series:

Abstract

Collapsing is a post-quantum strengthening of collision resistance, needed to lift many classical results to the quantum setting. Unfortunately, the only existing standard-model proofs of collapsing hashes require LWE. We construct the first collapsing hashes from the quantum hardness of any one of the following problems:

  • LPN in a variety of low noise or high-hardness regimes, essentially matching what is known for collision resistance from LPN.

  • Finding cycles on exponentially-large expander graphs, such as those arising from isogenies on elliptic curves.

  • The “optimal” hardness of finding collisions in any hash function.

  • The polynomial hardness of finding collisions, assuming a certain plausible regularity condition on the hash.

As an immediate corollary, we obtain the first statistically hiding post-quantum commitments and post-quantum succinct arguments (of knowledge) under the same assumptions. Our results are obtained by a general theorem which shows how to construct a collapsing hash \(H'\) from a post-quantum collision-resistant hash function H, regardless of whether or not H itself is collapsing, assuming H satisfies a certain regularity condition we call “semi-regularity”.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    [Zha19b] gives a proof relative to a novel computational assumption, but it has been cryptanalyzed [Rob21].

References

  1. Alon, N., Benjamini, I., Lubetzky, E., Sodin, S.: Non-backtracking random walks mix faster. Commun. Contemp. Math. 9, 585–603 (2007)

    Article  MathSciNet  Google Scholar 

  2. Amos, R., Georgiou, M., Kiayias, A., Zhandry, M.: One-shot signatures and applications to hybrid quantum/classical authentication. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) 52nd ACM STOC, pp. 255–268. ACM Press (2020)

    Google Scholar 

  3. Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.: Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. In: Avanzi, R., Heys, H. (eds.) SAC 2016. LNCS, vol. 10532, pp. 317–337. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69453-5_18

    Chapter  Google Scholar 

  4. Alagic, G., Majenz, C., Russell, A., Song, F.: Quantum-access-secure message authentication via blind-unforgeability. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part III. LNCS, vol. 12107, pp. 788–817. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_27

    Chapter  Google Scholar 

  5. Ambainis, A., Rosmanis, A., Unruh, D.: Quantum attacks on classical proof systems: the hardness of quantum rewinding. In: 55th FOCS, pp. 474–483. IEEE Computer Society Press (2014)

    Google Scholar 

  6. Brassard, G., Høyer, P., Tapp, A.: Quantum algorithm for the collision problem. ACM SIGACT News (Cryptol. Column) 28, 14–19 (1997)

    Article  Google Scholar 

  7. Brakerski, Z., Lyubashevsky, V., Vaikuntanathan, V., Wichs, D.: Worst-case hardness for LPN and cryptographic hashing via code smoothing. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part III. LNCS, vol. 11478, pp. 619–635. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_21

    Chapter  Google Scholar 

  8. Chia, N.-H., Chung, K.-M., Yamakawa, T.: A black-box approach to post-quantum zero-knowledge in constant rounds. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part I. LNCS, vol. 12825, pp. 315–345. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_12

    Chapter  Google Scholar 

  9. Czajkowski, J., Hülsing, A., Schaffner, C.: Quantum indistinguishability of random sponges. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 296–325. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_11

    Chapter  Google Scholar 

  10. Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. J. Cryptol. 22(1), 93–113 (2009)

    Article  MathSciNet  Google Scholar 

  11. Chiesa, A., Ma, F., Spooner, N., Zhandry, M.: Post-quantum succinct arguments. In: Proceedings of FOCS (2021)

    Google Scholar 

  12. Couveignes, J.-M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291

  13. Cao, S., Xue, R.: The gap is sensitive to size of preimages: collapsing property doesn’t go beyond quantum collision-resistance for preimages bounded hash functions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, LNCS 13509, pp. 564–595 (2022)

    Google Scholar 

  14. Czajkowski, J.: Quantum indifferentiability of SHA-3. Cryptology ePrint Archive, Report 2021/192 (2021). https://eprint.iacr.org/2021/192

  15. Don, J., Fehr, S., Majenz, C., Schaffner, C.: Security of the Fiat-Shamir transformation in the quantum random-oracle model. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 356–383. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_13

    Chapter  MATH  Google Scholar 

  16. Fuchs, E., Lauter, K., Litman, M., Tran, A.: A cryptographic hash function from Markoff triples. Cryptology ePrint Archive, Report 2021/983 (2021). https://eprint.iacr.org/2021/983

  17. Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators (extended abstract). In: 29th FOCS, pp. 12–24. IEEE Computer Society Press (1988)

    Google Scholar 

  18. Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)

    Article  MathSciNet  Google Scholar 

  19. Hosoyamada, A., Sasaki, Yu.: Quantum collision attacks on reduced SHA-256 and SHA-512. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part I. LNCS, vol. 12825, pp. 616–646. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_22

    Chapter  Google Scholar 

  20. Lombardi, A., Ma, F., Spooner, N.: Post-quantum zero knowledge, revisited (or: how to do quantum rewinding undetectably). Cryptology ePrint Archive, Report 2021/1543 (2021). https://eprint.iacr.org/2021/1543

  21. Liu, Q., Zhandry, M.: Revisiting post-quantum Fiat-Shamir. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 326–355. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_12

    Chapter  Google Scholar 

  22. Petit, C., Lauter, K., Quisquater, J.-J.: Full cryptanalysis of LPS and Morgenstern hash functions. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 263–277. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85855-3_18

    Chapter  MATH  Google Scholar 

  23. Petit, C., Lauter, K.E., Quisquater, J.-J.: Cayley hashes: a class of efficient graph-based hash functions (2012)

    Google Scholar 

  24. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin,R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press (2005)

    Google Scholar 

  25. Roberts, B.: Security analysis of quantum lightning. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021, Part II. LNCS, vol. 12697, pp. 562–567. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_19

    Chapter  Google Scholar 

  26. Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145 (2006). https://eprint.iacr.org/2006/145

  27. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th FOCS, pp. 124–134. IEEE Computer Society Press (1994)

    Google Scholar 

  28. Tillich, J.-P., Zémor, G.: Hashing with SL\(_2\). In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 40–49. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48658-5_5

    Chapter  Google Scholar 

  29. Unruh, D.: Collapse-binding quantum commitments without random oracles. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 166–195. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_6

    Chapter  Google Scholar 

  30. Unruh, D.: Computationally binding quantum commitments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 497–527. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_18

    Chapter  Google Scholar 

  31. Unruh, D.: Collapsing sponges: post-quantum security of the sponge construction. Cryptology ePrint Archive, Report 2017/282 (2017). https://eprint.iacr.org/2017/282

  32. Van De Graaf, J.: Towards a formal definition of security for quantum protocols. Ph.D. thesis, CAN (1998). AAINQ35648

    Google Scholar 

  33. Watrous, J.: Zero-knowledge against quantum attacks. In: Kleinberg, J.M. (ed.) 38th ACM STOC, pp. 296–305. ACM Press (2006)

    Google Scholar 

  34. Yu, Y., Zhang, J., Weng, J., Guo, C., Li, X.: Collision resistant hashing from L-exponential learning parity with noise. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part II. LNCS, vol. 11922, pp. 3–24. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34621-8_1

    Chapter  Google Scholar 

  35. Zhandry, M.: How to record quantum queries, and applications to quantum indifferentiability. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 239–268. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_9

    Chapter  Google Scholar 

  36. Zhandry, M.: Quantum lightning never strikes the same state twice. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part III. LNCS, vol. 11478, pp. 408–438. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_14

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. NTT Research, Sunnyvale, USA

    Mark Zhandry

  2. Princeton University, Princeton, USA

    Mark Zhandry

Authors
  1. Mark Zhandry
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mark Zhandry .

Editor information

Editors and Affiliations

  1. New York University, New York, NY, USA

    Yevgeniy Dodis

  2. University of Florida, Gainesville, FL, USA

    Thomas Shrimpton

Rights and permissions

Reprints and permissions

Copyright information

© 2022 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Zhandry, M. (2022). New Constructions of Collapsing Hashes. In: Dodis, Y., Shrimpton, T. (eds) Advances in Cryptology – CRYPTO 2022. CRYPTO 2022. Lecture Notes in Computer Science, vol 13509. Springer, Cham. https://doi.org/10.1007/978-3-031-15982-4_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-15982-4_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-15981-7

  • Online ISBN: 978-3-031-15982-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation