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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Relevant crypto.stackexchange.com/q/50322/36960 $\endgroup$
    – DannyNiu
    Commented Mar 16, 2019 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
    Commented Mar 16, 2019 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
    Commented Mar 16, 2019 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 ♦
    Commented Mar 18, 2019 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
    Commented Mar 18, 2019 at 16:28

2 Answers 2

Reset to default
2
$\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.

Improve this answer
$\endgroup$
12
  • 4
    $\begingroup$ The storage requirements may pose a challenge for implementation on a (simulated) quantum computer in which qubits are scarce. $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 18, 2019 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
    Commented Mar 18, 2019 at 14:52
  • 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
    Commented Mar 18, 2019 at 15:21
  • 1
    $\begingroup$ @DontTurnAround The nonce and LFSR points lead me to wonder if what you went with is even a Pearson hash. Also, you may be interested in knowing that you can answer your own question; The information you included in those comments read more like a self-answer than kind of commentary on this answer. $\endgroup$
    – Ella Rose
    Commented Mar 19, 2019 at 15:53
  • 1
    $\begingroup$ I'm aware that I may answer my own questions, however I would not have chosen Pearson without Paul so I wanted to give him some credit. $\endgroup$
    – DontTurnAround
    Commented Mar 26, 2019 at 3:13
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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Mar 19, 2019 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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