Optimizing BKZ Blocksize Scheduling in Lattice-Based Cryptography using Reinforcement Learning

Sammanfattning

The ongoing development of quantum computers threatens to break current cryptographic systems if successfully realized. In response to this threat, researchers are actively developing new algorithms designed to withstand quantum attacks. The security of these emerging post quantum cryptographic standards relies heavily on the hardness of lattice problems, such as Module Learning With Errors (MLWE). The primary tool for assessing the practical security of these schemes is lattice reduction, specifically the Block Korkine Zolotarev (BKZ) algorithm. The efficiency of BKZ is highly sensitive to its block size parameter. However, conventional reduction approaches rely on static, predetermined schedules or manually crafted heuristics. These inflexible strategies often result in redundant computational effort or suboptimal reduction quality, as they cannot dynamically adapt to the state of the lattice during execution. This thesis frames BKZ block size scheduling as a sequential decision making problem and introduces a Reinforcement Learning (RL) approach to dynamically optimize the reduction process. By formulating the scheduling process as a Markov Decision Process, an agent is trained using Proximal Policy Optimization. The agent learns a scheduling policy that adjusts the block size based on the observed geometric state of the lattice, represented by the Gram Schmidt Orthogonalization profile, explicitly balancing geometric improvement against computational cost. The proposed RL scheduling policy is evaluated on MLWE lattice instances and benchmarked against standard single shot BKZ and the adaptive NoMod heuristic. Performance is assessed using geometric metrics, cryptanalytic metrics relevant to machine learning based recovery attacks, and overall execution time. Empirical results indicate that the RL driven scheduling outperforms the baseline methods in execution time, delivering a 10× speedup, though it underperforms in strict reduction quality. Additionally, it excels in the simulated attack, achieving an approximate 40 percent success rate compared to the 29 percent success rate of the NoMod baseline. Ultimately, this work demonstrates the viability of RL as a powerful framework for automating and optimizing complex algorithmic parameters in lattice based cryptanalysis.