[Cryptography] quantum computers & crypto

[Natanael]

Den mån 8 nov. 2021 01:31Jerry Leichter <leichter at lrw.com> skrev:

>
> >> 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.
>

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).

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20211108/b645241a/attachment.htm>