|
The report is pretty interesting- > The NTRU Prime submission [60], which consists of two structured-lattice-based cryp-
tosystems, was first proposed in [231] as an exploration of the design space of “NTRU-
like” cryptosystems, with the goal of reducing the attack surface with only minor loss of
efficiency.
Design. NTRU Prime has several unusual design features. It has two variants: Streamlined
NTRU Prime, which is modeled after the original NTRU, and NTRU LPRime, which com-
bines some aspects of NTRU with some aspects of Ring-LWE cryptosystems (in the style
of Lyubashevsky-Peikert-Regev [150]). In addition, NTRU Prime is constructed over a dif-
ferent ring: the “NTRU Prime ring,” Zq[x]/(x
p −x−1). Finally, certain key parts of NTRU
Prime are designed to operate deterministically (e.g., using rounding rather than random
noise and eliminating the possibility of random decryption failures). The submitters have
argued that these features improve the security of the scheme.
Security. The current version of NTRU Prime has performance and concrete security es-
timates (e.g., quantitative estimates of the computational resources required for usage and
cryptanalysis) that are roughly comparable to other lattice-based cryptosystems.13 As a
result, the current version of NTRU Prime is notable more for its unusual design features,
and claims that it offers higher security in a qualitative sense.
In order to state these claims, the designers of NTRU Prime have advocated for a spe-
cific approach to security analysis, based on a taxonomy of security risks [15]. This taxon-
omy is used to justify various design decisions, such as using rounding rather than random
noise, and eliminating the possibility of decryption failures. However, some care is needed
when reading this taxonomy, as it is a matter of subjective judgement which risks are the
most serious and what is the best way of mitigating those risks.
One particular issue is the choice of the NTRU Prime ring (rather than a cyclotomic
ring), which is claimed to eliminate the possibility of certain kinds of algebraic attacks.
To date, most work on the cryptanalysis of algebraically structured lattices (see Appendix
C) has focused on cyclotomic rings, because they are widely used and simpler to analyze.
Relatively little is known about the security of cryptographic schemes that use the NTRU
Prime ring. ... > Overall assessment. The case for NTRU Prime relies substantially on the claim that its
unusual choice of ring provides a security benefit over the algebraic structures used by the
other lattice candidates, i.e., the claim that (1) there is likely to be an attack that signifi-
cantly diminishes the security of NTRU, KYBER, and Saber, and (2) no similar attack is
likely to affect NTRU Prime. At the end of the third round, the evidence for these two
points is not particularly convincing. No algebraic attack has been published that directly
impacts the concrete or asymptotic security of any of the third-round structured lattice can-
didates.14 From a practical perspective, it seems likely that an unexpected breakthrough in
cryptanalysis of any structured lattice scheme would reduce the community’s confidence
in all such schemes, including NTRU Prime.
For these reasons, NIST is not moving NTRU Prime to the fourth round of the evalua-
tion process. In order to hedge against the possibility of a security vulnerability involving
structured lattice KEMs, NIST will consider standardizing a KEM that is not based on
lattices, after a fourth round of evaluation. |