Paper 2018/1019

Decentralized Evaluation of Quadratic Polynomials on Encrypted Data

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

Abstract

Machine learning and group testing are quite useful methods for many different fields such as finance, banks, biology, medicine, etc. These application domains use quite sensitive data, and huge amounts of data. As a consequence, one would like to be able to both privately and efficiently compute on big data. While fully homomorphic encryption can be seen as a very powerful tool for such a task, it might not be efficient enough, and namely because of the very large ciphertexts. In addition, the result being encrypted, efficient distributed decryption is important to control who can get the information. For our applications, we first remark that 2-DNF formulae evaluation is enough, but efficient multiparty decryption is still required to guarantee privacy. Boneh-Goh-Nissim proposed a nice encryption scheme that supports additions, one multiplication layer, and additions, by using a bilinear map on a composite-order group: this is perfectly suited for 2-DNF formulae evaluation. However, computations on such elliptic curves with composite order turned out to be quite inefficient, and namely when multi-party decryption is required. Fortunately, Freeman proposed a generalization, based on prime-order groups, with the same properties, but better efficiency. Whereas the BGN cryptosystem relies on integer factoring for the trapdoor in the composite-order group, and thus possesses one public/secret key only, our first contribution is to show how the Freeman cryptosystem can handle multiple users with one general setup that just needs to define a pairing-based algebraic structure. Users’ keys are efficient to generate and can also support efficient multi-party decryption, without a trusted server, hence in a fully decentralized setting. Fortunately, it helps to efficiently address some machine learning models and the group testing on encrypted data, without central authority.