Paper 2008/422

A New Approach for Algebraically Homomorphic Encryption

Frederik Armknecht and Ahmad-Reza Sadeghi

Abstract

The existence of an efficient and provably secure algebraically homomorphic scheme (AHS), i.e., one that supports both addition and multiplication operations, is a long stated open problem. All proposals so far are either insecure or not provable secure, inefficient, or allow only for one multiplication (and arbitrary additions). As only very limited progress has been made on the existing approaches in the recent years, the question arises whether new methods can lead to more satisfactory solutions. In this paper we show how to construct a provably secure AHS based on a coding theory problem. It allows for arbitrary many additions and for a fixed, but arbitrary number of multiplications and works over arbitrary finite fields. Besides, it possesses some useful properties: i) the plaintext space can be extended adaptively without the need for re-encryption, ii) it operates over arbitrary infinite fields as well, e.g., rational numbers, but the hardness of the underlying decoding problem in such cases is less studied, and iii) depending on the parameter choice, the scheme has inherent error-correcting up to a certain number of transmission errors in the ciphertext. However, since our scheme is symmetric and its ciphertext size grows exponentially with the expected total number of encryptions, its deployment is limited to specific client-server-applications with few number of multiplications. Nevertheless, we believe room for improvement due to the huge number of alternative coding schemes that can serve as the underlying hardness problem. For these reasons and because of the interesting properties of our scheme, we believe that using coding theory to design AHS is a promising approach and hope to encourage further investigations.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Algebraically Homomorphic EncryptionCoding TheoryProvable Security
Contact author(s)
Frederik Armknecht @ trust rub de
History
2008-10-02: received
Short URL
https://ia.cr/2008/422
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/422,
      author = {Frederik Armknecht and Ahmad-Reza Sadeghi},
      title = {A New Approach for Algebraically Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2008/422},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/422}},
      url = {https://eprint.iacr.org/2008/422}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.