Paper 2020/567

An Improvement of Multi-Exponentiation with Encrypted Bases Argument: Smaller and Faster

Yi Liu, Qi Wang, and Siu-Ming Yiu


A cryptographic primitive, called encryption switching protocol (ESP), has been proposed recently. This two-party protocol enables interactively converting values encrypted under one scheme into another scheme without revealing the plaintexts. Given two additively and multiplicatively homomorphic encryption schemes, parties can now encrypt their data and convert underlying encryption schemes to perform different operations simultaneously. Due to its efficiency, ESP becomes an alternative to fully homomorphic encryption schemes in some privacy-preserving applications. In this paper, we propose an improvement in ESP. In particular, we consider the multi-exponentiation with encrypted bases argument ({\sf MEB}) protocol. This protocol is not only the essential component and efficiency bottleneck of ESP, but also has tremendous potential in many applications and can be used to speed up many intricate cryptographic protocols, such as proof of knowledge of a double logarithm. According to our theoretical analysis and experiments, our proposed {\sf MEB} protocol has lower communication and computation cost. More precisely, it reduces the communication cost by roughly $29\%$ compared to the original protocol. The computation cost of the verifier is reduced by $19\% - 42\%$, depending on the settings of experimental parameters. This improvement is particularly useful for verifiers with weak computing power in some applications. We also provide a formal security proof to confirm the security of the improved {\sf MEB} protocol.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.Inscrypt 2020
Encryption switching protocolsPaillier encryptionTwin-ciphertext proofZero-knowledge
Contact author(s)
liuy7 @ mail sustech edu cn
2021-03-28: last of 3 revisions
2020-05-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yi Liu and Qi Wang and Siu-Ming Yiu},
      title = {An Improvement of Multi-Exponentiation with Encrypted Bases Argument: Smaller and Faster},
      howpublished = {Cryptology ePrint Archive, Paper 2020/567},
      year = {2020},
      doi = {10.1007/978-3-030-71852-7_27},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.