Pencil: Private and Extensible Collaborative Learning without the Non-Colluding Assumption

Pencil: Private and Extensible Collaborative Learning without the Non-Colluding Assumption

Speakers: Xuanqi Liu

Conference: NDSS Symposium

YouTube: (no public video)

Overview

This article delves into "Pencil," a groundbreaking framework for collaborative machine learning that addresses critical challenges in data privacy, model confidentiality, and system extensibility. Presented at the NDSS Symposium by Xuanqi Liu, Pencil introduces a novel approach to enable multiple data owners (DOes) and a model owner (MO) to train neural networks together without compromising sensitive information. The talk highlights the growing tension between the need for large, diverse datasets to train robust AI models and stringent privacy regulations like GDPR, particularly in sectors such as anti-money laundering (AML).

Existing privacy-preserving machine learning paradigms often fall short. Federated Learning (FL) sacrifices model privacy, while Secure Multiparty Computation (MPC) frameworks typically rely on a precarious "non-colluding assumption" among third-party servers, a significant vulnerability. Homomorphic Encryption (HE) methods, though powerful, frequently lack the extensibility required for real-world multi-party scenarios. Pencil distinguishes itself by being the first private training framework to simultaneously satisfy data privacy, model privacy, and extensibility to multiple data providers, crucially without relying on the fragile non-colluding assumption. This innovation is vital for industries where data cannot be directly shared and the trained model itself is a proprietary asset.

Background

[▶ Watch: Introduction to collaborative ML privacy challenges and Pencil (0:00)]()

The landscape of privacy-preserving machine learning has seen various approaches, each with inherent trade-offs that Pencil aims to overcome.

Federated Learning (FL), exemplified by horizontal FL schemes, allows clients (DOes) to train local models and submit obfuscated versions to an aggregator. While effective at preserving data privacy by keeping raw data on client devices, FL fundamentally ignores model privacy. The global model is shared among all participants, allowing DOes to learn the final model even with partial contributions. This imbalance disproportionately benefits DOes and is unacceptable in scenarios where the model is proprietary to the MO.

Secure Multiparty Computation (MPC) offers a more robust privacy guarantee. In MPC-based schemes, DOes upload secret shares of their data to several third-party computing servers. The model itself is also secret-shared, ensuring model privacy. However, the Achilles' heel of most MPC proposals is the non-colluding assumption. This critical drawback means that if even two of the computing servers collude, the entire protocol's security can be compromised. While some schemes adopt n-out-of-n sharing, where all parties act as computing servers, they suffer from significantly limited training efficiency and scalability, making them impractical for large-scale collaborative learning.

Homomorphic Encryption (HE) methods, such as those focusing on outsourced training, involve a DO encrypting data and sending it to a cloud service for computation. The trained model remains encrypted. This paradigm is ill-suited for the single-MO-multi-DOes scenario Pencil addresses, as the MO requires the plaintext model for deployment or further fine-tuning with other DOes. The lack of direct access to the plaintext model limits its utility for the MO.

Finally, Differential Privacy (DP) is a technique used to add noise to data or model updates to protect individual data points. While not a standalone solution for collaborative learning, DP can be combined with other techniques. Pencil incorporates an optional DP guarantee, allowing DOes to add perturbations to weight updates for enhanced data privacy.

Pencil's innovation lies in its ability to synthesize the strengths of these approaches while mitigating their weaknesses, specifically by providing data privacy, model privacy, and extensibility without the non-colluding assumption, a unique combination not found in prior art.

Key Findings

[▶ Watch: Pencil's unique advantages over existing privacy-preserving ML (2:00)]()

Pencil makes several pivotal contributions to the field of privacy-preserving machine learning, fundamentally altering the landscape for collaborative model training:

1. Simultaneous Privacy and Extensibility without Non-Collusion: Pencil is the first framework to simultaneously achieve data privacy (DOes' data remains confidential), model privacy (MO's model is not revealed to DOes), and extensibility (MO can easily integrate multiple, potentially heterogeneous, data providers) without relying on the precarious non-colluding assumption among third parties. This addresses a major open problem in cryptographic neural network computation.
2. Efficient 2-Party Protocol Reduction: The core innovation is reducing the complex n-party collaborative training problem to an efficient two-party computation paradigm. The MO interacts with one DO at a time, and switching DOes incurs no extra cost. This design is crucial for Pencil's scalability and extensibility.
3. Novel Preprocessing Optimization: Pencil introduces a preprocessing optimization technique that offloads computationally intensive Homomorphic Encryption (HE) operations to an offline phase. This significantly reduces online training time and communication overhead, making the framework practical for deeper neural networks.
4. Hardware Acceleration for HE: The development of a highly-parallelized GPU version of the BFV HE cryptosystem provides substantial performance boosts, achieving an average of 10x speedup over CPU-based implementations, with encryption and multiplication seeing 16.8x and 16.5x speedups, respectively.
5. Superior Performance and Scalability: Extensive evaluations demonstrate that Pencil achieves nearly identical test accuracies compared to plaintext training (average 0.7% decline). It offers 10x to 260x higher throughput and 2 orders of magnitude less communication than prior art like QUOTIENT and Semi2k. Crucially, its overhead remains constant regardless of the number of participating DOes, unlike other multi-party MPC methods.
6. Robustness Against Advanced Attacks: Pencil is proven robust against sophisticated attacks, including Gradient Matching Attack (mitigated by secret-shared DPSGD) and adaptive attacks targeting its preprocessing design (secured by proper parameter selection, making reconstruction computationally infeasible for adversaries).

These findings collectively position Pencil as a practical and secure solution for real-world collaborative AI development under strict privacy constraints.

Technical Deep Dive

[▶ Watch: Threat model, semi-honest assumption, and cryptographic preliminaries (4:00)]()

Pencil's technical sophistication lies in its strategic combination of cryptographic primitives and a unique architectural design to enable secure, extensible, and efficient collaborative learning.

Threat Model and Preliminaries

The system operates under a semi-honest threat model, where all participating parties (MO and DOes) follow the protocol honestly but may attempt to infer private information from observed data. Crucially, any party may collude with others. Pencil's design reduces this n-party setting to a secure two-party server/client computation paradigm, where the MO and one chosen DO interact at each training step. Security guarantees are established over these 2-party protocols, extending to the general n-party extensible scheme without the non-colluding assumption. Inference attacks based solely on prediction results are not considered.

Pencil leverages several cryptographic and mathematical preliminaries:

• Notations: Standard vector, matrix, and tensor notations are used.
• Lattice-based Homomorphic Encryption (HE): Pencil employs the BFV leveled HE cryptosystem, based on the RLWE problem, which supports addition and multiplication of polynomials in the encrypted domain. Encrypted values are denoted with a bracket.
• Additive Secret Sharing: An additive secret-sharing scheme over the ring Zt (integers modulo t = 2l) is used. If a value x is shared between MO (Party 0) and DO (Party 1), then x = (x)0 + (x)1.
• Fixed-point Representation: Decimal numbers used in machine learning are represented as integers x = x 2f with f* bits of precision. Truncation is required after multiplications to maintain precision and prevent overflow.
• Neural Network Training: Standard Neural Network Training involves Forward Propagation (input x fed through layers f_i(x) = W x + b) and Backpropagation (minimizing a loss function L(Y, t) by computing partial derivatives and updating weights).

Pencil Training Overview

Pencil's architecture defines clear roles and a privacy invariant:

• Roles: The DO holds all training data and labels. The MO holds all trainable parameters (model weights). The network architecture is public.
• Privacy Invariant: Except for the final output Y (revealed to the DO to calculate loss), all intermediate outputs of each layer X_i are secret-shared between the DO and MO: X_i = (X_i)0 + (X_i)1.
• Layer Evaluation: Each layer f_i is evaluated via a secure computation protocol, taking shared inputs (X_i-1) from both parties and producing shared outputs (X_i).

Linear Protocols

Linear layers, such as fully connected and convolutional layers, are fundamental to neural networks and heavily rely on homomorphic evaluations.

Forward Propagation (Algorithm 1)

Algorithm 1 details the evaluation of a linear layer f(X) = W X + b:

1. Input: Shared (X) between MO and DO. MO holds W and b.
2. Output: Shares (Y) of Y = W X + b.
3. Step 1: DO encrypts its share (X)1 and sends it to MO.
4. Step 2: MO evaluates W X using homomorphic plaintext-ciphertext additions and multiplications. This leverages the property that W X = W ((X)0 + (X)1).
5. Step 3: MO chooses a random mask s, calculates (Y)1 = W X - s, and sends it back for decryption.
6. Step 4: DO decrypts (Y)1 to get its share. MO computes its share (Y)0 = s + b.

This process adapts efficient private NN inference techniques for batched inputs.

Backpropagation (Algorithm 2)

Backpropagation is more complex as both operands for gradient computation can be secret-shared.

1. Calculation of ∂x: ∂x = ∂y W*. Similar to forward propagation, MO provides W, and (∂y) is secret-shared. A protocol akin to Algorithm 1 computes (∂x).
2. Calculation of ∂b: ∂b = ∂y 1*. This is a summation across all B samples. Both parties sum their shares locally, and DO sends (∂b)1 to MO for reconstruction.
3. Calculation of ∂w: ∂w = ∂y X*. This is the most challenging, as both ∂y and X are secret-shared. A naive approach involving ciphertext-ciphertext multiplication is prohibitively expensive.

Algorithm 2: Weight Gradient ∂w Calculation

• Step 1: DO sends encrypted (X)1 and (∂Y)1 to MO.
• Step 2: MO evaluates W_ss = (∂Y)0 (X)1 + (∂Y)1 (X)0. This leverages linearity to avoid full ciphertext-ciphertext multiplication.
• Step 3: MO chooses a random mask s, sends W_ss - s for decryption.
• Step 4: DO decrypts to get W_ss - s + (∂Y)1 (X)1.
• Step 5: DO adds a perturbation e (for Differential Privacy) to its share of ∂w.
• Step 6: MO recovers the full ∂w by adding its local term (∂Y)0 (X)0 and mask s.

Incorporating Differential Privacy (DP)

To protect training data privacy, DOes can optionally add perturbations to the gradients. In Algorithm 2, Step 5, the DO adds noise e ~ N(0, (Cσ/B)2) to ∂w, where B is the batch size and C is an L2 norm bound. This implements a secret-shared version of the DPSGD algorithm.

Non-linear Protocols

Non-linear layers like ReLU and average pooling are evaluated using MPC-based protocols, primarily relying on Oblivious Transfer (OT) extension.

• ReLU: Implemented as DReLU(x) x*, where DReLU(x) = 1 if x ≥ 0 and 0 otherwise. DReLU(x) is computed and secret-shared during forward propagation and reused in backpropagation.
• 2D Average Pooling: Involves division, handled by a secure division protocol.
• Truncation: For fixed-point numbers, precision is reduced after multiplications using an approximate truncation protocol that handles large errors efficiently.

Preprocessing Optimization (Algorithm 3 & 4)

A significant portion of computation in linear layers involves plaintext-ciphertext evaluations. Pencil proposes a preprocessing optimization to offload these heavy HE operations offline.

• **General Protocol P(o, u, v) for u * v:** This protocol calculates shares of u v* where u and v are private.
• Fixed u, Variable v: In preprocessing, DO chooses random v', sends it. MO chooses random s, evaluates u v' - s, and sends it back. Both get shares of u v'. Online, DO sends masked v - v' to MO. MO calculates u (v - v') + (u v')0. DO gets (u v')1. Multiple evaluations use multiple masks.
• Variable u: Similar approach, MO also masks its u.
• Algorithm 3: P(o, u, v) Preprocessing Optimization: Generates m2 shared products u'_i v'_j offline. Online, MO and DO randomly pick scalars k_i and l_j to linearly combine these precomputed shares to obtain u v.
• Algorithm 4: Optimized Training Protocol of Linear Layers: Integrates P(o, u, v) into linear layer training. The P_prep(o) phase is executed once, and only the efficient P_online(o, u, v) runs during training, drastically reducing online HE computation.

Extending to Multiple DOes

Pencil's design inherently supports multiple DOes without additional overhead. The framework avoids the high cost of direct n-party computation by decomposing the procedure into a 2-PC paradigm. The MO interacts with one DO at a time, and model weights are kept in plaintext by the MO, allowing incremental updates. This design makes Pencil extensible to more DOes without proportional increases in computation or communication overhead, a stark contrast to previous general n-party MPC methods.

System Design and Security Analysis

Pencil is a modular system incorporating the BFV HE cryptosystem (with GPU acceleration), MPC protocols for non-linear operations, a preprocessing module, and the core 2-party training protocol orchestrated for multi-DOes.

Security Analysis (Theorem IV.1) confirms that the Pencil framework (without preprocessing) is a cryptographic training protocol, satisfying correctness, data privacy (MO learns nothing useful about DO's data except weight updates and final model), and model privacy (DO learns nothing useful about MO's model except predictions on its dataset). This relies on the real/ideal world paradigm with simulators for both MO and DO, assuming the existence of oblivious transfer, homomorphic encryption, and secure non-linearity protocols.

The preprocessing optimization introduces a slight distinguishability. This is quantified by m-linear combinatorially private sets (Definition IV.2). Theorem IV.2 and Corollary IV.1 prove that with appropriate m and fixed-point precision f, it is computationally difficult for an adversary to derive private information from these sets, requiring an exhaustive search space of O(2^(fm))*.

The Differential Privacy mechanism (Algorithm 2, Step 5) is also formally analyzed. It is proven to provide (ε, δ)-differential privacy for any δ > 0, given specific parameters for noise σ, L2 norm bound C, batch size B, and total dataset size N.

Hardware Acceleration

To enhance efficiency, a full GPU acceleration of the BFV HE cryptosystem was implemented. This involved:

• Parallelization: BFV operations are mapped to vector operations in NTT (Number Theory Transform) form, further accelerated by RNS (Residual Number System) decomposition for 64-bit integer arithmetic. This achieves a high degree of parallelism (e.g., 8192 for typical parameters).
• Memory Management: A memory pool reduces the overhead of frequent GPU memory allocation/deallocation.

Demo / Proof of Concept

[▶ Watch: Pencil training overview: 2-party protocol and roles (6:00)]()

While no live demonstration was explicitly mentioned, the comprehensive evaluation section serves as a robust proof of concept for Pencil's capabilities and performance. The experiments were conducted on a physical machine with an Intel Xeon Gold 6230R CPU and NVIDIA RTX A6000 GPU, using CUDA 11.7, and both LAN (384MB/s) and WAN (44MB/s) network settings. The BFV HE parameters were N=8192, t=259, q≈2^180 (3 RNS components), providing 128 bits of security, with a fixed-point precision f=25. Datasets included MNIST, CIFAR10, and AGNews, with MLP, CNN, TextCNN, and pre-trained AlexNet/ResNet50 architectures.

End-to-End Training Performance

1. Training from Scratch:

• Accuracy: Pencil achieved nearly identical test accuracies to plaintext training, with an average decline of only 0.7%. For example, MNIST CNN reached 98.23% (Pencil) vs. 98.59% (Plaintext), and CIFAR10 CNN 71.69% (Pencil) vs. 72.27% (Plaintext).
• Training Time (LAN): Without preprocessing, MNIST CNN converged in 7.8 hours, and CIFAR10 CNN in 280 hours (10 epochs). With the preprocessing optimization (Pencil+), these times were significantly reduced to 4.4 hours for MNIST CNN and 229 hours for CIFAR10 CNN.
• Communication (LAN): For MNIST CNN, communication was 1.71 MB/sample without preprocessing, reduced to 0.36 MB/sample with Pencil+. This demonstrates the significant impact of preprocessing on both time and communication, especially for linear-heavy models.

1. Transfer Learning Models:

• Using pre-trained AlexNet and ResNet50 as feature extractors for CIFAR10 substantially improved accuracy and reduced training time. CIFAR10 ResNet50 achieved 90.02% (Pencil) vs. 89.87% (Plaintext), a marked improvement over training CNN from scratch (71.69%).
• ResNet50 fine-tuning (10 epochs) completed in 6.2 hours with Pencil+, representing a 4.4x boost in throughput compared to training a CNN from scratch. This highlights that for large models, transfer learning makes cryptographic training much more practical.

1. Training with Heterogeneous DOes:

• Simulations with 5 DOes, each having a dataset dominated by two CIFAR10 labels, showed that sequentially incorporating more DOes significantly improved test accuracies. This empirically validated Pencil's extensibility and ability to handle diverse data contributions.

1. Impact of DP Noises:

• Adding Differential Privacy noise to weight gradients on CIFAR10 models resulted in minor accuracy drops (approximately 2%) for a noise level σ = 10-2.

Performance Breakdown and Comparison

• Linear Protocols: Preprocessing (Pencil+) achieved a 3x-5x online speedup and reduced communication cost by 90% for fully connected layers and 2/3 for 2D-convolutional layers.
• Hardware Acceleration (GPU vs CPU): The GPU-based BFV implementation achieved an average of 10x speedup over the CPU-based Microsoft SEAL library. Encryption saw a 16.8x speedup, and multiplication 16.5x.
• Efficiency Comparison with Prior Art:
• In a 2-party setting, Pencil (without preprocessing) achieved a 13x speedup over QUOTIENT 3 and 2 orders of magnitude over Semi2k 13. Pencil+ (with preprocessing) further improved this to a 40x speedup over QUOTIENT.
• In a multi-party setting, Semi2k's overhead grew significantly with more parties (e.g., throughput dropped from 1.11x10^4 img/h for 2 parties to 0.07x10^4 img/h for 5 parties). In contrast, Pencil's overhead remained constant regardless of the number of parties, confirming its superior extensibility.

Pencil Against Attacks

1. Gradient Matching Attack 63: This attack attempts to reconstruct original input data from model updates. Pencil's defense lies in its secret-shared DPSGD. With a noise level σ = 10-2, reconstructed images were smoothed and completely unidentifiable, effectively protecting the original data.
2. Adaptive Attacks against Preprocessing Design: An MO might attempt to reconstruct individual inputs from the m-linear combinatorially private sets generated during preprocessing. Pencil's defense relies on proper selection of m and f. For m=8 and f=25, breaking one pixel would require 9.5 x 10^55 seconds (roughly 10^48 years), equivalent to deciphering elements encrypted by 7680-bit RSA keys. This demonstrates extreme computational difficulty for such an adversary.

Defensive Implications

[▶ Watch: Secure linear layer forward propagation protocol (6:00)]()

Pencil offers significant defensive implications for organizations and practitioners seeking to leverage collaborative machine learning while adhering to strict privacy and intellectual property requirements.

First and foremost, Pencil empowers organizations (Model Owners) to train high-quality models using sensitive data from multiple external partners (Data Owners) without ever directly accessing the raw data. This is critical for compliance with regulations like GDPR, HIPAA, and CCPA, where direct data sharing is often legally or ethically prohibited. Defenders can now confidently engage in joint model development without fear of data leakage from their partners.

Secondly, the framework's strong model privacy guarantees ensure that the trained model, a valuable proprietary asset, remains confidential to the MO. Data Owners only learn predictions on their data, not the underlying model weights. This protects the MO's intellectual property and business advantage, making collaborative ventures viable even when the model itself is a trade secret.

Third, Pencil's extensibility means that MOs can incrementally add new DOes to improve model performance without incurring exponential overhead. This flexibility allows for agile model development and continuous improvement by incorporating diverse datasets over time, enhancing the robustness and generalization capabilities of the deployed models.

Furthermore, the integration of Differential Privacy allows DOes to add an extra layer of protection to their data contributions, providing formal privacy guarantees against reconstruction attacks like Gradient Matching Attack. This gives DOes greater control and confidence in participating in collaborative training.

Finally, the robust security analysis against adaptive attacks on the preprocessing optimization, demonstrating computational infeasibility of reconstruction, provides a high level of assurance for the protocol's integrity. Defenders can rely on Pencil to protect both data and model parameters against sophisticated adversaries, making it a viable solution for high-stakes applications like anti-money laundering, medical diagnostics, and fraud detection.

Key Takeaways

• Pencil is the first framework to provide data privacy, model privacy, and extensibility for collaborative neural network training without relying on the non-colluding assumption.
• It achieves efficiency by reducing n-party computation to an efficient two-party protocol, where the Model Owner interacts with one Data Owner at a time without extra overhead for switching.
• A novel preprocessing optimization significantly reduces online Homomorphic Encryption computation, while a highly-parallelized GPU acceleration of the BFV HE cryptosystem provides an average 10x speedup over CPU implementations.
• Pencil delivers nearly identical test accuracies to plaintext training (average 0.7% decline) and demonstrates superior performance, achieving 10x to 260x higher throughput and 2 orders of magnitude less communication than prior art.
• The framework is robust against sophisticated attacks like Gradient Matching Attack (due to secret-shared DPSGD) and adaptive attacks on its preprocessing design, offering security comparable to 7680-bit RSA keys for parameter reconstruction.
• Pencil makes private and extensible collaborative learning practical for real-world applications under strict privacy regulations, enabling secure multi-party AI development.

About the Speaker(s)

The talk was presented by Xuanqi Liu. Based on the provided metadata, no further biographical details are available.