# Is Vertical Logistic Regression Privacy-Preserving?
A Comprehensive Privacy Analysis and Beyond

Yuzheng Hu  UIUC<EMAIL_ADDRESS>,  Tianle Cai  Princeton University
<EMAIL_ADDRESS>,  Jinyong Shan  Sudo Technology Co.,LTD
<EMAIL_ADDRESS>,  Shange Tang  Princeton University
<EMAIL_ADDRESS>,  Chaochao Cai  Sudo Technology Co.,LTD
<EMAIL_ADDRESS>,  Ethan Song  Sudo Technology Co.,LTD
<EMAIL_ADDRESS>,  Bo Li  UIUC<EMAIL_ADDRESS>and  Dawn Song  UC
Berkeley<EMAIL_ADDRESS>
###### Abstract.

We consider vertical logistic regression (VLR) trained with mini-batch
gradient descent — a setting which has attracted growing interest among
industries and proven to be useful in a wide range of applications including
finance and medical research. We provide a comprehensive and rigorous privacy
analysis of VLR in a class of open-source Federated Learning frameworks, where
the protocols might differ between one another, yet a procedure of obtaining
local gradients is implicitly shared. We first consider the honest-but-curious
threat model, in which the detailed implementation of protocol is neglected
and only the shared procedure is assumed, which we abstract as an oracle. We
find that even under this general setting, single-dimension feature and label
can still be recovered from the other party under suitable constraints of
batch size, thus demonstrating the potential vulnerability of all frameworks
following the same philosophy. Then we look into a popular instantiation of
the protocol based on Homomorphic Encryption (HE). We propose an active attack
that significantly weaken the constraints on batch size in the previous
analysis via generating and compressing auxiliary ciphertext. To address the
privacy leakage within the HE-based protocol, we develop a simple-yet-
effective countermeasure based on Differential Privacy (DP), and provide both
utility and privacy guarantees for the updated algorithm. Finally, we
empirically verify the effectiveness of our attack and defense on benchmark
datasets. Altogether, our findings suggest that all vertical federated
learning frameworks that solely depend on HE might contain severe privacy
risks, and DP, which has already demonstrated its power in horizontal
federated learning, can also play a crucial role in the vertical setting,
especially when coupled with HE or secure multi-party computation (MPC)
techniques.

Vertical logistic regression, federated learning, homomorphic encryption,
differential privacy, label recovery attack

††copyright: none††conference: ACM Conference on Computer and Communications
Security; Due 15 May 2019; London, TBD††journalyear: 2022††ccs: Security and
privacy Privacy-preserving protocols††ccs: Security and privacy Privacy
protections††ccs: Computing methodologies Machine learning

##  1\. Introduction

Recent years have witnessed the advancement of Artificial Intelligence (AI) in
a wide range of tasks, such as image recognition (He et al., 2016), natural
language processing (Devlin et al., 2018), recommendation (Gharibshah et al.,
2020) and game (Silver et al., 2016). These achievements crucially rely on the
availability of massive amount of labeled data. Across various industries,
however, data are usually distributed over multiple places in different forms,
and most organizations only possess partial or limited amount of unlabeled
data due to the heavy cost of annotation. Further, it has been increasingly
difficult for organizations to share and cooperatively use their data from a
legislative perspective owing to regulations like General Data Protection
Regulation (GDPR) (Voigt and Von dem Bussche, 2017) and California Consumer
Privacy Act (CCPA) (CCPA, 2018), which enforce strict requirements on the use
of data in order to protect individuals’ privacy.

To address this issue, the concept of federated learning (FL) was proposed by
Google (Konečnỳ et al., 2016a, b; McMahan et al., 2016) in 2016, aiming to
build machine learning models across multiple decentralized parties without
revealing their raw data. Over the past few years, there is an increasing
concern towards privacy and security within both academia and industry, and FL
has been widely adopted in finance (Liu et al., 2020a), medical research
(Jochems et al., 2016), smart phones (Hard et al., 2018) and so on. Meanwhile,
several open source FL systems have been developed, including TensorFlow
Federated (TFF) (Authors, 2019d) by Google, Federated AI Technology Enabler
(FATE) (Authors, 2019a) by Tencent Webank, PySyft (Ryffel et al., 2018) by
Openmined, LEAF (Caldas et al., 2018) by CMU and PaddleFL (Authors, 2019c) by
Baidu. The convenience brought by these frameworks makes FL the mainstream
paradigm for proprietary entities to learn jointly across their geographical
boundaries.

Based on the distribution characteristics of data, FL can be categorized into
horizontal federated learning (HFL) and vertical federated learning (VFL)
(Yang et al., 2019). HFL is a system in which all participants share the same
feature space, but the sample space could be significantly different. For
example, a set of domestic banks may share a similar financial profile,
however very few common customers. In such case, HFL can be applied to
agglomerate models learnt in each individual banks. In VFL (a.k.a. split
learning), participants first align their user ID to ensure a common sample
space, then jointly train a model based on the aggregation of different
features. For example, banks and fund companies may own different perspectives
of a customer’s financial status, so they can perform better risk management
leveraging the information from multiple dimensions.

While FL came up as a promising solution to preserve users’ privacy, potential
risk of data leakage has been recognized under this new paradigm, which may
hinder its widespread adoption. The main observation is that, although the raw
data stays untouched, the exchange of intermediate values within the execution
of FL framework, might reveal much private information even with cryptography
algorithm. Zhu and Han (Zhu and Han, 2020) show that it is possible to learn
from gradients and recover the original input as long as the batch size is
small; Zhao et al. (Zhao et al., 2020) further show that the label can be
directly inferred from the gradients. Other forms of attack include membership
inference (Nasr et al., 2019), in which the adversary aims to learn whether a
given sample belongs to another participant; property inference (Melis et al.,
2019), where the adversary intends to learn data properties that are
independent of the main task; and model poisoning/backdoor attack (Bhagoji et
al., 2019; Bagdasaryan et al., 2020), with the goal of causing the global
model to misclassify a set of chosen inputs. As FL is gaining more popularity
within the AI community, privacy analysis of the current FL frameworks has
become one of the most important research directions, which could potentially
lead to the improvement over existing algorithms and protocols.

It has come to our attention that a major study of the privacy analysis of FL
focuses on HFL, whereas the corresponding work on VFL lacks, albeit VFL is
being widely used in industry (Wang, 2019; Feng and Yu, 2020; Gu et al., 2020;
Webank, 2019a, b). As far as we know, there are only a few exceptions: Weng et
al. (Weng et al., 2020) propose reverse multiplication attack and reverse sum
attack for logistic regression and Secure XGBoost (Cheng et al., 2021) in the
VFL setting and demonstrate the privacy leakage of feature and partial order;
Luo et al. (Luo et al., 2021) study feature attack with similar models in the
prediction phase. However, the theoretical analyses are either not rigorous or
based on unrealistic assumptions; further, none of these works consider the
privacy of labels of training instances, which is a crucial part of the raw
data. Recently, Liu et al. (Liu et al., 2020b) point out that the label can be
inferred from the sign of gradients, but this is just a simple extension of
(Zhao et al., 2020) in the vertical setting and does not hold when using an
approximate version of the cross-entropy loss. Li et al. (Li et al., 2022)
consider the model-agnostic split learning, and propose a norm-based approach
and a direction-based approach to identify the labels based on the information
of per-sample gradient during training; however, their analyses relies on
certain heuristics regarding the behavior of the model and is restricted to
the two-party case.

Aiming to provide an in-depth understanding of a specific model, we focus on a
popular setting in VFL, where two (or multiple) parties collaboratively train
a logistic regression model using mini-batch gradient descent, with separated
features and labels owned by only one of them (Hardy et al., 2017). We refer
to the setting as vertical logistic regression (VLR). Though being simple, VLR
has attracted growing interest among industries and proven to be useful in
many practical settings such as risk control (Chen et al., 2021), credit
scoring, (Zheng et al., 2020) and clinical diagnosis (Wu et al., 2013). Also,
while this setting has been studied by (Weng et al., 2020; Luo et al., 2021)
as mentioned above, our work tends to provide a comprehensive and rigorous
understanding of the training framework, which could potentially serve as a
useful guideline for practice.

Specifically, starting from the two-party scenario and assuming an oracle of
obtaining local gradients which is actually being deployed in practice
(Authors, 2019b), we provide a fine-grained privacy analysis for both parties,
and propose attacks on both feature and label levels under suitable conditions
of batch size. For feature attack we come up with a corresponding hardness
result, and for label recovery attack we show it naturally generalizes to the
multi-party scenario. We then take into account the protocol of obtaining
gradients based on Homomorphic Encryption (HE), and propose an active attack
via generating and compressing auxiliary ciphertext, which allows us to relax
the constraints of batch size. See Figure 1 for an illustration of our privacy
analysis. We proceed to develop a countermeasure based on Differential Privacy
(DP) against the proposed attack, and provide utility and privacy guarantees
for the updated algorithm. Finally, we verify the effectiveness of our attack
and defense on benchmark datasets, indicating the fundamental weakness in
existing frameworks as well as the power of coupling DP with HE techniques in
VLR.

Figure 1. Illustration of our privacy analysis. Under a general oracle of
obtaining local gradients and some constraints on batch size, Party $A$ can
steal $B$’s single-dimension feature, whereas $B$ can steal $A$’s labels.
Within a specific HE-based protocol, both parties can perform the same attacks
with less constraints on batch size. Differential Privacy serves as a simple-
yet-effective countermeasure to the proposed attacks.

The main contributions of this paper are summarized as follows:

  * •

We provide a fine-grained privacy analysis of VLR in the honest-but-curious
setting: under suitable conditions of batch size, 1) for Party $A$, we
construct a feature attack when $B$ has single-dimension feature and provide a
hardness result for the rest case; 2) for Party $B$, we identify a label
recovery attack when the initialization is small. We also show that the label
recovery attack can naturally generalize when there are multiple parties. Our
attack is strong in the sense that we (i) assume no prior knowledge of the
data; (ii) make no assumptions on the model’s accuracy; (iii) do no resort to
external tools such as learning-based algorithm; it holds (iv) independently
of the existence of the third party and (v) can be performed at any time
during training. It only requires the knowledge of intermediate gradients, and
is formalized via a careful dissection of the linear system;

  * •

We then consider the active adversarial model: by taking into account the
specific implementation of protocol based on Homomorphic Encryption (HE), we
propose an active attack via generating and compressing auxiliary ciphertext,
which allows us to relax the constraints of batch size and greatly extend the
range of applications;

  * •

We develop a simple-yet-effective countermeasure for the proposed attack based
on Differential Privacy (DP), which is realized by injecting Gaussian noise to
the HE-based protocol. While DP appears as a standard building block in HFL
(Geyer et al., 2017; Truex et al., 2019; Wei et al., 2020), to the best of our
knowledge, we are the first to couple it with HE techniques in the vertical
setting. We also provide both utility and privacy guarantees for the updated
algorithm;

  * •

Experiment results on benchmark datasets verify the effectiveness of our
proposed attack and defense, and showcase both the potential weakness of
general VFL frameworks that solely rely on HE, as well as the capability of
coupling DP with HE or MPC techniques to achieve better performance in terms
of data privacy.

The rest of the paper is organized as follows: Section 2 is our preliminary.
We provide privacy analysis for Party $B$ and $A$ in Section 3 and 4
respectively. We then introduce the protocol of obtaining gradients and
propose an active attack in Section 5. Section 6 describes our countermeasure
and provides theoretical guarantees for both privacy and utility. In Section 7
we conduct experiments on benchmark datasets to evaluate our attack and
defense. We conclude our work in Section 8.

###  1.1. Related Works

##### Privacy Leakage of Federated Learning.

Identifying the privacy leakage of FL has seen a growing interest over the
past years. Among them, a major set of works consider the setting of HFL,
while only a few exceptions involve the privacy analysis of VFL (Weng et al.,
2020; Luo et al., 2021; Liu et al., 2020b; Li et al., 2022). Within HFL, data
leakage attracts the most attention: (Hitaj et al., 2017; Wang et al., 2019)
use GAN (Goodfellow et al., 2014) to generate class-representative and
synthesized samples; (He et al., 2019; Zhu and Han, 2020; Geiping et al.,
2020; Yin et al., 2021; Erdogan et al., 2021) adopt a optimization framework
to invert the gradient and learn the data; (Aono et al., 2017) observes the
special structure of gradient with single input and partially recovered the
private data; (Bhagoji et al., 2019; Li et al., 2019) show how to reconstruct
the data when they are uniformly distributed or binary; (Zhao et al., 2020)
further demonstrates that the sign of cross-entropy loss could directly reveal
the label. Meanwhile, other forms of attack have been proposed, including
membership inference (Shokri et al., 2017; Nasr et al., 2019), property
inference (Melis et al., 2019) which resembles the class-representative
inference in model inversion (Fredrikson et al., 2015), and model
poisoning/backdoor attack (Baruch et al., 2019; Bagdasaryan et al., 2020). We
refer the reader to (Bouacida and Mohapatra, 2021) for a comprehensive survey
of the security vulnerabilities in FL ecosystem, and (Kairouz et al., 2019)
for general open problems in FL.

##### General Defense Strategies.

  * •

Homomorphic Encryption. Homomorphic Encryption (HE) (Rivest et al., 1978) is a
form of encryption which allows operations on the encrypted data without
access to the secret key. Based on the utility of the cryptosystem, HE can be
categorized into partially homomorphic encryption (PHE), somewhat homomorphic
encryption (SWHE) and fully homomorphic encryption (FHE) (Acar et al., 2018).
While FHE enjoys more desirable properties and has been deployed in practical
settings such as training with genomic data (Chen et al., 2018), we resort to
the Paillier cryptosystem for efficiency, which is a standard form of
additively homomorphic encryption within PHE and has been used in VLR in many
previous works (Aono et al., 2016; Aono et al., 2017; Hardy et al., 2017).

  * •

Differential Privacy. Differential Privacy (DP) (Dwork, 2006) offers a
probabilistic framework to quantify privacy and has become a standard building
block in machine learning community ever since its birth. DP ensures that the
outcome of an algorithm will not be impacted by the presence or absence of a
single instance, and is usually realized via randomization: making the
algorithm stochastic by adding noise. Based on the structure of noise, there
are several types of mechanism to achieve DP: Laplace, Exponential and
Gaussian Mechanism (Dwork et al., 2014). See Section 6 for formal definitions.

DP has been applied to a wide range of learning tasks to ensure privacy
(Chaudhuri et al., 2011; Song et al., 2013; Bassily et al., 2014; Abadi et
al., 2016), in which the noise is injected to the parameter after a step of
update. For FL, DP is mostly used in the horizontal setting (Geyer et al.,
2017; Truex et al., 2019; Wei et al., 2020). On the contrary, we apply DP to
the VFL framework, carefully couple the noise-injection mechanism with the HE-
based protocol and inject noise to the sensitive information before
communication.

##  2\. Preliminaries

###  2.1. (Vertical) Logistic Regression

In binary logistic regression, the goal is to learn a linear model
$\bm{\theta}\in\mathbb{R}^{d}$ that correctly maps the sample
$\bm{x}\in\mathbb{R}^{d}$ to its corresponding label $y\in\\{-1,1\\}$. To
achieve this, we use the training set $D=\\{(\bm{x}_{i},y_{i})\\}_{{i\in[n]}}$
with $[n]=\\{1,2,\ldots,n\\}$, and consider the following unregularized
empirical risk minimization:

(1)
$\displaystyle\min_{\bm{\theta}}\ell_{D}(\bm{\theta}):=-\frac{1}{n}\sum_{i=1}^{n}\log
S(y_{i}\bm{\theta}^{\top}\bm{x}_{i}),$

where $S(z)=\frac{1}{1+e^{-z}}$ is the sigmoid function. In practice, we
usually resort to mini-batch gradient descent, which is an effective algorithm
of solving Eq. (1).

##### Mini-batch Gradient Descent (MGD).

The parameter is initialized as $\bm{\theta}=\bm{\theta}_{0}$. At $t$-th
iteration, a mini-batch $\mathcal{B}_{t}$ of the indices of training examples
with fixed batch size $s$ is sampled from $D$, and the mini-batch gradient,
which is the average gradient over $\mathcal{B}_{t}$, is computed as follows:

(2)
$\displaystyle\nabla\ell_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})=\frac{1}{s}\sum_{i\in\mathcal{B}_{t}}\left(S(y_{i}\bm{\theta}_{t-1}^{\top}\bm{x}_{i})-1\right)y_{i}\bm{x}_{i}.$

The model is then updated as

(3)
$\displaystyle\bm{\theta}_{t}=\bm{\theta}_{t-1}-\eta_{t}\nabla\ell_{\mathcal{B}_{t}}(\bm{\theta}_{t-1}),$

where $t\geq 1$ and $\eta_{t}$ represents the learning rate. We assume $s$
divides $n$, so there are $m:=n/s$ iterations in one epoch. The algorithm is
executed for $e$ epochs and there will be $T:=me$ iterations in total.

##### First-order Taylor Approximation.

Since the sigmoid function is non-polynomial, and the operations of
exponential and logarithmic functions are cryptographically computational-
inefficient, a natural solution is to use simple functions to approximate the
gradient. There are several standard methods to approximate Eq. (2), such as
first-order Taylor approximation (Aono et al., 2016; Hardy et al., 2017),
minimax approximation (Chen et al., 2018) and piecewise approximation
(Mohassel and Zhang, 2017). It turns out that the specific choice of
approximation scheme has minimal effect on the privacy analysis. Therefore, we
will focus on the first one throughout the main body of this paper, and leave
the analyses of other approximation methods to Appendix E and F.

Now, doing Taylor’s expansion of $S(z)$ at $z=0$, we have

$\displaystyle S(z)=\frac{1}{2}+\frac{1}{4}z+O(z^{2}).$

Therefore, the gradient in Eq. (2) can be approximated as

(4)
$\displaystyle\nabla\ell_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})\approx\frac{1}{4s}\sum_{i\in\mathcal{B}_{t}}f_{i,t}\bm{x}_{i},$

where we define the coefficients

(5) $\displaystyle f_{i,t}:=\bm{\theta}^{\top}_{t-1}\bm{x}_{i}-2y_{i},\
\forall t{\in[T]},\ \forall i\in[n].$

##### Vertical Logistic Regression.

We start with two-party vertical logistic regression (the multi-party case
will be discussed at the end of Section 4). Suppose $A$ and $B$ vertically
share a group of data — formally, given a sample
$(\bm{x},y)\in\mathbb{R}^{d}\times\\{-1,1\\}$, the feature $\bm{x}$ is split
into $\bm{x}^{A}\in\mathbb{R}^{d_{A}}$ and $\bm{x}^{B}\in\mathbb{R}^{d_{B}}$,
where $\bm{x}=\left(\begin{array}[]{@{}c@{}}\bm{x}^{A}\\\
\hline\cr\bm{x}^{B}\end{array}\right)$, $d=d_{A}+d_{B}$, $(\bm{x}^{A},y)$
belongs to Party $A$, and $\bm{x}^{B}$ belongs to Party $B$. Now, both parties
want to jointly optimize a binary logistic regression model using mini-batch
gradient descent. Since we are considering a linear model, the separation in
feature naturally induces a separation in parameter, i.e. the model parameter
$\bm{\theta}\in\mathbb{R}^{d}$ is also split into
$\bm{\theta}^{A}\in\mathbb{R}^{d_{A}}$ and
$\bm{\theta}^{B}\in\mathbb{R}^{d_{B}}$, belonging to Party $A$ and Party $B$
respectively. The gradients of both parties at each iteration then write as

(6)
$\displaystyle\nabla^{A}_{t}=\frac{1}{4s}\sum_{i\in\mathcal{B}_{t}}f_{i,t}\bm{x}^{A}_{{i}}\quad\text{and}\quad\nabla^{B}_{t}=\frac{1}{4s}\sum_{i\in\mathcal{B}_{t}}f_{i,t}\bm{x}^{B}_{{i}}.$

##### Data Assumption.

We assume that the data $\\{\bm{x}_{i}\\}_{i\in[n]}$ are sampled from a
probability distribution which is continuous w.r.t. the Lebesgue measure over
$\mathbb{R}^{d\times n}$, and that $\|\bm{x}_{i}\|_{2}\leq 1,\ \forall
i\in[n]$. These assumptions are canonical in the machine learning literature.

###  2.2. Threat Models

In this subsection, we formally state the key ingredients of our threat
models. We use two parties $A$ and $B$ for illustration and consider both the
passive adversarial model (see Section 3 and 4) and the active adversarial
model (see Section 5).

##### Adversary’s objective.

At a time during training, the main goal of the label party (Party $A$) is to
identify the feature of the non-label party (Party $B$); whereas the main goal
of a non-label Party is to recover the hidden label from the label party.

##### Passive Adversarial Model.

In the passive adversarial model (a.k.a. the honest-but-curious model), a
corrupted party (Party $A$ or Party $B$) correctly follows the protocol
specification and the adversary obtains the input and internal state of the
corrupted party (Hazay and Lindell, 2010). We make two key assumptions within
this threat model: 1) first of all, each party is capable of obtaining his own
share of gradient ($\nabla^{A}_{t}$ or $\nabla^{B}_{t}$) at each iteration —
we abstract such ability as an oracle and ignore the details of implementation
for now; 2) second, the non-label party holds the information about the
initialization scheme (not necessarily the precise value), i.e. how
$\bm{\theta}_{0}$ is initialized.

##### Active Adversarial Model.

In the active adversarial model, a corrupted party can arbitrarily deviate
from the protocol specification, according to the adversary’s instructions
(Hazay and Lindell, 2010). In this adversarial model, we focus on an
instantiation of computing the gradients $\nabla^{A}_{t}$ and $\nabla^{B}_{t}$
based on HE (Authors, 2019b; Hardy et al., 2017), and show how the adversary
can obtain more information by modifying the original protocol. Such active
attack is expected to be stronger than the ones proposed in the passive
adversarial model, as will be seen in Section 5.

##### Publicly-available information.

The mini-batch and the learning rate used in each iteration are known to all
participants — combined with the assumption in the passive adversarial model,
this ensures that both parties can do local updates on their own share of
model parameters.

##  3\. Privacy Analysis for Party $B$

As an adversary, Party $A$ seeks to obtain information about the feature
$\bm{x}_{B}$. At $t$-th iteration, $A$ receives his own gradient

(7)
$\displaystyle\nabla^{A}_{t}=\frac{1}{4s}\sum_{i\in\mathcal{B}_{t}}f_{i,t}\bm{x}^{A}_{i},$

which is the linear combination on his own share of feature. We will restrict
our discussion to $s\leq d_{A}$, and resort to a useful result in linear
algebra.

###### Theorem 3.1.

Suppose $\\{\bm{z}_{i}\\}_{i\in[n]}$ is randomly sampled from a probability
distribution which is continuous w.r.t. the Lebesgue measure over
$\mathbb{R}^{d^{\prime}\times n}$ and we want to solve $a_{i}\in\mathbb{R}$,
then $\forall I\in\mathbb{R}^{d^{\prime}},$ $\forall S\subseteq D$ such that
$|S|=s$, the linear system

(8) $\displaystyle\sum_{i\in S}a_{i}\bm{z}_{i}=\bm{I}$

has at most one solution with probability one if $s\leq d^{\prime}$.

The proof is mainly based on the fact that degenerate matrix has zero Lebesgue
measure, and the details are deferred to Appendix A. As a direct consequence,
we immediately have the following corollary.

###### Corollary 3.2.

If $s\leq d_{A}$, then $\forall t$, Party $A$ can uniquely determine the
values of $f_{i,t}$ for all $i\in{\mathcal{B}}_{t}$ with probability one.

###### Proof.

The uniqueness follows from Theorem 3.1, and the fact that
$\\{\bm{x}_{A,i}\\}_{i\in[n]}$ also follows a continuous probability
distribution. The existence is trivial. ∎

Saying in another way, Corollary 3.2 allows Party $A$ to determine the
coefficients of the linear system Eq. (7). Now denote

(9) $\displaystyle g_{i,t}:=\bm{\theta}_{t-1}^{\top}\bm{x}_{i}$

and decompose

(10) $\displaystyle
g_{i,t}=\underbrace{(\bm{\theta}_{t-1}^{A})^{\top}\bm{x}^{A}_{i}}_{g^{A}_{i,t}}+\underbrace{(\bm{\theta}_{t-1}^{B})^{\top}\bm{x}^{B}_{i}}_{g^{B}_{i,t}}.$

After obtaining the coefficient

$\displaystyle f_{i,t}=g_{i,t}-2y_{i},$

Party $A$ can extract the information known to himself (which is
$g^{A}_{i,t}-2y_{i}$), and obtain the values of $g_{i,t}^{B}$, which is
exactly the inner product of the data $\bm{x}$ and the parameter $\bm{\theta}$
on $B$’s feature. Therefore, in the special case $d_{B}=1$, Party $A$ can
determine the order of the data according to the $x_{B}$ feature in each
batch.

###### Lemma 3.3.

Suppose $s\leq d_{A}$ and $d_{B}=1$, then Party $A$ can learn the ratio of the
data in ${\mathcal{B}}_{t}$ in terms of feature $x^{B}$.

###### Proof.

For $i,j\in{\mathcal{B}}_{t}$, Party $A$ can compute the ratio of $x_{B,i}$
and $x_{B,j}$ via calculating $g_{i,t}^{B}/g_{j,t}^{B}$. Therefore, he will be
able to sort the data in ${\mathcal{B}}_{t}$ in terms of feature $x^{B}$. ∎

There are two special cases of Lemma 3.3: when $s=n$, Party $A$ directly
obtains the order of the full dataset $D$; when $s=1$, there is essentially no
sorting and thus Party $A$ can obtain no information about the feature
$x_{B}$. When $2\leq s\leq n-1$, in order to obtain the full order, we need a
few epochs to make different batches ‘intertwine’ with each other, as shown in
the following lemma.

###### Lemma 3.4.

Under the same condition as in Lemma 3.3, and we further assume $s\geq 2$.
Then Party $A$ can learn the ratio of the dataset $D$ in terms of feature
$x_{B}$ in at most $\lfloor\log_{2}(m)\rfloor+1$ epochs with probability at
least $1-\mathcal{O}(\frac{1}{m^{s-1}})$.

The proof of Lemma 3.4 is deferred to Appendix A. Now, after
$\lfloor\log_{2}(m)\rfloor+1$ epochs, Party $A$ will be able to learn the
ratio between different data points on $B$’s feature:

(11) $\displaystyle\frac{x^{B}_{i}}{x^{B}_{1}}:=r_{i},\ 2\leq i\leq n.$

Without loss of generality, assume $1\in\mathcal{B}_{1}$ and
$1\in\mathcal{B}_{k}$ for some $m+1\leq k\leq 2m$. By comparing $g_{1,k}$ and
$g_{1,1}$ — the inner products of the same feature $x_{1}^{B}$ and $B$’s
parameter $\theta^{B}$ at different iterations, we immediately have the
following theorem.

###### Theorem 3.5.

Suppose $s\leq d_{A}$ and $d_{B}=1$, then Party $A$ can learn the precise
value of the data in terms of feature $x^{B}$ (up to a difference in sign) in
at most $\max\\{\lfloor\log_{2}(m)\rfloor+1,2\\}$ epochs with probability at
least $1-\mathcal{O}(\frac{1}{m^{s-1}})$.

###### Proof.

By the update formula of $\theta^{B}_{k}$, we have

$\displaystyle g_{1,k}-g_{1,1}$
$\displaystyle=\theta^{B}_{k-1}x^{B}_{1}-\theta^{B}_{0}x^{B}_{1}$
$\displaystyle=-\sum_{t=1}^{k-1}\frac{\eta_{t}}{4s}\sum_{j\in\mathcal{B}_{t}}(\theta_{t-1}{x}_{j}-2y_{j})x^{B}_{j}x^{B}_{1}$
$\displaystyle=-\sum_{t=1}^{k-1}\frac{\eta_{t}}{4s}\sum_{j\in\mathcal{B}_{t}}f_{j,t}r_{j}(x^{B}_{1})^{2}$
(12) $\displaystyle=-\left[\sum_{t=1}^{k-1}\left(\frac{\eta_{t}}{4s}\sum_{i\in
D_{t}}f_{j,t}r_{j}\right)\right](x^{B}_{1})^{2}.$

Therefore,

(13) $\displaystyle
x^{B}_{1}=\pm\sqrt{\frac{4s(g_{1,1}-g_{1,k})}{\sum\limits_{t=1}^{k-1}\sum\limits_{j\in\mathcal{B}_{t}}f_{j,t}r_{j}\eta_{t}}}$

and $x^{B}_{i}=r_{i}x^{B}_{1}$, where $r_{i}$ is defined in Eq. (11). ∎

When $d_{B}\geq 2$, we provide a hardness result: by simply observing
$\\{g_{i,t}^{B}\\}_{i\in\mathcal{B}_{t},t\in[T]}$, Party $A$ cannot learn
$B$’s feature in general. The main observation is that an orthogonal
transformation would not change the coefficients obtained during training.

###### Theorem 3.6.

Assume Party $A$ does not know the precise value of $\bm{\theta}^{B}_{0}$ and
$d_{B}\geq 2$. Fix the mini-batch and learning rate used in each iteration,
then there are infinitely many choices of $\\{\bm{x}_{i}^{B}\\}_{i\in[n]}$
that yield the same set of $\\{g_{i,t}^{B}\\}_{i\in\mathcal{B}_{t},t\in[T]}$
through the optimization process. As a consequence, $A$ cannot determine the
precise value of $B$’s feature.

###### Proof.

Denote $O(d_{B},\mathbb{R})$ as the orthogonal group in dimension $d_{B}$.
Since $A$ does not hold the information of $\bm{\theta}_{0}^{B}$, we can pick
an arbitrary $\bm{Q}\in O(d_{B},\mathbb{R})$ and consider the following
transformation

$\displaystyle\bm{\theta}_{t-1}^{B}\mapsto\bm{Q}\bm{\theta}_{t-1}^{B},\
\forall t\in[T]\ \ \text{and}\ \ \bm{x}^{B}_{i}\mapsto\bm{Q}\bm{x}^{B}_{i},\
\forall i\in[n].$

By the update formula on $\bm{\theta}^{B}$, we have

(14)
$\displaystyle\bm{Q}\bm{\theta}_{t}^{B}=\bm{Q}\bm{\theta}_{t-1}^{B}-\frac{1}{4s}\sum_{i\in\mathcal{B}_{t}}(\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-2y_{i})\bm{Q}\bm{x}_{i}^{B},$

which is equivalent to

$\displaystyle\bm{Q}\bm{\theta}_{t}^{B}=\bm{Q}\bm{\theta}_{t-1}^{B}-\frac{1}{4s}$
$\displaystyle\sum_{i\in\mathcal{B}_{t}}\big{(}(\bm{Q}\bm{\theta}_{t-1}^{B})^{\top}(\bm{Q}\bm{x}_{i}^{B})$
(15)
$\displaystyle+(\bm{\theta}_{t-1}^{A})^{\top}\bm{x}_{i}^{A}-2y_{i}\big{)}\bm{Q}\bm{x}_{i}^{B},$

i.e. the mini-batch gradient descent acting on a new dataset with
$\hat{\bm{x}}_{i}=\left(\begin{array}[]{@{}c@{}}\bm{x}_{i}^{A}\\\
\hline\cr\bm{Q}\bm{x}_{i}^{B}\end{array}\right)$ and starting from
$\bm{Q}\bm{\theta}_{0}$. Party $A$ cannot distinguish the two processes by
observing $g_{i,t}^{B}$, since the inner product

(16)
$\displaystyle\left<\bm{Q}\bm{\theta}_{t-1}^{B},\bm{Q}\bm{x}^{B}_{i}\right>=\left<\bm{\theta}_{t-1}^{B},\bm{x}_{i}^{B}\right>$

remains unchanged. Combining the fact that $O(d_{B},\mathbb{R})$ has infinite
cardinality when $d_{B}\geq 2$ gives the result as desired. ∎

##  4\. Privacy Analysis for Party $A$

We shall see that Party $A$ and $B$ are symmetric except that $B$ does not
hold the label. Therefore, the main goal of an adversarial $B$ is to obtain
information about the label $y$. At $t$-th iteration, $B$ receives his own
gradient

(17)
$\displaystyle\nabla^{B}_{t}=\frac{1}{4s}\sum_{i\in\mathcal{B}_{t}}f_{i,t}\bm{x}^{B}_{i}$

which is still the linear combination on his own share of feature. Similar to
the previous section, we will restrict our discussion to $s\leq d_{B}$,
implying that the linear system given by Eq. (17) is not underdetermined. As a
corollary of Theorem 3.1, Party $B$ also holds the value of

(18) $\displaystyle
f_{i,t}=(\bm{\theta}_{t-1}^{A})^{\top}\bm{x}^{A}_{i}+(\bm{\theta}_{t-1}^{B})^{\top}\bm{x}^{B}_{i}-2y_{i}$

for $t\in[T]$ and $i\in\mathcal{B}_{t}$. In the right hand side, Party $B$
does not know about the first and the third term, so at first sight it seems
unlikely for him to gain information about the label. However, we will show in
the following analysis that label attack would still be possible under certain
circumstances.

We first consider a special case where Party $A$ only holds the label, meaning
that Party $B$ have full control of the model.

###### Theorem 4.1.

Suppose $d_{A}=0$, then Party $B$ can uniquely determine the label
$\\{y_{i}\\}_{i\in S_{t}}$ for arbitrary sampled batch $\mathcal{B}_{t}$ with
probability one.

The proof of Theorem 4.1 is deferred to Appendix B. Some might argue for a
simpler attack in this special case: since $B$ holds both the data and the
model, he can directly feed the data to the trained model and use the output
to ‘guess’ the label. However, there are two drawbacks of this approach: 1) it
heavily relies on the model’s training accuracy, and do not have any
guarantees on the predictions; 2) the attack can only be performed after (or
at the end of) training.

Now we will consider the more realistic case $d_{A}\geq 1$. The intuition here
is that $|2y_{i}|=2$, so if Party $B$ can convince himself that the full inner
product satisfies $|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|<2$, then

(19)
$\displaystyle\operatorname{sign}(f_{i,t})=\operatorname{sign}(-2y_{i})=-y_{i},$

so he can use the opposite sign of $f_{i,t}$ to determine the value of $y_{i}$
in the $t$-th iteration. This can be formulated into the following criterion.

###### Criterion 4.2.

For $t=1,\cdots,T^{*}$, Party $B$ uses $-\operatorname{sign}(f_{i,t})$ to
determine $y_{i},\ \forall i\in\mathcal{B}_{t}$.

###### Remark 4.3.

If Criterion 4.2 is valid for $T^{*}\geq m$, then Party $B$ can obtain the
label of the full dataset $D$.

Now the analysis naturally breaks into two parts:

  * •

Show when Criterion 4.2 is valid for $T^{*}=1$;

  * •

Determine the largest $T^{*}$ that we can safely apply the criterion.

We will first deal with the second part. Define
$h_{t}=\max\limits_{i}\\{|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|+2\\}$ and we
will establish a recursive relation of $h_{t}$ in the following lemma.

###### Lemma 4.4.

Suppose we use a constant learning rate $\eta_{t}=\eta$ in mini-batch gradient
descent. Then we have

(20) $\displaystyle h_{t+1}\leq\left(1+\frac{\eta}{4}\right)h_{t}.$

###### Proof.

By the update formula Eq. (3), for $1\leq j\leq n$ we have

(21)
$\displaystyle\bm{\theta}_{t}^{\top}\bm{x}_{j}=\bm{\theta}_{t-1}^{\top}\bm{x}_{j}-\frac{\eta}{4s}\sum_{i\in\mathcal{B}_{t}}(\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-2y_{i})\bm{x}_{i}^{\top}\bm{x}_{j}.$

Applying Cauchy-Schwarz and triangle inequality, we have

(22)
$\displaystyle\big{|}\bm{\theta}_{t}^{\top}\bm{x}_{j}\big{|}\leq\big{|}\bm{\theta}_{t-1}^{\top}\bm{x}_{j}\big{|}+\frac{\eta}{4}\cdot\frac{1}{s}\sum_{i\in\mathcal{B}_{t}}\left(\big{|}\bm{\theta}_{t-1}^{\top}\bm{x}_{i}\big{|}+2\right),$

implying

(23)
$\displaystyle\left(\big{|}\bm{\theta}_{t}^{\top}\bm{x}_{j}\big{|}+2\right)\leq\left(\big{|}\bm{\theta}_{t-1}^{\top}\bm{x}_{j}\big{|}+2\right)+\frac{\eta}{4s}\sum_{i\in\mathcal{B}_{t}}\left(\big{|}\bm{\theta}_{t-1}^{\top}\bm{x}_{i}\big{|}+2\right).$

Taking maximum over $1\leq j\leq n$ on both side, we immediately have

(24) $\displaystyle h_{t+1}\leq\left(1+\frac{\eta}{4}\right)h_{t}.$

∎

As a corollary, we immediately obtain a possible choice of $T$ that will be
safe for the implementation of the criterion.

###### Corollary 4.5.

Suppose $\max\limits_{i}\\{|\bm{\theta}_{0}^{\top}\bm{x}_{i}|\\}=\epsilon<2$.
Then Criterion 4.2 is valid for

(25) $\displaystyle
T_{\epsilon}=\bigg{\lceil}\log_{\left(1+\frac{\eta}{4}\right)}\left(\frac{4}{2+\epsilon}\right)\bigg{\rceil}.$

###### Proof.

We have $h_{1}=2+\epsilon$ and the criterion fails with threshold $4$. By
Lemma 4.4, the criterion is safe for the first
$\bigg{\lceil}\log_{\left(1+\frac{\eta}{4}\right)}\left(\frac{4}{2+\epsilon}\right)\bigg{\rceil}$
iterations. ∎

We now come back to the first part. Party $B$ need to determine whether
Criterion 4.2 is valid for $t=1$, i.e.
$\max\limits_{i}\\{|\bm{\theta}_{0}^{\top}\bm{x}_{i}|\\}<2$ based on his
knowledge of the initialization scheme. We will discuss several possible
choices of initialization.

##### Deterministic Initialization.

Suppose $\bm{\theta}_{0}$ is initialized to be a fixed vector. If

(26)
$\displaystyle\max\limits_{i}\\{|\bm{\theta}_{0}^{\top}\bm{x}_{i}|\\}=\epsilon<2,$

then by Corollary 4.5, we can set $T^{*}=T_{\epsilon}$ in Criterion 4.2. As a
special case, we have

###### Theorem 4.6.

If we apply Zero Initialization _(Tripathi et al., 2018)_ to
$\bm{\theta}_{0}$, then Criterion 4.2 is valid for

(27) $\displaystyle
T_{0}=\bigg{\lceil}\log_{\left(1+\frac{\eta}{4}\right)}2\bigg{\rceil}.$

##### Small Random Initialization.

This is a common strategy in modern machine learning problems to ensure an
$O(1)$ output, so that optimization can be significantly boosted. Common
initialization schemes such as Xavier Initialization (Glorot and Bengio, 2010)
and Kaiming Initialization (He et al., 2015) all fall into this category.
Formally, since $\|\bm{x}_{i}\|_{2}\leq 1,\ \forall i\in[n]$, we need to
ensure that $\mathbb{E}\|\bm{\theta}_{0}\|_{2}=O(1)$, $i.e.$
$\mathbb{E}\theta_{0,j}^{2}=O\left(\frac{1}{d}\right),\ \ \forall j\in[d]$. To
achieve this, we set $\gamma$ to be a mean-zero sub-exponential random
variableand initialized each element of $\bm{\theta}_{0}$ i.i.d. through
$\gamma/\sqrt{d}$. We then have the following lemma.

###### Lemma 4.7.

Suppose $\|\gamma\|_{\psi_{1}}=l$, then with probability at least
$1-2ne^{-\sqrt{d}}$, we have

(28)
$\displaystyle\big{|}\bm{\theta}_{0}^{\top}\bm{x}_{i}\big{|}<\frac{l}{c}d^{-\frac{1}{4}},\
\ \ \ \ \forall i\in[n],$

where $c\leq 1$ is an absolute constant.

###### Proof.

For a fixed $i\in[n]$, note $\|\bm{x}_{i}\|_{2}\leq 1$ and
$\|\bm{x}_{i}\|_{\infty}\leq 1$. Applying Bernstein’s inequality (Theorem
2.8.1 in (Vershynin, 2018)), we have

$\displaystyle\ \ \
\Pr\left(\bigg{|}\sum_{j=1}^{d}\theta_{0,j}x_{i,j}\bigg{|}\geq\epsilon\right)$
$\displaystyle\leq
2\exp\left[-c\min\left(\frac{\epsilon^{2}}{L^{2}\|\bm{x}_{i}\|_{2}^{2}},\frac{\epsilon}{L\|\bm{x}_{i}\|_{\infty}}\right)\right]$
(29) $\displaystyle\leq
2\exp\left[-c\min\left(\frac{d\epsilon^{2}}{l^{2}},\frac{\sqrt{d}\epsilon}{l}\right)\right].$

Setting $\epsilon=\frac{l}{c}d^{-\frac{1}{4}}$, we have with probability at
most $2e^{-\sqrt{d}}$,

(30)
$\displaystyle|\bm{\theta}_{0}^{\top}\bm{x}_{i}|\geq\frac{l}{c}d^{-\frac{1}{4}}.$

Taking a union bound over $i\in[n]$ yields the result as desired. ∎

Together with Corollary 4.5, we immediately have

###### Theorem 4.8.

Suppose each element of $\bm{\theta}_{0}$ is initialized i.i.d. through
$\gamma/\sqrt{d}$, where $\gamma$ is a mean-zero sub-exponential random
variable with $\|\gamma\|_{\psi_{1}}=l$. Then with probability at least
$1-2ne^{-\sqrt{d}}$, Criterion 4.2 is valid for

(31) $\displaystyle
T_{l}=\bigg{\lceil}\log_{\left(1+\frac{\eta}{4}\right)}\left(\frac{4c}{2c+ld^{-\frac{1}{4}}}\right)\bigg{\rceil},$

where $c\leq 1$ is an absolute constant.

###### Remark 4.9.

Suppose Party $B$ holds the label of the full dataset $D$ in the first epoch,
then he can repeat the procedure as in Section 3 and obtains
$g_{i,t}^{A}=(\bm{\theta}_{t-1}^{A})^{\top}\bm{x}^{A}_{i}$ for every $t\geq 1$
and $i\in S_{t}$. In particular, when $d_{A}=1$, he can learn the precise
value of the data in terms of feature $x_{A}$ (up to a difference in sign) in
at most $\max\\{\lfloor\log_{2}(m)\rfloor+1,2\\}$ epochs with probability at
least $1-\mathcal{O}(\frac{1}{m^{s-1}})$.

##### Large Random Initialization.

The strategy is to initialize each element of $\bm{\theta}_{0}$ to be $O(1)$,
$e.g.\ $ $\mathcal{N}(0,1)$. This is less common in modern machine learning as
it makes the output dependent on the dimension, $e.g.$
$\bm{\theta}_{0}^{\top}\bm{x}_{i}=O(d)$ in logistic regression. Although less
favorable from the perspective of optimization, it is suitable for the
vertical FL framework since now $\bm{\theta}_{t-1}^{\top}\bm{x}_{i}$ dominates
the observable signal ${f}_{i,t}$, and therefore makes Criterion 4.2 invalid.
In some sense, one must trade efficiency for privacy.

##### Discussion of the Multi-party Scenario.

Finally, we will generalize the label recovery attack to the multi-party
scenario. The main observation is that the proposed attack only relies on the
understanding of the full inner product through the initialization scheme, and
does not depend on the number of parties or how the features are split between
them.

Specifically, suppose there are $p$ parties $U_{1},\cdots,U_{p}$ with $p\geq
3$, $U_{1}$ is the only party that holds the label, and they own a disjoint
set of the features $\bm{x}^{U_{i}}$ where
$\bm{x}=\bm{x}^{U_{1}}\parallel...\parallel\bm{x}^{U_{p}}$. Denote
$d_{i}=\text{dim}(\bm{x}^{U_{i}}),\ i\in[p]$ and $d=\sum_{i=1}^{p}d_{i}$.
Similar to the proof of Corollary 4.5, we have the following theorem for Party
$U_{i},\ 2\leq i\leq p$.

###### Theorem 4.10.

Suppose $s\leq d_{U_{i}}$ for some $2\leq i\leq p$. If $\bm{\theta}_{0}$ is
initialized (with high probability) such that

(32)
$\displaystyle\max_{i}\\{|\bm{\theta}_{0}^{\top}\bm{x}_{i}|\\}=\epsilon<2,$

then Criterion 4.2 is valid for $U_{i}$ for

(33) $\displaystyle
T_{\epsilon}=\bigg{\lceil}\log_{\left(1+\frac{\eta}{4}\right)}\left(\frac{4}{2+\epsilon}\right)\bigg{\rceil}$

(with high probability).

##  5\. Protocol-aware Active Attack

For the privacy analysis in Section 3 and 4, we assume the existence of an
oracle such that both parties can obtain their local gradients, and ignore the
details of practical implementation. In this section, we will describe the
protocol through which both parties can cooperatively learn their own share of
gradient, without violating the privacy of individual instance directly.
Further, by modifying the protocol maliciously, both parties can relax the
constraints of batch size as appears in the previous sections, and therefore
are able to perform the same attack in more general scenarios. We refer to
this as ‘active attack’.

###  5.1. Protocol of Obtaining Gradient

We will discuss how both parties collaboratively obtain $\nabla^{A}_{t}$, and
the procedure for computing $\nabla^{B}_{t}$ shares a similar philosophy.
Aside from the information known to himself, Party $A$ needs to compute
$\bm{H}^{A}_{t}:=\sum_{i\in\mathcal{B}_{t}}g_{i,t}^{B}\bm{x}^{A}_{i}$ via the
assistance from Party $B$, where
$g_{i,t}^{B}=(\bm{\theta}_{t-1}^{B})^{\top}\bm{x}^{B}_{i}$. Also, Party $B$
cannot directly send the value of $g_{i,t}^{B}$ to Party $A$ as it will
violate the privacy of individual $i$.

Note $\bm{H}^{A}_{t}$ is essentially a linear combination of the $\bm{x}^{A}$
feature, with the coefficients being unknown. Therefore, a natural solution to
the above problem is (additively) homomorphic encryption, such as Paillier
(Paillier, 1999) and OU (Okamoto and Uchiyama, 1998). Here we will resort to
the former one. In Paillier cryptosystem, there exists a pair of keys $pk_{B}$
and $sk_{B}$, where both parties can use $pk_{B}$ to encrypt a plaintext $a$
as its corresponding ciphertext $[\\![a]\\!]$, but only Party $B$ can use
$sk_{B}$ to decrypt $[\\![a]\\!]$ and get $a$, which we denote as
$D([\\![a]\\!])=a$. For vector $\bm{v}$, we will use $[\\![\bm{v}]\\!]$ to
denote element-wise encryption and similarly $\bm{D}$ for decryption.

The most notable property of $[\\![\cdot]\\!]$ is additively homomorphic, i.e.
$[\\![a]\\!]+[\\![b]\\!]=[\\![a+b]\\!]$ and $k[\\![a]\\!]=[\\![ka]\\!]$ for
all plaintext $a,b$ and $k\in\mathbb{Z}$. We are now ready to present the
protocol111The protocol is standard and resembles a few works in the
literature (Authors, 2019b; Hardy et al., 2017) — the only difference here is
that we do not assume the existence of a trusted third party $C$. Also, we
assume all the quantities presented in this protocol appear in the form of
integers and ignore the process of encoding and decoding.

Protocol 1 Party $A$ and $B$ compute the gradient $\nabla^{A}_{t}$

0: The public key $pk_{B}$ and $d_{A},d_{B}$ for both parties The secret key
$sk_{B}$ for $B$

1: Initialize $\bm{S}^{A}_{t}\leftarrow[\\![\bm{0}_{d_{A}}]\\!]$

2: for $i\in\mathcal{B}_{t}$ do

3: $B$ computes $g_{i,t}^{B}=(\bm{\theta}_{t-1}^{B})^{\top}\bm{x}^{B}_{i}$ and
encrypts it as $[\\![g_{i,t}^{B}]\\!]$

4: end for

5: $B$ sends $[\\![g_{i,t}^{B}]\\!]$, $i\in\mathcal{B}_{t}$ to $A$

6: for $i\in\mathcal{B}_{t}$ do

7: $A$ computes
$\bm{S}^{A}_{t}\leftarrow\bm{S}^{A}_{t}+[\\![g_{i,t}^{B}]\\!]\bm{x}^{A}_{i}$

8: end for

9: $A$ generates a random vector $\bm{r}\in\mathbb{Z}^{d_{A}}$ and computes
$[\\![\bm{r}]\\!]$

10: $A$ masks the summation
$\widetilde{\bm{S}}^{A}_{t}:=\bm{S}^{A}_{t}-[\\![\bm{r}]\\!]$ and sends it to
$B$

11: $B$ decrypts to get $\bm{D}(\widetilde{\bm{S}}^{A}_{t})$ and sends it back
to $A$

12: $A$ computes
$\bm{G}^{A}_{t}:=\bm{D}(\widetilde{\bm{S}}^{A}_{t})+\sum_{i\in\mathcal{B}_{t}}(g_{i,t}^{A}-2y_{i})\bm{x}^{A}_{i}+\bm{r}$,
where $g_{i,t}^{A}=(\bm{\theta}_{t-1}^{A})^{\top}\bm{x}^{A}_{i}$

12: The gradient for $A$ at iteration $t$:
$\nabla^{A}_{t}=\frac{1}{4s}\bm{G}^{A}_{t}$

To see the correctness of Protocol 1, note Party $B$ receives

(34) $\displaystyle\widetilde{\bm{S}}^{A}_{t}$
$\displaystyle=[\\![\bm{0}_{d_{A}}]\\!]+\sum_{i\in\mathcal{B}_{t}}[\\![g_{i,t}^{B}]\\!]\bm{x}^{A}_{i}-[\\![\bm{r}]\\!]$
(35)
$\displaystyle=\bigg{[}\\!\\!\bigg{[}\sum_{i\in\mathcal{B}_{t}}g_{i,t}^{B}\bm{x}^{A}_{i}-\bm{r}\bigg{]}\\!\\!\bigg{]}=[\\![\bm{H}^{A}_{t}-\bm{r}]\\!],$

where we use additive homomorphic in Eq. (35). Therefore, Party $A$ can
recover $\bm{H}^{A}_{t}$ by adding $\bm{r}$ to the plaintext
$\bm{D}(\widetilde{\bm{S}}^{A}_{t})$.

###  5.2. Active Attack

While constructing attacks in Section 3 and 4, we assume the batch size is no
more than the dimension of Party $A$’s (or Party $B$’s) features, i.e. $s\leq
d_{A}$ (or $s\leq d_{B}$). Unfortunately, such attacks could be easily
invalidated by increasing the batch size. To further strengthen our results,
we propose generating auxiliary ciphertext during the execution of information
transfer. Similarly, we will use Party $A$ as an example to illustrate our
strategy and the results can be easily generalized to Party $B$.

The idea is that Party $A$ receives the encrypted coefficient
$[\\![g_{i,t}^{B}]\\!]$ from Party $B$ and uses it to multiply
$\bm{x}^{A}_{i}$ in line 7 of Protocol 1, so intuitively he can gain more
information about $g_{i,t}^{B}$ by increasing the dimension of $\bm{x}_{A}$.
To this end, Party $A$ extends his share of feature on the training samples to
$\bm{z}^{A}_{i}:=\left(\begin{array}[]{@{}c@{}}\bm{x}^{A}_{i}\\\
\hline\cr\widetilde{\bm{x}}^{A}_{i}\end{array}\right)$ for $i\in[n]$, where
$\\{\widetilde{\bm{x}}^{A}_{i}\\}_{i\in[n]}$ is randomly sampled from a
continuous probability distribution and
$\dim(\widetilde{\bm{x}}^{A})=\widetilde{d}_{A}$. We also assume
$\widetilde{d}_{A}=(u-1)d_{A}$ for some $u\in\mathbb{Z}^{+}$ and therefore
$\dim(\bm{z}^{A})=ud_{A}$.

Now, we modify line 7 of Protocol 1 by multiplying each
$[\\![g_{i,t}^{B}]\\!]$ with $\bm{z}^{A}_{i}$, and Party $A$ obtains

(36)
$\displaystyle\bm{E}^{A}_{t}:=\bigg{[}\\!\\!\bigg{[}\sum_{i\in\mathcal{B}_{t}}g_{i,t}^{B}\bm{z}^{A}_{i}\bigg{]}\\!\\!\bigg{]}$

after the loop. But now $\text{dim}(\bm{E}^{A}_{t})=ud_{A}$, so it will not be
accepted by Party $B$. Therefore, we compress multiple ciphertexts into one
ciphertext with longer plaintext length. Specifically, we use $\bm{v}[j]$ to
denote the $j$-th element of vector $\bm{v}$, and assume each plaintext has
been encoded as an $\iota$-bit integer. Now define

(37)
$\displaystyle\bm{S}^{A}_{t}[i]:=\sum_{s=0}^{u-1}\bm{E}^{A}_{t}[i+sd_{A}]*2^{s\iota},\
\ \ \forall i\in[d_{A}],$

then the dimension of $\bm{D}\left(\bm{S}^{A}_{t}\right)$ will be $d_{A}$.
Further, for each $i\in[d_{A}]$, $D\left(\bm{S}^{A}_{t}[i]\right)$ can be
uniquely split into $u$ integers by $\iota$-bit since

(38) $\displaystyle
D\left(\bm{S}^{A}_{t}[i]\right)=\sum_{s=0}^{u-1}D\left(\bm{E}^{A}_{t}[i+sd_{A}]\right)*2^{s\iota}.$

Therefore, $\bm{D}(\bm{E}^{A}_{t})$ can be recovered from
$\bm{D}(\bm{S}^{A}_{t})$. Finally, before sending $\bm{S}^{A}_{t}$ to Party
$B$ for decryption, Party $A$ will similarly generate a noise vector $\bm{r}$
and mask the object. This step ensures that Party $B$ cannot distinguish
whether Party $A$ has hidden any information in $\bm{S}^{A}_{t}$. We now
present the complete algorithm as follow.

Algorithm 2 Active attack of Party $A$

0: $[\\![g_{i,t}^{B}]\\!],i\in\mathcal{B}_{t}$ for $A$

1: Initialize $\bm{E}^{A}_{t}\leftarrow[\\![\bm{0}_{ud_{A}}]\\!]$

2: for $i\in\mathcal{B}_{t}$ do

3: $A$ computes
$\bm{E}^{A}_{t}\leftarrow\bm{E}^{A}_{t}+[\\![g_{i,t}^{B}]\\!]\bm{z}_{A,i}$

4: end for

5: $A$ compresses $\bm{E}^{A}_{t}$ into $\bm{S}^{A}_{t}$ via Eq. (37)

6: $A$ generates a random vector $\bm{r}\in\mathbb{Z}^{{d_{A}}}$ and computes
$[\\![\bm{r}]\\!]$

7: $A$ masks the object
$\widetilde{\bm{S}}^{A}_{t}:=\bm{S}^{A}_{t}-[\\![\bm{r}]\\!]$ and sends it to
$B$

8: $B$ decrypts to get $\bm{D}(\widetilde{\bm{S}}^{A}_{t})$ and sends it back
to $A$

9: $A$ computes $\bm{D}(\widetilde{\bm{S}}^{A}_{t})+\bm{r}$, then splits it by
$\iota$-bit

9: The plaintext of $\bm{E}^{A}_{t}$: $\bm{D}(\bm{E}^{A}_{t})$

Note that the output of Algorithm 2 essentially provides Party $A$ a linear
system

(39)
$\displaystyle\sum_{i\in\mathcal{B}_{t}}g_{i,t}^{B}\bm{z}^{A}_{i}=\bm{D}(\bm{E}^{A}_{t}),$

which has $s$ variables $g_{i,t}^{B},\ i\in\mathcal{B}_{t}$ and $ud_{A}$
linear equations. Compared to the original protocol which gives $d_{A}$ linear
equations, Party $A$ obtains $(u-1)d_{A}$ additional equations via the
generation of auxiliary ciphertext. Further, since
$\\{\widetilde{\bm{x}}_{A,i}\\}_{i\in[n]}$ is sampled from a continuous
probability distribution, we can apply Theorem 3.1 and conclude the uniqueness
of $g_{i,t}^{B},\ i\in\mathcal{B}_{t}$ when $s\leq ud_{A}$. This further
allows us to perform the same attack as in Section 3. Analogously, Party $B$
can adopt the same strategy and perform the same attack in Section 4 when
$s\leq ud_{B}$.

Finally, we will pick a suitable $u$ so that the Paillier cryptosystem can
work properly. Denote $N$ as the maximum number that we can apply encryption
on and the length of $N$ is $\kappa$-bit. Note in Eq. (37) we produce a
ciphertext whose plaintext has length at most $u\iota$. Therefore, to ensure
the correctness of encryption, we can pick
$u=\lfloor\frac{{\kappa-1}}{\iota}\rfloor$ and Algorithm 2 can still function
properly. In practice, a $\iota=64$-bit encoding scheme on the plaintext can
guarantee good model performance and the length of $N$ is $\kappa=2048$-bit or
even more, implying $u\geq{31}$. Therefore, unless
$s>31\max\\{d_{A},d_{B}\\}$, at least one of the attacks in Section 3 or 4
will still be effective and therefore can be applied to more general scenarios
in practice. This is a significant improvement over the original protocol.
Additionally, if $d_{A}$ and $d_{B}$ is not publicly available, then both
party can maliciously claim a larger ‘$d_{A}$’ or ‘$d_{B}$’ to obtain more
linear equations from the other side. The constraints on batch size will then
be negligible.

In all, the proposed active attack is mainly based on generating and
compressing auxiliary ciphertext. While the idea of creating linear equations
is straightforward and does appear in a previous work (Li et al., 2021), in
context of the HE-based protocol where the linear equations essentially come
from the decoding party, we cannot simply attach the auxilliary ciphertext to
the original ones, which would result in denial of decoding. Instead, we need
to project the high-dimensional vector into the original domain to permit
decoding in a lossless manner. This is guaranteed by our compressing
mechanism, which leverages the power-of-$2$ summation to ensure unique
decodability. Together with the capacity of the Paillier cryptosystem as well
as the encoding scheme on the plaintext, we can obtain a lower bound on the
number of linear equations guaranteed by our active attack.

##  6\. Countermeasure

So far we’ve been mostly discussing privacy attacks in vertical logistic
regression. In this section, we will complement the previous results by
proposing a countermeasure. Note merely increasing the batch size might not be
adequate due to the active attack demonstrated in Subsection 5.2.

Take Party $A$ as an example. It is straightforward to see from Algorithm 2
that the privacy breach arises from the linear system Eq. (39), through which
Party $A$ can learn the precise value of $g_{i,t}^{B}$. To fix this issue, a
natural approach222Aside from the current framework, another straightforward
solution is to use secret sharing (Beimel, 2011), so that both parties can
only obtain random shares of the gradient throughout the training process. See
(Mohassel and Zhang, 2017) for an example. for Party $B$ is to modify Protocol
1 and mask the plaintext with random noise before encryption, so that the
solution to the linear system deviates from the true value $g_{i,t}^{B}$. This
strategy corresponds to differential privacy (Dwork, 2006), which is a classic
tool in secure multi-party computation and machine learning.

###  6.1. DP-Paillier-MGD

Let us begin with the formal definition of Differential Privacy (DP).

###### Definition 6.1 (Differential Privacy).

A randomized algorithm $\mathcal{A}$ with domain $\mathcal{D}$ and range
$\mathcal{R}$ is $(\epsilon,\delta)$-differentially private if for all
$\mathcal{S}\in\mathcal{R}$ and for all $D_{1},D_{2}\in\mathcal{D}$ that
differ by at most one instance,

$\displaystyle\Pr(\mathcal{A}(D_{1})\in\mathcal{S})\leq\exp{(\epsilon)}\Pr(\mathcal{A}(D_{2})\in\mathcal{S})+\delta.$

DP is usually realized via randomization: making the output undeterministic by
adding noise. Here we set the noise vector to be Gaussian, which has been
widely adopted in practice (Abadi et al., 2016; Bassily et al., 2014).

###### Definition 6.2 (Gaussian Mechanism).

Given $f:\mathcal{D}\to\mathbb{R}^{d}$, the Gaussian Mechanism with parameter
$\sigma$ is defined as:

(40) $\displaystyle
M_{G}\left(D,f(\cdot),\sigma\right):=f(D)+(Y_{1},\cdots,Y_{d})^{\top},$

where $D\in\mathcal{D}$ and $Y_{i}$ are i.i.d. random variables drawn from
$\mathcal{N}(0,\sigma^{2})$.

An important caveat here is that we will not resort to the original definition
of DP — which is interpreted as a privacy guarantee regarding the membership
inference attack — because Party $A$ and $B$ need to align their user ID
before initializing the procedure of VFL and hence hold the data records in
the training set. Instead, we seek to leverage the effect of obfuscation
brought along by the noise-adding mechanism, to ensure that DP also serves as
a good countermeasure for the attacks proposed in the previous sections.

Specifically, the strategy for Party $B$ is to mask the sensitive information,
and therefore Party $A$ cannot learn the precise value of $g_{i,t}^{B}$ after
solving the linear system. Similarly, Party $A$ will also mask the sensitive
information $g_{i,t}^{A}-2y_{i}$ before encryption. Denote $\bm{SV}^{B}_{t}$
as the sensitive vector concatenated by all
$\\{g_{i,t}^{B}\\}_{i\in\mathcal{B}_{t}}$ and similarly define
$\bm{SV}^{A}_{t}$. Both parties adopt Gaussian Mechanism for masking, and the
updated algorithm, which we name as DP-Paillier-MGD, is given as follow.

Algorithm 3 DP-Paillier-MGD

0: mini-batch $\mathcal{B}_{t}$, learning rate $\eta_{t}=\eta$, two Paillier
cryptosystems $\mathscr{P}_{1},\mathscr{P}_{2}$ variance
$\sigma_{A}^{2},\sigma_{B}^{2}$ of noise vector for $A,B$

1: Initialize
$\bm{\theta}_{0}=\bm{\theta}_{0}^{A}\parallel\bm{\theta}_{0}^{B}$

2: for $t=1:T$ do

3: $B$ generates $\bm{Z}^{B}\sim\mathcal{N}(\bm{0},\sigma_{B}^{2}\bm{I}_{s})$,
computes $Sec(\bm{SV}^{B}_{t}):=\bm{SV}^{B}_{t}+\bm{Z}^{B}$ and encrypts it in
$\mathscr{P}_{1}$

4: both parties follow the procedure of Protocol 1 using $\mathcal{P}_{1}$
until $A$ obtains $\bm{X}_{\mathcal{B}_{t}}^{A}Sec(\bm{SV}_{t}^{B})$, where
$\bm{X}_{\mathcal{B}_{t}}^{A}$ is formed via stacking
$\\{\bm{x}_{i}^{A}\\}_{i\in\mathcal{B}_{t}}$ by column

5: $A$ computes
$\widetilde{\bm{G}}_{t}^{A}:=\bm{X}_{\mathcal{B}_{t}}^{A}\bm{SV}_{t}^{A}+\bm{X}_{\mathcal{B}_{t}}^{A}Sec(\bm{SV}_{t}^{B})$

6: $A$ generates $\bm{Z}^{A}\sim\mathcal{N}(\bm{0},\sigma_{A}^{2}\bm{I}_{s})$,
computes $Sec(\bm{SV}^{A}_{t}):=\bm{SV}^{A}_{t}+\bm{Z}^{A}$ and encrypts it in
$\mathscr{P}_{2}$

7: both parties follow the procedure of Protocol 1 using $\mathcal{P}_{2}$
until $B$ obtains $\bm{X}_{\mathcal{B}_{t}}^{B}Sec(\bm{SV}_{t}^{A}))$, where
$\bm{X}_{\mathcal{B}_{t}}^{B}$ is similarly defined as
$\bm{X}_{\mathcal{B}_{t}}^{A}$

8: $B$ computes
$\widetilde{\bm{G}}_{t}^{B}:=\bm{X}_{\mathcal{B}_{t}}^{B}\bm{SV}_{t}^{B}+\bm{X}_{\mathcal{B}_{t}}^{B}Sec(\bm{SV}_{t}^{A})$

9: $A$ updates
$\bm{\theta}_{t}^{A}=\bm{\theta}_{t-1}^{A}-\frac{\eta}{4s}\widetilde{\bm{G}}_{t}^{A}$,
$B$ updates
$\bm{\theta}_{t}^{B}=\bm{\theta}_{t-1}^{B}-\frac{\eta}{4s}\widetilde{\bm{G}}_{t}^{B}$

10: end for

10:
$\\{Sec(\bm{SV}_{t}^{A})\\}_{t\in[T]},\\{Sec(\bm{SV}_{t}^{B})\\}_{t\in[T]}$

###  6.2. Utility and Privacy Guarantees

In this subsection, we will present utility and (worst-case) privacy
guarantees for Algorithm 3. We assume

(41) $\displaystyle\max_{t\in[T]}\|\bm{\theta}_{t-1}\|_{2}\leq 4G-2$

for some $G>\frac{1}{2}$, so that

(42)
$\displaystyle\max\limits_{i\in[n],t\in[T]}\|\nabla\mathcal{L}_{i}(\bm{\theta}_{t-1})\|_{2}$
$\displaystyle\leq\frac{\max\limits_{i\in[n],t\in[T]}|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-2y_{i}|}{4}\leq
G,$

where $\nabla\mathcal{L}_{i}(\bm{\theta}_{t-1})$ is the gradient on instance
$i$.

####  6.2.1. Utility Analysis

We begin ourselves on the utility side and provide a convergence analysis for
Algorithm 3 under the noise level $\sigma_{A}$ and $\sigma_{B}$. Note that
under the first-order approximation scheme, the original update on
$\bm{\theta}$ can be treated as mini-batch gradient descent of the following
loss function:

(43)
$\displaystyle\mathcal{L}(\bm{\theta}):=\frac{1}{8n}\sum_{i=1}^{n}(\bm{\theta}^{\top}\bm{x}_{i}-2y_{i})^{2},$

with the mini-batch gradient
$\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})$ identical to the one
defined in Eq. (4). After injecting noise in Algorithm 3, the update on
$\bm{\theta}$ becomes

(44)
$\displaystyle\bm{\theta}_{t}=\bm{\theta}_{t-1}-\eta_{t}\left(\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})+{\bm{e}_{t}}\right),$

where the gradient error is

(47)
$\displaystyle\bm{e}_{t}:=\frac{1}{4s}\left(\begin{array}[]{c}\bm{X}_{\mathcal{B}_{t}}^{A}\bm{Z}^{B}\\\
\bm{X}_{\mathcal{B}_{t}}^{B}\bm{Z}^{A}\end{array}\right).$

Our first step is to control the magnitude of $\bm{e}_{t}$, which is mainly
done by a standard concentration inequality and deferred to Appendix C.

###### Lemma 6.3.

Denote $\sigma:=\max\\{\sigma_{A},\sigma_{B}\\}$. Given $k\geq 1$, we have
$\|\bm{e}_{t}\|_{2}\leq\sqrt{\frac{k}{s}}\sigma$ for $t\in[T]$ with
probability at least $1-2T\exp(-ck)$, where $c$ is an absolute constant.

With Lemma 6.3 at hand, we are now ready to state the utility guarantee of
Algorithm 3. It is basically a combination of the standard mirror descent
argument, as well as a martingale trick to control the stacking of noise over
the training horizon.

###### Theorem 6.4.

Let $\bm{\theta}^{*}$ be an arbitrary reference point. Assume

(48)
$\displaystyle\max\limits_{t\in[T]}\|\bm{\theta}_{t-1}-\bm{\theta}^{*}\|_{2}\leq
C,$

then with step size $\eta={\mathcal{O}}(\frac{1}{\sqrt{T\ln T}})$, Algorithm 3
satisfies

(49)
$\displaystyle\mathcal{L}\left(\frac{1}{T}\sum_{t\in[T]}\bm{\theta}_{t-1}\right)\leq\mathcal{L}(\bm{\theta}^{*})+\mathcal{O}\left(\frac{u+1}{\sqrt{T}}\right)$

with probability at least $1-2\delta$, where
$u:=\sqrt{\frac{\ln(2T/\delta)}{cs}}\sigma$.

###### Proof.

Let $\delta=2Te^{-ck}$ in Lemma 6.3, we have with failure probability at most
$\delta$,

(50)
$\displaystyle\|\bm{e}_{t}\|_{2}\leq\sqrt{\frac{k}{s}}\sigma=\sqrt{\frac{\ln(2T/\delta)}{cs}}=u$

for $t\in[T]$. Now denote

(51)
$\displaystyle\bm{g}_{t}:=\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})\
\ \ \text{and}\ \ \ \bm{G}_{t}:=\nabla\mathcal{L}(\bm{\theta}_{t-1}).$

Since $\|\nabla\mathcal{L}_{i}(\bm{\theta}_{t-1})\|_{2}\leq G$, we have
$\|\bm{g}_{t}\|_{2},\|\bm{G}_{t}\|_{2}\leq G$ by triangle inequality. Now for
$t\in[T]$, consider

(52) $\displaystyle\ \ \ \ \|\bm{\theta}_{t}-\bm{\theta}^{*}\|_{2}^{2}$
$\displaystyle=\|\bm{\theta}_{t-1}-\bm{\theta}^{*}\|_{2}^{2}+2\eta\langle\bm{\theta}^{*}-\bm{\theta}_{t-1},\bm{g}_{t}+\bm{e}_{t}-\bm{G}_{t}\rangle$
(53) $\displaystyle\ \ \
+2\eta\langle\bm{\theta}^{*}-\bm{\theta}_{t-1},\bm{G}_{t}\rangle+\eta^{2}\|\bm{g}_{t}+\bm{e}_{t}\|_{2}^{2}$
$\displaystyle\leq\|\bm{\theta}_{t-1}-\bm{\theta}^{*}\|_{2}^{2}+2\eta\underbrace{\langle\bm{\theta}^{*}-\bm{\theta}_{t-1},\bm{g}_{t}+\bm{e}_{t}-\bm{G}_{t}\rangle}_{\epsilon_{t}}$
(54) $\displaystyle\ \ \
+2\eta(\mathcal{L}(\bm{\theta}^{*})-\mathcal{L}(\bm{\theta}_{t-1}))+2\eta^{2}\left(G+\|\bm{e}_{t}\|_{2}\right)^{2},$

where we use the convexity of $\mathcal{L}$ in the first inequality.
Rearranging both side, we have

(55) $\displaystyle\ \ \ \ \mathcal{L}(\bm{\theta}_{t-1})$ (56)
$\displaystyle\leq\mathcal{L}(\bm{\theta}^{*})+\frac{\|\bm{\theta}_{t-1}-\bm{\theta}^{*}\|_{2}^{2}-\|\bm{\theta}_{t}-\bm{\theta}^{*}\|_{2}^{2}}{2\eta}+\frac{\eta}{2}\left(G+u\right)^{2}+\epsilon_{t}.$

Now apply $\frac{1}{T}\sum\limits_{t\in[T]}$ to both sides, and note the
convexity of $\mathcal{L}$ again, we have

(57) $\displaystyle\ \ \ \
\mathcal{L}\left(\frac{1}{T}\sum_{t\in[T]}\bm{\theta}_{t-1}\right)$ (58)
$\displaystyle\leq\frac{1}{T}\sum\limits_{t\in[T]}\mathcal{L}(\bm{\theta}_{t-1})$
(59)
$\displaystyle\leq\mathcal{L}(\bm{\theta}^{*})+\frac{\|\bm{\theta}_{0}-\bm{\theta}^{*}\|_{2}^{2}}{2\eta
T}+\frac{\eta}{2}\left(G+u\right)^{2}+\frac{1}{T}\sum_{t\in[T]}\epsilon_{t}.$

Setting $\eta=\frac{\|\bm{\theta}_{0}-\bm{\theta}^{*}\|_{2}}{(G+u)\sqrt{T}}$,
we have

(60)
$\displaystyle\mathcal{L}\left(\frac{1}{T}\sum_{t\in[T]}\bm{\theta}_{t-1}\right)$
$\displaystyle\leq\mathcal{L}(\bm{\theta}^{*})+\frac{(G+u)C}{\sqrt{T}}+\frac{1}{T}\sum_{t\in[T]}\epsilon_{t}.$

Finally, it suffices to control the sum of error term
$\sum_{t\in[T]}\epsilon_{t}$. Note

(61) $\displaystyle\mathbb{E}[\epsilon_{t}\mid\bm{\theta}_{<t}]$
$\displaystyle=\mathbb{E}[\langle\bm{\theta}^{*}-\bm{\theta}_{t-1},\bm{g}_{t}+\bm{e}_{t}-\bm{G}_{t}\rangle\mid\bm{\theta}_{<t}]$
(62)
$\displaystyle=\big{<}\mathbb{E}[\bm{g}_{t}+\bm{e}_{t}-\bm{G}_{t}\mid\bm{\theta}_{<t}],\bm{\theta}^{*}-\bm{\theta}_{t-1}\big{>}$
(63) $\displaystyle=0,$

so $\\{\epsilon_{t}\\}_{t\in[T]}$ is a martingale difference sequence.
Further, by Cauchy-Schwarz and triangle inequality we have

(64) $\displaystyle\mathbb{E}|\epsilon_{t}|$
$\displaystyle\leq\|\bm{\theta}^{*}-\bm{\theta}_{t-1}\|_{2}(\|\bm{g}_{t}\|_{2}+\|\bm{G}_{t}\|_{2}+\|\bm{e}_{t}\|_{2})$
(65) $\displaystyle\leq(2G+u)C.$

Therefore, by Azuma-Hoeffding inequality (Corollary 2.20 in (Wainwright,
2019)) we have

(66)
$\displaystyle\sum_{t\in[T]}\epsilon_{t}\leq(2G+u)C\sqrt{2T\ln(1/\delta)}$

with probability at least $1-\delta$. Plugging Eq. (66) into Eq. (60) gives
the result as desired. ∎

###### Remark 6.5.

The error in the right hand side consists of two parts: the first term is
$\mathcal{L}(\bm{\theta}^{*})$, which can be made small by considering an
optimal reference point; the second term is
$\widetilde{\mathcal{O}}(\frac{1}{\sqrt{T}})$, which matches the standard
convergence rate of mini-batch gradient descent in the convex setting
_(Duchi,2018)_ up to a logarithmic factor, and achieves the exact rate when
there is no noise, i.e. $\sigma=0$.

####  6.2.2. Privacy Analysis

We will now turn to the privacy side. As mentioned at the beginning of this
section, we will not argue that Algorithm 3 is
$(\epsilon,\delta)$-differentially private, mainly because this is usually
seen as a privacy guarantee regarding membership inference attack. Therefore,
we choose the upper bound on $T^{*}$ that we can safely apply Criterion 4.2 as
a measurement of privacy leakage. We focus on the label recovery attack as the
feature attack is expected to fail, since it relies on the precise value of
the sensitive information and therefore can be easily broken by noise, whereas
the label recovery attack only requires the sensitive information to fall in a
certain range. Note such upper bound might not accurately reflect practice as
we are actually considering the worst case scenario and there could be
cancellation of noise in reality; nevertheless, compared to the similar result
presented in Corollary 4.5, this upper bound still sheds light on the
effectiveness of Gaussian mechanism. We will use experiments to provide
stronger support in the next section.

###### Theorem 6.6.

Suppose $\max\limits_{i}\\{|\bm{\theta}_{0}^{\top}\bm{x}_{i}|\\}=\epsilon<2$,
then Criterion 4.2 is valid for Algorithm 3 with

(67)
$\displaystyle\widetilde{T_{\epsilon}}=\bigg{\lceil}\log_{\left(1+\frac{\eta}{4}\right)}\left(\frac{4u+4}{4u+2+\epsilon}\right)\bigg{\rceil}<{T_{\epsilon}}$

with probability at least $1-\delta$, where $u$ is defined in Theorem 6.4.

###### Proof.

Define $q_{t}=\max\limits_{i}\\{|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|+p\\}$
where $p=4u+2$. By the update formula of Algorithm 3, which is given by Eq.
(44), for $1\leq j\leq n$ we have

(68)
$\displaystyle\bm{\theta}_{t}^{\top}\bm{x}_{j}=\bm{\theta}_{t-1}^{\top}\bm{x}_{j}-\frac{\eta}{4s}\sum_{i\in\mathcal{B}_{t}}(\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-2y_{i})\bm{x}_{i}^{\top}\bm{x}_{j}-\eta\bm{e}_{t}^{\top}\bm{x}_{j}.$

Discarding the failure probability and applying Cauchy-Schwarz and triangle
inequality, we have

(69)
$\displaystyle\big{|}\bm{\theta}_{t}^{\top}\bm{x}_{j}\big{|}\leq\big{|}\bm{\theta}_{t-1}^{\top}\bm{x}_{j}\big{|}+\frac{\eta}{4s}\sum_{i\in\mathcal{B}_{t}}\left(\big{|}\bm{\theta}_{t-1}^{\top}\bm{x}_{i}\big{|}+2\right)+\eta
u,$

with probability at least $1-\delta$, implying

(70)
$\displaystyle\left(\big{|}\bm{\theta}_{t}^{\top}\bm{x}_{j}\big{|}+p\right)\leq\left(\big{|}\bm{\theta}_{t-1}^{\top}\bm{x}_{j}\big{|}+p\right)+\frac{\eta}{4s}\sum_{i\in\mathcal{B}_{t}}\left(\big{|}\bm{\theta}_{t-1}^{\top}\bm{x}_{i}\big{|}+p\right),$

Taking maximum over $1\leq j\leq n$ on both side, we immediately have

(71) $\displaystyle q_{t+1}\leq\left(1+\frac{\eta}{4}\right)q_{t}.$

Finally, note $q_{1}=4u+2+\epsilon$ and the threshold of failure is
$4u+4+\epsilon$. Therefore, Criterion 4.2 is valid for

(72)
$\displaystyle\widetilde{T_{\epsilon}}=\bigg{\lceil}\log_{\left(1+\frac{\eta}{4}\right)}\left(\frac{4u+4}{4u+2+\epsilon}\right)\bigg{\rceil}.$

∎

##  7\. Experiments

In this section, we implement vertical logistic regression on practical
problems including classifying digits 0 and 1 in MNIST dataset (LeCun et al.,
2010) and predicting default payments on UCL default of credit card clients
Data Set (Yeh and Lien, 2009) to showcase the effectiveness of our label
attack and defense strategy.

##### Data.

MNIST is a dataset of the images of handwritten digits from 0 to 9. For
evaluating vertical logistic regression, we take all the 0, 1 from MNIST and
construct a binary classification problem. We assign label -1 to digit 0 and
label 1 to digit 1 in the binary classification problem. There are 5923
training samples and 980 test samples for digit 0; 6742 training samples and
1135 test samples for digit 1, respectively. UCL default of credit card
clients Data Set (abbreviated as credit) contains information on default
payments, demographic factors, credit data, history of payment, and bill
statements of credit card clients in Taiwan from April 2005 to September 2005.
There are 30000 samples and we randomly split them into a training set of
27000 samples and a test set of 3000 samples. Each sample has a 23-dimensional
feature and a binary label. We standardize the features of the credit dataset
before processing logistic regression.

##### Learning Setting.

For both datasets, we consider the vertical logistic regression where Party A
can access the first half of the features and Party B can access the last
half. The batch size is set to 256. Note here we focus on the validity of
Criterion 4.2, which only involves the value of the full inner product, hence
independent of the choices of batch size or the splitting ratio. We mildly
tune the learning rate from $[0.001,0.003,0.01]$ and choose 0.01 as the final
learning rate. We evaluate 3 commonly-used initialization schemes including
zero initialization (set all parameters to 0), Xavier Initialization (Glorot
and Bengio, 2010) Kaiming Initialization (He et al., 2015). We set the total
number of epochs to 30 and 10 for MNIST and credit dataset, respectively. For
each setting, we repeat the experiment with 5 different random seeds and plot
both mean (solid curve) and standard error (shadow).

##### Attack and Defense.

We evaluate our attack by calculating the alignment of the label obtained from
Criterion 4.2 with the true label. For defense, we implement Algorithm 3 with
different $\epsilon\in[0.1,0.2,0.5]$ and fix $\delta$ to 0.1. Although we
don’t consider $(\epsilon,\delta)$-DP as a formal privacy guarantee, we can
still heuristically estimate the $\ell_{2}$-sensitivity iteratively and
demonstrate that Algorithm 3 satisfies $(\epsilon,\delta)$-DP with

(73)
$\displaystyle\sigma_{A}=\sqrt{2\ln\left(\frac{5}{4\delta}\right)}\frac{\sqrt{\frac{8G^{2}e^{2}T\eta^{2}}{s}+64G^{2}e}}{\epsilon},$
(74)
$\displaystyle\sigma_{B}=\sqrt{2\ln\left(\frac{5}{4\delta}\right)}\frac{\sqrt{\frac{8G^{2}e^{2}T\eta^{2}}{s}+(8G-4)^{2}e}}{\epsilon}.$

The detailed derivation is deferred to Appendix D. We then calculate the
standard deviations $\sigma_{A},\sigma_{B}$ according to the above equations
where $T$ is chosen to be $30$ and $G$ is chosen to be $1$.

##### Results on MNIST.

In Figure 2, 3, we report the experiment results on MNIST under the setting
where the initialization follows Xavier Initialization. We observe that the
performance of VFL under our defense is comparative to that without defense,
especially for larger $\epsilon$. Meanwhile, the success rate of the label
attack is significantly reduced. Though the theory of differential privacy
encourages the choice of smaller $\epsilon$, we find that, in practice, even
for $\epsilon$ as large as $0.5$, the success rate of label attack is as small
as a random guess. This is because $\sigma_{A},\sigma_{B}$ are already very
large (larger than 10) for $\epsilon=0.5$. The results under Kaiming
Initialization are similar. For zero initialization, the success rate of label
attack stays $100\%$ for 10 more epochs than Xavier Initialization while the
accuracy increases faster.

Figure 2. Training and test accuracy under different settings on MNIST. VFL
can achieve good performance, i.e., more than $90\%$ test accuracy, even for
$\epsilon$ as small as $0.2$.

Figure 3. Other results on MNIST. Top: For all choices of $\epsilon$, the
success rate of label attack is reduced to about $50$%, which is same to
random guess. In contrast, for VFL without defense, the success rate of label
attack is $100\%$ for several epochs. This validates the effectiveness of our
attack and defense. Bottom: Norm of $\bm{\theta}$ is bounded by 2 throughout
training, which verify the choice of $G=1$.

##### Results on credit dataset.

In Figure 4 we report the experiment results on credit dataset. The results
are similar to MNIST. Since the dimension of the features in credit dataset is
small, i.e., 23, the scales of Xavier Initialization and Kaiming
Initialization are large. We thus use this dataset to provide a comparison
between different initialization schemes. As shown in Figure 4, Xavier
Initialization has slower convergence speed while the success rate of attack
is lower than 1. This phenomenon partially explains why most of existing
frameworks of VLR prefer to use zero initialization and verifies our analysis
in Section 3.

Figure 4. Experiment results on credit dataset with a highlight on the
comparison between different initialization schemes. Models with Xavier
Initialization converge slower than those with zero initialization as shown in
Top and Middle figures. The success rate of label attack is less than 1 for
Xavier Initialization on credit dataset because the feature dimension is small
(23 dimensions) so that the scale of Xavier Initialization is large.

##  8\. Conclusion

In this paper, we provide a formal privacy analysis for VLR, under an oracle
of obtaining local gradients at each iteration within the honest-but-curious
threat model. When the linear system is uniquely solvable, i.e. $s\leq d_{A}$
or $s\leq d_{B}$, we 1) identify feature attack for Party $A$ when $d_{B}=1$
and provide hardness result when $d_{B}\geq 2$; 2) construct label recovery
attack for Party $B$ when the initialization is small. By taking into account
the protocol of obtaining gradient, which is mainly based on Homomorphic
Encryption, we propose an active attack via generating and compressing
auxiliary ciphertext and thereby relax the constraints of batch size. Since
increasing the batch size might not be adequate to addressing the privacy
leakage, we adopt a simple-yet-effective countermeasure based on DP, which
injects noise to the sensitive information before communication. We provide
both utility and privacy guarantees for the updated algorithm. Experiment
results on benchmark datasets demonstrate the effectiveness of our attack and
defense, indicating the vulnerability of existing frameworks as well as the
power of coupling DP with HE techniques.

To be fair, other forms of attacks certainly exist (either simpler or being
much more sophisticated) beyond those proposed in this paper. For example, it
is possible that when the feature dimension is small, inference attacks using
model’s predictions could reveal partial information about the data. It is
also possible that some advanced techniques (such as gradient inversion (Yin
et al., 2021)) could allow the adversary to recover much more information
about the data. However, our goal in this paper is to analyze the existence of
privacy leakage in a provable, mathematically-rigorous manner. A desirable
answer should either be ‘Yes’, as suggested in Theorem 3.5, 4.1 and 4.8, or
‘No’, as pointed out by Theorem 3.6. Saying in another way, we are trying to
uncover the most intrinsic and fundamental vulnerability of the VLR systems
that resort to the gradient oracle. We believe this is exactly what separates
our paper from previous works.

In all, our work suggests that all VFL frameworks that solely rely on HE might
contain severe privacy risks, and DP, being an important building block of
horizontal federated learning, can also exert its power in the vertical
setting. We hypothesize that a hybrid protocol that makes use of both HE (or
MPC) and DP would lead to the best practical performance. From a broader
perspective, we hope this work would inspire more works to focus on the
(rigorous) privacy analysis of general VFL beyond logistic regression, which
could lead to substantial improvement over existing algorithms and protocols.

## References

  * (1)
  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016.  Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 308–318.
  * Acar et al. (2018) Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti. 2018\.  A survey on homomorphic encryption schemes: Theory and implementation.  ACM Computing Surveys (CSUR) 51, 4 (2018), 1–35.
  * Aono et al. (2016) Yoshinori Aono, Takuya Hayashi, Le Trieu Phong, and Lihua Wang. 2016.  Scalable and secure logistic regression via homomorphic encryption. In Proceedings of the Sixth ACM Conference on Data and Application Security and Privacy. 142–144.
  * Aono et al. (2017) Yoshinori Aono, Takuya Hayashi, Lihua Wang, Shiho Moriai, et al. 2017\.  Privacy-preserving deep learning via additively homomorphic encryption.  IEEE Transactions on Information Forensics and Security 13, 5 (2017), 1333–1345.
  * Authors (2019a) The FATE Authors. 2019a.  Federated AI Technology Enabler (FATE).  (2019).  https://github.com/FederatedAI/FATE
  * Authors (2019b) The FATE Authors. 2019b.  Federated logistic regression.  (2019).  https://github.com/FederatedAI/FATE/blob/master/python/federatedml/linear_model/logistic_regression/
  * Authors (2019c) The PaddleFL Authors. 2019c.  PaddleFL.  (2019).  https://github.com/PaddlePaddle/PaddleFL
  * Authors (2019d) The TFF Authors. 2019d.  TensorFlow Federated (TFF).  (2019).  https://www.tensorflow.org/federated
  * Bagdasaryan et al. (2020) Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. 2020\.  How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics. PMLR, 2938–2948.
  * Baruch et al. (2019) Moran Baruch, Gilad Baruch, and Yoav Goldberg. 2019\.  A little is enough: Circumventing defenses for distributed learning.  arXiv preprint arXiv:1902.06156 (2019).
  * Bassily et al. (2014) Raef Bassily, Adam Smith, and Abhradeep Thakurta. 2014.  Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 464–473.
  * Beimel (2011) Amos Beimel. 2011\.  Secret-sharing schemes: A survey. In International conference on coding and cryptology. Springer, 11–46.
  * Bhagoji et al. (2019) Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. 2019.  Analyzing federated learning through an adversarial lens. In International Conference on Machine Learning. PMLR, 634–643.
  * Bouacida and Mohapatra (2021) Nader Bouacida and Prasant Mohapatra. 2021.  Vulnerabilities in Federated Learning.  IEEE Access 9 (2021), 63229–63249.
  * Caldas et al. (2018) Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečnỳ, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. 2018.  Leaf: A benchmark for federated settings.  arXiv preprint arXiv:1812.01097 (2018).
  * CCPA (2018) CCPA. 2018.  California Consumer Privacy Act (CCPA).  (2018).  https://www.caprivacy.org/
  * Chaudhuri et al. (2011) Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. 2011\.  Differentially private empirical risk minimization.  Journal of Machine Learning Research 12, 3 (2011).
  * Chen et al. (2021) Chaochao Chen, Jun Zhou, Li Wang, Xibin Wu, Wenjing Fang, Jin Tan, Lei Wang, Alex X Liu, Hao Wang, and Cheng Hong. 2021\.  When homomorphic encryption marries secret sharing: Secure large-scale sparse logistic regression and applications in risk control. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2652–2662.
  * Chen et al. (2018) Hao Chen, Ran Gilad-Bachrach, Kyoohyung Han, Zhicong Huang, Amir Jalali, Kim Laine, and Kristin Lauter. 2018.  Logistic regression over encrypted data from fully homomorphic encryption.  BMC medical genomics 11, 4 (2018), 3–12.
  * Cheng et al. (2021) Kewei Cheng, Tao Fan, Yilun Jin, Yang Liu, Tianjian Chen, Dimitrios Papadopoulos, and Qiang Yang. 2021.  Secureboost: A lossless federated learning framework.  IEEE Intelligent Systems (2021).
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805 (2018).
  * Duchi (2018) John C Duchi. 2018\.  Introductory lectures on stochastic optimization.  The mathematics of data 25 (2018), 99–185.
  * Dwork (2006) Cynthia Dwork. 2006\.  Differential privacy. In International Colloquium on Automata, Languages, and Programming. Springer, 1–12.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al. 2014\.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci. 9, 3-4 (2014), 211–407.
  * Erdogan et al. (2021) Ege Erdogan, Alptekin Kupcu, and A Ercument Cicek. 2021\.  Unsplit: Data-oblivious model inversion, model stealing, and label inference attacks against split learning.  arXiv preprint arXiv:2108.09033 (2021).
  * Feng and Yu (2020) Siwei Feng and Han Yu. 2020\.  Multi-participant multi-class vertical federated learning.  arXiv preprint arXiv:2001.11154 (2020).
  * Fredrikson et al. (2015) Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. 2015\.  Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security. 1322–1333.
  * Geiping et al. (2020) Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. 2020.  Inverting Gradients–How easy is it to break privacy in federated learning?  arXiv preprint arXiv:2003.14053 (2020).
  * Geyer et al. (2017) Robin C Geyer, Tassilo Klein, and Moin Nabi. 2017.  Differentially private federated learning: A client level perspective.  arXiv preprint arXiv:1712.07557 (2017).
  * Gharibshah et al. (2020) Zhabiz Gharibshah, Xingquan Zhu, Arthur Hainline, and Michael Conway. 2020.  Deep learning for user interest and response prediction in online display advertising.  Data Science and Engineering 5, 1 (2020), 12–26.
  * Glorot and Bengio (2010) Xavier Glorot and Yoshua Bengio. 2010.  Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, 249–256.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014\.  Generative Adversarial Nets. In Advances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (Eds.), Vol. 27. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2014/file/5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf
  * Gu et al. (2020) Bin Gu, Zhiyuan Dang, Xiang Li, and Heng Huang. 2020\.  Federated doubly stochastic kernel learning for vertically partitioned data. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2483–2493.
  * Hard et al. (2018) Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. 2018\.  Federated learning for mobile keyboard prediction.  arXiv preprint arXiv:1811.03604 (2018).
  * Hardy et al. (2017) Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Richard Nock, Giorgio Patrini, Guillaume Smith, and Brian Thorne. 2017.  Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption.  arXiv preprint arXiv:1711.10677 (2017).
  * Hazay and Lindell (2010) Carmit Hazay and Yehuda Lindell. 2010.  Efficient secure two-party protocols: Techniques and constructions.  Springer Science & Business Media.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2015\.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision. 1026–1034.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. 770–778.
  * He et al. (2019) Zecheng He, Tianwei Zhang, and Ruby B Lee. 2019.  Model inversion attacks against collaborative inference. In Proceedings of the 35th Annual Computer Security Applications Conference. 148–162.
  * Hitaj et al. (2017) Briland Hitaj, Giuseppe Ateniese, and Fernando Perez-Cruz. 2017\.  Deep models under the GAN: information leakage from collaborative deep learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 603–618.
  * Jochems et al. (2016) Arthur Jochems, Timo M Deist, Johan Van Soest, Michael Eble, Paul Bulens, Philippe Coucke, Wim Dries, Philippe Lambin, and Andre Dekker. 2016.  Distributed learning: developing a predictive model based on data from multiple hospitals without data leaving the hospital–a real life proof of concept.  Radiotherapy and Oncology 121, 3 (2016), 459–467.
  * Kairouz et al. (2019) Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. 2019\.  Advances and open problems in federated learning.  arXiv preprint arXiv:1912.04977 (2019).
  * Konečnỳ et al. (2016a) Jakub Konečnỳ, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. 2016a.  Federated optimization: Distributed machine learning for on-device intelligence.  arXiv preprint arXiv:1610.02527 (2016).
  * Konečnỳ et al. (2016b) Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. 2016b.  Federated learning: Strategies for improving communication efficiency.  arXiv preprint arXiv:1610.05492 (2016).
  * LeCun et al. (2010) Yann LeCun, Corinna Cortes, and Chris Burges. 2010\.  MNIST handwritten digit database.  (2010).
  * Li et al. (2022) Oscar Li, Jiankai Sun, Xin Yang, Weihao Gao, Hongyi Zhang, Junyuan Xie, Virginia Smith, and Chong Wang. 2022\.  Label Leakage and Protection in Two-party Split Learning. In International Conference on Learning Representations.  https://openreview.net/forum?id=cOtBRgsf2fO
  * Li et al. (2021) Yuchen Li, Yifan Bao, Liyao Xiang, Junhan Liu, Cen Chen, Li Wang, and Xinbing Wang. 2021.  Privacy Threats Analysis to Secure Federated Learning.  arXiv preprint arXiv:2106.13076 (2021).
  * Li et al. (2019) Zhaorui Li, Zhicong Huang, Chaochao Chen, and Cheng Hong. 2019\.  Quantification of the leakage in federated learning.  arXiv preprint arXiv:1910.05467 (2019).
  * Liu et al. (2020a) Yang Liu, Yan Kang, Chaoping Xing, Tianjian Chen, and Qiang Yang. 2020a.  A secure federated transfer learning framework.  IEEE Intelligent Systems 35, 4 (2020), 70–82.
  * Liu et al. (2020b) Yang Liu, Zhihao Yi, and Tianjian Chen. 2020b.  Backdoor attacks and defenses in feature-partitioned collaborative learning.  arXiv preprint arXiv:2007.03608 (2020).
  * Luo et al. (2021) Xinjian Luo, Yuncheng Wu, Xiaokui Xiao, and Beng Chin Ooi. 2021\.  Feature inference attack on model predictions in vertical federated learning. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 181–192.
  * McMahan et al. (2016) H Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. 2016\.  Federated learning of deep networks using model averaging.  arXiv preprint arXiv:1602.05629 (2016).
  * Melis et al. (2019) Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. 2019.  Exploiting unintended feature leakage in collaborative learning. In 2019 IEEE Symposium on Security and Privacy (SP). IEEE, 691–706.
  * Mohassel and Zhang (2017) Payman Mohassel and Yupeng Zhang. 2017.  Secureml: A system for scalable privacy-preserving machine learning. In 2017 IEEE symposium on security and privacy (SP). IEEE, 19–38.
  * Nasr et al. (2019) Milad Nasr, Reza Shokri, and Amir Houmansadr. 2019.  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP). IEEE, 739–753.
  * Okamoto and Uchiyama (1998) Tatsuaki Okamoto and Shigenori Uchiyama. 1998.  A new public-key cryptosystem as secure as factoring. In International conference on the theory and applications of cryptographic techniques. Springer, 308–318.
  * Paillier (1999) Pascal Paillier. 1999\.  Public-key cryptosystems based on composite degree residuosity classes. In International conference on the theory and applications of cryptographic techniques. Springer, 223–238.
  * Rivest et al. (1978) Ronald L Rivest, Adi Shamir, and Leonard Adleman. 1978\.  A method for obtaining digital signatures and public-key cryptosystems.  Commun. ACM 21, 2 (1978), 120–126.
  * Ryffel et al. (2018) Theo Ryffel, Andrew Trask, Morten Dahl, Bobby Wagner, Jason Mancuso, Daniel Rueckert, and Jonathan Passerat-Palmbach. 2018\.  A generic framework for privacy preserving deep learning.  arXiv preprint arXiv:1811.04017 (2018).
  * Shokri et al. (2017) Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. 2017.  Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP). IEEE, 3–18.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. 2016\.  Mastering the game of Go with deep neural networks and tree search.  nature 529, 7587 (2016), 484–489.
  * Song et al. (2013) Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. 2013\.  Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing. IEEE, 245–248.
  * Tripathi et al. (2018) MM Tripathi et al. 2018\.  Zero Initialization of modified Gated Recurrent Encoder-Decoder Network for Short Term Load Forecasting.  arXiv preprint arXiv:1812.03425 (2018).
  * Truex et al. (2019) Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. 2019.  A hybrid approach to privacy-preserving federated learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security. 1–11.
  * Vershynin (2018) Roman Vershynin. 2018\.  High-dimensional probability: An introduction with applications in data science. Vol. 47.  Cambridge university press.
  * Voigt and Von dem Bussche (2017) Paul Voigt and Axel Von dem Bussche. 2017.  The eu general data protection regulation (gdpr).  A Practical Guide, 1st Ed., Cham: Springer International Publishing 10 (2017), 3152676\.
  * Wainwright (2019) Martin J Wainwright. 2019\.  High-dimensional statistics: A non-asymptotic viewpoint. Vol. 48.  Cambridge University Press.
  * Wang (2019) Guan Wang. 2019\.  Interpret federated learning with shapley values.  arXiv preprint arXiv:1905.04519 (2019).
  * Wang et al. (2019) Zhibo Wang, Mengkai Song, Zhifei Zhang, Yang Song, Qian Wang, and Hairong Qi. 2019\.  Beyond inferring class representatives: User-level privacy leakage from federated learning. In IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2512–2520.
  * Webank (2019a) Webank. 2019a.  A case of traffic violations insurance-using federated learning.  (2019).  https://www.fedai.org/cases
  * Webank (2019b) Webank. 2019b.  Utilization of FATE in risk management of credit in small and micro enterprises.  (2019).  https://www.fedai.org/cases
  * Wei et al. (2020) Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. 2020.  Federated learning with differential privacy: Algorithms and performance analysis.  IEEE Transactions on Information Forensics and Security 15 (2020), 3454–3469.
  * Weng et al. (2020) Haiqin Weng, Juntao Zhang, Feng Xue, Tao Wei, Shouling Ji, and Zhiyuan Zong. 2020\.  Privacy leakage of real-world vertical federated learning.  arXiv preprint arXiv:2011.09290 (2020).
  * Wu et al. (2013) Shuang Wu, Tadanori Teruya, Junpei Kawamoto, Jun Sakuma, and Hiroaki Kikuchi. 2013.  Privacy-preservation for stochastic gradient descent application to secure logistic regression. In The 27th Annual Conference of the Japanese Society for Artificial Intelligence, Vol. 27. 1–4.
  * Yang et al. (2019) Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. 2019\.  Federated machine learning: Concept and applications.  ACM Transactions on Intelligent Systems and Technology (TIST) 10, 2 (2019), 1–19.
  * Yeh and Lien (2009) I-Cheng Yeh and Che-hui Lien. 2009.  The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients.  Expert Systems with Applications 36, 2 (2009), 2473–2480.
  * Yin et al. (2021) Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M Alvarez, Jan Kautz, and Pavlo Molchanov. 2021\.  See through Gradients: Image Batch Recovery via GradInversion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 16337–16346.
  * Zhao et al. (2020) Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. 2020\.  idlg: Improved deep leakage from gradients.  arXiv preprint arXiv:2001.02610 (2020).
  * Zheng et al. (2020) Fanglan Zheng, Kun Li, Jiang Tian, Xiaojia Xiang, et al. 2020\.  A vertical federated learning method for interpretable scorecard and its application in credit scoring.  arXiv preprint arXiv:2009.06218 (2020).
  * Zhu and Han (2020) Ligeng Zhu and Song Han. 2020.  Deep leakage from gradients.  In Federated learning. Springer, 17–31.

##  Appendix A Omitted Proofs from Section 3

###### Proof of Theorem 3.1.

We use $m(E)$ to denote the Lebesgue measure of set
$E\in\mathbb{R}^{d^{\prime}\times n}$. Since the data are randomly sampled
from a continuous probability distribution, it suffices to show the following
set

(75) $\displaystyle L:=\bigg{\\{}\exists\mathcal{B}\subseteq D\ \ s.t.\ \
|\mathcal{B}|=s\wedge\\{\bm{z}_{j}\\}_{j\in\mathcal{B}}\ \ \text{are linear
dependent}\bigg{\\}}$

is of Lebesgue measure zero. Note

(76) $\displaystyle C:=\bigg{\\{}\mathcal{B}\subseteq
D:|\mathcal{B}|=s\bigg{\\}}$

is finite, so by taking a union bound, it suffices to show: for a fixed set
$\mathcal{B}$ satisfying $|\mathcal{B}|=s$,

(77) $\displaystyle
E_{\mathcal{B}}=\bigg{\\{}\\{\bm{z}_{j}\\}_{j\in\mathcal{B}}\ \ \text{are
linear dependent}\bigg{\\}}$

is of Lebesgue measure zero. Denote the matrix concatenated by
$\\{\bm{z}_{j}\\}_{j\in\mathcal{B}}$ in column as
$\bm{M}\in\mathbb{R}^{d^{\prime}\times s}$ and the $i$-th row of $\bm{M}$ to
be $\bm{m}_{i}^{\top}$. Note that $\\{\bm{z}_{j}\\}_{j\in\mathcal{B}}$ are
linear independent is equivalent to

$\displaystyle\forall 1\leq i_{1}<\cdots<i_{s}\leq d^{\prime},\ \ s.t.\ \
\det\left(\bigg{\\{}\bm{m}_{i_{1}},\cdots,\bm{m}_{i_{s}}\bigg{\\}}\right)=0.$

Further, singular matrix has zero Lebesgue measure, so

(78) $\displaystyle m(E_{\mathcal{B}})\leq
m\bigg{(}\det\left(\bigg{\\{}\bm{m}_{i_{1}},\cdots,\bm{m}_{i_{s}}\bigg{\\}}\right)=0\bigg{)}=0,$

which gives the result as desired. ∎

###### Proof of Lemma 3.4.

We say a set $G\subset\\{1,2,\cdots,n\\}$ is sortable if for $i,j\in G$, we
hold the value of $x_{i}^{B}/x_{j}^{B}$. The idea is to count the number of
sortable set at the end of each epoch $t$, which we denote as $n_{t}$. Note
for two sets $G_{1}$ and $G_{2}$, if $p\in G_{1},q\in G_{2}$, and both $p,q$
appears in the same batch, then we can merge $G_{1}$ and $G_{2}$ into a larger
sortable set. Eventually our goal is to obtain a single set
$\\{1,2,\cdots,n\\}$ via merging.

After the first epoch, there are $m$ different sets
$\mathcal{B}_{1},\cdots,\mathcal{B}_{m}$, so $n_{1}=m$. Now, suppose at the
end of epoch $t$, there is a set $G$ constituted of $k$ different
$\mathcal{B}_{i}$ and $1\leq k\leq m-1$, then the probability of the following
event

(79) $\displaystyle E_{G}=\\{\forall j\in[tm+1,tm+m],\ S_{j}\subset G\ \vee\
S_{j}\cap G=\emptyset\\}$

(i.e. $G$ is regrouped into $k$ new batches in
$\\{\mathcal{B}_{j}\\}_{j\in[tm+1,tm+m]}$) can be bounded as

(80)
$\displaystyle\frac{\prod_{i=1}^{k}C_{is}^{s}\prod_{j=1}^{m-k}C_{js}^{s}}{\prod_{l=1}^{m}C_{ls}^{s}}\leq\frac{1}{C_{ms}^{s}}\leq\frac{1}{m^{s}}.$

Here, the randomness comes from the random draw of the mini-batches. Also,
when $E_{G}$ does not happen, by definition the set $G$ will intertwine with
an element $q\notin G$. Suppose $q\in\mathcal{B}_{l}$ for some $l\in[m]$, then
$G$ will merge with a larger group that contains $\mathcal{B}_{l}$ as its
subset. Therefore, with failure probability at most $\frac{n_{t}}{m^{s}}$,
each of the set will merge with another in the following epoch, leading to
$n_{t+1}\leq n_{t}/2$. Hence, we can obtain a single set $\\{1,2,\cdots,n\\}$
in at most $T=\lfloor\log_{2}(m)\rfloor+1$ epochs, and by union bound the
failure probability is at most

(81)
$\displaystyle\sum_{t=1}^{T}\frac{n_{t}}{m^{s}}\leq\frac{2n_{1}}{m^{s}}=\frac{2}{m^{s-1}}.$

∎

##  Appendix B Omitted proofs from Section 4

###### Proof of Theorem 4.1.

Since $d_{A}=0$, we have

(82)
$\displaystyle\bm{\theta}_{t-1}^{\top}\bm{x}_{i}=\left(\bm{\theta}^{B}_{t-1}\right)^{\top}\bm{x}^{B}_{i}.$

Therefore, by extracting the information known to himself, Party $B$ can
deduce the information of

(83) $\displaystyle\bm{I}_{t}=\sum_{i\in\mathcal{B}_{t}}y_{i}\bm{x}^{B}_{i}.$

We will now show the constrained linear system

(84) $\left\\{\begin{aligned}
\sum_{i\in\mathcal{B}_{t}}z_{i}\bm{x}^{B}_{i}&=\bm{I}_{t}\\\ s.t.\ \ \
z_{i}^{2}&=1,\ \ \ \forall i\in\mathcal{B}_{t}\end{aligned}\right.$

with respect to $\\{z_{i}\\}_{i\in\mathcal{B}_{t}}$ has unique solution with
probability one. The existence is trivial since $z_{i}=y_{i},\ \forall
i\in\mathcal{B}_{t}$ is a solution. To see the uniqueness, suppose there are
two different solutions $\\{z_{i}\\}_{i\in\mathcal{B}_{t}}$ and
$\\{\tilde{z}_{i}\\}_{i\in\mathcal{B}_{t}}$ satisfying Eq. (84). Taking the
difference, we have

(85) $\displaystyle\sum_{i\in\mathcal{B}_{t}}w_{i}\bm{x}^{B}_{i}=0,$

where

(86) $\displaystyle\bm{w}\neq\bm{0}\ \wedge\ w_{i}\in\\{-1,0,1\\},\ \ \ \
\forall i\in\mathcal{B}_{t}.$

Denote the set that contains all possible $\bm{w}$ in (86) as $T^{s}$. Similar
to the proof in Theorem 3.1, we only need to show for a fixed set
$\mathcal{B}\in D$ with $|\mathcal{B}|=s$,

(87) $\displaystyle E_{\mathcal{B}}=\bigg{\\{}\exists\bm{w}\in T^{s}\ \ s.t.\
\ \sum_{i\in\mathcal{B}}w_{i}\bm{x}^{B}_{i}=0\bigg{\\}}$

is of Lebesgue measure zero. Since $T^{s}$ is a finite set with cardinality
$3^{s}-1$, it suffices to show for a fixed $\bm{w}\in T^{s}$ that

(88) $\displaystyle
L_{\mathcal{B}}=\bigg{\\{}\sum_{i\in\mathcal{B}}w_{i}\bm{x}^{B}_{i}=0\bigg{\\}}$

satisfies $m(L_{\mathcal{B}})=0$. This is obviously true since the data
$\\{\bm{x}^{B}_{i}\\}_{i\in[n]}$ is drawn from a continuous probability
distribution, and that $L_{\mathcal{B}}$ is a proper subspace of
$\mathbb{R}^{d_{B}\times s}$.

∎

##  Appendix C Omitted proof from Section 6

###### Proof of Lemma 6.3.

By considering a union bound, it suffices to show

(89)
$\displaystyle\|\bm{e}_{t}\|_{2}\leq\sqrt{\frac{k}{s}}\max\\{\sigma_{A},\sigma_{B}\\}$

holds with probability at least $1-2\exp(-ck)$ for a fixed $t$. Note

(90)
$\displaystyle\|\bm{e}_{t}\|_{2}\leq\frac{1}{4s}\left(\|\bm{X}_{\mathcal{B}_{t}}^{A}\bm{Z}^{B}\|_{2}+\|\bm{X}_{\mathcal{B}_{t}}^{B}\bm{Z}^{A}\|_{2}\right),$

so by symmetry it suffices to show

(91) $\displaystyle\|\bm{X}_{\mathcal{B}_{t}}^{A}\bm{Z}^{B}\|_{2}\leq
2\sqrt{ks\sigma_{B}^{2}}$

with probability at least $1-\exp(-ck)$. Define
$\bm{P}_{A}:=\left(\bm{X}_{\mathcal{B}_{t}}^{A}\right)^{\top}\bm{X}_{\mathcal{B}_{t}}^{A}$,
then we have $\|\bm{P}_{A}\|_{F}^{2}\leq s^{2}$ and
$\|\bm{P}_{A}\|_{2}\leq\|\bm{P}_{A}\|_{F}\leq s$. Applying Hanson-Wright
inequality (Theorem 6.2.1 in (Vershynin, 2018)), we have for every $t>0$,

$\displaystyle\ \ \ \
\mathbb{P}\bigg{\\{}\left(\bm{Z}^{B}\right)^{\top}\bm{P}_{A}\bm{Z}^{B}-\mathbb{E}\left[\left(\bm{Z}^{B}\right)^{\top}\bm{P}_{A}\bm{Z}^{B}\right]\geq
t\bigg{\\}}$ (92)
$\displaystyle\leq\exp\left[-c\min\left(\frac{t^{2}}{9s^{2}\sigma_{B}^{4}},\frac{t}{3s\sigma_{B}^{2}}\right)\right].$

Pick $t=3ks\sigma_{B}$, then with probability at least $1-\exp(-ck)$, we have

(93) $\displaystyle\left(\bm{Z}^{B}\right)^{\top}\bm{P}_{A}\bm{Z}^{B}$
$\displaystyle\leq
3ks\sigma_{B}^{2}+\mathbb{E}\left[\left(\bm{Z}^{B}\right)^{\top}\bm{P}_{A}\bm{Z}^{B}\right]$
(94)
$\displaystyle=3ks\sigma_{B}^{2}+\sigma_{B}^{2}\operatorname{Tr}(\bm{P}_{A})$
(95) $\displaystyle\leq 4ks\sigma_{B}^{2},$

This finishes the proof as desired. ∎

##  Appendix D Heuristic $(\epsilon,\delta)$-DP Guarantee of Algorithm 3

We will show that Algorithm 3 satisfies $(\epsilon,\delta)$-DP (though we do
not see this as a formal privacy guarantee) when the variance of the Gaussian
random variables are chosen according to Eq. (73) and (74). We begin with a
useful definition.

###### Definition D.1 ($\ell_{2}$-sensitivity).

The $\ell_{2}$-sensitivity of a function $f:\mathcal{D}\to\mathbb{R}^{d}$ is
defined as:

(96)
$\displaystyle\Delta_{2}(f):=\max\limits_{D_{1},D_{2}}\|f(D_{1})-f(D_{2})\|_{2}$

for all $D_{1},D_{2}\in\mathcal{D}$ that differ by at most one instance.

Denote $f$ as the original algorithm given by Eq. (3). In the following
analysis, we will use $\Delta(\bm{v})$ to represent $\Delta_{2}(f_{\bm{v}})$,
where $f_{\bm{v}}$ repeats the procedure of $f$ until it outputs the
(intermediate) result $\bm{v}$.

For arbitrary dataset $D$ and $D^{\prime}$ which differ by at most one
instance, consider the corresponding sequences
$\\{\bm{\theta}_{t-1}\\}_{t\in[T]}$ and
$\\{\bm{\theta}_{t-1}^{\prime}\\}_{t\in[T]}$ generated via feeding $D$ and
$D^{\prime}$ to $f$, and the mini-batch at step $t$ are $\mathcal{B}_{t}$ and
$\mathcal{B}_{t}^{\prime}$ respectively. Our first step is to give a recursive
relation on $\Delta(\bm{\theta}_{t-1})$.

###### Lemma D.2.

Let $\eta\leq 1$. Then for $t\in[T]$, we have

(97)
$\displaystyle\Delta(\bm{\theta}_{t})\leq\begin{cases}\Delta(\bm{\theta}_{t-1})&\emph{if}\
\ \mathcal{B}_{t}=\mathcal{B}_{t}^{\prime}\\\
\Delta(\bm{\theta}_{t-1})+\frac{2\sqrt{2}\eta G}{s}&\emph{o.w.}\end{cases}$

###### Proof of Lemma D.2.

When $\mathcal{B}_{t}=\mathcal{B}_{t}^{\prime}$, we have

(98) $\displaystyle\ \ \ \
\|\bm{\theta}_{t}-\bm{\theta}_{t}^{\prime}\|_{2}^{2}-\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2}^{2}$
$\displaystyle=\eta^{2}\|\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})-\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1}^{\prime})\|_{2}^{2}$
(99) $\displaystyle\ \ \ \
-2\eta\langle\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime},\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})-\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1}^{\prime})\rangle$
(100)
$\displaystyle\leq-\left(\frac{2\eta}{\beta}-\eta^{2}\right)\|\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})-\nabla\mathcal{L}_{\mathcal{B}_{t}}(\bm{\theta}_{t-1}^{\prime})\|_{2}^{2}\leq
0,$

where we apply the co-coercivity of gradient in the inequality, since
$\mathcal{L}_{\mathcal{B}_{t}}$ is convex and $\frac{1}{4}$-smooth.

When $\mathcal{B}_{t}\neq\mathcal{B}_{t}^{\prime}$, they differ by at most one
instance. Denote their intersection as $\mathcal{I}_{t}$ and
$p=\mathcal{B}_{t}\backslash\mathcal{I}_{t},\
q=\mathcal{B}_{t}^{\prime}\backslash\mathcal{I}_{t}$. Now denote

(101)
$\displaystyle\bar{\mathcal{L}}_{t}(\bm{\theta})=\frac{s-1}{s}\mathcal{L}_{\mathcal{I}_{t}}(\bm{\theta}),$

then

(102) $\displaystyle\ \ \ \
\|\bm{\theta}_{t}-\bm{\theta}_{t}^{\prime}\|_{2}^{2}$
$\displaystyle=\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2}^{2}-2\eta\bigg{<}\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime},\nabla\bar{\mathcal{L}}_{t}(\bm{\theta}_{t-1})-$
$\displaystyle\ \ \ \
\nabla\bar{\mathcal{L}}_{t}(\bm{\theta}_{t-1}^{\prime})+\frac{1}{s}\left(\nabla\mathcal{L}_{p}(\bm{\theta}_{t-1})-\nabla\mathcal{L}_{q}(\bm{\theta}_{t-1}^{\prime})\right)\bigg{>}+$
$\displaystyle\ \ \ \
\eta^{2}\bigg{\|}\nabla\bar{\mathcal{L}}_{t}(\bm{\theta}_{t-1}^{\prime})-\nabla\bar{\mathcal{L}}_{t}(\bm{\theta}_{t-1})+$
(103) $\displaystyle\ \ \ \ \ \ \ \
\frac{1}{s}\left(\nabla\mathcal{L}_{p}(\bm{\theta}_{t-1})-\nabla\mathcal{L}_{q}(\bm{\theta}_{t-1}^{\prime})\right)\bigg{\|}_{2}^{2}$
$\displaystyle\leq\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2}^{2}+\frac{4\eta
G}{s}\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2}+\frac{8\eta^{2}G^{2}}{s^{2}}$
(104)
$\displaystyle-\left(\frac{2\eta}{\beta}-2\eta^{2}\right)\|\nabla\bar{\mathcal{L}}_{t}(\bm{\theta}_{t-1})-\nabla\bar{\mathcal{L}}_{t}(\bm{\theta}_{t-1}^{\prime})\|_{2}^{2}$
(105)
$\displaystyle\leq\left(\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2}+\frac{2\sqrt{2}\eta
G}{s}\right)^{2}.$

Since the choice on $D$ and $D^{\prime}$ is arbitrary, we obtain the result as
desired. ∎

We now proceed to control $\Delta(\bm{SV}_{t}^{A})$ and
$\Delta(\bm{SV}_{t}^{B})$.

###### Lemma D.3.

Let $\eta\leq 1$. Then for $t\in[T]$, we have

(106) $\displaystyle\Delta(\bm{SV}_{t}^{A})$
$\displaystyle\leq\begin{cases}\sqrt{s}\Delta(\bm{\theta}_{t-1})&\emph{if}\ \
\mathcal{B}_{t}=\mathcal{B}_{t}^{\prime}\\\
\sqrt{s\Delta^{2}(\bm{\theta}_{t-1})+(8G)^{2}}&\emph{o.w.}\end{cases},$ (107)
$\displaystyle\Delta(\bm{SV}_{t}^{B})$
$\displaystyle\leq\begin{cases}\sqrt{s}\Delta(\bm{\theta}_{t-1})&\emph{if}\ \
\mathcal{B}_{t}=\mathcal{B}_{t}^{\prime}\\\
\sqrt{s\Delta^{2}(\bm{\theta}_{t-1})+(8G-4)^{2}}&\emph{o.w.}\end{cases}.$

###### Proof of Lemma D.3.

When $\mathcal{B}_{t}=\mathcal{B}_{t}^{\prime}$, we have

(108) $\displaystyle\|\bm{SV}_{t}^{A}-(\bm{SV}_{t}^{A})^{\prime}\|_{2}$
$\displaystyle=\sqrt{\sum_{i\in\mathcal{B}_{t}}\big{<}\bm{\theta}_{t-1}^{A}-(\bm{\theta}_{t-1}^{A})^{\prime},\bm{x}_{i}^{A}\big{>}^{2}}$
(109)
$\displaystyle\leq\sqrt{\sum_{i\in\mathcal{B}_{t}}\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2}^{2}\|\bm{x}_{i}\|_{2}^{2}}$
(110)
$\displaystyle\leq\sqrt{s}\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2},$

so $\Delta(\bm{SV}_{t}^{A})\leq\sqrt{s}\Delta(\bm{\theta}_{t-1})$. Similarly,
$\Delta(\bm{SV}_{t}^{B})\leq\sqrt{s}\Delta(\bm{\theta}_{t-1})$. On the other
hand, when $\mathcal{B}_{t}\neq\mathcal{B}_{t}^{\prime}$ we have

(111) $\displaystyle\ \ \ \|\bm{SV}_{t}^{A}-(\bm{SV}_{t}^{A})^{\prime}\|_{2}$
(114)
$\displaystyle=\sqrt{\begin{multlined}\sum_{i\in\mathcal{I}_{t}}\big{<}\bm{\theta}_{t-1}^{A}-(\bm{\theta}_{t-1}^{A})^{\prime},\bm{x}_{i}^{A}\big{>}^{2}\\\
+\left(\langle\theta_{t-1}^{A},\bm{x}_{p}^{A}\rangle-2y_{p}-\langle\theta_{t-1}^{A},\bm{x}_{q}^{A}\rangle+2y_{q}\right)^{2}\end{multlined}\sum_{i\in\mathcal{I}_{t}}\big{<}\bm{\theta}_{t-1}^{A}-(\bm{\theta}_{t-1}^{A})^{\prime},\bm{x}_{i}^{A}\big{>}^{2}\\\
+\left(\langle\theta_{t-1}^{A},\bm{x}_{p}^{A}\rangle-2y_{p}-\langle\theta_{t-1}^{A},\bm{x}_{q}^{A}\rangle+2y_{q}\right)^{2}\,}$
(115)
$\displaystyle\leq\sqrt{\sum_{i\in\mathcal{I}_{t}}\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2}^{2}\|\bm{x}_{i}\|_{2}^{2}+(8G)^{2}}$
(116)
$\displaystyle\leq\sqrt{s\|\bm{\theta}_{t-1}-\bm{\theta}_{t-1}^{\prime}\|_{2}^{2}+(8G)^{2}}.$

Therefore,
$\Delta(\bm{SV}_{t}^{A})\leq\sqrt{s\Delta^{2}(\bm{\theta}_{t-1})+(8G)^{2}}$.
Similarly,
$\Delta(\bm{SV}_{t}^{B})\leq\sqrt{s\Delta^{2}(\bm{\theta}_{t-1})+(8G-4)^{2}}$.
∎

Finally, we will resort to the following lemma, which relates
$\ell_{2}$-sensitivity to a DP guarantee and is standard in literature.

###### Lemma D.4 (Theorem A.1 of (Dwork et al., 2014)).

Let $f$ be an arbitrary function generating $d$-dimensional outputs and
$\epsilon\in(0,1)$. Then for $c^{2}>2\ln(1.25/\delta)$, the Gaussian Mechanism
with parameter $\sigma\geq c\Delta_{2}f/\epsilon$ is
$(\epsilon,\delta)$-differentially private.

The final result is stated in the following theorem.

###### Theorem D.5.

Let

(117)
$\displaystyle\sigma_{A}=\sqrt{2\ln\left(\frac{5}{4\delta}\right)}\frac{\sqrt{\frac{8G^{2}e^{2}T\eta^{2}}{s}+64G^{2}e}}{\epsilon},$
(118)
$\displaystyle\sigma_{B}=\sqrt{2\ln\left(\frac{5}{4\delta}\right)}\frac{\sqrt{\frac{8G^{2}e^{2}T\eta^{2}}{s}+(8G-4)^{2}e}}{\epsilon},$

then Algorithm 3 with step size $\eta\leq 1$ is
$(\epsilon,\delta)$-differentially private w.r.t.
$\\{Sec(\bm{SV}_{t}^{A})\\}_{t\in[T]}$ and
$\\{Sec(\bm{SV}_{t}^{B})\\}_{t\in[T]}$.

###### Proof of Theorem D.5.

Since there exists at most one $t$ in an epoch such that
$\mathcal{B}_{t}\neq\mathcal{B}_{t}^{\prime}$, we have

(119) $\displaystyle\Delta(\\{\bm{SV}_{t}^{A}\\}_{t\in[T]})$
$\displaystyle\leq\sqrt{\sum_{t\in[T]}\Delta^{2}(\bm{SV}_{t}^{A})}$ (120)
$\displaystyle\leq\sqrt{\sum_{t\in[T]}s\Delta^{2}(\bm{\theta}_{t-1})+(8G)^{2}e}$
(121) $\displaystyle\leq\sqrt{sm\sum_{i\in[e]}\left(\frac{2\sqrt{2}i\eta
G}{s}\right)^{2}+(8G)^{2}e}$ (122)
$\displaystyle\leq\sqrt{\frac{8G^{2}e^{2}T\eta^{2}}{s}+64G^{2}e},$

where we use Lemma D.3 in the second inequality, Lemma D.2 and the fact
$\Delta(\bm{\theta}_{0})=0$ in the third inequality. Similarly, we have

(123)
$\displaystyle\Delta(\\{\bm{SV}_{t}^{B}\\}_{t\in[T]})\leq\sqrt{\frac{8G^{2}e^{2}T\eta^{2}}{s}+(8G-4)^{2}e}.$

Applying Lemma D.4, we can conclude that Algorithm 3 is
$(\epsilon,\delta)$-differentially private w.r.t.
$\\{Sec(\bm{SV}_{t}^{A})\\}_{t\in[T]}$ and
$\\{Sec(\bm{SV}_{t}^{B})\\}_{t\in[T]}$. when $\Sigma_{A}$ and $\Sigma_{B}$ are
chosen according to Eq. (73) and (74). ∎

##  Appendix E Discussion of Minimax Approximation

Let $P_{d}$ denote the set of polynomials of degree at most $d$, and for a
continuous function $f\in C[a,b]$ denote

(124) $\displaystyle\|f\|_{\infty}=\max\big{\\{}|f(x)|:x\in[a,b]\big{\\}},$

the minimax approximation is then defined as follow.

###### Definition E.1.

$p\in P_{d}$ is a $d$-th minimax approximation of $f\in C[a,b]$ if

(125) $\displaystyle\|p-f\|_{\infty}=\inf\limits_{q\in
P_{d}}\big{\\{}\|q-f\|_{\infty}\big{\\}}.$

Consider the $3$-th minimax approximate of the sigmoid function of $[-5,5]$,
which is shown to be

(126) $\displaystyle\sigma_{3}(z)=-0.004z^{3}+0.197z+0.5$

in (Chen et al., 2018). The mini-batch gradient can then be approximated as

(127)
$\displaystyle\nabla\ell_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})\approx\frac{1}{s}\sum_{i\in\mathcal{B}_{t}}f_{i,t}\bm{x}_{i}$

at $t$-th iteration, where the coefficient is defined through

(128) $\displaystyle
f_{i,t}:=-0.004(\bm{\theta}_{t-1}^{\top}\bm{x}_{i})^{3}+0.197\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-0.5y_{i}.$

We assume $s\leq\min\\{d_{A},d_{B}\\}$ in the following analyses, so that both
parties can learn the precise value of $f_{i,t}$ with probability one by
Theorem 3.1.

###  E.1. Privacy Analysis for Party $B$

Decompose

(129)
$\displaystyle\bm{\theta}_{t-1}^{\top}\bm{x}_{i}=\underbrace{\left(\bm{\theta}^{A}_{t-1}\right)^{\top}\bm{x}^{A}_{i}}_{g^{A}_{i,t}}+\underbrace{\left(\bm{\theta}^{B}_{t-1}\right)^{\top}\bm{x}^{B}_{i}}_{g^{B}_{i,t}}.$

So by extracting the information known to himself (the part involving
$g_{i,t}^{A}$ and $y_{i}$) from $f_{i,t}$, Party $A$ can obtain the
information of

$\displaystyle r_{i,t}$
$\displaystyle=-0.004\left(g^{B}_{i,t}\right)^{3}-0.012g^{A}_{i,t}\left(g^{B}_{i,t}\right)^{2}$
(130) $\displaystyle\ \ \
-\left(0.012\left(g^{A}_{i,t}\right)^{2}-0.197\right)g^{B}_{i,t},$

which is a cubic polynomial with respect to the variable $g_{i,t}^{B}$.
Consider the corresponding function

(131) $\displaystyle
m_{i,t}(z)=0.004z^{3}+0.012g^{A}_{i,t}z^{2}+\left(0.012\left(g^{A}_{i,t}\right)^{2}-0.197\right)z,$

it is straightforward to see that $-m_{i,t}(z)$ has a local maximum at
$z_{0}=\sqrt{\frac{197}{12}}-g^{A}_{i,t}$ and a local minimum at
$z_{1}=-\sqrt{\frac{197}{12}}-g^{A}_{i,t}$. Therefore, $A$ can uniquely
determine $g^{B}_{i,t}$ from $r_{i,t}$ iff

$\displaystyle r_{i,t}\notin[-m_{i,t}(z_{1}),-m_{i,t}(z_{0})].$

Denote

(132)
$\displaystyle\mathcal{C}_{t}=\\{i\in\mathcal{B}_{t}:r_{i,t}\notin[-m_{i,t}(z_{1}),-m_{i,t}(z_{0})]\\},$

then under $d_{B}=1$, Party $A$ can sort $\mathcal{C}_{t}$ according to the
$x_{B}$ feature. If we assume the full dataset $D$ becomes sortable in $Q$
epochs, then using a similar approach as in Theorem 3.5, we obtain the
following theorem.

###### Theorem E.2.

In the minimax approximation scheme, suppose $s\leq d_{A}$ and $d_{B}=1$, and
$D$ becomes sortable in $Q$ epochs. Then Party $A$ can learn the precise value
of the data in terms of feature $x_{B}$(up to a difference in sign) in
$\max\\{Q,2\\}$ epochs.

###  E.2. Privacy Analysis for Party $A$

In analogy to Theorem 4.1, Party $B$ can determine the label within every
batch with probability one if $d_{A}=0$ (note this does not require $s\leq
d_{B}$). Now suppose $d_{A}\geq 1$ and $s\leq d_{B}$. Note

(133) $\displaystyle
f_{i,t}\mid_{\bm{\theta}_{t-1}^{\top}\bm{x}_{i}=0}=-0.5y_{i},$

so the intuition in Section 4 holds and the analyses naturally breaks into two
parts. It is straightforward to see that the first part only involves the
initialization of $\bm{\theta}_{0}$ and is irrelevant to the approximation
method, so we will mainly focus on the second part. First, consider

(134) $\displaystyle n(z)=-0.004z^{3}+0.197z,$

then it is straightforward to verify that

$\displaystyle|n(z)|<0.5,\ \ \forall|z|<3.2.$

This implies that Criterion 4.2 is valid at iteration $t$ if

(135)
$\displaystyle\max\limits_{i}\\{|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|\\}\leq
3.2.$

Now, assuming a constant learning rate $\eta_{t}=\eta$, we have

$\displaystyle\bm{\theta}_{t}^{\top}\bm{x}_{i}=\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-\frac{\eta}{s}\sum_{j\in\mathcal{B}_{t}}[$
$\displaystyle-0.004(\bm{\theta}_{t-1}^{\top}\bm{x}_{j})^{3}+0.197\bm{\theta}_{t-1}^{\top}\bm{x}_{j}$
(136) $\displaystyle-0.5y_{j}]\bm{x}_{j}^{\top}\bm{x}_{i}.$

Applying Triangle Inequality and Cauchy-Schwarz Inequality,

(137)
$\displaystyle|\bm{\theta}_{t}^{\top}\bm{x}_{i}|\leq|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|+\frac{\eta}{s}\sum_{j\in\mathcal{B}_{t}}[0.004|\bm{\theta}_{t-1}^{\top}\bm{x}_{j}|^{3}+0.197|\bm{\theta}_{t-1}^{\top}\bm{x}_{j}|+0.5].$

Suppose $\max\limits_{i}\\{|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|\\}<3.2$ and
taking maximum over both side, we have

(138)
$\displaystyle\max_{i}\\{|\bm{\theta}_{t}^{\top}\bm{x}_{i}|\\}\leq\left(1+\frac{\eta}{4}\right)\max_{i}\\{|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|\\}+\frac{\eta}{2}.$

Therefore,
$h_{t}:=\max\limits_{i}\\{|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|+2\\}$ satisfies

(139) $\displaystyle h_{t+1}\leq\left(1+\frac{\eta}{4}\right)h_{t}.$

Note now the threshold becomes $3.2+2=5.2$, and we immediately have the
following theorem.

###### Theorem E.3.

In the minimax approximation scheme, If $\bm{\theta}_{0}$ is initialized (with
high probability) such that

(140)
$\displaystyle\max_{i}\\{|\bm{\theta}_{0}^{\top}\bm{x}_{i}|\\}=\epsilon<2,$

then Criterion 4.2 is valid for

(141)
$\displaystyle\overline{T_{\epsilon}}=\bigg{\lceil}\log_{\left(1+\frac{\eta}{4}\right)}\left(\frac{5.2}{2+\epsilon}\right)\bigg{\rceil}$

(with high probability).

##  Appendix F Discussion of Piecewise Approximation

Another commonly used approximation method of the sigmoid function is the
piecewise linear approximation (Mohassel and Zhang, 2017):

(142) $S(z)\approx\begin{cases}0,&z\leq-0.5\\\ z+0.5,&|z|<0.5\\\ 1,&z\geq
0.5\end{cases}.$

The mini-batch gradient can then be approximated as

(143)
$\displaystyle\nabla\ell_{\mathcal{B}_{t}}(\bm{\theta}_{t-1})\approx\frac{1}{s}\sum_{i\in\mathcal{B}_{t}}f_{i,t}\bm{x}_{i}$

at $t$-th iteration, where the coefficient is defined through

$\displaystyle f_{i,t}:=$
$\displaystyle\vmathbb{1}[|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|<0.5](\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-0.5y_{i})$
(144) $\displaystyle+$
$\displaystyle\vmathbb{1}[y_{i}\bm{\theta}_{t-1}^{\top}\bm{x}_{i}\leq-0.5](-y_{i}).$

We assume $s\leq\min\\{d_{A},d_{B}\\}$ in the following analyses, so that both
parties can learn the precise value of $f_{i,t}$ with probability one by
Theorem 3.1.

###  F.1. Privacy Analysis for Party $B$

Note that

(145) $|f_{i,t}|=\begin{cases}1&\ \text{if}\ \
y_{i}\bm{\theta}_{t-1}^{\top}\bm{x}_{i}\leq-0.5\\\
|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-0.5y_{i}|\in(0,1)&\ \text{if}\ \
|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|<0.5\\\ 0&\ \text{if}\ \
y_{i}\bm{\theta}_{t-1}^{\top}\bm{x}_{i}\geq 0.5\end{cases}$

Decompose

(146)
$\displaystyle\bm{\theta}_{t-1}^{\top}\bm{x}_{i}=\underbrace{\left(\bm{\theta}^{A}_{t-1}\right)^{\top}\bm{x}^{A}_{i}}_{g^{A}_{i,t}}+\underbrace{\left(\bm{\theta}^{B}_{t-1}\right)^{\top}\bm{x}^{B}_{i}}_{g^{B}_{i,t}}.$

then there are three possible cases:

  * (1)

$|f_{\bm{i},t}|=1.$ Then Party $A$ can learn the range of $g_{i,t}^{B}$

(147) $g_{i,t}^{B}\begin{cases}\leq-0.5-g_{i,t}^{A},&\ \ \text{if}\ \ y=1,\\\
\geq 0.5-g_{i,t}^{A},&\ \ \text{if}\ \ y=-1.\end{cases}$

  * (2)

$0<|f_{i,t}|<1.$ Then Party $A$ can learn the precise value of
$g_{i,t}^{B}=f_{i,t}+0.5y_{i}-g_{i,t}^{A}$.

  * (3)

$f_{i,t}=0.$ Then Party $A$ can learn the range of $g_{i,t}^{B}$

(148) $g_{i,t}^{B}\begin{cases}\geq 0.5-g_{i,t}^{A},&\ \ \text{if}\ \ y=1,\\\
\leq-0.5-g_{i,t}^{A},&\ \ \text{if}\ \ y=-1.\end{cases}$

Therefore, if Party $A$ collect those instance which falls into the second
case:

(149) $\displaystyle D_{t}=\\{i\in\mathcal{B}_{t}:0<|f_{i,t}|<1\\},$

then under $d_{B}=1$, he can sort the data in $D_{t}$ according to the $x_{B}$
feature. Also, similar to the previous method, we have the following theorem.

###### Theorem F.1.

In the piecewise approximation scheme, suppose $s\leq d_{A}$ and $d_{B}=1$,
and $D$ becomes sortable in $R$ epochs. Then Party $A$ can learn the precise
value of the data in terms of feature $x_{B}$ (up to a difference in sign) in
$\max\\{R,2\\}$ epochs.

###  F.2. Privacy Analysis for Party $A$

In analogy to Theorem 4.1, Party $B$ can determine the label within every
batch with probability one if $d_{A}=0$ (note this does not require $s\leq
d_{B}$). Now suppose $d_{A}\geq 1$ and $s\leq d_{B}$.

Similar to the previous subsection, there are three possible cases:

  1. (1)

$|f_{i,t}|=1.$ Then $f_{i,t}=-y_{i}$ and Party $B$ can directly obtain the
label via

(150) $\displaystyle y_{i}=-\operatorname{sign}{(f_{i,t})};$

  2. (2)

$0<|f_{i,t}|<1.$ Then $f_{i,t}=\bm{\theta}_{t-1}^{\top}\bm{x}_{i}-0.5y_{i}$
and $|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|<0.5$. Therefore, Party $B$ can
directly obtain the label via

(151) $\displaystyle y_{i}=-\operatorname{sign}{(f_{i,t})};$

  3. (3)

$f_{i,t}=0.$ Then Party $B$ only knows

(152) $\displaystyle
y_{i}=\operatorname{sign}{(\bm{\theta}_{t-1}^{\top}\bm{x}_{i})}\ \ \wedge\ \
|\bm{\theta}_{t-1}^{\top}\bm{x}_{i}|\geq 0.5,$

so he cannot say much about the label in general.

Therefore, denote

(153) $\displaystyle\mathcal{L}_{t}:=\\{i\in\mathcal{B}_{t}:0<|f_{i,t}|\leq
1\\},$

and we have the following theorem.

###### Theorem F.2.

In the piecewise approximation scheme, Party $B$ can use
$y_{i}=-\operatorname{sign}(f_{i,t})$ to determine the label for
$i\in\mathcal{L}_{t}$ and all $t$.