Kyber 256 Challenge With my student Ziyu, we solved the Kyber 256 challenge, the highest existing challenge. Challenge: Kyber-256-k1 Secret Key: [0 0 -2 0 1 0 1 -1 0 1 0 -1 2 2 1 1 -1 1 0 0 2 0… | Jintai Ding

Kyber 256 Challenge With my student Ziyu, we solved the Kyber 256 challenge, the highest existing challenge. Challenge: Kyber-256-k1 Secret Key: [0 0 -2 0 1 0 1 -1 0 1 0 -1 2 2 1 1 -1 1 0 0 2 0 0 1 0 -2 -1 -2 1 -2 1 -1 -2 2 0 0 -1 1 -2 2 -2 -1 1 -1 -1 1 1 1 0 1 -2 1 0 0 -1 3 1 2 0 -1 -2 -2 0 0 2 0 1 0 2 1 1 -1 0 1 -1 -1 1 1 -1 -1 -1 1 2 -1 0 1 0 2 1 0 -2 1 0 0 1 0 1 1 1 0 -1 -2 0 2 2 -2 -1 1 -1 -2 -1 1 -1 -1 -1 0 1 -1 -1 0 -2 0 0 -3 2 3 0 -1 -3 0 -1 -2 0 0 -1 1 0 0 0 1 1 0 -2 0 -1 0 -1 1 -1 -1 -1 0 0 1 0 -1 0 2 0 -1 2 0 -2 2 -1 -2 -2 -1 -3 0 1 -1 -1 -2 1 0 -2 -3 0 -2 0 3 -2 0 0 1 -1 2 0 1 -1 0 -1 0 2 -3 0 -1 -1 0 0 1 0 0 0 -3 1 0 1 0 0 1 0 -2 -1 -1 0 0 2 0 -1 -2 1 0 0 -2 2 0 1 0 0 -1 -3 0 0 -1 -3 1 0 0 -1 -1 0 -1 2 1 0 -1 1 2 -1 0 2 -1 1 2] Decrypted / Sined Message: “You know, Watson, I don't mind confessing to you that I have always had an idea that I would have made a highly efficient criminal.” ― Arthur Conan Doyle, The Return of Sherlock Holmes Authors: Jintai Ding, Ziyu Zhao Algorithm and Implementation: Primal attack on Kannan embedding, Preprocessing (up to β=145) with BGJ-AMX and BGJ-GPU, Final sieve with BGJ-GPU, Solving Rank 156 (expected 163). Hardware and CPU-Time: The computation was distributed across a total of 16 RTX 4090 GPUs in a shared system. We estimate the equivalent of 15 RTX 4090 GPU-months for the entire computation. Comments: There was also a failed attempt after BKZ (β=142) with maximum sieving rank 170 (expected 168), which took roughly 8 RTX 4090 months.