Grover algorithm for public key cryptography - FrodoKEM

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

• Are you asking using Grover's Against FrodoKem or Against the symmetric key encryption that FrodoKem produced? What symmetric encryption is under usage after FrodoKem? Consider it like RSA-KEM ( Key Encapsulation Mechanism) + AES-GCM (Data Encapsulation Mechanism (DEM)). Grover will beat AES-128 in a near future but not AES-256. Nov 12, 2021 at 12:29
• Thank you @kelalaka. What about breaking FrodoKEM it self? Is it possible with Grover's algorithm?
– C.S.
Nov 12, 2021 at 12:40
• Of course it is not clear that how one can run the $\sqrt{2^n}$ Grover Oracles calls in the real life. What is the cost of ( timexmoney ) of preparing the next Oracle... Nov 12, 2021 at 12:51
• Nov 12, 2021 at 14:46

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.

• Why would you not be able to attack (= build the fitness function) the initial seed (which also has 128 bits) used to generated the (sk, pk) pair using Grover? This would assume that finding a sk (or rather a seed that es expanded to a sk) that results in the same pk allows you to decapsulate successfully. Nov 12, 2021 at 15:45
• @Fleeep: my apologies; I had thought that Frodo-640 took a longer secret seed - double checking, I see that it doesn't. Then, yes, you could use Grover's to recover it; on the other hand, I suspect that'll be a constant factor more complex than attacking the symmetric system that uses the seed, but it's certainly possible (if impractical; see above) Nov 12, 2021 at 17:55
• @Fleeep: ok, I modified my answer to address this alternative attack Nov 12, 2021 at 18:12