Saber: module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM

Jan-pieter D’anvers, Angshuman Karmakar, Sujoy Sinha Roy, Frederik Vercauteren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Citations (Scopus)
333 Downloads (Pure)

Abstract

In this paper, we introduce Saber, a package of cryptographic primitives whose security relies on the hardness of the Module Learning With Rounding problem (Mod-LWR). We first describe a secure Diffie-Hellman type key exchange protocol, which is then transformed into an IND-CPA encryption scheme and finally into an IND-CCA secure key encapsulation mechanism using a post-quantum version of the Fujisaki-Okamoto transform. The design goals of this package were simplicity, efficiency and flexibility resulting in the following choices: all integer moduli are powers of 2 avoiding modular reduction and rejection sampling entirely; the use of LWR halves the amount of randomness required compared to LWE-based schemes and reduces bandwidth; the module structure provides flexibility by reusing one core component for multiple security levels. A constant-time AVX2 optimized software implementation of the KEM with parameters providing more than 128 bits of post-quantum security, requires only 101K, 125K and 129K cycles for key generation, encapsulation and decapsulation respectively on a Dell laptop with an Intel i7-Haswell processor.
Original languageEnglish
Title of host publicationProgress in Cryptology – AFRICACRYPT 2018
Subtitle of host publication10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7–9, 2018, Proceedings
EditorsAntoine Joux, Abderrahmane Nitaj, Tajjeeddine Rachidi
PublisherSpringer
Chapter16
Pages282-305
Number of pages24
ISBN (Electronic)9783319893396
ISBN (Print)9783319893389
DOIs
Publication statusPublished - 6 Apr 2018
Event10th International Conference on Cryptology in Africa (AFRICACRYPT 2018)
- Marrakesh, Morocco
Duration: 7 May 20189 May 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10831
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Cryptology in Africa (AFRICACRYPT 2018)
Country/TerritoryMorocco
CityMarrakesh
Period7/05/189/05/18

Fingerprint

Dive into the research topics of 'Saber: module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM'. Together they form a unique fingerprint.

Cite this