Paper 2019/1233

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

Koji Nuida, Satsuya Ohata, Shigeo Mitsunari, and Nuttapong Attrapadung


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
Multiparty computationsecure function evaluationadditively homomorphic encryption
Contact author(s)
nuida @ mist i u-tokyo ac jp
2019-10-21: received
Short URL
Creative Commons Attribution


      author = {Koji Nuida and Satsuya Ohata and Shigeo Mitsunari and Nuttapong Attrapadung},
      title = {Arbitrary Univariate Function Evaluation and Re-Encryption Protocols over Lifted-ElGamal Type Ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1233},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.