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

Yi Liu, Qi Wang, Siu-Ming Yiu

TL;DR

This paper presents an optimized cryptographic protocol called Multi-Exponentiation with Encrypted Bases Argument (MEB). Their improved MEB protocol significantly reduces communication costs and computation time for verifiers, making it a more efficient building block for privacy-preserving applications like secure multi-party computation and encryption switching protocols.

What Problem Does This Paper Address?

In today's data-driven world, preserving data privacy while enabling its use is a critical challenge. Cryptographic techniques like fully homomorphic encryption (FHE) and secure multi-party computation (MPC) offer solutions, but often suffer from efficiency issues. A primitive called Encryption Switching Protocol (ESP) was introduced to facilitate secure computations by allowing parties to switch between different encryption schemes without revealing plaintexts. A core component of ESP, and a bottleneck for its efficiency, is the Multi-Exponentiation with Encrypted Bases Argument (MEB) protocol. This protocol is crucial for proving knowledge of encrypted values and their relationships, but the original MEB protocol is computationally expensive, especially for the verifier. This paper aims to improve the MEB protocol to be both smaller and faster, thereby enhancing the efficiency of ESP and other related cryptographic protocols.

Methods

The authors propose an improved MEB protocol that achieves greater efficiency by decomposing the original complex statement into several conditions and then batching them into a single proof of a specific relationship. This approach leads to a more compact and efficient protocol. The core of their improvement lies in a novel way of structuring the proofs and leveraging existing cryptographic primitives like Paillier encryption and Pedersen commitments. They also introduce a new way to batch the executions of the Twin-Ciphertext Proof (TCP), which is a direct application of MEB. The security of their proposed protocol is formally proven using standard cryptographic definitions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Decomposition and Batching: The key to the improvement is breaking down the complex MEB statement into smaller, manageable conditions and then proving them all at once. This is a common strategy in cryptography to reduce overhead.
  • Bridging Encryption Schemes: The protocol cleverly bridges the gap between additively homomorphic encryption (like Paillier) and commitment schemes (like Pedersen), allowing proofs about one to imply properties about the other.
  • Efficiency for Verifiers: A significant focus is on reducing the computational burden on the verifier. This is particularly important for applications where one party (the verifier) might have limited computational resources.
  • Argument Size Reduction: The improved protocol achieves a smaller argument size, which directly translates to lower communication costs.

Key Results

The paper demonstrates significant improvements over the original MEB protocol:

  • Communication Cost: The argument size of their protocol is roughly 29% smaller than the original, leading to reduced communication overhead.
  • Verifier Computation Cost: The computation cost for the verifier is reduced by 19% to 42%, depending on the experimental parameters. This is a substantial improvement, especially for resource-constrained verifiers.
  • Prover Efficiency: While the primary focus is on the verifier, the paper also indicates improvements in prover efficiency.
  • Security: The paper provides a formal security proof, confirming that the improved MEB protocol is a secure argument of knowledge.

Limitations and Future Work

The authors acknowledge that their current implementation is a proof-of-concept and uses a single thread. Future work could focus on optimizing the implementation for better performance, potentially by parallelizing computations. They also suggest exploring further improvements in both communication cost and efficiency. The paper also notes that their MEB protocol is constructed using Paillier encryption, but similar constructions can be made for other additively homomorphic schemes like Pedersen commitments.

Summary updated

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 (MEB) protocol. This protocol is not only the essential component and efficiency bottleneck of ESP, but also has tremendous potential in many applications. For example, it 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 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 MEB protocol.
BibTeX
@article{liu2020improvement,
  author = {Yi Liu and Qi Wang and Siu-Ming Yiu},
  title = {{An Improvement of Multi-Exponentiation with Encrypted Bases Argument: Smaller and Faster}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
}
Figure