Performance of Post-Quantum Signatures: Analysis and Comparison

 
Performance of PQ Sigs
 
John Kelsey, NIST, March 2020
 
Remaining PQ Signatures
 
Lattice-based
Dilithium
QTesla
Falcon
 
Symmetric
Sphincs+
Picnic
 
Multivariate
GEMSS
Rainbow
LUOV
MQDSS
 
Remaining PQ Signatures
 
Lattice-based
Dilithium
Qtesla
 
(Broken)
Falcon
 
Symmetric
Sphincs+
Picnic
 
Multivariate
GEMSS
Rainbow
LUOV 
 
(Broken)
MQDSS
 
(Broken)
 
So we have six left
 
Lattice-based
Dilithium
  
} These are very different schemes, even though based on
Falcon
  
} the same underlying kind of problem.
 
Symmetric
Sphincs+
  
} These have almost nothing in common with each other
Picnic
  
} except huge, slow signatures.
 
Multivariate
GEMSS
  
} These also look pretty different to me, but I’m not confident
Rainbow
  
} in my assessment.
 
Properties
 
Lattice-based
Dilithium
  
} Reasonable performance on sign and verify.
Falcon
  
} PK and signature bigger than RSA/ECDSA but not too bad.
Symmetric
Sphincs+
  
} Tiny public keys, enormous signatures.  Very slow.
Picnic
  
} Security based on symmetric crypto.
Multivariate
GEMSS
  
} Huge public keys, tiny signatures.
Rainbow
  
} Fast signing and verifying.
 
What does it look like to put these into use?
 
TLS
Code signing
Firmware updates
Signed email
Signed logs and logcrypt
Etc.
 
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?
 
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
 
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
 
How Big are Signatures and Keys?
 
 
Both reasonable
Dilithium, Falcon
 
Small sig, huge PK
Rainbow, GEMSS
 
Huge sig, small PK
Picnic, SPHINCS+
 
 
*Variants exist but don’t change this much.    **Slow/small SPHINCS+ cuts sig size in half
 
Comparing with RSA*
 
SK size matters for
implementations
 
All applications care
about sig size
 
Most care about PK
 
Cert chains care
about PK+sig
 
 
*Sizes in terms of 3K RSA key and signature sizes
 
What Happens When We Go To Level 5*?
 
* Compared to 16K RSA
 
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!
 
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.
 
Performance on Intel/AMD Desktop Machines*
 
* Averaged from 37 machines
 
How about 64-bit ARM processors*?
 
* Averaged from 11 machines
 
Living on the Low End: 32-bit ARMs
 
* Nobody implemented any GEMSS variant on 32-bit ARMs, probably it didn’t fit too well!
 
Across platforms: Signing
*,+
 
* Some variants omitted—I kept the best performers.    + In terms of EDDSA signatures
 
Across platforms: verifying
*,+
 
* Some variants omitted—I kept the best performers.    + In terms of EDDSA verifies.
 
Across Platforms: Signing+Verifying
*,+
 
* Some variants omitted—I kept the best performers.    + In terms of EDDSA sign+verify.
 
How many EDDSA sigs for one PQ sig*?
 
* I had to omit GEMSS, SPHINCS+, and PICNIC: they swamp everything else!
 
How many EDDSA verifies for one PQ verify*?
 
* I had to omit GEMSS, SPHINCS+, and PICNIC: they swamp everything else!
 
How About Level 5 Security?
 
PQM4 Data—Data on low-end ARMs
 
Cycle counts on an M4 at 24 MHz (downclocked to avoid memory wait states)
 
Comparing with Supercop Data
 
Falcon looks
much slower
(more cycles)
on PQM4
 
Likely cause
(from David):
no floating
point unit.
 
PQM4: Working Memory Needed to Operate
(bytes)
 
No comparable
data from
SUPERCOP.
 
Suggests an
advantage for
falcon on low-end.
 
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.
 
 
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
 
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.
Slide Note
Embed
Share

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.


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.

E N D

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.

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#