Mryntu

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 $|xranglerightarrow(-1)^f(x)|xrangle$. 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!

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, 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.