[Cryptography] quantum computers & crypto

[Jerry Leichter]

>> [Suggestions for ciphers with longer keys]
> Why not just use Triple AES26, ala Triple DES?  E_AES256_k1 -> D_AES256_k2 -> E_AES256_k1 ?  Voila (albeit @1/3 the throughput), 512 bits!
> 
> Or even Triple AES256 with three different keys, Ek1 -> Dk2 -> Ek3 for 768 bits?
Keep in mind that all that we know with any degree of certainty about 3-DES is that it's no weaker than DES-X (XOR'ing a single 64-bit extra key before and after DES itself) - and we know that DES-X is "pretty strong" *against brute force attack."  This was one of Phillip Rogaway's earliest results in concrete security.

So, sure, maybe Triple AES256 is really significantly strong than AES256 - and maybe it's exactly as strong as "AES256-X," which would be stronger against a brute-force attack that is out of even conceptual reach even with quantum techniques.

BTW, there's actually a completely different reason for considering systems with *much* larger keys.  Keys concentrate vulnerabilities:  Leaking 128 bits out of a document almost never reveals anything of significance.  (Oh, sure, sometimes the really relevant number is something like a price, and it's contained in just a few bytes.  But that's unusual.)  On the other hand, leaking 128 bits of key material can be a disaster, as it can serve to unlock a huge amount of material.

Now consider side-channel attacks.  Often, they work but have very low data rates.  Very old papers on them would point out that you can't entirely eliminate them, but if you can force their data rates low enough - say, a bit an hour - well, how much damage can they do?  At a bit an hour, of course, in a week you can leak enough bits of a 128-bit key to make a search for the rest trivial.

Today, we're seeing tons of clever side channel attacks, particularly of late within shared CPU's, and closing them completely is proving very difficult and a performance killer.

Now, if a key were 10Kbits long, and you in fact needed all of them ... a side channel attack might be somewhat more difficult.
                                                        -- Jerry