“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

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

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 , 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.