Paper 2018/1019

Decentralized Evaluation of Quadratic Polynomials on Encrypted Data

Chloé Hébant, Duong Hieu Phan, and David Pointcheval


Since the seminal paper on Fully Homomorphic Encryption (FHE) by Gentry in 2009, a lot of work and improvements have been proposed, with an amazing number of possible applications. It allows outsourcing any kind of computations on encrypted data, and thus without leaking any information to the provider who performs the computations. This is quite useful for many sensitive data (finance, medical, etc.). Unfortunately, FHE fails at providing some computation on private inputs to a third party, in cleartext: the user that can decrypt the result is able to decrypt the inputs. A classical approach to allow limited decryption power is distributed decryption. But none of the actual FHE schemes allows distributed decryption, at least with an efficient protocol. In this paper, we revisit the Boneh-Goh-Nissim (BGN) cryptosystem, and the Freeman's variant, that allow evaluation of quadratic polynomials, or any 2-DNF formula. Whereas the BGN scheme relies on integer factoring for the trapdoor in the composite-order group, and thus possesses one public/secret key only, the Freeman's scheme can handle multiple users with one general setup that just needs to define a pairing-based algebraic structure. We show that it can be efficiently decentralized, with an efficient distributed key generation algorithm, without any trusted dealer, but also efficient distributed decryption and distributed re-encryption, in a threshold setting. We then provide some applications of computations on encrypted data, without central authority.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Information Security Conference, ISC 2019
Contact author(s)
duong-hieu phan @ unilim fr
2019-07-03: revised
2018-10-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chloé Hébant and Duong Hieu Phan and David Pointcheval},
      title = {Decentralized Evaluation of Quadratic Polynomials on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1019},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.