A multistage protocol for aggregated queries in distributed cloud databases with privacy protection

We define a new generalized additive homomorphic property and introduce a Multipart ElGamal Cryptosystem (MEC) with split keys, which enjoys this property. MEC is a novel modification of the ElGamal cryptosystem with split keys. This paper presents the results of extensive experiments evaluating the effectiveness of the MSQP protocol employing MEC and comparing it with MSQP employing the ElGamal cryptosystem, for a collection of publicly available medical datasets. The experiments evaluating our protocol on 11 real-life databases and a synthetic database demonstrate that the MSQP protocol employing MEC is more efficient than other options and can be recommended for practical implementations.