NIST‘s position on PQ-AEAD?

[Simon Hoerder]

Hi,

I just came across this paper https://eprint.iacr.org/2023/218 and was wondering what NIST‘s position regarding PQ-AEAD is. 

Independent of this particular paper, I can’t remember seeing any recommendations regarding PQ-AEAD algorithms; clearly it’s not as simple as „use 256-bit keys“ and you’re fine. I‘d appreciate if someone could point me towards a statement or roadmap from NIST that can be used referenced in discussions with product managers, product architects and other people that need to plan ahead for the PQC migration.

Thanks,

Simon

[Bas Westerbaan]

For most use cases, we don't even need to double key sizes in the foreseeable future as Grover's algorithm is quite impractical — quoting NIST's FAQ:

To protect against the threat of quantum computers, should we double the key length for AES now? (added 11/18/18)

Grover’s algorithm allows a quantum computer to perform a brute force key search using quadratically fewer steps than would be required classically. Taken at face value, this suggests that an attacker with access to a quantum computer might be able to attack a symmetric cipher with a key up to twice as long as could be attacked by an attacker with access only to classical computers. However there are a number of mitigating factors suggesting that Grover’s algorithm will not speed up brute force key search as dramatically as one might suspect from this result. First of all, quantum computing hardware will likely be more expensive to build and use than classical hardware. Additionally, it was proven by Zalka in 1997 that in order to obtain the full quadratic speedup, all the steps of Grover’s algorithm must be performed in series. In the real world, where attacks on cryptography use massively parallel processing, the advantage of Grover’s algorithm will be smaller.

Taking these mitigating factors into account, it is quite likely that Grover’s algorithm will provide little or no advantage in attacking AES, and AES 128 will remain secure for decades to come. Furthermore, even if quantum computers turn out to be much less expensive than anticipated, the known difficulty of parallelizing Grover’s algorithm suggests that both AES 192 and AES 256 will still be safe for a very long time. This of course assumes that no new cryptographic weaknesses, either with respect to classical or quantum cryptanalysis, are found in AES.

Based on such understanding, current applications can continue to use AES with key sizes 128, 192, or 256 bits. NIST will issue guidance regarding any transitions of symmetric key algorithms and hash functions to protect against threats from quantum computers when we can foresee a transition need. Until then, users should follow the recommendations and guidelines NIST has already issued. In particular, anything with less than 112 bits of classical security should not be used.

To wit: NIST PQC security level 1 is defined as being as hard to break by quantum attack as AES-128.

The paper you link discusses a very specific use case, where queries can be made in superposition. Unless you use whitebox cryptography, I doubt you'd be affected.

Best,

 Bas

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/26FF6871-7CEB-4601-88E0-76A0C9459A78%40hoerder.net.

[Taylor R Campbell]

> Date: Wed, 22 Feb 2023 14:24:09 +0100
> From: Simon Hoerder <si...@hoerder.net>

>
> I just came across this paper https://eprint.iacr.org/2023/218 and
> was wondering what NIST's position regarding PQ-AEAD is.

I don't know what NIST's position is, but the paper you linked -- as
well as many others about quantum attacks on symmetric crypto -- is
about an almost-nonsensical threat model where the adversary can
submit queries that are _quantum superpositions_ of chosen plaintexts
or chosen ciphertexts.

In other words, for example, your web server doing AEAD would have to
be running on a quantum computer itself, and you would have to make it
do something like serve superpositions of web pages encrypted with TLS
-- under a fixed key -- in answer to superpositions of HTTP requests
submitted by the adversary over a quantum network somehow.

This threat model is completely unrealistic for almost all
applications in the real world. The only context I can imagine where
it would be applicable in the foreseeable future is whitebox
cryptography.