Accuracy of BKZ-blocksize prediction for lattice attacks against NTRU

[Leo Ducas]

Dear colleagues,

Disclaimer: this post *does not* challenge NTRU concrete security claims.

Earlier this year, together with Dana, Huijing and Melissa [DDGR20], we proposed scripts for refined security estimates of LWE as part of the `leaky-LWE-estimator' [Git-LLWEE]. In a second version, some adaptations were made to also provide refine estimates for NTRU, in particular adaptation for the fact the the underlying NTRU lattice contains not one but several short vectors.

However, this prediction for NTRU were not tested against experimental evidence, unlike the refined estimates for LWE. This message, together with a branch on the `leaky-LWE-estimator' [Git-LLWEE-NTRU], aims at filling this void.

There could be two sources of concerns regarding these estimates specific to the case of NTRU:
1/ The lack of independence between the n many short vector solutions
2/ A possible `dense-sublattice' effect. Indeed [KF16] showed such an effect exists in "extreme" regimes, but the analysis is based on a worst-case argument: it could be that this effect still exists for more standard regimes, but escape our analysis. The "phase-transition" between both regimes seems beyond our current understanding.

It appears that experiments (data given below) dismisses such concerns: the predictions of the successful BKZ-blocksize β for NTRU with "standard" parameters given by that scripts are very close to experiments: as the dimension grows, they converge up to one bikz or so, both for LWE and for NTRU.

In conclusion: w.r.t. to the current form of the primal lattice attack, NTRU is slightly weaker than LWE for the same parameters, and we seem to have a fair understanding of the phenomenon, both quantitatively and qualitatively.

Best regards
-- Leo


[DDGR20]
LWE with Side Information: Attacks and Concrete Security Estimation
Dana Dachman-Soled and Léo Ducas and Huijing Gong and Mélissa Rossi
https://eprint.iacr.org/2020/292

[KF16]
Comparison between Subfield and Straightforward Attacks on NTRU
Paul Kirchner and Pierre-Alain Fouque
https://eprint.iacr.org/2016/717

[Git-LLWEE]
https://github.com/lducas/leaky-LWE-Estimator

[Git-LLWEE-NTRU]
https://github.com/lducas/leaky-LWE-Estimator/tree/NTRU_keygen

LWE/NTRU Instances:
- modulus q=512
- secrets/errors: uniform ternary
- prime n

Experiments:
- averaged over 100 trials (using 10 cores)

Commands:
In folder leaky-LWE-Estimator/NTRUvsLWE
>  sage lwe_experiments.sage 100 10
>  sage ntru_experiments.sage 100 10

Data:

LWE (m=n)

n,         exp. β,    pred.  β

37,      2.000,     2.000
41,      2.000,     2.000
47,      2.000,     2.035
53,      2.350,     2.596
59,      5.310,     5.736
67,      12.220,    15.020    
71,      17.560,    19.665    
79,      25.880,    27.583
83,      29.920,    31.315
89,      36.740,    36.733
97,      42.870,    43.781
101,     46.820,    47.228
107,     52.620,    52.637
113,     58.880,    58.546

NTRU
                
n,         exp. β,    pred.  β

37,      2.000,     2.000
41,      2.000,     2.000
47,      2.000,     2.000
53,      2.000,     2.000
59,      2.010,     2.000
67,      2.320,     4.205
71,      2.820,     9.000
79,      9.530,     19.233
83,      15.390,    23.193
89,      23.340,    28.832
97,      31.650,    36.104
101,     35.990,    39.510
107,     42.580,    44.663
113,     48.630,    49.643   

[D. J. Bernstein]

Leo Ducas writes:
> In conclusion: w.r.t. to the current form of the primal lattice
> attack, NTRU is slightly weaker than LWE for the same parameters

Do I correctly understand that "same parameters" here means same noise
distribution, not just same dimension and modulus (and samples)?

For many proposed RLWE/RLWR parameters, the security level of the actual
RLWE-based/RLWR-based cryptosystems (Product NTRU) given decryption
failures appears to be considerably worse than the security level
against lattice attacks (although in some cases this depends on how
security is measured). Switching from those cryptosystems to Quotient
NTRU with the same dimension, same modulus, and same noise distribution
often produces smaller decryption-failure rates (exact numbers depend on
the exact strategies for rounding, error correction, etc.) and thus
_increases_ cryptosystem security against the best attacks known,
contradicting what readers would understand from the above quote.

It's more useful to compare cryptosystems with the same dimension, same
modulus, and the _same failure rate_, so that decryption-failure
security is equalized (as far as we know!), and to then compare lattice
security. Also, a high failure rate would swamp any differences in
lattice security levels, so the failure rate should be low.

(People trying hard to control risks will want lattice attacks analyzed
for the possibility of big improvements even if the known attacks are
less threatening than other attacks, but the same people will take
failure rate 0 anyway. In the opposite direction, there are people who
think failure rate 0 is a stronger defense than needed, but the idea of
simply _ignoring_ quantitative failure rates is untenable given how much
damage we've seen decryption-failure attacks causing. Any clear design
strategy should be able to say what failure rate is acceptable, and then
hopefully it's clear how to calculate the amount of noise allowed.)

This type of direct cryptosystem comparison, with equal failure rates,
already appears in the NTRU Prime submission. There are both Product
NTRU and Quotient NTRU options, with the same rings, and with the noise
distribution chosen in each case to allow a simple proof that the
failure rate is 0 (guaranteeing that there are no failure attacks). The
submission calculates Core-SVP and other estimates of lattice security
for both cryptosystems, accounting for the lower noise in one
cryptosystem and the rotations in the other cryptosystem.

Concretely, sntrup761 ends up with Core-SVP 2^153 while ntrulpr761 ends
up with Core-SVP 2^155. This is a much smaller difference than one would
expect from extrapolating the numbers in the message I'm replying to.
This in turn is because sntrup761 has a larger noise distribution, which
gains almost as many bits in Core-SVP as are lost through rotations.

The NTRU Prime submission also surveys many problems with Core-SVP,
including problems with the standard rotation analysis. For example, the
standard analysis doesn't account for the fact that rotations for NTRU
Prime generally increase in size (whereas for NTRU Classic they're all
the same size), and doesn't account for the fact that multiples larger
than rotations might also be found. The gap between 2^153 and 2^155 can
easily be reversed (or increased!) by small changes in the analysis, so
conclusions about what's quantitatively more secure are unwarranted.

https://eprint.iacr.org/2020/292 (Table 4) says block size 508.47 on
average for ntruhps2048677 (including a bonus from exploiting the
constant-sum noise in that system), while checking the NTRU submission
(Table 5) I see ntruhps2048677 claiming block size only 496. Does this
mean that https://eprint.iacr.org/2020/292 generally ends up less
optimistic for the attacker than the standard rotation analysis?
Concretely, how does this analysis compare sntrup761 to ntrulpr761?

Saying "NTRU is slightly weaker than LWE for the same parameters" as a
"conclusion" isn't an appropriate way to summarize what's going on here.
It's failing to note (1) that the underlying rotation effect has already
been included in NTRU analyses for many years and (2) that there's an
effect in the opposite direction reducing security of _cryptosystems_
based on RLWE. Previous quantitative comparisons of these two effects
say that RLWE could be stronger _or weaker_ for equal failure rates.

Obviously there's also the possibility of improved attacks in either
direction. It's possible, for example, that the extra samples released
in RLWE-based cryptosystems reduce the security levels of those systems
far below Quotient NTRU systems---even if the RLWE-based systems have
"the same parameters" and worse failure rates! This could even be true
for _known_ attacks, depending on the exact parameter choices. It could
even be true for known attacks against parameters proposed in NISTPQC.
One shouldn't overstate how much is known about this comparison.

> and we seem to have a fair understanding of the phenomenon, both
> quantitatively and qualitatively.

The numbers shown seem to say that the latest analysis is disproven by
the experiments: it tends to overestimate security. It's hard to be sure
about this, since the only statistic provided for each size is the
average; there are enough sizes for a crude meta-analysis, and that's
what I'm referring to when I say "seem", but there are likely to be
confounding factors, and in any case there's no basis for confidence.

I would suggest following standard statistical practice of showing the
average _and_ the variance, and doing many more experiments for each
size. Best guess at this point is that this will provide solid evidence
(say six sigmas at reasonable cost) that the new analysis is inaccurate.

There's also a missing comparison to previous work. The literature
already contains various NTRU attack experiments and various related
analyses (which I'm not saying are consistent!). Could it be that the
new analysis is _less_ accurate than previous analyses? One would expect
a table directly comparing results from these analyses to results from
various previous analyses.

---Dan

[Leo Ducas]

Dear Dan,

thank you for your kind review.

Do I correctly understand that "same parameters" here means same noise
distribution, not just same dimension and modulus (and samples)?

Yes, same everything: dimension n, (samples m=n), modulus q and noise distribution. I.e. I am comparing the underlying problems, not the concrete cryptosystems submitted to the NIST.

 

It's more useful to compare cryptosystems with the same dimension,

same modulus, and the _same failure rate_,

Not when the concerns are the one I was trying to clarify, no. I'm not questioning best design, I am trying to understand the differences in the underlying problems. The later is a sub-question of the former, and is better treated in isolation.

https://eprint.iacr.org/2020/292 (Table 4) says block size 508.47 on
average for ntruhps2048677 (including a bonus from exploiting the
constant-sum noise in that system), while checking the NTRU submission
(Table 5) I see ntruhps2048677 claiming block size only 496. Does this
mean that https://eprint.iacr.org/2020/292 generally ends up less
optimistic for the attacker than the standard rotation analysis?

In the paper, we state: " However, due to the other approximations made in [43], our refined analysis does not invalidate the original security claims."

More specifically, the NTRU specs uses a lower on the length of the secrets f and g rather than their exact length (I suspect, for the purpose of avoid the lattice rescaling step in the analysis).

 

Saying "NTRU is slightly weaker than LWE for the same parameters" as a
"conclusion" isn't an appropriate way to summarize what's going on here.
It's failing to note (1) that the underlying rotation effect has already
been included in NTRU analyses for many years

And I'm confirming the effect of rotations, except that I am suggesting a slightly larger gap. I didn't mean to claim novelty on this part. Again the post is about saying that most of those analysis had not been experimented with before, which could raise concerns, especially the one listed as 1/ and 2/.

The numbers shown seem to say that the latest analysis is disproven by
the experiments: it tends to overestimate security.

The numbers are sufficient to lift my own concerns of significant impact from 1/ and especially 2/, which was the whole point of the message.

Scripts are provided for those interested in gathering more data for answering other questions than 1/ and 2/.

> There's also a missing comparison to previous work.

The DDGR paper gives a clear and direct comparison to the method of May and SIlverberg for exploiting rotation:

" Our results are compiled in Table 4 and Table 5, and the conclusion is, according to the probabilistic simulation method, that it is seems preferable to not make any guesses, and let lattice reduction naturally exploit the presence of many short vectors. "

Regards
-- Leo

[Leo Ducas]

> May and SIlverberg

I meant May and Silverman. Apologies to Alice and Joseph for this confusion.

-- Leo

[Leo Ducas]

https://eprint.iacr.org/2020/292 (Table 4) says block size 508.47 on
average for ntruhps2048677 (including a bonus from exploiting the
constant-sum noise in that system), while checking the NTRU submission
(Table 5) I see ntruhps2048677 claiming block size only 496. Does this
mean that https://eprint.iacr.org/2020/292 generally ends up less
optimistic for the attacker than the standard rotation analysis?

In the paper, we state: " However, due to the other approximations made in [43], our refined analysis does not invalidate the original security claims."

Actually, there is even more explicit answer in the paper already, top of p28:

" A third remark is that, even without hints, and using the same GSA-intersect method, ourtool gives about 10 extra bikz of security to NTRU-HPS compared to the analysis given in thestandardization document [43]. The largest part of this difference can be accounted for by thefact that [43] uses a lower-bound on the length of one half of the secret. Such a simplification avoids the need for an isotropization step, which would complicate an ad-hoc script, but is fully automatized by our tool. "

 

-- Leo