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

• The first contribution is an end-to-end protocol for two providers jointly performing logistic regression over vertically partitioned data without exchanging raw data or revealing shared entities.A coordinator manages privacy-preserving entity resolution and additively homomorphic encryption.Source: §1 · p. 2
• The second contribution is the first formal study of how entity-resolution errors affect learning, addressing an overlooked risk in linking vertically partitioned databases.The motivation includes error-prone matching and documented cases where exact matching missed 25% of true matches [Schnell, 2013, Winkler, 2009].Source: §1 · pp. 2–3
• Wrongly linking examples from different classes can damage the optimal classifier significantly more than wrongly linking examples from the same class.Source: §1 · p. 3
• Under reasonable assumptions, large-margin examples retain their optimal classifications despite entity-resolution mistakes.Examples receiving a large-margin classification from the optimal classifier still receive the same class from the learned classifier using mistake-prone resolved data.Source: §1 · p. 3
• The empirical-loss bounds converge at a rate of order 1/n^α, with α ∈(0, 1] assumption-dependent and penalties tied to the classifier, entity resolution, and class statistics.Source: §1 · p. 3
• When entity-resolution mistakes are sufficiently few, generalization rates are not notably affected, supporting federated learning when database aggregation substantially improves classification accuracy.Source: §1 · p. 3

• Federated learning keeps data at providers while this work addresses vertically partitioned logistic regression with additional privacy requirements and entity-resolution errors.The setting protects provider privacy against a central aggregator and assumes entity resolution has a given error rate.Source: §2 · p. 4
• Differential privacy protects individuals by making outputs insensitive to example inclusion, but calibrated noise generally degrades predictive performance [Dwork, 2008, Dwork and Roth, 2014].Such methods add noise to algorithms or data [Chaudhuri and Monteleoni, 2009, Duchi et al., 2013].Source: §2 · p. 4
• The paper instead uses cryptographic guarantees, including additively homomorphic encryption, trading computational cost for preserved predictive power.Related cryptographic frameworks include Paillier, Brakerski-Gentry-Vaikuntanathan cryptosystems, garbled circuits, and secret sharing.Source: §2 · p. 4
• Most secure distributed-learning research uses horizontal partitions, whereas vertical partitions require more complex and expensive protocols.Prior vertical methods include logistic regression [Wu et al., 2013], Paillier-based featurewise p-values [Duverle et al., 2015], hybrid secure linear regression [Gascón et al., 2017], and multi-model protocols using secret sharing, garbled circuits, and oblivious transfer [Mohassel and Zhang, 2017].Source: §2 · p. 4
• Earlier secure-learning papers generally assume known row correspondences and do not address entity resolution, despite unstable or erroneous identifiers making matching necessary in realistic vertical settings.Privacy-preserving entity resolution is itself an established research area [Hall and Fienberg, 2010, Christen, 2012, Vatsalan et al., 2013a].Source: §2 · p. 4
• Sufficient-statistics methods can approximate optimal models without exact entity resolution, but Patrini et al. [2016b] requires labels shared among all parties and offers less comprehensive theoretical guarantees than this work.These approaches use weak entity resolution between groups sharing feature subsets [Nock et al., 2015, Nock, 2016, Patrini, 2016, Patrini et al., 2016b].Source: §2 · p. 5

Security model

• The security model assumes honest-but-curious, non-colluding participants who follow the protocol while attempting to infer information from received messages.The third party holds the decryption key but receives only encrypted model updates, considered non-private in this setup.Source: §3 · p. 5

Privacy constraints

• Providers’ raw sensitive data and knowledge of common entities—including their count—remain private, while schemas and secure communication channels are public assumptions.Providers may use their own unencrypted records locally whenever useful.Source: §3 · p. 5

Additively homomorphic encryption

• Additively homomorphic encryption enables addition of ciphertexts and multiplication of ciphertexts by plaintexts, but not multiplication of two ciphertexts, preserving encrypted intermediate results.These operations extend component-wise to vectors and matrices, enabling linear-algebra primitives for machine learning; Paillier is cited as an example [1999].Source: §3 · p. 6
• Floating-point computation requires encoding numbers as modular integers using an encrypted significand and unencrypted exponent, with limitations described in Appendix II.The encoding preserves addition and multiplication needed by the algorithms.Source: §3 · p. 6

Limitations

• 2m bits per encoded floating-point ciphertext and additions two to three orders of magnitude slower than plaintext quantify Paillier’s overhead, although engineered implementations remain tractable for many real-world problems.Here, m is typically at least 1024.Source: §3 · p. 6

• Entity resolution is required to learn jointly from vertically partitioned features when shared unique IDs are unavailable across organisations.Source: §4 · p. 6
• Cryptographic longterm keys encode multiple identifiers as Bloom filters, with Dice coefficient similarity computed from matching hashed n-gram bits.The approach protects weak identifiers that would otherwise be shared directly; insecure parameters or too few hashed identifiers can enable cryptanalytic attacks [Kuzu et al., 2011, 2013, Niedermeyer et al., 2014].Source: §4 · pp. 6–7
• A third party greedily selects the most similar CLK pairs, producing row permutations and a mask that identify matched entities for learning; blocking can accelerate comparisons.The matching step evaluates all possible CLK pairs, whose count equals the product of the dataset sizes before optional blocking.Source: §4 · p. 7
• The third party encrypts the mask with Paillier before sending it to both providers, preserving whether entities match because match status can reveal sensitive information.The mask is integrated into private learning as a novel contribution, while the longer dataset is truncated to matched rows and its owner learns which rows lack correspondence.Source: §4 · pp. 7–8

Setup

• The method learns a linear model for binary labels and adapts logistic-loss gradients to additive homomorphic encryption, initially in a centralized setting.The federated learning protocol is deferred to Section 6.Source: §5 · p. 8

Optimization

• Training computes encrypted gradients, while hold-out loss monitoring and ridge regularization combat overfitting and support early stopping.The hold-out loss is evaluated on a separate set H.Source: §5 · p. 9

Taylor loss

• A second-order Taylor expansion approximates the logistic loss and yields the corresponding mini-batch gradient required for encrypted computation.The resulting objective is called the Taylor loss.Source: §5 · p. 9
• The second-order approximation balances precision and computational overhead: third order is equivalent, fourth and fifth orders are unsuitable, and sixth order is costly without significant gains.Fourth- and fifth-order approximations can take negative values, preventing suitable minimization.Source: §5 · pp. 9–10

Approximation limits

• Because the expansion is centered at zero, approximation quality degrades when |θ⊤x_i| is large; feature standardization is sufficient for good performance, although Taylor and logistic losses have different minimizers.The logistic loss is bounded above by the Taylor loss, so their values are not directly comparable.Source: §5 · p. 10

Applying the encrypted mask

• The encrypted mask is incorporated by multiplying each loss term by its encrypted mask, producing masked gradients and masked hold-out loss for privacy-preserving training.The model-independent constant in the masked loss can be set to zero without affecting minimization.Source: §5 · p. 10

• Secure logistic regression runs SGD on vertically partitioned data, with providers A and B holding separate feature columns and A holding the labels.After entity resolution, both datasets have n aligned rows, while the complete matrix X remains distributed across providers.Source: §6 · p. 10
• Secure gradient computation is the computational bottleneck, replacing raw-data operations with encrypted variants while enabling standard stochastic optimization and Taylor-loss early stopping.The implementation chooses SAG for experiments, caches prior gradients, and evaluates loss rather than hold-out error because encrypted error computation is too costly.Source: §6 · pp. 10–11
• Coordinator C generates the cryptosystem keys and distributes the public key and encrypted mask, hiding hold-out and mini-batch sampling from C.The protocol uses an additively homomorphic encryption scheme and supports secure initialization and stopping through a common hold-out.Source: §6 · pp. 10–11
• Only the model and mini-batch are shared in clear between A and B; all other messages remain encrypted, and C receives only the aggregated gradient.The appendix additionally evaluates potential information leakage from the protocols.Source: §6 · p. 12

7 Theoretical assessment of the learning component

• Overall, the theory establishes that entity-resolution errors need not substantially impair learning when their magnitude, size, and cross-class proportion remain controlled under the stated calibration assumptions.The analysis covers classifier deviation, margins, empirical Taylor loss, and generalization ability.Source: §7 · p. 12, §7.2 · p. 13, §7.2.2 · p. 16

7.1 Convergence

• Encrypted computation preserves the underlying arithmetic, so ridge-regularized SAG on the second-order Taylor loss converges toward the empirical optimum at a geometric rate approaching ρ^k.Here, 0 < ρ < 1 and k is the number of mini-batch updates.Source: §7.1 · p. 13

7.2.1 Modelling entity resolution mistakes

• Entity-resolution mistakes are modeled as an unknown permutation between providers, decomposed into T elementary swaps, including T+ swaps that cross label classes.The factorization always exists with T ≤ n, and the data provider holding labels is provider A.Source: §7.2.1 · pp. 13–14

7.2.2 Assumptions on permutations and data

• The analysis assumes permutations are accurate in magnitude and bounded in size, while data and model parameters satisfy calibration conditions; its results depend on δm, δρ, and δµ.The bounded-size condition roughly requires T = o(√n) in the worst case, while accuracy controls directional permutation errors.Source: §7.2.2 · pp. 14–16

7.3 Relative error bounds for ˆθ∗vs θ∗

• Under accurate permutations and calibrated data, the relative classifier error ∥ˆθ∗−θ∗∥2/∥θ∗∥2 converges to zero, faster when classification gain δm/δρ is larger.Learning tolerates larger permutations when the proportion ρ of cross-class elementary permutations decreases, guiding entity-resolution trade-offs.Source: §7.3 · pp. 16–17

7.4 Immunity of optimal large margin classification to P∗

• Under Theorem 6’s conditions, optimal large-margin classification is immune to permutation errors at margin κ: examples with optimal margin above κ retain their predicted class.The immunity condition links sample size n, permutation effects ξ, and margin κ; increasing n without worsening ξ can reduce the minimum immune margin.Source: §7.4 · p. 17

7.5 Bound on the difference of Taylor losses for θ∗vs ˆθ∗on the true data

• On true data, the entity-resolved classifier’s Taylor loss differs from the optimal classifier’s by o(1), with convergence governed by C(n) and roughly proportional to 1/n^α.Unlike the margin-immunity bound, this loss bound also depends on the normalized class sufficient statistic δµ.Source: §7.5 · p. 18

7.6 Generalization abilities for classifiers learned from E/R’ed data

• With high probability, generalization is affected by entity resolution only through penalty U(n); if α ≥ 1/2, the E/R-free slow-rate convergence O(1/√n) is preserved.For smaller α, entity resolution may slow generalization convergence.Source: §7.6 · p. 18

Taylor vs. logistic

• Taylor loss converges at a similar rate to logistic loss, with test-time accuracy comparable and accuracy and AUC differences of at most 1.8 points across UCI datasets.Both losses converge to different minima and minimizers, but their resulting test accuracy is similar.Source: §8 · p. 19, Table 2 · p. 20

Scalability

• The scalability experiments use the 160K-example PACS benchmark, vertically split across two providers, then upsampled and augmented with feature products.Implementations ran on separate 16-core, 60GiB AWS machines using 1024-bit Paillier encryption.Source: §8 · p. 19
• Privacy-preserving entity resolution scales quadratically with dataset size because brute-force matching compares all row pairs, yet handles datasets up to 10M rows in hours.The matching workload is embarrassingly parallel across the coordinating party’s cluster.Source: §8 · pp. 19–20
• Federated learning runtime grows linearly with both rows and features per epoch, with encrypted operations and communication forming the system bottleneck.Encryption was estimated to cause a slowdown of about two orders of magnitude.Source: §8 · p. 20

Benchmark

• The end-to-end system performs exactly on par with logistic regression on perfectly linked data for accuracy, AUC, and f1-score, despite around 1% wrongly linked entities.This supports that matching mistakes are not detrimental for learning; the fraction of shared entities also appears not to matter.Source: §8 · pp. 20–21, Table 3 · p. 21

9 Conclusion

• The end-to-end system keeps records, linkage identifiers, and the linkage map confidential while combining entity resolution with distributed logistic regression under Paillier encryption.The authors describe it as a scalable and accurate solution that adds no extrinsic privacy noise, although differential privacy could be layered on when model attacks are a concern.Source: §9 · p. 21
• The theoretical analysis finds that reasonable entity-resolution mistakes need not change learning qualitatively, with generalization rates remaining of the same order and large-margin examples retaining their optimal-classifier labels.Because federated learning can substantially improve the optimal classifier by expanding the feature set, the authors argue it can be extremely beneficial when each peer materially uplifts the other.Source: §9 · p. 21

Appendix

• The appendix distinguishes theorem and lemma numbering with letters to separate them from the main-file numbering.Source: Appendix · p. 25

I Paillier encryption scheme

• Paillier encryption provides additive homomorphism over Z_m, supporting encrypted addition, plaintext scalar multiplication, vector operations, dot products, and compatible matrix multiplication.Operations inside encryption are modulo m in plaintext space, while ciphertext operations are modulo m^2; multiplying by an unencrypted value requires rerandomization to protect that value.Source: I Paillier encryption scheme · pp. 26–27

II Encoding

• The encoding represents floating-point values as base-β significand–exponent pairs, preserving a large value range while constraining significands to the Paillier plaintext space.With 53-bit inputs and a 1023-bit key range, the scheme can accumulate 19 multiplications before overflow might occur, but overflow is not detectable in the basic scheme.Source: II Encoding · pp. 27–28
• The encoding leaves exponents public, leaking each encrypted number’s order of magnitude within a factor of β, while overflow and leakage remain limitations of the representation.Larger bases or fixed exponents can mitigate magnitude leakage, but addition and multiplication have different effects on the leakage range.Source: II Encoding · p. 28

Secure loss initialization

• Secure loss initialization caches encrypted hold-out quantities independent of θ, so later secure logistic-loss evaluations can reuse them without revealing the underlying data.B receives encrypted target-related and feature-derived values and retains the resulting encrypted µ_H without sending it to C.Source: Secure loss initialization · p. 29, II Encoding · p. 29

Secure logistic loss

• Secure logistic loss is evaluated once per outer-loop iteration from encrypted intermediate values, while C sees only the final loss ℓ_H(θ) and B receives encrypted model-dependent values.Correctness follows from constructing encrypted quadratic terms and combining them with the previously cached encrypted µ_H to approximate the logistic loss.Source: Secure logistic loss · pp. 29–30

IV Security evaluation

• Entity matching uses random permutations and a mask to hide matched entities from A and B, while cryptographic linkage constructions protect A’s and B’s information from C.Additively homomorphic encryption protects each provider’s data from the other, whereas C receives only computed values such as the shared gradient.Source: IV Security evaluation · p. 31
• The protocol does not protect against information leakage through the model or its iterative computation.This limitation remains despite the other data-protection mechanisms.Source: IV Security evaluation · p. 31
• A mini-batch’s revealed gradient can disclose match information or labels, although batch-size selection and coordinator checks can mitigate this leakage.Zero gradients can reveal no common entities in a batch, while a single match can reveal its label; the match count follows a hypergeometric distribution.Source: IV Security evaluation · p. 31
• The public exponent in encrypted-number encoding leaks information about plaintexts, and increasing the base can reduce but not eliminate this unnecessary leakage.The authors note that fixed-point encoding is a planned alternative.Source: IV Security evaluation · pp. 31–32

V.1 Notations

• The proofs distinguish the ideal sample S from the error-prone training sample ˆS and represent linkage errors as permutations affecting the shuffle feature space.The observation matrix is transposed so observations occupy columns, while labels associated with A remain unaffected by permutations on B.Source: §V.1 · pp. 32–33
• The mean operator is invariant to within-class permutations, so when permutations separately preserve positive and negative classes, classifier drift arises only from mistakes in the linear mapping.The optimal Taylor-loss classifier is a linear mapping of the mean operator.Source: §V.1 · p. 33
• The notation defines elementary permutation pairs, matrices that quantify local mistakes, and vectors measuring successive changes in mean operators for the proof’s linear-algebraic analysis.The construction also includes regularization matrices, doubly indexed matrices, and key vectors used in the helper theorem.Source: §V.1 · pp. 33–35

V.2 Helper Theorem

• Theorem P expresses the difference between successive optimal classifiers as Λ_tθ∗, regardless of the permutation-matrix sequence.The expression uses Λ_t, ε_t, and λ_t as defined in the cited equations.Source: §V.2 · p. 36
• Lemma O characterizes existence of V_t from V_{t−1}, with the proof relying on permutation updates, Sylvester’s determinant formula, and Sherman–Morrison inversion.The condition is derived after tracking the affected shuffle observations while XA remains unchanged.Source: §V.2 · pp. 36–38
• The complete sequence of matrices V_t and optimal classifiers exists when V_0 exists and the stated invertibility condition is satisfied.The paper notes that V_0 exists by taking γ > 0 and Γ ≻ 0.Source: §V.2 · p. 38
• Under the invertibility assumption, Theorem Q gives the cumulative deviation of the optimal classifier from the error-free classifier for any T ≥ 1.Because the result applies to every permutation matrix, it also applies to every entity-resolution algorithm.Source: §V.2 · pp. 40–41

V.3 Assumptions: details and discussion

• The remaining assumptions are described as weak, requiring regularization strength proportional to a squared norm and data size no smaller than a potentially small constant.The discussion also notes conditions involving observation norms and homogeneity of γλ_1(Γ).Source: §V.3 · pp. 41–42
• The (ε, τ)-accuracy assumption bounds projected shuffle-space errors by ε times corresponding observation stretch plus τ.It also bounds permutation-induced error stretch by the maximal stretch of the related observations affected by the permutation.Source: §V.3 · p. 41
• The additive parameter τ is necessary because an observation can have zero projection along a direction while its shuffle error has nonzero projection.The anchor parts coincide, so the relevant error stretch is measured in the shuffle features.Source: §V.3 · pp. 41–42

• Corollary W shows that (ε, τ)-accuracy and data-model calibration imply the invertibility assumption for every t ≥1.Lemma V yields (1 − c1,t)^2 > 121/144 > 1/144 > c0,tc2,t > 0.Source: §V.4 · p. 50
• Lemma X establishes Id + Λt ≻ 0 and Vt ≻ 0 under (ε, τ)-accuracy and data-model calibration, ensuring Λt has only real eigenvalues.The proof combines Lemmas T, U, and V to control the eigenvalues and show strict positivity.Source: §V.4 · pp. 50–51
• For T elementary permutations, the proof bounds accumulated deviation by 1 (HT,0 − Id) ≤ (1 + q)^T − 1 ≤ T^2q.The estimate uses qk ≤ (Tq)^k ≤ Tq when Tq ≤ 1, a condition implied by α-bounded permutation size and calibration.Source: §V.4 · pp. 51–52
• Theorem Y assumes P* is (ε, τ)-accurate and α-bounded, with data-model calibration, and asserts a bound holding for all T ≥1.Its proof invokes Theorem Q and bounds the effect of repeated elementary permutations.Source: §V.4 · p. 51

Proof of Theorem 6

• The permutation-induced shift in the mean operator is zero when an elementary permutation exchanges observations from the same class.The shift depends only on between-class mistakes, and the derived expression gives ∥ε_t∥2 = 0 for within-class permutations.Source: §V.4 · pp. 52–53
• Assuming at most T errors, the proof bounds the remainder term by placing all between-class errors at the final elementary permutations, then applies α-boundedness to complete the result.The argument uses T+ ≤ T and ξ/n as the relevant factor before concluding the proof through Theorem Y.Source: §V.4 · pp. 53–54
• Theorem 6 follows from the proof of Theorem Y after establishing the theorem’s stated bound in (187).The upper bound uses a factor no larger than (ξ/n)^α under the stronger α-boundedness constraint.Source: §V.4 · pp. 52, 54

V.5 Proof of Theorem 8

• Theorem 8 follows by applying the Cauchy–Schwarz inequality to each example.Source: §V.5 · pp. 54–55

V.6 Proof of Theorem 9

• Theorem 9 analyzes the loss difference between the true-data optimum and the classifier learned from entity-resolved data.Source: §V.6 · p. 55
• The proof derives the bound through elementary algebra and the Cauchy–Schwarz inequality.Source: §V.6 · p. 55
• Theorem Y is then invoked to obtain the stated bound for Theorem 9.Source: §V.6 · p. 55
• The bound includes the optimal classifier’s maximum margin and a class-mismatch penalty δρ .= √ξρ/4.Source: §V.6 · p. 55
• The proof also defines the normalized mean-operator for the true dataset as a quantity in [0, 1].Source: §V.6 · p. 56
• The final algebraic expression contains terms involving δµ0, δm, δρ, and C(n).Source: §V.6 · p. 56
• Using data-model calibration, the proof establishes C(n) ≤(1/4)α ≤1 and concludes Theorem 9.Source: §V.6 · p. 56

V.7 Proof of Theorem 10

• Entity resolution in the vertical-partition setting preserves the validity of empirical upper bounds on the maximum observation norm used in the Rademacher-complexity analysis.The bound remains computable using the observed dataset rather than the optimal matched dataset.Source: §V.7 · p. 57
• Using Theorem 9 and [Bartlett and Mendelson, 2002, Theorem 7], the argument establishes Theorem 10 for the Lipschitz Taylor loss with probability ≥1 −δ over S ∼Dn.Source: §V.7 · pp. 58–59

VI Cryptographic longterm keys, entity resolution and learning

• Cryptographic longterm keys hash input objects into Bloom filters, setting at most hs of l bits using h hash functions and s objects.This two-phase construction first hashes objects and then repeatedly hashes their binary codes into the filter.Source: VI Cryptographic longterm keys, entity… · p. 59
• CLK similarity uses the Dice coefficient D(z, z′), with a learned threshold τ determining when two encoded inputs represent the same entity.The coefficient lies in [0, 1], and pairs above the threshold are treated as matches.Source: VI Cryptographic longterm keys, entity… · p. 59
• When two entities have identical, error-free inputs, their CLKs attain Dice coefficient 1 and are therefore recognized as the same entity for every applicable threshold.This is the key exact-match property of the CLK representation.Source: VI Cryptographic longterm keys, entity… · p. 60
• For binary CLK representations, the worst stretch direction is proportional in absolute value to the XOR pattern between the observed and true Bloom-filter vectors.The analysis focuses on the CLK features shared with provider B and derives the direction maximizing the stretch.Source: VI Cryptographic longterm keys, entity… · p. 60
• Under the simplifying assumption of exactly hs set bits, the analysis suggests that suitable observation norms may yield δ > 0 with (ε, δ)-accuracy for ε < 1.The estimate uses √2 − 1 ≈ 0.414, while omitting other features and considering only maximizing directions.Source: VI Cryptographic longterm keys, entity… · p. 60
• Despite its simplifications, the analysis indicates that CLK-based entity resolution may be useful not only for privacy but also for learning in the vertical setting.The conclusion is explicitly qualified by ignoring non-Bloom-filter features and restricting the analyzed directions.Source: VI Cryptographic longterm keys, entity… · p. 60