更新：本文介紹的PSI方法的Python版完整程式碼已在Github開源：

作者：Delta - 開箱即用的區塊鏈隱私計算框架（

https：//

deltampc。com

）

在上一篇文章中，我們介紹瞭如何使用不經意傳輸（OT）來構建不經意偽隨機函式（OPRF），並使用不經意偽隨機函式來構造隱私集合求交（PSI）。

但是，上文介紹的方法，速度很慢，因為在構造不經意偽隨機函式時，需要使用

l

次不經意傳輸（

l

是輸入資料的長度），進而導致隱私集合求交需要使用

O(nl)

次不經意傳輸（

n

為集合大小）。我們知道，由於不經意傳輸使用公私鑰加密技術，所以不經意傳輸的速度是很慢的。所以，我們要對上文介紹的方法進行改進，而改進的主要目標，就是減少使用的不經意傳輸數量。

要做到這一點，我們就需要引入一個新的方法，不經意傳輸擴充套件。能夠少量（常數次）“慢速”的不經意傳輸，來實現大量“快速”的不經意傳輸。下面，我就來介紹不經意傳輸擴充套件。

不經意傳輸擴充套件（Oblivious Transfer Extension, OTE）

這裡介紹的不經意傳輸擴充套件方法，來自文章［2］

不經意傳輸擴充套件的目標，是使用少量“慢速”的基礎不經意傳輸，配合對稱加密，來實現大量“快速”的不經意傳輸。 形式化的來說，我們以符號

OT_l^m

來表示進行

m

次不經意傳輸，每次傳輸

l

個位元，則不經意傳輸擴充套件的定義為：使用

OT_k^k

來實現

OT_l^m

，其中

k

是一個比較小的安全引數，且

m \gg k

。

下面，我們來介紹如何使用

OT_k^k

來實現

OT_l^m

。我們首先使用

OT^k_m

來實現

OT_l^m

，因為使用

OT^k_m

比使用

OT_k^k

更加簡單直觀，同時使用

OT_k^k

可以很簡單地實現

OT_k^m

。之後，我們再簡單地介紹如何使用

OT_k^k

實現

OT_k^m

。

我們使用

S

來表示

OT^k_m

中的傳送者，

R

表示

OT^k_m

中的接收者。

S

有

m

對輸入

(x_{j,0},x_{j,1}),1 \leq j \leq m

，

R

有

m

個選擇位元

r = (r_1, ..., r_m)

。

S

和

R

之間有一個統一的隨機函式

H: [m] \times \{0,1\}^k \rightarrow \{0,1\}^l

，即將長度為

k

的位元串隨機對映到長度為

l

的位元串。之後的步驟如下：

R

先初始化一個隨機的位元矩陣

T

，矩陣

T

的大小為

m \times k

，即

m

行

k

列，矩陣的每個元素都是0或1。

S

隨機初始化

k

個選擇位元

s=(s_1,...,s_k)

R

作為傳送者，

S

作為接收者，執行

OT_m^k

。對於第

i

次長度為

m

的不經意傳輸，

R

的輸入為

(t^i,t^i \bigoplus r)

，其中

t^i

表示矩陣

T

的第

i

列，長度為

m

；

S

的輸入為

s_i

。當

s_i=0

時，

S

得到

t^i

，當

s_i=1

時，

S

得到

t^i \bigoplus r

。將

S

收到的所有列組合成一個

m \times k

的矩陣，稱為

Q

現在，

R

作為接收者，

S

作為傳送者。

S

要執行

m

次傳輸，對於

1 \leq j \leq m

，

S

傳送一對資料

(y_{j,0},y_{j,1})

，其中

y_{j,0} = x_{j,0} \bigoplus H(j,q_j)

，

y_{j,1} = x_{j,1} \bigoplus H(j,q_j \bigoplus s)

，

q_j

為矩陣

Q

的第

j

行

對於

1 \leq j \leq m

，

R

輸出

z_j = y_{j,r_j} \bigoplus H(j,t_j)

，其中

t_j

表示矩陣

T

的第

j

行

現在，我們來證明方法的正確性，即

z_j = x_{j, r_j}

。

從步驟2中我們可以得知，

s_i = 0

時，

q^i = t^i

；

s_i = 1

時，

q^i = t^i \bigoplus r

。我們可以將它寫成如下形式：

q^i = t^i \bigoplus (s_i · r)\\

其中，符號

·

表示按位與運算。那麼，對於矩陣

Q

中的第

i

列，第

j

行的元素

q^i_j

，有如下等式：

q^i_j = t^i_j \bigoplus (s_i · r_j) \\

我們把

s_i

當作選擇位元，當

s_i = 0

時，

q^i_j = t^i_j

；當

s_i = 1

時，

q^i_j = t^i_j \bigoplus r_j

。我們換一個角度，把

r_j

當作選擇位元，當

r_j = 0

時，

q^i_j = t^i_j

；當

r_j=1

時，

q^i_j = t^i_j \bigoplus s_i

。這一結果，對於所有

1 \leq i \leq k

都成立，那麼我們可以得到：當

r_j = 0

時，

q_j = t_j

；當

r_j = 1

時，

q_j = t_j \bigoplus s

，它可以寫成如下形式

q_j = t_j \bigoplus (r_j · s) \\

從上式，我們可以得到

t_j = q_j \bigoplus (r_j · s) \\

這時我們來看

z_j

。由於

y_{j,0} = x_{j,0} \bigoplus H(j,q_j)

，

y_{j,1} = x_{j,1} \bigoplus H(j,q_j \bigoplus s)

，那麼

y_{j,r_j} = x_{j,r_j} \bigoplus H(j,q \bigoplus (r_j · s))

，將

y_{j,r_j}

和

t_j

帶入到公式

z_j = y_{j,r_j} \bigoplus H(j,t_j)

中，可得

z_j = y_{j,r_j} \bigoplus H(j,t_j) =x_{j,r_j} \bigoplus H(j,q \bigoplus (r_j · s)) \bigoplus H(j,q \bigoplus (r_j · s)) = x_{j,r_j}

，證畢。

從不經意傳輸的角度看，我們可以把

r_j

當作接收者

R

的選擇位元，

(q_j, q_j \bigoplus s)

是傳送者

S

輸入的一對資料，當

r_j = 0

時，

t_j = q_j

；

r_j = 1

時，

t_j = q_j \bigoplus s

，這就是了一個不經意傳輸。由於

1 \leq j \leq m

，因此我們總共構造了

m

個不經意傳輸。

這種不經意傳輸所傳輸的資料

(q_j, q_j \bigoplus s)

是隨機的，如果想要傳輸特定的資料，也就是

(x_{j,0},x_{j,1})

，我們可以把

(q_j, q_j \bigoplus s)

當作加密函式的key，用來加密

(x_{j,0},x_{j,1})

，得到

(y_{j,0},y_{j,1})

，然後接收者

R

就可以使用

t_j

，解密出

r_j

對應的

x_{j,r_j}

。這裡的加密與解密操作是很簡單的，使用對稱加密即可，這相比公私鑰加密要快的多。

由此，我們透過

OT^k_m

，外加

2m

次的對稱加密，就實現了

OT^m_l

。

OT^k_m

的開銷是

k

次OT，加上

2m

次的對稱加密，相比

OT^m_l

的

m

次OT，還是要小很多的。尤其是當

m \gg k

時，這種差距就更加明顯。

之前還說到，我們可以進一步使用

OT^k_k

來實現

OT^k_m

，縮減開銷。從

OT^k_k

到

OT^k_m

是很簡單的，步驟如下：

傳送者

S

隨機初始化

k

對長度為

k

的金鑰

(s_{i,0}, s_{i,1})

接收者

R

有

k

個選擇位元

r = (r_1,...,r_k)

，透過

OT^k_k

，得到

k

個金鑰

s_{i,r_i}

對於

1 \leq i \leq k

，傳送者

S

傳送

(y_{i,0},y_{i,1})

，其中

y_{i,b} = x_{i,b} \bigoplus G(s_{i,b})

，

G：\{0,1\}^k \rightarrow \{0,1\}^m

為一個偽隨機函式

對於

1 \leq i \leq k

，接收者

R

得到

z_i = y_{i,r_i} \bigoplus G(s_{i,r_i})

我們可以看到，主要的思路就是透過

OT^k_k

傳輸長度為

k

的金鑰，作為對稱加密的金鑰，然後加密長度為

m

的資料，再進行傳輸。這樣做其實並沒有減少傳輸的資料量，因為實際上都要傳輸長度為

m

的資料給接收方。

更進一步

在有了不經意傳輸擴充套件之後，我們可以用它來改進之前的隱私集合求交演算法。最簡單的想法，就是將之前隱私集合求交演算法中所有的不經意傳輸，都使用不經意傳輸擴充套件來替換。這樣的確能夠提升演算法的效率，因為我們將大量“慢速”的不經意傳輸，替換為了少量的“慢速”不經意傳輸加大量的對稱加密。但是，演算法的傳輸量並沒有減少，仍然需要進行

O(nl)

次傳輸，每次傳輸2個長度為

k

的位元串。單純使用不經意傳輸擴充套件來替換不經意傳輸，只是減少了每次傳輸的計算開銷，並沒有減少傳輸上的開銷。那麼，能不能繼續減少傳輸上的開銷呢？答案是可以的。我們需要在不經意傳輸擴充套件的基礎上更進一步，繼續擴充套件。

觀察之前的不經意傳輸與不經意傳輸擴充套件，它們都是

1-2

不經意傳輸，也就是二選一。基於

1-2

不經意傳輸的正規化，對於一個長為

l

的輸入資料，我們需要為它的每一個位元進行一次不經意傳輸，所以傳輸量是

O(l)

。不經意傳輸除了

1-2

不經意傳輸，還有

1-n

不經意傳輸，也就是n選一。如果我們使用

1-n

不經意傳輸，那麼，對於一個長為

l

的輸入資料，傳輸量變為了

O(l/n)

。如果我們用

1-n

不經意傳輸來替換

1-2

不經意傳輸，很明顯，隱私集合求交演算法的傳輸量會縮減，但是漸進複雜度依然沒變，還是

O(nl)

，也就是說，傳輸量依然與輸入資料的長度

l

有關。但是，如果我們能實現

1-\infty

的不經意傳輸呢？那麼，隱私集合求交總體的傳輸量就會縮減到

O(n)

，因為我們只需要一次

1-\infty

不經意傳輸，就能實現不經意偽隨機函式（OPRF），也就是隱私比較了。

那麼，如何構建

1-\infty

不經意傳輸呢？我們要在剛剛介紹的不經意傳輸擴充套件的基礎上，實現大量的

1-\infty

不經意傳輸。

由不經意傳輸擴充套件到#FormatImgID_197#不經意傳輸

現在我們回頭看不經意傳輸擴充套件，接收方

R

會先隨機初始化一個

m \times k

的位元矩陣

T

，矩陣

T

的每一列

t^i

都會和選擇位元向量

r

進行異或，透過

1-2

不經意傳輸傳送給傳送方

S

。我們將

t^i \bigoplus r

得到的每一列，組成一個矩陣

U

， 那麼

u^i = t^i \bigoplus r\\

我們可以發現，

T

的第

j

行

t_j

，與

U

的第

j

行

u_j

進行異或

t_j \bigoplus u_j

，得到的都是全零或全一，是零還是一取決於選擇

r_j

。現在我們假設一個編碼函式

C:\{0,1\} \rightarrow \{0,1\}^k

，

C(b) = b^k

，也就是將輸入的位元

b

重複

k

次，即重複編碼。那麼，我們可以得到

t_j \bigoplus u_j = C(r_j)

。現在觀察傳送者

S

透過不經意傳輸得到的矩陣

Q

，我們知道

q_j = t_j \bigoplus (r_j · s)

，那麼，結合編碼函式

C

，我們可以得到：

q_j = t_j \bigoplus (C(r_j) · s) \\

思考一下，如果我們改變編碼函式

C

，上面的等式是否會成立？很顯然，只要

q^i = t^i

或

q^i = u^i

成立，上面的等式就是成立的。那麼，我們就可以對編碼函式

C

進行改動。

之前的編碼函式

C:\{0,1\} \rightarrow \{0,1\}^k

是重複編碼，輸入是一個位元，我們可以將它改為隨機編碼，且能接受任意長位元的輸入，即：

C:\{0,1\}^* \rightarrow \{0,1\}^k \\

那麼，現在接收者

R

的選擇位

r_j

就不需要限制在一個位元了，可以為一個任意長度的資料，即

r_j:\{0,1\}^*

。 我們知道，接收者

R

現在有位元矩陣

T

，傳送者

S

有矩陣

Q

，每一行

t_j = q_j \bigoplus (C(r_j) · s)

。對於傳送者

S

來說，它可以對任意長度的輸入

r

計算

q_j \bigoplus (C(r

，只有當

r_j = r

時，

t_j = q_j \bigoplus (C(r

才會成立。從不經意傳輸的角度來看，這就是一種

1-\infty

的不經意傳輸，因為接收者

R

只能獲得

t_j

一個輸出，傳送者

S

卻能對任意長的

r

計算

q_j \bigoplus (C(r

，也就是說，傳送者

S

能產生任意多個輸出，但是接收者

R

只能知道其中的一個。

實現不經意偽隨機函式（OPRF）

那麼，我們就可以使用

1-\infty

不經意傳輸，來實現隱私比較。讓

r_j

和

r

分別為

R

和

S

需要比較的資料，傳送者

S

輸出

H(j,q_j \bigoplus (C(r

，接收者

R

輸出

H(j,t_j)

，

H

是一種雜湊函式。只需要比較

R

與

S

的輸出，就可以實現隱私比較。

從上一篇文章，我們可以得知，隱私比較可以看作不經意偽隨機函式（OPRF）。那麼，我們就可以透過對不經意傳輸擴充套件進行改造，構造出大量不經意偽隨機函式。形式化的描述如下：

接收者

R

有

m

個選擇字串

r=(r_1,...,r_m)

，

r_i \in \{0,1\}^*

， 接收者

R

與傳送者

S

有一個共同的隨機編碼函式

C:\{0,1\}^* \rightarrow \{0,1\}^k

，

C

的編碼長度為

k

， 有一個共同的雜湊函式

H:[m]\times\{0,1\}^k \rightarrow \{0,1\}^v

R

先初始化一個

m \times k

隨機的位元矩陣

T

。

S

隨機初始化

k

個選擇位元

s=(s_1,...,s_k)

R

構建矩陣

U

，

u_j = t_j \bigoplus C(r_j)

，其中

u_j

與

t_j

分別表示

U

與

T

的第

j

行

R

作為傳送者，

S

作為接收者，執行

OT_m^k

。對於第

i

次長度為

m

的不經意傳輸，

R

的輸入為

(t^i,u^i)

，

t^i

和

u^i

分別表示矩陣

T

和

U

的第

i

列；

S

的輸入為

s_i

。當

s_i=0

時，

S

得到

t^i

，當

s_i=1

時，

S

得到

u^i

。將

S

收到的所有列組合成一個

m \times k

的矩陣，稱為

Q

現在，

R

作為接收者，

S

作為傳送者，可以執行

m

次OPRF。對於

1 \leq j \leq m

，

R

輸出

H(j,t_j)

，

S

輸出

H(j,q_j \bigoplus (C(r

，

r

，

r

為

S

選擇的任意值。

由此，我們就透過改造不經意傳輸擴充套件，實現了大量的不經意偽隨機函式。我們只需要進行固定次數（

k

次）的

1-2

不經意傳輸，就能實現

m

次（

m \gg k

）不經意偽隨機函式。每次不經意偽隨機函式，只需要使用一個雜湊函式，進行一次傳輸即可完成，與輸入的長度

l

無關，開銷很小。

安全性

我們現在來考慮上述協議的安全性。

假設接收者

R

是誠實且好奇的，也就是說，

R

會正確地執行協議，但是同時它會盡可能地嘗試從協議的輸出中窺探傳送者

S

的資訊。假設

S

發給

R

的資訊是

H(q_j \bigoplus (C(r

，

r

，

R

想要去暴力碰撞

r

，我們可以發現：

q_j \bigoplus (C(r

其中，只有

s

對

R

來說是未知的。如果要保證安全，我們需要讓

C(r

的漢明重量大於

\kappa

，這樣的情況下，

R

需要至少猜測出

s

中的

\kappa

位，才能完成碰撞攻擊。

\kappa

是一個安全引數，

\kappa

的值越大，攻擊者就越難完成攻擊。一般來說，

\kappa

的值需要至少大於等於128。

我們知道隨機編碼

C

的輸出長度是

k

，要使

C(r

的漢明重量大於

\kappa

，就需要

k > \kappa

。根據文章［1］的結論，只要

3\kappa < k < 4\kappa

，就能保證

C(r

的漢明重量小於

\kappa

的機率是可以忽略的。具體的證明這裡不做介紹，感興趣的讀者，可以自行檢視論文。

在隱私集合求交中的應用

回到隱私集合求交上，我們使用這種改進過的不經意偽隨機函式，可以大大提升演算法的效率。

上一篇文章中，已經介紹瞭如何使用不經意偽隨機函式來實現隱私隱私集合求交。隱私集合求交中，需要使用

1.2n+s

，也就是

O(n)

次的不經意偽隨機函式。現在，改進過的不經意偽隨機函式的開銷與輸入長度無關，是一個均攤的常數。使用改進過的不經意偽隨機函式後，隱私集合求交的漸進複雜度也就變為

O(n)

了，只與需要比較的集合大小相關，與集合中元素的長度無關。

從整體上看，隱私集合求交演算法只需要進行

k

次

1-2

不經意傳輸，外加

O(n)

次的對稱加密即可完成，其中

k

是個常數。我們可以將這

k

次不經意傳輸看作演算法的初始化階段，後續階段稱為線上階段，初始化階段的執行時間基本是固定的，線上階段的時間會隨著集合大小的增大而增大。 根據文章［1］中的試驗結果，當集合大小為

2^{20}

時，在內網環境下（延時0。2ms），使用改進過的不經意偽隨機函式的隱私集合求交，線上階段只需要不到4s時間，離線階段只需要600ms。與樸素的雜湊方法相比，樸素雜湊方法的執行時間在700ms左右。可以看出，這種方法的速度是很快的。

結論

綜上所述，我們使用固定次數的

1-2

不經意傳輸，外加對稱加密，就可以實現隱私求交演算法了。這樣實現的隱私求交演算法，速度是很快的，即使和樸素的雜湊方法相比，也不會很慢。演算法的傳輸量是

O(n)

，

n

是傳送者的集合大小，因此更加適合參與雙方進行比較的集合大小相差不大的情況。

本文只介紹了演算法的大致思路，如果需要詳細的瞭解，推薦閱讀原文章［1］。同時，原文章還有對應的開原始碼，可以作為參考：

https://github.com/osu-crypto/BaRK-OPRF

參考文獻：

［1］ Kolesnikov V， Kumaresan R， Rosulek M， et al。 Efficient batched oblivious PRF with applications to private set intersection［C］//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security。 2016： 818-829。

［2］ Ishai Y， Kilian J， Nissim K， et al。 Extending oblivious transfers efficiently［C］//Annual International Cryptology Conference。 Springer， Berlin， Heidelberg， 2003： 145-161。

隱私計算關鍵技術：隱私集合求交（PSI）的效能擴充套件

本文經「原本」原創認證，作者一個洋蔥，點選“閱讀原文”或訪問yuanben。io查詢【3GTCHEIO】獲取授權