Lattice-Based Cryptography for Future Security — Epoche B2
Beyond Quantum Threats: Lattice-Based Cryptography for Future Security The advent of quantum computing has introduced significant challenges to the field of cryptography. A common belief suggests that all forms of asymmetric cryptography, including the widely used Elliptic Curve Digital Signature Algorithm (ECDSA), are equally vulnerable to quantum attacks. This perspective often overlooks the distinct mathematical underpinnings of various cryptographic systems and the specific ways quantum algorithms target them. While it is true that quantum computers pose a fundamental threat to ECDSA, this threat is not universal across all asymmetric schemes. Instead, a new class of cryptography, known as lattice-based cryptography, offers a promising path towards post-quantum security by relying on problems that appear resistant to known quantum attacks [1] . The Quantum Threat to Factoring and Discrete Logarithms Modern public-key cryptography [2] , such as RSA, derives its security from the presumed difficulty of the integer factorisation problem. This problem states that, given a large composite integer $N$, it is computationally infeasible for classical computers to find its prime factors $p$ and $q$. Mathematically, the problem is to find $p, q$ given: $$ N = p \cdot q $$ where $p$ and $q$ are large prime numbers. Similarly, the security of Elliptic Curve Digital Signature Algorithm (ECDSA) relies on the Elliptic Curve Discrete Logarithm Problem (ECDLP). Given a base point $P$ on an elliptic curve and a point $Q = kP$ (where $k$ is a secret integer), ECDLP asks to find $k$. Both the integer factorisation problem and the ECDLP are instances of a broader class of problems solvable by Shor's algorithm because they can be reduced to the period-finding problem [3] . The period-finding problem is central to Shor's algorithm. Given a function $f(x)$ that is periodic with an unknown period $r$, such that $f(x) = f(x+r)$ for all integers $x$, the problem is to find $r$. Shor's algorithm leverages the quantum Fourier transform to efficiently discover this period. For integer factorisation, this involves finding the period of the modular exponentiation function $f(x) = a^x \pmod N$ for a randomly chosen base $a$. Once the period $r$ is found, the factors $p$ and $q$ can be efficiently derived. The computational advantage of Shor's algorithm over classical methods is dramatic. For integer factorisation, the most efficient classical algorithm is the General Number Field Sieve (GNFS). Its asymptotic time complexity, for an integer $N$, is typically expressed using the $L$-notation: $$ T_{\text{GNFS}}(N) = L_N[1/3, (64/9)^{1/3}] $$ where $L_N[\alpha, c] = \exp\left((c+o(1))(\log N)^\alpha (\log \log N)^{1-\alpha}\right)$ defines the sub-exponential complexity class. For ECDLP, the best general-purpose classical algorithm is Pollard's rho, with a time complexity proportional to the square root of the order $N_{\text{group}}$ of the elliptic curve group: $$ T_{\text{Pollard's rho}}(N_{\text{group}}) = O(\sqrt{N_{\text{group}}}) $$ This complexity is exponential in the bit-length of the group order. Compared to the sub-exponential complexity of GNFS, this allows ECC to achieve the same level of security with significantly smaller keys than RSA, which is the primary reason for its efficiency and widespread adoption. In stark contrast to these classical algorithms, Shor's algorithm can solve both integer factorisation and ECDLP in polynomial time with respect to $\log N$ (where $N$ is the number to be factored or the order of the group). The time complexity for Shor's algorithm to factor $N$ (in terms of elementary quantum gates) is: $$ T_{\text{Shor}}(N) = O((\log N)^2 \log \log N \log \log \log N) $$ This stark difference in complexity means that large-scale quantum computers would render RSA and ECDSA fundamentally insecure, necessitating a shift to new cryptographic paradigms. Lattices and Their Hard Problems Lattice-based cryptography operates on entirely different mathematical principles, deriving its security from the presumed hardness of problems related to lattices. A lattice $\mathcal{L}$ is a discrete set of points in $n$-dimensional Euclidean space $\mathbb{R}^n$, formed by all integer linear combinations of a set of linearly independent basis vectors $b_1, \dots, b_n \in \mathbb{R}^n$. Any point $v \in \mathcal{L}$ can be written as: $$ v = \sum_{i=1}^n x_i b_i $$ where $x_i$ are integers. The set $\{b_1, \dots, b_n\}$ is called a basis for the lattice $\mathcal{L}$. Crucially, a given lattice can have many different bases, some 'good' (nearly orthogonal) and some 'bad' (skewed). Two fundamental hard problems in lattices underpin lattice-based cryptography: The Shortest Vector Problem (SVP) : Given a basis for a lattice $\mathcal{L}$, find a non-zero vector $v \in \mathcal{L}$ such that its Euclidean norm $\|v\|$ is minimised. That is, find $v$ such that: $$ \|v\| = \min_{u \in \mathcal{L} \setminus \{0\}} \|u\| $$ The Euclidean norm of a vector $v=(v_1, \dots, v_n)$ is defined as $\|v\| = \sqrt{v_1^2 + \dots + v_n^2}$. The Closest Vector Problem (CVP) : Given a basis for a lattice $\mathcal{L}$ and a target point $t \in \mathbb{R}^n$ (which may or may not be in the lattice), find a lattice point $v \in \mathcal{L}$ that is closest to $t$. That is, find $v$ such that: $$ \|v - t\| = \min_{u \in \mathcal{L}} \|u - t\| $$ These problems are generally NP-hard for arbitrary lattices in high dimensions $n$. Cryptographic schemes are typically built upon approximate versions of these problems, which are also believed to be hard. A 2D lattice formed by skewed basis vectors b1 and b2. A target point 't' is shown, and the closest lattice point 'v' is highlighted. A dashed line connects 't' and 'v'. b 1 b 2 t v x 1 x 2 Fig. 1 — Visualisation of the Closest Vector Problem (CVP) in a 2-dimensional lattice. The lattice points (dark circles) are generated by integer linear combinations of basis vectors $b_1$ (ambe