Quantum Computing Hardware
Once large fault-tolerant quantum computers are built, which ciphers are expected to have their security seriously undermined by Shor's algorithm?
- APublic-key cryptography such as RSA and elliptic-curve cryptography
- BOnly symmetric-key ciphers such as AES
- CThe one-time pad (encryption with a single-use random key)
Show answer and explanation
Answer: A. Public-key cryptography such as RSA and elliptic-curve cryptography
The security of RSA rests on the difficulty of factoring large numbers, and that of elliptic-curve cryptography on the difficulty of the discrete logarithm problem. Shor's algorithm solves these problems in polynomial time by finding periods with the quantum Fourier transform. Keys too long to break in a realistic time on classical computers could then be broken with a sufficiently large fault-tolerant quantum computer. Against symmetric-key ciphers such as AES there is only the quadratic speed-up of Grover's algorithm, which can be countered with longer keys.
- A. Correct. Factoring and the discrete logarithm problem become solvable in polynomial time.
- B. The impact on symmetric-key ciphers is the quadratic speed-up of Grover's algorithm, which longer keys can counter. Shor's algorithm threatens public-key cryptography.
- C. The one-time pad, which uses a truly random key only once, is proven to be unbreakable regardless of computing power.