On Constructing Homomorphic Encryption Schemes from Coding Theory

Frederik Armknecht, Daniel Augot, Ludovic Perret, Ahmad-Reza SadeghiImacc 2011 · DOI

TL;DR

This paper introduces a novel homomorphic encryption scheme that leverages coding theory, offering a new security foundation beyond traditional number theory. While it has limitations like being secret-key and having restricted encryptions, it achieves efficient additive and multiplicative operations, making it suitable for specific applications.

What Problem Does This Paper Address?

Homomorphic encryption allows computations on encrypted data, a highly desirable cryptographic primitive. Existing schemes often rely on number-theoretic assumptions, which could be vulnerable to future quantum computers. Furthermore, achieving fully homomorphic encryption (evaluating any function) often leads to impractically large keys and slow operations. This paper aims to explore a new avenue for homomorphic encryption by basing its security on coding theory, a field less explored for this purpose. The authors also seek to develop schemes that are more efficient for specific tasks, even if they don't achieve full homomorphicity.

Methods

The core of the paper is a generic construction of a homomorphic encryption scheme based on "evaluation codes," a special class of linear codes. The scheme allows for the evaluation of polynomials up to a fixed degree $\mu$ on encrypted data. The encryption process involves encoding a message into an erroneous codeword, where the "good" locations (error-free positions) are part of the secret key. Decryption relies on knowing these good locations to correct the errors and recover the original message. The scheme is designed to be symmetric (secret-key) and has limitations on the number of fresh encryptions due to structural reasons related to the underlying algebraic structure (vector spaces over finite fields).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Coding Theory as a Security Foundation: This is a significant departure from traditional number-theoretic assumptions in cryptography, offering a potential alternative in the face of evolving threats (like quantum computing).
  • Trade-off between Generality and Efficiency: The scheme sacrifices full homomorphicity and public-key capabilities for improved efficiency in specific operations (addition and multiplication) and a simpler decryption process.
  • "Good" Locations as Secret Key: Using the error-free positions of a codeword as part of the secret key is an interesting design choice that enables efficient decryption and homomorphic operations.
  • Limitations are Structural: The paper clearly identifies that the limitations (secret-key, limited encryptions, no bootstrapping) are inherent to the chosen algebraic structure (vector spaces over finite fields) and not arbitrary design choices.
  • Potential for Practical Applications: Despite limitations, the authors argue that the efficiency gains make the scheme suitable for applications like Private Information Retrieval (PIR) and Oblivious Polynomial Evaluation (OPE), where limited homomorphic capabilities are sufficient.

Key Results

The paper presents a concrete instantiation of the scheme using Reed-Muller codes. For security levels of 80 to 128 bits and polynomial degrees up to 3, all operations (encryption, decryption, addition, multiplication) take less than a second after pre-computation. The ciphertext sizes are relatively small, ranging from 9.81 KByte to 60.95 KByte for the tested parameters. The security of the scheme is reduced to the hardness of the Decisional Synchronized Codewords Problem (DSCP), a problem related to decoding specific types of codes.

Limitations and Future Work

The authors acknowledge several limitations:

  • Secret-Key Only: The scheme cannot be public-key.
  • Limited Number of Encryptions: The number of fresh encryptions is restricted to avoid security loss.
  • No Bootstrapping: Gentry's bootstrapping technique, crucial for achieving full homomorphicity, cannot be applied to this scheme.

Future work directions include:

  • Exploring Other Codes: Investigating different types of codes beyond Reed-Muller codes to potentially improve efficiency or overcome limitations.
  • Alternative Algebraic Structures: Replacing the underlying finite field with a weaker structure like a ring to potentially avoid linear algebra-based attacks and limitations.
  • Secret Code Case: Further research into the security implications of keeping the code secret, which provides an additional security margin.
  • KDM Security: Investigating whether the scheme can be made Key-Dependent Message (KDM) secure, which is important for bootstrapping techniques.

Summary updated

BibTeX
@inproceedings{armknecht2011constructing,
  author = {Frederik Armknecht and Daniel Augot and Ludovic Perret and Ahmad-Reza Sadeghi},
  title = {{On Constructing Homomorphic Encryption Schemes from Coding Theory}},
  booktitle = {Imacc},
  year = {2011},
  doi = {10.1007/978-3-642-25516-8\_3},
}
Figure