5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\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 '15 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 '15 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 '15 at 22:52
  • $\begingroup$ One good reference is probably this: cr.yp.to/codes/grovercode-20100303.pdf $\endgroup$ – Hubert Kario May 2 '17 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 at 19:12
1
$\begingroup$

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

Symmetric Key Quantum Resistance[edit] 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.[20] 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.[21]

Here is the link:

http://en.wikipedia.org/wiki/Post-quantum_cryptography#Symmetric_Key_Based_Cryptography

You can find some references on that Wikipedia page

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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