[Cryptography] A thought about backdoors and quantuum-resistant encryption

[Michael Kjörling]

On 28 Aug 2015 13:04 -0400, from tytso at mit.edu (Theodore Ts'o):
> Would it
> be possible to create an encryption algorithm which is resistant to
> quantuum computing --- except for someone with a quantuum computer
> *AND* knowledge of some secret quantuum state stored in a quantuum
> computer only available to the NSA.

I don't know, and I don't know enough to even know where to begin
speculating.


> /.../ but if quantuum computer were a thing, they
> would be screwed if they kept on using AES, so the NSA would be quite
> happy with that outcome.

Why does that follow? It is my understanding that based on current
knowledge, quantum computing, when applied to symmetric cryptography,
causes the security level to drop to the square root of what it used
to be. So a cipher offering a 128-bit security level now offers a
64-bit security level (because sqrt(2^128) = 2^64) against an
adversary that has a sufficiently powerful quantum computer that they
are willing to throw at the problem. Which is a Bad Thing (tm).
However, a today 256-bit security level cipher in this hypothetical
quantum computing world "only" offers the equivalent of 128-bit
security, which is Not Great (tm) but certainly not Terrible (r).

So _symmetric_ cryptography is the easy part to solve: we just need to
double the key lengths, and figure out what that means in practice. In
situations where in a no-quantum-computing world we might have used
AES-256 or AES-128, we might use XES-512 and XES-256 [1] respectively
for a similar effective security level. In this hypothetical future
world, symmetric keys remain short enough that key management is not
significantly complicated compared to what it is like today.

[1] XES is obviously the next great thing after sliced bread:
eXtensible Encryption Standard. Because anything extensible is by
definition great. I mean, just look at how easy XML is!

-- 
Michael Kjörling • https://michael.kjorling.se • michael at kjorling.se
OpenPGP B501AC6429EF4514 https://michael.kjorling.se/public-keys/pgp
                 “People who think they know everything really annoy
                 those of us who know we don’t.” (Bjarne Stroustrup)