Timeline for What is a simple 8-bit cryptographic hash function that I can use in a quantum simulation of Grover's algorithm?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 26, 2019 at 3:13 | comment | added | DontTurnAround | 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. | |
| Mar 26, 2019 at 3:13 | comment | added | DontTurnAround | @EllaRose The nonce is simply appended to the input and its existence is therefore opaque to the hash function. The LFSR is a deterministic psuedorandom function that serves as the permutation table for Pearson. Unfortunately, quantum computing requires all operations to be deterministically reversible. As such, you cannot simply index into a shuffled array to permute, you must take an input register to an output through only operations on itself as to do otherwise is not guaranteed to prevent the loss of quantum information. | |
| Mar 26, 2019 at 3:06 | comment | added | DontTurnAround | The time required to execute this LSFR is essentially constant, especially when considering the exponential runtime associated with simulating 25 state bits for the Keccak f-[1] function. | |
| Mar 26, 2019 at 3:06 | comment | added | DontTurnAround | @PaulUszak I didn't bother to fully comprehend the Keccak f-[b] permutation function since the register size requirements for input/output/state already made SHA3 quite slow without the correct permuting implementation, but if my understanding is correct the permuting function requires 25 additional state bits aside from the state of the sponge. In a quantum implementation, the LSFR is quite inexpensive as it is composed of 9 CNOT gates, which perform the traditional XOR operation in a superposition. | |
| Mar 19, 2019 at 15:53 | comment | added | Ella Rose | @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. | |
| Mar 19, 2019 at 12:05 | comment | added | Paul Uszak | @DontTurnAround My quantum competency ~ 0 so this might be laughingly obvious, but how can you afford the time/space for 2 no. dynamic LFSRs but not the static permutation tables? Do you simply subsume the time penalty for operating the LFSRs into the hash rate? | |
| Mar 19, 2019 at 11:16 | vote | accept | DontTurnAround | ||
| Mar 19, 2019 at 11:16 | comment | added | DontTurnAround | For those curious, I implemented Pearson in a hybrid fashion allowing the blockchain "message" (last block hash, transactions, etc) to be arbitrarily long and in a classical form. The nonce, which was appended to the end of the message, took the form of a 12-qubit register. Pearson hashing is applied in two rounds using two different quantum-implemented LFSRs as permuting functions. As the output is built in-place in an 8-qubit register, the entire implementation consumes at most 21 qubits simultaneously (12 for nonce, 8 for register, 1 for validating success via a Hash Difficulty Oracle). | |
| Mar 19, 2019 at 11:12 | comment | added | DontTurnAround | 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. | |
| Mar 18, 2019 at 15:21 | comment | added | Ella Rose | 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. | |
| Mar 18, 2019 at 15:15 | comment | added | Paul Uszak | @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. | |
| Mar 18, 2019 at 14:52 | comment | added | Squeamish Ossifrage | 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. | |
| Mar 18, 2019 at 12:12 | history | edited | Paul Uszak | CC BY-SA 4.0 | Addressing Squeamish's storage comment, perhaps(?) |
| Mar 18, 2019 at 3:36 | comment | added | Squeamish Ossifrage | The storage requirements may pose a challenge for implementation on a (simulated) quantum computer in which qubits are scarce. | |
| Mar 18, 2019 at 0:13 | history | answered | Paul Uszak | CC BY-SA 4.0 |