[Cryptography] quantum computers & crypto

[Jerry Leichter]

>> 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 AES 256, the plaintext and ciphertext are 128 bits and the key
>  is 256 bits.  There are indeed many keys that produce the same
>  (P,C) pair.
You're right, of course - for some reason I only thought about AES128.

> [Estimates of how many times you will see multiple keys that work against several blocks.  In all cases, the numbers needed to disconfirm a bad guess are pretty small - certainly less than 10.]

The obvious approach then is to try any key you get out of Grover's algorithm against a few more blocks, and if it doesn't work, try again.  10*sqrt(N) is still a big win over N for the values of N we're concerned about....

Which raises the interesting question of what the distribution of expected answers is when running the algorithm repeatedly.  It seems like a reasonable guess that when there are multiple possible solutions, what Grover's algorithm settles into is a mixed state of all the possible solutions - but it's not clear that they have equal amplitudes.  If there are two solutions and one has a probability of 99.9% when you finally measure the result, you'll have to make a lot of runs to find the other candidate.

Of course, if the result is really a mixed state of all possible solutions, perhaps there's a way of applying that mixed state directly to additional possible inputs and limit the result to one that works in all cases....

Difficult math - certainly to me, but it appears some questions like this are even difficult for those who actually understand this stuff.

                                                        -- Jerry