[Cryptography] quantum computers & crypto

[Jerry Leichter]

>> 
>>> Another way to state the same thing is that a symmetric cipher with key of N bits is N/2-bits quantum-safe. This is because they're only vulnerable to Grover's algorithm, which is the quantum search algorithm.
>>> 
>>> So yeah, if you (e.g.) use AES-256, it's got quantum security of 128 bits.
>> BTW, to the limited degree I understand this, it's a *really* worst-case estimate.  To actually get the speedup, you need an oracle that can tell you if you've "guessed right."  To be useful, the oracle has to itself be implemented as a quantum computation - i.e., on a mixed state:  If you first measure, then use a classical implementation of the oracle (i.e., you first measure, then try out the key you get using a classical implementation of AES), you've lost your advantage.
> 
> Yes, you are indeed right. Knowing you got the right answer is the handwaved secondary problem of all cryptanalysis. It's especially true with things like Grover's algorithm. 
I think when people talk about Grover's algorithm for cryptanalysis, they assume a known plaintext attack.  Specifically, you're given a plaintext P and a ciphertext C such that C=AES(K,P).  You need to determine K.  Well, *any* K.  Since K, P, and C are all the same length, and AES "looks random," collisions are inevitable and multiple K's will produce a givn (P,C) pair.  In practical terms once you have a few of them you typically have other (P,C) pairs you can try it against - something you don't need a quantum algorithm for.

Modern cryptosystems are supposed to be secure against plaintext attacks - even against chosen plaintext attacks - so this is a legitimate starting point, especially since practical use of cryptosystems tends to give the adversary ways to force you to allow plaintext attacks.

Otherwise, yes, you have to come up with heuristics, which basically come down to looking at the entropy of the alleged decryption on the assumption that real plaintext has much lower entropy than the random noise that you get from trying to decrypt with the wrong key.  Quantifying this is obviously highly dependent on the model you have of correct plaintext.  In practice, this is usually not a problem for classical attacks.  How you would approach it for quantum attacks, I have no clue.
                                                        -- Jerry