CryptoDB
Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2024 |
| Abstract: | Sponge hashing is a novel class of cryptographic hash algorithms which underlies the current international hash function standard SHA3. 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 short digest which consists of a subset of the final output bits. While much is known about the post-quantum security of the sponge in the case when the block function is modeled as a random function or permutation, the case of invertible permutations 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 $\Omega(2^{n/2})$ many 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 oracle model. |
BibTeX
@inproceedings{crypto-2024-34265,
title={Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68391-6_7},
author={Joseph Carolan and Alexander Poremba},
year=2024
}