1
$\begingroup$

I am having a university assignment that requires me to study on the threats that quantum computer poses to modern cryptography.

At the moment, I know that modern symmetric encryption will reduce their key size strength in half through Grover's algorithm. It can also break existing standardized RSA, Curve448 and Curve25519 (Not Grover's algorithm).

Can I have the papers or some layman's reference link to those kinds of attacks? Other than the listed attacks, is there any other threats that quantum computer poses to modern cryptography?

$\endgroup$
6
  • $\begingroup$ Shor's algorithm is what is used for breaking public key cryptography, not Grover's algorithm. $\endgroup$
    – forest
    Commented Nov 11, 2022 at 3:00
  • $\begingroup$ @forest Does shor's algorithm also applies to named elliptic curve448 and curve25519? Due to my limited understanding, I only know shor's algorithm poses a great threat to RSA by simply ignoring the prime numbers factorization, a form of solving discrete logarithm problem. $\endgroup$
    – Hern
    Commented Nov 11, 2022 at 3:07
  • $\begingroup$ @Hern, Shor's algorithm is also applicable to discrete algorithm, regardless the form of the underlying group, so Curve448 and Curve25519 are also breakable by Shor's algo. $\endgroup$
    – DannyNiu
    Commented Nov 11, 2022 at 5:22
  • $\begingroup$ How about the entropy generation for cryptography keys generation? Is there any papers out there that states current cryptography keys generation could poses a problem to quantum computing(I don't really know about this one that's why I asked) $\endgroup$
    – Hern
    Commented Nov 11, 2022 at 5:54
  • 1
    $\begingroup$ "modern symmetric encryption will reduce their key size strength in half through Grover's algorithm" is a pessimistic worst-case scenario. See this for a more nuanced view. Independently: "entropy generation for cryptography keys generation" is a possible application of quantum physics to cryptography; not a "threat to modern cryptography"; the many failures of RNGs are typically attributable to inappropriate design, rather than to use of a not-enough-quantuim source. $\endgroup$
    – fgrieu
    Commented Nov 11, 2022 at 9:10

1 Answer 1

3
$\begingroup$

Shor's Algorithm for factoring: Threatens all cryptosystems based on using a cyclic group. This is a high level and high impact risk because the improvement Shor gives is exponential (for Discrete Logs) and super polynomial (for factoring).

The systems at risk include RSA, Diffie-Hellman, Elliptic Curve based systems, all these are public key (asymmetric) systems. The main thrust of NISTs post quantum cryptography (PQC) standards development is towards replacing these algorithms. Here is a high level description from the NIST project. Here is a page from IBM. Dan Bernstein and Tanja Lange have a book on PQC linked from here.

Note that lattice based, multivariate polynomial based, and code based asymmetric key systems are not currently believed to be vulnerable to any Quantum attack. However, one proposed post quantum safe algorithm (Rainbow) fell victim to a classical attack recently during the standardization process.

Grover's Quantum Search Algorithm: This is a threat to symmetric cryptosystems because it can be applied to any brute force searching method. The threat here is only polynomial in order (effective halving of the keylength representing brute force search complexity). Here is a question with answers on this topic.

Quantum Randomness Generation and Testing: There are proposals for both, though I haven't seen any instances of classical random number generators (if well-designed and robust against classical attacks) being subjected to a quantum attack which made a difference to their security.

Big Caveat: We are currently nowhere near building a functioning quantum computer that can threaten these systems, but the store and break later kind of attack is a real threat into the future, depending on how long you want your encrypted secrets to survive. Here is a question whose answer dispels some confusion about this. The question was asked in response to this announcement by IBM which specified 400 physical qubits in their Osprey quantum computer, and was mistaken to be logical qubits. In summary we need to use logical qubits not physical qubits to measure security.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.