Re: [CFRG] [EXTERNAL] Re: NSA vs. hybrid

[Christopher Peikert <[e-mail]>]

On Wed, Dec 8, 2021 at 6:43 PM Mike Ounsworth <Mike.Ounsworth=
[e-mail]> wrote:

> > As has been noted, so has NTRU gone through a good amount of review,
> even more perhaps than Rinjdael by this point in the competition for AES.
>
> I'm probably gonna embarrass myself, but here goes ... The argument that
> I've heard made is that there's a quantum leap (pun intended) between the
> complexity of the mathematics of RSA/ECC and NTRU. You can mostly wrap your
> brain around RSA if your highschool teaches modular arithmetic, and the
> attacks if you take 2nd year uni group theory. ECC also 2nd year group
> theory. Lattices, LWE, R-LWE, and especially module-LWE are this esoteric
> combination of rings, fields, and linear algebra that requires a very
> specific trajectory of graduate studies (likely over-simplified, apologies
> in advance).
>

It's unfortunate that people have this impression, because it's not true at
all.

Understanding NTRU or (even easier) R-LWE encryption requires just basic
polynomial arithmetic. They can be taught in about an hour to early
undergraduates, or even talented high schoolers (I've handled both).

Understanding ECC seems at least as difficult: one needs the curve equation
and its solutions, the group operation (how points are "added"), the
repeated-doubling algorithm, and Diffie-Hellman-style agreement. This isn't
super-advanced stuff, but it probably takes a couple of hours to convey a
thorough understanding to someone who already knows modular arithmetic.

Comprehending the best *attacks* is an entirely different matter, but
that's true for all of RSA, ECC, and lattices. How many people are experts
in the Number Field Sieve factoring algorithm -- the best attack on RSA?
This is not undergrad-level stuff, by any means. Nor are the best attacks
on lattices, though many experts have been working on them for decades.

No matter the area, the best attacks turn out to be a lot more complicated
than the cryptosystems themselves. But you don't need to understand the
attacks to understand how the schemes work, nor why they appear to be
secure.

Sincerely yours in cryptography,
Chris