https://pq-crystals.org/kyber/

CRYSTALS

Cryptographic Suite for Algebraic Lattices

 
CRYSTALS
 
Kyber Home
 
Resources
 
Software
CRYSTALS-Kyber

Introduction

Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM), whose
security is based on the hardness of solving the learning-with-errors
(LWE) problem over module lattices. Kyber is one of the finalists in
the NIST post-quantum cryptography project. The submission lists
three different parameter sets aiming at different security levels.
Specifically, Kyber-512 aims at security roughly equivalent to
AES-128, Kyber-768 aims at security roughly equivalent to AES-192,
and Kyber-1024 aims at security roughly equivalent to AES-256.

For users who are interested in using Kyber, we recommend the
following:

  * Use Kyber in a so-called hybrid mode in combination with
    established "pre-quantum" security; for example in combination
    with elliptic-curve Diffie-Hellman.
  * We recommend using the Kyber-768 parameter set, which--according
    to a very conservative analysis--achieves more than 128 bits of
    security against all known classical and quantum attacks.

Scientific Background

The design of Kyber has its roots in the seminal LWE-based encryption
scheme of Regev. Since Regev's original work, the practical
efficiency of LWE encryption schemes has been improved by observing
that the secret in LWE can come from the same distribution as the
noise and also noticing that "LWE-like" schemes can be built by using
a square (rather than a rectangular) matrix as the public key.
Another improvement was applying an idea originally used in the NTRU
cryptosystem to define the Ring-LWE and Module-LWE problems that used
polynomial rings rather than integers. The CCA-secure KEM Kyber is
built on top of a CPA-secure cryptosystem that is based on the
hardness of Module-LWE.

Users of Kyber

Kyber is already being integrated into libraries and systems by
industry. For example,

  * Cloudflare integrated Kyber alongside other PQ algorithms into
    CIRCL, the Cloudflare Interoperable, Reusable Cryptographic
    Library;
  * Amazon now supports hybrid modes involving Kyber in their AWS Key
    Management Service; and
  * already in 2019 IBM advertised the "World's First Quantum
    Computing Safe Tape Drive" using Kyber and Dilithium.

Performance Overview

The tables below gives an indication of the performance of Kyber. All
benchmarks were obtained on one core of an Intel Core-i7 4770K
(Haswell) CPU. We report benchmarks of two different implementations:
a C reference implementation and an optimized implementation using
AVX2 vector instructions. For benchmarks on an ARM Cortex-M4
microcontroller, see the benchmarks reported by the pqm4 project.

                         Kyber-512
Sizes (in bytes) Haswell cycles (ref) Haswell cycles (avx2)
sk:    1632      gen:    122684       gen:      33856
pk:    800       enc:    154524       enc:      45200
ct:    768       dec:    187960       dec:      34572
                         Kyber-768
Sizes (in bytes) Haswell cycles (ref) Haswell cycles (avx2)
sk:    2400      gen:    199408       gen:      52732
pk:    1184      enc:    235260       enc:      67624
ct:    1088      dec:    274900       dec:      53156
                         Kyber-1024
Sizes (in bytes) Haswell cycles (ref) Haswell cycles (avx2)
sk:    3168      gen:    307148       gen:      73544
pk:    1568      enc:    346648       enc:      97324
ct:    1568      dec:    396584       dec:      79128

As an update for round 2 of the NIST project we also proposed a
variant of Kyber that is meant to showcase the performance of Kyber
when hardware support for the symmetric primitives is available. This
variant, called Kyber-90s, uses AES-256 in counter mode and SHA2
instead of SHAKE.

              Kyber-512-90s
Haswell cycles (ref) Haswell cycles (avx2)
gen:    213156       gen:     21880
enc:    213156       enc:     28592
dec:    277612       dec:     20980
              Kyber-768-90s
Haswell cycles (ref) Haswell cycles (avx2)
gen:    389760       gen:     30460
enc:    432764       enc:     40140
dec:    473984       dec:     30108
               Kyber-1024-90s
Haswell cycles (ref) Haswell cycles (avx2)
gen:    636380       gen:     43212
enc:    672644       enc:     56556
dec:    724144       dec:     44328

Design 2017 by Peter Schwabe, last updated Dec 23, 2020
Title photo by James Mann (modified) (CC BY 2.0)