bochum-challeng.es

Hall Of Fame

Parameter Set

Authors

Kyber-192-k3

Henry Bambury

Submitted	2025-04-23
Solution	“Memories warm you up from the inside. But they also tear you apart.” — Kafka on the Shore by Haruki Murakami
Algorithm	Primal attack on Kannan embedding with progressive BKZ (20->55 1 tour enumeration with fpylll; 56->108 1 tour sieving with g6k triple sieve)
Hardware	Intel(R) Xeon(R) Platinum 8260L CPU @ 2.40GHz
Runtime	~195h (wall time)
Affiliation	The author is affiliated with Inria.

Kyber-192-k6

Henry Bambury

Submitted	2025-04-23
Solution	I could tell you my adventures - beginning from this morning, but it's no use going back to yesterday, because I was a different person then.” – Alice, from Alice's Adventures in Wonderland (Lewis Carroll)
Algorithm	Primal attack on Kannan embedding with progressive BKZ (20->55 1 tour enumeration with fpylll; 56->110 1 tour sieving with g6k triple sieve + 3 extra tours at bs=111)
Hardware	Intel(R) Xeon(R) Platinum 8260L CPU @ 2.40GHz
Runtime	~580h (wall time)
Affiliation	The author is affiliated with Inria.

Kyber-192-k12

Henry Bambury

Submitted	2025-04-23
Solution	“There is some good in this world, and it’s worth fighting for.” — The Two Towers by J.R.R. Tolkien
Algorithm	Primal attack on Kannan embedding with progressive BKZ (20->55 1tour enumeration with fpylll; 56->110 1 tour sieving with g6k triple sieve + 5 tours of bs=111 + 2 tours of bs=112)
Hardware	Intel(R) Xeon(R) Platinum 8260L CPU @ 2.40GHz
Runtime	~1996h (wall time)
Affiliation	The author is affiliated with Inria.

Kyber-160-k5

Anders Nilson

Submitted	2023-09-03
Solution	“And now here is my secret, a very simple secret: It is only with the heart that one can see rightly; what is essential is invisible to the eye.” – The Little Prince by Antoine de-Saint Exupery
Algorithm	g6k with fpylll (for sieving, hk3 sieve), Kannan embedding
Strategy	BKZ preprocessing, hk3 from β=40 to β=84.
Hardware	MacBook Pro M1 (aarch64, working inside virtualized Linux), utilizing one core and around 1GB DDR5
Runtime	~25h CPU time, ~147h wall time

Kyber-160-k10

Anders Nilson

Submitted	2023-09-03
Solution	“Never send a human to do a machine's job” – Agent Smith (The Matrix)
Algorithm	g6k with fpylll (for sieving, hk3 sieve), Kannan embedding
Strategy	BKZ preprocessing, hk3 from β=50 to β=81.
Hardware	MacBook Pro M1 (aarch64, working inside virtualized Linux), utilizing one core and around 1GB DDR5
Runtime	~23h CPU time, ~132h wall time

Kyber-176-k11

Alexander Karenin

Submitted	2023-08-07
Solution	“May the Force be with you.” — Star Wars, 1977
Algorithm	FPYLLL + G6K (for sieving, hk3 sieve), Kannan embedding
Strategy	BKZ preprocessing β=60 (pruned enumeration, 5 tours). BKZ with hk3 sieving β between 70 and 95, 9 tours.
Hardware	2 x AMD EPYC 7763 64-core processor (2450 MHz, 15 threads used), 1024 MB RAM
Runtime	~76h
Affiliation	The author is affiliated with the Technology Innovation Institute.

Kyber-144-k9

Anders Nilson

Submitted	2023-08-06
Solution	“It is not for me to judge another man's life. I must judge, I must choose, I must spurn, purely for myself. For myself, alone.” – Siddhartha by Herman Hesse
Algorithm	BKZ using Sage 10.0. β_max = 59
Hardware	MacBook Pro M1 (aarch64, working inside virtualized Linux), utilizing one core and around 1GB DDR5
Runtime	~15h

Kyber-128-k4

Nour-eddine Rahmani

Submitted	2023-08-02
Solution	“Man is the only real enemy we have. Remove Man from the scene, and the root cause of hunger and overwork is abolished forever.” – Animal Farm by George Orwell
Algorithm	BKZ using Sage 10.0. β_max = 50
Hardware	i7-12700KF, 16 GB DDR4
Runtime	~2h44m
Affiliation	The author is affiliated with the ACSA laboratory at Mohammed Premier University at Oujda.

Kyber-128-k8

Alexander Karenin

Submitted	2023-08-02
Solution	“The creatures outside looked from pig to man, and from man to pig, and from pig to man again; but already it was impossible to say which was which.” – Animal Farm by George Orwell
Algorithm	Progressive BKZ, fpylll, approxSVP oracle is pruned enumeration. β_max = 56
Hardware	Acer Swift 3X, Core i7-1165G7, 16 GB DDR4
Runtime	~55m
Affiliation	The author is affiliated with the Technology Innovation Institute, UAE.

Kyber-128-k1

Nour-eddine Rahmani

Submitted	2023-07-31
Solution	“Sometimes you need to scorch everything to the ground and start over. After the burning the soil is richer, and new things can grow. People are like that, too.” From Little Fires Everywhere by Celeste Ng
Algorithm	BKZ using Sage 10.0. β_max = 50
Hardware	i7-12700KF, 16 GB DDR4
Runtime	~1h04m
Affiliation	The author is affiliated with the ACSA laboratory at Mohammed Premier University at Oujda.

Kyber-128-k2

Alexander Karenin

Submitted	2023-07-26
Solution	“Better never means better for everyone... It always means worse, for some.” – The Handmaid’s Tale by Margaret Atwood
Algorithm	Progressive BKZ with varying tour numbers. approxSVP oracle is pruned enumeration. β_max = 50
Hardware	Acer Swift 3X, Core i7-1165G7, 16 GB DDR4
Runtime	~1h30m
Affiliation	The author is affiliated with the Technology Innovation Institute, UAE.

Kyber Parameters

A Kyber public key is a tuple $(A, t) \in R_{q}^{k \times k} \times R_{q}^{k}$ , where $R_{q} = Z_{q} [X] / (X^{n} + 1)$ and $n, q, k \in N$ .
The corresponding secret key is $(s, e) \in R_{q}^{k} \times R_{q}^{k}$ , where $t = A s + e$ .

The coefficients of both $s$ and $e$ follow a centered binomial distribution with parameter $η_{1} \in N$ . Kyber defines additional parameters $η_{2}, d_{u}, d_{v}$ , which determine noise and compression in the encryption algorithm. A Kyber ciphertext is a tuple of the form $(c_{1}, c_{2}) \in R_{q}^{k} \times R_{q}$

For all our instances, $d_{u} = 8, d_{v} = 8, η_{1} = 3, η_{2} = 3$ .

Format of Instances

In our challenges, ring elements $a \in R_{q}$ are given as arrays of length $n$ , in which the coefficients of $a$ are stored in ascending order, e.g.,

$a = a_{0} \cdot X^{0} + a_{1} \cdot X^{1} + \dots + a_{n - 1} \cdot X^{n - 1}$

is given as

$[a_{0}, a_{1}, \dots, a_{n - 1}]$

Consequently, $A = (A_{i, j})_{1 \leq i \leq j \leq k}$ is given as a three-dimensional array $A$ of size $k \times k \times n$ , where

$A_{i, j} = A [i] [j] [0] \cdot X^{0} + A [i] [j] [1] \cdot X^{1} + \dots + A [i] [j] [n - 1] \cdot X^{n - 1}$

Similary, $t = (t_{1}, \dots, t_{k})$ is given as a two-dimensional array $t$ of size $k \times n$ , where

$t_{i} = t [i] [0] \cdot X^{0} + t [i] [1] \cdot X^{1} + \dots + t [i] [n - 1] \cdot X^{n - 1}$

Our challenges also contain lists of ciphertexts $((c_{1}^{1}, c_{2}^{1}), (c_{1}^{2}, c_{2}^{2}), \dots)$ , 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.