PaperlayerView exact revision on arXiv

Source-linked AI summary

Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption

Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Richard Nock, Giorgio Patrini, Guillaume Smith, Brian Thorne

arXiv:1711.10677v1cs.LG

TL;DR

The paper studies private joint learning when providers hold different features for unlinked common entities, adding the problem of entity-resolution errors to federated learning. It develops a privacy-preserving two-phase protocol and formally analyzes error effects, finding support for learning under reasonable linkage-error assumptions while identifying practical limitations.

  • Problem

    The central gap is private learning on vertically partitioned data when only one provider has labels and entities are not linked across providers.

  • Method

    A three-party protocol combines privacy-preserving entity resolution with federated logistic regression using additively homomorphic encryption.

  • Results

    The system is reported as accurate as a naive centralized non-private solution, while the analysis covers classifier, loss, margin, and generalization effects of linkage mistakes.

  • Takeaways & Limitations

    Under reasonable assumptions on the number and magnitude of entity-resolution mistakes, the results strongly support federated learning when each provider’s data significantly uplifts the other.

  • Takeaways & Limitations

    The protocol incurs substantial encrypted-arithmetic overhead, and its Taylor loss is only a rough approximation of logistic loss when |θ⊤x_i| is large.

Abstract

from arXiv · show

Consider two data providers, each maintaining private records of different feature sets about common entities. They aim to learn a linear model jointly in a federated setting, namely, data is local and a shared model is trained from locally computed updates. In contrast with most work on distributed learning, in this scenario (i) data is split vertically, i.e. by features, (ii) only one data provider knows the target variable and (iii) entities are not linked across the data providers. Hence, to the challenge of private learning, we add the potentially negative consequences of mistakes in entity resolution. Our contribution is twofold. First, we describe a three-party end-to-end solution in two phases ---privacy-preserving entity resolution and federated logistic regression over messages encrypted with an additively homomorphic scheme---, secure against a honest-but-curious adversary. The system allows learning without either exposing data in the clear or sharing which entities the data providers have in common. Our implementation is as accurate as a naive non-private solution that brings all data in one place, and scales to problems with millions of entities with hundreds of features. Second, we provide what is to our knowledge the first formal analysis of the impact of entity resolution's mistakes on learning, with results on how optimal classifiers, empirical losses, margins and generalisation abilities are affected. Our results bring a clear and strong support for federated learning: under reasonable assumptions on the number and magnitude of entity resolution's mistakes, it can be extremely beneficial to carry out federated learning in the setting where each peer's data provides a significant uplift to the other.

1 Introduction

The paper addresses private joint learning from vertically partitioned, unlinked data by combining privacy-preserving entity resolution with secure federated logistic regression. It also formally analyzes how linkage mistakes affect classifiers, losses, margins, and generalization.

  • Contributions: Two providers jointly perform logistic regression over different features of undisclosed common entities through a coordinator, without exchanging raw data.The protocol uses privacy-preserving entity resolution and additively homomorphic encryption.
  • Contributions: Entity-resolution errors can be significantly more damaging when they link examples from different classes than when they link examples from the same class.The paper presents this as a formal bound on optimal-classifier deviation.
  • Contributions: Large-margin classifications by the optimal classifier remain unchanged when learned from data containing entity-resolution mistakes.This immunity concerns examples receiving a large-margin classification under the optimal unknown classifier.
  • Contributions: 1/n^α convergence bounds relate the empirical loss gap to penalties from the optimal classifier, entity resolution, and class sufficient statistics.Here n is the number of examples and α ∈(0, 1] depends on the assumptions.
  • Contributions: When mistakes are sufficiently few, entity resolution does not notably affect generalization rates.The generalization bounds are driven by the same key penalties as the empirical-loss bounds.
  • Implications: The authors argue that these results strongly support federated learning when combining databases significantly improves classification accuracy.The introduction also motivates collaboration through potential gains in statistical power for analytics and prediction.

2 Related work

Related work largely studies horizontal partitioning or assumes known correspondence between records, whereas this paper combines vertical partitioning, privacy, entity resolution, and learning analysis.

  • Scope: Federated learning keeps data at providers while protecting privacy against a central aggregator; this paper considers vertical partitioning and entity resolution with a given error rate.
  • Privacy approaches: Differential privacy commonly protects outputs by adding calibrated noise to data or algorithms.
  • Privacy approaches: The paper instead uses cryptographic guarantees such as additively homomorphic encryption, trading security properties for computational cost rather than predictive power.
  • Partitioning: Most secure distributed-learning work uses horizontal partitions, while vertical partitioning requires a more complex and expensive protocol.
  • Entity resolution: Prior cited approaches generally do not incorporate entity resolution, although stable row correspondence cannot be assumed when identifiers are error-prone.
  • Entity resolution: Patrini et al. study a pipelined entity-resolution and learning process, but require labels to be shared among all parties and provide less comprehensive theoretical guarantees.

3 Security environment and primitives

The security model assumes honest-but-curious, non-colluding participants and keeps records, linkage information, and common-entity knowledge private. Additively homomorphic encryption enables encrypted arithmetic, but introduces substantial computational overhead.

  • Security model: Participants follow the protocol, do not collude, and try to infer information from received data under the honest-but-curious security model.The coordinator holds the private decryption key.
  • Privacy requirements: The protocol keeps the number and identity of common entities secret from both data providers.
  • Privacy requirements: No raw sensitive data leaves either provider before encryption, although providers may use their own unencrypted records locally.
  • Encryption primitives: Additively homomorphic encryption lets parties compute encrypted sums and multiply ciphertexts by plaintexts without decrypting intermediate results.
  • Encryption primitives: The scheme supports component-wise vector and matrix operations, providing linear-algebra primitives for machine learning.
  • Costs and assumptions: Paillier ciphertexts are 2m bits long and encrypted addition is two to three orders of magnitude slower than unencrypted addition.Here m is typically at least 1024.

4 Privacy-preserving entity resolution

The paper privately resolves entities across vertically partitioned datasets without exposing identifiers or common-entity membership. It uses cryptographic longterm keys, coordinator-side matching, and encrypted outputs to prepare aligned data for learning.

  • Entity resolution is required because vertically partitioned datasets must identify corresponding entities before combining their features for learning.
  • Cryptographic longterm keys encode multiple personal identifiers in Bloom filters, with Dice similarity measuring candidate matches.
  • The coordinator matches CLKs using Dice coefficients and greedily selects the most similar pairs, with blocking available for faster computation.
  • Entity matching outputs permutations σ and τ for row alignment plus a mask m identifying rows shared by both providers for learning.
  • CLKs resist typographical errors but remain susceptible to cryptanalytic attacks when parameters are insecure or too few identifiers are hashed.
  • The encrypted mask keeps common-entity membership confidential, although truncation reveals to the longer-dataset owner which rows lack correspondence.

5 Logistic regression, Taylor approximation

The paper adapts logistic regression to additive homomorphic encryption by replacing the logistic loss with a second-order Taylor approximation. This enables encrypted gradient computation while requiring standardization and accepting approximation differences.

  • Additive homomorphic encryption requires approximating the logistic loss so gradients can be computed over encrypted values.
  • Logistic regression learns a linear model θ mapping feature vectors x to binary labels y from example-label pairs.
  • The second-order Taylor approximation balances precision against computational overhead, while higher-degree terms provide insufficient performance gains or unsuitable loss behavior.
  • The approximation around 0 is rough when |θ⊤x_i| is large, but feature standardization suffices for good performance in experiments.
  • The Taylor loss upper-bounds the logistic loss, so their values and minimizers are not directly comparable.
  • The encrypted mask is incorporated into the loss through masked statistics, while model-independent constant terms can be omitted during minimization.

6 Secure federated logistic regression

Federated learning splits the feature columns between providers and trains a shared logistic model using encrypted gradients after entity resolution aligns their rows. The coordinator receives encrypted updates rather than raw data.

  • After entity resolution, providers hold equally sized, row-aligned datasets whose columns form a vertically partitioned matrix X unavailable in one place.
  • The coordinator executes secure logistic regression with standard stochastic gradient descent while replacing raw-data computations with encrypted variants.
  • The coordinator generates the encryption key pair and sends the public key and encrypted entity mask to both providers before learning begins.
  • Secure gradients are computed for mini-batches, with the coordinator retaining prior gradients when the experiments use SAG optimization.
  • Only the model and mini-batch are sent in clear between providers; other messages are encrypted, and the coordinator receives only the encrypted gradient result.

7 Theoretical assessment of the learning component

The theoretical analysis characterizes how entity-resolution mistakes affect convergence, classification, empirical loss, and generalization. Under bounded, accurate permutations and calibrated data-model assumptions, these effects can vanish or remain limited.

  • 7.1 Convergence: Encrypted computation preserves the underlying arithmetic, while ridge-regularized Taylor loss enables strong-convexity convergence for SAG.The loss approaches its minimum at a rate approaching ρ^k, where k is the number of mini-batch updates and 0 < ρ < 1.
  • 7.2 Impact of entity resolution: parameters: Entity-resolution mistakes are modeled as an unknown permutation between the providers’ vertically partitioned records.The analysis tracks permutation size, class-mismatch permutations, and accuracy through parameters such as T, T+, ε, and τ.
  • 7.3 Impact on the optimal classifier: Under the stated conditions, the learned classifier’s normalized deviation from the optimal classifier converges to zero as the number of examples grows.The convergence depends on the permutation, data, and learning-problem parameters encoded in the theorem’s penalties and assumptions.
  • 7.4 Immunity of optimal large margin classification to P∗: Large-margin examples retain the optimal classifier’s class under entity-resolution mistakes, although their corresponding margins may change.This immunity is formalized under (ε, τ)-accuracy, α-boundedness, and data-model calibration assumptions.
  • 7.5 Empirical loss: The loss on true data converges to the optimal classifier’s loss at a rate roughly proportional to 1/n^α.The bound is governed by the same parameter-dependent quantity appearing in the classifier analysis.
  • 7.6 Generalization abilities for classifiers learned from E/R’ed data: Entity resolution affects generalization through a penalty term; if α ≥ 1/2, the E/R-free O(1/√n) convergence rate is retained.When α < 1/2, entity resolution may slow generalization convergence.

8 Experiments

Experiments evaluate the Taylor-loss approximation, scalability, and end-to-end predictive performance. The system achieves comparable test accuracy to logistic loss and perfectly linked logistic regression while scaling to large datasets.

  • End-to-end performance: Federated logistic regression scales to millions of rows in the order of hours per epoch.The overall experimental summary also reports comparable test-time accuracy and Taylor-loss convergence behavior.
  • Taylor vs. logistic: The Taylor loss converges at a similar rate to logistic loss and yields similar test-time accuracy despite different minima.This behavior is reported on MNIST with standardized features, constant learning rate η = 0.05, and ridge regularization Γ = 10−2I.
  • Scalability: Privacy-preserving entity resolution scales to datasets with up to 10M rows in a matter of hours.The matching workload is quadratic in dataset size because brute-force matching compares all possible row pairs, while the coordinator parallelizes these comparisons.
  • Scalability: Federated learning runtime grows linearly with both the number of examples and the number of features.Encrypted operations and communication of large ciphertexts form the system bottleneck, with encryption estimated to cause about a two-orders-of-magnitude slowdown.
  • End-to-end performance: The end-to-end system performs on par with logistic regression trained on perfectly linked data across accuracy, AUC, and F1-score.On PACS, the entity-matching algorithm incorrectly links around 1% of entities, and the reported mistakes are not detrimental to learning.

9 Conclusion

The paper presents a privacy-preserving federated linear-classification system for vertically partitioned data and formally analyzes entity-resolution errors. It reports confidentiality, scalability, accuracy, and limited impact from reasonable linkage mistakes.

  • Conclusion: The system pipelines privacy-preserving entity resolution with distributed logistic regression using Paillier encryption.Identifiers, records, and the linkage map remain confidential from other parties.
  • Conclusion: The system is described as the first scalable and accurate solution for this vertically partitioned learning problem.The protocol avoids adding extrinsic noise, while differential privacy could be applied on top when needed.
  • Conclusion: Under reasonable assumptions about entity-resolution mistakes, optimal classifiers, margins, and generalization remain largely stable.The paper states that generalization rates can remain of the same order and large-margin examples are unaffected.
  • Conclusion: The formal analysis suggests that entity-resolution errors need not fundamentally change the learning picture when their magnitude and size are reasonable.The analysis is presented as potentially useful for designing entity-matching methods targeted to learning.

Appendix

The appendix contains proofs and detailed material supporting the paper, with theorem and lemma numbering separated from the main text.

  • Appendix: Theorems and lemmata in the appendix use letters rather than the main file’s numbering.This convention distinguishes appendix results from the main-file numbering.

Paillier encryption scheme

The Paillier scheme supports encrypted addition and plaintext scalar operations, enabling arithmetic on protected values while keeping decryption with the private-key holder.

  • Paillier encryption scheme: Paillier uses a private key formed by large primes p and q and a public key m = pq.Plaintexts lie in Z_m, while ciphertexts lie in Z*_m^2.
  • Paillier encryption scheme: Encrypting the same plaintext with different random values produces multiple valid ciphertexts.The randomizer is freshly selected for each input, so ciphertexts do not uniquely identify a plaintext.
  • Paillier encryption scheme: The operator [[x]] ⊕ [[y]] computes an encryption of x + y without decrypting either operand.This additive homomorphism is extended to linearity and scalar multiplication.
  • Paillier encryption scheme: Multiplying an encrypted value by a small-set plaintext can expose that plaintext through guess verification.Adding an encryption of zero changes the random multiplier and protects the plaintext factor.
  • Paillier encryption scheme: Encrypted vectors support component-wise operations, plaintext scalar multiplication, Hadamard products, and compatible matrix multiplication.For example, encrypted Ax can be computed from encrypted x and plaintext A.
  • Paillier encryption scheme: Decryption requires the private-key holder and costs computationally about one modular exponentiation modulo m.The protocol therefore sends encrypted results to the party holding the private key for plaintext recovery.

II Encoding

The encoding maps floating-point values to a significand–exponent representation compatible with Paillier arithmetic, trading exact exponent secrecy for a broad numeric range.

  • II Encoding: Each fraction is represented as q = sβ^e, where s is the significand and e is the exponent.Addition aligns exponents, while multiplication multiplies significands and adds exponents.
  • II Encoding: The significand is restricted to 0 ≤ s < m so encoded values fit Paillier’s plaintext space.This limits precision to log2 m bits, which the paper considers acceptable for a 1024-bit-or-larger key.
  • II Encoding: The encoding supports a very large range of values compared with fixed-point encoding.It is based on floating-point representation and handles IEEE 754 single- and double-precision inputs.
  • II Encoding: 53-bit inputs can support 19 multiplications by 53-bit numbers before overflow might occur with the stated key capacity.Overflow cannot be detected in the described scheme; reserved intervals offer only a partial workaround.
  • II Encoding: The significand is encrypted but the exponent remains public, revealing each encrypted number’s order of magnitude.The leakage can be mitigated by choosing a larger base or fixing the exponent.
  • II Encoding: Addition preserves the leakage range β, whereas multiplication expands it to β^2.The paper notes that multiplication therefore mitigates the leakage by a factor of β.

III.1 Secure loss initialization

The section describes secure loss computation and the visibility boundaries among the coordinator and data providers. It also connects the protocol to encrypted linear-algebra operations and analyzes how linkage errors affect learned classifiers.

  • Data visibility: The coordinator sees only the final loss, while B receives encrypted intermediate values and neither party accesses the other provider’s raw data.Additively homomorphic encryption protects A’s values from B and vice versa, while protection from C relies on sharing only computed values.
  • Security evaluation: The model itself and its iterative computation remain unprotected channels for information leakage.This limitation is distinct from the protections applied to exchanged data and entity matching.
  • Security evaluation: Revealing clear gradients can leak the number of matched entities in a mini-batch or even a corresponding label.The protocol mitigates this risk by choosing the batch size carefully; the match count follows a hypergeometric distribution.
  • Effect of entity-resolution errors: The mean operator is invariant to permutations within classes, so only cross-class permutation errors contribute to classifier drift.The optimal classifier for the Taylor loss is a linear mapping of the mean operator.
  • Effect of entity-resolution errors: Under the invertibility assumption, theorems characterize classifier deviations for arbitrary sequences of permutation matrices.The resulting expressions support bounds on the distance between classifiers beyond the privacy setting.
Loading 1711.10677v1…