高效安全兩方計算基礎(chǔ)理論及關(guān)鍵技術(shù)研究.pdf

1、近年來，隨著計算機網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，以及云計算、大數(shù)據(jù)、物聯(lián)網(wǎng)等新興技術(shù)的廣泛應(yīng)用，網(wǎng)絡(luò)安全日益成為國家、政府、個人關(guān)注的熱門話題。鑒于當下國內(nèi)外各類隱私泄露事件的出現(xiàn)，人們的數(shù)據(jù)隱私保護意識日益增強，數(shù)據(jù)安全已成為全球網(wǎng)絡(luò)化進程中必須解決的問題。值得慶幸的是，密碼學(xué)為數(shù)據(jù)保護提供了豐富、強有力的手段，除機密性、隱私性外也涵蓋了諸如完整性、認證性等安全因素。因此，密碼學(xué)在保護網(wǎng)絡(luò)世界的數(shù)據(jù)安全中必然起到不可替代的作用。
　　安全

2、多方計算(SecureMulti-PartyComputation，SMPC)是現(xiàn)代密碼學(xué)領(lǐng)域的一個重要理論基礎(chǔ)和研究分支，其考慮的是分布式計算場景下的安全計算問題。分布式計算涉及到許多獨立而又相互連接的計算設(shè)備，他們希望共同執(zhí)行某些任務(wù)的計算。安全多方計算的目標就是使得參與方能夠以一種“安全”的方式執(zhí)行這樣的分布式計算。這里對于安全的理解，最直觀的就是保護各個參與方的輸入隱私性以及輸出正確性。其中，隱私性意味著每個參與方通過自己得到的

3、輸出以及自己的輸入信息，不能推測出其他人的任何輸入信息。而輸出正確性則保證了任務(wù)是被正確計算的。就計算任務(wù)而言，安全多方計算既包括如投幣、廣播等簡單任務(wù)，也包括如電子投票、電子拍賣、匿名交易等復(fù)雜的實際應(yīng)用問題。事實上，安全多方計算可視為一般密碼學(xué)協(xié)議的研究，任何密碼學(xué)協(xié)議都可以包括在安全多方計算的理論模型之中。由此可見，對于安全多方計算的深入研究，無論從基礎(chǔ)理論，亦或應(yīng)用協(xié)議等，都能極大地促進密碼學(xué)的發(fā)展。
　　從1982年姚期

4、智先生提出百萬富翁問題至今，安全多方計算的發(fā)展經(jīng)歷了興盛、平靜、再興盛這樣一個發(fā)展歷程。早期的研究主要集中于安全多方計算的可行性理論研究，密碼學(xué)者們給出了許多優(yōu)美的理論成果，表明任意的分布式計算任務(wù)在一定條件下均可以實現(xiàn)安全計算。這一時期，關(guān)于安全模型、形式化證明方法、通用協(xié)議構(gòu)造的研究在理論上逐步完善，但這些理論成果距離實用相距甚遠。近十年以來，安全多方計算迎來了又一個春天。主要表現(xiàn)在以下兩個方面:其一，實用化安全多方計算協(xié)議設(shè)計的進

5、展，使人們看到了安全多方計算應(yīng)用于解決實際問題的希望,因而引起較為廣泛的關(guān)注;其二,云計算環(huán)境為安全多方計算應(yīng)用于隱私保護下的數(shù)據(jù)處理提供了應(yīng)用背景。當前安全多方計算的研究主要包括其自身的基礎(chǔ)理論研究、高效協(xié)議的構(gòu)造以及在其他學(xué)科領(lǐng)域的交叉應(yīng)用研究。
　　本文主要研究高效安全兩方計算(SecureTwo-PartyComputation，STPC)相關(guān)基礎(chǔ)理論以及應(yīng)用。安全兩方計算是多方計算的一種特殊情況，其只包含兩個參與方，較之

6、于多方計算存在固有的優(yōu)勢，最主要的就是體現(xiàn)在高效性上。此外，現(xiàn)實世界中的諸多應(yīng)用僅涉及兩個實體，安全兩方計算能更好地運用到這些應(yīng)用中去。鑒于越來越多的人對于使用安全兩方計算來解決實際問題有著濃厚的興趣，我們的研究核心就是如何設(shè)計真正高效的安全兩方協(xié)議，從而加快安全多方計算從理論走向?qū)嵺`的步伐。當然，本文的研究屬于密碼學(xué)基礎(chǔ)理論研究，我們關(guān)心的是所設(shè)計的密碼協(xié)議能夠滿足的密碼學(xué)安全特性以及實現(xiàn)上的理論可行性，為實用協(xié)議的設(shè)計與實現(xiàn)奠定理論

7、基礎(chǔ)。我們不關(guān)心這些協(xié)議的具體實現(xiàn)以及部署，而注重嚴格的安全性證明，即在相應(yīng)的安全模型下給出形式化的安全性證明，這也是密碼學(xué)中可證明安全的基本要求。我們的研究包括安全兩方計算基礎(chǔ)協(xié)議構(gòu)造、安全兩方計算通用協(xié)議構(gòu)造、云輔助安全兩方計算協(xié)議構(gòu)造以及針對具體應(yīng)用的安全兩方計算協(xié)議構(gòu)造。在安全多方計算基礎(chǔ)工具方面，主要研究茫然傳輸協(xié)議(ObliviousTransfer,OT)在標準惡意敵手模型下的高效構(gòu)造;在針對任意功能函數(shù)(Function

8、ality)的通用協(xié)議構(gòu)造中，主要研究基于Yao混亂電路的兩方安全計算協(xié)議與cut-and-choose技術(shù)的結(jié)合，從而抵抗惡意敵手攻擊;在新型安全計算中，主要研究云輔助安全兩方計算的安全模型以及協(xié)議構(gòu)造;在具體應(yīng)用方面，主要針對隱私保護的模式匹配問題，研究高效安全的模式匹配協(xié)議。具體地，本文的研究內(nèi)容主要包括以下四個方面:
　　1.茫然傳輸協(xié)議是安全多方計算以及密碼學(xué)領(lǐng)域的基礎(chǔ)原語之一，被廣泛應(yīng)用在許多密碼協(xié)議中。傳統(tǒng)的1-ou

9、t-of-2茫然傳輸協(xié)議(OT12)涉及發(fā)送方和接收方，其中發(fā)送方持有一對秘密信息，接收方期望選擇其中之一。安全性要求發(fā)送方不知道接收方的選擇比特，且接收方僅獲得渴望得到的一個信息。推及一般情況，k-out-of-n茫然傳輸協(xié)議(OTkn)則意味著接收方希望秘密地從接收方的n個消息中選擇k個（當k=1時，即為OT1n）。對于茫然傳輸協(xié)議的研究主要在效率以及安全性。鑒于茫然傳輸協(xié)議被廣泛用作其他密碼協(xié)議的子協(xié)議，強安全性要求始終是研究的重

10、點。本文在惡意敵手模型下，首次給出可以實現(xiàn)全模擬的OT1n協(xié)議，所構(gòu)造的協(xié)議基于標準DDH（DecisionalDiffie-Hellman）假設(shè)，且具有常數(shù)輪數(shù)，通信復(fù)雜度、計算復(fù)雜度僅與n線性相關(guān)。
　　2.基于Yao混亂電路的通用兩方安全計算協(xié)議最早僅在半誠實敵手模型下是安全的?？紤]惡意敵手情況，雖然理論上有一個很完美的GMW編譯器，能將一個半誠實安全的協(xié)議轉(zhuǎn)變成一個抗惡意敵手的協(xié)議，但是其效率是難以忍受的。與GMW不同的，

11、cut-and-choose技術(shù)可以避免使用復(fù)雜的零知識證明方法，構(gòu)造更為高效的抵抗惡意敵手的通用兩方安全計算協(xié)議。將cut-and-choose技術(shù)與Yao混亂電路結(jié)合，在這種新框架下，各種新的問題也應(yīng)運而生。為了解決這些新問題，傳統(tǒng)的密碼學(xué)工具難以適用，這必然也催生出各種新型的密碼學(xué)原語。本文針對cut-and-choose雙向茫然傳輸協(xié)議(Cut-and-ChooseBilateralObliviousTransfer,CCBOT

12、)這一新型工具，首次在惡意敵手模型下基于標準DDH假設(shè)構(gòu)造了一個安全的cut-and-choose雙向茫然傳輸協(xié)議。該原語能實現(xiàn)混亂電路相關(guān)密鑰一次性傳輸，因而可以顯著提高通用兩方安全計算協(xié)議的輪復(fù)雜度。本文提出的協(xié)議新構(gòu)造，避免適用cut-and-choose技術(shù)以及承諾方案，輪數(shù)、通信量以及計算量均達到常數(shù)級別。
　　3.云計算的興起給數(shù)據(jù)處理帶來了全新的形式，其龐大的存儲和計算資源使得計算外包成為一種趨勢。云輔助安全多方計算

13、考慮在安全多方計算場景中增加一（或多）個沒有輸入和輸出的云服務(wù)器，他們承擔其他參與方的部分計算任務(wù)，協(xié)助協(xié)議的完成。通過這種方式，參與方實體的計算量會大大減少，協(xié)議也變得更加高效。本文主要研究云輔助安全兩方計算的安全模型以及協(xié)議的構(gòu)造，針對OTkn協(xié)議，首次構(gòu)造了云服務(wù)器輔助的OTkn協(xié)議。所構(gòu)造協(xié)議在半誠實云服務(wù)器情況下是安全的，且效率較之于以前的的協(xié)議更高效。
　　4.隱私保護逐漸成為諸多現(xiàn)實應(yīng)用所考慮的核心問題之一，譬如機器

14、學(xué)習(xí)、社交網(wǎng)絡(luò)等。這些應(yīng)用所涉及到的基本算法或協(xié)議大多數(shù)都可以使用安全兩方計算來描述。本文主要研究隱私保護的模式匹配協(xié)議。該協(xié)議涉及兩個參與方，一方持有一個與匹配的模式，一方持有文檔，協(xié)議的目的是返回成功匹配的結(jié)果，且不泄露其他任何信息。精確模式匹配的另一個變種為近似模式匹配問題，即要求兩個相似的模式能夠匹配成功，其被廣泛應(yīng)用與基因匹配、人臉識別、音樂檢索等問題中。本文在半誠實敵手模型下設(shè)計了一個安全的精確模式匹配協(xié)議，主要基于秘密分享