[Cryptography] quantum computers & crypto
Jerry Leichter
leichter at lrw.com
Sun Nov 7 12:42:19 EST 2021
>> 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
More information about the cryptography
mailing list