MODULE m1 · 8.0 HOURS
Quantum Threats and Lattice-based Cryptography
LEARNING OBJECTIVES
Module objectives
- Understand the threat models quantum computers pose to modern cryptographic systems (RSA, ECC).
- Analyze the mathematical foundations and security proofs of Lattice-based Cryptography.
- Learn the design principles of NIST-recommended Post-Quantum Cryptographic standards (ML-KEM, ML-DSA).
- Describe the efficiency and security characteristics (worst-case hardness) of lattice-based algorithms.
Quantum Threat Model
Modern public-key cryptography (PKI) primarily relies on the hardness of integer factorization (RSA) and discrete logarithm problems (ECC). Shor’s algorithm can solve these problems in polynomial time using a quantum computer, which implies that it effectively nullifies all current standard PKI[S3].
Lattice-based Cryptography
Lattice-based cryptography uses problems such as finding points in a lattice from basis vectors (e.g., SVP, LWE) in high-dimensional space as hard problems. It has been proven that these problems are hard even in the worst-case, and security is guaranteed in the average-case as well[S4].
Post-Quantum Standards (ML-KEM/ML-DSA)
- ML-KEM (Module-Lattice-based Key-Encapsulation Mechanism): A key encapsulation mechanism providing quantum resistance using lattice-based hard problems along with efficient implementation.
- ML-DSA (Module-Lattice-based Digital Signature Algorithm): A digital signature standard ensuring strong signature integrity using lattice-based mathematical structures. Lattice-based systems are becoming the center of PQC migration, proving strong worst-case to average-case hardness and efficient performance in the current standardization process[S4].
WORKED EXAMPLES
Worked examples
- Example 1: Analysis of the impact of quantum computers on RSA - RSA is based on the difficulty of factoring large integers. Shor's algorithm reduces the complexity of factoring n-bit integers from exponential to polynomial time, decrypting ciphertext immediately.
- Example 2: Understanding the Lattice-based Hard Problem (LWE) concept - Consider a system of linear equations A*s + e = t with a secret vector s and error e added. Lattice-based cryptography is based on the difficulty of the 'Learning With Errors' problem, which makes finding s from matrix A and result t difficult.
LAB PROTOCOL
Setting up Basic Lattice Cryptography Environment and Visualization
- 1
Create a Python 3 virtual environment in an isolated Linux/Docker environment.
- 2
Install and compile the liboqs library.
- 3
Write a script to collect key sizes and computation times according to parameter changes in the lattice-based LWE problem.
- 4
Run data analysis and visualization notebooks.
- All experiments must be performed within an isolated local virtual environment.
- Strictly prohibited to use actual operational certificates, private keys, or customer data.
- Do not treat research libraries as operational service security tools.
Lab deliverables
- Environment setup logs and compilation outputs.
- Algorithm performance (key size, time) comparative analysis data.
- Report on characteristics of lattice-based cryptography.
ASSIGNMENT
Writing a Quantum Threat Analysis Report
Deliverables
Rubric
- Accurately explains the principles of Shor's algorithm.
- Logically describes the concept of worst-case hardness in lattice-based cryptography.
- Describes the challenges faced by modern cryptography based on the provided sources [S3, S4].
KNOWLEDGE CHECK
Knowledge check
FIELD CHECK
Completion criteria
- Complete theory learning and submit quantum threat report.
- Successfully execute basic algorithms using liboqs in the lab environment.
- Achieve a correct answer rate of 80% or higher for each quiz item.
MODULE SOURCES
Module sources
- Security in Post-Quantum Era: A Comprehensive Survey on ...ieeexplore.ieee.org · paper
- Post-Quantum Cryptography and Quantum-Safe Security: A ...arxiv.org · paper