Secure Linear Aggregation Using Decentralized Threshold Additive Homomorphic Encryption For Federated Learning

For any set $X$, we denote by $|X|$ the number of elements of the set $X$. If $x$ is a string, $|x|$ denotes its bit length. And if $x$ is a vector, $|x|$ denotes the dimension of the vector. $x||y$ denotes the bit catenation of two strings $x$ and $y$.

Let $R=\mathbb{Z}[x]/(f(x))$ be a polynomial ring where $f(x)$ is a monic irreducible polynomial of degree $d$. Elements of the ring $R$ is denoted by vectors. For $\vec{a}\in R$, the coefficients of $\vec{a}$ is denoted by $a_{i}$ such that $\vec{a}=\sum_{i=0}^{d-1}a_{i}\cdot x^{i}$. The infinity norm of $||\vec{a}||$ is defined as $max_{i}|a_{i}|$ and the expansion factor of R is defined as $\delta_{R}=max\{||\vec{a}\cdot\vec{b}||/(||\vec{a}||\cdot||\vec{b}||):\vec{a},\vec{b}\in R\}$.

Let $h>1$ be an integer. Then $\mathbb{Z}_{h}$ denotes a set of integers $(-\frac{h}{2},\frac{h}{2}]$. The symbol $\mathbb{Z}/q\mathbb{Z}$ denotes a ring on integers $\{0,\ldots,q-1\}$. For $x\in\mathbb{Z}$, $[x]_{h}$ denotes the unique integer in $\mathbb{Z}_{h}$ with $[x]_{h}=x\bmod h$. For $\vec{x}\in R$, $[\vec{x}]_{h}$ denotes the element in $R$ obtained by applying $[\cdot]_{h}$ to all its coefficients. For $x\in\mathbb{R}$, $\lfloor x\rceil$ denotes rounding to the nearest integer and $\lfloor x\rfloor$, $\lceil x\rceil$ denote rounding up or down.

Let $\lambda$ be an integer as the security parameter. A function $negl(\lambda)$ is negligible in $\lambda$ if $negl(\lambda)=o(1/\lambda^{c})$ for every $c\in\mathbb{N}$. An event occurs with negligible probability if the probability of the event is $negl(\lambda)$. An event occurs with overwhelming probability if its complement occurs with negligible probability.

Given a probability distribution $\mathcal{D}$, we use $x\leftarrow\mathcal{D}$ to denote that $x$ is sampled from $\mathcal{D}$. For a set $X$, $x\leftarrow X$ denotes that $x$ is sampled uniformly from $X$. A distribution $\chi$ over integers is called $B$-bounded if it is supported on $[-B,B]$.

McMahan et al. [1] described the FL framework. We give a briefly review to see their federated averaging algorithm. As shown in Fig. 1, there is a parameter server $S_{1}$ and many users. $S_{1}$ exchanges model parameters with users to collaboratively build a better learning model. The federated averaging algorithm runs periodically. In each period, $S_{1}$ selects $n$ users randomly. In Fig. 1, we intended to show two periods with totally different users. Next we focus on a period $e$ where users in a set $U_{e}$.

The FL in a period is as follows.

1. 1.

   A user $u\in U_{e}$ is activated to download the global parameters from the parameter server.

2. 2.

   The user $u$ feeds their local data samples to get updated model parameters. And the parameters or their gradients $\omega_{u}$ with the number of local data samples $n_{u}$ should be sent to $S_{1}$.

3. 3.

   The parameter server $S_{1}$ compute the updated global model parameters $\omega=\frac{1}{\sum_{u\in U_{e}}n_{u}}\sum_{u\in U_{e}}n_{u}\omega_{u}$.

The parameter server $S_{1}$ continues to randomly activate a set of users in the next period until the parameters $\omega$ converge to that of the global optimal learning model.

Users could upload the $n_{u}$ together with $\omega_{u}$ so that the server could get the value $\sum_{u\in U_{e}}n_{u}$ and compute the updated $\omega$. So a sum only aggregation is enough for the federated averaging algorithm. However, a parameter server may execute more computations in other federated learning models [16, 17], where a sum only aggregation is not enough.

We adapt the notion of message-driven entities in [33] to the FL security model [5] to describe the participants in a FL scenario. A message-driven entity is initially invoked by an environment process. Each entity has their initial states. Once invoked, an entity waits for an activation that can happen for a message from the network or an environment process. On activation, the entity processes the incoming message or the arguments from a process with its current internal state, and generates a new internal state, outgoing messages and a cumulative output. Once an activation is completed, the entity waits for the next activation if it does not stop.

A protocol $\pi$ consists of a server side progress $\pi_{S}$ and a client side progress $\pi_{u}$. An FL process in $S_{1}$ invokes $\pi_{S}$, which runs periodically until $\pi_{S}$ is stopped by the FL process. In each period, $\pi_{S}$ randomly selects a set of users $U$ and activates their client side progresses. A user $u$ should have voluntarily invoked their $\pi_{u}$ before $S_{1}$ activates them. On activation, $\pi_{u}$ exchanges messages with $\pi_{S}$ until $\pi_{S}$ finishes a period or $\pi_{u}$ is stopped by the user. There may be some auxiliary entities for the security of the protocol $\pi$. A common setup includes a certificate authority (CA) [5]. A $CA$ is invoked and runs permanently to receive certificate requests from users and issue certificates to users. In our protocol, we also introduce blockchain miners $BM$. Miners are invoked to receive transactions from users and the server, and to execute smart contracts on commonly consented transactions.

The server and each user have a bi-directional secure channel between them. Practically, it reuses a transport layer secure channel established by FL processes. Users do not have direct links in the protocol $\pi$. The communications of users are transferred by the server. Users and the $CA$ may exchange messages at an initial stage. When the protocol $\pi$ runs, the $CA$ could be offline. Blockchain miners usually have a point-to-point (P2P) network to deliver transactions and blocks. When a blockchain is used in $\pi$, FL entities should have the ability to send and receive transactions to and from the P2P network.

An active adversary $\mathcal{A}$ could corrupt the server and users in $\pi$. For each period, the number of corrupted parties is at most $n_{c}$ [5]. When $\mathcal{A}$ corrupts an entity, it knows the internal states and long-term secrets of the entity, and controls all the behaviours of the entity from that point. Obviously, the server $S_{1}$ could be corrupted to act as a malicious server. When $\mathcal{A}$ corrupts a user, it could send transactions on behalf of the user.

We does not allow an adversary to corrupt $CA$ or $BM$ since we do not try to model the security of a CA system or a blockchain system. We simply make assumptions about them:

• •

  A transaction from a user or the server will be executed and recorded correctly by blockchain miners within a bounded delay.

• •

  A certificate from a $CA$ proves the binding relation of a verification key and the real identity of a user.

We define $GO_{\pi,e,\{S_{1}\}\cup U_{e},\mathcal{A}}(\vec{x},\vec{r})$ as a global output for $\pi$ in a period $e$ where $\vec{x}=\{x_{S}\}\cup\{x_{u}\}_{u\in U_{e}}$ denotes the inputs of the server $S_{1}$ and the inputs of users in the set $U_{e}$ of the period $e$, and $\vec{r}=\{r_{0},r_{S}\}\cup\{r_{u}\}_{u\in U_{e}}$ denotes the random inputs of the adversary $\mathcal{A}$, server $S_{1}$ and users in $U_{e}$. Let

be the random variable about $GO_{\pi,e,\{S_{1}\}\cup U_{e},\mathcal{A}}(\vec{x},\vec{r})$. The randomness comes from the adversary $\mathcal{A}$, server $S_{1}$ and users in $U_{e}$.

We define the input privacy of a user [5] as follows.

The security goal in [5] is input privacy of all uncorrupted users. Apparently, if the privacy of all users are protected, the privacy of a user is protected. If the privacy of each uncorrupted user in protected, the privacy of all uncorrupted users are protected. So the two definitions are equivalent.

Boneh et al. [20] give a definition of decentralized threshold fully homomorphic encryption (DTFHE). We refine it as a DTAHE definition for the FL scenario. A DTAHE scheme is a tuple of probabilistic polynomial time (PPT) algorithms $DTAHE=(Setup$, $KeyGen$, $Share$, $CombKey$, $Enc$, $Eval$, $ParDec$, $FinDec)$.

1. 1.

   $Setup(1^{\lambda})\rightarrow parm$: It takes as input a security parameter $\lambda$, outputs system parameters $parm$.

2. 2.

   $KeyGen(parm)\rightarrow(sk_{u},pk_{u})$: It takes as input the system parameter $parm$ to produce public and private keys for a user $u$.

3. 3.

   $Share(parm,\{pk_{v}\}_{v\in U\backslash\{u\}},t,sk_{u})\rightarrow\{e_{v,u}\}_{v\in U\backslash\{u\}}$: It takes as input the system parameter $parm$, public keys of users in a set $U$ excluding the user $u$, a threshold value $t$ and private keys $sk_{u}$ of the user $u$, to produce encrypted shares $e_{v,u}$ for each user $v\in U\backslash\{u\}$.

4. 4.

   $CombKey(parm,\{pk_{u}\}_{u\in U})\rightarrow pk$: It takes as input the system parameter $parm$, public keys of a set of users in $U$, and produces an encryption key $pk$.

5. 5.

   $Enc(parm,pk,m_{u})\rightarrow c_{u}$: It takes as input the system parameter $parm$, a public key $pk$ and a message $m_{u}$ from a user $u$, and produces a ciphertext $c_{u}$.

6. 6.

   $Eval(parm,\{c_{u}\}_{u\in U},\{\alpha_{u}\}_{u\in U})\rightarrow\hat{c}$: It takes as the system parameter $parm$, ciphers $\{c_{u}\}_{u\in U}$ and coefficients $\{\alpha_{u}\}_{u\in U}$, and produces an evaluated cipher $\hat{c}=\sum_{u\in U}\alpha_{u}\cdot c_{u}$.

7. 7.

   $ParDec(parm,\hat{c},\{e_{u,v}\}_{v\in U})\rightarrow\hat{m}_{u}$: It takes as input the system parameter $parm$, the cipher $\hat{c}$, and a set of encrypted shares $\{e_{u,v}\}_{v\in U\backslash\{u\}}$ to the user $u$, and produces a partially decrypted value $\hat{m}_{u}$.

8. 8.

   $FinDec(parm,t,\hat{c},\{\hat{m}_{u}\}_{u\in V})\rightarrow m$: It takes as input the system parameter $parm$, the threshold value $t$, the cipher $\hat{c}$ and partially decrypted ciphers $\{\hat{m}_{u}\}_{u\in V}$ from users in a set $V$ with $|V|\geq t$, and produces a plaintext $m$.

One could simply give an ElGamal based DTAHE instance following the constructions in [21], which justifies the correctness of the DTAHE definition.

We adapt the model of DTFHE in [20] for the DTAHE. The first definition is evaluation correctness.

The second definition is sematic security. It captures the privacy of messages.

The last definition is simulation security. It captures the privacy of shared secrets and private keys of users.

As shown in Fig. 2, initially a server $S_{1}$ runs $parm\leftarrow Setup(1^{\lambda})$ to provide a system-wide parameters for all users, and each user runs $(sk_{u},pk_{u})\leftarrow KeyGen(parm)$ to produce their key pairs. The server and users then runs a four-round protocol $\pi$ with an agreed threshold value $t$. We next focus on a period $e$ to show the protocol.

1. 1.

   Round 1 (AdvertiseKeys). When a user $u$ is active, it packs a message as $m_{u,1}=(u,pk_{u})$ and sends the message to the server $S_{1}$. The user then waits for the first response from $S_{1}$ or stops.

   The server $S_{1}$ makes a set $U_{e}^{1}=\emptyset$. After it receives a message $m_{u,1}=(u,pk_{u})$, it sets $U_{e}^{1}=U_{e}^{1}\cup\{u\}$. When $|U_{e}^{1}|>t$, $S_{1}$ packs a message as $m_{S,1}=\{m_{u,1}\}_{u\in U_{e}^{1}}$. The message $m_{S,1}$ is broadcasted to all the users in $U_{e}^{1}$ as their responses.

2. 2.

   Round 2 (ShareKeys). When a user $u$ receives $m_{S,1}$, it makes a $U_{e}^{1}$ set from $m_{S,1}$ and checks $|U_{e}^{1}|\geq t$. If the verification passes, the user executes as follows:

   1. (a)

      It makes a public key set $\{pk_{v}\}_{v\in U_{e}^{1}\backslash\{u\}}$ from $m_{S,1}$ and produce encrypted shares by

      $${\{{e_{v,u}}\}_{v\in U_{e}^{1}}}\leftarrow Share\left(\begin{gathered}parm,{\{p{k_{v}}\}_{v\in U_{e}^{1}\backslash\{u\}}},\hfill\\ t,s{k_{u}}\hfill\\ \end{gathered}\right).$$

   2. (b)

      It packs $m_{u,2}=(u,\{(v,e_{v,u})\}_{v\in U_{e}^{1}\backslash\{u\}})$ and sends the message to $S_{1}$. Then $u$ waits for the second response or stops.

   The server $S_{1}$ builds a set $U_{e}^{2}$ in the same way as $U_{e}^{1}$ satisfying $U_{e}^{2}\subseteq U_{e}^{1}$. When $|U_{e}^{2}|>t$, $S_{1}$ packs a message $m_{S,2,v}=(\{(u,e_{v,u})\}_{u\in U_{e}^{2}\backslash\{v\}})$ for each user $v\in U_{e}^{2}$, and sends them to the users in $U_{e}^{2}$.

3. 3.

   Round 3 (CipherCollection). When a user $u$ receives a message $m_{S,2,u}$, it makes a set $U_{e}^{2}$ from $m_{S,2,u}$. If $|U_{e}^{2}|\geq t$, $u$ executes as follows:

   • •

     It runs $pk\leftarrow CombKey(parm,\{pk_{u}\}_{u\in U_{e}^{2}})$.

   • •

     It runs $c_{u}\leftarrow Enc(parm,pk,m_{u})$ to compute the cipher of its private input $m_{u}$.

   • •

     It packs a message $m_{u,3}=(u,c_{u})$ and sends the message to $S_{1}$. Then $u$ waits for the third response or stops.

   The server $S_{1}$ builds a set $U_{e}^{3}$ in the same way as $U_{e}^{1}$ satisfying $U_{e}^{3}\subseteq U_{e}^{2}$. It runs

   $$\hat{c}\leftarrow Eval(parm,\{c_{u}\}_{u\in U_{e}^{3}},\{\alpha_{u}\}_{u\in U_{e}^{3}})$$

   and sends $m_{S,3}=\hat{c}$ to users in $U_{e}^{3}$.

4. 4.

   Round 4 (Decryption). When a user $u$ receives $m_{S,3}$, it runs

   $$\hat{m}_{u}\leftarrow ParDec(parm,\hat{c},\{e_{u,v}\}_{v\in U_{e}^{2}}).$$

   $u$ then packs a message $m_{u,4}=(u,\hat{m}_{u})$ and sends the message to the server $S_{1}$. The user $u$ finishes the client protocol $\pi_{u}$ for the period $e$ and stops.

   The server $S_{1}$ builds a set $U_{e}^{4}$ in the same way as $U_{e}^{1}$ satisfying $U_{e}^{4}\subseteq U_{e}^{3}$. If $|U_{e}^{4}|\geq t$, it runs

   $$m\leftarrow FinDec(parm,\hat{c},\{\hat{m}_{u}\}_{u\in U_{e}^{4}})$$

   to get $m$ as an aggregated value. The server finishes the server side protocol $\pi_{S}$ for the period $e$ and waits for the next period.

Bonawitz et al. [5] use a certificate authority (CA) and an extra consistency round to defend against an active adversary. We also use a CA but keep our protocol four rounds. We introduce a smart contract in a blockchain to encourage the server $S_{1}$ and users to be honest.

The blockchain is described as $\vec{\sigma}_{\lambda_{t}+1}=\Upsilon(\vec{\sigma}_{\lambda_{t}},Tx)$ [34] where $\Upsilon$ is a state transition function, $\vec{\sigma}_{\lambda_{t}}$ is the system state in a block height $\lambda_{t}$, and $Tx$ is a transaction in the system. A transaction could be described as

where $from$ and $to$ fields are the sender and receiver accounts of the transaction, $value$ field is the values to be transferred from the sender to the receiver, $data$ field is arbitrary data of the sender, $aux$ field is the auxiliary information used in the blockchain and $sig$ field is the sender’s signature. The instance of the blockchain certainly could be the Ethereum [34]. Any other blockchain system supporting state transition is fine.

Initially, the server $S_{1}$ has an account $acc_{S}$ and a user $u$ has an account $acc_{u}$ in the blockchain. The server should deploy a smart contract $EncCheck$ on the blockchain which will have an account $acc_{E}$ after deployment.

Now the server $S_{1}$ has two tasks to initialize the protocol. At first, the server $S_{1}$ runs $parm\leftarrow Setup(1^{\lambda})$ to provide system-wide parameters for all users. Secondly, the server $S_{1}$ produces a transaction as

to initialize the deployed smart contract.

A user $u$ has three tasks to participate in the protocol II. At first, it runs $(sk_{u},pk_{u})\leftarrow KeyGen(parm)$ to produce protocol keys. Secondly, it produces a transaction

and sends the transaction to the blockchain to store its public keys. Thirdly, the user $u$ should produce a signature key pair $(sk_{Sigu},vk_{Sigu})\leftarrow SIG.Gen(1^{\lambda})$ using a signature scheme $(SIG.Gen,SIG.Sign,SIG.Ver)$ that is existential unforgeable against adaptive chosen messages (EUF-CMA). And then $u$ applies for a certificate $cert_{u}$ of the verifying key $vk_{Sigu}$ from a CA.

The CA and miners are auxiliary entities in the protocol. A CA is used to defend against a “Sybil” attack where an adversary may create many blockchain accounts to act as users. The miners of a blockchain receive transactions, pack them into blocks, reach a consensus on a block and update the global state. The public keys of users, parameters of the server $S_{1}$, and deposited values of the server $S_{1}$ are states of the blockchain maintained by the miners. The whole picture of the protocol is in Fig. 3. We next focus on a period $e$ to show the protocol.

1. 1.

   Round 1 (AdvertiseAccounts). When a user $u$ is active, it looks up the deposit $Dep$, supported periods $prds$ and the threshold $t$ in the smart contract account $acc_{E}$ indexed by the server account $acc_{S}$. If $Dep$, $t$, or $prds$ are too small for the user’s local policy, the user simply stops. Otherwise, it produces a signature

   $$\sigma_{u}\leftarrow SIG.Sign(sk_{Sigu},acc_{u}||T_{u})$$

   where $T_{u}$ is a time stamp of the user. It packs a message as $m_{u,1}=(u,acc_{u},T_{u},\sigma_{u},cert_{u})$ and sends the message to the server $S_{1}$. The user $u$ then waits for the first response from $S_{1}$ or stops.

   The server $S_{1}$ builds a set $U_{e}^{1}$ as in the basic protocol. It then packs a message as $m_{S,1}=(\{m_{u,1}\}_{u\in U_{e}^{1}},esid)$ where $esid$ is a session number for the period. The message $m_{S,1}$ is broadcasted to all the users in $U_{e}^{1}$ set as their response.

2. 2.

   Round 2 (ShareKeys). When a user $u$ receives $m_{S,1}$, it parses $m_{S,1}$ to extract the identities of users which form a set $U_{e}^{1}$. If checks that $|U_{e}^{1}|\geq t$, and the time stamps, signatures and certificates are correct. If the verifications pass, $u$ looks up the blockchain to find public keys of users in $U_{e}^{1}$ by their accounts which form a set $\{pk_{v}\}_{v\in U_{e}^{1}\backslash\{u\}}$, and executes as in the basic protocol.

   The server $S_{1}$ executes in the same way as in the basic protocol to produce $m_{S,2,v}$ for a user $v$.

3. 3.

   Round 3 (CipherCollection). When a user $u$ receives a message $m_{S,2,u}$, it makes a set $U_{e}^{2}$ from $m_{S,2,u}$. If $|U_{e}^{2}|\geq t$, it executes in the same way as in the basic protocol to compute $pk$ and $c_{u}$. Then $u$ creates a transaction

   $$Tx_{u,2}=(acc_{u},acc_{E},0,Record||esid||c_{u},aux,sig)$$

   and sends the transaction to the blockchain. The user $u$ then waits for a response transaction of the server $S_{1}$ from the blockchain network or stops.

   The server $S_{1}$ makes a set $U_{e}^{3}=\emptyset$. After it receives a transaction $Tx_{u,2}$, if the transaction includes the same $esid$ as the current session number, $S_{1}$ sets $U_{e}^{3}=U_{e}^{3}\cup\{u\}$ where the identity $u$ is indexed by the $acc_{u}$. It then runs

   $$\hat{c}\leftarrow Eval(parm,\{c_{u}\}_{u\in U_{e}^{3}},\{\alpha_{u}\}_{u\in U_{e}^{3}}),$$

   and packs a transaction

   $$T{x_{S,2}}=\left(\begin{gathered}ac{c_{S}},ac{c_{E}},0,Check||false||\hfill\\ esid||\hat{c}||{\{ac{c_{u}}\}_{u\in U_{e}^{3}}},aux,sig\hfill\\ \end{gathered}\right)$$

   and sends the transaction to the blockchain.

4. 4.

   Round 4 (Decryption). When a user $u$ receives $Tx_{S,2}$, it builds a $U_{e}^{3}$ set indexed by $\{acc_{u}\}_{u\in U_{e}^{3}}$. If $U_{e}^{3}\subseteq U_{e}^{2}$, $|U_{e}^{3}|\geq t$, and the $esid$ field is the current session number, $u$ then executes in the same way as in the basic protocol to interact with the server $S_{1}$.

   The server $S_{1}$ executes in the same way as in the basic protocol to get an aggregated result.