[Cryptography] quantum computers & crypto

Jon Callas jon at callas.org
Sat Nov 6 19:01:33 EDT 2021



> On Nov 3, 2021, at 15:12, Jerry Leichter <leichter at lrw.com> wrote:
> 
>> 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. 

> 
> Exactly what searches allow you to construct such an oracle is a very non-trivial question.  I don't think we know if it's possible for AES.  If it is possible, it could well require a huge number of quantum gates - i.e., the naive approach would be to essentially replicate a classical implementation using quantum gates, but that's so far beyond anything we can imagine doing today as to not be worth worrying about.  Of course there might be a better approach; I don't believe we know.

I'm not convinced that in the abstract case it's possible. Here's a setup.

I'm going to encrypt a single bit, one or zero. I'm going to do it with pseudo counter mode. I'll encrypt a secret plaintext with a secret key, and then XOR it onto my bit -- which might be in any of the 128 possible positions. What's the value of the bit? It's just one or zero, it's easy to guess. Using Grover's algorithm, and given the final bitstring, solve for it. Show your work. I am not convinced it's even possible. 

I have the intuition that because this is information-theoretically secure, it's not possible. However, if I extend this out to a real counter mode problem where I have a secret key, a secret counter start, and some arbitrary plaintext, I'm still not sure that it's possible. I think some subset is possible. For example, if the plaintext is in ASCII, we know the result has to have the high bit zero in all bytes. But so what? 

Let's take this and do all of Shakespeare's sonnets, and I'm going to wave my hand so they all have the same length via some suitable normalization. I give you the cipher text and all I want to know is which sonnet. I'm still not convinced this highly constrained problem is possible. The generic problem of recognizing that a possible plaintext is the right one is very hard in the general case. Or so my intuition tells me.

	Jon



More information about the cryptography mailing list