6 ms·
This is pretty fascinating. For easier reading, the Signal blog post [0] they link to is great. Both Signal and Apple went with CRYSTALS-Kyber [1] as their pos
by sandyarmstrong 3y ago
This is pretty fascinating. For easier reading, the Signal blog post [0] they link to is great.
Both Signal and Apple went with CRYSTALS-Kyber [1] as their post-quantum algorithm. If you're interested in the math, and maybe learned at some point about how classic public key cryptography is built on the idea that it's easy to multiply two primes, but hard to factor them, and how this (or other math problems) can be used as a one-way function to make encryption hard to break, the hard math problem that backs Kyber is the "learning-with-errors" [2] problem.
[0] https://signal.org/blog/pqxdh/ https://signal.org/blog/pqxdh/
[1] https://pq-crystals.org/kyber/ https://pq-crystals.org/kyber/
[2] https://en.wikipedia.org/wiki/Learning_with_errors https://en.wikipedia.org/wiki/Learning_with_errors
- gjsman-1000 3y agoWas the CRYSTALS-Kyber name intentionally, or accidentally, a reference to Kyber Crystals (I.e. The Lightsaber energy source?)
- ZeWaka 3y agoAbsolutely a reference. Dilithium (from Star Trek) is name of their signature algorithm.
- throw0101c 3y agoThe trick to naming things is to first find a cool word/reference, and then 'reverse engineer' it as an acronym second: * https://en.wikipedia.org/wiki/Backronym https://en.wikipedia.org/wiki/Backronym
- ryukafalz 3y agoThough you can easily take it too far; I think US legislators have been running out of reasonable backronyms :)
- saagarjha 3y agoI'm amused by the Padmé reference as well.
- andy_xor_andrew 3y agoI'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.
- Retr0id 3y agoThe explanation in this video is what made it click for me: https://www.youtube.com/watch?v=K026C5YaB3A https://www.youtube.com/watch?v=K026C5YaB3A
- kevvok 3y agoSame here: this video helped me finally understand the basics concepts underlying LWE
- sandyarmstrong 3y agoThank you! This video was GREAT. I was having trouble putting it all together from the wikipedia page alone.
- tptacek 3y agoWell, 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.
- bjoli 3y agoI was reading the NIST comments and djb is not very happy with how they present things, and the other commenters seem to think he is a prick.
- londons_explore 3y agoI want an encryption algorithm composed of 2 parts chained, such that both parts need to be broken for the whole thing to be broken. And I'd like the US/The west to declare 1 part as secure, and I'd like Russia to declare the other part as secure. I'm fairly confident that Russia and the US won't collude to push a known-weak algorithm.
- snowwrestler 3y agoThey would not have to collude; there is no incentive for either to publicly endorse a secure algorithm. Both Russian and U.S. intelligence services want the ability to break into anything. They would publicly endorse insecure algorithms, and then employ more secure algorithms in their own classified systems. I think encryption quality is best evaluated by math and technical testing, not international political triangulation.
- dlubarov 3y agoAlternatively we could use hash-based signature schemes which have been proven secure under certain assumptions about hash functions, such as SPHINCS, or ZKP based schemes along the lines of Picnic (Picnic in particular uses LowMC which is somewhat new). In that case a backup seems unnecessary.
- 1vuio0pswjnm7 3y agohttps://kyberslash.cr.yp.to https://kyberslash.cr.yp.to