Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems
Alexander Meyer · 2025
Read Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems by Alexander Meyer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08791.txt.
Introduction
Alexander Meyer analyzes two families of encryption systems that may resist attacks from quantum computers, published in 2025. Most systems in use today rest on math problems that are hard for current machines. A quantum computer running Shor's algorithm could break them, so replacements are needed well in advance.
First, Meyer examines the McEliece system, a code-based scheme. Its safety rests on how hard it is to decode arbitrary linear codes. Next he explores NTRU, a lattice-based system grounded in the shortest vector problem. The paper then draws links between the structure and the security of the two systems. It is an analysis piece, comparing foundations rather than reporting a new encryption method.
Catalog record
| CREATOR | Alexander Meyer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 153 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-08791
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems Alexander Meyer Abstract 1 Introduction Although not fully developed yet, quantum computers are expected to emerge in the near future, likely within ten to twenty years, which will pose a great threat to our encrypted data. Most modern cryptographic systems are not unbreakable but are presumed to be computationally difficult with the tools currently available. These systems are centered around the concept of “trapdoor” mathematical functions that work easily in one direction (encryption) and harder in the other (decryption) without access to a special key. Examples of these prominent cryptosystems include RSA, the Diffie-Hellman Key Exchange, and elliptic curve cryptography, all of which are based on problems that are presumed to be difficult and expensive for a classical computer to perform. However, quantum computers will be able to crack these systems rapidly using Shor’s Algorithm, which is why research is currently being conducted into post-quantum cryptography to discover cryptographic methods that can withstand attacks from quantum computers [ 1 ] . In 2016, the National Institute of Standards and Technology ( NIST ) launched a competition to discover candidates for post-quantum cryptography, where experts submit proposals for new cryptosystems that will then undergo evaluation and attacks to determine their security. As the competition began, various kinds of cryptosystems were proposed and many were broken; however, lattice-based, code-based, and multivariate systems seemed to be the strongest. This paper will focus on both code-based and lattice-based systems and will also explore the connection between these two seemingly distinct cryptographic methods. 2 Code-Based Cryptography Code-based cryptographic systems incorporate error-correcting, linear codes, and their security is typically based on the difficulty of finding the nearest codeword for an arbitrary linear code [ 2 ] . One of the most significant code-based systems is the McEliece cryptosystem, which uses a special class of codes, binary Goppa codes. These codes have an efficient decoding algorithm in Patterson’s Algorithm, which allows the owner of the private key to decrypt a ciphertext quickly, whereas an eavesdropper cannot [ 3 ] . 2.1 Binary Goppa Codes Let g be an irreducible polynomial of degree t over the finite field GF(2^{m}) such that g(x)=\sum^{t}_{i=0}g_{i}x^{i}=g_{0}+g_{1}x+...+g_{i}x^{i} with g_{i}\in GF(2^{m}) [ 4 ] . Let L be the sequence L=(\alpha_{0},...,\alpha_{n-1}) of n distinct elements in GF(2^{m}) such that g(\alpha_{i})\neq 0 , for 0\leq i<n [ 4 ] . The binary Goppa code C(g,L) is defined as C(g,L)=\left\{c\in\mathbb{Z}^{n}_{2}\Bigg|\sum^{n-1}_{i=0}\frac{c_{i}}{x-\alpha_{i}}\equiv 0\pmod{g(x)}\right\} In other words, the binary Goppa code C(g,L) consists of the set of all vectors that belong to the kernel of the syndrome function [ 5 ] s(x)\equiv\sum^{n-1}_{i=0}\frac{c_{i}}{x-\alpha_{i}}\pmod{g(x)} The parity-check matrix of a Goppa code is the (n-k)\times n matrix H=XYZ where X=\begin{bmatrix}g_{t}&0&0&\cdots&0\\ g_{t-1}&g_{t}&0&\cdots&0\\ g_{t-2}&g_{t-1}&g_{t}&\ddots&\vdots\\ \vdots&\vdots&\vdots&\ddots&0\\ g_{1}&g_{2}&g_{3}&\cdots&g_{t}\end{bmatrix},\;Y=\begin{bmatrix}1&1&\cdots&1\\ \alpha^{1}_{0}&\alpha^{1}_{1}&\cdots&\alpha^{1}_{n-1}\\ \vdots&\vdots&\ddots&\vdots\\ \alpha^{t-1}_{0}&\alpha^{t-1}_{1}&\cdots&\alpha^{t-1}_{n-1}\end{bmatrix}\mathrm{,\;and} Z=\begin{bmatrix}\frac{1}{g(\alpha_{0})}&0&0&\cdots&0\\ 0&\frac{1}{g(\alpha_{1})}&0&\cdots&0\\ 0&0&\frac{1}{g(\alpha_{2})}&\ddots&\vdots\\ \vdots&\vdots&\ddots&\ddots&0\\ 0&0&\cdots&0&\frac{1}{g(\alpha_{n-1})}\end{bmatrix} Given that GH^{T}=0 , the k\times n generator matrix G of a binary Goppa code can be obtained by finding the null space of the parity-check matrix H . Note that binary Goppa codes have a length of n=2^{m} , a minimum dimension of n-mt , and a minimum distance of 2t+1 . Thus, the parameters of a [n,k,d] -Goppa code are [2^{m},\geq n-mt,\geq 2t+1] . 2.2 The McEliece Cryptosystem Proposed by Robert J. McEliece in 1978, the McEliece cryptosystem is a public-key encryption algorithm that has resisted cryptanalytic attacks to this day and serves as the basis for the majority of code-based systems. Despite being invented around the same time as RSA, the McEliece cryptosystem was not widely used due to its larger key size. However, due to the security it provides against quantum computers, the cryptosystem has received attention as a strong candidate for post-quantum cryptography. 2.2.1 Key Generation Suppose Alice wants to send a message to Bob. In order for this to happen, Bob must generate two keys, a public key and a private key. The public key will be shared online and is what Alice will use to encrypt her message. Bob will keep his private key secret, which he will use to decrypt Alice’s message. Note that it is infeasible for an eavesdropper to determine the private key solely from the public key. First, Bob selects a random irreducible Goppa polynomial of degree t and computes its corresponding generator matrix G . Then, Bob chooses an arbitrary k\times k binary non-singular matrix S and a random n\times n permutation matrix P (identity matrix with columns scrambled) [ 6 ] . Bob then computes his public key, which consists of the k\times n matrix \hat{G}=S\times G\times P and the value of t . Bob keeps his private key (S,G,P) secret. 2.2.2 Encryption In order to encrypt a message m , Alice must generate a random binary error vector e of length n and weight less than or equal to t . Then, to obtain the ciphertext c , Alice must compute c\equiv m\cdot\hat{G}+e\pmod{2} Note that ‘ \cdot ’ denotes matrix-vector multiplication and ‘ \times ’ denotes matrix multiplication [ 2 ] . If m is longer than k bits, Alice must break up m into multiple k -bit sequences, each of which can be encrypted separately and then concatenated. Note that k is known since it is the number of rows of the published matrix \hat{G} . 2.2.3 Decryption To decrypt the ciphertext c , Bob first uses his private key to calculate P^{-1} . Then, Bob computes \hat{c}\equiv c\cdot P^{-1}\equiv m\cdot S\times G+e\cdot P^{-1}\pmod{2} Next, Bob decodes \hat{c} to the scrambled message v\equiv m\cdot S\pmod{2} using Patterson’s Algorithm, an efficient decoding algorithm. Note that the permuted error vector e\cdot P^{-1} has weight t since P^{-1} simply scrambles the elements of the error vector, which means that decoding still works [ 6 ] . Finally, Bob recovers m by calculating m\equiv v\cdot S^{-1}\pmod{2} . 2.2.4 Encryption and Decryption Example For the sake of simplicity, this example will use small parameters for the binary Goppa code; however, note that in practice, the McEliece cryptosystem with these parameters would not be secure. Suppose Alice wants to send a message to Bob. First, Bob selects a [16,8,5] binary Goppa code and finds its generator matrix [ 7 ] G=\left[\begin{array}[]{*{20}c}1&0&0&0&0&0&0&0&1&0&0&1&0&1&0&1\\ 0&1&0&0&0&0&0&0&1&0&1&0&0&1&1&0\\ 0&0&1&0&0&0&0&0&1&1&0&0&0&0&1&1\\ 0&0&0&1&0&0&0&0&1&1&1&0&1&0&0&0\\ 0&0&0&0&1&0&0&0&0&1&0&1&1&1&0&0\\ 0&0&0&0&0&1&0&0&0&1&0&1&1&0&1&1\\ 0&0&0&0&0&0&1&0&0&0&1&1&1&1&1&1\\ 0&0&0&0&0&0&0&1&0&1&1&1&0&0&1&0\\ \end{array}\right] Next, Bob randomly chooses an invertible matrix S=\begin{bmatrix}0&0&1&0&0&1&1&0\\ 1&0&1&0&1&0&1&0\\ 0&0&0&0&0&1&0&0\\ 1&1&0&0&0&0&0&0\\ 0&1&0&1&0&1&0&1\\ 1&1&1&1&1&0&0&0\\ 0&0&0&1&0&1&0&1\\ 0&0&1&1&1&1&1&0\end{bmatrix} and a permutaion matrix P=\begin{bmatrix}e_{4},\;e_{5},\;e_{1},\;e_{12},\;e_{13},\;e_{11},\;e_{16},\;e_{2},\;e_{8},\;e_{9},\;e_{15},\;e_{7},\;e_{6},\;e_{3},\;e_{10},\;e_{14}\end{bmatrix} where the columns are the standard basis vectors e_{i} . Bob then computes his public key \hat{G}=S\times G\times P=\left[\begin{array}[]{*{16}c}0&0&0&0&0&1&1&0&0&1&1&1&1&1&0&1\\ 0&1&1&1&0&1&1&0&0&0&0&1&0&1&0&1\\ 0&0&0&1&1&0&1&0&0&0&1&0&1&0&1&0\\ 0&0&1&1&0&1&1&1&0&0&1&0&0&0&0&0\\ 1&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1\\ 1&1&1&0&0&0&0&1&0&0&0&0&0&1&1&1\\ 1&0&0&0&0&0&1&0&1&1&0&0&1&0&1&0\\ 1&1&0&1&0&0&1&0&0&0&1&1&1&1&0&0\end{array}\right] and makes his private key (S,G,P) . Alice wants to encrypt the message m=(1,0,1,0,0,1,1,0) , so she chooses an error vector e=(0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0) of weight 2 and computes c\equiv m\cdot\hat{G}+e\equiv(0,1,1,1,1,0,1,1,1,0,0,0,1,0,1,0)\pmod{2} which she sends to Bob. Bob then calculates \hat{c}\equiv c\cdot P^{-1}\equiv m\cdot S\times G+e\cdot P^{-1}\equiv(1,1,0,0,1,0,0,1,1,1,1,1,0,1,0,0)\pmod{2} Next, Bob uses the Patterson algorithm to decode \hat{c} to the message v=m\cdot S\equiv(1,1,0,0,1,1,1,1)\pmod{2} Finally, Bob recovers m by calculating m\equiv v\cdot S^{-1}\equiv(1,0,1,0,0,1,1,0)\pmod{2} 2.2.5 Security Suppose a third party named Eve intercepts the encrypted message sent from Alice to Bob. Eve has access to the public information, so she knows \hat{G} . Since she intercepts the ciphertext, she also knows the value of c=m\cdot\hat{G}+e , as well as the weight t of the error vector e . Without the private key, there are