Why Did NIST Pick Dilithium and FALCON?
When both of them are lattice-based methods and Dilithium is so much faster
--
And, so, NIST selected Dilithium for quantum robust digital signatures. But, they are also taking forward FALCON and SPHINCS+. While SPHINCS+ is a hash-based signature method, FALCON is a lattice method such as Dilithium. Why did NIST pick two lattice methods?
Well, first we will analyse why Dilithium was selected. If run a test, we get that we can achieve 51,315 key pair iterations in three seconds [here]:
Operation | Iterations | Total time (s) | Time (us): mean | pop. stdev | CPU cycles: mean | pop. stdev
------------------------------ | ----------:| --------------:| ---------------:| ----------:| -------------------------:| ----------:
Dilithium2 | | | | | |
keypair | 51315 | 3.000 | 58.463 | 175.138 | 116511 | 349422
sign | 17473 | 3.003 | 171.848 | 1143.485 | 342726 | 2281463
verify | 53125 | 3.001 | 56.486 | 176.715 | 112506 | 351939But when we try FALCON, it is much slower with only 243 key pair interations in three seconds [here]:
Falcon-512 | | | | | |
keypair | 243 | 3.003 | 12358.128 | 3272.904 | 24656358 | 6530080
sign | 5512 | 3.001 | 544.379 | 429.848 | 1085984 | 857600
verify | 32518 | 3.000 | 92.257 | 200.913 | 183949 | 400840The mean time for a keypair generation for Dilithium2 is thus 58us, while it is 12,358us for FALCON-512. Thus, Dilithium is so much faster than FALCON. So why did NIST select FALCON for standardization? We find the answer in the key and signature size. In the following table, we see the size of the…
