Welcome to the resource topic for 2019/1233
Title:
Arbitrary Univariate Function Evaluation and Re-Encryption Protocols over Lifted-ElGamal Type Ciphertexts
Authors: Koji Nuida, Satsuya Ohata, Shigeo Mitsunari, Nuttapong Attrapadung
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.
ePrint: https://eprint.iacr.org/2019/1233
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .