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

[Mike Ounsworth <[e-mail]>]

Thanks for the correction Chris!

In that case, I’ve probably been over-weighting that comment from Steven Galbraith in how I think about when lattice cryptosystems will have had “enough review”.

---
Mike Ounsworth

From: Christopher Peikert <christopher.peikert=[e-mail]>
Sent: December 9, 2021 8:47 AM
To: Mike Ounsworth <[e-mail]>
Cc: Richard Outerbridge <[e-mail]>; Loganaden Velvindron <[e-mail]>; CFRG <[e-mail]>
Subject: Re: [CFRG] [EXTERNAL] Re: NSA vs. hybrid

On Wed, Dec 8, 2021 at 6:43 PM Mike Ounsworth <Mike.Ounsworth=[e-mail]<mailto:[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
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.