Efficient Zero-Knowledge Arguments For Paillier Cryptosystem

Efficient Zero-Knowledge Arguments For Paillier Cryptosystem

Speakers: Borui Gong; Wang Fat Lau; Man Ho Au; Rupeng Yang; Haiyang Xue; Lichun Li

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=AmiXTXoydXY

Overview

This talk, presented by Borui Gong and co-authored by Wang Fat Lau, Man Ho Au, Rupeng Yang, Haiyang Xue, and Lichun Li, introduces a novel and efficient zero-knowledge proof (ZKP) system designed specifically for the Paillier cryptosystem when dealing with structured messages. The core problem addressed is a significant vulnerability in privacy-preserving data aggregation scenarios where a malicious party, acting as a data provider, could subtly manipulate encrypted messages to steal sensitive information from another party, such as age data in a political exit poll analysis.

The research focuses on enabling secure, verifiable computations without requiring parties to reveal their raw data. While homomorphic encryption schemes like Paillier are excellent for additive operations on encrypted data, ensuring the integrity and structure of the underlying plaintext messages has remained a challenge. This work proposes a practical solution that allows a prover to demonstrate that their encrypted messages adhere to predefined structures and contain valid data (e.g., binary flags) without disclosing the messages themselves, thereby preventing data leakage and enhancing trust in collaborative privacy-preserving analytics.

The significance of this work lies in its ability to bridge a critical security gap in real-world applications of homomorphic encryption. By providing a ZKP that is efficient, supports batch verification, and achieves sub-linear proof sizes, the presented system makes secure multi-party computation with structured Paillier ciphertexts far more practical and robust. It directly tackles the complexities of constructing ZKPs over composite moduli, a notorious hurdle for existing sub-linear proof systems, making it a crucial advancement for privacy-preserving technologies.

Background

▶ Watch: Introduction and problem: secure data aggregation with Paillier. (0:00)

Privacy-preserving data aggregation is a cornerstone of modern secure computation, finding applications in diverse fields from medical research to political analytics. A common use case, highlighted in the talk, involves two parties: P1, who has sensitive data (e.g., voter preferences), and P2, who holds complementary sensitive data (e.g., voter ages). Both want to perform a joint analysis, such as determining age groups that favor specific political candidates, without revealing their individual raw datasets to each other.

The Paillier cryptosystem is often chosen for such scenarios due to its additive homomorphic properties, which allow computations (specifically, additions) to be performed directly on ciphertexts, yielding an encrypted result that, when decrypted, corresponds to the result of the computation on the plaintexts. In the example provided, P1 would encrypt its structured data (e.g., binary flags indicating candidate preference, packed into slots within a message) using Paillier and send it to P2. P2 would then attach corresponding weights (e.g., age values) to these ciphertexts, perform homomorphic summations, and send the aggregated result back to P1 for decryption.

However, a critical vulnerability arises if P1 is malicious. As demonstrated in the talk, if P1 deviates from the agreed-upon message structure – for instance, by inserting a '1' bit in a higher position of a slot intended for a binary flag – then upon decryption and parsing of the final aggregated result, the corresponding weight from P2 (e.g., a specific age) could be easily observed in an unintended position, leading to data theft from P2. This highlights the necessity for P1 to provide a zero-knowledge proof that its encrypted messages conform to the specified structure without revealing the messages themselves.

Existing zero-knowledge proof constructions for Paillier largely focus on proving the correctness of encryption or basic properties but do not specifically address the integrity of structured messages. Furthermore, while sub-linear proof systems exist, they are generally impractical for Paillier-based scenarios. The primary reason is that these systems often require generating a circuit over a prime field to represent the underlying relations. Paillier, however, operates under modular arithmetic with a composite number (specifically, modulo N^2), making it challenging to translate Paillier-related computations into prime field circuits without incurring "infeasible circuit sizes and costs." The goal, therefore, was to construct a ZKP that supports batch proof and verification, has sub-linear proof size, boasts low verification cost, and can be reusable across multiple analyses and parties, all while working natively with Paillier's composite modulus.

Key Findings

▶ Watch: Zero-Knowledge Proof requirements: encryption and message structure. (4:00)

The research presented by Borui Gong and his team introduces several key findings and contributions that significantly advance the practicality and security of privacy-preserving computations using the Paillier cryptosystem:

1. First Efficient ZKP for Structured Paillier Messages: The most significant finding is the derivation of an efficient zero-knowledge proof system specifically designed to prove properties of structured messages encrypted under Paillier. This addresses a critical gap where existing Paillier ZKPs did not focus on ensuring the integrity of message structures, which is vital for preventing data leakage in collaborative computations.

1. Adaptation of BCC+16 for Composite Moduli: The core of their solution involves adapting the underlying protocol of BCC+16, an efficient ZKP system that typically works with linear and multiplication constraints, to operate under modular a composite number N^2 (Paillier's modulus). This adaptation overcomes the major challenge faced by other sub-linear proof systems that struggle with the incompatibility between prime field circuits and composite modulus arithmetic.

1. Novel Method for Proving R^N and Message Binarity: The authors devised an efficient constraint system to represent the R^N term in Paillier encryption using Alpha + Beta - 2 multiplication constraints, where Alpha is the number of binary decomposition bits of N and Beta is its Hamming weight. Crucially, they also developed a robust method to prove that a message is binary (i.e., m * (m-1) = 0) even under a composite modulus, which inherently has non-trivial roots. This is achieved through a range proof technique involving a small random challenge and linear combinations, effectively preventing a malicious prover from exploiting these non-trivial roots.

1. Auxiliary Messages for Scalable Structure Proofs: A pivotal innovation for handling long, structured messages (e.g., 64 slots, 32 bits per slot) is the concept of auxiliary messages. When messages become too long, the fixed-length requirement for the binary proof technique is violated, leading to multiple possible solutions for the binary representation bits given a Paillier ciphertext. By constructing shorter auxiliary messages from groups of binary records (e.g., 15 records per auxiliary message) and committing them using Paillier encryption, the system "fixes" these binary representation bits, enabling the efficient application of the binary proof technique to scale to complex message structures.

1. Achieving Sub-Linear Proof Size and Superior Performance: The proposed system demonstrates remarkable efficiency. For proving 800 Paillier messages, the proof size is less than 2 or 4 megabytes, and verification time is very small. Critically, it achieves sub-linear proof size, meaning the proof size per binary record decreases as more messages are proven in a batch. When compared to a standard zero-knowledge proof approach (where each binary record is individually encrypted and proven as 0 or 1), their system is 19 to 27 times smaller in proof size and 1.7 to 4 times faster in verification for 800 messages, making it highly practical for real-world aggregation scenarios.

1. Generalizability and Reusability: The developed technique is general and can be extended to prove various other relations over Paillier, such as equality proofs for sums of records (e.g., proving at least two 'ones' in a voter's preference) or range proofs for sums of units (e.g., proving more than two 'ones' in a record towards the same unit). This extensibility enhances its utility for a broader range of privacy-preserving computations and security requirements.

Technical Deep Dive

▶ Watch: Our solution: efficient, batchable, reusable ZKPs using BCC+16. (5:50)

The core challenge addressed by this work is designing an efficient zero-knowledge proof (ZKP) system for properties of messages encrypted under the Paillier cryptosystem, especially when those messages must adhere to specific structures. The Paillier cryptosystem operates modulo N^2, where N is a composite number, which complicates the use of many existing ZKP systems that rely on prime fields.

The authors' solution builds upon the BCC+16 protocol, which is known for constructing efficient ZKPs from a series of linear and multiplication constraints. The key insight is to represent the desired properties of Paillier messages as such a constraint system, but crucially, one that operates directly under modulo N^2.

Proving Correct Paillier Encryption

A Paillier ciphertext C of a message M with randomness R is given by C = (1 + N)^M R^N mod N^2. This can be rewritten as C = (1 + MN) R^N mod N^2. The term (1 + MN) is already a linear constraint (M is the message, N is the public modulus). The main challenge lies in representing R^N.

To model R^N as a series of constraints, the authors use a technique based on the binary decomposition of N. Let's say N has a binary representation. For example, if N = 21, its binary representation is 10101.

1. Successive Squaring: First, square R repeatedly to get R^(2^1), R^(2^2), R^(2^4), R^(2^8), R^(2^16), etc., up to R^(2^(α-1)), where α is the number of bits in the binary representation of N. Each squaring operation is a multiplication constraint.
2. Multiplication by Ones: Then, multiply the R^(2^k) terms corresponding to the '1' bits in N's binary representation. For N=21 (10101_2), this would involve R^1 R^4 R^16.

• R * R^4 = R^5 (one multiplication)
• R^5 * R^16 = R^21 (another multiplication)

If α is the number of binary decomposition bits of N and β is its Hamming weight (number of '1's in its binary representation), this method requires α + β - 2 multiplication constraints to compute R^N.

Combining this with the linear constraint for (1 + MN), the entire correct Paillier encryption can be represented using a specific set of linear and multiplication constraints.

Proving Message Binarity

A common requirement for structured messages, especially in voting or preference scenarios, is that certain bits must be binary (i.e., either 0 or 1). Mathematically, this is expressed as M * (M - 1) = 0. If this constraint were applied over a prime field, it would only have two roots: M=0 and M=1.

However, under a composite modulus like N^2, this equation can have non-trivial roots other than 0 and 1. These non-trivial roots are typically very large. A malicious prover could exploit these large roots to encode hidden data, leading to leakage.

To prevent this, the authors employ a range proof technique:

1. The prover first selects a small random number, r', from a range significantly smaller than the non-trivial roots. This r' is used to hide the message M.
2. The verifier then chooses a random challenge, b.
3. The prover computes a linear combination: L' = M + b * r'.
4. The prover sends L' to the verifier.
5. The verifier checks the range of L'. If L' is not excessively large, it implies that M and r' must have been small, making it highly probable that M was indeed 0 or 1 (and r' was within its designated small range), rather than one of the large non-trivial roots.

To further reduce the probability of a cheating prover, this process is repeated c times (e.g., c=80) to achieve a sufficiently low soundness error (e.g., 1/2^c). This method can be extended to prove that multiple messages are binary.

Proving Correct Message Structures

The next step is to prove that polynomial messages hold correct structures, meaning they are divided into several slots, and binary records are inserted only in the last bit of each slot.

Initially, for a simple case of two slots in a message, the approach is straightforward:

1. Apply the binary proof technique to each individual binary record.
2. Use a linear constraint to prove that these two records are located in the correct positions within the message.

Scaling to More Slots (Auxiliary Messages)

A major hurdle arises when scaling this to more complex structures, such as 64 slots, where each slot might consist of 32 bits. In this scenario, the direct application of the binary proof technique fails. The reason is that the technique for proving binary bits works reliably only if the binary representation bits of the message are fixed given its Paillier ciphertext. For very long messages, there might be multiple possible sets of binary representation bits that satisfy the constraints, making the proof ambiguous.

To overcome this length requirement issue, the authors introduce the concept of auxiliary messages:

1. Instead of directly proving the structure of a single very long message, they construct shorter auxiliary messages by grouping a fixed number of binary records (e.g., 15 records) from the original messages.
2. These auxiliary messages are then committed using Paillier encryption. By doing so, the length of each auxiliary message is kept within a range that satisfies the "length requirement," meaning its binary representation bits become fixed given its Paillier ciphertext.
3. Once the binary representation bits are fixed by committing to these auxiliary messages, the original range proof technique can be reliably reused to prove that all these records are indeed binary and are located in their correct positions within each original message structure.

By combining constraints for correct Paillier encryption, robust binary proofs (with range checks), and the clever use of auxiliary messages for scalability, the authors construct a comprehensive constraint system to represent the STAR relation – proving correct Paillier encryption with a plaintext holding specific internal structures.

Demo / Proof of Concept

▶ Watch: Constructing constraints for Paillier encryption's R^N term. (6:30)

While the talk does not feature a live, interactive demonstration of the system in action, it provides a thorough performance evaluation and proof-of-concept analysis. The authors rigorously examine their system under two distinct sets of cryptographic parameters, focusing on a practical scenario: a two-party data aggregation involving 800 Paillier messages.

The results clearly demonstrate the practical viability and efficiency of their proposed zero-knowledge argument system:

• Proof Size: For proving 800 Paillier messages simultaneously, the proof size generated by their system is remarkably compact, measuring less than 2 megabytes under one parameter set and less than 4 megabytes under another. This is a crucial metric for real-world adoption, as large proof sizes can be a bottleneck for transmission and storage.
• Verification Time: The verification time required to validate these proofs is reported as "very small," indicating that the system imposes a minimal overhead on the verifier, which is essential for responsive and scalable applications.
• Sub-linear Proof Size: A significant achievement is the attainment of sub-linear proof size. This means that as more messages are proven in a batch, the average proof size per binary record decreases. For large-scale aggregation scenarios, this property makes the system increasingly efficient, with the proof size for each binary record potentially becoming even less than the encryption cost for a single record.
• Comparative Performance: The research also includes a direct comparison against a baseline approach using a "standard ZKP" (or "OR proof"). In this baseline, P1 would encrypt each binary record individually using Paillier and then use a standard ZKP to prove that each encrypted value is either 0 or 1. For proving 800 messages in a batch, the proposed system shows substantial improvements:
• Proof Size: It is 19 times or 27 times smaller in proof size, depending on the parameter set.
• Verification Time: It is 1.7 times or 4 times faster in verification time.

These performance figures underscore the practical advantages of the new system, making it highly suitable for real-world data aggregation scenarios where proving hundreds or thousands of structured Paillier messages efficiently is paramount. The analysis effectively serves as a robust proof of concept, validating the theoretical constructions with concrete performance metrics.

Defensive Implications

▶ Watch: Proving messages adhere to predefined slot structures. (11:00)

The findings from this research have profound implications for defenders involved in designing, implementing, or auditing privacy-preserving systems that rely on the Paillier cryptosystem or similar homomorphic encryption schemes.

1. Mandate ZKP for Message Structures: The primary defensive measure is to require zero-knowledge proofs for message structures from any party providing encrypted data. As demonstrated, simply receiving Paillier ciphertexts is insufficient; a malicious prover can subtly manipulate the plaintext structure to leak sensitive information during aggregation. Defenders (like P2 in the example) must enforce that P1 provides a ZKP alongside the ciphertexts, attesting to the correct formation and content (e.g., binarity) of the underlying messages.

1. Integrate Proposed ZKP Construction: Organizations utilizing Paillier for privacy-preserving data aggregation should actively investigate and integrate the specific ZKP construction detailed in this research. Its efficiency, sub-linear proof size, and ability to handle composite moduli directly address the vulnerabilities and performance bottlenecks of previous approaches. This integration ensures data integrity and prevents the "weight leakage" attack described in the talk.

1. Audit Existing Implementations: Defenders should audit any existing privacy-preserving computation systems that use homomorphic encryption. If these systems rely on parties to trust that message structures are correctly formed without cryptographic proof, they are vulnerable to data leakage. Remediation would involve incorporating a robust ZKP mechanism.

1. Consider ZKP Support in Scheme Selection: When evaluating and selecting homomorphic encryption schemes for new projects, defenders should prioritize schemes that either inherently support or have well-developed, efficient zero-knowledge proof systems for specific message properties and structures. The ease and efficiency of integrating such ZKPs should be a key criterion in the decision-making process.

1. Leverage Generalizability for Broader Security: The technique's generalizability allows it to be extended beyond simple structural proofs. Defenders can utilize this framework to derive other crucial proofs, such as:

• Equality Proofs for Sums of Records: For example, proving that a voter has selected exactly one candidate (i.e., the sum of binary preferences is one), preventing invalid votes in elections.
• Range Proofs for Sums of Units: For instance, proving that a sum of weights falls within a specific range, which can further prevent "weight leakage" from the final combination or collaboration result by ensuring aggregated values conform to expected boundaries. This adds another layer of security against various forms of data manipulation.

By adopting these defensive strategies, organizations can significantly enhance the security and trustworthiness of their privacy-preserving data analytics, ensuring that sensitive information remains protected even when collaborating with potentially malicious or curious parties.

Key Takeaways

• Vulnerability in Paillier-based Aggregation: Privacy-preserving data aggregation using the Paillier cryptosystem is vulnerable to data leakage if a malicious party deviates from agreed-upon message structures, allowing them to extract sensitive information from collaborators.
• Limitations of Existing ZKPs: Prior zero-knowledge proof constructions for Paillier do not efficiently address structured messages, and existing sub-linear proof systems are impractical due to the challenges of operating over Paillier's composite modulus (N^2) rather than prime fields.
• Novel ZKP for Structured Paillier: The presented work introduces an efficient zero-knowledge argument system capable of proving both correct Paillier encryption and the integrity of structured messages (including binarity) directly over a composite modulus.
• Auxiliary Messages for Scalability: A key technical innovation is the use of "auxiliary messages" to overcome length limitations in binary proofs, enabling the system to scale efficiently to complex, multi-slot message structures.
• Significant Performance Gains: The proposed system achieves sub-linear proof size and offers substantial performance improvements, being 19-27 times smaller in proof size and 1.7-4 times faster in verification compared to standard ZKP approaches for batch proofs of 800 messages.
• Generalizability and Extensibility: The technique is general and reusable, allowing it to be extended to prove various other relations over Paillier, such as equality proofs for sums of records or range proofs for aggregated values, enhancing its utility for diverse security requirements.

About the Speaker(s)

The talk was presented by Borui Gong, who introduced the work as a collaborative effort. The full list of authors and speakers for this research includes Borui Gong, Wang Fat Lau, Man Ho Au, Rupeng Yang, Haiyang Xue, and Lichun Li. While specific titles and affiliations for all individuals were not detailed in the transcript, Borui Gong mentioned Man Ho Au as his supervisor, indicating their involvement in academic research. Their collective work focuses on advancing cryptographic techniques, particularly in the realm of zero-knowledge proofs and secure multi-party computation, to enhance privacy and security in data processing.