4
$\begingroup$

I would like to start my question with a quote:

If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means would make it necessary to search 2 to the power 55 keys before hitting the correct one. This would take more than a year even if one billion keys were tried every second, by comparison, Grover's algorithm could find the key after only 185 searches.

This quote is from A Brief History of Quantum Computing By Simon Bone and Matias Castro

As a reader, I wonder how the authors got the magic number of 185. Unfortunately, that is not justified.

I thought about it myself. To calculate the number of iterations, the Grover algorithm uses this formula:

$$k=\frac{\pi}{4\cdot \sin^{-1}\left(\frac{1}{\sqrt{2^n}}\right)}-0.5$$

If I just do that for the number $2^{56}$ (DES keysize), then it follows that you need k iterations:

$$k=\frac{\pi}{4\cdot \sin^{-1}\left(\frac{1}{\sqrt{2^{56}}}\right)}-0.5=210828713$$

That's still not the number the authors suggest. Therefore I ask here, if anyone can imagine, how the authors came to the number. Is my consideration correct?

Assuming it were $2^{16}$, then you would need about 200 iterations, which are still not 185. I am not aware of a cryptographic system with a key length of $2^{16} $ ...

Improve this question
$\endgroup$
3
  • $\begingroup$ it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^{55}$ classical queries would become $\sim 2^{55/2}\simeq 2^{27}$ queries in the quantum case. That's quite different from "$185$ searches" $\endgroup$
    – glS ♦
    Apr 1, 2019 at 11:30
  • $\begingroup$ Ok, I think so too, but do you agree with my calculation, or is $2^{56}$ wrong in the calculation: $k=\frac{\pi}{4\cdot \sin^{-1}\left(\frac{1}{\sqrt{2^{56}}}\right)}-0.5=210828713$ $\endgroup$
    – user4961
    Apr 1, 2019 at 11:38
  • $\begingroup$ well yes, I agree with the fact that the quoted result is pretty off. My calculation is just a rough approximation of the more precise estimate you compute. $2^{27.5}\sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text? $\endgroup$
    – glS ♦
    Apr 1, 2019 at 16:38

1 Answer 1

Reset to default
4
$\begingroup$

I think your answer is right, the original article Searching a Quantum Phone Book said that Grover's algorithm would solve the problem after quantum-DES enciphering the known clear text a mere 185 million times.

Although it is different from the results you calculated, but it looks much better than 185.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key. $\endgroup$
    – user4961
    Apr 1, 2019 at 14:31
  • $\begingroup$ Yes, I think so too. $\endgroup$
    – Yijun Wang
    Apr 1, 2019 at 14:37

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.