2504.16091

# Post-Quantum Homomorphic Encryption: A Case for Code-Based Alternatives **Authors**: Siddhartha Siddhiprada Bhoi, Arathi Arakala, Amy Beth Corman, Asha Rao > School of Computing Technologies, RMIT University, Australia Abstract Homomorphic Encryption (HE) allows secure and privacy-protected computation on encrypted data without the need to decrypt it. Since Shor’s algorithm rendered prime factorisation and discrete logarithm-based ciphers insecure with quantum computations, researchers have been working on building post-quantum homomorphic encryption (PQHE) algorithms. Most of the current PQHE algorithms are secured by Lattice-based problems and there have been limited attempts to build ciphers based on error-correcting code-based problems. This review presents an overview of the current approaches to building PQHE schemes and justifies code-based encryption as a novel way to diversify post-quantum algorithms. We present the mathematical underpinnings of existing code-based cryptographic frameworks and their security and efficiency guarantees. We compare lattice-based and code-based homomorphic encryption solutions identifying challenges that have inhibited the progress of code-based schemes. We finally propose five new research directions to advance post-quantum code-based homomorphic encryption. Keywords: Homomorphic encryption; code-based encryption; post-quantum cryptography; review 1 Introduction Homomorphic encryption (HE) allows computations to be performed directly on encrypted data without decryption, enabling privacy-preserving computation in applications such as secure cloud computing, medical data analysis, and federated learning [10]. HE ensures the confidentiality of sensitive data while still being usable for computation, making it a critical tool in modern cryptography. Homomorphic properties were first observed in classical public-key cryptosystems by Rivest et al [65] where certain operations like multiplication could be performed homomorphically on the ciphertexts. Although the scheme was broken a decade later by Brickell and Yacobi [26], it initiated the research on homomorphic encryption (HE) schemes in the cryptography community. Many early homomorphic encryption schemes were based on number-theoretic assumptions of NP-hardness. However, with the advent of quantum computing, classical cryptographic systems face significant threats. Quantum algorithms, such as Shor’s and Grover’s algorithms, can efficiently solve problems such as integer factorization and discrete logarithms, thus undermining the security foundations of widely used public-key schemes such as RSA and ECC [67]. As many early homomorphic encryption (HE) constructions rely on these same number-theoretic assumptions, the potential for quantum adversaries to break the underlying hard problems necessitated a comprehensive re‐examination of HE for a post‐quantum era. In response, research has increasingly focused on developing post-quantum homomorphic encryption (PQHE) schemes built on hard mathematical problems believed to be resistant to quantum attacks. In 2009, Gentry [44] proposed the first FHE scheme in his Ph.D. thesis, which allowed both addition and multiplication operations to be performed on ciphertexts without observation of the plaintexts. The scheme used NP-hard problems based on lattice-theory. Subsequently, lattice-based cryptography emerged as a leading candidate to construct PQHE schemes. Cryptographic primitives based on the Learning With Errors (LWE) problem and its ring variant (RLWE) also offer robust security guarantees as no efficient quantum algorithm is currently known for solving these problems — even approximately [55]. These lattice‐based approaches underpin modern schemes such as the Brakerski–Fan–Vercauteren (BFV) and Cheon–Kim–Kim–Song (CKKS) constructions, which have been reevaluated and adapted to meet post‐quantum security requirements [23]. Parallel to these theoretical advancements, practical frameworks such as PALISADE [35] and its successor OpenFHE [64] have integrated lattice‐based HE schemes optimized for post‐quantum security. These efforts underscore the practical drive to transition existing systems to quantum‐resistant alternatives while addressing efficiency challenges, such as managing noise growth during computations and optimizing bootstrapping procedures, to maintain the homomorphic properties essential for real-world applications [28]. Although most of the focus of HE schemes is still based on lattice-theory, in 2024 Chen proposed new techniques involving Quantum Fourier Transforms that claimed to solve LWE problems and their reductions to other lattice-based hard problems in polynomial time [29]. While the validity of the claim is questionable [68], it raised concerns about relying completely on the security of lattice-based cryptographic algorithms in the post-quantum era. A complementary, though less explored, approach to developing post-quantum homomorphic encryption (PQHE) schemes involves NP-hard problems related to error-correcting codes. Code-based cryptography has emerged as a promising option for post-quantum homomorphic encryption due to its inherent resistance to quantum attacks and potential efficiency advantages. Here, security assumptions are based on NP-hard problems, such as the Syndrome Decoding Problem (SDP) and the Binary Goppa Code Distinguishing Problem [17], both of which are resilient to known quantum algorithms. Unlike lattice-based schemes, which depend on complex algebraic structures and intricate noise management techniques, code-based homomorphic encryption utilizes well-established error-correcting codes. This makes implementation simpler and allows for alternative security assumptions. The specific trade-offs between security, efficiency, and implementation complexity highlight the importance of exploring code-based methods for future cryptographic systems, particularly in a post-quantum landscape. This review aims to be a resource for researchers wanting to advance PQHE using the less-studied code-based cryptography. It brings together the mathematical underpinnings of code-based HE schemes with the intention of deepening understanding of the NP-hard problems in this domain as well as presenting avenues to kickstart new research in the development of code-based PQFHE. The key contributions of this work are: 1. Insights from reviews of existing Homomorphic Encryption Schemes: Identifies the lop-sided focus of current FHE schemes on lattice-based NP-hard problems. This demonstrates a clear weakness in PQFHE schemes if quantum lattice reduction algorithms are found. 1. Systematic Review of Code-based Homomorphic Encryption Schemes: Provides a detailed analysis of code-based Homomorphic encryption schemes and their security guarantees. 1. Comparative Analysis of Code-Based with Lattice-based Homomorphic Encryption schemes: Presents a detailed comparison of code-based HE with lattice-based HE and identifies the reasons code-based HE is not well studied. 1. New directions for Code-based Homomorphic Encryption in the Post-Quantum Era: Outlines five clear research directions to advance the development of code-based PQ-FHE. We will first analyse the existing reviews of homomorphic encryption schemes, and illustrate the difference of this review. In Section 3 we provide a background on homomorphic encryption schemes categorising them into partially homomorphic, somewhat homomorphic and fully homomorphic. Then in Section 4 we present the details of code-based cryptography, while in Section 5 we detail code-based homomorphic schemes, giving a comprehensive analysis of the strengths and weaknesses of each scheme and comparing them to lattice-based schemes. Finally, we present the conclusion along with the challenges in implementing code-based PQHE and a list of future research opportunities. 2 Existing reviews of homomorphic encryption schemes To maximise the relevance of the current review, we analysed existing reviews on HE schemes. Scopus and IEEE databases were chosen as the source of our search process. On both databases we used the search terms “Homomorphic Encryption” and “Privacy-Preserving Encryption”, limited our results to only review articles and did not put limits on the year of publication. We found 108 articles, with the first review published in 2010. We found two duplicates across the database and they were removed. We screened the title and abstracts for relevance and excluded one article as it did not focus on HE or its applications. We then filtered out all articles published in the year 2020 and prior. This gave us 78 review articles on HE published in the last 5 years. Figure 1 illustrates the distribution of published articles over the last 5 years. The trend indicates a surge of research since 2023 driven by advancements in HE applications. Figure 2 presents the quality ratings of the journals where the review articles were published. It can be seen that only $33\%$ (26 articles) of the published reviews are in high quality Q1 journals. Most of the Q1 articles focussed on applications of HE in various fields rather than on the HE schemes and their theory. There were only four theoretical, non-application-based review articles and these were selected for further analysis. Alaya et al. [6] provide an overview of homomorphic encryption (HE) systems, highlighting trends in efficiency, security, and usability, while addressing challenges such as computational overhead and scalability. Aloufi et al. [10] investigate multi-party computations and secure collaborative analytics, discussing various schemes, security guarantees, and practical applications. Gorantala et al. [46] explore advancements in fully homomorphic encryption (FHE) and its real-world feasibility, focusing on performance improvements and necessary breakthroughs for secure cloud computing. Dhiman et al. [37] evaluate software libraries and tools for homomorphic encryption, comparing their performance and usability to assist researchers in tool selection. <details> <summary>extracted/6317219/ss.png Details</summary>  ### Visual Description ## Bar Chart: Number of HE Review Papers Published Per Year (2020-2025) ### Overview The image is a bar chart showing the number of HE (presumably Higher Education) review papers published per year from 2021 to 2025. The y-axis represents the number of review papers, and the x-axis represents the year. The bars are light blue. ### Components/Axes * **Title:** Number of HE Review Papers Published Per Year (2020-2025) * **X-axis:** Year, with labels for 2021, 2022, 2023, 2024, and 2025. * **Y-axis:** Number of Review Papers, with labels at intervals of 2, from 0 to 8. * **Data:** Light blue bars representing the number of papers published each year. ### Detailed Analysis * **2021:** Approximately 3 papers * **2022:** Approximately 5 papers * **2023:** Approximately 9 papers * **2024:** Approximately 9 papers * **2025:** Approximately 2 papers ### Key Observations The number of publications increases from 2021 to 2023, plateaus in 2023-2024, and then decreases significantly in 2025. ### Interpretation The chart indicates a surge in HE review paper publications in 2023 and 2024, followed by a sharp decline in 2025. This could be due to various factors, such as changes in research funding, shifts in academic focus, or the completion of specific research projects. The initial increase suggests growing interest or emphasis on HE review papers, while the subsequent decrease warrants further investigation to understand the underlying causes. The data suggests a potential cycle or trend in HE review paper publications over the observed period. </details> Figure 1: Distribution of review papers on Homomomorphic Encryption published in last 5 years by year of publication. <details> <summary>extracted/6317219/Picture2.png Details</summary>  ### Visual Description ## Pie Chart: Quarterly Distribution ### Overview The image is a pie chart displaying the distribution of a whole across four quarters (Q1, Q2, Q3, Q4). Each quarter is represented by a different color, and the percentage each quarter represents is displayed on the chart. ### Components/Axes * **Chart Type:** Pie Chart * **Categories:** Q1, Q2, Q3, Q4 * **Colors:** * Q1: Dark Teal * Q2: Orange * Q3: Dark Green * Q4: Light Blue * **Legend:** Located on the right side of the chart, listing each quarter and its corresponding color. ### Detailed Analysis * **Q1 (Dark Teal):** 33% * **Q2 (Orange):** 28% * **Q3 (Dark Green):** 25% * **Q4 (Light Blue):** 14% ### Key Observations * Q1 has the largest share (33%). * Q4 has the smallest share (14%). * The shares of Q2 and Q3 are relatively close (28% and 25%, respectively). ### Interpretation The pie chart illustrates the relative contribution of each quarter to a whole. Q1 contributes the most, suggesting it may be the most productive or significant quarter. Q4 contributes the least, suggesting it may be the least productive or significant quarter. The differences in percentages between the quarters indicate varying levels of contribution or activity across the year. </details> Figure 2: Scimago [1] journal quartile distribution of review papers on Homomorphic Encryption in 5 years Table 1 compares the range of topics covered by these four articles. We assessed whether the reviews provided an overview of HE systems, discussed multi-key HE, included research on Fully Homomorphic Encryption (FHE), presented libraries or frameworks to practically apply HE, provided description of HE toolkits, indicated techniques to speed up HE algorithms including refresh key generation, identified existing and foreseeable challenges in the domain of HE and presented future trends in HE. We also investigated if any of these reviews included HE schemes that used code-based cryptography. As shown in the last row of Table 1, none of the review articles mention code-based HE or discussed the advantages of using such approaches in the post-quantum era. The current review starts to address this deficiency in the existing literature by providing a first step towards developing an alternative code-based approach for HE in the post-quantum era. Table 1: Coverage of Homomorphic Encryption Topics in Previous Reviews | Aspect | Alaya et.al. [6] | Aloufi et.al. [10] | Gorantala et.al. [46] | Dhiman et.al. [37] | | --- | --- | --- | --- | --- | | Overview of HE systems | ✓ | ✓ | ✓ | ✓ | | Multi-key HE | $×$ | ✓ | $×$ | $×$ | | Fully Homomorphic Encryption (FHE) | ✓ | ✓ | ✓ | ✓ | | HE Libraries/ Frameworks | $×$ | $×$ | $×$ | ✓ | | HE Toolkits | $×$ | $×$ | $×$ | ✓ | | HE Accelerators | $×$ | $×$ | $×$ | ✓ | | Challenges in HE | ✓ | $×$ | ✓ | $×$ | | Future Trends | ✓ | $×$ | ✓ | $×$ | | Code-based HE | $×$ | $×$ | $×$ | $×$ | 3 Background on Homomorphic Encryption This section provides an overview of homomorphic encryption (HE), explaining its basic principles and levels of capability. Homomorphic encryption allows computations on encrypted data without decryption. Each of the different types: partially homomorphic encryption (PHE), somewhat homomorphic encryption (SWHE), and fully homomorphic encryption (FHE), offers varying degrees of flexibility and efficiency. This background helps in understanding the advancements and challenges in HE research. 3.1 Homomorphic Encryption: Definitions Homomorphic encryption (HE) is a cryptographic technique that allows computations to be performed on encrypted data without the need for decryption. This property enables the processing and analysis of sensitive information while preserving its confidentiality and integrity. 3.1.1 Formal definition of Homomorphic Encryption Formally, a homomorphic encryption scheme can be defined as a tuple of probabilistic polynomial-time (PPT) algorithms, denoted as $\text{HE}=(\text{KeyGen},\text{Enc},\text{Eval},\text{Dec})$ [10]. Each algorithm is described in detail below: - Key Generation (KeyGen): $\text{HE.KeyGen}(1^{\lambda})→(pk,sk,ek)$ : Given a security parameter $\lambda$ that determines the level of security, the key generation algorithm outputs a public key $pk$ , a secret key $sk$ , and an evaluation key $ek$ . The public key is used for encryption, the secret key for decryption, and the evaluation key for performing homomorphic operations. - Encryption (Enc): $\text{HE.Enc}(pk,m)→ c$ : Given a message $m$ and the public key $pk$ , the encryption algorithm outputs a ciphertext $c$ . The ciphertext $c$ is an encrypted version of the message $m$ , which can be processed homomorphically without revealing the underlying plaintext. - Evaluation (Eval): $\text{HE.Eval}(ek,f,c,c^{\prime})→ c_{\text{eval}}$ : Given two ciphertexts $c$ and $c^{\prime}$ , an evaluation key $ek$ , and a homomorphic function $f$ , the evaluation algorithm outputs an evaluated ciphertext $c_{\text{eval}}=f(c,c^{\prime})$ . The evaluation key $ek$ is used to enable homomorphic operations, and it plays a crucial role in the bootstrapping process, which refreshes the ciphertext to allow for further computations. - Decryption (Dec): $\text{HE.Dec}(sk,c)→ m$ : Given a ciphertext $c$ encrypted under the public key $pk$ , the decryption algorithm outputs the original message $m$ using the corresponding secret key $sk$ . This ensures that only the holder of the secret key can access the decrypted data. <details> <summary>extracted/6317219/HE.jpg Details</summary>  ### Visual Description ## Diagram: Homomorphic Encryption ### Overview The image illustrates a simplified diagram of a homomorphic encryption process. It shows how two inputs, X and Y, are encrypted separately, then evaluated in their encrypted forms, and finally decrypted to produce a result Z, which is equivalent to X + Y. ### Components/Axes * **Shapes:** Rectangles, Circles, Arrows * **Colors:** Green, Red, Yellow, Blue * **Text Labels:** X, Y, Z, A, B, C, Encryption, Decryption, Eval, +, = ### Detailed Analysis 1. **Top Row:** * A yellow rectangle labeled "Z" is positioned on the top-left. * An equals sign (=) is next to "Z". * A green rectangle labeled "X" is next to the equals sign. * A plus sign (+) is next to "X". * A red rectangle labeled "Y" is next to the plus sign. * The equation "Z = X + Y" is formed. 2. **First Encryption Branch (Left):** * A green rectangle labeled "X" is present. * A light blue arrow labeled "Encryption" points from "X" to a green circle labeled "A". 3. **Second Encryption Branch (Right):** * A red rectangle labeled "Y" is present. * A light blue arrow labeled "Encryption" points from "Y" to a red circle labeled "B". 4. **Evaluation:** * A green circle labeled "A" is present. * A plus sign (+) is next to "A". * A red circle labeled "B" is next to the plus sign. * A light blue arrow labeled "Eval" points from "A + B" to a yellow circle labeled "C". 5. **Decryption:** * A yellow circle labeled "C" is present. * A light blue arrow labeled "Decryption" points from "C" to a yellow rectangle labeled "Z". ### Key Observations * The diagram visually represents the process of homomorphic encryption, where operations can be performed on encrypted data. * The colors (green, red, yellow) seem to differentiate the data at different stages of the process. * The arrows indicate the flow of data and the transformations applied to it. ### Interpretation The diagram illustrates the core concept of homomorphic encryption. It demonstrates that by encrypting X and Y separately, performing an evaluation (addition in this case) on the encrypted values (A and B), and then decrypting the result (C), one can obtain the same result (Z) as if the addition was performed on the original unencrypted values of X and Y. This is significant because it allows computations to be performed on sensitive data without ever exposing the raw data itself, maintaining privacy and security. </details> Figure 3: Illustration of the general Homomorphic Encryption process. Here $X,Y$ are plaintexts, $A,B$ are encryptions of $X,Y$ respectively, $C$ is the homomorphic evaluation of $A,B$ , while $Z$ is the decrypted value of $C$ . Figure 3 provides a conceptual overview of how homomorphic encryption allows computations to be performed directly on encrypted data. The process happens in four main stages: 1. Plaintext Inputs ( $X,Y$ ): Two plaintext values, labeled $X$ (green) and $Y$ (red), are shown in Figure 3. In this example, the goal is to compute the sum $Z=X+Y$ securely. 1. Encryption ( $A,B$ ): Each plaintext is independently encrypted, producing ciphertexts $A$ (encrypted form of $X$ ) and $B$ (encrypted form of $Y$ ). These ciphertexts are represented by the green and red circles, respectively. 1. Homomorphic Evaluation ( $C$ ): The ciphertexts $A$ and $B$ are processed by a homomorphic evaluation function (indicated by the arrow labeled “Eval”). Because the scheme is homomorphic, the evaluation computes the sum of the underlying plaintexts—i.e., it effectively adds $X$ and $Y$ —without ever decrypting them. This step yields a new ciphertext $C$ . 1. Decryption ( $Z$ ): Finally, decrypting $C$ recovers the result $Z$ , which matches the sum $X+Y$ . In other words, $\mathrm{Dec}(C)=Z=X+Y$ . 3.1.2 Mathematical definition of Homomorphic Encryption Mathematically, a homomorphic encryption (HE) scheme is defined as follows: **Definition 1** *A homomorphic encryption (HE) scheme is an encryption scheme that satisfies the following property: For all ciphertexts $C_{1},C_{2}∈\mathcal{C}$ , all plaintexts $M_{1},M_{2}∈\mathcal{P}$ , and for any key $K$ , if $$ C_{1}=\operatorname{Enc}(M_{1})\quad\text{and}\quad C_{2}=\operatorname{Enc}(M% _{2}), $$ then $$ \operatorname{Dec}\bigl{(}C_{1}\circ C_{2}\bigr{)}=M_{1}\odot M_{2}. $$ Here, $\circ$ and $\odot$ denote the group operations in the ciphertext space $\mathcal{C}$ and the plaintext space $\mathcal{P}$ , respectively.* 3.2 Levels of Homomorphism HE schemes are often classified into three levels based on the types and number of homomorphic operations that can be supported. These are: - Partially Homomorphic Encryption (PHE): Supports only one operation (e.g., addition or multiplication). - Somewhat Homomorphic Encryption (SHE): Supports all operations, but has limitations on the number of operations of a certain type. - Fully Homomorphic Encryption (FHE): Enables unlimited arbitrary computations on encrypted data. Table 2 compares the salient features of the different levels of homomorphic encryption. Table 2: Features of Partial HE, Somewhat HE, and Fully HE. | Supported Operations | Supports one type of operation (either addition or multiplication). | Supports both addition and multiplication but only for a limited number of operations (shallow circuit depth). | Supports arbitrary computations (both addition and multiplication without a fixed limit). | | --- | --- | --- | --- | | Noise Growth | Minimal noise accumulation, making these schemes computationally efficient. | Noise accumulates with each operation (linear for additions; quadratic or even exponential for multiplications), limiting computation depth. | Requires advanced noise management techniques (bootstrapping, modulus switching, relinearization) to control error growth over arbitrary computations. | | Complexity & Efficiency | Generally the most efficient and simplest in design (e.g., RSA, Paillier, ElGamal). | More complex than PHE; efficiency is affected by the need to manage noise, often limiting practical depth without additional techniques. | Most complex and computationally intensive due to elaborate noise control and the necessity for periodic refreshment of ciphertexts. | | Common Examples | RSA (multiplicative), Paillier (additive), and ElGamal (multiplicative or adapted to additive in variants). | Early schemes such as Gentry’s original SWHE, later improved in the Brakerski–Gentry–Vaikuntanathan (BGV) and Fan–Vercauteren (FV) schemes. | Advanced lattice-based schemes including Gentry’s FHE, GSW, CKKS, among others, each incorporating techniques to enable fully homomorphic evaluation. | | Security Assumptions | Relies on hardness problems such as the Integer Factorization Problem (IFP), Decisional Composite Residuosity (DCR), or the Discrete Logarithm Problem (DLP). | Based on lattice problems such as Learning With Errors (LWE) or Ring-LWE, with security intricately linked to noise management. | Built on advanced lattice assumptions (Ideal Lattice, LWE, RLWE, and variants) and often require additional measures to maintain security under extensive operations. | 3.2.1 Partial Homomorphic Encryption(PHE) Partial Homomorphic Encryption (PHE) schemes support either additive or multiplicative homomorphism, allowing a single type of operation to be performed on ciphertexts. These schemes are computationally efficient but limited in functionality, as they cannot support both operations simultaneously. One of the most well-known PHE schemes is the RSA cryptosystem, which exhibits multiplicative homomorphism. In RSA, the product of two ciphertexts corresponds to the encryption of the product of their plaintexts, i.e., $Enc(m_{1})· Enc(m_{2})=Enc(m_{1}· m_{2})$ . However, RSA in its textbook form is deterministic, making it semantically insecure. RSA’s security relies on the Integer Factorization Problem (IFP), where the public key consists of a modulus $N=pq$ , where $p,q$ are prime numbers, and an exponent $e$ coprime to $\phi(N)$ . This simple version of RSA is vulnerable to chosen-ciphertext attacks if used without proper padding [65]. Another widely used PHE scheme is the Paillier cryptosystem [62], which supports additive homomorphism. In Paillier, the product of two ciphertexts corresponds to the encryption of the sum of their plaintexts, i.e., $Enc(m_{1})+Enc(m_{2})=Enc(m_{1}+m_{2})\mod n^{2}$ . Paillier is probabilistic, ensuring semantic security, and its hardness is based on the Decisional Composite Residuosity (DCR) assumption [62]. The public key in the Paillier cryptosystem consists of a modulus $n=pq$ . Encryption is performed by computing $c=g^{m}· r^{n}\mod n^{2}$ , where $g∈\mathbb{Z}^{*}_{n^{2}}$ and $0≤ r≤ n$ is a randomly chosen value such that $gcd(r,n)=1$ . Paillier is particularly useful in applications such as electronic voting and privacy-preserving aggregation due to its additive properties. The ElGamal cryptosystem and its variants, including EC-ElGamal, are also partially homomorphic encryption (PHE) schemes that exhibit multiplicative homomorphism. In ElGamal, the component-wise product of two ciphertexts corresponds to the encryption of the product of their plaintexts. Its security is based on the Discrete Logarithm Problem (DLP). The encryption process for plaintext $m$ involves computing the ciphertext $c=(g^{r},m· h^{r})$ using a randomly selected number $r$ where $1≤ r≤ n$ . Here $g$ is the generator of a cyclic group $G$ of order $n$ , $x$ is the private key and is a random element of the group and $h=g^{x}$ is the public key [41]. Variants like EC-ElGamal extend this framework to support additive homomorphism over elliptic curves, making them suitable for specific cryptographic applications. Other noteworthy PHE schemes include the Modified RSA Encryption Algorithm (MREA) [36], which extends RSA to support additive homomorphism, and the Chen-ElGamal (CEG) scheme [52], which combines features of Paillier and ElGamal for hybrid operations. However, these schemes often face challenges related to inefficiency or ciphertext expansion, which can limit their practicality for large-scale applications. 3.2.2 Somewhat Homomorphic Encryption (SWHE) Somewhat Homomorphic Encryption (SWHE) schemes enable additive and multiplicative operations on encrypted data; however, their computational utility is inherently limited by the growth of noise in the ciphertext. Each homomorphic operation introduces a small error term, and while additions increase noise linearly, multiplications typically cause quadratic (or even exponential) noise growth. Once the accumulated noise exceeds a certain threshold, correct decryption becomes impossible. The concept of SWHE was first introduced by Gentry in 2009 with a scheme based on ideal lattices [44]. In Gentry’s construction, the noise grows so rapidly with each multiplication that only circuits of very shallow depth can be evaluated reliably. To mitigate this, Gentry proposed the technique of bootstrapping — homomorphically evaluating the decryption function to refresh ciphertexts by reducing their noise. Despite its theoretical significance, the high computational cost of bootstrapping rendered early SWHE schemes impractical for many applications. Subsequent research has focused on optimizing noise management to extend the viable depth of homomorphic computations without the need for frequent bootstrapping. The Brakerski–Gentry–Vaikuntanathan (BGV) scheme [22] introduced modulus switching, a technique that reduces the ciphertext modulus and thereby decreases noise in a linear manner. This innovation enabled leveled homomorphic encryption, where the maximum allowable circuit depth is determined by the chosen parameters. Similarly, the Fan–Vercauteren (FV) scheme [42], which is based on the Ring Learning With Errors (RLWE) problem, employs efficient modulus reduction along with relinearization techniques to control noise growth. The FV scheme has proven particularly effective for applications such as encrypted database queries and privacy-preserving analytics [20]. Further advancements were made by Brakerski’s 2012 work [21], which introduced scale-invariant techniques. These schemes decouple noise accumulation from the magnitude of the plaintext, allowing the error to grow independently of the scale of the input data, thus enabling more efficient homomorphic computations. More recently, alternative algebraic approaches have been explored to enhance both efficiency and security. For instance, a 2023 scheme based on random rank metric ideal codes [4] leverages the randomness inherent in code-based constructions to achieve competitive key and ciphertext sizes while supporting unlimited homomorphic additions and a fixed number of multiplications. In parallel, a scheme based on multivariate polynomial evaluation [38] utilizes the algebraic properties of multivariate polynomials to perform limited-depth homomorphic operations with controlled noise growth. A recent scheme [33] leverages the hardness of the sparse LPN (Learning Parities with Noise) problem combined with linear homomorphic properties. This construction supports the evaluation of bounded‐degree polynomials on encrypted data while maintaining compact ciphertext sizes. It represents a departure from traditional lattice‐based assumptions, thereby broadening the theoretical foundations for SWHE schemes. Recent research has focused on refining noise management in SWHE schemes through optimized modulus switching and relinearization operations implemented in the Residue Number System (RNS) [53]. By mapping computations into smaller rings and managing the scale more precisely, these techniques allow for tighter control over noise growth—thus supporting deeper circuit evaluations before bootstrapping becomes necessary. Such advancements have also influenced approximate schemes like CKKS [30], which share similar noise management challenges to SWHE systems. Although these advances have significantly improved the practicality of SWHE, noise management remains a central challenge. The trade-offs between computational depth, performance overhead, and security parameters continue to guide the design of modern SWHE systems, ensuring that even as new techniques are developed, careful attention must be paid to balancing noise accumulation against the desired homomorphic functionality. 3.2.3 Fully Homomorphic Encryption (FHE) Gentry’s model of homomorphic encryption relies on lattice-based cryptography. Over the past 15 years, there has been a significant surge in research and development focused on creating and enhancing homomorphic encryption schemes, resulting in a multitude of public key encryption methods capable of supporting homomorphic operations. Since the design of the first fully homomorphic encryption scheme, there have been nearly 40 public key schemes proposed, of which only one is based on coding theory, 10 are based on number theory, and the rest are based on lattices. Current research focusses not only on the construction of homomorphic encryption but also on its application and implementation to various technologies. A Fully Homomorphic Encryption (FHE) scheme is a type of encryption scheme that permits direct operations on ciphertexts, eliminating the need for decryption to perform operations. Homomorphic addition and multiplication operations are crucial to this functionality, since they constitute a functionally complete set within the realm of finite rings. Put differently, an FHE scheme enables the execution of computations on encrypted data without the need for prior decryption. We can call any encryption scheme $E$ homomorphic with respect to any function $f$ if and only if the following statement is satisfied $$ Dec(Eval(f,Enc(x),Enc(y)))=f(x,y), $$ where $x\text{ and }y$ are plain text. Homomorphic encryption schemes possess two fundamental attributes: their ability to support a maximum degree of functions and the degree to which ciphertext length expands after each homomorphic operation. The first characteristic determines the types of functions the scheme can accurately evaluate. The second characteristic relates to the increase in ciphertext length, indicating how much the bit length of the ciphertext expands following each evaluation. When the limit on bit-length expansion remains consistent regardless of the complexity of the function, it is referred to as being compact. 3.3 The evolution of FHE schemes FHE schemes can be classified in 2017 into generations based on the efficiency of computation and the techniques used to manage noise in evaluating the ciphertext [8]. This section describes the four generations of FHE schemes, the algorithms, their security assumptions, benefits and limitations. Table 3 summarises the comparison of the four generations of fully homomorphic encryption schemes. Note that code-based techniques have not been used in any of the four generations. Table 3: Comparison of Fully Homomorphic Encryption (FHE) Models with respect to the underlying hard problem, the key techniques, advantages, disadvantages and whether bootstrapping is necessary. | FHE Model | Underlying Assumption / Hard Problem | Key Techniques | Advantages | Disadvantages | Bootstrapping Requirements | | --- | --- | --- | --- | --- | --- | | First Generation: Ideal Lattice FHE (Gentry’s Scheme) | Ideal lattice problems (e.g., SVP, SSSP, BDD) | Squashing to reduce decryption circuit complexity; Bootstrapping | Foundational breakthrough; supports arbitrary computations | High circuit complexity; challenging noise management; computationally expensive | Bootstrapping enabled via squashing (adds overhead) | | First Generation: AGCD-Based FHE (DGHV Scheme) | Approximate GCD, combined with SSSP | Integer arithmetic with modular noise reduction | Conceptually simple; non-lattice alternative | Large public key size; high computational cost; less efficient in practice | Bootstrapping is required to control noise accumulation | | Second Generation: LWE/RLWE-Based FHE (BV, BGV, FV Schemes) | Learning With Errors (LWE) and its ring variant (RLWE) | Modulus switching, relinearization, batching, scale invariance | More practical and efficient; implemented in libraries such as Microsoft SEAL | Noise growth limits circuit depth without bootstrapping; parameter tuning can be complex | Leveled FHE variants may avoid bootstrapping for fixed-depth circuits; bootstrapping still used for deeper evaluations | | Second Generation: NTRU-Based FHE | NTRU assumption and circular security | Bootstrapping and modulus switching adapted to NTRU structure | Initially faster encryption operations | Vulnerabilities discovered; requires larger parameters for security; largely deprecated | Bootstrapping is incorporated, but overall robustness is lower | | Third Generation: GSW-Based FHE (Approximate Eigenvector Method) | LWE/RLWE with an approximate eigenvector approach | Bit decomposition; optimized bootstrapping with reduced error growth | Improved noise management; supports deeper circuits with less noise amplification | Increased communication cost due to larger ciphertext sizes; higher computational overhead | Bootstrapping is more efficient, reducing overall complexity | | Fourth Generation: CKKS Scheme | RLWE tailored for approximate arithmetic | Leveled encryption; plaintext embedding into complex number vectors; modulus scaling | Efficient for real-valued and approximate computations (e.g., ML applications) | Inherent approximation errors; requires careful precision management | Designed primarily as a leveled scheme (bootstrapping is optional) | 3.3.1 First Generation: FHE based on Ideal Lattice The Gentry model [44] represents the foundational framework for Fully Homomorphic Encryption (FHE), leveraging the hardness of problems in ideal lattices. The scheme operates over an ideal $I$ and its corresponding integer sublattice $L(I)⊂eq\mathbb{Z}^{m}$ . The Gentry scheme is presented as below: 1. Key Generation: - Generate an ideal lattice $L$ with the secret basis $B_{sk}$ and a public basis $B_{pk}$ . - Select parameters: Modulus $q$ , error distribution $\chi$ . 1. Encryption: - A message $m∈\mathbb{F}_{2}$ is encoded into a point $a=m+2e∈\mathbb{R}^{d}$ , where $e$ is a small error vector with coefficients sampled uniformly from $\{0,± 1\}$ . The probabilities of selecting $+1$ and $-1$ are equal. - The ciphertext $c$ is derived by translating $a$ into the parallelepiped $P(B_{pk})$ , where $B_{pk}$ is the public key basis. This translation is achieved by computing: $$ c=a-\lfloor a\cdot B_{pk}^{-1}\rceil\cdot B_{pk}. $$ Where, $\lfloor·\rceil$ denotes rounding to the nearest integer. 1. Decryption: - To decrypt, the ciphertext $c$ is first translated back into the parallelepiped $P(B_{sk})$ , where $B_{sk}$ is the secret key basis. This is done by computing: $$ a^{\prime}=c-\lfloor c\cdot B_{sk}^{-1}\rceil\cdot B_{sk}. $$ - The plaintext $m$ is then recovered as $m=a^{\prime}\mod 2$ . The public key $B_{pk}$ and secret key $B_{sk}$ serve as bases for the ideal lattice $L(I)$ . The public key $B_{pk}$ is constructed from skewed vectors, making it unsuitable as a basis for $I$ , whereas the secret key $B_{sk}$ consists of orthogonal vectors, providing a suitable basis for $I$ . Bootstrapping: The scheme is not inherently bootstrappable due to the high complexity of the decryption circuit. To address this, Gentry introduced the squashing technique, which reduces the decryption complexity by embedding additional information about the secret key into the evaluation key. The security of the scheme relies on three core mathematical problems: - Sparse Subset Sum Problem (SSSP): Given a set of integers $S=\{a_{1},...,a_{n}\}⊂eq\mathbb{Z}$ , determine whether there exists a sparse subset $I⊂eq\{1,...,n\}$ such that $\sum_{i∈ I}a_{i}=0$ . - Bounded Distance Decoding Problem (BDD): Given a lattice and a target vector that is close to the lattice, find the closest lattice vector. - Ideal Shortest Vector Problem (Ideal SVP): Find the shortest non-zero vector in an ideal lattice. Additionally, the scheme assumes circular security, which means that the encryption of the secret key does not compromise the overall security of the scheme. Limitations and Vulnerabilities: 1. Efficiency Challenges: Ideal lattice-based fully homomorphic encryption (FHE) schemes are computationally intensive due to the complex algebraic structures involved. Both the reliance on ideal lattices and the need for bootstrapping introduces significant overhead, limiting practical efficiency. 1. Principal Ideal Vulnerability: Cramer et al. [34] identified a critical vulnerability in schemes based on principal ideal lattices. They demonstrated that key-recovery attacks are feasible if there exists a quantum polynomial-time or classical $2^{n^{\frac{2}{3}-\epsilon}}$ -time algorithm for solving the Principal Ideal Problem (PIP). This vulnerability undermines the security of schemes relying on principal ideal lattices, as an adversary could exploit the structure of the lattice to recover the secret key. 3.3.2 First Generation: FHE based on AGCD Problem In 2010, van Dijk et al. [69] introduced the DGHV Fully Homomorphic Encryption (FHE) scheme, which is built on number-theoretic assumptions. The DGHV scheme marks a significant milestone in the advancement of FHE, as it was the first construction to achieve fully homomorphic encryption using basic arithmetic operations over integers. The DGHV scheme operates over the integers and relies on the hardness of the Approximate Greatest Common Divisor (AGCD) problem. The construction consists of three main algorithms: key generation, encryption, and decryption. 1. Key Generation: - The secret key is an odd random integer $p$ , sampled uniformly from a suitable range. - The public key consists of a set of integers $(x_{0},x_{1},...,x_{n})$ , where each $x_{i}$ is generated as: $$ x_{i}=p\cdot q_{i}+r_{i}. $$ Here, $q_{i}$ is a large random integer, and $r_{i}$ is a small random integer sampled from a noise distribution. The integer $x_{0}$ is chosen to be the largest odd integer in the public key. 1. Encryption: - To encrypt a message $m∈\mathbb{F}_{2}$ , the following steps are performed: 1. Select a random subset $S⊂eq\{1,2,...,n\}$ . 1. Generate a random integer $r$ from a noise distribution. 1. Compute the ciphertext $c$ as: $$ c=m+2r+2\sum_{i\in S}x_{i}\!\!\!\mod x_{0}. $$ The ciphertext $c$ is a noisy encoding of the message $m$ , where the noise terms $r$ and $r_{i}$ ensure security. 1. Decryption: - To decrypt a ciphertext $c$ , the original message $m$ is recovered as: $$ m=(c\!\!\!\mod p)\!\!\!\mod 2. $$ The decryption process relies on the fact that $p$ is the secret key and the noise terms are small relative to $p$ . Security Assumptions The security of the DGHV scheme is based on the following computational problems and assumptions: - Approximate Greatest Common Divisor (AGCD) Problem: Given a set of integers $x_{i}=p· q_{i}+r_{i}$ , where $p$ is a secret odd integer and $r_{i}$ are small noise terms, the AGCD problem requires recovering $p$ . This problem is believed to be computationally hard, even for quantum computers. - Sparse Subset Sum Problem (SSSP): The scheme also relies on the hardness of the SSSP, which involves finding a sparse subset of integers that sums to a specific value. - Circular Security: The DGHV scheme assumes circular security, meaning that the encryption of the secret key $p$ does not compromise the overall security of the scheme. Limitations and Drawbacks Despite its theoretical significance, the DGHV scheme has several practical limitations: - Large Public Key Size: The public key consists of $n+1$ integers, each of which is significantly larger than the secret key $p$ . This results in large public key size, which can be impractical for real-world applications. - High Computational Complexity: The encryption and decryption processes involve arithmetic operations on large integers, leading to high computational overheads. - Noise Growth: While the scheme supports homomorphic operations, the noise in the ciphertext grows with each operation, eventually requiring bootstrapping to maintain correctness. However, bootstrapping in the DGHV scheme is computationally expensive. 3.3.3 Second Generation: FHE based on LWE and RLWE Brakerski and Vaikuntanathan introduced two Fully Homomorphic Encryption (FHE) schemes, marking the beginning of the second generation of FHE. These schemes are based on the Learning With Errors (LWE) problem [24] and the Ring Learning With Errors (RLWE) problem [23]. The symmetric scheme based on LWE, referred to as the BV scheme, and its RLWE-based counterpart, the BGV scheme, are foundational to modern FHE. Below, we provide a detailed description of these schemes, their algorithms, and their key innovations. BV Scheme: LWE-Based FHE The BV scheme is based on the LWE problem, which involves solving linear equations perturbed by small noise. The scheme consists of the following algorithms: 1. Encryption: - For a message $m∈\mathbb{F}_{2}$ , the ciphertext $c$ is represented as: $$ c=(a,b)=\left(a,\langle a,s\rangle+2e+m\right), $$ where: - $a$ is a random vector in $\mathbb{Z}_{q}^{n}$ , - $s$ is the secret key, a random vector in $\mathbb{Z}_{q}^{n}$ , - $e$ is a small error term drawn from an error distribution $\chi$ , - $\langle a,s\rangle$ denotes the inner product of $a$ and $s$ . 1. Decryption: - The decryption process computes the plaintext as: $$ m=\left(b-\langle a,s\rangle\!\!\!\mod q\right)\!\!\!\mod 2. $$ Decryption succeeds if the error term $e$ is sufficiently small, specifically when $|e|<q/4$ . The BV scheme introduced two critical techniques to enable fully homomorphic encryption: - Relinearization (Key-Switching): This technique reduces the size of ciphertexts after homomorphic multiplication. Specifically, it reduces the ciphertext size from $\mathcal{O}(n^{2})$ to $\mathcal{O}(n)$ , where $n$ is the dimension of the LWE problem. - Dimension-Modulus Reduction (Modulus Switching): This technique transforms a ciphertext $c^{\prime}\!\!\!\mod q$ into a ciphertext $c\!\!\!\mod p$ , where $p\ll q$ . Modulus switching reduces the noise growth during homomorphic operations, enabling deeper computations without bootstrapping. By eliminating the need for Gentry’s squashing technique as well as the reliance on the Sparse Subset Sum Problem (SSSP), the BV scheme becomes more efficient and practical. BGV Scheme: RLWE-Based FHE The BGV scheme extends the BV framework to the Ring Learning With Errors (RLWE) setting, offering improved efficiency and scalability. The scheme operates over the ring $R=\mathbb{Z}[x]/\langle x^{d}+1\rangle$ , where $d=2^{M}$ for some integer $M$ . The BGV scheme is defined as follows: 1. Key Generation: - A secret key $sk=(1,s)∈ R_{q}^{2}$ is generated, where $s$ is a small random element sampled from the error distribution $\chi$ . - A public key $pk=(a,b)$ is computed as: $$ b=a\cdot s+2e\!\!\!\mod q, $$ where $a$ is a random element in $R_{q}$ , and $e$ is a small error term. 1. Encryption: - For a message $\mu∈\mathbb{F}_{2}$ , the message is encoded as $m=(\mu,0)∈ R_{q}^{2}$ . - The ciphertext $c$ is computed as: $$ c=m+2(e_{0},e_{1})+a\cdot r, $$ where $r,e_{0},e_{1}$ are small random elements sampled from $\chi$ . 1. Decryption: - The decryption process computes the inner product $\langle c,s\rangle$ and outputs the plaintext as: $$ m=\langle c,s\rangle\!\!\!\mod 2. $$ Brakerski introduced a scale-invariant variant of the BGV scheme [21], achieved by scaling down both the ciphertext and the error by a factor of $q$ , where $q$ is the ciphertext modulus, thus reducing the noise growth during homomorphic multiplications from exponential to linear. This innovation replaces the traditional modulus switching technique, further improving the scheme’s efficiency. FV Scheme: Optimized RLWE-Based FHE The FV scheme, an optimized version of the BGV scheme, was introduced by Fan and Vercauteren [42]. It is designed for efficient modular arithmetic on encrypted integers and is implemented in Microsoft’s SEAL library [2]. The FV scheme operates as follows: 1. Key Generation: - The secret key $sk=s$ is sampled from the error distribution $\chi$ . - The public key $pk=(p_{0},p_{1})$ is computed as: $$ p_{0}=-(a\cdot s+e)\!\!\!\mod q,\quad p_{1}=a, $$ where $a$ is a random element in $R_{q}$ , and $e$ is a small error term. 1. Encryption: - For a message $m∈ R_{p}$ , the ciphertext $c=(c_{0},c_{1})$ is computed as: $$ c_{0}=(p_{0}\cdot u+e_{1}+\Delta m)\!\!\!\mod q,\quad c_{1}=(p_{1}\cdot u+e_{2% })\!\!\!\mod q, $$ where $u,e_{1},e_{2}$ are small random elements sampled from $\chi$ , and $\Delta=\lfloor q/p\rfloor$ . 1. Decryption: - The decryption process computes: $$ m=\left\lfloor\frac{p\cdot(c_{0}+c_{1}\cdot s)\mod q}{q}\right\rfloor\!\!\!% \mod p. $$ The BGV and FV schemes have been further enhanced through techniques such as batching, modulus switching, and improved bootstrapping. These optimizations enable their integration into practical cryptographic libraries like HElib [48] and SEAL [2], making them suitable for applications such as privacy-preserving machine learning and secure computation. 3.3.4 Second Generation: FHE based on NTRU The NTRU encryption scheme, introduced by Hoffstein et al. in 1998 [50], is a lattice-based cryptosystem that has played a significant role in the development of post-quantum cryptography. The scheme was initially proposed with a provisional patent, which was later granted in 2000 [51]. NTRU is often referred to as the LTV scheme in the literature [56], and it incorporates techniques such as bootstrapping and modulus switching to achieve its functionality. The NTRU scheme operates over the ring $R=\mathbb{Z}[x]/\langle x^{d}+1\rangle$ , where $d=2^{m}$ for some integer $m$ . The scheme consists of three main algorithms: key generation, encryption, and decryption. 1. Key Generation: - Let $\chi$ be a bounded distribution over the ring $R$ . Sample two small random polynomials $f^{\prime}$ and $g$ from $\chi$ . - Compute the secret key polynomial $f=2f^{\prime}+1$ , ensuring that $f\equiv 1\!\!\mod 2$ and is invertible in $R_{q}=\mathbb{Z}_{q}[x]/\langle x^{d}+1\rangle$ . - Compute the public key polynomial $h=2g· f^{-1}\!\!\!\mod q$ . - The key pair is $(pk,sk)=(h,f)$ . 1. Encryption: - For a binary message $m∈\{0,1\}$ , sample small random polynomials $s$ and $e$ from $\chi$ . - Compute the ciphertext $c$ as: $$ c=h\cdot s+2e+m\!\!\!\mod q. $$ Here, $h$ is the public key, and $s$ and $e$ are small random noise terms. 1. Decryption: - To decrypt the ciphertext $c$ , compute: $$ m=(f\cdot c\!\!\!\mod q)\!\!\!\mod 2. $$ The correctness of decryption relies on the fact that $f$ is the secret key and that the noise terms $s$ and $e$ are small. Security Assumptions The security of the NTRU scheme is based on the following computational problems and assumptions: - Circular Security: The scheme assumes that the encryption of the secret key does not compromise the overall security of the system. - Ring Learning With Errors (RLWE) Problem: The hardness of solving the RLWE problem over the ring $R$ is a fundamental assumption for the security of NTRU. - Decisional Small Polynomial Ratio (DSPR) Problem: This problem involves distinguishing between a random polynomial and a ratio of two small polynomials in the ring $R$ . The DSPR problem is believed to be computationally hard, even for quantum computers. Limitations and Vulnerabilities Despite its initial promise, the NTRU scheme has several limitations and vulnerabilities that have impacted its practical adoption: - Parameter Sizing: To achieve security against known attacks, the parameters of NTRU-based schemes must be significantly larger than those initially proposed. This results in larger key sizes and reduced efficiency. - Error Rates: Research by Lepoint and Naehrig [54] has shown that RLWE-based schemes exhibit lower error rates compared to NTRU-based schemes. This makes RLWE-based schemes more robust for practical applications. - Attacks: Numerous attacks have been documented against NTRU-based schemes, including lattice reduction attacks and subfield attacks. While parameters have been improved to mitigate these attacks, the resulting schemes are less efficient than their RLWE counterparts. Due to the aforementioned limitations, NTRU-based schemes are no longer widely used or supported by cryptographic libraries. The efficiency and security advantages of RLWE-based schemes have made them the preferred choice for lattice-based cryptography in both academic research and practical implementations. 3.3.5 Third Generation: FHE Based on LWE and RLWE The third generation of homomorphic encryption introduced a novel approach known as the approximate eigenvector method [45]. This method significantly advances the field by eliminating the need for key and modulus switching techniques, which were critical in earlier schemes such as BGV and FV. A key advantage of this approach is its ability to control error growth during homomorphic multiplications, limiting it to a small polynomial factor. Specifically, when multiplying $l$ ciphertexts with the same error level, the final error increases by a factor of $l·\text{poly}(n)$ , where $n$ represents the dimension of the encryption scheme or lattice. This is a substantial improvement over previous schemes, where error growth was quasi-polynomial. This third-generation scheme is commonly referred to as the GSW scheme, named after its inventors Gentry, Sahai, and Waters. Below, we provide a detailed description of the GSW scheme, its algorithms, and its optimizations. GSW Scheme: Approximate Eigenvector Method The GSW scheme is based on the Learning With Errors (LWE) problem and employs an approximate eigenvector approach to achieve fully homomorphic encryption. The scheme consists of the following algorithms: 1. Key Generation: - The secret key $s$ is a vector of the form $s=(1,s_{2},...,s_{n})∈\mathbb{Z}_{q}^{n}$ , where each $s_{i}$ is randomly selected. - The public key $A∈\mathbb{Z}_{q}^{n× n}$ is constructed such that $A· s≈ 0$ . This ensures that the product of $A$ and the secret key $s$ results in a small error term. 1. Encryption: - For a message $m∈\mathbb{Z}_{q}$ , the ciphertext $C$ is constructed as: $$ C=mI_{n}+RA, $$ where: - $I_{n}$ is the $n× n$ identity matrix, - $R$ is a random binary matrix of dimension $n× n$ , - $A$ is the public key. The ciphertext $C$ is a noisy encoding of the message $m$ , where the noise is introduced by the matrix $R$ . 1. Decryption: - To decrypt the ciphertext $C$ , compute: $$ C\cdot s=mI_{n}s+RAs\approx mI_{n}s+Re\approx mI_{n}s, $$ where $e$ is a small error term. Since $s_{1}=1$ , the first element of the vector $C· s$ approximates $m$ . - The decrypted message is obtained as: $$ m\approx(C\cdot s)_{1}. $$ Homomorphic Multiplication and Bootstrapping The GSW scheme employs bit decomposition for homomorphic multiplication allowing for efficient computation of products of ciphertexts. However, the scheme has some limitations: - High Communication Costs: The ciphertext size in the GSW scheme is relatively large compared to the plaintext, leading to increased communication overhead. - Computational Complexity: The scheme involves complex matrix operations, which can be computationally intensive. To address these limitations, several optimizations have been proposed: - Arithmetic Bootstrapping: Alperin-Sheriff and Peikert (AP) [11] introduced a bootstrapping algorithm that treats decryption as an arithmetic function rather than a Boolean circuit, significantly reducing computational complexity . - Homomorphic Matrix Operations: Hiromasa et al. [49] extended the GSW scheme to support homomorphic matrix operations, further enhancing its applicability. - Programmable Bootstrapping (PBS): Ducas and Micciancio [39] introduced the FHEW scheme, which incorporates the AP bootstrapping technique and enables programmable bootstrapping. This allows for the homomorphic evaluation of arbitrary functions, including the NAND operation, using lookup tables. In addition to the GSW scheme, the third generation of homomorphic encryption includes three distinct schemes based on the torus: - TLWE (Torus Learning With Errors): Generalizes the LWE problem to the torus $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ . - TRLWE (Torus Ring Learning With Errors): Extends the RLWE problem to the torus, enabling encryption of plaintexts in the ring of integer polynomials $R$ . - TRGSW (Torus Ring GSW): A ring variant of the GSW scheme on the torus, which supports homomorphic operations on encrypted data. The TRLWE scheme operates over the ring $R=\mathbb{Z}[x]/\langle x^{d}+1\rangle$ , where $d=2^{M}$ . The message space is defined as $T=R[x]/\langle x^{d}+1\rangle\mod 1$ , and the scheme is constructed as follows: 1. Key Generation: - For a security parameter $\lambda$ , generate a small secret key $s∈ R_{2}^{n}$ , where $R_{2}=\mathbb{F}_{2}[x]/\langle x^{d}+1\rangle$ . 1. Encryption: - For a message $m∈\mathbb{T}$ , sample a random mask $a$ uniformly from $\mathbb{T}^{n}$ and a small error $e$ from a bounded distribution $\chi$ . - Compute the ciphertext $c$ as: $$ c=(a,s\cdot a+m+e)\in\mathbb{T}^{n}\times\mathbb{T}. $$ 1. Decryption: - Compute the phase function $\psi_{s}(c)=b-s· a$ , where $c=(a,b)$ . - The decrypted message is obtained by rounding $\psi_{s}(c)$ to the nearest point in the message space $M⊂eq\mathbb{T}$ . Chillotti et al. [32] introduced several optimizations for torus-based FHE schemes, including the ability to generate fresh ciphertexts by linearly combining existing ones. However, non-linear operations remain challenging due to the limitations of TLWE. To address this, the TRGSW scheme was developed, which supports generalized scale-invariant operations and enables efficient switching between TRLWE and TLWE. 3.3.6 Fourth Generation: FHE based on LWE and RLWE In 2017, Cheon et al. introduced a groundbreaking collection of Fully Homomorphic Encryption (FHE) schemes [30], which are specifically designed for approximate arithmetic on real and complex numbers. This scheme, originally named HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers), is now commonly referred to as the CKKS scheme, named after its authors. The CKKS scheme provides a leveled homomorphic encryption framework, enabling efficient computations on encrypted data while maintaining approximate correctness. Additionally, the authors released an open-source library to facilitate the implementation and deployment of this scheme. The CKKS scheme operates over the ring $R=\mathbb{Z}[x]/\langle x^{d}+1\rangle$ , where $d=2^{M}$ for some integer $M$ . The scheme is designed to handle approximate arithmetic, making it particularly suitable for applications involving real or complex numbers, such as machine learning and scientific computing. The CKKS scheme consists of the following algorithms: 1. Key Generation: - Let $p$ be a base, $q_{0}$ a modulus, and $L$ a selected level. Define $q_{l}=p_{l}· q_{0}$ for $l=1,...,L$ . - Let $\chi$ be a $B$ -bounded distribution, and let $DG(\sigma^{2})$ denote a vectorial discrete Gaussian distribution over $\mathbb{Z}^{d}$ with variance $\sigma^{2}$ . Let $ZO(\rho)$ denote a distribution over $\{-1,0,1\}^{d}$ with $0<\rho<1$ . - Generate the secret key $sk=(1,s)$ , where $s$ is sampled from $\chi$ . - Sample a random value $a∈ R_{q_{L}}$ and compute $b=-a· s+e\mod q_{L}$ , where $e$ is sampled from $DG(\sigma^{2})$ . - Sample $a^{\prime}∈ R_{t· q_{L}}$ and $e^{\prime}∈ DG(\sigma^{2})$ ; compute $b^{\prime}=-a· s+e^{\prime}+t· s^{\prime}\!\!\!\mod t· q_{L}$ . - Output the secret key $sk=(1,s)$ , the public key $pk=(b,a)$ , and the evaluation key $evk=(b^{\prime},a^{\prime})$ . 1. Encryption: - For a message $m∈ R$ , sample random values $v∈ ZO(1/2)$ and $e_{0},e_{1}∈ DG(\sigma^{2})$ . - Compute the ciphertext $c=(\beta,\alpha)$ , where: $$ \beta=v\cdot b+m+e_{0}\!\!\!\mod q_{l},\quad\alpha=v\cdot a+e_{1}\!\!\!\mod q_% {l}. $$ The ciphertext $c$ is a noisy encoding of the message $m$ , where the noise terms $e_{0}$ and $e_{1}$ ensure security. 1. Decryption: - To decrypt the ciphertext $c=(\beta,\alpha)$ , compute: $$ m=\langle c,sk\rangle\!\!\!\mod q_{l}=\beta+\alpha\cdot s\!\!\!\mod q_{l}. $$ The decrypted message $m$ is an approximation of the original plaintext, with the error introduced during encryption. A notable feature of the CKKS scheme is its ability to encode messages as elements in the extension field $\mathbb{C}$ , which corresponds to the complex numbers. Specifically: - The message space is defined as $S=R[x]/\langle x^{d}+1\rangle$ , where the roots of the polynomial $x^{d}+1$ are the complex primitive roots of unity in $\mathbb{C}$ . - A message $m∈ S$ can be embedded into a vector of complex numbers by evaluating it at these roots. This allows for efficient encoding and decoding of real and complex numbers, making the CKKS scheme particularly suitable for applications involving approximate arithmetic. The CKKS scheme offers several advantages over previous FHE schemes: - Approximate Arithmetic: The scheme is specifically designed for approximate computations, making it ideal for applications such as machine learning, where exact precision is not required. - Efficient Encoding: The ability to encode messages as complex numbers allows for efficient representation of real and complex data, reducing the computational overhead associated with homomorphic operations. - Leveled Homomorphism: The CKKS scheme supports leveled homomorphic encryption, enabling a predetermined number of homomorphic operations without the need for bootstrapping. This makes it more efficient for practical applications. 3.4 Security Assumptions of current FHE schemes The security of lattice-based Fully Homomorphic Encryption (FHE) schemes relies on the hardness of several well-studied computational problems in lattice theory. These problems form the foundation of the cryptographic assumptions underlying the security of LWE (Learning With Errors) and RLWE (Ring Learning With Errors)-based schemes. Below, we provide a brief analysis of the various problems and their relevance to FHE. The reader can find more details about the NP-Hard problems in [55]. 3.4.1 Shortest Vector Problem (SVP) The Shortest Vector Problem (SVP) is a fundamental problem in lattice theory and serves as the basis for many lattice-based cryptographic schemes. Given a lattice $L$ , the SVP involves finding the shortest non-zero vector in $L$ . Several variants of the SVP are used in cryptographic constructions: - $\gamma$ -Approximate Shortest Vector Problem ( $SVP_{\gamma}$ ): - Given a lattice $L$ and an approximation factor $\gamma≥ 1$ , the goal is to find a non-zero vector $v∈ L$ such that: $$ \|v\|\leq\gamma\cdot\lambda_{1}(L), $$ where $\lambda_{1}(L)$ is the length of the shortest non-zero vector in $L$ . - Decisional Shortest Vector Problem ( $GapSVP_{\gamma,r}$ ): - Given a lattice $L$ , an approximation factor $\gamma≥ 1$ , and a bound $r>0$ , the goal is to decide whether: $$ \lambda_{1}(L)\leq r\quad\text{or}\quad\lambda_{1}(L)\geq\gamma\cdot r. $$ - $\gamma$ -Unique Shortest Vector Problem ( $uSVP_{\gamma}$ ): - Given a lattice $L$ and an approximation factor $\gamma≥ 1$ , the goal is to find the shortest non-zero vector $v∈ L$ under the condition that: $$ \lambda_{1}(L)<\gamma\cdot\lambda_{2}(L), $$ where $\lambda_{2}(L)$ is the length of the second shortest vector in $L$ . The hardness of these problems is crucial for the security of lattice-based FHE schemes. If the SVP is solvable, then the decisional variant $GapSVP_{\gamma,r}$ is also solvable. 3.4.2 Closest Vector Problem (CVP) The Closest Vector Problem (CVP) is a generalization of the SVP, where the goal is to find the lattice vector closest to a given target vector $t∈\mathbb{R}^{n}$ . The CVP and its variants are defined as follows: - $\gamma$ -Approximate Closest Vector Problem ( $CVP_{\gamma}$ ): - Given a lattice $L$ , a target vector $t∈\mathbb{R}^{n}$ , and an approximation factor $\gamma≥ 1$ , the goal is to find a vector $v∈ L$ such that: $$ \text{dist}(t,v)\leq\gamma\cdot\text{dist}(t,L), $$ where $\text{dist}(t,L)$ is the distance between $t$ and the lattice $L$ . - Decisional Closest Vector Problem ( $DCVP_{\gamma,r}$ ): - Given a lattice $L$ , a target vector $t∈\mathbb{R}^{n}$ , an approximation factor $\gamma≥ 1$ , and a bound $r>0$ , the goal is to decide whether: $$ \text{dist}(t,L)\leq r\quad\text{or}\quad\text{dist}(t,L)\geq\gamma\cdot r. $$ - $\alpha$ -Bounded Distance Decoding ( $BDD_{\alpha}$ ): - Given a lattice $L$ , a target vector $t∈\mathbb{R}^{n}$ , and a parameter $\alpha≤ 1$ , the goal is to find the closest lattice vector $v∈ L$ under the condition that: $$ \text{dist}(t,L)<\alpha\cdot\lambda_{1}(L). $$ The CVP and its variants are closely related to the SVP and are used in the security analysis of lattice-based cryptographic schemes. 3.4.3 Shortest Integer Solution (SIS) Problem The Shortest Integer Solution (SIS) problem is another fundamental problem in lattice-based cryptography. It is defined as follows: - SIS Problem ( $SIS_{q,m,\beta}$ ): - Given a matrix $A∈\mathbb{Z}_{q}^{m× n}$ and a bound $\beta<q$ , the goal is to find a non-zero integer vector $x∈\mathbb{Z}^{m}$ such that: $$ xA\equiv 0\pmod{q}\quad\text{and}\quad\|x\|\leq\beta. $$ The SIS problem is equivalent to finding a short vector in the scaled dual lattice $L_{q}^{\perp}(A)$ . It is used in the construction of cryptographic primitives such as digital signatures and hash functions. 3.4.4 Learning With Errors (LWE) and Ring-LWE The Learning With Errors (LWE) problem and its ring variant (Ring-LWE) are central to the security of many lattice-based FHE schemes. These problems are defined as follows: - LWE Problem: - Given a matrix $A∈\mathbb{Z}_{q}^{m× n}$ , a secret vector $s∈\mathbb{Z}_{q}^{n}$ , and a noise vector $e∈\mathbb{Z}_{q}^{m}$ sampled from a discrete Gaussian distribution, the LWE instance is: $$ b=As+e\pmod{q}. $$ The goal is to recover the secret vector $s$ given $(A,b)$ . - Ring-LWE Problem: - Given a polynomial ring $R_{q}=\mathbb{Z}[x]/\langle f(x)\rangle$ , a secret polynomial $s(x)∈ R_{q}$ , and a noise polynomial $e(x)∈ R_{q}$ , the Ring-LWE instance is: $$ b(x)=a(x)s(x)+e(x)\pmod{f(x)}, $$ where $a(x)∈ R_{q}$ is a random polynomial. The goal is to recover the secret polynomial $s(x)$ given $(a(x),b(x))$ . The security of LWE and Ring-LWE-based schemes relies on the hardness of solving these problems using lattice reduction algorithms. However, as demonstrated by Albrecht et al. [27], there is no universal attack that can efficiently solve all instances of these problems. The effectiveness of lattice reduction attacks depends on the choice of parameters, such as the modulus $q$ , the dimension $n$ , and the error distribution. For Ring-LWE, the security analysis is similar to that of LWE, but with additional considerations due to the ring structure. According to the Homomorphic Encryption Security Standard, selecting an appropriate error distribution ensures that there are no superior attacks on Ring-LWE compared to LWE. However, the error distribution must be sufficiently spread to maintain security. The security of lattice-based FHE schemes is grounded in the hardness of problems such as SVP, CVP, SIS, LWE, and Ring-LWE. These problems are believed to be resistant to quantum attacks, making lattice-based cryptography a promising candidate for post-quantum security. While lattice reduction algorithms pose a potential threat, careful parameter selection and error distribution management can mitigate these risks, ensuring the robustness of lattice-based cryptographic schemes. Lattice-based homomorphic encryption (HE) schemes, like those based on Learning With Errors (RLWE) and NTRU, have made notable strides in efficiency and security. However, they still face challenges such as large ciphertext expansion, high computational overhead, and susceptibility to quantum attacks. Concerns about their long-term security arise from their reliance on lattice problems. To address these limitations, researchers are turning to alternative hardness assumptions. Code-based cryptography, known for its strength in post-quantum encryption, offers potential benefits for HE, including robust security and efficiency. Exploring code-based HE schemes may help overcome the shortcomings of lattice approaches while maintaining resistance to quantum threats. 4 Code-Based Cryptography Code-based cryptography relies on the NP-hard problem of indistigushabilty and decoding a random linear code and is a promising option for post-quantum cryptography. Code-based cryptosystems work by choosing the private key as a linear code $C$ , which can efficiently correct a predetermined number of errors. The public key, denoted as $C^{\prime}$ , is a disguised version of the linear code and is designed so that it will appear random and not reveal the private key to an observer who doesn’t have access to $C$ . With access to the public key $C^{\prime}$ , a sender can encrypt their message and potentially add errors. An attacker who sees the ciphertext, will need to decode it to recover the message. As the ciphertext is a random codeword, there is no polynomial-time algorithm to do this. The receiver who has the private key $C$ can transform the ciphertext into a codeword of $C$ , which can be efficiently decoded to retrieve the message. In this section we first introduce the NP-hard problems on which code-based cryptography is based. We will then introduce existing code-based ciphers. 4.1 NP-Hard Problems in Coding Theory There are two categories of NP-hard problems in this area. The first is around the difficulty of decoding a random linear code and the second is around the difficulty of proving equivalence of codes. While the NP-hard problems in both categories are defined over the Hamming metric, we also present the analogous problems in the rank metric. 4.1.1 The Decoding Problems in Coding Theory There are three variations of decoding problems, each of which is described below: Decoding Problem (DP): Let $\mathbb{F}_{q}$ be a finite field and consider a code defined by a generator matrix $$ G\in\mathbb{F}_{q}^{k\times n}. $$ Given a received vector $r∈\mathbb{F}_{q}^{n}$ and an integer $t$ (representing an error weight threshold), the task is to decide whether there exists a message $m∈\mathbb{F}_{q}^{k}$ and an error vector $e∈\mathbb{F}_{q}^{n}$ with $$ \operatorname{wt}(e)\leq t,\;\text{such that,}\;\;r=mG+e. $$ This problem is fundamental in algebraic coding theory. Syndrome Decoding Problem (SDP): In the syndrome formulation, one is given a parity-check matrix $$ H\in\mathbb{F}_{q}^{(n-k)\times n}, $$ a syndrome $s∈\mathbb{F}_{q}^{n-k}$ , and an integer $t$ . The goal is to find an error vector $e∈\mathbb{F}_{q}^{n}$ satisfying $$ eH^{\top}=s\quad\text{and}\quad\operatorname{wt}(e)\leq t. $$ By converting $G$ into systematic form and obtaining the corresponding $H$ , the DP can be recast as an SDP, and conversely, one can recover a DP instance from an SDP instance. Given Weight Codeword Problem (GWCP): Given a parity-check matrix $H$ and an integer $w$ , the problem asks whether there exists a codeword $$ c\in\mathbb{F}_{q}^{n}, $$ such that $$ cH^{\top}=0\quad\text{and}\quad\operatorname{wt}(c)=w. $$ By augmenting the generator matrix with the received vector, one shows that GWCP is equivalent to the DP (and hence to the SDP). 4.1.2 Code Equivalence Problems Code equivalence problem is known as the indistinguishability of a random linear code. Similar to decoding problems, there are three varieties of code equivalence problems. Permutation Equivalence Problem (PEP): Given two generator matrices $$ G,\,G^{\prime}\in\mathbb{F}_{q}^{k\times n}, $$ find a permutation $\phi∈ S_{n}$ (the symmetric group on $n$ elements) such that $$ \phi(\langle G\rangle)=\langle G^{\prime}\rangle. $$ This problem is a special case of the broader linear equivalence issues. Linear Equivalence Problem (LEP): For $G,\,G^{\prime}∈\mathbb{F}_{q}^{k× n}$ , the goal is to find a mapping $$ \phi\in(\mathbb{F}_{q}^{\star})^{n}\rtimes S_{n}, $$ that sends the code generated by $G$ to that generated by $G^{\prime}$ . Subcode Equivalence and the Permuted Kernel Problem (PKP/SEP): - PKP: Given $G∈\mathbb{F}_{q}^{k× n}$ and another matrix $H^{\prime}$ (typically related to a subcode), find a permutation matrix $P$ such that $$ H^{\prime}(GP)^{\top}=0. $$ - SEP: Reformulated as the subcode equivalence problem, one seeks a permutation matrix $P$ such that $$ \langle G^{\prime}\rangle\subset\langle GP\rangle. $$ A relaxed version of PKP requires only finding a non-zero codeword (i.e. a subcode of dimension 1) that meets the equivalence condition. 4.1.3 Rank-Metric Analogues and the MinRank Problem There are analogues to the problems above with respect to the rank metric. Rank Syndrome Decoding Problem (Rank SDP): In the rank metric, where matrices are considered over $\mathbb{F}_{q^{m}}$ , the problem is analogous to the classical SDP. Given a parity-check matrix $$ H\in\mathbb{F}_{q^{m}}^{(n-k)\times n}, $$ a syndrome $$ s\in\mathbb{F}_{q^{m}}^{n-k}, $$ and an integer $t$ , the task is to find an error vector $$ e\in\mathbb{F}_{q^{m}}^{n}, $$ with rank weight $$ \operatorname{wt}_{R}(e)\leq t, $$ satisfying $$ eH^{\top}=s. $$ While reductions from the classical SDP suggest its hardness, the NP-completeness of the Rank SDP remains an open question. MinRank Problem: For $\mathbb{F}_{q}$ -linear (matrix) codes, the MinRank problem is stated as follows. Given matrices $$ G_{1},\dots,G_{k}\in\mathbb{F}_{q}^{m\times n}, $$ an integer $t$ , and a matrix $R∈\mathbb{F}_{q}^{m× n}$ , the goal is to find a matrix $$ E\in\mathbb{F}_{q}^{m\times n} $$ of rank at most $t$ , and scalars $\lambda_{1},...,\lambda_{k}∈\mathbb{F}_{q}$ , such that $$ R=\lambda_{1}G_{1}+\cdots+\lambda_{k}G_{k}+E. $$ This problem, which is equivalent to the decoding problem in the rank metric for matrix codes, is known to be NP-complete. In summary, the Decoding Problem (DP), the Syndrome Decoding Problem (SDP), and the Given Weight Codeword Problem (GWCP) are shown to be equivalent formulations central to algebraic coding theory. These problems underpin many cryptographic constructions based on error-correcting codes. Additionally, several code equivalence problems (including PEP, LEP, and SEP/PKP) extend these ideas, while the rank-metric analogues such as the Rank SDP and the NP-complete MinRank problem further illustrate the complexity landscape in coding theory. 4.2 Frameworks in Code-Based Cryptography This section describes the three existing cryptosystems built on NP-hard problems in coding theory. We will discuss the McEleice framework, the Niederiter Framework and two variants of the Alekhnovich Framework here. In addition to these, there are the Quasi-cyclic framework [3], Augot-Finiasz (AF) cryptosystem [14] and the GPT cryptosystem [43] which are widely in use and are derivative variations of the above three frameworks. Details of all the code-based frameworks can be found in [70]. 4.2.1 McEliece Framework McEliece [58] proposed a public key cryptosystem using a linear code, for example, a binary Goppa code. The secret key is chosen as one of the many possible generators of a chosen linear code. The public key is a new matrix created by adding randomness and permuting the generator. The new matrix looks like a random matrix and will not leak information about the actual generator. A sender will multiply this random matrix with the plaintext and the product will be added to a random binary error vector whose weight will be less than the error-correcting bound of the chosen linear code. The resulting ciphertext is sent back to the owner of the secret key. To decode the ciphertext, the receiver first performs the decoding algorithm to remove the error vector added in the encoding, then performs the inverse of the operations done to generate the random matrix and retrieve the original message. Without knowledge of the generator and the random transformation, an attacker observing the ciphertext will find it computationally hard to find the message. The McEliece framework is described in Table 4. The parameters of the framework are $(q,n,k,t)$ where $q$ is a prime or prime power, $n$ the length of the codeword, $k$ the length of the plaintext and $t$ the error correcting capacity of the code. $GL_{k}$ is the general linear group of order $k$ . Table 4: The McEliece Cryptosystem Framework, giving the processes of key generation, encryption and decryption. | Transmitter (Key Owner) | Communication | Sender (Plaintext owner) | | --- | --- | --- | | Key Generation | | | | 1. Select linear code $C⊂eq\mathbb{F}_{q}^{n}$ with parameters $[n,k,t]$ | | | | 2. Choose $k× n$ generator matrix $\mathbf{G}$ for $C$ | | | | 3. Generate a random $k× k$ invertible matrix $\mathbf{S}∈\mathrm{GL}_{k}(\mathbb{F}_{q})$ | | | | 4. Generate a random $n× n$ permutation matrix $\mathbf{P}$ | | | | 5. Compute the Public Key: $\mathbf{G^{\prime}}=\mathbf{SGP}$ | | | | Private Key: $(\mathbf{G},\mathbf{S},\mathbf{P})$ | $\xrightarrow{\text{Public Key }(t,\mathbf{G^{\prime}})}$ | Store public key $(t,\mathbf{G^{\prime}})$ | | Encryption | | | | 1. Encode message $\mathbf{m}∈\mathbb{F}_{q}^{k}$ | | | | 2. Generate error vector $\mathbf{e}∈\mathbb{F}_{q}^{n}$ with $\mathrm{wt}(\mathbf{e})≤ t$ | | | | 3. Compute ciphertext: $\mathbf{c}=\mathbf{mG^{\prime}}+\mathbf{e}$ | | | | $\xleftarrow{\text{Ciphertext }\mathbf{c}}$ | | | | Decryption | | | | 1. Compute $\mathbf{cP}^{-1}=\mathbf{mSG}+\mathbf{eP}^{-1}$ | | | | 2. Decode using the Private Key $C$ to recover $\mathbf{mS}$ | | | | 3. Compute $\mathbf{m}=\mathbf{mS}·\mathbf{S}^{-1}$ | | | 4.2.2 Niederreiter Framework The Niederreiter framework [60] uses the parity-check matrix instead of the generator matrix, resulting in an equivalently secure system. Niederreiter originally proposed using GRS codes as secret codes. In this scheme the plaintext is encoded as a vector of length $n$ and weight less than or equal to the error correcting capacity of the code. The general Niederreiter framework with a linear code is presented in Table 5. Table 5: The Niederreiter Cryptosystem Framework giving the processes of key generation, encryption and decryption. | Transmitter (Key Owner) | Communication | Sender(Plaintext owner) | | --- | --- | --- | | Key Generation | | | | 1. Select a linear code $C⊂eq\mathbb{F}_{q}^{n}$ with parameters $[n,k,t]$ | | | | 2. Choose an $(n-k)× n$ parity-check matrix $\mathbf{H}$ for $C$ | | | | 3. Generate a random invertible matrix $\mathbf{S}∈\mathrm{GL}_{n-k}(\mathbb{F}_{q})$ | | | | 4. Generate a random $n× n$ permutation matrix $\mathbf{P}$ | | | | 5. Compute the Public Key: $\mathbf{H^{\prime}}=\mathbf{SHP}$ | | | | Private Key: $(\mathbf{H},\mathbf{S},\mathbf{P})$ | $\xrightarrow{\text{Public Key }(t,\mathbf{H^{\prime}})}$ | Store public key $(t,\mathbf{H^{\prime}})$ | | Encryption | | | | 1. Encode message $\mathbf{m}∈\mathbb{F}_{q}^{n}$ with $\mathrm{wt}(\mathbf{m})≤ t$ | | | | 2. Compute ciphertext: $\mathbf{c}^{T}=\mathbf{H^{\prime}}\mathbf{m}^{T}$ | | | | $\xleftarrow{\text{Ciphertext }\mathbf{c}}$ | | | | Decryption | | | | 1. Compute $\mathbf{S}^{-1}\mathbf{c}^{T}=\mathbf{HP}\mathbf{m}^{T}$ | | | | 2. Use the decoding algorithm of $C$ to recover $\mathbf{P}\mathbf{m}^{T}$ | | | | 3. Compute $\mathbf{m}^{T}=\mathbf{P}^{-1}(\mathbf{P}\mathbf{m}^{T})$ | | | 4.2.3 Alekhnovich’s Cryptosystem Alekhnovich’s cryptosystem [9] is the first code-based cryptosystem with provable security proof. It relies solely on the decoding problem and lays the foundations for modern code-based cryptography, where researchers attempt to construct code-based cryptosystems with a provable reduction to the problem of distinguishing a random codeword from a uniform string. There are two variants of this cryptosystem, both relying on the hard problem of distinguishing a random vector from an erroneous codeword of the code $C$ . We present the first (encrypts one bit at a time) and second (encrypts a vector of bits at a time) variants of the Alkehnovich cryptosystem in Tables 6 and 7. In both variants $n$ is the length of the ciphertext, $t$ the error-correcting bound of $C$ and $k$ the number of rows in the generator matrix of $C$ . Table 6: The Alekhnovich First Variant Framework, giving the processes of key generation, encryption and decryption. | Transmitter (Key Owner) | Communication | Sender (Plaintext owner) | | --- | --- | --- | | Key Generation | | | | 1. Select parameters: $t∈ o(\sqrt{n})$ | | | | 2. Choose random matrix $\mathbf{A}∈\mathbb{F}_{2}^{k× n}$ | | | | 3. Generate random vector $\mathbf{e}∈\mathbb{F}_{2}^{n}$ with $\mathrm{wt}(\mathbf{e})=t$ | | | | 4. Generate random vector $\mathbf{x}∈\mathbb{F}_{2}^{k}$ | | | | 5. Compute $\mathbf{y}=\mathbf{xA}+\mathbf{e}$ | | | | 6. Construct $\mathbf{H}^{T}=(\mathbf{A}^{T},\mathbf{y}^{T})$ | | | | 7. Define code $C=\ker(\mathbf{H})$ | | | | 8. Choose generator matrix $\mathbf{G}∈\mathbb{F}_{2}^{(n-k)× n}$ for $C$ | | | | Public Key: $(\mathbf{G},t)$ | | | | Private Key: $\mathbf{e}$ | $\xrightarrow{\text{Public Key }(\mathbf{G},t)}$ | Store public key $(\mathbf{G},t)$ | | Encryption | | | | 1. Encode message $\mathbf{m}∈\mathbb{F}_{2}$ | | | | 2. If $\mathbf{m}=0$ : | | | | - Choose $\mathbf{a}∈\mathbb{F}_{2}^{n-k}$ | | | | - Choose $\mathbf{e^{\prime}}∈\mathbb{F}_{2}^{n}$ with $\mathrm{wt}(\mathbf{e^{\prime}})=t$ | | | | - Compute ciphertext: $\mathbf{c}=\mathbf{aG}+\mathbf{e^{\prime}}$ | | | | 3. If $\mathbf{m}=1$ : | | | | - Choose random $\mathbf{c}∈\mathbb{F}_{2}^{n}$ | | | | $\xleftarrow{\text{Ciphertext }\mathbf{c}}$ | | | | Decryption | | | | 1. Compute $\mathbf{b}=\langle\mathbf{e},\mathbf{c}\rangle$ | | | | 2. If $\mathbf{b}=0$ : Decrypt $\mathbf{m}=0$ (high probability) | | | | 3. If $\mathbf{b}=1$ : Decrypt $\mathbf{m}=1$ (probability $1/2$ ) | | | Table 7: The Alekhnovich Second Variant Framework, giving the processes of key generation, encryption and decryption. | Transmitter (Key Owner) | Communication | Sender (Plaintext owner) | | --- | --- | --- | | Key Generation | | | | 1. Choose random matrices: | | | | - $\mathbf{A}∈\mathbb{F}_{2}^{n/2× n}$ | | | | - $\mathbf{X}∈\mathbb{F}_{2}^{n× n/2}$ | | | | - $\mathbf{E}∈\mathbb{F}_{2}^{n× n}$ with row weight $t$ | | | | 2. Compute $\mathbf{M}=\mathbf{XA}+\mathbf{E}∈\mathrm{GL}_{n}(\mathbb{F}_{2})$ | | | | 3. Define binary code $C_{0}$ capable of correcting errors from a BSC with transition probability $t^{2}/n$ | | | | 4. Define map $\phi:\mathbf{x}\mapsto\mathbf{Mx}$ | | | | 5. Construct code $C=\phi^{-1}(C_{0})\cap\ker(\mathbf{A})$ | | | | 6. Choose generator matrix $\mathbf{G}∈\mathbb{F}_{2}^{k× n}$ for $C$ | | | | Public Key: $(\mathbf{G},t)$ | | | | Private Key: $\mathbf{E}$ | $\xrightarrow{\text{Public Key }(\mathbf{G},t)}$ | Store public key $(\mathbf{G},t)$ | | Encryption | | | | 1. Encode message $\mathbf{m}∈\mathbb{F}_{2}^{k/2}$ | | | | 2. Choose random $\mathbf{r}∈\mathbb{F}_{2}^{k/2}$ | | | | 3. Choose random $\mathbf{e}∈\mathbb{F}_{2}^{n}$ with $\mathrm{wt}(\mathbf{e})=t$ | | | | 4. Compute $\mathbf{x}=(\mathbf{m},\mathbf{r})∈\mathbb{F}_{2}^{k}$ | | | | 5. Compute ciphertext: $\mathbf{c}=\mathbf{xG}+\mathbf{e}$ | | | | $\xleftarrow{\text{Ciphertext }\mathbf{c}}$ | | | | Decryption | | | | 1. Compute $\mathbf{y}^{T}=\mathbf{E}\mathbf{c}^{T}=\mathbf{z}^{T}+\mathbf{E}\mathbf{e}^{T}$ | | | | 2. Decode $\mathbf{y}$ using $C_{0}$ to recover $\mathbf{z}$ | | | | 3. Solve $\mathbf{xG}=\phi^{-1}(\mathbf{z})$ to recover $\mathbf{x}$ | | | | 4. Extract message $\mathbf{m}$ from $\mathbf{x}$ | | | Despite the security advantages of code-based ciphers the challenges that have impeded its practical application are the large size of the keys and ciphertext expansion, making it costly and inefficient to communicate. 4.3 Advantages in the Post-Quantum Era Code-based cryptosystems are known for their strong resistance to quantum attacks as no known quantum algorithms efficiently solve SDP or distinguish Goppa codes. Additionally, they involve simpler arithmetic operations compared to lattice-based schemes and avoid complex noise management techniques. Their relative simplicity and efficiency in implementation compared to lattice-based schemes make them attractive candidates for post-quantum cryptographic applications. - Quantum Resistance: Code-based cryptography derives its security from the Syndrome Decoding Problem (SDP), which has been proven NP-hard [16], and the Goppa Code Distinguishing Problem. Unlike the Shor-vulnerable RSA/ECC systems, no known quantum algorithm solves SDP sub-exponentially [18]. The Classic McEliece cryptosystem, a NIST Post-Quantum Standardization finalist [61], exemplifies this resilience. While lattice-based schemes rely on LWE/Ring-LWE assumptions vulnerable to future quantum advances [7], code-based systems maintain security through decades-old coding theory foundations [66]. - Efficiency: Code-based HE replaces lattice-based polynomial ring arithmetic with finite field matrix operations. For example, encryption in McEliece variants requires only $\mathcal{O}(n^{2})$ matrix-vector multiplications, compared to $\mathcal{O}(n^{3})$ FFT-accelerated polynomial multiplications in Ring-LWE schemes [57]. Martínez et al. [57] demonstrated 1.8 $×$ faster encryption in code-based RLWE hybrids compared to pure lattice implementations. The absence of probabilistic decryption failures further reduces redundant computations [40]. - Implementation Simplicity: Code-based schemes inherently manage noise through error-correcting codes rather than artificial noise sampling. Armknecht et al. [13] showed this eliminates lattice-style noise flooding and modulus switching. For example, McEliece-based HE uses predetermined error vectors from code distance properties, avoiding Gentry’s [44] complex bootstrapping framework. Recent implementations by Chen et al. [28] required 40% fewer code lines compared to lattice-based libraries. This simplicity extends to hardware acceleration - FPGA implementations show 2.3 $×$ better area-time product than lattice analogs [47]. 5 Code-Based Homomorphic Encryption Schemes This section presents code-based HE constructions, along with their functionality and comparative analysis. 5.1 Bogdanov and Lee Homomorphic Encryption This scheme [19] was constructed by combining the encryption structure of the local cryptosystem of Applebaum, Barak, and Wigderson [12] with a key scrambling of the McEliece cryptosystem [58]. The ABW PKE scheme is based on hardness-on-average assumptions for natural combinatorial NP-hard optimization problems with the following assumptions: 1. It is infeasible to solve a random set of sparse linear equations mod 2, of which a small fraction is noisy. 1. It is infeasible to distinguish between a random unbalanced bipartite graph and a graph in which a set $S$ with only $|S|/3$ neighbors is planted at random on the large side. 1. There is a pseudo-random generator, where every output depends on a random subset of the constant size of the input. The basic idea here is to construct a generator matrix for the McEliece cryptosystem with the above assumptions. The encryption scheme can be described below: 1. KeyGen Choose a uniformly random subset $S^{\prime}⊂eq\{1,·s,n\}$ of size $s$ and an $n× r$ matrix $M$ from the following distribution. First, choose a set of uniformly random but distinct values $a_{1},·s,a_{n}$ from $F_{q}$ . Set the $i^{th}$ row $M_{i}$ to $$ M_{i}=\left\{\begin{array}[]{lr}(a_{i}a_{i}^{2}\cdots a_{i}^{s/3}0\cdots 0),&% \text{if }i\in S^{\prime}\\ (a_{i}a_{i}^{2}\cdots a_{i}^{s/3}a_{i}^{s/3+1}\cdots a_{i}^{r}),&\text{if }i% \notin S^{\prime}\end{array}\right\} $$ The secret key is the pair $(S^{\prime},M)$ and the public key is the matrix $P=MR$ , where $R$ is a random $r× r$ matrix over $F_{q}$ with determinant 1. 1. Encryption Given a public key $P$ , to encrypt a message $m∈ F_{q}$ , choose a uniformly random $x∈ F_{q}^{r}$ and an error vector $e∈ F_{q}^{n}$ by choosing each of its entries independently at random from a random distribution $\chi$ . Output the ciphertext $c=Px+m1+e$ , where $1∈ F_{q}^{n}$ is the all ones vector. 1. Decryption Given a secret key $(S^{\prime},M)$ , to decrypt a ciphertext $c∈ F_{q}^{n}$ , first find a solution to the following system of $(s/3)+1$ linear equations over variables $y_{i}∈ F_{q},i∈ S^{\prime}$ $$ \sum_{i\in S^{\prime}}y_{i}M_{i}=0, $$ $$ \sum_{i\in S^{\prime}}y_{i}=1, $$ with $y_{i}=0$ when $i∉ S^{\prime}$ . Output the value $\sum_{i∈[n]}y_{i}c_{i}$ . 5.2 Armknecht Scheme Armknecht [13] provided a generic construction of a symmetric key homomorphic encryption scheme that can evaluate multivariate polynomials up to a fixed degree $\mu$ . 1. Keygen(s, $\mu$ , L) The input $s$ represents the security parameter, $L$ is the expected total number of encryptions, and $\mu$ is the maximum degree of supported polynomials. The setup algorithm will then select a codeword support $x$ , a message support $y$ , and two special evaluation codes $C$ and $C^{\prime}$ in such a way that $C^{\mu}⊂eq C^{\prime}$ , and the length of codewords is at least L. The choice of appropriate codes and parameters will vary depending on the coding scheme. Keygen will generate a set, $I$ , of size T and a subset of $[n]$ , where $[n]$ is the set $\{1,2·s n\}$ . T depends on the above parameter and the deployed code. I represents the good locations for the generated encryptions and serves as the secret key of the scheme. The final output will be the secret key $k=(x,y,I)$ . 1. Encrypt(m,k) The inputs are a plaintext message $m∈\mathbb{F}$ , and a secret key $k=(x,y,I)$ . Encrypt first chooses a random encoding $w∈ C$ of m, using the Encode algorithm and the knowledge of the supports $x$ and $y$ . Then, it samples a uniformly random error vector $e∈\mathbb{F}^{n}$ , such that $supp(e)⊂eq[n]\ I$ and computes $c=w+e$ . Finally, the ciphertext is defined as the pair $(c,1)$ where the first entry is an erroneous codeword in $C(I)$ that encodes the plaintext m while the second entry, the integer, is a counter to keep track of the number of multiplications. 1. Decrypt( $(c,\gamma),k)$ ) Decrypt gets as input the secret key $k=(x,y,I)$ and a pair $(c,\gamma)$ with $c∈ C(I)$ and $\gamma≤\mu$ . It outputs $m=Decode(c,I)$ where Decode is used with respect to $x$ and $y$ . 1. Add( $(c_{1},\gamma_{1}),(c_{2},\gamma_{2})$ ), outputs $(c_{1}+c_{2},\max(\gamma_{1},\gamma_{2}))$ . 1. Mult( $(c_{1},\gamma_{1}),(c_{2},\gamma_{2})$ , outputs $(c_{1}· c_{2},\gamma_{1}+\gamma_{2})$ . Next, we will discuss Algebraic Geometry (AG) codes and types in detail for the applications of this scheme. We will also compare the variations of the codes to be used in this scheme. 5.2.1 Comparison and Security Implications from an AG Code Perspective AG codes are codes constructed from algebraic curves over finite fields, providing a flexible framework for designing codes with various parameters and properties. From the perspective of AG codes, we can compare Reed-Muller (RM) codes, Reed-Solomon (RS) codes, and Goppa codes as follows: Reed-Muller Codes: RM codes can be regarded as a special case of AG codes, specifically constructed from the projective line. They have a relatively simple structure, making them easier to analyze. Reed-Solomon Codes: RS codes are also a special case of AG codes, but they are constructed from the projective line in a different manner. They exhibit a more complex structure compared to RM codes and offer enhanced error-correcting capabilities. Goppa Codes: Goppa codes are more general than both RM and RS codes, as they can be constructed from a wider array of algebraic curves. This flexibility allows for the design of codes with improved security properties and higher error-correcting capabilities. Goppa codes are generally considered to be more secure than RM and RS codes due to their less understood structure, along with the ability to choose parameters that enhance resistance to known attacks. However, it is essential to note that the security of any code-based cryptosystem relies on the specific choice of parameters and the use of appropriate decoding algorithms. A comparison of RM, RS and Goppa Codes can be found in Table 8. Table 8: Comparison of the three different Alegbraic Geometry Codes detailed above. | Definition Encoding Decoding | Linear code defined by parity check matrix of monomials Multiplication by generator matrix Majority-logic decoding, Berlekamp’s algorithm | Linear code defined by parity check matrix of polynomials Multiplication by generator matrix Berlekamp-Massey decoding, Euclidean algorithm | Linear code defined by a Goppa polynomial and a set of elements Multiplication by generator matrix Sudan-Guruswami algorithm, McEliece cryptosystem | | --- | --- | --- | --- | | Efficiency | Generally less efficient than RS and Goppa codes | Efficient encoding and decoding | Efficient decoding for certain parameters | | Security | Less secure than Goppa codes due to well-understood structure | Moderate security | Generally considered more secure than RM and RS codes | | Key Size | Larger than RS codes for the same level of security | Smaller than RM and Goppa codes | Can be larger than RS codes depending on parameters | 5.3 Rank Metric Based Homomorphic Encryption The rank-metric-based homomorphic encryption scheme, introduced by Aguilar et al. [4], marks a significant advancement in the field of homomorphic encryption. The authors initially developed an additively homomorphic encryption (AHE) scheme and later extended it to support multiplicative homomorphism. By incorporating bootstrapping techniques and various optimizations, they transformed the scheme into a somewhat homomorphic encryption (SWHE) system capable of performing both addition and multiplication on encrypted data. The AHE scheme is parameterized by the following values: - $q$ : The cardinality of the base field. - $m$ : The dimension of the field extension. - $n$ : The length of the vectors. - $w$ : The rank weight of the error, where $w<m$ . Key Generation (KeyGenAHE) The key generation algorithm proceeds as follows: 1. Sample $f=(f_{1},...,f_{w})\xleftarrow{\$}S_{w}(\mathbb{F}_{q^{m}})$ , where $S_{w}(\mathbb{F}_{q^{m}})$ denotes the set of $w$ -dimensional subspaces over $\mathbb{F}_{q^{m}}$ . 1. Extend $f$ into a basis $b=(f_{1},...,f_{w},g_{1},...,g_{m-w})∈ S_{m}(\mathbb{F}_{q^{m}})$ . 1. Define $g=(g_{1},...,g_{m-w})$ . 1. Compute the matrix $B=\text{Mat}(b)$ , by extending each element of $b$ from $\mathbb{F}_{q^{m}}$ to $\mathbb{F}_{q}$ . 1. Define $D$ as the last $m-w$ columns of $(B^{-1})^{T}$ . 1. Sample $s\xleftarrow{\$}\mathbb{F}_{q}^{n}$ with $F=\text{supp}(f)$ . 1. Return the secret key $sk=(f,g,D,s)$ . Encryption (EncryptAHE) The encryption algorithm is defined as follows: 1. Sample $r=(r_{1},R_{2})\xleftarrow{\$}\mathbb{F}_{q^{m}}^{n}× M_{w,n}(\mathbb{F}_% {q})$ , where $M_{w,n}(\mathbb{F}_{q})$ denotes the set of $w× n$ matrices over $\mathbb{F}_{q}$ . 1. Compute $u=r_{1}$ and $e=fR_{2}$ . 1. Compute $v=s· u+e+\hat{m}$ , where $\hat{m}=g(1)\star m∈\mathbb{F}_{q^{m}}^{n}$ , and $g(1)$ is the first row of $g$ . 1. Return the ciphertext $ct=(u,v)$ . Decryption (DecryptAHE) The decryption algorithm proceeds as follows: 1. Compute $d^{T}\text{Mat}(v-s· u)$ , where $d=D(1)$ . The EncryptAHE and DecryptAHE algorithms are deterministic functions, meaning their outputs are solely determined by their inputs. The randomness in the encryption process is incorporated within the EncryptAHE function itself, ensuring that the function remains deterministic given the input message and the randomly sampled values. This property is crucial for the correctness and security of the AHE scheme. In the EncryptAHE algorithm, the error term $e$ is sampled as $e=fR_{2}$ , where $R_{2}$ is randomly sampled from the matrix space $M_{w,n}(\mathbb{F}_{q})$ . This is mathematically equivalent to directly sampling $e$ from the vector space $\mathbb{F}_{q}^{n}$ . Additionally, the term $\hat{m}$ , derived from the message $m$ using the basis vector $g(1)$ , is restricted to the subspace $\langle g(1)\rangle_{\mathbb{F}_{q}}^{n}$ . This restriction plays a crucial role in ensuring the correctness and security of the AHE scheme. To extend the AHE scheme to support multiplicative homomorphism, the following algorithms are introduced: Given two ciphertexts $ct=(u,v)$ and $ct^{\prime}=(u^{\prime},v^{\prime})$ , the multiplication algorithm computes: $$ \text{Mul}(ct,ct^{\prime})=(v\cdot v^{\prime},-(u\cdot v^{\prime}+u^{\prime}% \cdot v),u\cdot u^{\prime})\in\mathbb{F}_{q^{m}}^{n}\times\mathbb{F}_{q^{m}}^{% n}\times\mathbb{F}_{q^{m}}^{n}. $$ Given the secret key $sk=(f,g,D,s)$ and the resulting ciphertext $(a,b,c)$ from the multiplication operation, the decryption algorithm computes: $$ \text{DecryptMul}(sk,(a,b,c))=d^{T}\text{Mat}(a+s\cdot b+s\cdot s\cdot c), $$ where $d=D(2)$ , the second column of D . Key switching is a technique used to change the encryption key while preserving the ciphertext. This is essential for refreshing the key to improve security or to enable more efficient operations. The key generation algorithm for key switching proceeds as follows: 1. Generate a new basis $b_{2}$ of $\mathbb{F}_{q^{m}}$ and a new secret key $sk_{2}=(f_{2},g_{2},D_{2},s_{2})$ as in KeyGenSHE. 1. For $1≤ i≤ m$ , define $s_{1,i}=d^{T}\text{Mat}(\gamma_{i}\star s_{1})$ , where $d=D(1)$ , the first column of D. 1. Define $ksk=(ksk_{1},...,ksk_{m})$ , where $ksk_{i}\xleftarrow{\$}\text{EncryptSHE}(sk_{2},s_{1,i})$ . 1. For $1≤ i≤ m$ , define $p_{i}=d(i)\star(1,0,...,0)∈\mathbb{F}_{q^{m}}^{n}$ , where $d(i)$ is the $i^{th}$ column of $D$ . 1. Define $projk=(projk_{1},...,projk_{m})$ , where $projk_{i}\xleftarrow{\$}\text{EncryptSHE}(sk_{2},p_{i})$ . 1. Return $(sk_{2},ksk,projk)$ . The homomorphic decryption algorithm with key switching proceeds as follows: 1. Define $u_{i}∈\mathbb{F}_{q}^{n}$ such that $u=\sum_{i=1}^{m}\gamma_{i}\star u_{i}$ . 1. Define $v_{i}∈\mathbb{F}_{q}^{n}$ such that $v=\sum_{i=1}^{m}\gamma_{i}\star v_{i}$ . 1. Compute $ct_{1}=\sum_{i=1}^{m}v_{i}· projk_{i}$ . 1. Compute $ct_{2}=\sum_{i=1}^{m}u_{i}· ksk_{i}$ . 1. Return $ct_{1}-ct_{2}$ . The rank-metric-based homomorphic encryption scheme extends the capabilities of additively homomorphic encryption to support multiplicative homomorphism through the introduction of multiplication and key-switching algorithms. These enhancements enable the scheme to perform basic computations on encrypted data, making it suitable for applications requiring privacy-preserving computations. The deterministic nature of the encryption and decryption processes, combined with careful error sampling and message encoding, ensures the correctness and security of the scheme. Key switching further enhances the flexibility and security of the system, allowing for efficient key management and homomorphic operations. 5.4 Comparison of Code-based HE with Lattice-Based HE As illustrated in Table 9, code‐based HE schemes typically suffer from significantly larger key sizes—often in the order of megabytes or even gigabytes—due to their reliance on matrix-based structures such as those in the McEliece cryptosystem. While their operations (often based on simple XOR and matrix-vector multiplications) can be parallelized, the computational overhead remains high. In contrast, lattice‐based HE schemes, particularly those built on Ring-LWE, benefit from optimizations like the Number Theoretic Transform (NTT) that allow for much more compact key representations (usually in the range of 1–10 KB) and faster arithmetic operations. Ciphertext expansion in code-based schemes tends to be high. In contrast, lattice-based schemes offer more moderate expansion—for example, schemes like CKKS typically expand ciphertexts by about $8×$ relative to the plaintext. Table 9: Efficiency Comparison of code-based vs lattice-based Homomorphic encryption. | Key Sizes | Large (e.g., McEliece keys: $≈$ 1 MB–1 GB due to matrix-based structures). Recent code-based FHE schemes still struggle with key size reduction. | Smaller (e.g., Ring-LWE keys: $≈$ 1-10 KB). Optimizations like NTT (Number Theoretic Transform) enable compact representations. | | --- | --- | --- | | Computation Speed | Matrix/vector operations are parallelizable but computationally heavy. Simpler arithmetic (e.g., XOR-based operations in some schemes). | Faster due to polynomial ring optimizations (e.g., NTT accelerates multiplication in CKKS/BGV [30]). | | Ciphertext Expansion | High (e.g., ciphertexts are large matrices or vectors). | Moderate (e.g., CKKS ciphertexts expand 8x plaintext size). | Noise management is a critical aspect of HE schemes. Table 10 summarizes that code-based HE inherits inherent error correction from the underlying codes (such as Goppa codes), which helps to keep noise growth bounded in additive settings. However, noise growth in these schemes is generally linear, as seen in some additive constructions [13]. In lattice-based HE, the noise grows polynomially with each multiplicative operation, necessitating frequent noise management strategies modulus switching and bootstrapping. Mature bootstrapping techniques, as pioneered by Gentry and further optimized in schemes such as BGV [21], mitigate the effects of noise accumulation, albeit at an additional computational cost. Table 10: Noise Management Comparison of code-based vs lattice-based homomorphic encryption. | Noise Growth | Inherits error-correction properties: errors are intentionally added but bounded by code distance. Noise grows linearly in some additive schemes (e.g., [13]). | Noise grows polynomially with multiplicative operations. Requires frequent management (e.g., modulus switching). | | --- | --- | --- | | Bootstrapping | Limited progress, with high overhead. | Mature techniques (e.g., Gentry’s bootstrapping in BGV [21]). Optimized via sparse embeddings or hybrid key-switching. | | Error Correction | Built-in error correction can mitigate noise. | Relies on probabilistic decryption; no inherent error correction. | The security foundations of code-based HE rest on NP-hard problems like the Syndrome Decoding Problem (SDP) and the Linear Code Distinguishing Problem. These problems have withstood quantum attacks, as there is no known quantum speedup for solving them. However, the large key sizes and relatively immature FHE implementations have limited their widespread adoption (Table 11). On the other hand, Lattice-based HE relies on newer assumptions such as Learning With Errors (LWE) and its ring variant (RLWE), which provide strong security guarantees via worst-case hardness reductions. While these schemes have been integrated into many NIST-backed PQC standards and benefit from extensive industrial testing, their security also depends on emerging lattice reduction techniques and careful management of side-channel vulnerabilities. Table 11: Security Assumptions and Trade-offs between code-based vs lattice-based homomorphic encryption. | Core Hard Problems | Syndrome Decoding Problem (SDP), Linear Code Distinguishing Problem (NP-hard). | Learning With Errors (LWE), Ring-LWE (reductions to worst-case lattice problems). | | --- | --- | --- | | Quantum Resistance | SDP has no known quantum speedup; robust against Shor’s/Grover’s algorithms. | LWE/Ring-LWE are quantum-resistant but rely on newer assumptions. | | Standardization | Limited adoption (e.g., Classic McEliece is a NIST PQC finalist but not HE-focused). | Dominates NIST PQC standards (e.g., Kyber, Dilithium). HE schemes (CKKS/BGV) are industry-tested. | | Attack Surface | Structural attacks (e.g., weak code choice) and ISD attacks (exponential time). | Side-channel attacks, decryption failures, and novel lattice reductions (e.g., BKZ). | Table 12: Summary of Trade-offs between code-based vs lattice-based homomorphic encryption. | Strengths | - Provable NP-hard security. - Built-in error correction. - Simpler operations. | - Efficient bootstrapping. - Optimized libraries (e.g., Microsoft SEAL). - NIST-backed. | | --- | --- | --- | | Weaknesses | - Large keys/ciphertexts. - Immature FHE implementations. | - Complex noise management. - Relies on newer security assumptions. | Table 12 provides a concise summary of the strengths and weaknesses of both approaches. Code-based HE offers provable NP-hard security and built-in error correction along with simpler operational models. However, these advantages are offset by practical challenges such as large key and ciphertext sizes and less mature implementations. Lattice-based HE schemes, conversely, enjoy efficient bootstrapping, a host of optimized libraries (e.g., Microsoft SEAL), and robust backing from NIST initiatives. Their primary challenges lie in complex noise management and the reliance on relatively newer security assumptions that continue to be scrutinized by the research community. The security of homomorphic encryption (HE) schemes, especially those based on lattice and code structures, is an area of ongoing research and evaluation. Lattice-based HE schemes, such as those relying on the Learning With Errors (LWE) problem, have played a crucial role in the development of fully homomorphic encryption systems. However, recent advancements in quantum algorithms have raised concerns about their long-term security. A recent study [29] proposed a polynomial-time quantum algorithm for solving the LWE problem under certain polynomial modulus-noise ratios; if this finding is correct, it could undermine the security assumptions of lattice-based HE schemes. Although a flaw was identified in this algorithm, the search for quantum solutions highlights potential vulnerabilities in lattice-based cryptosystems. On the other hand, code-based HE schemes, while less common, provide alternative security bases rooted in different hard problems, such as the Ideal Rank Syndrome Decoding (IRSD) problem. The security of these schemes is often associated with the difficulty of decoding random linear codes, a challenge that remains difficult even for quantum computers. A code-based somewhat homomorphic encryption scheme [4] has demonstrated security based on the IRSD problem, indicating resilience against certain quantum attacks. 6 Conclusion and Future Work Code-based homomorphic encryption offers promise in the realm of post-quantum cryptography. Its strong security foundation is based on NP-hard problems, such as the syndrome decoding problem, and includes built-in error-correction capabilities, which provide robust protection against both classical and quantum threats. Although there are current challenges related to efficiency and noise management, ongoing research and efforts toward standardization are enhancing its practical implementation. As the cryptographic community continues to explore and improve these schemes, code-based homomorphic encryption is set to play a crucial role in securing sensitive computations in a future where quantum computing becomes a reality. 6.1 Challenges in Code-Based HE Code-based homomorphic encryption faces several technical challenges that must be addressed to fully harness its potential. Key issues include improving computational efficiency, reducing the overheads associated with large key and ciphertext sizes, and managing noise accumulation. While the inherent error-correcting properties of certain code families provide an advantage in controlling noise, significant work is still needed to refine these schemes for practical, high-performance deployment. Braverski [25] demonstrated that LPN (Learning Parity with Noise)-based schemes face fundamental limitations when adapted for homomorphic encryption, primarily due to their linear algebraic structure. These limitations directly parallel challenges in code-based HE. LPN-based HE relies on linear operations over finite fields (e.g., XORs). Braverski shows that repeated homomorphic operations expose linear relationships between ciphertexts, enabling adversaries to recover secret keys via linear algebra attacks. Braverski highlights that enforcing homomorphism in LPN requires relaxing noise distributions or code parameters, inadvertently reducing security margins. Code-based HE (McEliece variants) also depends on linear codes, where ciphertexts are generated via matrix-vector multiplications. Homomorphic operations (e.g., additions) preserve this linearity, creating similar attack surfaces. An adversary could exploit homomorphic additions to derive the structure of the generator matrix, weakening code secrecy [13]. So to enforce Homomorphic encryption, a novel framework has to be constructed, which does not rely on algebraic structure. 6.2 Research Opportunities Code-based cryptography offers a promising avenue for post-quantum HE, but several challenges remain before it can be considered a practical standard. Addressing the efficiency of bootstrapping, key size reduction, error management, and security proofs are critical areas of future research. Advancements in these domains will be essential to establish code-based HE as a viable alternative to lattice-based schemes in the post-quantum era. 1. Limited Fully Homomorphic Encryption (FHE) Constructions Most research on post-quantum HE focuses on lattice-based schemes, leaving code-based HE relatively underdeveloped. The main challenge with the latter lies in designing efficient bootstrapping techniques for fully homomorphic encryption (FHE) based on coding theory. Existing proposals, such as those built on the McEliece cryptosystem, do not inherently support homomorphic operations efficiently. Developing bootstrapping methods that enable arbitrary-depth computation while maintaining practical key sizes and computational efficiency remains an open problem [59, 15]. 1. Key Size and Efficiency Constraints One of the primary barriers to widespread adoption of code-based cryptographic schemes, including HE, is the relatively large key sizes. Traditional code-based encryption, such as the McEliece and Niederreiter cryptosystems, requires public keys that can be several megabytes in size. While variants using Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes and Rank-Metric codes have been proposed to mitigate this issue, further research is needed to develop compression techniques and structured code families that reduce key sizes without compromising security [59, 5]. An alternate approach to tackle this problem can be found in the algebraic structure of the Torus. Chilloti et.al. [31] constructed a third-generation homomorphic encryption scheme on a Torus that proved to be efficient in encrypting the data homomorphically and demonstrated scalablity in operations through modular arithmetic. If the computations on a code-based cryptosystem can be translated from a Field to a Torus, we have an opportunity to achieve efficiency along with the code-based guarantees of security against chosen plaintext attacks and ciphertext-only attacks. 1. Efficient Error-Correction Mechanisms for HE Operations Homomorphic operations in code-based cryptography require mechanisms for handling accumulated noise, similar to error growth in lattice-based schemes. However, unlike LWE-based HE, where noise growth is well-studied, error propagation in code-based HE remains an open area. Designing efficient error-correction techniques that maintain the correctness of homomorphic computations while minimizing decryption failures is a crucial research direction [15, 63]. 1. Security Assumptions and Standardization While code-based cryptosystems have withstood decades of cryptanalysis, their homomorphic counterparts lack comprehensive security analyses. The hardness of decoding random linear codes remains a strong assumption, but ensuring that code-based HE schemes are resilient against quantum attacks requires further investigation. Standardizing security reductions and proofs for homomorphic operations is essential for integrating code-based HE into post-quantum cryptographic standards [5]. 1. Integration with Secure Computation and Applications HE is often used in conjunction with other cryptographic protocols, such as secure multi-party computation (MPC) and zero-knowledge proofs (ZKP). Research into how code-based HE can efficiently integrate with these techniques is still in its early stages. Potential applications include privacy-preserving blockchain technologies, federated learning, and secure genomic data processing [63]. References - [1] Scimago journal & country rank. Accessed: March 17, 2025. - [2] Microsoft seal (release 3.6). https://github.com/Microsoft/SEAL, November 2019. Microsoft Research, Redmond, WA. - [3] Carlos Aguilar-Melchor, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, and Gilles Zémor. Efficient encryption from random quasi-cyclic codes. IEEE Transactions on Information Theory, 64(5):3927–3943, 2018. - [4] Carlos Aguilar-Melchor, Victor Dyseryn, and Philippe Gaborit. Somewhat homomorphic encryption based on random codes. Designs, Codes and Cryptography, pages 1–25, 2025. - [5] Carlos Aguilar-Melchor, Nicolas Gama, Philippe Gaborit, and Julien Schrek. A proposal for a code-based homomorphic encryption scheme. Post-Quantum Cryptography (PQCrypto), pages 179–196, 2018. - [6] Bechir Alaya, Lamri Laouamer, and Nihel Msilini. Homomorphic encryption systems statement: Trends and challenges. Computer Science Review, 36:100235, 2020. - [7] Martin Albrecht. Lwe without modular reduction and improved side-channel attacks. CRYPTO, 2018. - [8] Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. Homomorphic encryption standard. Cryptology ePrint Archive, Paper 2019/939, 2019. - [9] Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 298–307. IEEE, 2003. - [10] A. Aloufi, P. Hu, Y. Song, and K. Lauter. Computing blindfolded on data homomorphically encrypted under multiple keys: A survey. ACM Computing Surveys (CSUR), 54(9):1–37, 2021. - [11] Jacob Alperin-Sheriff and Chris Peikert. Faster bootstrapping with polynomial error. In Advances in Cryptology–CRYPTO 2014, pages 604–623. Springer, 2014. - [12] Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171–180, 2010. - [13] Frederik Armknecht, Daniel Augot, Ludovic Perret, and Ahmad-Reza Sadeghi. On constructing homomorphic encryption schemes from coding theory. In IMA International Conference on Cryptography and Coding, pages 23–40. Springer, 2011. - [14] Daniel Augot and Matthieu Finiasz. A public key encryption scheme based on the polynomial reconstruction problem. In Eli Biham, editor, Advances in Cryptology — EUROCRYPT 2003, pages 229–240, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. - [15] Marco Baldi, Franco Chiaraluce, and Giuseppe Santini. Soft-decision decoding of ldpc codes for code-based cryptosystems. IEEE Transactions on Information Forensics and Security, 14(2):322–332, 2019. - [16] Alexander Barg. Complexity of decoding for the general error pattern. IEEE Transactions on Information Theory, 1998. - [17] Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information theory, 24(3):384–386, 2003. - [18] Daniel J. Bernstein. Classic mceliece: Conservative code-based cryptography. In NIST PQC Standardization Conference, 2017. - [19] Andrej Bogdanov and Chi-Hoon Lee. Homomorphic encryption from codes. Technical Report 2011/622, IACR Cryptology ePrint Archive, 2011. - [20] Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, and David J. Wu. Private database queries using somewhat homomorphic encryption. In Applied Cryptography and Network Security, volume 7954 of Lecture Notes in Computer Science, pages 102–118. Springer, 2013. - [21] Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. In Annual cryptology conference, pages 868–886. Springer, 2012. - [22] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 309–325, 2012. - [23] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014. - [24] Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) lwe. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 97–106, 2011. - [25] Zvika Braverski et al. When homomorphism becomes a liability. Journal of Cryptology, 35(3):1–34, 2022. - [26] E. Brickell and Y. Yacobi. On privacy homomorphisms. In Advances in Cryptology — CRYPTO’ 88, volume 304 of Lecture Notes in Computer Science, pages 117–125. Springer, 1988. - [27] Wouter Castryck, Ilia Iliashenko, and Frederik Vercauteren. On error distributions in ring-based lwe. LMS Journal of Computation and Mathematics, 19(A):130–145, 2016. - [28] Abel CH Chen. Homomorphic encryption based on post-quantum cryptography. In 2023 IEEE International Conference on Machine Learning and Applied Network Technologies (ICMLANT), pages 1–5. IEEE, 2023. - [29] Yilei Chen. Quantum algorithms for lattice problems. Cryptology ePrint Archive, 2024. - [30] Jung Hee Cheon, A. Kim, M. Kim, and Y. Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology–ASIACRYPT 2017, Cham, Switzerland, 2017. Springer. - [31] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachene. Tfhe: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):1–58, 2019. - [32] Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for tfhe. In Proceedings of the International Conference on Theory and Applications of Cryptology and Information Security, pages 670–699. Springer, 2021. - [33] Henry Corrigan-Gibbs, Alexandra Henzinger, Yael Kalai, and Vinod Vaikuntanathan. Somewhat homomorphic encryption from linear homomorphism and sparse LPN. Cryptology ePrint Archive, Paper 2024/1760, 2024. - [34] Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal ideals in cyclotomic rings. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology–EUROCRYPT 2016, pages 559–585, Berlin, Germany, 2016. Springer. - [35] PALISADE Developers. Palisade lattice cryptography library, 2022. Version 1.11.9. - [36] R. S. Dhakar, A. K. Gupta, and P. Sharma. Modified rsa encryption algorithm (mrea). In Proceedings of the 2nd International Conference on Advanced Computing, Communications and Technologies, pages 426–429, 2012. - [37] Shalini Dhiman, Ganesh Kumar Mahato, and Swarnendu Kumar Chakraborty. Homomorphic encryption library, framework, toolkit and accelerator: A review. SN Computer Science, 5(1):24, 2023. - [38] Uddipana Dowerah and Srinivasan Krishnaswamy. A somewhat homomorphic encryption scheme based on multivariate polynomial evaluation. In 2019 29th International Conference Radioelektronika (RADIOELEKTRONIKA), pages 1–6, 2019. - [39] Léo Ducas and Daniele Micciancio. Fhew: bootstrapping homomorphic encryption in less than a second. In Annual international conference on the theory and applications of cryptographic techniques, pages 617–640. Springer, 2015. - [40] Nico Döttling et al. Code-based cryptography: A unifying framework. TCC, 2019. - [41] Taher Elgamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469–472, 1985. - [42] Jun Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. Technical Report 2012/144, IACR Cryptol. ePrint Arch., 2012. - [43] Ernst M Gabidulin, Aleksei Vladimirovich Paramonov, and OV Tretjakov. Ideals over a non-commutative ring and their application in cryptology. In Advances in Cryptology—EUROCRYPT’91: Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, April 8–11, 1991 Proceedings 10, pages 482–489. Springer, 1991. - [44] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 169–178, 2009. - [45] Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors. In Advances in Cryptology–CRYPTO 2013, pages 729–748. Springer, 2013. - [46] Shruthi Gorantala, Rob Springer, and Bryant Gipson. Unlocking the potential of fully homomorphic encryption. Communications of the ACM, 66(5):72–81, 2023. - [47] Qian Guo et al. Hardware acceleration of code-based cryptography. IEEE Transactions on Computers, 2021. - [48] Shai Halevi and Victor Shoup. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Paper 2020/1481, 2020. - [49] Tomoya Hiromasa, Masayuki Abe, and Tatsuaki Okamoto. Packing messages and optimizing bootstrapping in gsw-fhe. In Advances in Cryptology – EUROCRYPT 2015, volume 9056 of Lecture Notes in Computer Science, pages 699–727. Springer, 2015. - [50] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. Ntru: A ring-based public key cryptosystem. In Proceedings of the International Algorithmic Number Theory Symposium, pages 267–288, Cham, Switzerland, 1998. Springer. - [51] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. Public key cryptosystem method and apparatus, Jun 2000. - [52] Y. Hu. Improving the Efficiency of Homomorphic Encryption Schemes. PhD thesis, Worcester Polytechnic Institute, 2013. - [53] Yongwoo Lee, Seonyoung Cheon, Dongkwan Kim, Dongyoon Lee, and Hanjun Kim. $\{$ ELASM $\}$ : $\{$ Error-Latency-Aware $\}$ scale management for fully homomorphic encryption. In 32nd USENIX Security Symposium (USENIX Security 23), pages 4697–4714, 2023. - [54] Tancrède Lepoint and Michael Naehrig. A comparison of the homomorphic encryption schemes FV and YASHE. In Africacrypt, volume 8469 of Lecture Notes in Computer Science, pages 318–335. Springer, 2014. - [55] Yang Li, Kee Siong Ng, and Michael Purcell. A tutorial introduction to lattice-based cryptography and homomorphic encryption. arXiv preprint arXiv:2208.08125, 2022. - [56] Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the 44th Symposium on Theory of Computing, pages 1219–1234, 2012. - [57] Ramon Martínez et al. Code-based rlwe: A new path to post-quantum he. In ASIACRYPT, 2022. - [58] Robert J McEliece. A public-key cryptosystem based on algebraic. Coding Thv, 4244(1978):114–116, 1978. - [59] Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo S. L. M. Barreto. Mdpc-mceliece: New mceliece variants from moderate density parity-check codes. 2013 IEEE International Symposium on Information Theory (ISIT), pages 2069–2073, 2013. - [60] Harald Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Prob. Contr. Inform. Theory, 15(2):157–166, 1986. - [61] NIST. Nist post-quantum cryptography standardization. CSRC, 2022. - [62] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology–EUROCRYPT ’99, volume 1592 of Lecture Notes in Computer Science, pages 223–238. Springer, 1999. - [63] Edoardo Persichetti. On the security of code-based cryptography against quantum adversaries. Designs, Codes and Cryptography, 88(6):1097–1113, 2020. - [64] Yuriy Polyakov, Kurt Rohloff, Gleb Palienko, Dave Cousins, Jack Crawford, Shantanu Sharma, Elena Dubrova, Vinod Vaikuntanathan, Jung Hee Cheon, Miran Kim, Kyoohyung Han, Jinhyuk Kim, Daejun Park, Zhe Liu, Shouhuai Xu, Keke Chen, Wei Dai, Vadim Lyubashevsky, Thomas Schneider, Karthikeyan Bhargavan, Adriana López-Alt, and Eran Tromer. OpenFHE: Open-source fully homomorphic encryption library. In Proceedings of the 29th ACM Conference on Computer and Communications Security (CCS), 2022. - [65] Ronald L Rivest, Len Adleman, Michael L Dertouzos, et al. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169–180, 1978. - [66] Nicolas Sendrier. Structural cryptanalysis of mceliece variants with compact keys. IEEE Transactions on Information Theory, 2007. - [67] Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999. - [68] Nigel Smart. Understanding lwe, 2024. Accessed: March 17, 2025. - [69] Marten Van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Advances in Cryptology–EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 24–43. Springer, 2010. - [70] Violetta Weger, Niklas Gassner, and Joachim Rosenthal. A survey on code-based cryptography. arXiv preprint arXiv:2201.07119, 2022.