Is there a family of cryptographic hash functions that can be realized with a smallish depth quantum circuit?

Mark S

4/13/24, 2:32 PM

Certain number-theoretic cryptographic hash functions, such as $x^2\bmod N$, are known to be broken by a quantum computer. For example, one could use Shor's algorithm to factor $N$ into its product of two primes $(p_1,p_2)$, and use these primes to find collisions at-will. It's also been a long-open problem to find a hash that satisfies a version of Simon's promise; if such a hash could be found, then it would likewise be susceptible to easy inversion with a quantum computer.

Other common hash functions such as SHA256 have much less structure, and a quantum computer could likely only afford a "modest" polynomial speedup, via Grover's algorithm. Even still, estimates for the depth of a quantum circuit to evaluate even one call to Grover's oracle for a function like SHA256 is on the order of tens- to hundreds-of-thousand gates. With $f(x)$ being the SHA256 output of $n$-bit strings $x$; even to implement SHA256 to prepare $\frac{1}{\sqrt{2^n}}|x\rangle|f(x)\rangle$ with a quantum computer would likely require significant error correction. I'm not sure the details but I think the nature of SHA256's scrambling is difficult to realize with good quantum gates such as CCNOT gates or CSWAP gates.

It's this last point that I'm interested in. I'm looking for a nice family of cryptographic hash functions $f$ on $n$ bits (qubits) that are likely secure against a quantum computer, still requiring a brute-force Grover/birthday style attack to find collisions, but are nonetheless easy to evaluate in superposition with a quantum computer, i.e. having a shallow(ish) depth quantum circuit of CCNOT/CSWAP/CNOT gates.

For example, I'd like to see about preparing $\frac{1}{\sqrt{2^n}}|x\rangle|f(x)\rangle$ with a quantum computer, for a nice enough cryptographic function $f$ that is still designed with a small-depth quantum circuit. Are there any such hash functions commonly used, or is it straightforward to modify existing hash functions?

1 + 0

quantum-cryptanalysis

Score:3

Crypto

Daniel S

4/15/24, 4:30 AM

I'm not sure if I fully understand the premise of this question. It's relatively straightforward to construct a function for which Simon's promise holds, though such functions will be classically weak as hash functions. We simply choose a linear function $\ell:\mathbb F_2^n\to\mathbb F_2^n$ with a 1-dimensional nullspace generated by $\mathbf s$ and choose our favourite pseudo-random permutation on $\mathbf F_2^n$, say, $\pi(x)$ and define our hash function to be $\pi\circ\ell(x)$.

Also, SHA256 is not too burdensome to implement on a quantum computer in comparison to the circuits required for the modular exponentiations in Shor's algorithm. The roughly twelve thousand Toffoli-depth cited by Leet et al in T-depth reduction method for efficient SHA-256 quantum circuit construction is really quite modest. The pain for Grover comes with the number of iterations required and the fact that these iterations are highly non-parallelisable.

If this is still unpalatable, one can look to the functions that reached the finals of the recent NIST lightweight cryptography competition. Recent work by Lee et al in their paper Efficient Implementation of Lightweight Hash Functions on GPU and Quantum Computers for IoT Applications finds that the hash function from the winning ASCON family can be implemented with 35,136 qubits and a T-depth of 2,487. If one is prepared to look past hash functions approved for standardisation, the same paper notes that the Xoodyak hash function from the same competition (which has no especial weakness that I know of) can be implemented with 14,464 qubits and a T-depth of 760.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is there a family of cryptographic hash functions that can be realized with a smallish depth quantum circuit?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.