hybrid-dual-estimator

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:

1. dual: the standard dual attack;
2. HYBRID1: the hybrid dual attack which guesses all possible vectors of the secret;
3. 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".

Verify the results

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

Estimate a new scheme

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.

Remarks

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.