I am looking into Authentication in lattice cryptography. Specifically in the NIST KEM finalists. I was specifically looking to see if there was a GCM (Galois counter mode) equivalence in the lattice space.

As I understand, GCM will also be broken by quantum computing and therefore may need investigating also.

Do the NIST finalists have some sort of authentication process that is comparable to GCM? Or am I misunderstanding some aspect of how lattice cryptography works?

(I am specifically interested in hardware implementations of these methods, so if there is anything specific to hardware I'd love to hear it!)


1 Answer 1


As I understand, GCM will also be broken by quantum computing

The idea that GCM would be broken is, at best, questionable; it is broken only in the scenario where you allow the attacker to make entangled queries, and is returned entangled answers. That is, for this to be an applicable attack, the implementation under attack must also be a Quantum implementation; that is, it must receive the entangled state from the adversary, it must maintain it throughout the encryption/decryption process, and then return the entangled result back to the adversary.

This is in contrast to RSA/DH/ECC - there, you can take the public key, load it into your Quantum Computer, run Shor's, and directly obtain the private key - the only cooperation you need from the device under attack is the public key (which we generally assume is public).

In a white-box scenario, this attack against GCM is plausible (because the adversary would be able to install the entire implementation-under-attack within his Quantum Computer and make entangled queries at will). Outside of that, this would seem (to me) to assume an extraordinary amount of cooperation from the device under attack. In some ways, this could be considered a side channel attack; only much easier to defend against than most side channel attacks (just don't implement GCM in a way that preserves Quantum entanglement - given that we currently don't know how to preserve entanglement over that many operations even if we wanted to, this sounds quite easy).

No one thinks GCM is broken because DPA probing can, given a sufficient number of queries, generally recover the key - it's not clear to me why this easier-to-defend against attack is more of a concern.

  • $\begingroup$ Interesting insights. I suppose I did not think that storing quantum entanglements was even a concern. So do you believe that the implementation of GCM with lattice solutions is likely to happen? $\endgroup$
    – Daftyler
    Apr 26, 2021 at 20:13
  • 2
    $\begingroup$ @Daftyler:: I do not see any reason why someone wouldn't create an IES-style Lattice/GCM encryption method... $\endgroup$
    – poncho
    Apr 26, 2021 at 21:22
  • 1
    $\begingroup$ NIST is only standardizing KEMs and Signatures at this time. KEMs exchange a random value which is turned into a symmetric key using a KDF, for use with something like AES-GCM. Signatures can authenticate the key exchange. $\endgroup$ Apr 27, 2021 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.