This is one of the better introductions to post-quantum cryptography that I've seen. It's pretty light on math and it offers broad coverage; including some of the current state of the art systems under consideration by NIST.
An especially good focus here is the comparison of systems based on different classes of intractability assumptions.
> A major problem with this system is that it has very large keys. To encrypt just one bit of information requires public keys with size n^2 in the security parameter.
Can't this be solved by e.g. forcing some kind of random sparsity structure on the matrix and then compressing with a format like CSC or CSR? (probably just not understanding LWE completely)
The issue is that finding a class of sparse matrices that don't ruin the security guarantees is really tricky. This more or less is the approach that ring-lwe takes - the matrices can be represented as polynomials and therefore are only linear in the security parameter, not quadratic (it also speeds up all the other operations via FFT-type techniques). But even there you have to be really careful about how you're constructing these polynomials, which boils down to a bunch of fancy algebraic number theory.
As of the current state of the art: yes, that's correct. Isogenies are slow with very small key sizes; lattices (and Goppa codes) are fast with large key sizes.
Isogenies are a good use case for e.g. constrained hardware that doesn't have much space but can tolerate longer key exchange turnaround times. Conversely you'd really want something like lattices for typical key exchange between a client browser and web server.
Code-based solutions have similar advantages and disadvantages lattices and are much older. McEliece is only slightly older than RSA. But because the structure of most types of error correcting codes, it has been very difficult to develop safe systems with the same versatility as lattice based systems. Code-based systems have fewer intractability problems available and virtually all types of codes tried to date have been broken - see research over the past two decades by Nicolas Sendrier, for example.
I want to see a quantum-resistant PAKE, because then you can use the resulting key material to do symmetric crypto (which is generally resistant anyway).
This is great. Deidre Connolly has been doing a pretty fantastic job of popularizing elliptic curve isogeny crypto, and her talk at Cloudflare is an excellent (detailed) intro to post-quantum key exchange:
12 comments
[ 3.7 ms ] story [ 43.4 ms ] threadAn especially good focus here is the comparison of systems based on different classes of intractability assumptions.
> A major problem with this system is that it has very large keys. To encrypt just one bit of information requires public keys with size n^2 in the security parameter.
Can't this be solved by e.g. forcing some kind of random sparsity structure on the matrix and then compressing with a format like CSC or CSR? (probably just not understanding LWE completely)
Isogenies are a good use case for e.g. constrained hardware that doesn't have much space but can tolerate longer key exchange turnaround times. Conversely you'd really want something like lattices for typical key exchange between a client browser and web server.
Code-based solutions have similar advantages and disadvantages lattices and are much older. McEliece is only slightly older than RSA. But because the structure of most types of error correcting codes, it has been very difficult to develop safe systems with the same versatility as lattice based systems. Code-based systems have fewer intractability problems available and virtually all types of codes tried to date have been broken - see research over the past two decades by Nicolas Sendrier, for example.
https://twitter.com/durumcrustulum/status/839279075315314692