5
$\begingroup$

In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|x\rangle\rightarrow(-1)^{f(x)}|x\rangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.

My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?

I would be very interested in what you think about it!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:

  1. AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965  
  2. MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377
  3. SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383

A general programmatic framework to express general oracles, synthesize them into quantum circuits (while keeping quantum memory bounded), and perform cost analyses does not exist to the best of my knowledge.

Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^{64}$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^{86}$ in the first paper above).

In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you for your answer. Perhaps you can help me with this: "Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a circuit that checks whether $f(x) = y$". The last part is obvious, but why does $f$ have to be called twice? $\endgroup$
    – user4961
    Apr 17, 2019 at 10:19
  • 2
    $\begingroup$ @QuantaMag The reason for the two calls is that first one has to evaluate $f$ (coherently, i.e., by way of a reversible circuit), then one evaluates the equality function, but then one has to uncompute the call to $f$. In other words: $$ \sum_x |x\rangle |0\rangle |0\rangle \mapsto \sum_x |x\rangle |f(x)\rangle |0\rangle \mapsto \sum_x |x\rangle |f(x)\rangle |f(x)\stackrel{?}{=}y \rangle \mapsto \sum_x |x\rangle |0\rangle |f(x)\stackrel{?}{=} y\rangle $$ If you don't uncompute the call to $f(x)$, then there will be no interference possible. $\endgroup$
    – MartinQuantum
    Apr 20, 2019 at 7:28
  • 1
    $\begingroup$ @QuantaMag See also the answer quantumcomputing.stackexchange.com/a/5232/1828 to a related question about why we have to uncompute garbage. $\endgroup$
    – MartinQuantum
    Apr 20, 2019 at 7:32
  • $\begingroup$ This is great. Are there also storage requirements for applying Grover's algorithm directly to DES or AES? $\endgroup$
    – vy32
    Jan 30, 2021 at 22:37
  • $\begingroup$ @MartinQuantum 2. 3. cases are not encryption, they are hash algorithms, that I missed noticing when you answer this. $\endgroup$
    – kelalaka
    Mar 14, 2021 at 18:57

Your Answer

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