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=sDZn_7l6p8w

Overview

This talk, presented by Borui Gong at IEEE S&P, introduces a novel and efficient construction for Zero-Knowledge Arguments (ZKAs) tailored specifically for the Paillier cryptosystem. The core problem addressed is the inherent vulnerability in secure multi-party computation (MPC) scenarios where a malicious party, despite using a homomorphic encryption scheme like Paillier, could deviate from agreed-upon message structures to surreptitiously extract sensitive data from other participants. The research focuses on designing a ZKA that can prove both the correctness of Paillier encryptions and the adherence to predefined message structures, particularly for messages containing binary records arranged in specific slots.

The significance of this work lies in its ability to enhance the security and trustworthiness of various privacy-preserving applications, such as secure data aggregation for statistical analysis or electronic voting. Existing ZKA solutions for Paillier often suffer from limitations, including linear proof costs, impracticality when dealing with the composite modulus inherent to Paillier, or a lack of focus on proving complex message structures. This research overcomes these challenges by proposing a system that achieves sublinear proof size, low verification cost, and supports batch proof and verification, making it practical for real-world large-scale deployments.

The presented solution is a joint effort by Borui Gong, Wang Fat Lau, Man Ho Au, Rupeng Yang, Haiyang Xue, and Lichun Li. It offers a robust framework for ensuring data integrity and confidentiality in MPC by compelling provers to demonstrate compliance with protocol specifications without revealing the underlying sensitive data. By addressing the specific complexities of Paillier's composite modulus and the need for structured message proofs, this work represents a significant step forward in building more secure and verifiable privacy-preserving systems.

Background

▶ Watch: Introduction and problem setup with exit poll example (0:00)

Secure multi-party computation (MPC) often relies on homomorphic encryption schemes to allow computations on encrypted data without revealing the plaintext. The Paillier cryptosystem is a prominent choice for MPC due to its additive homomorphic property, meaning that the sum of plaintexts can be derived from the product of their corresponding ciphertexts. This characteristic makes Paillier particularly suitable for secure data aggregation tasks, such as calculating exit poll statistics, demographic analyses, or sums in financial applications.

Consider a concrete example presented in the talk: an exit poll scenario involving two parties, P1 and P2. P1, perhaps a media or polling company, collects voter preferences for different candidates. P2, like a telecommunications company (e.g., AT&T), possesses demographic data, such as voter ages. The goal is for both parties to securely determine the age groups that favor each candidate without revealing their raw data to each other.

In a typical Paillier-based secure aggregation protocol, P1 would structure its data by packing records into a message. For instance, for each voter, P1 might create a binary representation where 1 denotes a vote for a candidate and 0 otherwise, with these binary records inserted into specific slots within a larger message. P1 then encrypts these structured messages using Paillier and sends the ciphertexts to P2. P2, knowing the ages (weights) corresponding to each entity, would then attach these weights to the ciphertexts, compute the weighted sum (exploiting Paillier's additive homomorphism), and send the aggregated result back to P1. Finally, P1 decrypts the result and parses it to obtain the desired statistics, such as age groups supporting each candidate.

However, a critical vulnerability arises if P1 is malicious. A malicious P1 could deviate from the agreed-upon message structure. For example, instead of inserting a binary 1 in the designated last bit of a slot, P1 might insert it into a higher bit position within the slot. When P1 later decrypts and parses the final aggregated result, the corresponding weight from P2 (e.g., an age value W2) would appear in that higher bit position of the final result. This seemingly minor deviation allows P1 to easily "steal" or infer P2's sensitive data by manipulating the message structure, completely undermining the privacy guarantees of the protocol.

To prevent such malicious behavior, P1 must be compelled to prove that its encrypted messages adhere to the correct structure before P2 performs any computations. This is where Zero-Knowledge Proofs (ZKPs) become essential. P1 would need to prove two things:

1. Each ciphertext is a correct Paillier encryption of a message.
2. Each message holds the correct structure: divided into several slots, with binary records inserted only in the last bit of each slot, and other bits kept at zero.

While multiple ZKP constructions exist for Paillier, they generally fall short in this specific scenario. They typically do not focus on proving structured messages, and their computational costs are often linear with respect to the number of entities, making them impractical for large-scale analyses involving thousands of messages. Furthermore, adapting existing sublinear ZKP systems (like SNARKs or STARKs) is challenging. These systems usually require representing statements as circuits over a prime field. However, Paillier operates under a composite modulus, N^2, where N is a composite number. Translating operations over N^2 into a prime field circuit results in prohibitively large circuit sizes and computational costs, rendering such approaches infeasible.

The goal of this research, therefore, was to construct a ZKP system that specifically addresses these limitations: supporting batch proof and verification, achieving sublinear proof size, ensuring low verification cost, and being reusable across different analyses, all while operating effectively within the composite modulus environment of the Paillier cryptosystem.

Key Findings

▶ Watch: ZKP requirements and why existing solutions are impractical (4:00)

The central contribution of this research is the development of an efficient Zero-Knowledge Argument (ZKA) construction specifically designed for the Paillier cryptosystem, capable of proving not only the correctness of encryption but also the adherence to complex, structured message formats. This addresses a critical security gap in Paillier-based multi-party computation (MPC) where a malicious prover could otherwise leak sensitive data by manipulating message structures.

The key findings and contributions can be summarized as follows:

1. Novel ZKP for Paillier with Structured Messages: The work introduces the first ZKP construction that explicitly focuses on proving Paillier messages with intricate structures, such as binary records placed in specific slots. This directly tackles the vulnerability of malicious provers deviating from protocol specifications to steal data.

1. Operation over Composite Modulus: Unlike many existing ZKP systems that operate over prime fields, this construction successfully devises a constraint system that works directly under the composite modulus N^2 of the Paillier cryptosystem. This bypasses the impracticality and inefficiency of translating Paillier operations into prime field circuits, a significant hurdle for previous approaches.

1. Sublinear Proof Size and Efficient Batch Verification: The proposed system achieves sublinear proof size, meaning that as the number of messages being proven simultaneously increases, the proof size per message decreases. This is a crucial feature for practical applications involving large datasets. Furthermore, it supports batch proof and verification, significantly reducing the overall computational overhead when processing multiple encryptions.

1. Robust Binary and Structured Message Proof Techniques: The research introduces innovative techniques to overcome challenges specific to proving binary values and structured slots within a composite modulus. This includes a verifier-driven range check mechanism to prevent provers from exploiting non-trivial roots when proving M * (M-1) = 0, and the clever use of auxiliary messages to satisfy specific length requirements, enabling the binary proof technique to be extended to messages with many slots.

1. Significant Performance Improvements: Empirical evaluation demonstrates substantial performance gains compared to generic "all-proof" methods. For instance, when proving 800 Paillier messages, the system achieves a proof size that is 19 to 27 times smaller and verification times that are 1.7 to 4 times faster under different parameter settings. This makes the solution highly practical for real-world aggregation scenarios.

1. Reusable and Extensible Core Technique: The developed constraint system and its underlying techniques are general and reusable. The core methodology can be extended to construct proofs for other properties of Paillier encryptions, such as equality proofs (e.g., proving that a voter has at most two 1s in their preference records, as in plurality-at-large elections) or range proofs (e.g., proving that there are more than T ones in a record to prevent weight leakage).

In essence, this work provides a practical and efficient cryptographic primitive that significantly enhances the security of Paillier-based MPC protocols, making privacy-preserving data aggregation more trustworthy and resistant to malicious insider attacks.

Technical Deep Dive

▶ Watch: Overview of their solution: adapting BCC+16 for Paillier (5:50)

The core of the proposed solution involves constructing an efficient Zero-Knowledge Argument (ZKA) for Paillier encryptions that can simultaneously prove message structure. The underlying protocol is inspired by BCC+16, a framework for constructing ZKPs from linear and multiplication constraints, but critically adapted to operate under a composite modulus (N^2) rather than a prime field. The overall objective is to construct a constraint system that represents the desired relation R_star, encompassing both correct Paillier encryption and correct message structure.

Constraints for Correct Paillier Encryption

The Paillier encryption of a message M with randomness R is given by C = (1 + N)^M * R^N mod N^2.

To represent this in a constraint system, it can be rewritten as:

C = (1 + M N) R^N mod N^2 (using the approximation (1+N)^M = 1+MN mod N^2 for M < N).

The first part, (1 + M * N), is easily represented using linear constraints. The challenge lies in efficiently representing R^N mod N^2 within the constraint system.

To construct constraints for R^N, the approach leverages the binary decomposition of N. Let N be represented in binary as (b_k b_{k-1} ... b_1 b_0).

The process involves two main steps:

1. Repeated Squaring: Square R successively to obtain powers of two: R^2, R^4, R^8, ..., up to R^(2^k). This requires Alpha - 1 multiplication constraints, where Alpha is the number of bits in N.
2. Multiplication of Selected Powers: Multiply together the R^(2^i) terms where the corresponding bit b_i in the binary representation of N is 1. For example, if N=11 (binary 1011), we need R^1, R^2, R^8. We would compute R R^2 = R^3, then R^3 R^8 = R^11. This step requires Beta - 1 multiplication constraints, where Beta is the Hamming weight (number of 1s) of N.

In total, representing R^N requires (Alpha - 1) + (Beta - 1) = Alpha + Beta - 2 multiplication constraints.

Combining these, one correct Paillier encryption corresponding to ciphertext C, message M, and randomness R can be represented using a specific number of linear and multiplication constraints.

Proving a Message is Binary

A crucial part of proving message structure is to ensure that certain bits are indeed binary (either 0 or 1). The standard algebraic technique to prove M is binary is to enforce the constraint M * (M - 1) = 0. This works perfectly over a prime field where the only roots are 0 and 1.

However, this approach fails under a composite modulus N^2. In Z_{N^2}, M (M - 1) = 0 mod N^2 can have non-trivial roots other than 0 and 1. For example, if N is composite (e.g., N=pq), there might exist values X and Y (which are typically very large) such that X (X - 1) = 0 mod N^2, yet X is not 0 or 1. A malicious prover could use these non-trivial roots to craft invalid binary messages that still satisfy the algebraic constraint, thus compromising the proof.

To circumvent this, the talk proposes a verifier-aided range check mechanism:

1. The prover first chooses a randomness R_prime from a relatively small range, significantly smaller than the non-trivial roots X or Y. This R_prime is used to hide the message M.
2. The verifier then chooses a random challenge bit L (either 0 or 1).
3. The prover computes a linear combination: L_prime = L * M + R_prime mod N^2.
4. The prover sends L_prime back to the verifier.
5. The verifier checks the range of L_prime. Since R_prime is chosen from a small range, and M is expected to be 0 or 1, L_prime should also fall within a small, predictable range. If L_prime is not "that large," the verifier is convinced that the prover did not use any non-trivial roots. If M were a non-trivial root X, then L * X + R_prime would likely be a large number, failing the range check.

This process, however, still leaves a 1/2 probability of a cheating prover succeeding in a single round. To reduce the soundness error to an acceptable level, this entire process is repeated Kappa times (e.g., Kappa = 80 for 80-bit security). This technique can be extended to prove that a polynomial number of messages are all binary by applying the same constraints to each message.

Proving Messages Hold Correct Structures (Many Slots)

The next challenge is to prove that messages are not only correctly encrypted and contain binary values but also adhere to a specific slot structure. For example, a message might be divided into 64 slots, with each slot consisting of 32 bits, and the binary record expected only in the last bit of each slot.

Initially, for a small number of slots (e.g., two slots), one might apply the binary proof technique to each binary record and then use a linear constraint to prove their correct positioning within the message. However, this approach encounters a problem when dealing with many slots (e.g., 64 slots, each 32 bits long).

The issue is that the binary proof technique (the range check described above) relies on the assumption that given a Paillier ciphertext, its binary representation bits can be fixed or uniquely determined if the plaintext message satisfies a certain length requirement. If the message is too long (e.g., 64 slots * 32 bits = 2048 bits), its Paillier ciphertext might correspond to multiple different binary representations, making the range check ineffective. The binary value of individual bits within a very long message might not be uniquely constrained by the ciphertext itself.

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

1. Instead of proving all binary records within a single long message directly, the prover constructs auxiliary messages. These auxiliary messages are formed by concatenating binary records from multiple original messages. For example, binary records from every 15 original messages might be combined to form one auxiliary message.
2. These auxiliary messages are specifically designed to be of a length that satisfies the "length requirement" (i.e., short enough that their binary representation is uniquely fixed by their Paillier ciphertext).
3. The prover then uses Paillier encryption to commit to these auxiliary messages.
4. Now, because these auxiliary messages satisfy the length requirement, the previously described binary proof technique (with range checks) can be effectively applied to them. This proves that all the collected binary records within the auxiliary messages are indeed binary.
5. Finally, linear constraints are used to link these proven binary records back to their correct positions within the original, structured messages.

By combining these techniques – efficient Paillier encryption constraints, a robust binary proof mechanism using range checks, and the innovative use of auxiliary messages for structured proofs – the researchers construct a comprehensive constraint system for R_star. This system allows proving that a polynomial number of messages are correct Paillier encryptions and that their corresponding plaintexts hold the specified complex structures.

Demo / Proof of Concept

▶ Watch: Challenge of proving binary messages under composite modulus (8:15)

While the talk did not feature a live, interactive demonstration of the system, the speakers presented a detailed performance evaluation and comparative analysis that serves as a robust proof of concept for the efficiency and practicality of their proposed Zero-Knowledge Argument (ZKA) system. The results highlight the system's ability to achieve sublinear proof size and low verification costs, making it suitable for real-world secure data aggregation scenarios.

The performance of the system was examined under two distinct sets of parameters, demonstrating its robustness across different configurations. The primary scenario considered was the two-party data aggregation task, where the system would prove the correctness and structure of Paillier messages.

Key performance metrics presented include:

• Proof Size: When proving 800 Paillier messages simultaneously, the generated proof size was remarkably small, measured at less than 2 to 4 megabytes under different parameter settings. This is a crucial factor for practical deployment, as smaller proofs require less bandwidth for transmission and less storage.
• Verification Time: The required verification time for these proofs was also reported as "very small," indicating that the system imposes a minimal overhead on the verifier. This is essential for scenarios where verifiers might have limited computational resources or need to process proofs quickly.
• Sublinear Proof Size: A significant achievement highlighted was the sublinear nature of the proof size. This means that as the number of messages being proven in a batch increases, the average proof size required for each binary record actually decreases. This characteristic is highly desirable for large-scale applications, where proving thousands or even millions of records becomes economically viable. The speakers noted that for a sufficiently large number of messages, the proof size per binary record could be even less than the encryption size for a single binary bit, showcasing the system's exceptional efficiency.

The talk also included a direct comparison against a baseline approach referred to as an "all-proof" system. This "all-proof" method would involve P1 encrypting each binary record individually using Paillier and then proving that each record is either zero or one using a standard, perhaps less optimized, ZKP. The comparison revealed substantial advantages for the proposed system:

• Proof Size Reduction: When proving 800 messages, the proposed system achieved a proof size that was 19 times smaller or even 27 times smaller than the "all-proof" system, depending on the parameter set. This represents a massive improvement in data efficiency.
• Verification Time Acceleration: Concurrently, the verification time for the proposed system was 1.7 times faster or up to 4 times faster than the "all-proof" system under different parameters. This significantly reduces the computational burden on the verifier.

These performance figures underscore the practical applicability of the research. The ability to handle hundreds or more messages at a time with such efficiency directly addresses the needs of real-world aggregation scenarios, where previous ZKP approaches for Paillier were often deemed too costly or too slow. The comprehensive performance evaluation effectively serves as a strong proof of concept, demonstrating that the derived ZKP is not only theoretically sound but also practically viable and superior to existing alternatives for structured Paillier messages.

Defensive Implications

▶ Watch: Their novel method for securely proving message binarity (9:00)

The efficient Zero-Knowledge Arguments (ZKAs) for the Paillier cryptosystem, as presented in this talk, provide critical defensive capabilities for secure multi-party computation (MPC) protocols, particularly those involving data aggregation. The primary defensive implication is the prevention of data leakage through message structure manipulation.

Here's how defenders can leverage this information:

1. Enforcing Protocol Compliance: The most direct implication is that a verifier (e.g., P2 in the exit poll scenario) can now mandate that the prover (P1) provide a ZKA alongside every batch of Paillier ciphertexts. This ZKA serves as cryptographic assurance that P1 has correctly formed its messages according to the agreed-upon structure (e.g., binary records in specific slots, other bits zero) and that the ciphertexts are valid Paillier encryptions of these structured messages. This eliminates the vulnerability where a malicious P1 could insert '1's into higher bit positions to extract sensitive weights from P2 during decryption.

1. Enhancing Trust and Verifiability in MPC: For organizations building or participating in MPC systems, this ZKA offers a crucial layer of trust. Defenders no longer need to implicitly trust the honesty of the data provider regarding message formatting. Instead, they receive a mathematically verifiable proof. This shifts the security model from "trust P1 not to cheat" to "P1 must cryptographically prove it's not cheating," significantly bolstering the overall security posture of the MPC.

1. Securing Privacy-Preserving Data Aggregation: Applications like secure exit polls, medical research involving aggregated patient data, or financial analyses across multiple institutions can now be implemented with stronger guarantees. Defenders can confidently aggregate data, knowing that the structural integrity of individual contributions has been verified, thus safeguarding the privacy of the contributing parties' raw data.

1. Batch Verification for Scalability: The system's ability to support batch proof and verification is a significant defensive advantage. In real-world scenarios, data aggregation often involves hundreds or thousands of records. Defenders can efficiently verify a large number of proofs simultaneously, making the integration of this ZKA practical without introducing prohibitive computational bottlenecks. The sublinear proof size further reduces the network and processing load on the verifier.

1. Extensibility for Broader Security Guarantees: The core constraint system is general and extensible. This means defenders can adapt and extend this technique to enforce other crucial properties of Paillier-encrypted data. For instance:

• Equality Proofs: To prove that specific records within a message sum to a certain value or contain at most T ones (e.g., ensuring a voter only votes for a limited number of candidates in a multi-choice election).
• Range Proofs: To prove that encrypted values fall within a specific range, further preventing information leakage or ensuring data sanity.

These extensions allow defenders to build increasingly sophisticated and robust privacy-preserving applications with verifiable constraints.

By implementing this ZKA, defenders transform a potentially vulnerable Paillier-based MPC into a demonstrably secure one, ensuring that privacy guarantees are maintained even in the presence of malicious participants. It provides a concrete, efficient tool for building verifiable and trustworthy privacy-preserving systems in a variety of sensitive data environments.

Key Takeaways

• Addresses a Critical Vulnerability in Paillier-based MPC: The research directly tackles the problem of malicious provers exploiting message structure deviations to leak sensitive data in secure multi-party computation scenarios relying on the Paillier cryptosystem, enhancing the security of privacy-preserving data aggregation.
• Novel ZKP Construction for Structured Paillier Messages: It introduces an efficient Zero-Knowledge Argument (ZKA) specifically designed to prove both the correctness of Paillier encryptions and the adherence to complex, structured message formats (e.g., binary records in specific slots) over a composite modulus.
• Achieves Sublinear Proof Size and Efficient Batch Verification: The proposed system is highly practical, offering sublinear proof size (meaning proof size per record decreases with batch size) and supporting efficient batch proof and verification, which is crucial for large-scale data aggregation tasks.
• Overcomes Composite Modulus Challenges with Innovative Techniques: The solution successfully navigates the complexities of Paillier's composite modulus (N^2) by employing a verifier-aided range check for binary proofs (to counter non-trivial roots) and introducing auxiliary messages to enable structured proofs for long messages.
• Demonstrates Significant Performance Gains: Empirical evaluations show that the system dramatically outperforms generic "all-proof" methods, achieving proof sizes that are 19-27 times smaller and verification times that are 1.7-4 times faster when proving hundreds of messages.
• Reusable and Extensible for Broader Applications: The core constraint system and techniques are general and can be extended to prove other valuable properties of Paillier-encrypted data, such as equality proofs (e.g., maximum number of votes) and range proofs (e.g., preventing weight leakage from final results), offering flexibility for future secure applications.

About the Speaker(s)

The talk "Efficient Zero-Knowledge Arguments For Paillier Cryptosystem" was presented by Borui Gong. He is the lead author of this research.

The work is a joint effort with his co-authors and collaborators: Wang Fat Lau, Man Ho Au (who is also Borui Gong's supervisor), Rupeng Yang, Haiyang Xue, and Lichun Li. The transcript does not provide specific titles or affiliations for all authors beyond Man Ho Au being a supervisor, but their collective expertise contributed to this advanced cryptographic research.