Hacker News Reader

Comment by andy_xor_andrew | Hacker News Reader

I'm way out of my depth in terms of the math here.

But my 'software engineer brain' likes the ideal of using the prime factoring problem, because it's so simple to understand, and feels like some kind of universal primitive. "It's easy to multiply but hard to factor." It just seems so intuitive.

But I'm reading the 'learning with errors' wiki page and it's beyond my comprehension.

There's a weird fear in my mind that all these "post quantum algorithms" are so complicated, with such a large surface area, that they may hide flaws. While prime factoring, or even the elliptic key stuff, is so simple to comprehend.

that said, obviously the experts know what they're doing, and I'll use what they suggest. just saying that this thought has crossed my mind.

View on HN

I know that thinking, but learning more about RSA, I came to realize that there's a flipside of this.

People think "RSA is easy", because someone gave them a lecture of a simplified/wrong/insecure version of RSA. Pretty much all "simple introductions to RSA" you can find out there are wrong.

The truth is: RSA isn't that simple. If you want to have RSA, and want to have it secure, there's a whole bunch of things to consider. But RSA looks simple.

So lots of people go ahead and implement their RSA. And then you end up with, hey, I can break almost a third of the top 100 webpage's RSA implementations. (I'm not kidding, I did that -> https://robotattack.org/ .)

I think the fact that crystals-kyber is obviously not that simple may actually protect us. Because hopefully most peopple will end up using some hopefully well audited optimized free implementation, because they won't even have the idea that they could do this on their own.

I love that security by difficulty is the new security by obscurity, but actually secure.

Is it new? Security by difficulty _is_ security.

Yeah talking about difficulty, then you will love this: https://www.science.org/content/article/china-s-quantum-sate...

If we really wanna be security, then entailment is a good bet. I could imagine essential financial clearing, emergency infrastructure could use this level security. Don't know how feasible it is for consumer grade usage yet though.

People rolling their own crypto still makes my jaw drop.

I get people want something custom but the tradeoffs are just too great.

Well, one way to think about this is: how much abstract algebra are you keeping in your head to reassure yourself of the security of classical asymmetric cryptography? It's surprisingly deep. Some programmers are "comfortable" with it because they've been brought up being taught that "factoring" is just the way asymmetric cryptography works, but that has never really been the whole case.

Elliptic curve is not at all simple to comprehend! It's easy to implement, but the motivation for designing systems around them (the effectiveness of the index calculus on elliptic curve groups) and the discoveries made on attacking them (like the MOV attack that transforms ECDLP problems to FFDLP problems) are not at all simple.

Arguably, elliptic curve is an odder corner of mathematics than lattices.

100%. Another underappreciated point is that factoring connection is very misleading. That is, we don't know if factoring is equivalent to breaking RSA (in particular, the algorithms breaking low-exponent RSA (which one shouldn't use for a number of reasons) don't factor the modulus). It might be true that computing e-th roots (i.e. breaking RSA) is tractable while factoring is not.

Similarly, PKCS is complex but every part of PKCS is there because without it there is a concrete attack. Burt Kaliski (former chief scientist of RSA Labs) has an amazing talk which goes into detail about this: https://www.youtube.com/watch?v=sqsDKjPaJVg For example, why does RSA need randomized padding, besides the trivial IND-CPA violation? Because if you encrypt the same message to many recipients, the attacker can use Hastad's attack, which uses lattices in a deep way, to recover the message from non-randomized ciphertexts https://en.wikipedia.org/wiki/Coppersmith%27s_attack?useskin... Very much like an airline checklist in a way :-)

Another nugget in the talk: how RSA embedded a public key in their products and bootstrapped VeriSign! Can't recommend it highly enough.

The LWE problem is one level of abstraction away from the fundamental lattice problems it reduces to. It is somewhat analogous to the Diffie-Hellman problem that many constructions reduce to, which itself is related to the lower-level discrete logarithm problem.

The lattice equivalent of integer factorization is the shortest vector problem: you're given n vectors of length m, and you have to find the sum of integer multiples of those vectors that comes closest to (or a small factor away from the closest) the zero vector. Say you have the 4 vectors

    [ 3 92  4  2]
    [54  0 92 41]
    [19 91 61 48]
    [39 59 40 14].

The shortest vector that you can obtain from adding integer multiples of these vectors is [19 -8 -15 2], which you can obtain by 3*[39 59 40 14] + [19 91 61 48] - 2*[54 0 92 41] - 3*[ 3 92 4 2].

With only 4 vectors it is easy to find the solution here. But the hardness grows exponentially with the dimension, and the dimensions in cryptographically relevant lattices are in the hundreds to thousands.

The explanation in this video is what made it click for me: https://www.youtube.com/watch?v=K026C5YaB3A

Same here: this video helped me finally understand the basics concepts underlying LWE

Thank you! This video was GREAT. I was having trouble putting it all together from the wikipedia page alone.

> There's a weird fear in my mind that all these "post quantum algorithms" are so complicated, with such a large surface area, that they may hide flaws.

That's correct (emphasis on "may", of course), and is why it's absolutely imperative to always use PQC/ECC hybrid cryptosystems rather than pure PQC. See eg [0] for a more detailed explanation.

0: https://blog.cr.yp.to/20240102-hybrid.html

There are essentially no mainstream systems that don't do this. That's why new systems deploy things like PQ3.

Do you mean:

> There are essentially no mainstream systems that don't [use PQC/ECC hybrid cryptosystems?].

If so, good. I'll admit my expectations are a bit biased from having to deal with projects that go out of their way to produce defective software (eg DRM, malicious abuse of undefined behaviour by compliers, cloudflare and other captcha-walls, etc) so I tend to assume the worst by default.

Yes. So far as I know, there's no mainstream system that has even proposed to use solely Kyber and not Kyber+ECC. It's been a built-in assumption since the earliest Chrome PQC experiments.

It's not at all clear that factoring is actually hard. I fully expect factoring to be broken classically within my lifetime. FWIW I am a practicing cryptographer.

Curiously, the "large surface area hiding flaws" is actually what happened with RSA. Examples are

1. (large) speedups in solving it in the 90s, 2. issues where if enough of your key leaks, it can all be recovered. This leakage can occur via certain side-channel attacks 3. the "easy RSA" people learn is hard to make secure, which perhaps took a decade of doing very wrong to get right. By this, I mean padding attacks on RSA.

As for understanding LWE, see for example the blog posts

https://mark-schultz.github.io/nist-standard-out/

Reply on news.ycombinator.com