Efficient Trapdoors for Lattice-based Encryption Schemes

10.03.2016, 11:00 – 12:00

2016/03/10 11:00-12:00

Speaker: Rachid El Bansarkhani | Location: Hochschulstraße 10 (S2|02), Piloty Building, Room B002, Darmstadt

Organizer: Prof. Johannes Buchmann / Prof. Melanie Volkamer / Moritz Horsch


Lattice-based encryption schemes still suffer from a low message throughput per ciphertext. This is mainly due to the fact that the underlying schemes still follow a traditional design concept and do not tap the full potentials of LWE. In particular, many constructions still encrypt data in an one-time-pad manner considering LWE instances as random vectors added to a message, most often encoded bit vectors. Recently, a novel encryption scheme based on the A-LWE assumption (relying on the hardness of LWE) has been proposed, where data is embedded into the error term without changing its target distributions. By this novelty it is possible to encrypt much more data as compared to the classical approach. Combinations of both concepts are also possible.

In this talk we revisit this approach and propose amongst others an efficient trapdoor construction of reduced storage size. More precisely, the public key size is reduced to a constant number of 3 polynomials, out of which 2 polynomials are sampled uniformly at random from a seed, as opposed to 1 + log q polynomials according to the previously most efficient trapdoor candidate. We also show how to ensure CCA (or RCCA) security, while entailing a great deal of flexibility to encrypt arbitrary large messages by use of the same secret key. This feature is naturally induced by the characteristics of LWE.

Short Bio

Link to Rachid El Bansarkhanis website.