A team led by Prof. HU Honggang from the University of Science and Technology of China (USTC) solved a 95-dimensional Learning With Errors (LWE) problem with a relative error of 0.005 at the TU Darmstadt challenge, surpassing the previous record of 90 dimensions set two years ago.

The record page of the team. (Image from LWE website)

The TU Darmstadt Lattice Challenge is an internationally recognized competition in the field of post-quantum cryptography, aimed at advancing techniques for solving lattice problems. Lattices occupy a significant position in modern cryptography, particularly in post-quantum algorithms. The LWE problem is one of the core challenges in lattice-based cryptography.

HU’s team employed a Two-Step model, optimizing the Block Korkin-Zolotarev (BKZ) algorithm’s lattice basis preprocessing strategy. This significantly improved the quality of the lattice basis, enabling the sieve method to find the target solution in a shorter timeframe.

With the help of the model, the team solved a 95-dimensional LWE problem with a relative error of 0.005, completing the entire computational process in approximately 46 days.

This solution of the 95-dimensional LWE problem provides a valuable foundation for further research. Encouraged by the advancement, the team will work harder on post-quantum cryptography and its practical applications, contributing to cybersecurity in quantum computing.

(Written by WANG Hanzhi, edited by HUANG Rui, USTC News Center)