Two-Party Secure Computation for Any Polynomial Function on Ciphertexts under Different Secret Keys

Multikey fully homomorphic encryption proposed by Lopez-Alt et al. (STOC12) is a significant primitive that allows one to perform computation on the ciphertexts encrypted by multiple different keys independently. Then, several schemes were constructed based on decisional small polynomial ratio or learning with errors. These schemes all require an expansion algorithm to transform a ciphertext under a single key into an encryption of the same message under a set of keys. To achieve the expansion algorithm without interaction with these key-keepers, their encryption algorithm not only outputs a ciphertext of a plaintext but also exports auxiliary information generated from the randomness used in the former encryption process. Beyond that, the size of the ciphertext encrypted by multiple keys increases linearly or quadratically in the number of participants. In this paper, we studied the problem whether someone can directly perform arbitrary computation on ciphertexts encrypted by different keys without any auxiliary information in the output of the encryption algorithm and an increase in the size of the ciphertext in the expansion algorithm. To this end, we proposed a novel and simple scheme of secure computation on ciphertexts under two different keys directly without any auxiliary information. In other words, each party just provides its own ciphertexts encrypted by the GSW scheme (CRYPTO13). In the procedure of executing evaluation on these ciphertexts, the size of the new ciphertext remains the same as that of the GSW ciphertext.