💻 computer science

Homomorphic encryption schemes based on coding theory and polynomials

This survey presents the state of the art in homomorphic encryption schemes that leverage coding theory and polynomials to enable secure computations on encrypted data without decryption.

Original authors: Giovanni Giuseppe Grimaldi

Published 2026-06-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Giovanni Giuseppe Grimaldi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Locked Box" Problem

Imagine you have a very valuable secret (your private data), and you want to ask a friend (a cloud server) to do some math on it. The problem is, you don't trust your friend. If you give them the secret, they might peek. If you give them the locked box, they can't do the math.

Homomorphic Encryption is like a magical locked box. It allows your friend to shake the box, mix the contents, and even multiply the items inside, all while the box remains locked. When they hand the box back to you, you unlock it, and the result inside is the correct answer to the math problem, even though your friend never saw the actual numbers.

This paper is a survey (a big review) of different ways people have tried to build these "magical boxes." The author groups these methods into two main families:

Coding Theory: Building boxes based on patterns and error-correcting codes (like fixing a scratched CD).
Polynomials: Building boxes based on complex algebraic equations (like solving a giant puzzle).

Part 1: The "Coding Theory" Family (The Pattern Matchers)

These schemes treat data like a message written in a specific code. If you add or multiply two coded messages, the result is still a valid code, but it might get a little "noisy" (like static on a radio).

Armknecht et al.'s Scheme: Imagine a game where you hide a secret message inside a long list of numbers. You know exactly which numbers are the "good" ones and which are "bad" (noise). The security relies on the fact that an attacker doesn't know which is which.
- The Catch: It's like a "Somewhat Homomorphic" box. You can add things forever, but you can only multiply a few times before the noise gets too loud to understand.
Challa & Gunta's Schemes: These use a specific type of code called Reed-Muller. Think of it as a grid of lights. You hide your message in the pattern of lights. To encrypt, you scramble the grid and hide the "real" lights among random ones.
- The Catch: The authors claim these are "Fully Homomorphic" (you can do unlimited math), but the paper notes they rely on "non-standard" security ideas. They haven't been proven safe against all modern hackers yet, and no one is actually using them in real life right now.
Bogdanov & Lee's Scheme: This one tried to use a modified version of a famous code (Reed-Solomon).
- The Result: It failed. The paper explains that hackers found a clever trick (using "square codes") to figure out the secret pattern. Once they knew the pattern, they could open any box. This scheme is considered broken.
Aguilar-Melchor et al.'s Scheme: This uses "Rank Metric" codes. Imagine the data isn't just a list of numbers, but a grid of numbers where the "weight" of the error matters.
- The Catch: It allows unlimited additions but only one multiplication. To do more, you need a special "refresh" button (bootstrapping), but the paper says their specific refresh method is insecure.

Summary of Coding Theory: These ideas are mathematically beautiful and clever, but many are either broken, unproven, or too theoretical to be used in real-world apps today.

Part 2: The "Polynomial" Family (The Equation Solvers)

These schemes treat data as coefficients in a giant polynomial equation (like $3x^2 + 5x + 2$ ). They rely on the fact that adding or multiplying these equations is easy, but figuring out the secret ingredients from the result is incredibly hard.

Dasgupta & Pal / DGHV: These use simple integer math with "noise." Imagine trying to guess a secret number by looking at a number that is the secret plus a tiny bit of random static.
- Status: These are foundational ideas that helped start the field, but they are slow and mostly used for theory now.
BFV, BGV, and CKKS: These are the stars of the show. They are the "Fully Homomorphic" boxes that actually work in the real world.
- BFV & BGV: These are like precision calculators. They are great for exact math (like counting money or database queries). They are "Leveled," meaning you can decide how deep the math goes before the box gets too noisy.
- CKKS: This is the "Approximate Calculator." It's designed for real numbers (like temperature or stock prices). It accepts a tiny bit of rounding error, which makes it much faster and perfect for AI and machine learning.
GSW: This is a very important theoretical box. It proved that you can build a fully homomorphic system using a specific type of matrix math. It's the grandfather of many modern fast schemes.
FHEW / TFHE: These are the Speed Demons. They introduced a trick called "bootstrapping."
- The Analogy: Imagine your box gets noisy after every math problem. Bootstrapping is like a "cleaning machine" that takes the noisy box, cleans out the static, and puts the data back in a fresh, quiet box. TFHE can do this cleaning so fast (in less than a second) that you can do any amount of math, no matter how complex.

Summary of Polynomials: These schemes are the current industry standard. They are secure, practical, and used in real software libraries today.

The Final Verdict: Two Sides of the Same Coin

The author concludes that while these two families (Coding vs. Polynomials) look different, they are actually cousins.

Coding Theory views the data as a "noisy message" that needs decoding.
Polynomials view the data as a "noisy equation" that needs solving.

The Main Takeaway:
The paper draws a clear line in the sand:

Coding Theory schemes are mostly theoretical. They are interesting for mathematicians, but many have been broken or lack the security proof needed for real-world use.
Polynomial/Ring schemes (like BFV, BGV, CKKS, TFHE) are the practical winners. They are built on rock-solid security assumptions, they are fast enough to be useful, and they are currently driving the technology for secure cloud computing.

The paper ends by saying that while we currently rely on the polynomial "winners," the ideas from coding theory are still valuable. They might hold the key to future breakthroughs, provided researchers can solve the security and speed issues that currently hold them back.

Technical Summary: Homomorphic Encryption Schemes Based on Coding Theory and Polynomials

Problem Statement

Homomorphic encryption (HE) enables secure computation on encrypted data without decryption, a capability crucial for privacy-preserving cloud computing. While fully homomorphic encryption (FHE) allows arbitrary computations, practical implementation faces significant challenges regarding efficiency, noise management, and security foundations.

The paper addresses the landscape of HE schemes by categorizing them into two primary algebraic families: those based on coding theory and those based on polynomials (often realized through lattice-based structures). The central problem is to survey the state-of-the-art in these specific domains, analyzing their construction, security assumptions, and practical viability. The paper highlights a dichotomy: while many coding-theoretic proposals are algebraically elegant, they often rely on non-standard security assumptions or have been broken, whereas polynomial/ring-based schemes have become the standard for practical, secure HE.

Methodology

The paper employs a comprehensive survey methodology, reviewing and analyzing specific cryptographic schemes from the literature. The analysis is structured into two main sections:

Coding Theory-Based Schemes: The authors examine schemes where the encryption process involves encoding messages into codewords (or noisy codewords) of linear codes. Key concepts include:
- Evaluation Codes: Using polynomial evaluation over finite fields (e.g., Reed-Muller, Reed-Solomon) to define the code structure.
- Rank Metric Codes: Utilizing rank weight and ideal codes over extension fields.
- Security Mechanisms: Relying on problems such as the Decoding Synchronized Codes Problem (DSCP), Ideal Rank Metric Decoding (IRSD), or the difficulty of identifying "good" vs. "bad" locations in a codeword.
Polynomial-Based Schemes: The authors review schemes where the underlying algebraic structure is defined by polynomial rings (often quotient rings like $Z[x]/(x^n+1)$ ). Key concepts include:
- Lattice Assumptions: Most modern schemes rely on the Learning With Errors (LWE) or Ring-LWE (RLWE) problems.
- Noise Management: Techniques such as bootstrapping, relinearization, and modulus switching to control noise growth during homomorphic operations.
- Approximate Arithmetic: Schemes designed for real/complex number computations (e.g., CKKS).

The paper details the algorithms (Keygen, Encrypt, Decrypt, Eval) for specific schemes, including Armknecht et al., Challa-Gunta, Bogdanov-Lee, Aguilar-Melchor et al., Dasgupta-Pal, BFV, BGV, CKKS, GSW, FHEW/TFHE, and DGHV.

Key Contributions and Results

1. Analysis of Coding-Theoretic Schemes

The survey reveals that while coding-theoretic schemes offer interesting algebraic structures, they face significant security and practical hurdles:

Armknecht et al.: A somewhat homomorphic scheme based on evaluation codes and Reed-Muller codes. Security relies on the DSCP. It is symmetric-key and supports a bounded number of multiplications.
Challa-Gunta: Two symmetric-key schemes (vector and matrix versions) based on Reed-Muller codes claiming FHE. The paper notes these rely on non-standard security claims (hiding codeword positions) and lack practical deployment.
Bogdanov-Lee: An asymmetric somewhat homomorphic scheme based on modified Reed-Solomon codes. Result: The paper explicitly states this scheme is broken. A distinguisher-based attack using the "square code" dimension allows an adversary to recover the secret set of coordinates and decrypt any ciphertext in polynomial time.
Aguilar-Melchor et al.: A symmetric-key scheme based on random rank-metric ideal codes. It supports one ciphertext multiplication. Result: The proposed bootstrapping mechanism is deemed insecure because the number of bootstrapping keys exceeds the threshold for solving the underlying IRSD problem.

2. Analysis of Polynomial-Based Schemes

The survey identifies polynomial/ring-based schemes as the current standard for secure and practical HE:

Dasgupta-Pal & DGHV: Early schemes based on integer arithmetic and the Approximate GCD (AGCD) problem. They are somewhat homomorphic but can be made fully homomorphic via bootstrapping.
BFV, BGV, CKKS, GSW: These are asymmetric, leveled fully homomorphic schemes based on LWE/RLWE.
- BFV/BGV: Support exact arithmetic over finite rings. They utilize relinearization to handle the degree growth of ciphertexts during multiplication.
- CKKS: Supports approximate arithmetic, making it suitable for real/complex data applications.
- GSW: A foundational scheme using matrix-based ciphertexts and the "Flatten" operator.
FHEW/TFHE: Fully homomorphic schemes designed for fast bootstrapping of Boolean circuits. They operate over the torus and utilize gate bootstrapping to refresh noise, allowing for unbounded circuit depth.

3. Comparative Synthesis

The paper provides a comparative overview (Table 1) highlighting a major divide:

Coding-Theoretic Schemes: Often conceptually important but frequently suffer from non-standard security assumptions, lack of modern validation, or specific vulnerabilities (e.g., Bogdanov-Lee). They remain primarily theoretical or conceptual.
Polynomial/Ring-Based Schemes: Built on well-established hardness assumptions (LWE, RLWE) that are central to post-quantum cryptography. These schemes have led to practical implementations, software libraries, and are widely used for both exact and approximate arithmetic.

Significance and Claims

The paper claims that the distinction between "coding theory" and "polynomial" approaches should not be viewed as a rigid separation of disjoint objects. Instead, they represent a common spectrum of algebraic homomorphic encryption:

Algebraic Core: Both families encode information into structured algebraic objects (codewords or polynomials) and exploit the compatibility of this structure with addition and multiplication.
Paradigm Difference: The contrast lies in the formulation of correctness and security. Coding-theoretic schemes frame problems in terms of decoding (interpolation from hidden errors), while polynomial schemes frame them in terms of noisy arithmetic over structured rings.
Current State: The paper concludes that while lattice-based (polynomial) schemes currently dominate both theory and practice due to robust security foundations and efficiency, coding-theoretic approaches remain a vital research direction. They offer alternative design paradigms and raise independent mathematical questions regarding decoding problems.

The paper identifies several open problems, including the need for code-based schemes with standard assumptions (like LWE), secure and efficient bootstrapping outside the lattice setting, and systematic security analyses for non-standard proposals. It emphasizes that the mere existence of an appealing algebraic structure is insufficient; a robust hardness assumption and precise noise control are essential for a convincing HE scheme.