Performance of Post-Quantum Signatures: Analysis and Comparison

Explore the performance and characteristics of various post-quantum signature schemes including Lattice-based Dilithium, QTesla, Falcon, Symmetric Sphincs+, Picnic, Multivariate GEMSS, Rainbow, and more. Understand the implications of using these schemes in TLS, code signing, firmware updates, signed email, and logs. Evaluate the feasibility of integrating post-quantum signatures in today's world compared to RSA and EDDSA. Delve into the challenges and benefits of utilizing different post-quantum signature schemes.

• Post-Quantum Signatures
• Performance Analysis
• RSA
• EDDSA
• Security

lucan Follow

Uploaded on Aug 05, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Performance of PQ Sigs John Kelsey, NIST, March 2020

2. Remaining PQ Signatures Lattice-based Dilithium QTesla Falcon Symmetric Sphincs+ Picnic Multivariate GEMSS Rainbow LUOV MQDSS

3. Remaining PQ Signatures Lattice-based Dilithium Qtesla Falcon (Broken) Symmetric Sphincs+ Picnic Multivariate GEMSS Rainbow LUOV MQDSS (Broken) (Broken)

4. So we have six left Lattice-based Dilithium Falcon } These are very different schemes, even though based on } the same underlying kind of problem. Symmetric Sphincs+ Picnic } These have almost nothing in common with each other } except huge, slow signatures. Multivariate GEMSS Rainbow } These also look pretty different to me, but I m not confident } in my assessment.

5. Properties Lattice-based Dilithium Falcon Symmetric Sphincs+ Picnic Multivariate GEMSS Rainbow } Reasonable performance on sign and verify. } PK and signature bigger than RSA/ECDSA but not too bad. } Tiny public keys, enormous signatures. Very slow. } Security based on symmetric crypto. } Huge public keys, tiny signatures. } Fast signing and verifying.

6. What does it look like to put these into use? TLS Code signing Firmware updates Signed email Signed logs and logcrypt Etc.

7. Can we make PQ signatures work in current world? Will the signature and public key sizes fit? Are they fast enough? Do they take too many resources to implement?

8. To answer this: compare with RSA and EDDSA RSA Easy to compare 3K RSA with sizes of PQ signatures We know we can make stuff work with RSA-sized PKs and sigs EDDSA Fast and efficient modern signature scheme Faster signing, slower verification Smaller keys and signatures SUPERCOP data always includes this algorithm

9. How Much Bigger does Everything Get? Public keys and signatures will get bigger Some schemes: not so bad Others are pretty awful. Some applications only care about signature size others care about PK and signatures . Private key size only matters for implementations

10. How Big are Signatures and Keys? Both reasonable Dilithium, Falcon scheme sk size pk size sig size pk + sig ed25519 64 32 64 96 rsa3072 384 384 384 384 Small sig, huge PK Rainbow, GEMSS dilithium2 2800 1184 2044 3228 falcon512dyn* 1281 897 659 1556 Huge sig, small PK Picnic, SPHINCS+ gemss128* 14520 417408 33 417441 picnic2l1fs 49 33 12306 12339 rainbow1a 100209 152097 64 152161 Sphincsf128** 64 32 16976 17008 *Variants exist but don t change this much. **Slow/small SPHINCS+ cuts sig size in half

11. Comparing with RSA* SK size matters for implementations scheme sk size pk size sig size pk + sig dilithium2 7.3 3.1 5.3 8.4 All applications care about sig size falcon512dyn 3.3 2.3 1.7 4.1 gemss128 37.8 1087.0 0.1 1087.1 Most care about PK picnic2l1fs 0.1 0.1 32.0 32.1 Cert chains care about PK+sig rainbow1a 261.0 396.1 0.2 396.3 sphincsf128 0.2 0.1 44.2 44.3 *Sizes in terms of 3K RSA key and signature sizes

12. What Happens When We Go To Level 5*? scheme sk size pk size sig size pk+sig dilithium4 2.0 0.9 1.8 1.3 falcon1024dyn 1.2 0.9 0.7 0.8 gemss256 42.7 1877.0 0.1 938.5 picnicl5fs 0.1 0.0 66.8 33.4 rainbow6a 464.6 703.8 0.1 351.9 sphincsf256 0.1 0.0 25.6 12.8 * Compared to 16K RSA

13. Takeaways from size comparisons Dilithium and Falcon can be used now Probably won t break much But both keys and signatures get 3-8x as big as RSA Rainbow and GEMSS have wonderful signature size Sigs fit anywhere same or smaller than EDDSA sigs But public keys are enormous. Certificate chains are going to be a nightmare with these schemes. SPHINCS+ and Picnic have tiny public keys but huge signatures I can t think of any applications where tiny PK + huge sig is a win . Still, both are better for certificate chains than Rainbow/GEMSS!

14. How Much Slower Does Everything Get? All these are based on SUPERCOP data Best coverage is for high-end machines 64-bit Intel 64-bit ARM A little coverage of lower-end (four machines!) 32-bit ARM I compare everything to EDDSA Because SUPERCOP data always includes ED25519 We know it s something people can use now. Mostly concentrate on Level 1 security That s what I have the most data for A little data on Level 5 security at end.

15. Performance on Intel/AMD Desktop Machines* scheme dilithium2 falcon512dyn falcon512tree gemss128 bluegemss128 redgemss128 picnicl1fs rainbow1a SPHINCS128-f SHPINCS128-s keygen sign verify sign+verify 3.1 11.5 15.0 8.5 1.0 0.5 0.4 20.1 37.5 35.4 32.4 0.7 29.8 12.4 3.4 3.8 2.2 363.9 362.3 5831.4 6684.5 4842.4 51984.3 10282.8 223.4 133.5 11862.0 2372.3 78.3 55.4 0.2 19678.3 57.6 1843.4 4.4 1.6 1744.1 27387.5 420.4 6250.8 * Averaged from 37 machines

16. How about 64-bit ARM processors*? scheme dilithium2 falcon512dyn falcon512tree gemss128 bluegemss128 redgemss128 picnicl1fs rainbow1a SPHINCS128-f SHPINCS128-s keygen sign verify sign+verify 2.5 13.8 10.4 6.9 1.0 0.4 0.3 4.4 3.0 2.0 203.8 209.9 24815.9 14531.6 10031.3 152573.9 18413.6 375.3 194.4 147.3 128.1 123.9 51.8 1.2 15.1 6.3 39729.1 4876.4 189.2 88.8 0.1 10112.1 31.2 982.8 4.5 2.0 1077.7 15771.6 291.1 4100.2 * Averaged from 11 machines

17. Living on the Low End: 32-bit ARMs Average from 4 machines: A7, A9-NEON, A-17(2) scheme keygen sign verify sign+verify dilithium2 2.8 9.4 1.0 3.1 falcon512dyn 137.5 8.1 0.3 2.2 falcon512tree 139.2 5.3 0.2 1.5 picnicl1fs 0.2 101.2 29.6 47.7 rainbow1a 19750.9 7.6 1.7 3.2 SPHINCS128-f 25.2 757.9 10.6 199.6 SHPINCS128-s 806.7 11411.9 4.4 2889.7 * Nobody implemented any GEMSS variant on 32-bit ARMs, probably it didn t fit too well!

18. Across platforms: Signing*,+ Intel64 ARM64 ARM32 dilithium2 11.5 13.8 9.4 falcon512tree 8.5 6.9 5.3 redgemss128 223.4 375.3 #N/A picnicl1fs 133.5 194.4 101.2 rainbow1a 4.4 4.5 7.6 SPHINCS128-f 1744.1 1077.7 757.9 SPHINCS128-s 27387.5 15771.6 11411.9 * Some variants omitted I kept the best performers. + In terms of EDDSA signatures

19. Across platforms: verifying*,+ Intel64 ARM64 ARM32 dilithium2 falcon512tree redgemss128 picnicl1fs rainbow1a SPHINCS128-f SPHINCS128-s 1.0 0.4 35.4 32.4 0.7 29.8 12.4 1.0 0.3 1.0 0.2 123.9 51.8 1.2 15.1 6.3 #N/A 29.6 1.7 10.6 4.4 * Some variants omitted I kept the best performers. + In terms of EDDSA verifies.

20. Across Platforms: Signing+Verifying*,+ Intel64 ARM64 ARM32 scheme dilithium2 falcon512dyn falcon512tree redgemss128 picnicl1fs rainbow1a sphincs+128f 3.4 3.8 2.2 78.3 55.4 1.6 420.4 4.4 3.0 2.0 3.1 2.2 1.5 189.2 88.8 2.0 291.1 #N/A 47.7 3.2 199.6 * Some variants omitted I kept the best performers. + In terms of EDDSA sign+verify.

21. How many EDDSA sigs for one PQ sig*? 16.0 14.0 12.0 10.0 8.0 6.0 4.0 2.0 0.0 dilithium2 falcon512dyn falcon512tree rainbow1a Intel64 ARM64 ARM32 * I had to omit GEMSS, SPHINCS+, and PICNIC: they swamp everything else!

22. How many EDDSA verifies for one PQ verify*? 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0 Intel64 ARM64 ARM32 dilithium2 falcon512tree rainbow1a * I had to omit GEMSS, SPHINCS+, and PICNIC: they swamp everything else!

23. How About Level 5 Security? Speed in terms of EDDSA-Goldilocks (level 5) Average over 37 64-bit Intel/AMD processors scheme keygen sign verify dilithium4 1.9 4.9 0.6 falcon1024dyn 312.6 9.1 0.3 gemss256 4949.6 28505.1 1.7 picnicl5fs 0.1 166.0 43.9 rainbow6a 70783.6 8.3 2.3 sphincsf256sha256simple 63.8 1485.2 15.5

24. PQM4 DataData on low-end ARMs scheme keygen sign verify sign+verify dilithium2 1321024 4532604 1380727 5913331 falcon-512 189279143 39110245 474411 39584656 falcon-512-tree 195637141 17872505 475187 18347692 sphincs128-f 16552135 521963206 20850719 542813925 Cycle counts on an M4 at 24 MHz (downclocked to avoid memory wait states)

25. Comparing with Supercop Data Falcon looks much slower (more cycles) on PQM4 Supercop ARM32 cycles/PQM4 cycles scheme keygen sign verify sign+verify Likely cause (from David): no floating point unit. dilithium2 1.15 1.11 1.10 1.11 falcon512dyn 3.33 11.17 1.39 10.30 falcon512tree 3.40 7.75 1.65 7.07 sphincs+128-f 1.59 1.59 1.54 1.59

26. PQM4: Working Memory Needed to Operate (bytes) No comparable data from SUPERCOP. keygen sign verify dilithium2 36424 61312 40664 Suggests an advantage for falcon on low-end. falcon-dyn 1592 2540 512 falcon-tree 1584 2708 512 sphincs+128f 2192 2248 2544

27. Takeaways from Performance Comparison Falcon, Dilithium, and Rainbow aren t too painful Up to factor of 12 or so slowdown not great, but probably doable Falcon is really fast for verifying Rainbow is almost as good Sphincs+ and Picnic are very slow to sign messages GEMSS s performance is awful almost everywhere Don t know if this is bad implementation or inherent to algorithm. Better on high-end Intel/AMD platforms, but still bad.

28. Takeaways: Comparing Signatures Dilithium and Falcon Can be dropped into existing protocols using signatures Size and speed aren t too much worse Both based on lattices, but very different schemes. Picnic and Sphincs+ Huge signatures and small public keys Symmetric only, so based on less new assumptions Slow to verify, *very* slow to sign. Maybe some niche applications Rainbow and GEMSS Multivariate schemes Huge public keys, small signatures Rainbow speed is practical if public keys are pre-distributed GEMSS signature speed is terrible probably disqualifying

29. Based on Performance/Size Only. Dilithium, Falcon, and Rainbow probably should go to the immediate standardization bin SPHINCS+ and Picnic probably should go to the keep around as a fallback. I m not sure whether GEMSS should go into further study or go away bins.