Paper 2019/1233 Original: eprint.iacr.org/2019/1233 ↗

Arbitrary Univariate Function Evaluation and Re-Encryption Protocols over Lifted-ElGamal Type Ciphertexts

Abstract

Homomorphic encryption (HE) is one of the main tools in secure multiparty computation (MPC), and the (elliptic-curve) lifted-ElGamal cryptosystem is certainly the most efficient among the existing HE schemes. However, the combination of MPC with this most efficient HE has rarely appeared in the literature. This is mainly because the major known techniques for (additively) HE-based MPC are not available for this scheme due to its typical restriction that only a plaintext in a small range can be efficiently decrypted. In this paper, we resolve this problem. By our technique, a Server having a lifted-ElGamal ciphertext $[[m]]$ with unknown small plaintext $m$ can obtain a ciphertext $[[ \varphi(m) ]]$ for an arbitrary function $\varphi$ by just one-round communication with a semi-honest Client (and also two-rounds with a malicious Client) having a decryption key, where $m$ is kept secret for both parties. This property enlarges much the variations of MPC based on the most efficient lifted-ElGamal cryptosystem. As an application, we implemented MPC for exact edit distance between two encrypted strings; our experiment for strings of length $1024$ shows that the protocol takes only $45$ seconds in LAN environments and about $3$ minutes even in WAN environments. Moreover, our technique is also available with other "lifted-ElGamal type" HE schemes and admits different keys/schemes for the original and the resulting ciphertexts. For example, we can securely convert a level-2 (i.e., after multiplication) ciphertext for some two-level HE schemes into a level-1 (i.e., before multiplication) ciphertext, and securely apply arbitrary functions $\varphi(m)$ to encrypted plaintexts for some attribute-based HE schemes. This is the first result (even by using communication) on realizing these two functionalities.