Kyber Parameters
A Kyber public key is a tuple (A,t) ∈ ℛqk × k × ℛqk, where ℛq = ℤq[X]/(Xn+1) and n, q, k ∈ ℕ. The corresponding secret key is (s,e) ∈ ℛqk × ℛqk, where t = As + e.
The coefficients of both s and e follow a centered binomial distribution with parameter η1 ∈ ℕ. Kyber defines additional parameters η2, du, dv, which determine noise and compression in the encryption algorithm. A Kyber ciphertext is a tuple of the form (c1,c2) ∈ ℛqk × ℛq
For all our instances, du = 8, dv = 8, η1 = 3, η2 = 3.
Format of Instances
In our challenges, ring elements a ∈ ℛq are given as arrays of length n, in which the coefficients of a are stored in ascending order, e.g.,
a = a0 ⋅ X0 + a1 ⋅ X1 + … + an − 1 ⋅ Xn − 1
is given as
[a0,a1,…,an − 1]
Consequently, A = (Ai, j)1 ≤ i ≤ j ≤ k is given as a three-dimensional array A of size k × k × n, where
Ai, j = A[i][j][0] ⋅ X0 + A[i][j][1] ⋅ X1 + … + A[i][j][n−1] ⋅ Xn − 1
Similary, t = (t1,…,tk) is given as a two-dimensional array t of size k × n, where
ti = t[i][0] ⋅ X0 + t[i][1] ⋅ X1 + … + t[i][n−1] ⋅ Xn − 1
Our challenges also contain lists of ciphertexts ((c11,c21),(c12,c22),…), 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 0.292β. (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.