the strongest encryption is just noise
Modern encryption standards really aren’t too bad to understand!
Learning With Errors (LWE) is the most fun math you’ve never heard of.
Basically every modern encryption (quantum resistant!) algorithm is based on the concept. It’s actually really easy to understand.
Imagine if every linear problem had a little bit of noise. Just enough to mess you up.
Go back to middle school for a moment:
Pretty easy right? X is obviously 7.
Now I tell you this, and that it’s the same X:
Wait. That can’t possibly be the same X…right?
Imagine it actually is, but the reason it’s confusing is you have a bad calculator. A *randomly* bad calculator that’s off by a little bit every time.
With a single equation you can somewhat eyeball it, just round down in your head. But if you do thousands upon thousands, all with a random amount of error in a random direction, it’s computationally impossible to reverse.
Decryption is basically “rounding” the noisy result back to the nearest point. The “key” / secret itself is quite interesting, because it’s basically the vector that get’s you the right answer.
(in practice LWE works over integers mod q, not regular real numbers, but this is a simplified analogy)
Without the key, let’s say you have the value 25.5. You don’t know what to whether round up to 26 or down to 25. The key essentially tells you for certain:
psst, the answer is actually 26Thus, you take the (noisy) encrypted message, denoise it, then boom, unencrypted plaintext. Mathematically, the points are in a multi-dimensional lattice structure…but the way it’s actually computed is just a bunch of linear algebra, hence LWE (learning with errors)
Congratulations, you now (somewhat) understand CRYSTALS-KYBER!
Traditional factoring (think RSA) is really clean, hence vulnerable to Shor’s algorithm.
LWE is so ambiguously noisy that no one has found a quantum algorithm that can reduce the complexity at all!
There’s a ton of other useful applications for LWE besides encryption, including more esoteric stuff fingerprintable LLM weights and even program obfuscation.
It’s actually really easy to code toy versions of LWE yourself, way simpler than RSA. Highly encourage you write your own, you can do it in like ~20 lines of code.
Chris Peikert has really good lectures and papers on the subject. He’s specifically the guy that essentially made LWE possible on modern computers. Go check out his talk “The Learning With Errors Problem and Cryptographic Applications”
Modern encryption standards really aren’t too bad to understand!
Neat -- thanks!
Interestingly your post brought this to mind, and now I've got to go and look to see if the external review that Bruce Schneier wanted, ever happened:
https://www.newscientist.com/article/mg19426055-300-noise-keeps-spooks-out-of-the-loop/
-I can think of a use case, but it's pretty niche
PS I think there's a word missing above Figure 3 between "stuff" and "fingerprintable".
Encryption thats not a jig? Maybe try an open Encryption, like what could be used to decrypt. An algorithm that when run doesn't do anything except for the last step. Then its a fresh start where the code can be employed on the second pass. That way the target of sharing information is based on adjacent commands. That only works as intended so Encryption becomes obsolete. Like a "what are you doing".