malb
Discrepancy in Dense Sublattice Attack Estimation Between Old and New Versions
I noticed a non-negligible gap between the estimations for the dense sublattice attack embedded in the NTRU primal module when comparing the old and new versions of the tool from https://github.com/WvanWoerden/NTRUFatigue/tree/main
Specifically, I observed the following differences for the case where $n=1024$, $q=65537$, and $\sigma=2$:
Old Version: $\beta = 657$, Time complexity: $2^{214.9}$
New Version: $\beta = 936$, Time complexity: $2^{292.8}$
As we can see, the new version reports a significantly higher value for $\beta$ and a larger time complexity. This raises the question of whether this is due to a more precise analysis or if there is an error in the new implementation.
Questions:
- Are there any updates or changes in the assumptions, parameters, or methods in the new version that would explain this significant increase in $\beta$ and time complexity?
- Could there be an error in the new version of the tool that caused the discrepancy in the time complexity estimation?
- Is there any documentation or clarification available that explains this change in the results?
Looking forward to any insights or explanations regarding this discrepancy.
Hi. Apologies for taking so long to look into this. I am having difficulties reproducing this bug exactly. There is no change in the dense sublattice estimation code between the initial commits when the NTRU module was added and now. How did you manage to obtain these two results?
I obtain the results through:
where $\beta$ under NTRUFatigue is 654 while $\beta$ under lattice estimator is 936.
Also, I'm afraid that I'm confused with standard deviation and variance in NTRUFatigue, then I obtain the other results through:
where $\beta$ under NTRUFatigue is 707 while $\beta$ under lattice estimator is 936, still not aligned.
Did I misunderstand anything?
I’ve identified the cause of the discrepancy. The PrimalDSD implementation in lattice-estimator considers only the DSD attack, whereas combined_attack_prob in NTRUFatigue evaluates both SKR and DSD. The SKR case is handled in PrimalUSVP in lattice-estimator, and a minor deviation also arises from differences in the underlying simulation model. This issue can be closed.
