512 bit vs. 384 bit curves

[falko-strenzke]

We are currently specifying composite schemes combining PQC Level 5 with 384 bit curves.

The potential problem that I see here is that 384 bit curves do not fulfull requirements for long term security.

For instance the BSI uses 512 bit curves already now for long term secure keys:

• BSI country signing CA: 512 bit ECDSA from 2019:
  • https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR03116/BSI-TR-03116-2.pdf?__blob=publicationFile&v=5#page=10
  • Refers for long term secure key size to https://www.ecrypt.eu.org/csa/documents/D5.4-FinalAlgKeySizeProt.pdf#page=59
  • There, for long term security (up to 30 - 50 years): 512 bit ECC keys

One point to consider here is that we do not necessarily know today what the relevant requirements will be for the composite pairs. Today it may be convincing that the traditional scheme plays only a transitory role. But actually an application with long term security requirements that has to use the composite at the point where the new standard is available, it is necessary to fulfill that requirement in both scenarios where either of the two schemes turns out to be insecure.

From that perspective I see it as natural to pair schemes in composite constructions only with equal classical security. Especially for encryption this is ultimately important in my opinion, but also applies to signatures.

I am aware that the the current selection of pairs is aligned with the choices of LAMPS. However, from my perspective it would make sense to point them to this issue as well.

[falko-strenzke]

For the sake of completeness: With X448+Kyber1024 we have one combination with a similar security level. However, whoever is by regulatory requirements committed to 256 bit cannot use X448. Furthermore, there may be other reasons to why Secp or Brainpool parameters have to be used in certain context.

[falko-strenzke]

After the internal discussions among the draft team, we came to the conclusion that it makes sense to keep the current combinations that combine EC and Dilithium / Kyber as given in the following table

targeted classical security level / bits	Kyber / Dil. level	curve length /bits
128	L3 (192 bit class. sec.)	256
192	L5 (256 bit class. sec.)	384

That means that the EC curves are chosen to match the targeted classical (not PQ) security level. The PQC scheme is chosen with a safety margin in the security parameters to account for potential improvements of classical attacks on the new lattice based algorithms.