Cryptology ePrint Archive: Report 2018/230

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

Jan-Pieter D’Anvers and Angshuman Karmakar and 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.

Category / Keywords: public-key cryptography /

Original Publication (with minor differences): AFRICACRYPT 2018

Date: received 27 Feb 2018, last revised 18 Mar 2019

Contact author: angshuman karmakar at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20190318:104623 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]