Paper 2018/230

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

Jan-Pieter D’Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Vercauteren

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.AFRICACRYPT 2018
Contact author(s)
angshuman karmakar @ esat kuleuven be
History
2019-03-18: last of 7 revisions
2018-03-01: received
See all versions
Short URL
https://ia.cr/2018/230
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/230,
      author = {Jan-Pieter D’Anvers and Angshuman Karmakar and Sujoy Sinha Roy and Frederik Vercauteren},
      title = {Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM},
      howpublished = {Cryptology ePrint Archive, Paper 2018/230},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/230}},
      url = {https://eprint.iacr.org/2018/230}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.