Complexity estimates for running the primal-uSVP and dual attacks against all LWE-based, and the primal-uSVP attack against all NTRU-based, Round 1 schemes proposed as part of the PQC process run by NIST. We make use of the [APS15] estimator. The code for generating this table is available on Github, as well as the paper. Clicking on a particular estimate cell in the table will provide with stand-alone Sagemath code for reproducing the estimate.

Below, we provide LWE-equivalent parameters, where n = LWE secret dimension, k = MLWE rank (if any), q = modulo, Ļƒ = standard deviation of the error, ā„¤q/(šœ™) is the ring (if any). For NTRU schemes we provide ā€–fā€–, ā€–gā€– = lengths of the short polynomials. If you spot a mistake in a parameter set or cost model, please feel free to open a ticket or to make a pull-request.

We stress that the columns under "Proposed BKZ cost models" give different cost estimates for the same attack, i.e. the primal-uSVP attack in one case and dual attack in another. Many of these estimates explicitly are lower bounds (under some assumptions). Thus, a relatively small number in one of those columns does not necessarily correspond to a known attack on the scheme given in the corresponding row. Given that the numbers in different columns diverge greatly, most of these estimates must be either too optimistic or pessimistic for the attacker.

Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn Postlethwaite, Fernando Virdia, Thomas Wunderer.