安全多方計算(1):不經意傳輸協議

一、前言

在安全多方計算系列的首篇文章（安全多方計算之前世今生）中，我們提到了百萬富翁問題，并提供了百萬富翁問題的通俗解法，該通俗解法可按圖1簡單回顧。

圖1 百萬富翁問題通俗解法

百萬富翁問題通俗解法場景中，我們可以將Alice和Bob的訴求總結如下：

Alice：有9個裝有物品的箱子，Bob只能打開其中一個箱子看到物品，看不到其他箱子內的物品。

Bob：不希望Alice知道自己打開的是哪個箱子。

百萬富翁問題通俗解法可以通過密碼學中的n選1的不經意傳輸協（Oblivious Transfer，OT）議完美解決。

通過百萬富翁問題通俗解法場景描述，對OT協議解決的問題可抽象為：Alice擁有n條消息{m₁,…,m_n}，Bob想知道其中一條消息m_i；通過執行OT協議，Bob可以正確獲得想要知道的消息m_i，無法獲得其它n-1條消息，而Alice無法知道Bob獲得的是哪條消息。

OT協議按研究類別區分，可以分為以下3種OT協議：

• 2選1的OT協議（2條消息中正確解密1條）
• n選1的OT協議（n條消息中正確解密1條）
• OT擴展協議（n條消息中正確解密m條，m<n）

受篇幅所限，本文僅介紹2選1與n選1的OT協議，OT擴展協議則在后續系列文章中進行介紹。

二、利用RSA加密實現n選1的OT協議

自1981年提出以來，OT協議有多種多樣的實現形式，其中最容易理解的是基于RSA公鑰算法實現的n選1的OT協議[1]。

2.1 RSA加解密過程簡介

此處不講解RSA原理，只介紹RSA加解密過程和用到的參數，便于密碼學知識儲備不足的讀者理解后面的OT協議。

RSA密鑰參數：N=p*q，L=(p-1)*(q-1)其中p和q為大素數。

RSA公私鑰對：生成d和e，滿足d與L互質，e與L互質，且d*e mod L=1，則令（d，N）為公鑰，e為私鑰。

則RSA算法對明文m（m為大整數）的加解密過程如圖2所示。

圖2 RSA算法加解密計算過程

2.2 RSA實現n選1的OT協議過程描述

基于RSA公鑰算法實現的n選1的OT協議執行過程如圖3所示。

dqsx

圖3 基于RSA公鑰算法實現n選1的OT協議執行過程

協議執行過程分為4個步驟：

1. Alice有n條消息，則產生n個RSA公私鑰對，并將n個私鑰保留，n個公鑰發送給Bob。
2. Bob隨機產生一個大整數key，假定Bob想要獲得第t條消息，則Bob用收到的第t個RSA公鑰加密大整數key，加密計算結果為s，Bob將s發送給Alice。
3. Alice用保留的n個RSA私鑰，依次解密s，獲得n個解密結果，依次為{key₁,key₂,…,key_t,…,key_n}；利用對稱加密算法，利用key₁~key_n，加密對應的消息m₁~m_n，得到密文消息M₁~M_n，將M₁~M_n發送給Bob。
4. Bob利用自己掌握的大整數key作為密鑰，對第t條密文M_t進行對稱解密，則得到想要的第t條原始明文消息m_t。

2.3 n選1的OT協議解決百萬富翁問題

將圖1中的百萬富翁問題和圖3中的n選1的OT協議結合，我們可以對圖1中的操作步驟做如圖4的改造：

Step1：Alice構造9條明文消息，序號<x，消息為“0”；否則消息為“1”。

Step2：Alice與Bob執行9選1的OT協議，解密第7條消息，看到0，y<x；看到1，y≥x。

圖4 基于n選1的OT協議實現百萬富翁問題

2.4 協議分析

該協議執行過程可以滿足OT協議中Alice和Bob的核心訴求，關鍵在于第2步和第3步。

第3步中，Alice利用n個私鑰逐個嘗試解密s，得到key₁~key_n，由于s是由Bob利用第t個公鑰加密整數key計算得到的，因此只有key_t=key，但對于Alice來說，key₁~key_n都是大整數，根本無法區分哪個才是Bob掌握的key，實現了Bob的訴求，即Alice無法知道Bob選擇的是哪條消息。

對于Bob來說，拿到了n個密文消息M₁~M_n，但是自己只有一個key，此key只能解密消息M_t，對于其他n-1條消息則無法解密，實現了Alice的訴求，即Bob只能正確得要Bob想要得到1條消息，無法正確得到其他n-1條消息。

如果n=2，則該n選1的OT協議就退化成了2選1的OT協議。

雖然基于RSA實現的n選1的OT協議簡單易懂，但是卻存在如下缺陷：

• key為0或1時，Alice的訴求無法保證。Bob如果將key指定為0或1，則根據圖2中RSA的加解密計算方法，無論私鑰e是否正確，解密后的m₀=m均成立，意味著第3步中，Alice強行解密s得到的key₁~key_n均等于key，則Bob可以解密所有的消息，獲得所有的明文m₁~m_n。
• 協議計算效率有待優化。第1步Alice需要產生n個RSA公私鑰對，而RSA公私鑰對的產生比較耗時。

為了提高安全性和計算效率，還有基于其他密碼學方法的OT協議，如基于離散對數的OT協議，將在本文第四節和第五節中進行介紹。（如果您僅希望簡單了解OT協議的原理和能解決的問題，則讀到此處足矣，本文后面的內容適合有一定密碼學基礎讀者。）

三、基于離散對數實現2選1的OT協議

為了優化OT協議計算效率和安全性，學者一般對2選1的OT協議和n選1的OT協議分開進行研究。對于2選1的OT協議，Tung Chou[2]于2015年基于離散對數問題，在DH密鑰協商協議的基礎上設計的2選1的OT協議，被認為是一個簡單清晰的2選1的OT協議。

3.1 離散對數簡介

離散對數問題通俗理解：有限域F_p^*（p為大素數，F_p^*中元素共p-1個整數，取值1~p-1）上大整數的冪乘取模容易計算（a^b mod p=>c，a、b∈F_p^*），而對數計算困難( log _a c=>b)。

3.2 離散對數實現2選1的OT協議過程描述

基于離散對數實現2選1的OT協議執行過程如圖5所示。

圖5 離散對數實現2選1的OT協議執行過程

協議執行過程分為4個步驟：

• Alice有消息m₀、m₁∈F_p^*，則Alice挑選g、a∈F_p^*，并計算A=g^amod p，將A、g、p發送給Bob。
• Bob想要第σ條消息（σ=0或1），Bob挑選b∈F_p^*，并計算B=A^σ*g^b mod p，將B發送給Alice。
• Alice利用a、A、B，按照圖4中的步驟3計算C₀和C₁的值，然后用C₀為密鑰，對稱加密m₀；用C₁為密鑰，對稱加密m₁。將加密后的密文M₀和M₁傳遞給Bob。
• Bob利用A和b計算解密密鑰g^ab mod p，對稱解密對應的密文后拿到想要的正確消息。

3.3 協議分析

該協議的核心步驟是步驟2和步驟3，對這兩步中的參數B、C₀、C1進行展開，展開后如圖6所示。

圖6 2選1的OT協議部分參數展開

從圖6的展開式可知，無論σ=0還是σ=1，C₀和C₁始終只有一個為g^ab，而另一個對于Bob而言則不可計算（Bob不知道a的值），gab的計算實質上就是DH密鑰協商協議。

對于Alice來說，僅知道B、A、g，不知道b的情況下，由于離散對數問題難解，因此是無法推斷出σ=0還是σ=1。

與2.2的協議相比，該協議不存在Bob選擇特殊的b會導致密文消息M₀和M₁同時正確解密這一缺陷。

四、基于離散對數實現n選1的OT協議

章節將以Wen-Guey Tzeng[3]提出的高效n選1的OT協議為例，講解如何基于離散對數實現基本的n選1的OT協議。

4.1 離散對數實現n選1的OT協議過程描述

基于離散對數實現n選1的OT協議執行過程如圖7所示。

圖7 離散對數實現n選1的OT協議執行過程

協議執行過程分為4個步驟：

• Alice有n條消息{m₁,…,m_n}，m_i∈G(G代表素數域F_p^*)，挑選G的兩個生成元g和h，將g、h、p發送給Bob。
• 假定Bob想獲得第t條消息，則Bob隨機選擇大整數r∈G，并計算y=g^r*h^tmod p，將y發送給Alice。
• Alice利用y、g、h，分別對n條消息，重復執行圖6中左下角的計算步驟，每一次執行都會隨機選擇大整數k_i∈G，并結合消息m_i計算a_i和b_i。然后將n組（a_i，b_i）發送給Bob。
• Bob拿到n組（a_i，b_i）后，利用掌握的大整數r，計算想要的第t條消息m_t=b_t∕(a_t)^r。

4.2 協議分析

對于第4步Bob的操作，我們把消息m_t泛指為m_x，則對m_x的計算公式展開后如圖8所示。

圖8 消息mx的計算公式展開

從圖8可以看出，要想獲得消息m_x，要么令x=t，此時消息為Bob想要獲得的消息；要么計算出h^(t-x)*kx，由于k_x是Alice的秘密數字，因此保證了Bob不可能正確解密除消息m_t之外的其余n-1條消息。

對于Alice來說，雖然知道y、g、h，但是不知道r的情況下，由于離散對數問題難解，因此是無法推斷出t的正確值。

與2.2的協議相比，該協議不存在Bob選擇特殊的r會導致n條消息同時正確解密這一缺陷，同時也不存在需要產生n對公私鑰這一耗時操作。

五、總結

本文介紹了OT協議和3個基于密碼學實現的OT協議實例，并結合百萬富翁問題的通俗解法看到了OT協議的應用實例，這樣的實例很難看出OT協議的重要性。

其實OT協議是安全多方計算中很重要的一個協議，在安全多方計算系列的首篇文章（安全多方計算之前世今生）中，我們提到，安全多方計算的通用技術路線可以用混淆電路解決，而混淆電路的構建離不開OT協議。因此，下期文章將會講解如何通過OT協議實現混淆電路，以及如何實現基于混淆電路的通用安全多方計算路線。

參考文獻

[1] https://en.wikipedia.org/wiki/Oblivious_transfer

[2] Chou T , Orlandi C . The Simplest Protocol forOblivious Transfer[C]// International Conference on Cryptology and InformationSecurity in Latin America. Springer International Publishing, 2015.

[3] Tzeng W G . Efficient 1-out-of-noblivious transfer schemes with universally usable parameters[J]. IEEETransactions on Computers, 2004, 53(2):p.232-240.