It seems that quite a few currently available encryption schemes will possibly be broken by quantum computing. Are there any symmetric encryption schemes that will remain unbroken (either because of their design or by increasing the key size)? In particular are there any such schemes that may be used with a single key in a non-deterministic manner?


3 Answers 3


Yes; virtually all of them. Quantum computers give a quadratic speedup on a general search problems (so key lengths need to double), but I don't know of any symmetric schemes in actual use for which quantum computation gives a bigger speedup.

  • $\begingroup$ So just trying to understand the second part of your answer - you're saying none of the existing symmetric schemes are quantum resistant? $\endgroup$
    – petro444
    May 2, 2015 at 22:39
  • 3
    $\begingroup$ @petro444 I'm saying they all are quantum resistant. "Speedup" here is a bad thing; it refers to the attacker being able to break a cipher faster than brute force, and the faster/bigger the speedup the smaller the effective key length. Quantum computing gives an unavoidable quadratic speedup (a brute-force of X things on a quantum computer requires $\sqrt{X}$ operations), which corresponds to a halving of effective key length, but that's it -- you just need to double key lengths. $\endgroup$
    – cpast
    May 2, 2015 at 22:48
  • 1
    $\begingroup$ Ok, thanks, I'll accept your answer. But if you're feeling generous, would you mind adding a couple of references to backup your answer as well? $\endgroup$
    – petro444
    May 2, 2015 at 22:52
  • $\begingroup$ One good reference is probably this: cr.yp.to/codes/grovercode-20100303.pdf $\endgroup$ May 2, 2017 at 14:20
  • 1
    $\begingroup$ @elsa NIST is not looking for symmetric cryptography, but for asymmetric crypto. Current standard primitives for asymmetric crypto get utterly destroyed by quantum computers. $\endgroup$
    – SEJPM
    May 23, 2019 at 19:12

While the other answer itself is correct (that currently, quantum algorithms impact on symmetric encryption is to reduce the effective key size from $n$ to $n/2$ via Grover search), you can base symmetric encryption on problems that are thought to be resistant to quantum algorithms.

An easy example is encryption from the LWE assumption. Given that the LWE assumption holds, the following is a symmetric (bit)-encryption scheme:

$$\mathsf{Enc}_s(m) = (a, \langle a,s\rangle + \frac{q}{2}m + e)$$ Here, $a\sim\mathsf{Unif}(\mathbb{Z}^n_q)$, and $e\sim\mathsf{DiscGauss}_\sigma(\mathbb{Z}_q^n)$. There are some additional details (bounds on $\sigma$ and $q$, specifying decryption, etc), but with careful analysis this works out.

What does "resistant to quantum algorithms" mean though? Essentially that Grover search is the best algorithm possible, so even in the "specific" case of using a quantum-resistant hardness assumption, there's still a quadratic speedup. This can be seen as reinforcing why symmetric crypto is "safe" --- the quantum attacks against it are fairly broad, and tend to apply to any specific situation you can think of (in fact, I believe they always apply, but don't want to make that strong of a claim as a casual practitioner).

  • $\begingroup$ It is not immediately clear to me why the "LWE assumption" would be considered more solid (or Quantum Resistant) than, say, the "AES assumption" $\endgroup$
    – poncho
    Aug 5, 2023 at 18:23
  • $\begingroup$ @poncho Breaking search LWE is (roughly) equivalent to giving close-to-optimal decoding algorithms for random codes in the Additive White Gaussian Noise channel. This is to say that it would open up a new application of quantum computing, compared to solely breaking cryptography. $\endgroup$
    – Mark Schultz-Wu
    Aug 5, 2023 at 18:27

The Wikipedia article on Post Quantum Cryptography has the following to say about symmetric algorithm quantum resistance.

Provided one uses sufficiently large key sizes, the symmetric key cryptographic systems like AES and SNOW 3G are already resistant to attack by a quantum computer. Further, key management systems and protocols that use symmetric key cryptography instead of public key cryptography like Kerberos and the 3GPP Mobile Network Authentication Structure are also inherently secure against attack by a quantum computer. Given its widespread deployment in the world already, some researchers recommend expanded use of Kerberos-like symmetric key management as an efficient and effective way to get Post Quantum cryptography today.

You can find some references on that Wikipedia page.

  • 2
    $\begingroup$ I my humble opinion, you shouldn't just copy-paste from wikipedia... $\endgroup$
    – hola
    Apr 7, 2019 at 3:06

Your Answer

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

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