Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

10-2024

Abstract

The Paillier cryptosystem is renowned for its applications in electronic voting, threshold ECDSA, multi-party computation, and more, largely due to its additive homomorphism. In these applications, range proofs for the Paillier cryptosystem are crucial for maintaining security, because of the mismatch between the message space in the Paillier system and the operation space in application scenarios. In this paper, we present novel range proofs for the Paillier cryptosystem, specifically aimed at optimizing those for both Paillier plaintext and affine operation. We interpret encryptions and affine operations as commitments over integers, as opposed to solely over ZN. Consequently, we propose direct range proof for the updated cryptosystem, thereby eliminating the need for auxiliary integer commitments as required by the current state-of-the-art. Our work yields significant improvements: In the range proof for Paillier plaintext, our approach reduces communication overheads by approximately 60%, and computational overheads by 30% and 10% for the prover and verifier, respectively. In the range proof for Paillier affine operation, our method reduces the bandwidth by 70%, and computational overheads by 50% and 30% for the prover and verifier, respectively. Furthermore, we demonstrate that our techniques can be utilized to improve the performance of threshold ECDSA and the DCR-based instantiation of the Naor-Yung CCA2 paradigm.

Keywords

Public-key cryptography, Paillier cryptosystem. Range proof, Multiplicative-to-additive function, Threshold ECDSA, Naor-Tung CCA2. Sigma protocol

Discipline

Information Security

Research Areas

Cybersecurity

Publication

Proceedings of the ACM Conference on Computer and Communications Security (CCS 2024) : Salt Lake City, USA, October 14-18

Publisher

ACM Digital Library

City or Country

Salt Lake City, USA

Download

Share

COinS