We provide an estimator for all 5 LWE-based NIST candidates by using the hybrid dual attack based on our paper https://eprint.iacr.org/2021/152.
It includes 3 algorithms:
- dual: the standard dual attack;
- HYBRID1: the hybrid dual attack which guesses all possible vectors of the secret;
- HYBRID2M: the hybrid dual attack with optimal pruning and efficient matrix multiplication.
Users can select different cost models and assumptions by setting different values to "costmodel" and "asm".
To verify our results in Table 1 for the 5 LWE-based NIST candidates, one just need to run the estimator directly. The estimator only take less than 2 minutes for the core-SVP model, and it takes about 10 minutes for the practical model.
Among all the schemes, estimating Frodo takes the most time as its secret range is very large. Therefore, for Frodo, we use the following strategy to accelerate the estimator. We reduce the "tk" for this kind of schemes with large secret range. For example, the secret range of Frodo640 is (-12,12), then the exact value of "tk" is 13. We set this value to 7 so that the estimator will finish in 2 minutes (for the classical core-SVP oracle). Note that this strategy gives us an “upper bound” for the estimation. Nevertheless, the influence of this change on the result is very small. The recommended values for Frodo976 and Frodo1344 are 6 and 5, respectively.
| Table1: Estimations under classical core-SVP model and assumption from [ADPS16] | |||||||
| Name | Security Level | Dual | HYBRID 2M | ∆ | |||
| λ | λ | r | b | m | |||
| Kyber512 | 1 | 117 | 114 | 13 | 389 | 500 | 3 |
| Kyber768 | 3 | 181 | 175 | 24 | 598 | 676 | 6 |
| Kyber1024 | 5 | 253 | 245 | 34 | 836 | 864 | 8 |
| Saber512 | 1 | 117 | 114 | 11 | 390 | 531 | 3 |
| Saber768 | 3 | 189 | 184 | 20 | 627 | 739 | 5 |
| Saber1024 | 5 | 258 | 250 | 31 | 854 | 908 | 8 |
| Dilithium1024 | 2 | 123 | 121 | 14 | 415 | 1028 | 2 |
| Dilithium1280 | 3 | 181 | 179 | 15 | 613 | 1356 | 2 |
| Dilithium1792 | 5 | 251 | 246 | 30 | 843 | 1716 | 5 |
| Frodo640 | 1 | 141 | 139 | 10 | 475 | 640 | 2 |
| Frodo976 | 3 | 205 | 202 | 17 | 689 | 976 | 3 |
| Frodo1344 | 5 | 270 | 264 | 28 | 903 | 1257 | 6 |
| NTRULPrime653 | 1 | 130 | 125 | 25 | 424 | 531 | 5 |
| NTRULPrime761 | 2 | 155 | 148 | 38 | 501 | 590 | 7 |
| NTRULPrime857 | 2 | 176 | 168 | 46 | 569 | 655 | 8 |
| NTRULPrime953 | 3 | 195 | 187 | 44 | 635 | 726 | 8 |
| NTRULPrime1013 | 4 | 209 | 200 | 45 | 681 | 783 | 9 |
| NTRULPrime1277 | 5 | 269 | 256 | 90 | 867 | 936 | 13 |
To estimate a new scheme other than those 5 NIST candidates, one need to provide the parameters of the scheme. Note that for the schemes that error and secret are from different distributions, one need to compute the scaling factor "c" in the parameter sets.
The secret of NTRULPrime follows a distribution with a fixed Hamming weight. To unify the code, our estimator does not consider this restriction. The difference caused by this is negligible.