LWE and NTRU security estimates

[Virdia, Fernando (2016)]

Dear PQC-Forum,

We have been looking at the LWE- and NTRU-based submissions and at the proposed cost models for lattice reduction, and have computed some complexity estimates for the primal-uSVP and dual lattice attacks on these schemes.

For each Round 1 submission, we extracted the LWE/NTRU parameters and (where applicable) the cost models and estimated the security of each scheme under every cost model encountered.

Our results can be found at https://estimate-all-the-lwe-ntru-schemes.github.io, more details on our approach can be found at https://estimate-all-the-lwe-ntru-schemes.github.io/paper.pdf. Code for reproducing all the results can be found at https://github.com/estimate-all-the-lwe-ntru-schemes/estimate-all-the-lwe-ntru-schemes.github.io, while for each particular estimate you can get stand-alone Sagemath code for reproducing it by clicking on its cell.

We would be grateful to get feedback from the community about the results. In particular, if we made any mistake extracting a parameter set or a cost model, please open a ticket at https://github.com/estimate-all-the-lwe-ntru-schemes/estimate-all-the-lwe-ntru-schemes.github.io/issues so that it can be corrected. With this work it is not our intention to support any particular cost model or scheme, but rather to provide a useful dataset for further analysis.

Best

Martin R. Albrecht

Benjamin R. Curtis

Amit Deo

Alex Davidson

Rachel Player

Eamonn Postlethwaite

Fernando Virdia

Thomas Wunderer

[Alperin-Sheriff, Jacob (Fed)]

So, having looked through this table a bit, it appears that you estimate significantly worse security than the authors only for Emblem/R.Emblem. Is this correct?

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.

[Mike Hamburg]

Also PapaBear, because of a typo in the ThreeBears spec.

[Fernando Virdia]

Dear Jacob

Emblem seems to cost using BKZ.sieve from [APS15], which translates
roughly to `8d-Sieve + O(1)` on our table. They do attain 128 bits of
classical security there, compatibly with NIST Category 1.

Our "Claimed" column is not currently very precise, since we failed at
finding exact costs from all the submissions, and hence in some cases
used 128 to mean AES128. It may be possibly appropriate to translate
AES128 to 64 bits of "quantum" claimed security.

It is also important to say that the APS15 estimator has been updated as
part of this project, in order to better cost attacks on small but
non-ternary secret (e.g. by scaling the uSVP embedding lattice), as
Emblem n=611 appears to be. This may be the reason why that particular
instance goes slightly below 128 bits under 8d-Sieve + O(1).

In any case, it might be best to wait with drawing conclusions until
designers had a chance to cross check our results for typos and the like.

Best

Fernando Virdia

Estimate all the {LWE, NTRU} schemes! team

On 31/01/18 18:47, Alperin-Sheriff, Jacob (Fed) wrote:
> So, having looked through this table a bit, it appears that you estimate
> significantly worse security than the authors only for Emblem/R.Emblem.
> Is this correct?
>

> *From: *"Virdia, Fernando (2016)" <Fernando.V...@live.rhul.ac.uk>
> *Date: *Wednesday, January 31, 2018 at 12:21 PM
> *To: *"pqc-...@list.nist.gov" <pqc-...@list.nist.gov>
> *Subject: *[pqc-forum] LWE and NTRU security estimates

>
> Dear PQC-Forum,
>
> We have been looking at the LWE- and NTRU-based submissions and at the
> proposed cost models for lattice reduction, and have computed some
> complexity estimates for the primal-uSVP and dual lattice attacks on
> these schemes.
>
> For each Round 1 submission, we extracted the LWE/NTRU parameters and
> (where applicable) the cost models and estimated the security of each
> scheme under every cost model encountered.
>
> Our results can be found at

> https://estimate-all-the-lwe-ntru-schemes.github.io<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Festimate-all-the-lwe-ntru-schemes.github.io&data=02%7C01%7Cjacob.alperin-sheriff%40nist.gov%7Cb66eff903a364dce189308d568cefe18%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C636530160598222567&sdata=3LY9KjRcSu9QviZMeLUCGJkhxgqr9CttbpFqUu5AtyM%3D&reserved=0>,

> more details on our approach can be found at

> https://estimate-all-the-lwe-ntru-schemes.github.io/paper.pdf<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Festimate-all-the-lwe-ntru-schemes.github.io%2Fpaper.pdf&data=02%7C01%7Cjacob.alperin-sheriff%40nist.gov%7Cb66eff903a364dce189308d568cefe18%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C636530160598222567&sdata=ywhXEhOnxDzyRyVkHEb1tJ3sTfPIRqwc8aWQP03Jq54%3D&reserved=0>.

> Code for reproducing all the results can be found at

> https://github.com/estimate-all-the-lwe-ntru-schemes/estimate-all-the-lwe-ntru-schemes.github.io<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Festimate-all-the-lwe-ntru-schemes%2Festimate-all-the-lwe-ntru-schemes.github.io&data=02%7C01%7Cjacob.alperin-sheriff%40nist.gov%7Cb66eff903a364dce189308d568cefe18%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C636530160598222567&sdata=V2yImXZm8xiQyro1S3ZvcQovmHoCC2coxoVveYcDtYo%3D&reserved=0>,

> while for each particular estimate you can get stand-alone Sagemath code
> for reproducing it by clicking on its cell.
>
> We would be grateful to get feedback from the community about the
> results. In particular, if we made any mistake extracting a parameter
> set or a cost model, please open a ticket at

> https://github.com/estimate-all-the-lwe-ntru-schemes/estimate-all-the-lwe-ntru-schemes.github.io/issues<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Festimate-all-the-lwe-ntru-schemes%2Festimate-all-the-lwe-ntru-schemes.github.io%2Fissues&data=02%7C01%7Cjacob.alperin-sheriff%40nist.gov%7Cb66eff903a364dce189308d568cefe18%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C636530160598222567&sdata=nTypsp8q4qXH%2FzrtzsF4fjjLWfYPuew45KbXmHyfVR4%3D&reserved=0>so

> that it can be corrected. With this work it is not our intention to
> support any particular cost model or scheme, but rather to provide a
> useful dataset for further analysis.
>
> Best
>
> Martin R. Albrecht
>
> Benjamin R. Curtis
>
> Amit Deo
>
> Alex Davidson
>
> Rachel Player
>
> Eamonn Postlethwaite
>
> Fernando Virdia
>
> Thomas Wunderer
>
> --
> You received this message because you are subscribed to the Google
> Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to

> pqc-forum+...@list.nist.gov<mailto:pqc-forum+...@list.nist.gov>.

[Thomas Prest]

Dear Martin, Benjamin, Amit, Alex, Rachel, Eamonn, Fernando and Thomas,

I believe that everyone here working on lattice-based schemes will agree
with me that your web page and associated paper are extremely helpful and
instructive. Thanks a lot!

Best,
Thomas

> --
> You received this message because you are subscribed to the Google Groups
> "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to pqc-forum+...@list.nist.gov.

[D. J. Bernstein]

> So, having looked through this table a bit, it appears that you estimate
> significantly worse security than the authors only for Emblem/R.Emblem.

I see the 2^68.90 "estimate" regarding EMBLEM-611, but I don't see a
clear statement of how the thing being estimated is supposed to be
related to the security of EMBLEM-611. Is there an attack that's

* claimed to break EMBLEM-611 and
* estimated to use 2^68.90 operations?

What exactly are the operations being counted, and what information is
available to justify using the estimate?

My impression is the 2^68.90 actually comes from

* taking a _small piece_ of a quantum attack against EMBLEM-611,
* dividing this piece into _expensive operations_,
* _asymptotically_ counting the number of these operations, and
* replacing o(1) in the asymptotics with 0.

Overall this looks to me like a massive underestimate of the actual cost
of the attack, even if we're super-optimistic about progress in quantum
computation. My impression is also that this cost gap varies from one
submission to another, so it's entirely possible for a submission that
has lower security against the same attack to have a higher number in
the table---which undermines the primary use of tables such as this.

Suppose a metric (for example, this one) is a wild guess that severely
underestimates the cost of an attack. The metric is then pushed to the
left in the table. This sorting makes the metric much more visible,
especially since there are so many columns in the table. Even if readers
take the time to look at the larger numbers, they'll generally use the
underestimates, since they'll incorrectly assume that the 14 columns are
reporting the costs of 14 different attacks and that the smallest column
is the security level against all known attacks.

Non-quantum estimates for EMBLEM-611 include 2^75.92 for "Core-Sieve"
and 2^141.74 for "Core-Enum+O(1)". Sorting by "Core-Sieve" I see the
following two systems listed at the top:

Core-Sieve Core-Enum+O(1)
EMBLEM n=611 75.92 141.74
uRound2.KEM n=500 83.74 125.93

These four numbers are telling completely different stories regarding
the security of EMBLEM-611 and uRound2.KEM-500. Is EMBLEM-611 hundreds
of times easier to break than uRound2.KEM-500, or thousands of times
harder? How do these compare to the "2^143 classical gates" that NIST
estimated for finding an AES-128 key (category 1)?

My impression is that the 75.92 and 83.74 are massive underestimates
(as above, except this time non-quantum). In the real world, public
experiments are passing 2^64 cycles and continue to show enumeration
beating sieving. Section 6.7 of the NTRU Prime submission identifies
serious errors in typical claims regarding the costs of sieving; for a
proper analysis one needs to look at the cost of hardware (offhand I'd
guess that the "Core-Sieve" shown above is using roughly 2^70 bits of
memory, while "Core-Enum" can fit inside a small GPU core) and then
account for communication costs and parallelism.

If there's a serious argument that sieving beats enumeration within
feasible cryptanalytic computations despite these effects, then this
argument should be presented in a paper for further analysis. Yes,
getting the numbers right is real work, but what's the alternative?
Saying that it's "conservative" to massively underestimate costs is
missing the point: if EMBLEM-611 is more secure than uRound2.KEM-500,
but a massive underestimate of costs is telling users to switch from
EMBLEM-611 to uRound2.KEM-500, then security has been reduced.

Of course a central database of lattice dimensions etc. is useful, but
this doesn't mean that the database should be fed through every
available "estimate" without regard to accuracy.

---Dan

[Alperin-Sheriff, Jacob (Fed)]

This is basically in line with their response to me.