Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Algebraically Homomorphic Encryption, Coding Theory, Provable Security

Date: received 1 Oct 2008

Contact author: Frederik Armknecht at trust rub de

Available format(s): PDF | BibTeX Citation

Version: 20081002:031257 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]