Paper 2020/567

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

Yi Liu and Qi Wang and Siu-Ming Yiu

Abstract

A cryptographic framework, called encryption switching protocol (ESP), has been proposed recently, which enables ciphertexts encrypted under \emph{different} schemes to be converted to the same scheme without revealing the plaintexts. This solves a major issue in privacy-preserving applications, in which users can now encrypt their data under different schemes and still be able to process their encrypted data together. In this paper, we propose an improvement to ESP. In particular, we consider the multi-exponentiation with encrypted bases argument ({\sf MEB}) protocol, which 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. Based on our analysis and experiments, our proposed {\sf MEB} protocol can reduce the communication cost by $36\%$ when compared to the original protocol and reduce the computation cost of the verifier by $20\% - 47\%$ depending on the settings of experimental parameters. This is particularly useful for verifiers with weak computing power. We also provide a formal security proof to confirm the security of the improved {\sf MEB} protocol.