隱私計算技術解讀：橫向聯邦學習

01.橫向聯邦學習的概念

聯邦學習

（

Federated

Learning

，

FL

）這一名詞由谷歌在

2

016

年提出

［

1

］

，並從此受到持續關注。聯邦學習能夠有效幫助多個機構在滿足使用者隱私保護、資料安全和政府法規的要求下，進行資料使用和機器學習建模。

在

國內，

“聯邦學習”這一概念結合資料分佈的具體場景，由微眾銀行率先將其分為橫向聯邦學習、縱向聯邦學習與聯邦遷移學習

［

2

］

。

在該劃分標準下

，

谷歌最初提出的聯邦學習場景為橫向聯邦學習

，

即多個數據方擁有的資料特徵維數相同

，

最終訓練出的模型的輸入維數與各資料方的資料特徵維數也相同

。

在該設定下

，

各資料方可以在相同的特徵空間上用各方的所有樣本來訓練模型。

一個經典的應用場景是：谷歌在其安卓手機自帶的

Gboard

鍵盤上，使用橫向聯邦學習方法訓練了機器學習模型，用以預測（聯想）使用者的下一輸入詞

［

3

］

。

橫向聯邦學習通常存在一箇中心伺服器，在每一輪（或幾輪）的學習中，中心伺服器將模型下發給各資料方，各資料方用本地資料訓練出模型引數的更新梯度，伺服器使用安全聚合（

Secure

Aggregation

， SecAgg

）方法將各方梯度收集到伺服器端，計算出平均梯度，用以更新伺服器端的模型，在下一輪下發給各資料方，直至收斂

［

4

］

。

FedSGD

是谷歌

最初

提出的基於安全聚合方法的聯邦平均隨機梯度下降演算法

［

1

］

，此後，為了減少通訊開銷，又提出了

FedAvg

演算法，透過增加本地學習的輪數，減少了梯度聚合的互動次數，並且加速了模型收斂

［

5

］

。

無論

FedSGD

或

FedAvg

，

其核心都是

計算得出梯度，並能隨之應用各種基於梯度（一階導數）的最佳化方法，如

SGD

、

RMSProp

、

AdaGrad

、

AdaDelta

、

Adam

等。

綜合多方本地梯度

，

協同計算聚合梯度而不暴露任一方梯度值的方法

，

即為安全聚合

。

在橫向聯邦學習中

，

各參與方基於相同初始模型

、

各自本地資料進行神經網路的正向傳播與誤差的反向傳播

，

並基於此計算出本地梯度

；

對於各個參與方的本地梯度

，

使用

01

的方式進行梯度融合

，

計算出樣本總體的梯度值

，

並以此進行基於梯度的最佳化演算法

。

記參與方

u

的梯度為

g

u

，

則

，

在使用安全聚合時

，

其傳輸給聚合伺服器的值

（

記作

y

u

）

為

：

其中

，

s

u，v

指參與方

u

與參與方

v

協商後的

.橫向聯邦學習的概念

。

透過這種方法

，

聚合後各參與方的隨機掩碼抵消

，

成為梯度的聚合值

。

安全聚合

隨機掩碼

安全聚合的基礎是金鑰協商

（

Key

Agreement

）

機制

。

02

.金鑰協商

Diffie

方法是常用的一種金鑰協商機制

。

它的安全性可以規約為離散對數問題的計算困難性

。

DH

金鑰協商時

，

首先需要選取兩個大數

p

和

g

並公開

。

其中

，

p

是一個大素數

，

g

是

p

的一個本原單位根

（

primitive

root

）。（

本原單位根的意思是

：

在模

p

乘法運算下

，

g

^1， g^2， 。。。， g^（p-1）

這

p

-1

個數互不相同

，

且在

1

～

p-1

間取值

）

假設兩個通訊者為

Alice

和

Bob

：

對於

Alice

，隨機產生一個整數

a

，

a

對外保密，計算

Ka = g^a mod p

，將

Ka

傳送給

Bob

；

對於

Bob

，隨機產生一個整數

b

，

b

對外保密，計算

Kb = g^b mod p

，將

Kb

傳送給

Alice

；

在

Alice

方面，收到

Kb

後，計算出金鑰為：

key

A

= Kb^a mod p = g^（b*a） mod p

；

在

Bob

方面

，收到

Ka

後，計算出金鑰為：

key

B

= Ka ^ b mod p = g^（a*b） mod p

。

顯然

，

keyA

=

keyB

。

對於其他人

，知道

p

和

g

，

即使獲得

了

Ka

和

Kb

，但是當它們都是

大整數時

，

由於

離散對數數學難題，

無法反推計算出

key

。

透過這種方式

，

Alice

與

Bob

就透過交換公開資訊的方式

，

協商出了相同的私有資訊

。

-Hellman

容易想到

，

如果把離散對數數學難題改成基於橢圓曲線的離散對數問題

（

ECDLP

），

也能達到類似效果

。

這就是

金鑰協商

ECDH

。

要理解

ECDH

，

需要對於橢圓曲線有一些基本瞭解

。

ECDH

：Elliptic Curve Diffie–Hellman key Exchange

橢圓曲線密碼學演算法

（Elliptic Curve Cryptography，

，

由

Neal Koblitz

和

Victor Miller

在

1985

年提出，它和

RSA

有著相同的公鑰密碼學功能；

不同的是

，解決

ECD

L

P

最行之有效的方法需要消耗指數運算時間，這比整數分解所需要的時間大的多，這也就意味著，相同大小的輸入，

ECC

能夠比

RSA

提供更高的安全性，例如

256

位元的橢圓曲線金鑰和

3072

位元的

RSA

金鑰的安全性相當。越小的金鑰在速度、效率、頻寬、儲存上有著許多優勢。

本文不贅述

ECC

背後的複雜數學知識

，

而只是將一個橢圓曲線的引數抽象成

：

（

1

）素數

p

，

決定了

有限域的大小

（

2

）橢圓曲線的係數

a

、

b

（

3

）基點

G

（子群的生成元）

（

4

）子群的階

n

（

5

）

cofactor h （h = N/n）

可以認為

，

ECDLP

的困難在於

，

對於

H

=

dG

，

如果只知道

H

和基點

G

，

無法反推

d

。

利用此性質

，

可以構造

ECDH

協議如下

：

1） Alice

生成隨機整數

a

，計算

A=a*G

；

2） Bob

生成隨機整數

b

，計算

B=b*G

；

3） Alice

將

A

傳遞給

Bob

；

4） Bob

將

B

傳遞給

Alice

；

5） Bob

收到

Alice

傳遞的

A

，計算

Q =b*A

；

6） Alice

收到

Bob

傳遞的

B

，計算

Q`=a*B

；

則

Alice

、

Bob

雙方

獲

得

Q=b*A=b*（a*G）=（b*a）*G=（a*b）*G=a*（b*G）=a*B=Q‘

，即雙方得到一致的金鑰

Q

。

ECC

）

基於金鑰協商的結果

，

各參與方兩兩之間獲得了相同的金鑰

，

該金鑰可以用作

03

的種子

，

用來生成安全聚合時所需的

.金鑰協商在橫向聯邦學習中的應用

。

對於小規模的企業間橫向聯邦資料協作場景

，

透過上文的金鑰協

商

、

安全聚合的方式

，

即可成功完成模型訓練過程

。

然而

，

對於大規模參與方的橫向聯邦學習場景

，

尤其當各參與方硬體資源

、

網路條件不平衡的情況下

，

考慮到參與方由於網路不穩定等原因導致的協作中響應慢

、

掉線等情況

，

還需要對安全聚合的過程進行修改

，

使之在部分裝置掉線後仍能聚合出正確結果

。

解決該問題的一種思路是引入

偽隨機數生成器

機制

。

隨機掩碼

秘密分享是多方安全計算中的一種常用技術

，

將秘密透過某種規則切分後分發給多個參與方

，

資料的裂片被一組參與方分別擁有，

此外

，

資料

處於分裂態

時

可以

進行

運算，而運算的結果在多方參與的情況下可以還原。

在處理掉線問題時

，

需要使用符合如下性質

（

t

-

Privacy

與

r-Reconstruction

）

的秘密分享方案

：

將一個秘密

s

，

在符合如下要求的情況下

，

共享給

n

個參與方

：

t

-

Privacy

：

任意

t

個參與方無法獲得秘密資訊

s

；

r-Reconstruction

：

任意

r

個參與方能夠恢復秘密

s

。

一種經典的

t-out-of-n

秘密分享為

Shamir秘密分享

Shamir秘密分享

l

對於秘密

s

，隨機選擇

t-1

階多項式

f

（

x

）

，其中

f

（0）=s

l

參與方

P

i

收到（

α

i

，

f

（

α

i

）

）

顯然

，

使用拉格朗日插值法

，

任意

t

個秘密份額可以恢復出原秘密

，

任意少於

t

個秘密份額無法洩露任何資訊

。

由於在處理裝置掉線時只需要用到秘密分享的

r

-

Reconstruction

性質

，

此處就不再贅述

Shamir

秘密分享的其它算術性質

（

如四則運算等

）。

透過

Shamir

秘密分享機制

，

各參與方可以將自身掩碼拆分為

n

份分享出去

，

一旦聚合伺服器發現某些參與方掉線

，

即可透過未掉線的

t

個參與方恢復掩碼

，

避免部分掩碼無法被抵消造成的梯度偏差

。

Shamir秘密分享

［

1

］ Mcmahan H B ， Moore E ， D Ramage， et al。 Federated Learning of Deep Networks using Model Averaging。 Proceedings of the 20 th International Conference on Artificial Intelligence and Statistics （AISTATS） 2017。 JMLR： W&CP volume 54

［

2

］ YANG Q， LIU Y， CHEN T， et al。 Federated machine learning： Concept and applications， 2019， arXiv：1902。04885

［

3

］ A。 Hard， K。 Rao， R。 Mathews， S。 Ramaswamy， et al。 Federated learning for mobile keyboard prediction， 2018， arXiv：1811。03604

［

4

］ Keith Bonawitz， Vladimir Ivanov， Ben Kreuter， et al。 Practical Secure Aggregation for Privacy-Preserving Machine Learning。 In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security （CCS ’17）。 Association for Computing Machinery， New York， NY， USA， 1175–1191。 2017。

［

5

］ H。B。 McMahan， E。 Moore， D。 Ramage， et al ，Communication-efficient learning of deep networks from decentralizeddata， Proceedings of the 20th International Conference on ArtificialIntelligence and Statistics， AISTATS， 2017。