Analyzing Reductions in Kyber to Derive Key Length Recommendations for Post-Quantum Cryptography

Student: Brandon Robinson

Faculty Mentor: Mark Gondree

Computer Science

College of Science, Technology, and Business

This project investigates the relationship between security reductions and key length recommendations in lattice-based post-quantum cryptography, with a focus on CRYSTALS-Kyber. Kyber’s security relies on the hardness of the Module Learning With Errors (M-LWE) problem. By tracing reductions from Kyber’s CCA and CPA security models to M-LWE, this work visualizes and analyzes the underlying assumptions, model-specific tightness, and cost estimates of known attacks. My core contribution is an “attack map” that breaks down each reduction step, from Kyber to M-LWE. It evaluates associated costs using both theoretical and practical attack vectors, including primal and dual lattice reduction, as well as side-channel assisted attacks. This analysis is grounded in formal input-output relationships and draws from primary sources including the 2017 Kyber proposal, the 2021 NIST specification, and numerous papers related to post-quantum lattice-based cryptography. By comparing the effectiveness and cost of each attack path, this project provides insight into the concrete security margins of Kyber and how they inform conservative key length choices in a post-quantum setting.