使用多方計算保護機器學習的隱私安全-Part 1 ———— 從零開始的簡單教程

在我們公眾號裏發過多篇同態加密的文章，受到大家熱烈關注。密碼學因為區塊鏈而走入平常百姓的視野，我們公眾號就是做區塊鏈上密碼學的佈道傳播。同態加密可以保護數據的隱私安全，而安全多方計算同樣是有趣的。

在這篇文章中，我們將從頭開始構建一個簡單的安全計算協議，並嘗試用它來訓練基本布爾函數的簡單神經網路。還有一個帶有相關源代碼的Python筆記。

我們假設我們有三個非串通方案 P0, P1, P2來一起進行計算。即訓練神經網路並在之後使用它們進行預測；然而，因為未知的原因，他們並未如期地顯示學習模型。我們將假設一些用戶願意提供訓練數據，如果能保持這些數據是隱私的話，同樣有些人對他們輸入的數據是否也是隱私的，則有興趣去使用學習模型。

為了能夠做到這一點，我們需要以一定的精度安全地計算有理數；特別是加和乘這些, 我們還需要計算Sigmoid函數（1/(1+np.exp(-x))），它的傳統結構在安全設置下會進行令人驚訝的繁重計算操作。因此，我們將遵循構建安全AI的方法並使用多項式對其進行近似，然後進行一些優化。

安全多方計算

同態加密（Homomorphic Encryption，HE）和安全多方計算（secure Multi-Party Computation，MPC）是現代密碼學中密切相關的兩個領域，常常互相使用對方的技術以便解決大致相同的問題：計算接受私密數據輸入的函數而不泄露任何東西，除了（可選）最終輸出。例如，在我們的私人機器學習環境中，兩種技術都可以用來訓練我們的模型並進行預測（不過在HE的情形下，如果數據來自使用不同加密鑰的用戶，需要做一些專門的技術處理）。

從高層次來看，對其本身來說，HE經常可以用MPC替換，反之亦然。至少就今天而言，可以大致表現HE不怎麼需要交互，但是要昂貴的計算，但是MPC的計算很廉價卻需要大量的交互。或者換句話說，MPC用兩方或者多方的交互取代了昂貴的計算。

現在，這提供了很好的實際性能，以至於人們可以主張MPC是明顯更成熟的技術 – 作為這一主張的依據，已經有幾家公司提供了基於MPC的服務。

定點算術

運算將在一個有限的區域內進行，於是我們首先需要決定如何將有理數r表示為域元素，即取自0, 1, ..., Q-1的整數x（Q為質數）。我們將採用典型的做法，根據固定的精度放大每個有理數，比如，在6位精度的情形下，我們將放大10**6倍，然後將結果的整數部分作為定點數表示。例如，Q = 10000019時，我們得到encode(0.5) == 500000和encode(-0.5) == 10000019 - 500000 == 9500019。

def encode(rational):

upscaled = int(rational * 10**6)

field_element = upscaled % Q

return field_element

def decode(field_element):

upscaled = field_element if field_element <= Q/2 else field_element - Q

rational = upscaled / 10**6

return rational

注意，在這一表示下的加法是直截了當的，(r * 10**6) + (s * 10**6) == (r + s) * 10**6 ，然而乘法增加了一個額外的放大因子，我們必須除掉它以保證精度並避免數字爆掉。(r * 10**6) * (s * 10**6) == (r * s) * 10**6 * 10**6

共享和重建數據

進行編碼輸入時，每個用戶需要一種和其他用戶分享數據的方式以便於計算，當然一切都是加密進行的。

我們需要的成分是祕密共享的，它將把一個值以某種方式拆分成三份，這樣，任何見到少於三份數據的人無法知道關於這個值的任何信息。然而，一旦見到了三份數據，就可以輕易地重建這個值。

出於簡單性考慮，這裡我們將使用複製祕密共享，其中每方收到不止一份數據。具體來說，隱私值x將以類似於x == x0 + x1 + x2地方法分成x0,x1,x2三個可分享數據，P0方收到(x0, x1)，P1收到(x1, x2)，P2收到(x2, x0)。不過本教程中這一方法將是祕密的，會直接將共享的x儲存為由三部分組成的向量[x0, x1, x2]。

def share(x):

x0 = random.randrange(Q)

x1 = random.randrange(Q)

x2 = (x - x0 - x1) % Q

return [x0, x1, x2]

並且當兩方或多方同意向某人透露其值時，他們只需發送分享部分即可進行重建。

def reconstruct(shares):

return sum(shares) % Q

然而，如果部分是下面提到的一次或多次安全運算的結果，出於私密性考慮，我們在重建前進行一次再共享。

def reshare(xs):

Y = [ share(xs[0]), share(xs[1]), share(xs[2]) ]

return [ sum(row) % Q for row in zip(*Y) ]

嚴格來說，這不是必要的，但這樣做可以更容易地瞭解協議為何安全；直觀地，它確保分享的部分是新的，不包含關於我們用於計算結果的數據的信息。

加法與減法

這樣我們已經可以進行安全的加法和減法運算了：每方直接加減其擁有的部分，由於(x0 + x1 + x2) + (y0 + y1 + y2) == (x0 + y0) + (x1 + y1) + (x2 + y2)，通過這一操作可以得到x + y的三部分（技術上說應該是reconstruct(x) + reconstruct(y)，但是隱式寫法更易讀）。

def add(x, y):

return [ (xi + yi) % Q for xi, yi in zip(x, y) ]

def sub(x, y):

return [ (xi - yi) % Q for xi, yi in zip(x, y) ]

請注意，不需要通信，因為這些是本地計算。

乘法

自從每方都有兩個部分開始，乘法可以通過類似上面提到的加法和減法的方式進行。由各方基於已有的兩個分享計算新份額。具體而言，對下面的代碼中定義的z0、z1、z2而言，我們有x * y == z0 + z1 + z2（技術上來說……）

然而，每方擁有兩個不變地部分是不夠滿意的，而像P1直接將z1發給P0這樣的做法是不安全的。一個簡單的修正是直接將每份zi當成私密輸入共享；這樣就得到了一個正確而安全的共享w（乘積）。

def mul(x, y):

# local computation

z0 = (x[0]*y[0] + x[0]*y[1] + x[1]*y[0]) % Q

z1 = (x[1]*y[1] + x[1]*y[2] + x[2]*y[1]) % Q

z2 = (x[2]*y[2] + x[2]*y[0] + x[0]*y[2]) % Q

# reshare and distribute; this requires communication

Z = [ share(z0), share(z1), share(z2) ]

w = [ sum(row) % Q for row in zip(*Z) ]

# bring precision back down from double to single

v = truncate(w)

return v

然而任有一個問題遺留，如前所述，reconstruct(w)具有雙精度：它編碼時使用的放大因子是10**6 * 10**6，而不是10**6。在不安全設定下，我們本可以通過標準的除法（除以10**6）來修正這一點，但是由於我們操作的是有限域中的祕密共享元素，這變得不那麼直截了當了。

除以一個公開的常量，這裡是10**6，足夠簡單：我們直接將部分乘以其域中的逆元素10**(-6)。對某v和u < 10**6，如果reconstruct(w) == v * 10**6 + u，那麼乘以逆元素得到v + u * 10**(-6)，那麼v就是我們要找到的值。在不安全設定下，殘值u * 10**(-6)足夠小，可以通過取整消除。與此不同，在有限域元素的安全設置中，這種意義已經丟失，我們需要以其他方式擺脫它。

一種方法是確保u == 0。具體而言，如果我們事先知道u，那麼我們可以不對w作除法，而對w == (w - share(u))作除法，然後我們就如願以償地得到v == v 和u == 0，沒有任何殘留值。

剩下的問題當然是如何安全地得到u，以便計算w。具體細節見CS』10，不過基本的思路是首先在w上加上一個大的掩碼，將掩碼後的值表露給其中一方，使其得以計算掩碼後的u。最後，共享和解掩碼這一掩碼後的值，然後計算w。

def truncate(a):

# map to the positive range

b = add(a, share(10**(6+6-1)))

# apply mask known only by P0, and reconstruct masked b to P1 or P2

mask = random.randrange(Q) % 10**(6+6+KAPPA)

mask_low = mask % 10**6

b_masked = reconstruct(add(b, share(mask)))

# extract lower digits

b_masked_low = b_masked % 10**6

b_low = sub(share(b_masked_low), share(mask_low))

# remove lower digits

c = sub(a, b_low)

# division

d = imul(c, INVERSE)

return d

注意，上面的imul是將每個共享與公共常數相乘的本地操作，在這種情況下是10 ** 6的域反轉。

安全的數據類型

作為最後一步，我們將上述過程包裝在自定義抽象數據類型中，允許我們在表達神經網路時使用NumPy。

class SecureRational(object):

def __init__(self, secret=None):

self.shares = share(encode(secret)) if secret is not None else []

return z

def reveal(self):

return decode(reconstruct(reshare(self.shares)))

def __repr__(self):

return "SecureRational(%f)" % self.reveal()

def __add__(x, y):

z = SecureRational()

z.shares = add(x.shares, y.shares)

return z

def __sub__(x, y):

z = SecureRational()

z.shares = sub(x.shares, y.shares)

return z

def __mul__(x, y):

z = SecureRational()

z.shares = mul(x.shares, y.shares)

return z

def __pow__(x, e):

z = SecureRational(1)

for _ in range(e):

z = z * x

return z

使用這種類型，我們可以像其他任何類型一樣安全地操作值：

x = SecureRational(.5)

y = SecureRational(-.25)

z = x * y

assert(z.reveal() == (.5) * (-.25))

此外，需要調試的時候，我們可以切換為不安全類型而不需要修改其餘（神經網路）代碼。再比如，我們可以隔離計數器的使用，查看進行了多少次乘法，進而讓我們模擬下需要多少通訊。