Cryptology ePrint Archive: Report 2015/047
Linearly Homomorphic Encryption from DDH
Guilhem Castagnos and Fabien Laguillaumie
Abstract: We design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.
Category / Keywords: public-key cryptography / Linearly Homomorphic Encryption, Orders of Quadratic Fields, Diffie-Hellman Assumptions
Original Publication (with major differences): Proc. of CT-RSA 2015
Date: received 20 Jan 2015, last revised 26 Jan 2015
Contact author: guilhem castagnos at math u-bordeaux1 fr
Available format(s): PDF | BibTeX Citation
Note: An extended abstract of this paper will be published in the proceedings of CT-RSA 2015. This is the full version.
Version: 20150126:121521 (All versions of this report)
Short URL: ia.cr/2015/047
[ Cryptology ePrint archive ]