[CFRG] Fw: Round 4 (Code-based KEMs) OFFICIAL COMMENT

Sent from Outlook for iOS<https://aka.ms/o0ukef>
________________________________
From: 'John Mattsson' via pqc-forum <[email protected]>
Sent: Sunday, November 10, 2024 9:03 AM
To: pqc-forum <[email protected]>
Subject: [pqc-forum] Re: Round 4 (Code-based KEMs) OFFICIAL COMMENT

Hi,

There seems to be substantial interest in using FrodoKEM+ECC from European governments as it is seen as a conservative choice. My thought was that ML-KEM+BIKE+ECC and ML-KEM+HQC+ECC seem like more conservative choices than FrodoKEM+ECC while also providing significantly better performance. What is conservative is a matter of opinion, but my thinking would be that a theoretical attack breaking all lattice-based crypto (ML-KEM, FrodoKEM) is more likely than attacks breaking both structured lattices and QC-MDPC.

At CFRG last week there was a comment that this was an "Interesting thought indeed". Based on that I thought I could share the excel sheets I made. I don't think I have seen any public discussion of Lattice+Code+ECC hybrids before. Ericsson does currently not have any concrete plans to use FrodoKEM or Lattice+Code hybrids, but we would like a QC-MDPC KEM standardized and implemented as a backup algorithm to ML-KEM for ephemeral encapsulation. This does not mean we doubt ML-KEM, we would also like to have a NIST approved backup algorithm for AES for crypto agility.

Table 1.KEM Public key and ciphertext sizes in bytes. Total size is public key size plus ciphertext size which is a relevant measure when KEMs are used for ephemeral key exchange is protocols like TLS 1.3 and IKEv2.

Name
Category
Public key
Ciphertext
Total
ML-KEM-512
1
800
768
1568
BIKE-L1
1
1541
1573
3114
ML-KEM-512+BIKE-L1
1
2341
2341
4682
HQC-128
1
2249
4481
6730
ML-KEM-512+HQC-128
1
3049
5249
8298
FrodoKEM-640
1
9616
9720
19336
ML-KEM-768
3
1184
1088
2272
BIKE-L3
3
3083
3115
6198
ML-KEM-768+BIKE-L3
3
4267
4203
8470
HQC-192
3
4522
9026
13548
ML-KEM-768+HQC-192
3
5706
10114
15820
FrodoKEM-976
3
15632
15744
31376
ML-KEM-1024
5
1568
1568
3136
BIKE-L5
5
5122
5154
10276
ML-KEM-1024+BIKE-L5
5
6690
6722
13412
HQC-256
5
7245
14469
21714
ML-KEM-1024+HQC-256
5
8813
16037
24850
FrodoKEM-1344
5
21520
21632
43152

Table 2. KEM performance in cycles (50%) on 2023 AMD Ryzen 7 7700. Performance number from eBACS: ECRYPT Benchmarking of Cryptographic Systems by Bernstein and Lange (editors) https://bench.cr.yp.to/results-kem/amd64-hertz.html. Total is cycles for key gen + encapsulation + decapsulation.

Name
Category
Key Gen
Encapsulation
Decapsulation
Total
ML-KEM-512 (kyber512)
1
15420
24443
18693
58556
HQC-128 (hqc128round4)
1
61311
170433
283249
514993
ML-KEM-512+HQC-128
1
76731
194876
301942
573549
BIKE-L1 (bikel1)
1
459202
83286
1069392
1611880
ML-KEM-512+BIKE-L1
1
474622
107729
1088085
1670436
FrodoKEM-640 (frodokem640shake)
1
2084314
2265633
2222733
6572680
ML-KEM-768 (kyber768)
3
26537
36373
27911
90821
HQC-192 (hqc192round4)
3
145927
388479
616013
1150419
ML-KEM-768+HQC-192
3
172464
424852
643924
1241240
BIKE-L3 (bikel3)
3
1276234
177463
3365184
4818881
ML-KEM-768+BIKE-L3
3
1302771
213836
3393095
4909702
FrodoKEM-976 (frodokem976shake)
3
4272608
4592978
4483035
13348621
ML-KEM-1024 (kyber1024)
5
34305
48320
38330
120955
HQC-256 (hqc256round4)
5
295441
733761
1192579
2221781
ML-KEM-1024+HQC-256
5
329746
782081
1230909
2342736
BIKE-L5
5
?
?
?
?
ML-KEM-1024+BIKE-L5
5
?
?
?
?
FrodoKEM-1344 (frodokem1344shake)
5
7309062
7857621
7702139
22868822

I apologize for any potential errors in the tables above or if I chose the wrong algorithm variants from eBACS. I could not find performance numbers for BIKE-L5 on eBACS. FrodoKEM with SHAKE seemed like the fairest comparison to the other SHAKE based algorithms. I am a bit skeptical to the use of AES as a KDF
https://csrc.nist.gov/csrc/media/Projects/crypto-publication-review-project/documents/initial-comments/sp800-38b-initial-public-comments-2024.pdf

The Excel documents are available here.
https://github.com/emanjon/KEMs

Cheers,
John Preuß Mattsson

From: Crick Waters <[email protected]>
Date: Tuesday, 29 October 2024 at 17:22
To: pqc-forum <[email protected]>
Cc: John Mattsson <[email protected]>
Subject: Re: Round 4 (Code-based KEMs) OFFICIAL COMMENT
You don't often get email from [email protected]. Learn why this is important<https://aka.ms/LearnAboutSenderIdentification>
Patero concurs and has implemented the same. We support the standardization of Classic McEliece as recommended.
Regards,
Crick
Crick Waters
CEO Patero
On Saturday, October 26, 2024 at 12:11:13 PM UTC-7 John Mattsson wrote:
We strongly think NIST should standardize Classic McEliece, which has properties that makes it the best choice in many different applications. We are planning to use Classic McEliece.

- Classic McEliece is the most conservative KEM and Classic McEliece category 5 is the best option for protecting various other keys (ML-KEM, ML-DSA, SLH-DSA, FN-DSA, LMS, XMSS, etc.) in transit and storage. Classic McEliece occupies a role similar to SLH-DSA, providing a very conservative security assurance.

- The small ciphertexts and good performance makes Classic McEliece the best choice for many applications of static encapsulation keys of which there are many (WireGuard, S/MIME, IMSI encryption, File encryption, Noise, EDHOC, etc.). For many such applications, key generation time is not important, and the public key can be provisioned out-of-band. When the public key is provisioned in-band, Classic McEliece has the best performance after a few hundred encapsulations. For static encapsulation use cases where ML-KEM provides the best performance, Classic McEliece is the best backup algorithm. The memory requirement can be kept low by streaming the key.

We think NIST should standardize mceliece348864 (category 1), mceliece460896 (category 3), and one of mceliece6688128, mceliece6960119, and mceliece8192128 (category 5). 261 kB and 524 kB encapsulation keys can be used where 1 MB public keys cannot.

In addition, we think NIST should standardize one of BIKE and HQC. BIKE and HQC are the best backup algorithms to ML-KEM for ephemeral encapsulation keys. Additionally, ML-KEM+BIKE and ML-KEM+HQC hybrids seems like more conservative choices than FrodoKEM while also providing better performance. We are currently not planning to use BIKE or HQC, but we would like to see a standardized backup algorithm for ML-KEM in case attacks are found. Such a backup algorithms should have a different construction than ML-KEM. This practice of implementing independent cryptographic backup algorithms has long been a guiding principle in the telecom industry.

Cheers,
John Preuß Mattsson
Expert Cryptographic Algorithms and Security Protocols, Ericsson

--
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 [email protected]<mailto:[email protected]>.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/GVXPR07MB96782E9B7E14F2A3CC3D7F9A895F2%40GVXPR07MB9678.eurprd07.prod.outlook.com<https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/GVXPR07MB96782E9B7E14F2A3CC3D7F9A895F2%40GVXPR07MB9678.eurprd07.prod.outlook.com?utm_medium=email&utm_source=footer>.

_______________________________________________
CFRG mailing list -- [email protected]
To unsubscribe send an email to [email protected]