Timeline for Does Grover's algorithm really threaten symmetric security proofs?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 19, 2023 at 19:45 | comment | added | Dan Staley | Another important difference between quantum and parallel classical computing is how they scale - $n$ quantum bits effectively create $2^n$ states that would need $2^n$ threads to be processed in parallel in a classical system. | |
| Oct 19, 2023 at 6:18 | comment | added | linkhyrule5 | @VictorEspinoza While a complete explanation of why quantum is not just parallel classical doesn't fit in a comment, you can get a decent intuition by noting that parallel algorithms generally (especially in practice) have limits on how efficiently information can be shared between threads; information transfer also tends to end up forcing bits of sequential code into your parallel algorithm. Quantum computers don't have this problem, at the cost of not being able to query an individual "thread". | |
| Oct 17, 2023 at 4:16 | vote | accept | Victor Espinoza | ||
| Oct 17, 2023 at 4:07 | comment | added | Victor Espinoza | Ok thank you, I know it is a little bit off from question but how this quantum = parallel understanding is wrong? You can calculate non-primitive recursion function better in a quantum computer than in a classical (This property it's what limits this kind of computers even in crypto), isn't it? | |
| Oct 17, 2023 at 4:00 | comment | added | Hhan | Still, the quantum cryptanalysis with assuming quantum encryption oracle is of theoretic interest. In some simple cases like Even-Mansour or FX, this kind of hypothetical quantum oracle attacks are discovered first, then the attacks using the classical encryption oracle + quantum implementation of them (without knowing key) better than classical bound follow, inspired by the quantum oracle attacks. | |
| Oct 17, 2023 at 3:56 | comment | added | Hhan | For the second comment, this is indeed a very important point, which I didn't include in my answer because it seems a little bit off from your question. But, yes, making quantum query to (say) AES without knowning secret key is somewhat strange assumption, because someone who holds the AES key is probably classical and may not answer quantumly. However, when we are applying Grover search on key with the quantum implementation of AES, with the knowledge of some plaintext-ciphertext pairs, the key space is indeed reduced by half-bit. | |
| Oct 17, 2023 at 3:52 | comment | added | Hhan | @VictorEspinoza If you want to understand the quantum query by something like classical parallel query, the important thing is that a single quantum query (potentially) evaluates every possible input simultaneously, which makes the situation complex and the classical bound useless. Also, I need to say that this quantum=parallel understanding is a usual mistake. | |
| Oct 17, 2023 at 2:09 | comment | added | Victor Espinoza | So, the quantum query attack is really possible on classical AES or we are talking about a Quantum AES implementation where you can do this quantum queries? | |
| Oct 17, 2023 at 2:09 | comment | added | Victor Espinoza | Ok, thank you for your answer one more question if may. I understand that the quantum query it's just a query using the inherent property of quantum superposition qubits which is just a parallel version of classical queries, isn't it? I have told that quantum computers are just big deal when you are talking about primitive recursive function or no-totally sequential algorithm, that's why a quantum computer cannot calculate the Ackerman function better than a classical computer. | |
| Oct 17, 2023 at 0:42 | history | answered | Hhan | CC BY-SA 4.0 |