Recent work has solidly established lattice-based signatures as a viable replacement for number-theoretic schemes should quantum computing come into fruition. In fact, the current lattice-based schemes have key and signature sizes comparable to RSA while being an order of magnitude faster. The main focus of this talk will be presenting the main ideas behind the latest results in this area. In addition to the high level intuition, I will try to motivate the many employed optimizations, such as having an NTRU-like public key and sampling from a bimodal Gaussian distribution.
Most of the talk will be based on the papers “Lattice Signatures without Trapdoors” and “Lattice Signatures and Bimodal Gaussians”. The latter is joint work with Leo Ducas, Alain Durmus, and Tancrede Lepoint.