I am wondering if one can apply Grover algorithm on a key encapsulation mechanism in order to crack the shared key.
For example, FrodoKEM is a key generation protocol that, for some parameters, shares 128 key bits.
Can we break it using Grover? i.e. reduce it to $2^{64}$ operations?
Reference for FrodoKEM: https://frodokem.org/files/FrodoKEM-specification-20171130.pdf
I am wondering if one can apply Grover algorithm on a key encapsulation mechanism in order to crack the shared key.
Here's how Grover's algorithm works (simplified): you take a 'fitness' function (that takes a guess at the value you're searching for and evaluates to a '1' if the guess is correct and '0' if it is not - for AES, the fitness function might be 'use the guess as an AES key and encrypt the known plaintext block, and check if the result is the known ciphertext block).
Then, you take this fitness function (and some other Quantum operations) and iterate it a large number of times - if you iterate it the correct number of times, then when you measure the result, it is with high probability a value that the fitness function evaluates to 1.
Now, if we were to consider attacking Frodo, there are two ways to attack it. One could try to recover the shared secret directly from the public key shares; in this case, we have available to the fitness function the public key shares, and our guess to the shared secret. However, we don't have an efficient way to check whether that guess is correct (based on the public key shares), and so we don't know how to build this fitness function (and so Grover's does not appear to apply).
On the other hand, we can try to recover the secret seed that Frodo used to derive the public key [1] (or alternatively, within the Frodo encapsulation process). For Frodo-640 (NIST level 1), this secret seed is 128 bits; since one could define a mapping between this 128 bit value (and public data, that is, the public seed) and the public key, we could use that to generate the fitness function.
Now, this attack is not inherent to postquantum cryptography; it works not by directly attacking the 128 bit shared secret, but instead of how this parameter set of Frodo generates its key shares, using a 128 bit random value as a 'secret seed'. What Frodo does is take that 128 bit secret seed and extends it using SHAKE to generate much longer share and error vectors; the Frodo designers could have used a longer secret seed, and expand that to SHAKE - this would make Grover's much more difficult (because the secret seed to recover is much longer, and trying to recover the internal SHAKE state or the sequence of SHAKE outputs would also take too long). The designers of Frodo did not do this, probably because it wouldn't actually improve security.
On the third hand, we generally do something with the shared key; we may feed that into a KDF (perhaps along with some public data, such as nonces), and then use that result as an AES key. We can build a fitness function based on that, and so Grover's would apply to that system - most likely, this KDF/AES construction would be simpler to implement within a Quantum Computer than the Frodo public key (or encapsulation) process; hence it is likely to be easier to attack the system there (if only by a constant factor).
On the fourth hand, it is reasonable to ask whether Grover's is really a threat against a 128 bit secret - all these fitness function evaluations are done serially, and it would be impractical to evaluate any function $2^{64}$ times in a row. And, while you could try to get around this by running Grover's on a large number of Quantum Computers by dividing up the secret space, we lose part of Grover's advantage if we do that, and so we end up using a lot of Quantum Computers.
[1]: Note that Frodo has two seeds; one public which defines the lattice to be used, and one which is secret, and which is used to generate the sample and error matrices; since the public seed is in the public key, the attacker doesn't need to guess that; all he needs to do is to recover the secret seed.
