<div dir="auto"><div><br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Den mån 8 nov. 2021 01:31Jerry Leichter <<a href="mailto:leichter@lrw.com">leichter@lrw.com</a>> skrev:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
>> You need to determine K.  Well, *any* K.  Since K, P, and C are all<br>
>> the same length, and AES "looks random," collisions are inevitable and<br>
>> multiple K's will produce a givn (P,C) pair.<br>
> <br>
> * In AES 256, the plaintext and ciphertext are 128 bits and the key<br>
>  is 256 bits.  There are indeed many keys that produce the same<br>
>  (P,C) pair.<br>
You're right, of course - for some reason I only thought about AES128.<br>
<br>
> [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.]<br>
<br>
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....<br>
<br>
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.<br>
<br>
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....<br>
<br>
Difficult math - certainly to me, but it appears some questions like this are even difficult for those who actually understand this stuff.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">What I recall is what Grover's algorithm is proven optimal in the general case in terms of how fast a quantum algorithm can find a solution for a search problem. Improving on the lower bound requires finding an exploitable mathematical structure in the problem (in AES, that is). </div><div dir="auto"><br></div><div dir="auto">Any attempts to apply additional clever tests just mean you do more of the work in each cycle on the quantum computer itself to filter out vad candidates (with more qubits required accordingly), rather than just testing each and every candidate output on a classical computer. <br></div></div>