Category 5 NTRU parameters

[John Schanck]

Dear pqc-forum,

NIST has formally requested category 5 parameter sets from the NTRU team.

We surveyed the options, and we have decided to recommend:
1. the NTRU-HPS parameter set with q=4096 and n=1229, and
2. the NTRU-HRSS parameter set with n=1373.

Reference implementations are available at:
https://github.com/jschanck/ntru.

Our analysis using the "Beyond Core-SVP" assumptions finds that the
best known RAM model attack on ntruhps40961229 requires 2^301 bit
operations and uses 2^199 bits of memory. Similarly, the best known
RAM model attack on ntruhrss1373 requires 2^310 bit operations and
2^205 bits of memory.

The attached graph ("ntru_cat5_options.png") shows the size and
security of the options that we considered. It also shows the size and
security of Kyber1024, FireSaber, and sntrup1277. Additional data is
given in a tables below.

Some comments:

* Our recommendation of n=1373 for NTRU-HRSS follows the same logic
that we used in selecting ntruhrss701: n=701 is the largest value
that is compatible with q=2^13; n=1373 is the largest value that
is compatible with q=2^14.

* The NTRU-HPS parameter set with q=4096 and n=1061, which we are
not recommending, has public keys and ciphertexts that are only
22 bytes larger than Kyber1024. Our current analysis suggests
that this parameter set can be broken with 2^264 bit
operations and 2^173 bits of memory. This falls short of the
2^272 bit operations that are needed for category 5. We expect
that this parameter set is more secure than AES-256, but we are
not recommending it at this time.

Cheers,
John (on behalf of the NTRU team)

---

NTRU-HPS options
----------------
n | β | Core-SVP | Beyond Core-SVP | Sieve memory | pk bytes
1061 | 806 | 235.4 | 264.3 | 173.1 | 1590
1123 | 855 | 249.7 | 278.0 | 182.9 | 1683
1229 | 939 | 274.2 | 301.6 | 199.5 | 1842
1277 | 977 | 285.3 | 312.6 | 207.1 | 1914
1373 | 1054 | 307.8 | 334.2 | 222.4 | 2058

NTRU-HRSS options
-----------------
n | β | Core-SVP | Beyond Core-SVP | Sieve memory | pk bytes
1277 | 890 | 259.9 | 288.3 | 189.9 | 2234
1373 | 970 | 283.2 | 310.7 | 205.6 | 2401

NB: The values of β listed above were generated using the scripts
from [1]. These scripts rely on an outdated analysis, and in the future
we will likely use the scripts from [2]. The "Beyond Core-SVP" and
"Sieve memory" columns use tables from [3] and the python script that
is copied below.

[1] https://github.com/jschanck/estimator
[2] https://github.com/lducas/leaky-LWE-Estimator
[3] https://github.com/jschanck/eprint-2019-1161


---

import os
import csv
from math import log as ln, ceil, pi as PI, e as EXP1

def log2(x): return ln(x) / ln(2)

def load_csv(f, metric):
filename = os.path.join("data", "cost-estimate-{f}-{metric}.csv")
filename = filename.format(f=f, metric=metric)
with open(filename, "r") as csvfile:
csvreader = csv.DictReader(csvfile, delimiter=",", quotechar='"',
quoting=csv.QUOTE_MINIMAL)
D = {int(L['d']) : L for L in csvreader}
return D

def linear_interp_cost(b, data, field='log_cost'):
assert(b >= min(data))
assert(b <= max(data))
if b in data: return float(data[b][field])

bl = max(x for x in data if x <= b)
bh = min(x for x in data if b <= x)
p = (b - bl)/(bh - bl)
return log2((1-p)*2**float(data[bl][field]) + p*2**float(data[bh][field]))

def adjust(b):
return b - ceil(b*ln(4/3)/ln(b/(2*PI*EXP1)))

if __name__ == '__main__':
gates = load_csv("list_decoding", "classical")
memory = load_csv("sieve_size", "vectors")

progressivity_overhead = 2*log2(5.46)

params = [ # Current parameters (n, β)
(509, 364), (677, 496), (701, 466), (821, 612),
# HPS category 5 options
(1061, 806), (1123, 855), (1229, 939), (1277, 977), (1373, 1054),
# HRSS category 5 options
(1277, 890), (1373, 970)
]

print("n","β","d4f","gates","mem",sep='\t')
for (n,b) in params:
d = 2*n
sieve_dim = adjust(b)
d4f = b-sieve_dim
log2_sieve_calls = log2(d-b) + progressivity_overhead
log2_sieve_gates = linear_interp_cost(sieve_dim, gates)
log2_sieve_vecs = linear_interp_cost(sieve_dim, memory, 'log2_size')
log2_bits_per_vec = log2(8*sieve_dim)
g_cost = float(log2_sieve_calls + log2_sieve_gates)
m_cost = float(log2_bits_per_vec + log2_sieve_vecs)
print(n,b,d4f,f'{float(g_cost):.1f}',f'{float(m_cost):.1f}',sep='\t')

[Blumenthal, Uri - 0553 - MITLL]

First, thanks to the NTRU team for providing the category 5 parameter sets!

My personal opinion - a parameter set [that you do not recommend], whose public key/ciphertext sizes are closer to Kyber-1024, has sufficient strength and better usability for those who require category 5.

Please consider submitting the HPS with q=4096 and n=1061 parameter sets, in addition to what you provided.

I leave it to NIST to decide and declare whether the "2^272 bit operations" requirement is carved in stone, or "can be broken with 2^264 bit operations and 2^173 bits of memory" is good enough to satisfy the category 5 entry criteria. As I said, in my opinion it's good enough.

Thanks!
--
Regards,
Uri

There are two ways to design a system. One is to make is so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
- C. A. R. Hoare

--
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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20210621135026.2ocgbhzxbkuritrx%40weil.