See the introduction regarding proactively minimizing the complexity of a thorough security review, and see the general warnings regarding lattice-based cryptography.

Script to compute various security estimates

See the warnings in the script regarding overestimates, potential overestimates, underestimates, and potential underestimates:

• Latest version of script: estimate-20200927.sage.
• Previous version of script: estimate-20190329.sage.

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.