[Resource Topic] 2020/567: An Improvement of Multi-Exponentiation with Encrypted Bases Argument: Smaller and Faster

Welcome to the resource topic for 2020/567

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

Authors: Yi Liu, Qi Wang, 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.

ePrint: https://eprint.iacr.org/2020/567

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 .