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

語言: CN / TW / HK

創新中心 王真

專題:安全多方計算 標籤:不經意傳輸

摘要不經意傳輸協議是一種密碼學原語,同時也是安全多方計算中很重要的一個支撐協議,是混淆電路的實現基礎。

一、前言

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

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

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

Alice:有9個裝有物品的箱子,Bob只能開啟其中一個箱子看到物品,看不到其他箱子內的物品。

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

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

通過百萬富翁問題通俗解法場景描述,對OT協議解決的問題可抽象為:Alice擁有n條訊息{m 1 ,…,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所示。

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

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

  • Alice有n條訊息,則產生n個RSA公私鑰對,並將n個私鑰保留,n個公鑰傳送給Bob。

  • Bob隨機產生一個大整數key,假定Bob想要獲得第t條訊息,則Bob用收到的第t個RSA公鑰加密大整數key,加密計算結果為s,Bob將s傳送給Alice。

  • Alice用保留的n個RSA私鑰,依次解密s,獲得n個解密結果,依次為{key 1 ,key 2 ,…,key t ,…,key n };利用對稱加密演算法,利用key 1 ~key n ,加密對應的訊息m 1 ~m n ,得到密文訊息M 1 ~M n ,將M 1 ~M n 傳送給Bob。

  • 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 1 ~key n ,由於s是由Bob利用第t個公鑰加密整數key計算得到的,因此 只有 key t =key ,但對於 Alice 來說, key 1 ~key n 都是大整數,根本無法區分哪個才是 Bob 掌握的 key ,實現了 Bob 的訴求 ,即Alice無法知道Bob選擇的是哪條訊息。

對於 Bob 來說,拿到了 n 個密文訊息 M 1 ~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 0 =m均成立,意味著第3步中,Alice強行解密s得到的key 1 ~key n 均等於key,則Bob可以解密所有的訊息,獲得所有的明文m 1 ~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 0 、m 1 ∈F p * ,則Alice挑選g、a∈F p * ,並計算A=g a mod 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 0 和C 1 的值,然後用C 0 為金鑰,對稱加密m 0 ;用C 1 為金鑰,對稱加密m 1 。將加密後的密文M 0 和M 1 傳遞給Bob。

  • Bob利用A和b計算解密金鑰g ab mod p,對稱解密對應的密文後拿到想要的正確訊息。

3.3 協議分析

該協議的核心步驟是步驟2和步驟3,對這兩步中的引數B、C 0 、C 1 進行展開,展開後如圖6所示。

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

從圖6的展開式可知,無論σ=0還是σ=1,C 0 和C 1 始終只有一個為g ab ,而另一個對於Bob而言則不可計算(Bob不知道a的值),g ab 的計算實質上就是DH金鑰協商協議。

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

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

四、基於離散對數實現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 1 ,…,m n },m i ∈G(G代表素數域F p * ),挑選G的兩個生成元g和h,將g、h、p傳送給Bob。

  • 假定Bob想獲得第t條訊息,則Bob隨機選擇大整數r∈G,並計算y=g r *h t mod 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步Bob的操作,我們把訊息m t 泛指為m x ,則對m x 的計算公式展開後如圖8所示。

圖8 訊息m x 的計算公式展開

從圖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 for Oblivious Transfer[C]// International Conference on Cryptology and Information Security in Latin America. Springer International Publishing, 2015.

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

往期回顧

安全多方計算之前世今生 (https://mp.weixin.qq.com/s/L56ixeedbt1Bo8047pWcuw)