Private and Accurate Decentralized Optimization via
Encrypted and Structured Functional Perturbation

The problem of optimizing a global objective function through the cooperation of multiple agents has gained increased attention in recent years [1, 2]. This is driven by the wide applicability of the problem to many engineering and scientific domains, ranging from cooperative control, distributed sensing, multi-agent systems, and sensor networks to large-scale machine learning; see, e.g., [3, 4, 5, 6].

In this paper, we consider a peer-to-peer network of $n$ agents that solves the following optimization problem cooperatively:

where $x$ is the common parameter of all the agents, $\mathcal{D}$ is the domain of $x$, and $\mathcal{N}$ denotes the collection of all the agents.

Despite the enormous success of gradient-based distributed optimization algorithms, they all require agents to explicitly share optimization variables and/or gradient estimates in every iteration. This would become a problem in applications involving sensitive data. Zhu et al. [7] showed that obtaining private training data from publicly shared gradients is possible, and the recovery is pixelwise accurate for images and token-wise matching for texts. Consequently, we wish to solve (1) in a private way.

In the machine learning community, one of the common forms of the individual function is $f_{i}(x)\triangleq\mathbb{E}_{\xi_{i}\sim\mathcal{D}_{i}}[l_{i}(x,\xi_{i})]$, where $\mathcal{D}_{i}$ is the local data distribution of agent $i$, and $\xi_{i}$ is a data sample or a batch of data samples. In such a case, each function $f_{i}$ contains information on the data distribution $\mathcal{D}_{i}$, which is usually sensitive. It is thus crucial to keep the objective functions private. More specifically, by privacy, we refer to keeping all $f_{i}$ from being inferred by adversaries. In this work, we consider two types of adversaries:

• •

  The eavesdropper: an external adversary having access to all information transmitted through the communication channels within the network.

• •

  The curious-but-honest adversary: an external adversary that corrupts a subset of the agents. The adversary knows all the information of every corrupted agent $i$, including all the information within agent $i$, e.g., the individual function $f_{i}$, and all the information passed from its neighbor to agent $i$. However, each corrupted agent obeys the optimization protocol precisely.

Plenty of efforts have been reported to counteract potential privacy breaches in distributed optimization. Privacy preserving algorithms either process the messages being transmitted between agents or change the functions to be optimized. We refer to them as message-based and function-based methods, respectively. Differential Privacy (DP) [8, 9], a de facto standard for privacy serving, has been introduced to the context of distributed optimization [10, 11, 12, 13]. The DP-based methods can be categorized into message-perturbing [10, 11, 12] and function-perturbing ones [13]. The message-perturbing methods inject noises to the messages each agent sends, while the latter adds functional noises into each agent’s cost function $f_{i}$.

However, the direct combination of DP and distributed optimization suffers from the accuracy-privacy trade-off. Huang et al. [12] observed that, by fixing the other parameters, the accuracy level of the obtained solution is in the order of $O(\frac{1}{\epsilon^{2}})$, where $\epsilon$ is the privacy budget that is inversely proportional to privacy. The papers [14, 15] adopted encryption techniques to preserve privacy in distributed optimization. Nevertheless, the heavy communication and computation overhead prevents the methods from many real-world applications.

Adding structured noise [16] is a workaround for the accuracy-privacy trade-off and the heavy overhead mentioned above. The paper [16] constructed a set of zero-sum Gaussian noises to perturb the affine terms of the objective functions that are assumed to be quadratic. Nonetheless, the method fails under an eavesdropping attack due to the naive communication method. Besides, the privacy analysis in [16] is carried out under a self-defined privacy framework. We provide a categorization of the current privacy-preserving distributed optimization algorithms in Table I.

In this paper, we integrate the encryption-based scheme and the structured noise method deliberately under the functional DP framework. The proposed new method, termed the Encrypted Functional Perturbation with Structured Noise algorithm (EFPSN), enjoys the benefits of several previous methods. In particular, EFPSN adopts the Paillier encryption scheme to construct zero-sum noises among the agents secretly. The noises are subsequently used to generate functional perturbations for each agent’s cost function. Such a procedure differs from those in [14, 15] and bypasses the heavy communication and computation overhead caused by encryption at every iteration. Then, based on the perturbed cost functions, any existing decentralized optimization algorithm can be utilized to obtain the accurate solution to problem (1) thanks to the structured noises. We further theoretically prove that EFPSN is ($\epsilon,\delta$)-differentially private and can achieve nearly perfect privacy under deliberate parameter settings. In other words, EFPSN can achieve nearly perfect privacy without sacrificing accuracy.

The rest of this paper is organized as follows: Section 2 specifies the notation and provides related background knowledge. Then, we develop the Encrypted Functional Perturbation with Structured Noise algorithm in Section 3. Privacy analysis under the DP framework is carried out in Section 4. Finally, simulation examples and conclusion are presented in Section 5 and Section 6 correspondingly.

This section introduces the notation, graph-related concepts and some background knowledge on Hilbert space and Paillier Cryptosystem, since generating functional perturbations relies on the orthonormal systems in some Hilbert space, and Paillier Cryptosystem [17] is adopted to construct structured noises privately.

In this section, we propose the Encrypted Functional Perturbation with Structured Noise algorithm (EFPSN in short) that privately solves the problem (1). Unlike the majority of privacy-preserving algorithms, EFPSN does not sacrifice accuracy for privacy.

To achieve privacy, EFPSN adds structured functional perturbations on individual cost functions $\{f_{i}\}_{i\in N}$. Specifically, the algorithm aims at making the functional perturbations zero-sum. EFPSN consists of two phases, as shown in Algorithm 1.

In phase I, the agents in the network cooperate to generate functional perturbations in a way that is immune to eavesdropping attacks and honest-but-curious attacks to some extent. First, they generate keys and random numbers required by the Paillier encryption scheme. Then, they encrypt and send random noise $\lfloor 10^{P}\eta_{ijk}\rfloor$ to their neighbors, and the noises are further decrypted to construct the zero-sum perturbation. Due to encryption, the signals are transferred privately and securely under eavesdropping. However, since Paillier encryption only works for integers, we set a precision order $P$, and encrypt and decrypt $\lfloor 10^{P}\eta_{ijk}\rfloor$.

Subsequently, in Line 10, each agent $i$ calculates $\bar{\eta}_{ik}$ by subtracting the sum of noises it receives from the sum of noises it sends. Due to Paillier encryption’s homomorphic property, each agent only needs to decode once for each $k\in\mathbb{Z}_{K}$. This saves computation, especially when each agent has a large number of neighbors.

Paillier encryption scheme guarantees privacy under eavesdropping attacks. In terms of the honest-but-curious attacks, the noise coefficient sequence $\bar{\eta}_{i}$ of each agent $i\in\mathcal{N}$ remains unknown to the attacker as long as the attacker does not corrupt all $i$’s neighbors. Under such circumstances, the privacy of agent $i$ is maintained.

It is worth noting that $\sum_{i\in\mathcal{N}}\sum_{j\in\mathcal{N}_{i}}(\eta_{ijk}-\eta_{jik})=0$ for all $k$. Such a construction forces $\lim_{P\rightarrow\infty}\sum_{i}\bar{\eta}_{ik}=0$ to hold for all $k$. Therefore, we have generated a set of zero-sum signals $\{\bar{\eta}_{ik}\}_{i\in\mathcal{N}}$ given large $P$.

Finally in Line 12, the agents perturb the cost functions by adding $\Phi(\bar{\eta}_{i})$. $\Phi(\cdot)$ is a function that maps a sequence in $l_{2}$ to a function in $L_{2}(D)$. Such a construction depends on the orthonormal system $\{e_{k}\}_{k\in I}$ in $\mathcal{H}$ one chooses. For instance, given the orthonormal system $\{e_{k}\}_{k\in I}$ and a sequence $\bar{\eta}_{i}\triangleq\{\bar{\eta}_{ik}\}_{k\in I}$, $\Phi(\bar{\eta}_{i})=\sum_{k\in I}\bar{\eta}_{ik}e_{k}$. The orthonormal system we use will be specified later.

Since $\{\bar{\eta}_{i}\}_{i\in\mathcal{N}}$ is zero-sum when $P\rightarrow\infty$, we have

Therefore, the set of perturbing functions $\{\Phi(\bar{\eta}_{i})\}_{i\in\mathcal{N}}$ is zero-sum when $P\rightarrow\infty$. Additionally, the decrypted text in Line 10 is of precision $10^{-P}$. Consequently, the error brought by $P$ will be dominated by the floating-point error once $P$ is set to a moderately large value. Though $\{\Phi(\bar{\eta}_{i})\}_{i\in\mathcal{N}}$ is zero-sum, each agent $i$ gains privacy from the non-zero functional perturbation $\Phi(\bar{\eta}_{i})$.

In phase II, the agents may conduct any distributed optimization algorithm on $\{\hat{f}_{i}\}_{i\in\mathcal{N}}$. Since $\sum_{i}\hat{f}_{i}(x)=\sum_{i}f_{i}(x)$, the obtained solution solves the original problem (1) when $P\rightarrow\infty$. Namely, EFPSN solves problem (1) without any accuracy degeneration given proper $P$.

In this section, we analyse the privacy-related property of EFPSN under the framework of differential privacy. Particularly, we prove the mechanism of generating the masked functions is differentially private. And since DP is compatible with any post-processing, EFPSN remains differentially private.

First, we introduce the definition of $\mathcal{V}$-adjacency, which was originally proposed in [13].

We adopt the standard $(\epsilon,\delta)$-DP definition under our functional setting.

We choose our adjacency space $\mathcal{V}_{q}$ as follows. Given $q>1$, consider the weight sequence $\{k^{q}\}^{\infty}_{k=1}$ and define the adjacency vector space to be the image of the resulting weighted $l_{2}$ space under $\Phi$, i.e.,

where $\delta_{k}$ is the $k$th element of $\delta$. The rationale of considering such a space will be made clear from the analysis. Moreover,

is a norm on $\mathcal{V}_{q}$.

Now we introduce our main theorem about the privacy-preserving property of EFPSN.

In this section, we evaluate the performance of the proposed EFPSN algorithm using numerical experiments. We consider both convex and non-convex objective functions, and EFPSN is compared with the non-zero-sum functional perturbation mechanism proposed in [13]. Before displaying the results, we first demonstrate how the orthonormal system $\{e_{k}\}_{k\in I}$ based on which we generate the coefficients-function mapping $\Phi$, is constructed.

In the paper, we proposed the Encrypted Functional Perturbation with Structured Noise algorithm that solves the decentralized optimization problem 1 privately and accurately. Given exact consensus between agents, EFPSN could eliminate the privacy-accuracy trade-off by constructing a zero-sum functional perturbation. Since such construction requires secure communication between agents, we adopt the Paillier encryption scheme to fight against eavesdropping attackers. We rigorously proved the privacy property of EFPSN under the differential privacy framework. Simulations confirmed the efficacy of EFPSN in protecting privacy while maintaining accuracy.