Paper 2020/567

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

Yi Liu, Qi Wang, and Siu-Ming Yiu

Abstract

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.