隱私計算核心技術

非對稱加密算法

RSA

RSA 算法基礎

1. 歐拉函數(shù)：任意給定正整數(shù) n，在小于等于 n 的正整數(shù)中，有多少個數(shù)與 n 構成互質關系？計算這些值的方法叫做歐拉函數(shù)，以 \(\varphi(n)\) 表示。
2. 歐拉定理：如果兩個正整數(shù) a 和 n 互質，則 n 的歐拉函數(shù)可以讓下面的等式成立：

也就是說，a 的 \(\varphi(n)\) 次方被 n 除的余數(shù)為 1，或者說，a 的 \(\varphi(n)\) 次方減去 1，可以被 n 整除。

3. 費馬小定理：是歐拉定理的一個特殊情況，假設正整數(shù) a 和質數(shù) n 互質，因為質數(shù) n 的 \(\varphi(n)\) 等于 n-1，則歐拉定理可以寫成下面的公式：

4. 歐拉函數(shù)之積：如果 n 可以分解成兩個互質的整數(shù)之積，即 \(n = p_1 \times p_2\)，則積的歐拉函數(shù)等于各個因子的歐拉函數(shù)之積

5. 模反元素：如果兩個正整數(shù) a 和 n 互質，那么一定可以找到整數(shù) b（a 的模反元素），使得 \(ab-1\) 被 n 整除：

顯然，模反元素不止一個，而歐拉定理可以用來證明模反元素必然存在：

\(\begin{equation} a^{\varphi(n)}=a \times a^{\varphi(n)-1} \equiv 1(\bmod n) \end{equation}\)

密鑰生成

RSA 算法的安全性基于兩個大素數(shù)的乘積難以分解回原來的素數(shù)！

1. 隨機選擇兩個不相等的質數(shù) p 和 q，比如 61 和 53，實際應用中，這兩個質數(shù)越大，就越難破解
2. 計算 p 和 q 的乘積 n
3. 計算 n 的歐拉函數(shù) \(\varphi(n)\)：\(\varphi(n)=\varphi(p \times q)=\varphi(p) \times \varphi(q) = (p-1) \times (q-1)\)
4. 隨機選擇一個整數(shù) e，選擇條件是 \(1 < e < \varphi(n)\)，且 e 和 \(\varphi(n)\) 互質
5. 計算 e 對于 \(\varphi(n)\) 的模反元素 d： \(ed \equiv 1(\bmod \varphi(n))\)，這個式子等價于 \(ed - 1= k \times \varphi(n)\) （可以將 d 和 k 視為 x 和 y）
6. 將 n 和 e 封裝成公鑰，n 和 d 封裝成私鑰

注意，公鑰中包含 n，如果攻擊者能夠根據(jù) n 反推出 p 和 q，就能計算出私鑰，可以看出，RSA 的安全性是基于大整數(shù)因素分解及其困難這一假設。目前，大整數(shù)因數(shù)分解除了暴力破解，沒有很好的解決方案。

加密與解密

1. 加密：生成公私鑰之后，我們就可以進行加密計算了，加密計算公式為：\(m^e \equiv c(\bmod n)\)，其中 m 就是要加密的信息，c 就是計算生成的密文。
2. 解密：解密使用計算公式：\(c^d \equiv m(\bmod n)\)

為什么用私鑰解密就一定可以得到 m 呢？根據(jù)加密公式可知：\(c = m^e - kn\)，將 c 代入解密公式可得 \(\left(m^e-k n\right)^d \equiv m(\bmod n)\)，等同于求證 \(m^{e d}{\equiv m}(\bmod n)\)，證明過程有點復雜，這里先略過。

基于 RSA 算法的盲簽名

盲簽名是一種在不讓簽名者獲取所簽署消息具體內容的情況下進行數(shù)字簽名的技術。盲簽名允許擁有消息的一方先將消息盲化，而后讓簽名者對盲化的消息進行簽名，最后消息擁有者對簽字除去盲因子，得到簽名者關于原消息的簽名。

盲簽名的一個通俗的解釋是：Alice 想讓 Bob 在一張信件上簽名，但是不想讓 Bob 看到信件上面所寫的字。于是，Alice 在信件上面放了一張復寫紙，然后將信件和復寫紙放到了信封中交給 Bob。Bob 在拿到信封之后直接在信封上面簽字，這樣字跡就通過復寫紙寫到了信件上。Alice 拿到信封之后就可以得到 Bob 簽過字的信件。

基于 RSA 算法可以實現(xiàn)盲簽名，假設 Alice 要讓 Bob 對消息 \(m\) 進行盲簽名，Bob 擁有私鑰對 \((n, d)\) ，并共享了公鑰對 \((n, e)\) ，其具體實現(xiàn)步驟如下：

1. Alice 選取與 \(n\) 互質的盲因子 \(k\)，然后計算 \(t=m k^e(\bmod n)\) ，并把 \(t\) 發(fā)送給 Bob。
2. Bob 對 \(t\) 進行簽名，即計算 \(t^d \equiv\left(m k^e\right)^d(\bmod n)\)，并把計算結果發(fā)送給 Alice。
3. Alice 計算盲因子 \(k\) 的逆元 \(k^{-1}\) ，并計算 \(s \equiv k^{-1} t^d(\bmod n)\)，根據(jù)費馬小定理，可得 \(t^d \equiv\left(m k^e\right)^d \equiv m^d k^{e d-1} k \equiv m^d k(\bmod n)\) ，進而可得 \(s \equiv k^{-1} m^d k \equiv m^d(\bmod n)\) 。

最終 Alice 獲得了 Bob 的簽名，但 Bob 并不知曉所簽名的消息 \(m\) 的具體內容，即 Alice 獲得了 Bob 的盲簽名。

不經(jīng)意傳輸（Oblivious Transfer）

公鑰密碼系統(tǒng)主要依賴三大數(shù)學難題：大整數(shù)因子分解難題、離散對數(shù)難題、橢圓曲線上的離散對數(shù)難題

詳見 公鑰密鑰系統(tǒng)依賴的三大數(shù)學難題

也稱茫然傳輸，提出了一種在數(shù)據(jù)傳輸與交互過程中保護隱私的思路。在不經(jīng)意傳輸協(xié)議中，數(shù)據(jù)發(fā)送方同時發(fā)送多個消息，而接收方僅獲取其中之一。 發(fā)送方無法判斷接收方獲取了具體哪個消息，接收方也對其他消息的內容一無所知。

二選一不經(jīng)意傳輸：Alice 每次發(fā)送兩條信息 \((m_1, m_2)\) 給 Bob，Bob 提供一個輸入，并根據(jù)輸入獲得輸出信息，并根據(jù)輸出獲得輸出信息，在協(xié)議結束后，Bob 得到了自己想要的那條信息，而 Ailce 并不知道 Bob 最終得到的是哪條。

基于 RSA 加密算法：大數(shù)因數(shù)分解難題

大數(shù)因數(shù)分解難題涉及將一個大的合數(shù)分解為其素數(shù)因子。

下面來看一種基于 RSA 加密算法的不經(jīng)意傳輸協(xié)議的實現(xiàn)方式：

假設發(fā)送者 Alice 有 N 個電話號碼 \(m_1, ..., m_N\)，接受者 Bob 只能從中選取一個，但又不想讓 Alice 知道他拿了哪一個號碼。

1. 發(fā)送者 Alice 生成一對 RSA 公私鑰，并將公鑰 （n， e） 發(fā)送給接受者 Bob
2. Alice 方生成 N 個隨機數(shù) \(X_1, ..., X_N\)，將它們發(fā)送給接收者 Bob
3. Bob 方生成一個隨機數(shù) k 以及一個編號標識 b（也就是 Bob 選擇了第 b 個電話號碼），b 是 Bob 需要保密的信息
4. Bob 方用接受到的公鑰加密 k，同時用自己選中的 \(X_b\) 盲化后發(fā)送給 Alice：\(v = X_b+\left(k^e\right) \bmod n\)
5. Alice 方并不知道 Bob 方究竟選擇了哪個，她將 \(X_0, ..., X_N\) 中每個數(shù)據(jù)都拿去解密，獲得了 \(k_0, ..., k_N\) 個解密結果：\(k_t=\left(v-X_t\right)^d \bmod n\)。顯然，這 N 個結果中只有 \(k_b = k\)
6. Alice 方對 N 個解密結果分別加上真實要發(fā)送的信息后發(fā)送給 Bob：\(m_t^{\prime}=m_t+k_t\)，$m_t $ 是 Alice 需要保密的信息
7. Bob 方根據(jù)自己選中的消息編號，只需要對第 b 個消息解密就可以獲得自己選中的電話號碼。對于其他消息，Bob 即使去解密也只能獲得一個沒有意義的隨機值，而 Alice 方始終無法獲知 Bob 究竟拿到了哪一個號碼：\(m_b=m_b{ }^{\prime}-k\)

為便于理解，第四步和第五步的公式也可寫為：

第四步：\(v = X_b+ \text{Encryption}(k)\)

第五步：\(k_t=\text{Decryption}(v-X_t)\)，其中 \(k_b=\text{Decryption}(X_b+ \text{Encryption}(k)-X_b)= k\)

另一種類似的方式如下：將 Alice 方生成的 N 個隨機數(shù)換成 N 對 RSA 公私鑰

上圖中同時使用 RSA 和 AES 對數(shù)據(jù)進行加解密，兩者的區(qū)別如下：

	RSA	AES
類型	一種非對稱加密算法，公鑰用于加密，私鑰用于解密	一種對稱加密算法，使用相同的密鑰來進行加密和解密
用途	RSA 常用于加密小塊數(shù)據(jù)，如數(shù)字簽名、密鑰交換等。由于非對稱加密的計算開銷較大，因此 RSA 一般用于加密小數(shù)據(jù)或者加密對稱加密算法（如 AES）中的密鑰	AES 通常用于加密大量數(shù)據(jù)，如文件、通信數(shù)據(jù)等。對稱加密算法具有較高的加密和解密速度，因此適合處理大量數(shù)據(jù)的加密工作
加密速度	RSA 基于大整數(shù)的運算，其加密和解密過程較為耗時	AES 的加解密過程基于固定長度的數(shù)據(jù)塊和密鑰，因此可以使用高度優(yōu)化的算法和硬件實現(xiàn)
密鑰長度	RSA 的安全性依賴于大整數(shù)的因數(shù)分解問題，因此需要較長的密鑰長度來保證足夠的安全性。通常，RSA 密鑰長度為 1024 位或更長	AES 的安全性主要依賴于密鑰長度，一般使用 128 位、192 位或 256 位的密鑰。較長的密鑰長度通常提供更高的安全性，但也增加了加密和解密的計算開銷。

基于有限域的公鑰運算：有限域的離散對數(shù)難題（DLP 問題）

大數(shù)離散對數(shù)難題涉及在一個大的有限群中找到離散對數(shù)的難度。

基于離散對數(shù)實現(xiàn) 2 選 1 的 OT 協(xié)議執(zhí)行過程如下圖所示：

基于離散對數(shù)實現(xiàn) n 選 1 的 OT 協(xié)議執(zhí)行過程如下圖所示：https://blog.nsfocus.net/ot-1/

基于橢圓曲線的公鑰運算：橢圓曲線的離散對數(shù)難題（ECDLP）

關于橢圓曲線密碼學的知識點，請參考：公鑰密碼學依賴的三大數(shù)學難題

序號	Sender	Share	Receiver
目標	輸入：\((m_0, m_1)\) 輸出：\(None\)		輸入：選擇比特 b 輸出：\(m_b\)
1	生成隨機的 ECC 密鑰對 \((sk_s, pk_s)\) \(s\_pk\) 由 \(s\_sk\) 和基點 G 相乘得到	Sender 將 \(pk_s\) 發(fā)送給 Receiver \(\to\)	接收 \(pk_s\)， 從 \(pk_s\) 中提取橢圓曲線信息，生成新的 ECC 密鑰對 \((sk_r, pk_r)\)
2	\(ck_0 = pk_{new} * sk_s\) \(ck_1 = (pk_{new}-pk_s) * sk_s\)	Receiver 將 \(pk_{new}\) 發(fā)送給 Sender \(\leftarrow\)	\(if\ b=0,\ pk_{new} = pk_r\) $if\ b=1,\ pk_{new} = pk_r + pk_s $
3	\(cipher\_m_0 = Enc(ck_0, m_0)\) \(cipher\_m_1 = Enc(ck_1, m_1)\)	Sender 將加密后的 \((m_0, m1)\) 發(fā)送給 Receiver \(\to\)	計算 \(ck = pk_s * sk_r\) \(Dec(ck, cipher\_m_b)\)，即 \(m_b\)

證明過程如下：在第二步中

因此有：\(ck_b = pk_r * sk_s\)，由 ECDH 密鑰交換協(xié)議知：\(ck_b = pk_r * sk_s = pk_s * sk_r = ck\)

布隆過濾器（Bloom Filter）

布隆過濾器是由一個固定大小的二進制向量或者位圖（Bitmap）和一系列映射函數(shù)組成的。在初始狀態(tài)時，對于長度為 m 的位數(shù)組，它的所有位都被置為 0，如下圖所示：

當有變量被加入集合時，通過 k 個映射函數(shù)將這個變量映射成位圖中的 k 個點，把它們置為 1。

查詢某個數(shù)據(jù)的時候，只要看這些點是不是都是 1 就可以大概率知道集合中是否包含該數(shù)據(jù)了：如果這些點中有任何一個是 0，被查詢變量一定不在，如果都是 1，被查詢變量很可能存在。

為什么是可能存在，而不是一定存在呢？因為映射函數(shù)本身就是散列函數(shù)，散列函數(shù)會有碰撞。

可以看出，布隆過濾器在空間和時間方面都有巨大的優(yōu)勢：

1. 布隆過濾器存儲空間和插入、查詢時間都是常數(shù)
2. 散列函數(shù)相互之間沒有關系，方便并行實現(xiàn)
3. 布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優(yōu)勢

混淆電路（Grable Circuit）

百萬富翁問題：加密學問題

假設有兩個百萬富翁，他們都想知道誰更富有，但他們都想保護好自己的隱私，都不愿意讓對方或者任何第三方知道自己真正擁有多少財富。那么，如何在保護好雙方隱私的情況下，計算出誰更有錢呢？

使用一個更加專業(yè)的說法：一組互不信任的參與方在需要保護隱私信息以及沒有可信第三方的前提下進行協(xié)同計算的問題。

混淆電路（GC）：一種將計算任務轉化為布爾電路并對真值表進行加密打亂等混淆操作以保護輸入隱私的思路。利用計算機編程將目標函數(shù)轉化為布爾電路后，對每一個輸出的真值進行加密，參與方之間在互相不掌握對方私有數(shù)據(jù)的情況下共同完成計算。

可計算問題可以轉換為一個個電路，CPU 就是由加法電路、比較電路和乘法電路等組合而成的。一個電路由一個個邏輯門組成，比如與門、非門、或門、與非門等。每個邏輯門都有輸入端和輸出端。

在經(jīng)典的混淆電路中，加密和擾亂是以門為單位的，每個門都有一張真值表，下圖展示了與門的真值表：

不妨認為倆個富翁 Alice 和 Bob 的財富是用二進制表示的一個整數(shù)：

1. Alice 方的財富值用 a 表示：\(a=a_4 a_3 a_2 a_1 a_0=01101\)
2. Bob 方的財富用 b 表示：\(b=b_4 b_3 b_2 b_1 b_0=10100\)

下面以與門為例來說明混淆電路的工作原理，介紹如何使用混淆電路實現(xiàn)對 a 和 b 的與操作。

1. Alice 方首先對與門的每根輸入線（a 和 b）生成兩個隨機的標簽來分別對應 0 和 1，其中，標簽的比特位長度是 k，其取值是算法的安全參數(shù)，一般可以設為 128。
2. Alice 方將與門真值表中的 0 和 1 替換成對應的標簽，如下表所示：

3. Alice 方將真值表輸入線上的標簽作為加密密鑰對真值表輸出線標簽，并使用對稱加密算法進行加密：

4. Alice 方將真值表上的行順序打亂，這樣其他人就無法根據(jù)標簽值知曉其對應真值表上的哪一行：

5. 假設 \(a=a_4 a_3 a_2 a_1 a_0=01101\)，Alice 對 5 個比特位都生成混淆后的與門真值表，并將它們發(fā)送給 Bob，下表展示了針對第 0 位比特生成的經(jīng)混淆后的與門真值表，Bob 需要輸入線上的標簽值才能根據(jù)真值表進行計算，因此 Alice 方把值 a 的每個比特位對應的標簽發(fā)送給 Bob：\(x_0^{a_4} 、 x_1^{a_3} 、x_1^{a_2}、 x_0^{a_1} 、 x_1^{a_0}\)，因為標簽值是隨機生成的，因此 Bob 方無法從中獲得任何信息。

6. 真值表計算除了需要輸入線上 a 的值，還需要輸入線上 b 的值。但是，輸入線 b 對應的標簽都是由 Alice 方產(chǎn)生的，為此 Bob 需要從 Alice 處獲取。假設 \(b=b_4 b_3 b_2 b_1 b_0=10100\)，對于第 0 個比特位 \(b_0 = 0\)，Bob 使用不經(jīng)意傳輸協(xié)議，就可以從 Alice 處獲取對應的標簽 \(x_0^{b_0}\)。根據(jù)不經(jīng)意傳輸協(xié)議，Bob 是無法獲知 \(x_1^{b_0}\) 值的，Alice 也無法知曉 Bob 究竟獲取了哪個標簽。Bob 對每個比特位需使用不經(jīng)意傳輸協(xié)議獲取對應的標簽值：\(x_1^{b_4} 、 x_0^{b_3} 、 x_1^{b_2} 、 x_0^{b_1} 、 x_0^{b_0}\)。
7. 對于獲取到的標簽值，Bob 通過遍歷從 Alice 處獲得的對應的混淆后的與門真值表的每一行來嘗試解密。比如針對第 0 位，對真值表中的每一行，Bob 嘗試用 $x_1^{a_0} 、 x_0^{b_0} $ 去解密，直到解密成功，對每個比特位解密后，Bob 就可以獲得 \(x_0^{c_4} 、 x_0^{c_3} 、 x_1^{c_2} 、 x_0^{c_1} 、 x_0^{c_0}\)。
8. Bob 將解密獲得的 \(x_0^{c_4} 、 x_0^{c_3} 、 x_1^{c_2} 、 x_0^{c_1} 、 x_0^{c_0}\) 發(fā)送給 Alice，Alice 就可以根據(jù)自己生成標簽時的對應關系恢復出計算結果 00100，而這個結果正是 a 和 b 執(zhí)行與操作的計算結果。

至此，Alice 與 Bob 在保護好各自數(shù)據(jù)的前提下完成了與操作。兩個數(shù)的比較操作可以通過多個異或門和與門來實現(xiàn)。

我們定義變量 \(c_i\)：

以及其初始值 \(c_1=0\) 。在已知 \(a_i, b_i, c_i\) 的情況下， \(c_{i+1}\) 可以做如下推導：

注意：上述的混淆電路屬于半誠實模型，電路本身還有很多優(yōu)化空間。

秘密共享（Secret Sharing）

指將一個秘密分發(fā)給一組參與方，每個參與方只獲取這個秘密的一部分，這樣一個或少數(shù)幾個參數(shù)方無法還原出原始數(shù)據(jù)（秘密），只有滿足一定數(shù)量的參與方把各自的數(shù)據(jù)湊在一起，才能還原出真實數(shù)據(jù)。計算時，各參與方直接用它自己的本地數(shù)據(jù)進行計算，并且在適當?shù)臅r候交換一些數(shù)據(jù)（交換的數(shù)據(jù)本身看起來也是隨機的，不包含原始信息）。計算結束后，結果仍以秘密共享的方式分散在各參與方那里，并在使用方最終需要結果時將某些數(shù)據(jù)合起來。通過這種方式，秘密共享技術保證了計算過程中各個參與方看到的都是一些隨機數(shù)，但最后仍得到了想要的結果。

秘密共享方案的三種實現(xiàn)技術：

1. 有限域上的運算：基于超平面幾何的秘密共享，包括 Blakley 方案和 Brickell 方案；
2. 有限域上的運算：基于插值多項式的秘密共享，包括經(jīng)典的 Shamir 閾值秘密共享方案；
3. 環(huán)上的運算：Mignotte，Asmuth & Bloom 提出的基于中國剩余定理的秘密共享；

Shamir 門限秘密共享方案流程

1. 將秘密信息 s 拆成 n 份，每個參與方獲得一份，每一份被稱作一個 Share。每個參與者秘密地保存好自己的 Share。
2. 拆分時，預先設定至少 t （t <= n） 個參與者聚到一起才可以恢復 s。
3. 需要恢復 s 時，至少有 t 個參與者聚到一起，他們拿出各自的 Share，通過計算恢復出 s。

Shamir 門限秘密共享方案原理

Shamir 門限秘密共享方案的實現(xiàn)原理是對于任意一個 \(t-1\) 次多項式函數(shù)，只需要獲取其多項式曲線上的 t 個點就可以通過多項式插值（比如拉格朗日插值法）確定該多項式函數(shù)。而 Blakley 的解決方案基本思想是利用多維空間中的點：將共享的秘密看成 t 維空間中的一個點，每個子秘密為包含這個點的 \(t-1\) 維超平面的方程，構造 n 個這樣的平面分發(fā)給 n 個參與方，任意 t 個 \(t-1\) 維超平面的交點剛好確定共享的秘密，而 \(t-1\) 個子秘密，即 \(t-1\) 個 \(t-1\) 維超平面僅能確定其交線，得不到共享秘密的任何信息。

針對下面這個多項式函數(shù)，我們具體介紹一下秘密分發(fā)的過程：

p 是一個大素數(shù)，其中 \(f(0)=a_0=s\)（s 是需要保護的秘密），且 \(s < p\)，具體過程如下：

1. 秘密擁有者秘密隨機生成 \(t-1\) 個小于 \(p\) 的隨機數(shù) \(a_1, a_2, \ldots, a_{t-1}\) ，并隨機選取 \(n\) 個互不相同的整數(shù) \(x_1, x_2, \ldots, x_n\) 。
2. 將 \(n\) 個整數(shù)代入多項式函數(shù)，計算得到 \(n\) 個值 \(s_1=f\left(x_1\right), s_2=f\left(x_2\right), \ldots, s_n=f\left(x_n\right)\) 。
3. 將計算得到的 \(n\) 個值分別分發(fā)給 \(n\) 個參與方，即第 \(i\) 個參與方獲得 \(\left(x_i, s_i\right)\) （作為該參與方需要嚴格保守的秘密）。
4. 銷毀 \(f(x)\) 。根據(jù)多項式函數(shù)的性質，少于 \(t\) 個參與方都無法恢復出這個多項式函數(shù)。而大于等于 $$ 個參與者通過其子秘密 \(s_i\) 和 \(x_i\) 通過拉格朗日插值定理可以恢復上面多項式 \(f(x)\)，并且令 \(x=\) 實現(xiàn)秘密 s 的重構：

拉格朗日插值定理：通過給定的一組數(shù)據(jù)點，可以構造出一個多項式，該多項式通過這些點。

接下來以 \((3,4)\) -門限實例來說明 \(t\) 個參與方如何恢復秘密，這里假設秘密 \(s=2\)， \(p=23\)，構造的 \(f(x)\) 如下：

根據(jù)函數(shù)可知，這里 \(t\) 的取值為 3，另取 \(x_1=1 ， x_2=2 ， x_3=3 ， x_4=4\)，代入函數(shù)得 \(f(1)=7 ， f(2)=16 ， f(3)=6 ， f(4)=0\) 。 隨機選取其中 3 組數(shù)據(jù) \((1,7) 、(3,6) 、(4,0)\) ，并使用拉格朗日插值公式進行恢復 :

經(jīng)過上述計算，成功恢復出秘密 \(s\) 為 2 。

參考：秘密共享 — 隱私計算和區(qū)塊鏈共識中的榫卯

通過秘密共享實現(xiàn)隱私計算的原理

如何利用秘密共享進行隱私計算呢？這里以 （2， 2）-門限的加法為例，假設 Alice 和 Bob 為輸入方，Alice 擁有隱私輸入 a，Bob 擁有隱私輸入 b，Uzer 為結果使用方，設計兩個計算方 CP1 和 CP2，計算過程如下：

再以乘法為例：

$$ \begin{equation} c 1+c 2+c 3+c 4=a 1 \times b 1+a 2 \times b 2+a 1 \times b 2+a 2 \times b 1=(a 1+a 2) \times(b 1+b 2)=a \times b \end{equation} $$

同態(tài)加密（Homomorphic Encryption）

HE 是一種特殊的加密方法，它允許直接對加密數(shù)據(jù)執(zhí)行計算，如加法和乘法，而計算過程不會泄露原文的任何信息。計算的結果仍然是加密的，擁有密鑰的用戶對處理過的密文數(shù)據(jù)進行解密后，得到的正好是處理后原文的結果。

根據(jù)支持的計算類型和支持程度，同態(tài)加密可以分為以下三種類型：

1. 半同態(tài)加密（Partially Homomorphic Encryption， PHE）：只支持加法或乘法中的一種運算。其中，只支持加法運算的又叫加法同態(tài)加密（Additive Homomorphic Encryption， AHE）；
2. 部分同態(tài)加密（Somewhat Homomorphic Encryption， SWHE）：可同時支持加法和乘法運算，但支持的計算次數(shù)有限；
3. 全同態(tài)加密（Fully Homomorphic Encryption， FHE）：支持任意次的加法和乘法運算。

同態(tài)加密具有如下的特點：

1. 計算復雜度小，通信量高，通信輪次少的特點
2. 適合密文一次部署，多次計算的場景，大幅減少通信量

差分隱私（Differential Privacy）

差分隱私旨在提供一種當從統(tǒng)計數(shù)據(jù)庫查詢時，在保證查詢結果一定精度的同時最大限度減少識別出某個樣本的可能性。差分隱私的目的是用來對抗差分攻擊，通常其應用場景是統(tǒng)計查詢。

核心思想

這里以一個直觀的例子來說明差分隱私的原理。

假設數(shù)據(jù)集 D 包含 Alice 的記錄，而數(shù)據(jù)集 D' 中 Alice 的記錄被替換為 Bob 的記錄，其他記錄與數(shù)據(jù)集 D 完全一致。假設從 D 和 D' 兩個數(shù)據(jù)集中隨機挑選一個數(shù)據(jù)集并提取一些信息 O 給到攻擊者，如果攻擊者無法識別這些信息是從哪個數(shù)據(jù)集中提取出來的，那么可以認為所發(fā)布的信息保護了 Alice 的隱私。差分隱私要求任何被發(fā)布的信息都應當與信息 O 類似，確保攻擊者無法識別出任何具體的數(shù)據(jù)記錄。

差分隱私技術的核心思想是對于任意兩個相差一條記錄的數(shù)據(jù)集 D 和 D'，以及任意輸出 O，要求添加了隨機繞動的查詢機制 M（一般是一些統(tǒng)計信息的查詢，比如均值、方差）都能滿足：

其中 P 是通過查詢機制 M 獲得輸出 O 的概率，這意味著在數(shù)據(jù)集 D 中一條數(shù)據(jù)發(fā)生變化后通過 M 得到 O 的概率的變化會非常小，概率 P 的變化范圍由公式中的 \(\epsilon\) 決定，這是稱查詢機制 M 滿足 \(\epsilon\) 差分隱私。

直白一點來說，如果能設計一種算法，讓攻擊者在查詢 100 條信息和去掉任意一條信息的其他 99 條信息時，獲得相同值的概率非常接近，攻擊者就沒辦法確定第 100 條信息了，這樣我們就說第 100 條信息對應的個體得到了隱私保護。這樣的算法就是差分隱私算法。差分隱私其實是一個框架，一個用于評估保護隱私的查詢機制（算法）的框架。

差分隱私具有如下的特點：

1. 計算和通信新能與直接明文計算幾乎無區(qū)別
2. 安全性以及精度損失由加的噪聲決定

分類

根據(jù)原始數(shù)據(jù)的存儲位置劃分，差分隱私分為中心化差分隱私和本地化差分隱私：

1. 中心化差分隱私：實現(xiàn)加入很小的噪聲保護數(shù)據(jù)集中所有用戶的隱私，但是需要所有用戶將未經(jīng)處理的原始數(shù)據(jù)直接存儲在一個可信服務器上

1. 本地化差分隱私：允許用戶在本地隨機化原始數(shù)據(jù)后再發(fā)送給服務器，使得用戶得到了更強的隱私保護，但這一過程加入的噪聲遠大于全局差分隱私。注意，蘋果公司在 ios 輸入法中使用的差分隱私技術就屬于此類。

經(jīng)典算法

拉普拉斯機制

差分攻擊：攻擊者通過比較多次查詢獲得的不同結果來推算出部分原始明文數(shù)據(jù)。

差分隱私是如何進行隱私信息的保護，防止差分攻擊呢？

差分隱私通常的做法是在查詢結果中引入噪聲。

對于數(shù)值型的查詢結果，常用的方法是在查詢結果中加入服從拉普拉斯分布的噪聲，這種方法被稱為拉普拉斯機制。

拉普拉斯分布的概率密度函數(shù)為：\(p d f(x)=\frac{1}{2 \lambda} \mathrm{e}^{\left(-\frac{|x|}{\lambda}\right)}\)

橫軸表示隨機變量，縱軸表示相對應的概率密度，那么對于數(shù)據(jù)庫查詢：select count（*） from D where type=“AIDS”，可以在查詢結果中加入一個服從拉普拉斯分布的噪聲（加入噪聲后的查詢結果將具備一定的隨機性）。

根據(jù)差分隱私的理論，加入的噪聲參數(shù)滿足 \(\lambda = 1/\epsilon\)，即能滿足 ε-差分隱私。

隨機化回答機制

如果要發(fā)布的數(shù)據(jù)不是數(shù)值型，那么需要用其他方法引入噪聲。這里介紹一種用于數(shù)據(jù)采集的簡單機制：隨機化回答。

舉例來說，假設一個小伙想在互聯(lián)網(wǎng)上問一個敏感的是非題，比如“大家認為我和我的女朋友是否般配”。由于問題比較敏感，有些網(wǎng)友可能會不愿意給出真實的答案，這對結果統(tǒng)計可能沒有什么意義。為了解決這個問題，如圖 7-7 所示，我們可以讓每個人在他的答案中加入隨機噪聲。

1. 假設他的真實答案是“是”，擲一次骰子，如果擲出來的是 1，就回答真實答案是；如果擲出來是 2～6，就以投硬幣的方式回答是或者否。
2. 假設他的真實答案是“否”，也擲一次骰子，如果擲出來的是 1，就回答真實答案否；如果擲出來是 2～6，就以投硬幣的方式回答是或者否。由于回答存在隨機性，因此攻擊者并不能從一個回答者的答案中反推出他的真實答案。只要根據(jù) ε 來調整隨機化的概率，即可滿足 ε-差分隱私。

如何從隨機化回答中獲得統(tǒng)計信息呢？假設有 60 000 人按上面的規(guī)則進行了回復，其中有 28 000 個是，32 000 個否。可知，每個人以 5/6 的概率給的是假回復，即約有 50 000 人給出假回復，其中約有 25 000 個假是和 25 000 個假否。據(jù)此可以推算出來剩下的真實回復里約有 3000 個是和 7000 個否，即約有 70% 的人的答案為否。

零知識證明（Zero-Knowledge Proof，ZKP）

ZKP 指的是證明者能夠在不向驗證者提供任何有用信息的情況下，使驗證者相信某個論斷是正確的，允許證明者（Prover）、驗證者（Verifier）證明某項提議的真實，卻不必泄漏除了“提議是真實的”之外的任何信息。

交互式零知識證明

以數(shù)獨游戲為例來展開介紹零知識證明。假設有兩個人 Vicky 和 Patty，有一天，Patty 告訴 Vicky 自己花了半天時間解出了一道極難的數(shù)獨游戲題，而喜歡挑戰(zhàn)的 Vicky 自然也想嘗試一下。但他又擔心 Patty 是在拿無解的數(shù)獨題目來開玩笑，希望 Patty 能證明題目有解。顯然，如果 Patty 直接告訴 Vicky 答案，Vicky 也就無法自己獨立完成題目，從而無法享受游戲的樂趣了。為此，兩人設計了一種證明方案，方案分為以下幾個階段。

承諾階段

首先，Patty 將寫有答案的數(shù)獨盤面按數(shù)字剪成小紙片，并按照原順序擺放在桌子上，且題目中的原有數(shù)字正面朝上，答案部分正面朝下：

挑戰(zhàn)階段

Vicky 可以選擇按行、列或者九宮格的方式要求 Patty 證明。比如 Vicky 選擇按列方式挑戰(zhàn)。

回應挑戰(zhàn)階段

Patty 將桌面上每一列的 9 張紙片裝入一個盒子，并且打亂紙片順序進行混淆，然后將所有盒子交給 Vicky，作為挑戰(zhàn)的回應。

驗證階段

Vicky 打開盒子驗證每個盒子里的 9 張紙片剛好是 1～9 這 9 個數(shù)字。這也意味著 Patty 在承諾階段做出的承諾滿足“每列 1～9 都出現(xiàn)并且只出現(xiàn)一次”這一要求，同時在一定程度上說明 Patty 做出的承諾很可能是題目的答案（因為在做出承諾的時候并不知道 Vicky 會選擇哪種方式進行驗證，隨意給出的數(shù)字難以通過驗證）。

重復階段

盡管一次驗證成功能在一定程度上說明 Patty 做出的承諾很可能是題目的答案。但是，Vicky 無法確信，因為存在 1/3 的概率 Patty 恰巧事先猜對了 Vicky 會選擇按列進行驗證，然后給出的承諾僅僅滿足列的要求，不滿足行的要求和九宮格的要求。因此 Vicky 可以要求再試幾次，直到自己確信為止。

非交互式零知識證明

交互式零知識證明存在種種缺陷，如要求證明者時刻在線并等待挑戰(zhàn)，驗證者如需驗證，需要與證明者進行多次交互。

為此，Patty 發(fā)明了一個非交互式數(shù)獨零知識證明機器。該機器可以自動地隨機選擇按列、按行或者按九宮格收取紙片到盒子。Patty 為了證明自己沒有作弊，把自己打開機器傳送出盒子的動作拍攝成視頻并放到網(wǎng)上。這樣，Vicky 和 Tom 都可以在網(wǎng)上進行觀看、驗證。當然，有可能還是有人會認為機器有后門，那么 Patty 還需要將機器是如何制造、安裝等別人可能懷疑的地方都通過視頻放到網(wǎng)上。這一過程就可以稱為“可信任的初始設置儀式”。

不經(jīng)意偽隨機函數(shù) （Oblivious Pseudo Random Function OPRF）

核心思想

OPRF 的定義和安全性模型：OPRF 是一種兩方協(xié)議，其中一方（發(fā)送方）持有一個偽隨機函數(shù)（PRF）的密鑰 k，另一方（接收方）持有一個輸入 x。協(xié)議的目標是讓接收方得到 PRF 在 k 和 x 上的輸出 \(f(k, x)\)，而發(fā)送方不得到任何信息。OPRF 的安全性要求滿足正確性、單向性、隱私性和可驗證性等屬性。

OPRF 的基本構建模塊：OPRF 的構造依賴于一些密碼學原語，如偽隨機函數(shù)、雙線性映射、同態(tài)加密等。偽隨機函數(shù)是一種可以用密鑰和輸入生成隨機輸出的函數(shù)，具有不可區(qū)分性和抗碰撞性等特點。雙線性映射是一種可以在兩個群之間進行映射的函數(shù)，具有可計算性和非退化性等特點。同態(tài)加密是一種可以在密文上進行運算的加密方式，具有可加性或可乘性等特點。

OPRF 的分類：根據(jù)底層 PRF 的類型可以分為四大類

1. Naor-Reingold 型 OPRF：基于雙線性映射的 PRF，可以實現(xiàn)單向性和可驗證性。這類 OPRF 的優(yōu)點是效率高，缺點是需要大量的公共參數(shù)和存儲空間。
2. Dodis-Yampolskiy 型 OPRF： 基于哈希函數(shù)和同態(tài)加密的 PRF，可以實現(xiàn)單向性和可擴展性。這類 OPRF 的優(yōu)點是不需要公共參數(shù)和存儲空間，缺點是效率低。
3. Hashed Diffie-Hellman 型 OPRF：基于哈希函數(shù)和 Diffie-Hellman 協(xié)議的 PRF，可以實現(xiàn)單向性和可擴展性。這類 OPRF 的優(yōu)點是效率高且安全性強，缺點是需要雙線性映射或橢圓曲線群。
4. 通用型 OPRF：這類 OPRF 基于任意的 PRF，它使用一種通用的構造方法將任意的 PRF 轉化為一個 OPRF。這類 OPRF 的優(yōu)點是適用范圍廣，缺點是效率低且安全性弱。

PRF 是一個確定性的函數(shù)，記為 F。我們稱 F 是定義在 （k， X， Y）上的 PRF，其中 k 是密鑰空間，X 是輸入空間，Y 是輸出空間。

它有兩個輸入，一個是密鑰 k，另一個是數(shù)據(jù)塊 \(x \in X\)，輸出 \(y = F(k, x) \in Y\) 也是一個數(shù)據(jù)塊。

對于 PRF，其安全性要求：給定一個隨機產(chǎn)生的密鑰 k，函數(shù) \(F(k, .)\) 應該看上去像一個定義在 X 到 Y 上的隨機函數(shù)。

隨機函數(shù)：給定集合 X 和 Y，定義在 X 到 Y 上的映射 \(f\)：X \(\to\) Y，首先把所有定義在 X 到 Y 上的映射集中 i 起來，形成一個集合。這個集合里的每個元素都是一個類似 \(f\) 這樣的映射，記為 Func[X， Y]。現(xiàn)在從 Func[X， Y] 中隨機選擇一個函數(shù)，這個函數(shù)就是“隨機函數(shù)”。

注意，所謂的“隨機函數(shù)”只是強調這個函數(shù)是被隨機地選擇出來的，與函數(shù)的輸出是否隨機沒有關系。

舉個例子：假設 Alice 有一些輸入，Bob 有一個 key，OPRF 允許 Alice 將自己的輸入與 Bob 的 Key 結合經(jīng)過一系列運算轉變成相應的數(shù)。在這個過程中，Alice 不能知道 Bob 的 key，Bob 也不知道最后的結果 \(f(k, x)\)，每一個輸入 \(x_i\) 都可以計算出一個不同于其他輸入的數(shù)，這些數(shù)可以被看作是“偽隨機數(shù)”

OPRF 在隱私保護技術中的應用

1. OPRF 在隱私保護技術中的作用：可以用來實現(xiàn)一些隱私保護技術，如密碼認證、密碼存儲、密碼恢復、密碼搜索、密碼交換等，這些技術可以利用 OPRF 的單向性、可驗證性和可擴展性等屬性來保護用戶的密碼和數(shù)據(jù)。
2. OPRF 在密碼認證中的應用：可以用來實現(xiàn)一種安全的密碼認證協(xié)議，這種協(xié)議可以讓用戶使用自己選擇的密碼來登錄一個遠程服務器，而不需要將密碼或者其哈希值泄露給服務器或者其他攻擊者。這種協(xié)議可以防止字典攻擊，中間人攻擊和離線攻擊等。
3. OPRF 在密碼存儲中的應用：可以用來實現(xiàn)一種安全的密碼存儲方案，讓用戶將自己的密碼或其他敏感數(shù)據(jù)存儲在一個云服務處，而不需要將明文或其哈希值泄露給云服務商或其其他攻擊者，
4. OPRF 在密碼恢復中的應用： 可以用來實現(xiàn)一種安全的密碼恢復機制，讓用戶在忘記自己的密碼時，通過一個可信任的第三方來恢復自己的密碼或其他敏感數(shù)據(jù)，而不需要將明文或其哈希值泄露給第三方或其他攻擊者。
5. OPRF 在密碼搜索中的應用：可以用來實現(xiàn)一種安全的密碼搜索技術，讓用戶在一個加密的數(shù)據(jù)庫中進行關鍵字搜索，而不需要將關鍵字或其哈希值泄漏給數(shù)據(jù)庫提供者或其他攻擊者。
6. OPRF 在密碼交換中的應用：可以用來實現(xiàn)一種安全的密碼交換協(xié)議，如隱私求交，讓兩個用戶交換他們各自持有的一組元素（如聯(lián)系人、喜好、歷史記錄等），而不需要將元素或其哈希值泄漏給對方或其他攻擊者。

布谷鳥哈希（Cuckoo Hashing）

布谷鳥的行為：關鍵設計就是“踢出”（kicks out）這個動作

1. 布谷鳥媽媽從不筑巢，它將自己的鳥蛋生在其他鳥類的巢穴里，要別的鳥給它孵蛋
2. 新出生的布谷鳥會本能地將巢穴里的其他蛋踢出（kicks out）鳥巢，借巢長大

哈希的本質是從一個較大空間映射到一個較小的空間，因此在插入數(shù)據(jù)足夠多之后，根據(jù)鴿巢原理，一定會存在位置沖突。常見的哈希表會通過鏈表、開放地址探測等方式來處理沖突。

單桶多函數(shù)的布谷鳥哈希，便是開放地址法處理沖突的一種哈希表，只不過有沖突后，不是通過線性尋找新的位置，而是通過額外哈希函數(shù)來尋找。布谷鳥哈希利用較少計算換取了較大空間，它具有占用空間小、查詢迅速等特性。

核心思想

1. 使用兩個哈希函數(shù) \(h_1(x)\) 、\(h_2(x)\) 和兩個哈希桶 \(T_1\) 和 \(T_2\)
2. 插入元素 x：
   1. 如果 \(T_1[h_1(x)]、T_2[h_2(x)]\) 有一個為空，則插入；兩者都空，隨便選一個插入
   2. 如果 \(T_1[h_1(x)]、T_2[h_2(x)]\) 都滿，則隨便選擇其中一個（設為 y），將其踢出，插入 x
   3. 重復上述過程，插入元素 y（就是之前被踢出的倒霉蛋）
   4. 如果插入時，踢出次數(shù)過多，則說明哈希桶滿了。則進行擴容，ReHash 后，再次插入
3. 查詢元素 x：
   1. 讀取 \(T_1[h_1(x)]、T_2[h_2(x)]\) 和 x 比對即可

變種

布谷鳥哈希可以有很多變種，比如：

1. 使用兩個哈希函數(shù)和一個哈希桶
2. 使用兩個哈希函數(shù)和四路哈希桶

參考資料

1. OT（Oblivious Transfer，不經(jīng)意傳輸）協(xié)議詳解
2. 混淆電路介紹（二）邏輯電路
3. 混淆電路介紹（三）混淆電路原理
4. 《深入淺出隱私計算：技術解析與應用實踐》
5. 安全多方計算（5）：隱私集合求交方案匯總分析
6. 隱私計算關鍵技術：隱私集合求交（PSI）原理介紹
7. https://github.com/delta-mpc/python-psi/blob/master/README_zh.md
8. OPRF 原理
9. 布谷鳥哈希和布谷鳥過濾器