Overview
SABER is an IND-CCA2 secure Key Encapsulation Mechanism (KEM) whose security relies on the hardness of the Module Learning With Rounding problem (MLWR) and remains secure even against quantum computers. SABER is one of the round 2 candidates of the NIST Post-Quantum Cryptography Standardization effort.
The SABER-suite offers three security levels:
- LightSABER: post-quantum security level similar to AES-128
- SABER: post-quantum security level similar to AES-192
- FireSABER: post-quantum security level similar to AES-256
Design
The design goals of SABER are simplicity, efficiency and flexibility. It is designed with software and hardware implementations in mind, resulting in the following choices:
- Saber uses Learning with Rounding (LWR)
- Sampling from an error distribution is avoided, which makes the implementation easier and more secure by design.
Moreover, this is one less step that needs to be masked. - The amount of pseudorandomness required is reduced
- Sampling from an error distribution is avoided, which makes the implementation easier and more secure by design.
- All integer moduli are powers of two:
- Power of two moduli remove the need for modular reductions: these can be replaced by bitwise operations
This makes hardware and software implementation simpler - Power-of-two modulus makes masking of Saber simpler
- The bandwidth of both the public key and the ciphertext is reduced
(power of two moduli combined with LWR allows provably secure public key compression) - Rejection sampling is avoided entirely
- Power of two moduli remove the need for modular reductions: these can be replaced by bitwise operations
- The module structure provides flexibility
- Only one core component needs to be implemented for multiple security levels. This makes the implementation simpler.
One of the biggest advantages of Saber is its simplicity and efficiency: it is designed to be easy to understand and implement, and removes any unnecessary complexities that could lead to dangerous implementation mistakes. Moreover, Saber is constant-time by design and only uses simple operations. Therefore even a basic implementation of Saber will be relatively efficient and secure.
The design of Saber makes it a good fit for anonymous communication (e.g. Tor). In contrast to some other schemes, the running time is even constant-time over various different public keys as there is no rejection sampling. Moreover, due to the power-of-two moduli, the communication (public key, ciphertext) looks like uniformly random bits and contains no structure.
Security
The security of Saber is based on conservative estimates. Albrecht et al. estimated the following security for the different versions of Saber:
| LightSaber | Saber | FireSaber | |
|---|---|---|---|
| Classical Security | 2^118 core SVP | 2^189 core SVP | 2^260 core SVP |
| Quantum Security (0.265 β) | 2^107 core SVP | 2^172 core SVP | 2^236 core SVP |
Decryption failure attacks, as researched in [1][2][3], do not affect the security of Saber as the failure probability of Saber is sufficiently low, with 2^-120 for LightSaber, 2^-136 for Saber and 2^-165 for FireSaber.
Acknowledgements
The development of Saber has been supported by:
- European Commission through the Horizon 2020 research innovation programme:
- Cathedral ERC Advanced Grant 695305
- H2020-ICT-2014-645622 PQCRYPTO
- 2020-ICT-2014-644209 HEAT
- FENTEC (Grant No. 780108)
- CyberSecurity Research Flanders with reference number VR20192203
- Research Council KU Leuven:
- C14/18/067
- C16/15/058
- STG/17/019
- Semiconductor Research Corporation (SRC), under task 2909.001
- University of Birmingham
- the Ramsay research support fund