Script to compute various security estimates
See the warnings in the script regarding overestimates, potential overestimates, underestimates, and potential underestimates:
- Latest version of script:
- Previous version of script:
See also the "NTRU Prime: round 3" document for more detailed warnings.
The script computes 16 security estimates in the following 4 dimensions:
- Pre-quantum vs. post-quantum. ECC has a much stronger track record than lattice-based cryptography for pre-quantum security, so post-quantum security should be the main focus, but NIST also requires pre-quantum estimates.
- Free memory vs. real cost of memory. Free memory is a common oversimplification.
- Ignoring hybrid attacks vs. including hybrid attacks. Ignoring hybrid attacks is a common oversimplification.
- Sieving vs. enumeration. Enumeration generally produces smaller post-quantum estimates than sieving with real cost of memory, but sieving generally produces smaller estimates otherwise. Ignoring enumeration is a common oversimplification.
The estimates that assume free memory, ignore hybrid attacks, and ignore enumeration are often called "pre-quantum Core-SVP" and "post-quantum Core-SVP". Core-SVP is often incorrectly claimed to be a "conservative lower bound" on attack costs. NIST appears to rely on Core-SVP estimates. The Core-SVP estimates calculated by this script are typically 1 or 2 bits below Core-SVP estimates calculated by other available scripts, because this script carries out a somewhat more thorough search through attack parameters.
The following table shows pre-quantum Core-SVP for a selection of sizes for Streamlined NTRU Prime and NTRU LPRime. Post-quantum Core-SVP is about 10% below pre-quantum Core-SVP.
|System||Core-SVP||ciphertext bytes||public-key bytes|
Version: This is version 2020.10.31 of the "Security" web page.