Paper 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.

Note: An extended abstract of this paper will be published in the proceedings of CT-RSA 2015. This is the full version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. Proc. of CT-RSA 2015
Keywords
Linearly Homomorphic EncryptionOrders of Quadratic FieldsDiffie-Hellman Assumptions
Contact author(s)
guilhem castagnos @ math u-bordeaux1 fr
History
2015-01-26: last of 2 revisions
2015-01-22: received
See all versions
Short URL
https://ia.cr/2015/047
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/047,
      author = {Guilhem Castagnos and Fabien Laguillaumie},
      title = {Linearly Homomorphic Encryption from DDH},
      howpublished = {Cryptology ePrint Archive, Paper 2015/047},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/047}},
      url = {https://eprint.iacr.org/2015/047}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.