PQC tables

The goal of the following tables is to summarize the current ANSSI views regarding post-quantum cryptography scheme usages for (French) certifications. These tables are subject to change depending on new cryptanalysis, new submitted algorithms to the NIST Post-Quantum Cryptography Standardization, new recommandations, etc. The simplified tables may give a quick overview of the ANSSI recommandations, while the larger tables will give more information, in particular about the sizes of the private key (sk), the public key (pk), the ciphertext (ct), the shared secret (ss) and the signature (sig).

Tables (simplified)

On the ANSSI column

According to [ANSSI]

Moreover the conjectured post-quantum level should be as high as possible, preferably NIST level V (AES-256).

ANSSI encourages to use a conjectured post-quantum security level on symmetric primitives consistent with the selected post-quantum PKC algorithm – in practice at least the same security level as AES-256 for block ciphers and at least the same security level as SHA2-384 for hash functions.

We then consider, in the ANSSI column, that if a cryptographic scheme does not provide security parameters for level IV (at least as hard to break as SHA2-384) or level V (at least as hard to break as AES-256), the scheme is not suitable to be used to get a (French) certification.

About the hybrid mechanism, it can be:

• concatenate KDF for key exchange mechanisms [SFG, §3.3] and [ETSI, §8.2];
• cascade KDF for key exchange mechanisms [ETSI, §8.3];
• concatenate for signatures.

Notes (simplified tables)

We give in notes some additional content, either to justify our results or to give more information and some recommendations, coming from the ANSSI views or from other governments’ positions. Indeed, as mentioned in ANSSI,

Several governments have published similar position papers recommending to prepare the post-quantum transition. ANSSI’s views are similar to the BSI’s position on many issues (e.g. necessary migration, hybridation, cryptoagility).

Even if these tables are focused on the French context, they may be used in other national contexts too.

Post-quantum cryptography key exchange mechanisms and their usage for (French) certifications (simplified tables)

KEM	Variants (best security level)	NIST	ANSSI [ANSSI]
CRYSTALS-KYBER	1024	Standard [23]	Hybrid [13, 24, 26]
BIKE	Level 5	Round 4 [23]	Hybrid
Classic McEliece	6688128(f), 6960119(f), 8192128(f)	Round 4 [23]	Hybrid [7]
HQC	256	Round 4 [23]	Hybrid
SIKE	p751	Round 4 [23]	Not compliant [25]
NTRU	HPS-4096-821	Finalist (round 3) [22]	Maybe hybrid [1]
NTRU	HPS-4096-1229, HRSS-1373 [2]	Finalist (round 3) [22]	Hybrid
SABER	(u)FireSaber	Finalist (round 3) [22]	Hybrid
FrodoKEM	1344	Alternate (round 3) [22]	Hybrid [8]
NTRU Prime	sntrup1277, ntrulpr1277	Alternate (round 3) [22]	Hybrid

Post-quantum cryptography signatures and their usage for (French) certifications (simplified tables)

Signature	Variants (best security level)	NIST	ANSSI [ANSSI]
CRYSTALS-DILITHIUM	5	Standard [23]	Hybrid [13, 24, 26]
FALCON	1024	Standard [23]	Hybrid [13, 24]
Stateful hash-based	LMS, HSS, XMSS, XMSS-MT	Standard [10]	Compliant [9]
SPHINCS+	SHAKE-256s, SHAKE-256f, SHA2-512s, SHA2-512f	Standard [23]	Compliant [9, 24]
Rainbow	UOV parameters SL5 [6]	Finalist (round 3) [22]	Hybrid
GeMSS	256, all variants	Alternate (round 3) [22]	Not compliant [15]
Picnic	L5-FS, L5-UR, L5-full, 3-L5	Alternate (round 3) [22]	Hybrid

Tables

Notes

When two values are in a same cell, first is the one from the documentation, the second from the reference implementation submitted to Round 3 submission of NIST Post-Quantum Cryptography.

Other tables gathering data on PQC schemes can be found, for example at:

• Algorithms in liboqs;
• [ETSIKEM] and [ETSISIG];
• PQC wiki.

It is also possible to look for the different api.h or META.yml of PQClean.

For performance benchmarks, an interested reader may refer to eBACS or pqm4.

In the variants of LMS, HSS, XMSS and XMSS-MT, the .. or ../.. refers to the paramaters given:

• for LMS [RFC8554, Table 2];
• for XMSS [RFC8391, Table 2];
• for XMSS-MT [RFC8391, Table 4].

Post-quantum cryptography key exchange mechanisms and their usage for (French) certification

KEM	Security Levels	Variant (levels IV / V if available)	Type	NIST	ANSSI [ANSSI]	sk size (bytes)	pk size (bytes)	ct size (bytes)	ss size (bytes)
CRYSTALS-KYBER	I, III, V	1024	Lattice (structured)	Standard [23]	Hybrid [13, 24, 26]	3,168	1,568	1,568	32
BIKE	I, III, V	Level 5	Code	Round 4 [23]	Hybrid	580	5,122 / 10,276	5,154	32
Classic McEliece	I, III, V	6688128(f)	Code	Round 4 [23]	Hybrid [7]	13,932	1,044,992	240	32
Classic McEliece	I, III, V	6960119(f)	Code	Round 4 [23]	Hybrid [7]	13,948	1,047,319	226	32
Classic McEliece	I, III, V	8192128(f)	Code	Round 4 [23]	Hybrid [7]	14,120	1,357,824	240	32
HQC	I, III, V	256	Code	Round 4 [23]	Hybrid	7,285	7,245	14,469	64
SIKE	< I [25]	p751	Isogenies	Round 4 [23]	Not compliant	644	564	596	32
SIKE	< I [25]	p751, compressed	Isogenies	Round 4 [23]	Not compliant	602	335	410	32
NTRU	I, III, V	HPS-4096-821 (level III / V) [3]	Lattice (structured)	Finalist (round 3) [22]	Maybe hybrid [1]	1,590	1,230	1,230	32
NTRU	I, III, V	HPS-4096-1229 [2, 3]	Lattice (structured)	Finalist (round 3) [22]	Hybrid	2,366 [5]	1,842 [5]	1,842 [5]	32 [5]
NTRU	I, III, V	HRSS-1373 [2, 4]	Lattice (structured)	Finalist (round 3) [22]	Hybrid	2,938 [5]	2,401 [5]	2,401 [5]	32 [5]
SABER	I, III, V	FireSaber	Lattice (structured)	Finalist (round 3) [22]	Hybrid	3,040	1,312	1,472	32
SABER	I, III, V	FireSaber, compressed	Lattice (structured)	Finalist (round 3) [22]	Hybrid	1,760 [11]	1,312 [12]	1,472 [12]	32 [12]
SABER	I, III, V	uFireSaber	Lattice (structured)	Finalist (round 3) [22]	Hybrid	2,912	1,312	1,472	32
SABER	I, III, V	uFireSaber, compressed	Lattice (structured)	Finalist (round 3) [22]	Hybrid	1,632 [12]	1,312 [12]	1,472 [12]	32 [12]
FrodoKEM	I, III, V	1344	Lattice	Alternate (round 3) [22]	Hybrid [8]	43,088	21,520	21,632	32
NTRU Prime	I, II, III, IV, V	sntrup953 (level III / IV)	Lattice (structured)	Alternate (round 3) [22]	Maybe hybrid [14]	2,254	1,505	1,349	32
NTRU Prime	I, II, III, IV, V	ntrulpr953 (level III / IV)	Lattice (structured)	Alternate (round 3) [22]	Maybe hybrid [14]	1,652	1,349	1,477	32
NTRU Prime	I, II, III, IV, V	sntrup1013 (level IV)	Lattice (structured)	Alternate (round 3) [22]	Hybrid	2,417	1,623	1,455	32
NTRU Prime	I, II, III, IV, V	ntrulpr1013 (level IV)	Lattice (structured)	Alternate (round 3) [22]	Hybrid	1,773	1,455	1,583	32
NTRU Prime	I, II, III, IV, V	sntrup1277	Lattice (structured)	Alternate (round 3) [22]	Hybrid	3,059	2,067	1,847	32
NTRU Prime	I, II, III, IV, V	ntrulpr1277	Lattice (structured)	Alternate (round 3) [22]	Hybrid	2,231	1,847	1,975	32

Post-quantum cryptography signatures and their usage for (French) certification

Signature	Security Levels	Variant (levels IV / V if available)	Type	NIST	ANSSI [ANSSI]	sk size (bytes)	pk size (bytes)	sig size (bytes)
CRYSTALS-DILITHIUM	II, III, V	5	Lattice (structured)	Standard [23]	Hybrid [13, 24, 26]	4,880 [5]	2,592	4,595
FALCON	I, V	1024	Standard	Standard [23]	Hybrid [13, 24]	2,305 [5]	1,793	1,280 / 1,330
HSS	V [18]	with LMS_SHA256_M32_H..	Hash (stateful)	Standard [10]	Compliant [9]	Dependent	60	Dependent (ex: 15,533 [21])
LMS	V [18]	LMS_SHA256_M32_H..	Hash (stateful)	Standard [10]	Compliant [9]	Dependent	56	Dependent (ex: 2,828 [21])
SPHINCS+	I, II, III, V	SHAKE-256s	Hash (stateless)	Standard [23]	Compliant [9, 24]	128	64	29,792
SPHINCS+	I, II, III, V	SHA2-512s	Hash (stateless)	Standard [23]	Compliant [9, 24]	128	64	29,792
SPHINCS+	I, II, III, V	SHAKE-256f	Hash (stateless)	Standard [23]	Compliant [9, 24]	128	64	49,856
SPHINCS+	I, II, III, V	SHA2-512f	Hash (stateless)	Standard [23]	Compliant [9, 24]	128	64	49,856
XMSS	II, V [17]	XMSS-SHA2_.._256	Hash (stateful)	Standard [10]	Compliant [9]	Dependent	68	Dependent (ex: 5,716 [21])
XMSS	II, V [17]	XMSS-SHAKE_.._512	Hash (stateful)	Standard [10]	Compliant [9]	Dependent	132	Dependent (ex: 5,716 [21])
XMSS-MT	II, V [17]	XMSSMT-SHA2_../.._256	Hash (stateful)	Standard [10]	Compliant [9]	Dependent	68	Dependent (ex: 14,824 [21])
XMSS-MT	II, V [17]	XMSSMT-SHAKE_../.._512	Hash (stateful)	Standard [10]	Compliant [9]	Dependent	132	Dependent (ex: 14,824 [21])
Rainbow	I, III, V [6]	UOV parameters SL5 - Standard	Multivariate	Finalist (round 3) [22]	Hybrid	2,451,096 [19] / 2,451,128 [20]	2,869,440 [6] / 3,087,600 [20]	264 [20]
Rainbow	I, III, V [6]	UOV parameters SL5 - CZ	Multivariate	Finalist (round 3) [22]	Hybrid	2,451,096 [19] / 2,451,128 [20]	655,944 [20]	264 [20]
GeMSS	< I [15]	GeMSS256	Multivariate	Alternate (round 3) [22]	Not compliant	32	3,040,700	72
GeMSS	< I [15]	BlueGeMSS256	Multivariate	Alternate (round 3) [22]	Not compliant	32	3,087,963	74
GeMSS	< I [15]	CyanGeMSS256	Multivariate	Alternate (round 3) [22]	Not compliant	32	3,272,017	66
GeMSS	< I [15]	RedGeMSS256	Multivariate	Alternate (round 3) [22]	Not compliant	32	3,135,591	75
GeMSS	< I [15]	MagentaGeMSS256	Multivariate	Alternate (round 3) [22]	Not compliant	32	3,321,717	67
GeMSS	< I [15]	WhiteGeMSS256	Multivariate	Alternate (round 3) [22]	Not compliant	32	3,222,691	65
Picnic	I, III, V	L5-FS	ZKP / symmetric	Alternate (round 3) [22]	Hybrid	32 / 97	64 / 65	132,856 / 132,876
Picnic	I, III, V	L5-UR	ZKP / symmetric	Alternate (round 3) [22]	Hybrid	32 / 97	64 / 65	209,506 / 209,526
Picnic	I, III, V	L5-full	ZKP / symmetric	Alternate (round 3) [22]	Hybrid	32 / 97	64 / 65	126,286
Picnic	I, III, V	3-L5	ZKP / symmetric	Alternate (round 3) [22]	Hybrid	32 / 97	64 / 65	54,732 / 61,028

Explanations

[ANSSI] ANSSI views on the Post-Quantum Cryptography transition, 4 January 2022

[ANSSIACT] Sélection par le NIST de futurs standards en cryptographie post-quantique, 18 July 2022

[BBCPSTV] J. Baena, P. Briaud, D. Cabarcas, R. Perlner, D. Smith-Tone and J. Verbel, Improving Support-Minors rank attacks: applications to GeMSS and Rainbow

[Beu] W. Beullens, Breaking Rainbow Takes a Weekend on a Laptop

[BSI] Migration zu Post-Quanten-Kryptografie, 24 August 2020; Cryptographic Mechanisms: Recommendations and Key Lengths, BSI TR-02102-1, Version: 2022-1, 11 February 2022

[CD] W. Castryck and T. Decru, An efficient key recovery attack on SIDH (preliminary version)

[CNSA] Announcing the Commercial National Security Algorithm Suite 2.0 and NSA Releases Future Quantum-Resistant (QR) Algorithm Requirements for National Security Systems

[ETSI] Quantum-safe hybrid key exchanges. ETSI TS 103 744 V1.1.1, December 2020

[ETSIKEM] Quantum-Safe Public-Key Encryption and Key Encapsulation, ETSI TR 103 823, version 1.1.1, September 2021

[ETSISIG] Quantum-Safe Signatures, ETSI TR 103 616, version 1.1.1, September 2021

[KF] P. Kampanakis and S. Fluhrer, LMS vs XMSS: Comparion of two Hash-Based Signature Standards

[KPCSA] P. Kampanakis, P. Panburana, M. Curcio, C. Shroff and M. M. Alam, Post-Quantum LMS and SPHINCS+ Hash-Based Signatures for UEFI Secure Boot

[NIST2020] G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.-K. Liu, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson and D. Smith-Tone, Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process, NISTIR 8309, July 2020

[NIST2022] G. Alagic, D. Apon, D. Cooper, Q. Dang, T. Dang, J. Kelsey, J. Lichtinger, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson, D. Smith-Tone, Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, NIST IR 8413, July 2022. See also Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized and PQC Standardization Process: Announcing Four Candidates to be Standardized, plus Fourth Round Candidates

[NISTSTD] D. Cooper, D. Apon, Q. Dang, M. Davidson, M. Dworkin, and C. Miller, Recommendation for Stateful Hash-Based Signature Schemes, NIST Special Publication 800-208, October 2020

[NLNCSA] Prepare for the threat of quantum-computers, 18 January 2022

[RFC8391] A. Huelsing, D. Butin, S. Gazdag, J. Rijneveld and A. Mohaisen, XMSS: eXtended Merkle Signature Scheme, RFC 8391, May 2018

[RFC8554] D. McGrew, M. Curcio and S. Fluhrer, Leighton-Micali Hash-Based Signatures, RFC8554, April 2019

[SFG] D. Stebila, S. Fluhrer and S. Gueron, Hybrid key exchange in TLS 1.3, Network Working Group, Internet-Draft, 11 January 2022

[TPD] C. Tao, A. Petzoldt and J. Ding, Efficient Key Recovery for All HFE Signature Variants. In: T. Malkin and C. Peikert (eds), CRYPTO 2021. LNCS, vol. 12825, pp. 70-93. Springer (11 August 2021)

[1] Not compliant if conservative choice (non-local) for the computational model, hybrid otherwise

[2] Category 5 NTRU parameters

[3] I & III (non-local), I & III & V (local), not taking into account the parameters in [2]

[4] I (non-local), III (local), not taking into account the parameters in [2]

[5] Only from the code

[6] After the attack in [Beu] acknowledged in ROUND 3 OFFICIAL COMMENT: Rainbow, the authors proposed a new set of parameters UOV parameters

[7] From [BSI]

The mechanisms FrodoKEM-976, FrodoKEM-1344 as well as Classic McEliece with the parameters in Categories 3 and 5 are assessed to be cryptographically suitable to protect confidential.

From [NLNCSA]

For PQC, we recommend the most secure algorithms, such as Frodo or McEliece.

[8] From [ANSSI]

For example, a developer should be able to obtain a security visa for a product implementing FrodoKEM whether NIST decides that FrodoKEM will be one of the first PQC standards or not.

From [ANSSIACT]

En effet, certains algorithmes qui n’ont pas été retenus mais qui semblent disposer d’une sécurité à long terme au moins équivalente à celle des algorithmes sélectionnés (comme par exemple le mécanisme d’établissement de clé FrodoKEM, fondé sur les réseaux euclidiens non structurés) peuvent demeurer des options dignes d’intérêt pour des applications de haute sécurité suffisamment peu contraintes en termes de bande passante.

From [BSI]

The mechanisms FrodoKEM-976, FrodoKEM-1344 as well as Classic McEliece with the parameters in Categories 3 and 5 are assessed to be cryptographically suitable to protect confidential.

From [NLNCSA]

For PQC, we recommend the most secure algorithms, such as Frodo or McEliece.

[9] From [ANSSI]

Hash-based signatures are an exception for hybridation: due to their well-studied underlying mathematical problem, ANSSI estimates that these algorithms could be used today without hybridation. However, their potential application range is limited (low number of signatures queries or large signature sizes).

From [ANSSIACT]

à l’exception de mécanismes uniquement fondés sur la sécurité de fonctions de hachage comme SPHINCS+, pour lesquels l’hybridation est optionnelle

[10] See [NISTSTD], [RFC8391] and [RFC8554]

[11] See [KF, Table 2]

[12] Only from the documentation

[13] From [ANSSI]

For example, at the time of the writing, the NIST candidates FrodoKEM, Kyber, Dilithium or Falcon could be good options for first deployments.

[14] Depending on the analysis of the security level (bulletproofing strategies), the security level is:

• IV (strategy #1) and may be used in a hybrid way or
• III (strategy #2) and is not compliant

[15] The attacks in [TPD, BBCPSTV] show that the security of GeMSS256, BlueGeMSS256 and RedGeMSS256 are less than level I

[16] From [RFC8554]

If the public key is not exactly 24 + m bytes long, return INVALID

[17] From [RFC8391], see Errata ID: 6024

Parameters with SHA2 and n = 32 [...] and with SHA2 and n = 64 [...] yield post-quantum security of 128 and 256 bits, respectively. Parameters with SHAKE and n = 32 [...] [and] with SHAKE and n = 64 [...] yield post-quantum security of 86 and 170 bits, respectively.

and

In consequence, SHAKE-128 cannot provide more security than NIST post-quantum security level II.

We then will consider in the table only the SHA-256 and SHAKE256 variants, other paramaters being not relevant in the context of [ANSSI]

[18] See [KPCSA, Table 1]

[19] By assuming that o1 = 36, o2 = 64 and v1 = 148 which is coherent with the parameters in [6], the formula in page 17 of the documentation gives the equation o1 * o2 + v1 * (o1 + o2) + o1 * o2 + o1 * (v1 * (v1 + 1) / 2 + v1 * o1) + o2 * ((v1 + o1) * (v1 + o1 + 1) / 2 + (v1 + o1) * o2)

[20] By modifying the code as proposed in script_test.sh, we obtain the following values

[21] See [KF, Table 3], for 2^20 messages for LMS and XMSS and 2^60 for HSS and XMSS-MT

[22] See [NIST2020]

[23] See [NIST2022]

[24] See [ANSSIACT]

L’on peut donc désormais considérer les quatre algorithmes CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON et SPHINCS+ comme des choix à envisager dans la majorité des cas pour la sélection d’algorithmes post-quantiques pour la conception de produits de sécurité.

[25] The attack in [CD] shows that the security of SIKEp751 is less than level I

[26] See Table III of [CNSA]