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

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

On 12/8/21, 18:44, "CFRG on behalf of Mike Ounsworth" <[e-mail] on behalf of 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.

Strongly disagree.

> You can mostly wrap your brain around RSA if your high school teaches modular arithmetic,
> and the attacks if you take 2nd year uni group theory. ECC also 2nd year group theory.

Yes, it's fairly trivial to understand the basic attacks. If you go through more complicated stuff, like the work of Don Coppersmith - you'll find that the above would probably be insufficient. It's somewhat similar with lattices - see below.

> 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).

IMHO, in general - not true. It's fairly simple on basic level - e.g., LWE, but some attacks are quite subtle.

> I took this note during Steven Galbraith's keynote at PQCrypto2016:
> "There are only a dozen people in the world (2 in the room) who are
> experts in all the branches of math and algorithm theory that go into
> lattice problems, so that poses a big problem in predicting the number
> of bits of security that these things offer."
> (talk recording: https://youtu.be/xpBEgT9xyk8?t=520)

He's a co-author of SIKE, one of the PQC finalists, right? And he published a lot on ECC, Hyperelliptic curves, Isogenies, etc.

I don't know what level of expertise Dr. Galbraith meant, but I've heard scientists discussing the strength of the lattice-based problems, and articulating their position pretty reasonably.

And, sorry, it's hard to watch talks. Publications (especially peer-reviewed ones ;), are much better to rely upon. Probably, https://www.math.auckland.ac.nz/~sgal018/PQCrypto.pdf would be easier for people to discuss. Starting with slide 2.

> I am most certainly not one of those experts qualified to have an opinion,
> and I know the situation has improved since 2016,

I'm sure I'm not one of the 12 experts that Dr. Galbraith considered qualified to have
an opinion (on the subject). ;-). 
On the other hand, I'm equally sure his criteria is overly exclusionary.

> .  .  .  but either way I think
> NTRU, ECC, and Rijndael are not directly comparable in terms
> of how "hours of public effort" translate to "confidence".

Do you _fully_ understand the design of AES/Rijndael? And _all_ of the (published) attacks against it? Maybe, you find comfortable determining the strength of EC Supersingular Isogenies-based algorithms? ;-)