Hall Of Fame

Kyber Parameters

A Kyber public key is a tuple , where and . The corresponding secret key is , where .

The coefficients of both and follow a centered binomial distribution with parameter . Kyber defines additional parameters , which determine noise and compression in the encryption algorithm. A Kyber ciphertext is a tuple of the form

For all our instances, .

Format of Instances

In our challenges, ring elements are given as arrays of length , in which the coefficients of are stored in ascending order, e.g.,

is given as

Consequently, is given as a three-dimensional array of size , where

Similary, is given as a two-dimensional array of size , where

Our challenges also contain lists of ciphertexts , which are encryptions of UTF-8-encoded human-readable messages.

Estimated Bit-Complexity

The best known attack against Kyber is the primal lattice reduction attack. It models the problem of attacking Kyber as an instance of the (Unique) Shortest Vector Problem, and then uses the BKZ algorithm to recover the secret key.

The complexity of the attack is usually measured in the required BKZ blocksize . Given , the bit complexity is estimated in the Core-SVP model, which estimates the bit-complexity of the attack as . (We note that the Core-SVP model typically underestimates the actual bit complexity of the attack.)

The required blocksizes for the Kyber challenges were estimated with the Leaky LWE Estimator.