Abstract
Sponge hashing is a widely used class of cryptographic hash algorithms which underlies the current international hash function standard SHA-3. In a nutshell, a sponge function takes as input a bit-stream of any length and processes it via a simple iterative procedure: it repeatedly feeds each block of the input into a so-called block function, and then produces a digest by once again iterating the block function on the final output bits. While much is known about the post-quantum security of the sponge construction in the case when the block function is modeled as a random function or one-way permutation, the case of permutations allowing inverse queries, which more accurately models the construction underlying SHA-3, has so far remained a fundamental open problem.
In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the “double-sided zero-search” conjecture proposed by Unruh (eprint’ 2021) and show that finding zero-pairs in a random 2n-bit permutation requires at least \(\varOmega (2^{n/2})\) queries—and this is tight due to Grover’s algorithm. At the core of our proof lies a novel “symmetrization argument” which uses insights from the theory of Young subgroups. Second, we consider more general variants of the double-sided search problem and show similar query lower bounds for them. As an application, we prove the quantum one-wayness of the single-round sponge with invertible permutations in the quantum random permutation model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This was pointed out by Unruh [15].
- 2.
More formally, we require that \(\sigma \) and \(\omega \) map strings of the form \((x||0^n)\) to \((y||0^n)\), for \(x,y \in \{0,1\}^n\).
- 3.
\(W^K\) has a well-defined extension to all \(|f\rangle _F\) since we just need to XOR the string \((0^n||1^n)\) into the function output whenever the input is of the form \((x_1||y)\), for \(x_1 \in K\) and \(y \in \{0,1\}^n\).
- 4.
For two linear operators A and B, the commutator is defined as \([A,B] := AB-BA\).
- 5.
If the output is not of this form, simply output 0 (guess \(\varphi \) has no zero pairs).
References
Katz, J., Lindell, Y.: Introduction to Modern Cryptography, Second Edition. Chapman & Hall/CRC (2014)
Damgård, I.B.: Collision Free hash functions and public key signature schemes. In: Chaum, D., Price, W.L. (eds.) Advances in Cryptology — EUROCRYPT ’87, pp. 203–216. Springer, Berlin, Heidelberg (1988). https://doi.org/10.1007/3-540-39118-5_19
Merkle, R.C.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) Advances in Cryptology — CRYPTO ’87, pp. 369–378. Springer, Berlin, Heidelberg (1988). https://doi.org/10.1007/3-540-48184-2_32
Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) Advances in Cryptology — CRYPTO’ 89 Proceedings, pp. 218–238. Springer, New York, NY (2001). https://doi.org/10.1007/0-387-34805-0_21
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: The keccak sha-3 submission. Submission to NIST (Round 3) (2011)
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: Cryptographic sponge functions. Submission to NIST (Round 3) (2011)
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N. (ed.) Advances in Cryptology – EUROCRYPT 2008: 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings, pp. 181–197. Springer, Berlin, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_11
Freitag, C., Ghoshal, A., Komargodski, I.: Time-space tradeoffs for sponge hashing: attacks and limitations for short collisions. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part III, pp. 131–160. Springer Nature Switzerland, Cham (2022). https://doi.org/10.1007/978-3-031-15982-4_5
Akshima, Duan, X., Guo, S., Liu, Q.: On time-space lower bounds for finding short collisions in sponge hash functions. In: Rothblum, G., Wee, H. (eds.) Theory of Cryptography: 21st International Conference, TCC 2023, Taipei, Taiwan, November 29–December 2, 2023, Proceedings, Part III, pp. 237–270. Springer Nature Switzerland, Cham (2023). https://doi.org/10.1007/978-3-031-48621-0_9
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484–1509 (1997)
Regev, O.: An efficient quantum factoring algorithm (2024)
Czajkowski, J., Bruinderink, L.G., Hülsing, A., Schaffner, C., Unruh, D.: Post-quantum security of the sponge construction. Cryptology ePrint Archive, Paper 2017/771 (2017). https://eprint.iacr.org/2017/771
Czajkowski, J., Majenz, C., Schaffner, C., Zur, S.: Quantum lazy sampling and game-playing proofs for quantum indifferentiability. Cryptology ePrint Archive, Paper 2019/428 (2019). https://eprint.iacr.org/2019/428
Zhandry, M.: Redeeming reset indifferentiability and applications to post-quantum security. In: Tibouchi, M., Wang, H. (eds.) Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part I, pp. 518–548. Springer International Publishing, Cham (2021). https://doi.org/10.1007/978-3-030-92062-3_18
Unruh, D.: Compressed permutation oracles (and the collision-resistance of sponge/sha3). Cryptology ePrint Archive, Paper 2021/062 (2021). https://eprint.iacr.org/2021/062
Unruh, D.: Towards compressed permutation oracles. In: Guo, J., Steinfeld, R. (eds.) Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part IV, pp. 369–400. Springer Nature Singapore, Singapore (2023). https://doi.org/10.1007/978-981-99-8730-6_12
Zhandry, M.: How to record quantum queries, and applications to quantum indifferentiability. Cryptology ePrint Archive, Paper 2018/276 (2018). https://eprint.iacr.org/2018/276
Ambainis, A.: Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci. 64(4), 750–767 (2002)
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48, 778–797 (2001)
Ambainis, A., Hamburg, M., Unruh, D.: Quantum security proofs using semi-classical oracles. Cryptology ePrint Archive, Paper 2018/904 (2018). https://eprint.iacr.org/2018/904
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology – ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, pp. 41–69. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3
Rosmanis, A.: Tight bounds for inverting permutations via compressed oracle arguments (2022)
Alagic, G., Bai, C., Poremba, A., Shi, K.: On the two-sided permutation inversion problem (2023)
Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13–30 (1963)
Chvatal, V.: The tail of the hypergeometric distribution. Discret. Math. 25(3), 285–287 (1979)
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 1510–1523 (1997)
Alagic, G., Jeffery, S., Ozols, M., Poremba, A.: On quantum chosen-ciphertext attacks and learning with errors. Cryptography 4(4) (2020)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, (New York, NY, USA), pp. 212–219, Association for Computing Machinery (1996)
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46, 493–505 (1998)
Zalka, C.: Grover’s quantum searching algorithm is optimal. Phys. Rev. A 60, 2746–2751 (1999)
Dohotaru, C., Høyer, P.: Exact quantum lower bound for grover’s problem. Quantum Info. Comput. 9, 533–540 (2009)
James, T.R.: Theory of the Symmetric Group. Cambridge University Press, Encyclopedia of Mathematics and its Applications (1984)
Jones, A.R.: A combinatorial approach to the double cosets of the symmetric group with respect to young subgroups. Eur. J. Comb. 17(7), 647–655 (1996)
Wildon, M.: A model for the double cosets of young subgroups. University of London, Royal Holloway (2024)
Ambainis, A., Magnin, L., Roetteler, M., Roland, J.: Symmetry-assisted adversaries for quantum state generation In: 2011 IEEE 26th Annual Conference on Computational Complexity. IEEE (2011)
Alagic, G., Bai, C., Katz, J., Majenz, C.: Post-quantum security of the even-Mansour cipher. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology – EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 – June 3, 2022, Proceedings, Part III, pp. 458–487. Springer International Publishing, Cham (2022). https://doi.org/10.1007/978-3-031-07082-2_17
Acknowledgments
We thank Gorjan Alagic, Chen Bai, Luke Schaeffer and Kaiyan Shi for many useful discussions. JC acknowledges funding from the Department of Defense. AP is supported by the National Science Foundation (NSF) under Grant No. CCF-1729369.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 International Association for Cryptologic Research
About this paper
Cite this paper
Carolan, J., Poremba, A. (2024). Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14925. Springer, Cham. https://doi.org/10.1007/978-3-031-68391-6_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-68391-6_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-68390-9
Online ISBN: 978-3-031-68391-6
eBook Packages: Computer ScienceComputer Science (R0)