NTRU in eprint

[david.n...@gmail.com]

Dear colleagues

I wanted to attract your attention to the recent eprint of ours https://eprint.iacr.org/2021/1426

This attack is out of the specifications of the competition but we feel that it mandates that FO be used systematically in all NTRU implementations.

We would be grateful to get any comments concerning this eprint if any.

Kind regards

David

[D. J. Bernstein]

david.n...@gmail.com writes:
> This attack is out of the specifications of the competition but we feel that it
> mandates that FO be used systematically in all NTRU implementations.

I think people reading the paper (e.g., "Almost all lattice-based
cryptographic schemes in the NIST competition use FO, except NTRU" etc.)
will get the idea that there's an objection here to the NTRU submission.

However, mathematically, the NTRU submission _does_ use FO, including
the usual reencryption check.

If this were done by plugging a PKE into a generic FO layer then it
would produce a slowdown, so the submission merges reencryption into the
specified decapsulation algorithm in a way that makes the slowdown easy
to see and remove, and then removes it. This (as the submission briefly
mentions on page 25) doesn't change the output.

The NTRU submission describes this as avoiding reencryption, but for
security analysis it's important to realize that what's computed is,
whether ciphertexts are valid or not, always the same as FO with
reencryption. It's also important to realize that NTRU doesn't magically
avoid the huge side-channel target that FO reencryption creates in the
other lattice KEMs; the target is still there under a different name.

(The story for NTRU Prime is simpler. The use of rounding means that the
slowdown doesn't happen in the first place. The specified decapsulation
algorithm has an explicit FO layer. The huge side-channel target is
still there, obviously.)

Below are details that I sent around to some people in May, including
the high-level cost numbers driving how NTRU handled this:

* SABER and Kyber use 2 big mults in enc and 3 big mults in dec.
* NTRU and NTRU Prime use 1 big mult in enc and 2 big mults in dec.
* NTRU using a generic FO layer would use 1 big mult in enc and 3 big
mults in dec.

---Dan


Let's start with DH-like notation for Product NTRU (LPR): there's public
key A = aG+e and ciphertext (B,C) with B = Gb+d and C = Ab+M+c, with
a,b,c,d,e small and M encoding the message. The receiver computes aB,
subtracts from C to obtain eb+M+c-ad, and rounds to obtain M.

There are 2 big mults in PKE.enc, one for Gb and one for Ab, where by
"big mult" I mean small*big mod q. For PKE.dec there's just 1 big mult
for aB. There are also various small operations.

To get QROM IND-CCA2 security, everyone reencrypts, and everyone uses
implicit rejection and/or plaintext confirmation. Of course the
reencryption adds the enc cost to the dec cost, so there are 2 big mults
in KEM.enc and 3 big mults in KEM.dec. The proof is also loose, since
one needs the T transform to derandomize, deriving a,b,c,d,e from M.

Quotient NTRU, the original NTRU, forces A=0, by generating G as the
quotient -e/a. It has ciphertext simply B = Gb+d, skipping the M input
and skipping the C computation.

The receiver computes aB = -eb+ad. This is enough to recover (b,d) if,
for example, you require d to be a multiple of 3 and require b to have
coefficients in {-1,0,1}: reduce aB modulo 3 to obtain -eb, and divide
by -e modulo 3 to obtain b. Finally d = B-Gb. (Exchanging the roles of d
and b, taking b as a multiple of 3, also works in essentially the same
way.)

Here there's just 1 big mult in PKE.enc, for Gb. (The reciprocal of -e
modulo 3 can be precomputed, or forced to be 1, and in any case isn't a
big mult; the division also isn't a big mult.) There are 2 big mults in
PKE.dec, one for aB and one for Gb.

Notice that dec recovered the whole enc input (b,d), so the scheme is
deterministic, improving the tightness of known QROM IND-CCA2 proofs;
there's no need for the T transform. _Roughly_ this is what everyone now
does in the Quotient NTRU world, using reencryption, and using implicit
rejection and/or plaintext confirmation.

Of course the reencryption adds the cost of enc to the cost of dec,
giving 3 big mults. But wait: two of those mults are the same, computing
Gb and then computing Gb again. If you're willing to break the structure
of dec using enc as a subroutine, then you can simply reuse Gb from dec
to make the reencryption essentially free. There's then 1 big mult in
KEM.enc, and 2 big mults in KEM.dec.

This is basically what the NTRU submission does, except that I'm
glossing over distinctions between x^n-1 and (x^n-1)/(x-1). See Section
5.1 of https://eprint.iacr.org/2018/1174.pdf.

The NTRU Prime submission, specifically its Quotient NTRU option
(Streamlined NTRU Prime), achieves the same speedup in a different way,
preserving enc as a subroutine. The point is that it's a pure rounding
system, in particular rounding Gb to deterministically obtain B = Gb+d,
so there isn't any d in the input to begin with---the input is just b,
and the dec recovers b without bothering to recover d = B-Gb, so the
PKE.dec cost is just 1 big mult. The reenc then calls enc, which
recomputes B, so overall there are 2 big mults in KEM.dec.

Another way to achieve this speedup, if you don't like rounding, is to
compute d as a hash of b, but this requires the T transform again and
thus damages the proof tightness.

With any of these systems, a typical chosen-ciphertext attack will tweak
B = Gb+d so as to, e.g., add 3 to d. This can break decryption, changing
b, and basically the attack wins if it can detect this with noticeable
probability, so it's really important to hide the distinction between b
changing and b not changing. The easiest target for a side-channel
attack is the portion of the KEM.dec computation that recomputes d from
b, trying to recognize whether this portion has changed or not. I don't
think it matters whether this computation is labeled as part of dec (as
in the NTRU submission) or part of reenc (as in the NTRU Prime
submission); either way the critical bit of information is turning into
a big mult that really needs to be protected.

[D. J. Bernstein]

I wrote:
> To get QROM IND-CCA2 security, everyone reencrypts, and everyone uses
> implicit rejection and/or plaintext confirmation. Of course the
> reencryption adds the enc cost to the dec cost, so there are 2 big mults
> in KEM.enc and 3 big mults in KEM.dec. The proof is also loose, since
> one needs the T transform to derandomize, deriving a,b,c,d,e from M.

Sorry, that should say "deriving b,c,d from M".

---Dan