CWI Cryptology Group

Abstract: In this session we introduce lattices and some of their invariants. We take a look at bases and basis reduction algorithms with special attention to the LLL algorithm. We finish with some examples.

Abstract: Continuing with examples we now describe two uses of lattices in cryptanalysis: Coppersmith's attack on RSA based on stereotypical messages and the attack on the GGH signature scheme.

Abstract: We move on to "modern" lattice-based cryptography. We introduce the Short Integer Solution (SIS) problem one of the problems with average-case to worst-case reduction to lattice problems. We describe this reduction and give an example of a cryptographic primitive (collision-resistant hash functions) based on SIS.

Abstract: We introduce the "other half" of lattice-based cryptography: the Learning With Errors (LWE) problem. Cryptographic schemes whose security are based on LWE or SIS enjoy average-case to worst-case reduction to lattice problems. We introduce a variant of this problem called Ring-LWE that is widely used to bolster efficiency. We briefly discuss the security of schemes based on the latter.

Abstract: We introduce a "hot-topic" in lattice-based cryptography: fully homomorphic encryption. We discuss Gentry's bootstrapping theorem and give an example of a such a scheme based on RLWE.

Abstract: We discuss the latest scheme of Brakerski that achieves FHE from LWE and thus security based on problems for general lattices (contrary to RLWE).