Re:A Guide to Post-Quantum Cryptography
by throwawaymath on Monday October 22, 2018 @11:50PM
(#18280602)
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.
Re:A Guide to Post-Quantum Cryptography
by throwawaymath on Wednesday October 24, 2018 @08:55AM
(#18291951)
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.
Re:A Guide to Post-Quantum Cryptography
by tptacek on Tuesday October 23, 2018 @03:38PM
(#18286696)
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:
Re:A Guide to Post-Quantum Cryptography
by wish5031 on Tuesday October 23, 2018 @01:49PM
(#18285648)
Talking about LWE, the author says:
> 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)
Re:A Guide to Post-Quantum Cryptography
by blperez on Tuesday October 23, 2018 @02:26PM
(#18286042)
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.
An especially good focus here is the comparison of systems based on different classes of intractability assumptions.
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
> 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)