1
$\begingroup$

I'm taking a quantum computing course in which, for our final project, we must create a proof-of-concept implementation of Grover Search for finding hash collisions up to a difficulty (similar to blockchain).

I need a (relatively) simple hash function. As this will be running on a quantum simulator, I'm limited in the number of qubits which I can simulate. Ideally, the hash function should output 8-bits for arbitrarily sized input, should not be crackable (trivially, for example by hand), and should be relatively fast as the hash function (although classical) will be implemented with quantum logic gates.

I was considering an 8-bit version of SHA-1, however I'm not sure how adaptable SHA-1 would be in this situation.

$\endgroup$
  • $\begingroup$ Relevant crypto.stackexchange.com/q/50322/36960 $\endgroup$ – DannyNiu Mar 16 at 6:08
  • 1
    $\begingroup$ You could use a Keccak sponge with 1-bit words: 25 total bits of state, so you can use a sponge of capacity 8 for an 8-bit hash. $\endgroup$ – Squeamish Ossifrage Mar 16 at 13:41
  • 1
    $\begingroup$ Double Pearson, as in two Pearson hashes with separate tables, xored together. A lot simpler than inventing something weird & wonderful. $\endgroup$ – Paul Uszak Mar 16 at 23:06
  • $\begingroup$ An 8-bit hash is going to be very susceptible to collision search: probability that there is a collision among outputs for 20 random distinct inputs is >53% (except if the input space is small and the hash chosen to minimize that probability). $\endgroup$ – fgrieu Mar 18 at 8:07
  • $\begingroup$ Note proof-of-work is usually about finding (partial) preimages, which Grover's algorithm can do ‘faster’ than classical preimage search. But for collision search (which is less constrained than partial preimage search, and thus is easier), while one can apply Grover with BHT or tweak Grover with Ambianis, it's not clear that even if you count qubits and qubit operations as if they were bits and bit operations you could get anything cheaper than a classical collision search anyway. So I took this question to be about preimage search, not collision search. $\endgroup$ – Squeamish Ossifrage Mar 18 at 16:28
-1
$\begingroup$

I suggest a derivative of the Pearson Hash. It can be implemented in two forms, using separate and independent random permutation tables as:-

  1. h1 = T1[h1 ^ x[i]] , h2 = T2[h2 ^ x[i]] and then finally h = h1 ^ h2,
  2. h = T1[h ^ x[i]] followed immediately by h = T2[h ^ x[i]] so effectively you run one lookup table into the other,

where h is the final 8 bit output. The latter form seems cooler and simpler. Construct the tables T1 and T2 any way you can think of. Both methods result in good uniform output distribution with the expected $ 1 \over e $ rate of collisions. It's well proven, not trivially crackable and extremely simple if you can spare the requisite 512 bytes for the two tables.


Note. As pointed out in the comments, free qubits may be scarce. Might it be possible to ignore the storage requirements for the hash algorithm itself? If the experiment is for "Grover Search for finding hash collisions", you're primarily looking at techniques for breaking the hash not making it. Therefore I would be minded to exclude any storage requirement for making the hashes from the total simulated qubit count. Only you can decide if this is an appropriate compromise.

$\endgroup$
  • 3
    $\begingroup$ The storage requirements may pose a challenge for implementation on a (simulated) quantum computer in which qubits are scarce. $\endgroup$ – Squeamish Ossifrage Mar 18 at 3:36
  • 1
    $\begingroup$ The whole point of Grover's algorithm is that it can find preimages faster by querying quantum superpositions of the hash function. If you, say, had the quantum computer ask a classical computer to evaluate the hash on a single point at a time, Grover's algorithm wouldn't work. $\endgroup$ – Squeamish Ossifrage Mar 18 at 14:52
  • $\begingroup$ @SqueamishOssifrage Not what I said. I said add extra qubits to the quantum simulator resources to cater for the hash algorithm, but then don't count them for the purposes of the experiment. I'm suggesting: let quantum gate count($Pearson^2$) = 0. There ain't no classical computer in my cunning/madcap scheme. $\endgroup$ – Paul Uszak Mar 18 at 15:15
  • 2
    $\begingroup$ There is a classical computer involved here - the OP is simulating a quantum computer on a classical one. Simulating a quantum computer on a classical computer requires exponential cost. You can't simply tell the simulator "don't count these qubits against the cost" any more than you can do the same for brute forcing a key on a classical computer. Even if you could, I'm not sure doing so in regards to publishing the result would be ethical. $\endgroup$ – Ella Rose Mar 18 at 15:21
  • $\begingroup$ This is the function I ended up implementing. Compared with SHA-3, Pearson required far fewer qubits as the hash can be built in-place in an output register as opposed to a state register which is used to build the hash in a separate output register. Additionally, the Keccak spec requires ancillary bits for the permutation function which put us well over the resource limit. Our Grover implementation runs at least 4 times as fast with a double Pearson hash as compared to SHA-3. $\endgroup$ – DontTurnAround Mar 19 at 11:12
2
$\begingroup$

Your requirement that it not be trivially crackable is already violated by the premise of an 8-bit hash function: for a uniform random 8-bit function it takes an expected 128 trials to find a preimage, and the time for an expected ${\sim}256/n^3$ trials to find the first preimage among $n$ targets if parallelized $n^2$ ways. But maybe you meant there are no better-than-generic attacks on it. (Similarly, it takes an expected ~20 trials to find a collision, although it's not clear that collisions are relevant to your application.)

You could use a Keccak sponge with 1-bit words for a total 25-bit state, 12 rounds, and an 8-bit capacity. I don't know 25-bit Keccak admits better-than-generic attacks—I wouldn't be surprised if it did—but it is structurally the same as the Keccak permutation used in SHA-3, with 64-bit words, 1600-bit state, 24 rounds, and either $4\lambda$- or $2\lambda$-bit capacity (respectively, for the fixed-size hashes like SHA3-256, or for the extendable-output functions like SHAKE128) for $\lambda$-bit collision resistance and $2\lambda$-bit preimage resistance.

Right now, the best collision attacks on 1600-bit Keccak[1][2] seem to be limited to 6 rounds, which justified the use of 12 rounds for KangarooTwelve. There are newer attacks on other aspects of Keccak, but 12 seems like a reasonable margin—and it's not clear that those attacks would be cheaper than Grover. If all you want is preimage resistance, a $\lambda$-bit capacity should suffice for $\lambda$-bit preimage resistance.

One nice thing about a permutation-based sponge like Keccak is that the fixed permutation is, well, a permutation, so it will require no ancillary qubits to implement; the only need for ancillary qubits will arise from xoring the message into the state to hash it.

$\endgroup$
  • $\begingroup$ Thank you for your suggestion @SqueamishOssifrage. SHA-3 was the first thing I attempted to implement after seeing your original comment on my post. Unfortunately 25 bits of internal state is far too much as runtime essentially becomes asymptotic around 18 qubits on most hardware. I attempted to implement a variant of SHA-3 which still relied on a Keccak sponge but utilized a quantum XOR shift PRNG as the permuting function. While runnable, it was still far too slow and additionally the simpler permutation function resulted in poor hash distribution. $\endgroup$ – DontTurnAround Mar 19 at 11:08

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.