發(fā)布時(shí)間：2018-04-05 05:18

  本文選題：安全兩方計(jì)算　切入點(diǎn)：茫然傳輸　出處：《山東大學(xué)》2017年博士論文

【摘要】：近年來,隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的不斷發(fā)展,以及云計(jì)算、大數(shù)據(jù)、物聯(lián)網(wǎng)等新興技術(shù)的廣泛應(yīng)用,網(wǎng)絡(luò)安全日益成為國家、政府、個(gè)人關(guān)注的熱門話題。鑒于當(dāng)下國內(nèi)外各類隱私泄露事件的出現(xiàn),人們的數(shù)據(jù)隱私保護(hù)意識(shí)日益增強(qiáng),數(shù)據(jù)安全已成為全球網(wǎng)絡(luò)化進(jìn)程中必須解決的問題。值得慶幸的是,密碼學(xué)為數(shù)據(jù)保護(hù)提供了豐富、強(qiáng)有力的手段,除機(jī)密性、隱私性外也涵蓋了諸如完整性、認(rèn)證性等安全因素。因此,密碼學(xué)在保護(hù)網(wǎng)絡(luò)世界的數(shù)據(jù)安全中必然起到不可替代的作用。安全多方計(jì)算(Secure Multi-Party Computation,SMPC)是現(xiàn)代密碼學(xué)領(lǐng)域的一個(gè)重要理論基礎(chǔ)和研究分支,其考慮的是分布式計(jì)算場景下的安全計(jì)算問題。分布式計(jì)算涉及到許多獨(dú)立而又相互連接的計(jì)算設(shè)備,他們希望共同執(zhí)行某些任務(wù)的計(jì)算。安全多方計(jì)算的目標(biāo)就是使得參與方能夠以一種"安全"的方式執(zhí)行這樣的分布式計(jì)算。這里對于安全的理解,最直觀的就是保護(hù)各個(gè)參與方的輸入隱私性以及輸出正確性。其中,隱私性意味著每個(gè)參與方通過自己得到的輸出以及自己的輸入信息,不能推測出其他人的任何輸入信息。而輸出正確性則保證了任務(wù)是被正確計(jì)算的。就計(jì)算任務(wù)而言,安全多方計(jì)算既包括如投幣、廣播等簡單任務(wù),也包括如電子投票、電子拍賣、匿名交易等復(fù)雜的實(shí)際應(yīng)用問題。事實(shí)上,安全多方計(jì)算可視為一般密碼學(xué)協(xié)議的研究,任何密碼學(xué)協(xié)議都可以包括在安全多方計(jì)算的理論模型之中。由此可見,對于安全多方計(jì)算的深入研究,無論從基礎(chǔ)理論,亦或應(yīng)用協(xié)議等,都能極大地促進(jìn)密碼學(xué)的發(fā)展。從1982年姚期智先生提出百萬富翁問題至今,安全多方計(jì)算的發(fā)展經(jīng)歷了興盛、平靜、再興盛這樣一個(gè)發(fā)展歷程。早期的研究主要集中于安全多方計(jì)算的可行性理論研究,密碼學(xué)者們給出了許多優(yōu)美的理論成果,表明任意的分布式計(jì)算任務(wù)在一定條件下均可以實(shí)現(xiàn)安全計(jì)算。這一時(shí)期,關(guān)于安全模型、形式化證明方法、通用協(xié)議構(gòu)造的研究在理論上逐步完善,但這些理論成果距離實(shí)用相距甚遠(yuǎn)。近十年以來,安全多方計(jì)算迎來了又一個(gè)春天。主要表現(xiàn)在以下兩個(gè)方面:其一,實(shí)用化安全多方計(jì)算協(xié)議設(shè)計(jì)的進(jìn)展,使人們看到了安全多方計(jì)算應(yīng)用于解決實(shí)際問題的希望,因而引起較為廣泛的關(guān)注;其二,云計(jì)算環(huán)境為安全多方計(jì)算應(yīng)用于隱私保護(hù)下的數(shù)據(jù)處理提供了應(yīng)用背景。當(dāng)前安全多方計(jì)算的研究主要包括其自身的基礎(chǔ)理論研究、高效協(xié)議的構(gòu)造以及在其他學(xué)科領(lǐng)域的交叉應(yīng)用研究。本文主要研究高效安全兩方計(jì)算(Secure Two-Party Computation,STPC)相關(guān)基礎(chǔ)理論以及應(yīng)用。安全兩方計(jì)算是多方計(jì)算的一種特殊情況,其只包含兩個(gè)參與方,較之于多方計(jì)算存在固有的優(yōu)勢,最主要的就是體現(xiàn)在高效性上。此外,現(xiàn)實(shí)世界中的諸多應(yīng)用僅涉及兩個(gè)實(shí)體,安全兩方計(jì)算能更好地運(yùn)用到這些應(yīng)用中去。鑒于越來越多的人對于使用安全兩方計(jì)算來解決實(shí)際問題有著濃厚的興趣,我們的研究核心就是如何設(shè)計(jì)真正高效的安全兩方協(xié)議,從而加快安全多方計(jì)算從理論走向?qū)嵺`的步伐。當(dāng)然,本文的研究屬于密碼學(xué)基礎(chǔ)理論研究,我們關(guān)心的是所設(shè)計(jì)的密碼協(xié)議能夠滿足的密碼學(xué)安全特性以及實(shí)現(xiàn)上的理論可行性,為實(shí)用協(xié)議的設(shè)計(jì)與實(shí)現(xiàn)奠定理論基礎(chǔ)。我們不關(guān)心這些協(xié)議的具體實(shí)現(xiàn)以及部署,而注重嚴(yán)格的安全性證明,即在相應(yīng)的安全模型下給出形式化的安全性證明,這也是密碼學(xué)中可證明安全的基本要求。我們的研究包括安全兩方計(jì)算基礎(chǔ)協(xié)議構(gòu)造、安全兩方計(jì)算通用協(xié)議構(gòu)造、云輔助安全兩方計(jì)算協(xié)議構(gòu)造以及針對具體應(yīng)用的安全兩方計(jì)算協(xié)議構(gòu)造。在安全多方計(jì)算基礎(chǔ)工具方面,主要研究茫然傳輸協(xié)議(Oblivious Transfer,OT)在標(biāo)準(zhǔn)惡意敵手模型下的高效構(gòu)造;在針對任意功能函數(shù)(Functionality)的通用協(xié)議構(gòu)造中,主要研究基于Yao混亂電路的兩方安全計(jì)算協(xié)議與cut-and-choose技術(shù)的結(jié)合,從而抵抗惡意敵手攻擊;在新型安全計(jì)算中,主要研究云輔助安全兩方計(jì)算的安全模型以及協(xié)議構(gòu)造;在具體應(yīng)用方面,主要針對隱私保護(hù)的模式匹配問題,研究高效安全的模式匹配協(xié)議。具體地,本文的研究內(nèi)容主要包括以下四個(gè)方面:1.茫然傳輸協(xié)議是安全多方計(jì)算以及密碼學(xué)領(lǐng)域的基礎(chǔ)原語之一,被廣泛應(yīng)用在許多密碼協(xié)議中。傳統(tǒng)的1-out-of-2茫然傳輸協(xié)議(OT21)涉及發(fā)送方和接收方,其中發(fā)送方持有一對秘密信息,接收方期望選擇其中之一。安全性要求發(fā)送方不知道接收方的選擇比特,且接收方僅獲得渴望得到的一個(gè)信息。推及一般情況,k-out-of-n茫然傳輸協(xié)議(OTnk)則意味著接收方希望秘密地從接收方的n個(gè)消息中選擇k個(gè)(當(dāng)k=1時(shí),即為OTn1)。對于茫然傳輸協(xié)議的研究主要在效率以及安全性。鑒于茫然傳輸協(xié)議被廣泛用作其他密碼協(xié)議的子協(xié)議,強(qiáng)安全性要求始終是研究的重點(diǎn)。本文在惡意敵手模型下,首次給出可以實(shí)現(xiàn)全模擬的OTn1協(xié)議,所構(gòu)造的協(xié)議基于標(biāo)準(zhǔn)DDH(Decisional Diffie-Hellman)假設(shè),且具有常數(shù)輪數(shù),通信復(fù)雜度、計(jì)算復(fù)雜度僅與n線性相關(guān)。2.基于Yao混亂電路的通用兩方安全計(jì)算協(xié)議最早僅在半誠實(shí)敵手模型下是安全的�？紤]惡意敵手情況,雖然理論上有一個(gè)很完美的GMW編譯器,能將一個(gè)半誠實(shí)安全的協(xié)議轉(zhuǎn)變成一個(gè)抗惡意敵手的協(xié)議,但是其效率是難以忍受的。與GMW不同的,cut-and-choose技術(shù)可以避免使用復(fù)雜的零知識(shí)證明方法,構(gòu)造更為高效的抵抗惡意敵手的通用兩方安全計(jì)算協(xié)議。將cut-and-choose技術(shù)與Yao混亂電路結(jié)合,在這種新框架下,各種新的問題也應(yīng)運(yùn)而生。為了解決這些新問題,傳統(tǒng)的密碼學(xué)工具難以適用,這必然也催生出各種新型的密碼學(xué)原語。本文針對cut-and-choose雙向茫然傳輸協(xié)議(Cut-and-Choose Bilateral Oblivious Transfer,CCBOT)這一新型工具,首次在惡意敵手模型下基于標(biāo)準(zhǔn)DDH假設(shè)構(gòu)造了一個(gè)安全的cut-and-choose雙向茫然傳輸協(xié)議。該原語能實(shí)現(xiàn)混亂電路相關(guān)密鑰一次性傳輸,因而可以顯著提高通用兩方安全計(jì)算協(xié)議的輪復(fù)雜度。本文提出的協(xié)議新構(gòu)造,避免適用cut-and-choose技術(shù)以及承諾方案,輪數(shù)、通信量以及計(jì)算量均達(dá)到常數(shù)級(jí)別。3.云計(jì)算的興起給數(shù)據(jù)處理帶來了全新的形式,其龐大的存儲(chǔ)和計(jì)算資源使得計(jì)算外包成為一種趨勢。云輔助安全多方計(jì)算考慮在安全多方計(jì)算場景中增加一(或多)個(gè)沒有輸入和輸出的云服務(wù)器,他們承擔(dān)其他參與方的部分計(jì)算任務(wù),協(xié)助協(xié)議的完成。通過這種方式,參與方實(shí)體的計(jì)算量會(huì)大大減少,協(xié)議也變得更加高效。本文主要研究云輔助安全兩方計(jì)算的安全模型以及協(xié)議的構(gòu)造,針對OTnk協(xié)議,首次構(gòu)造了云服務(wù)器輔助的OTnk協(xié)議。所構(gòu)造協(xié)議在半誠實(shí)云服務(wù)器情況下是安全的,且效率較之于以前的的協(xié)議更高效。4.隱私保護(hù)逐漸成為諸多現(xiàn)實(shí)應(yīng)用所考慮的核心問題之一,譬如機(jī)器學(xué)習(xí)、社交網(wǎng)絡(luò)等。這些應(yīng)用所涉及到的基本算法或協(xié)議大多數(shù)都可以使用安全兩方計(jì)算來描述。本文主要研究隱私保護(hù)的模式匹配協(xié)議。該協(xié)議涉及兩個(gè)參與方,一方持有一個(gè)與匹配的模式,一方持有文檔,協(xié)議的目的是返回成功匹配的結(jié)果,且不泄露其他任何信息。精確模式匹配的另一個(gè)變種為近似模式匹配問題,即要求兩個(gè)相似的模式能夠匹配成功,其被廣泛應(yīng)用與基因匹配、人臉識(shí)別、音樂檢索等問題中。本文在半誠實(shí)敵手模型下設(shè)計(jì)了一個(gè)安全的精確模式匹配協(xié)議,主要基于秘密分享和茫然傳輸兩個(gè)基本工具。此外,本文將上述協(xié)議在云輔助模型下擴(kuò)展為近視模式匹配協(xié)議,該協(xié)議將大量的計(jì)算任務(wù)外包至云服務(wù)器,協(xié)議效率較之于之前的協(xié)議有很大提升。
[Abstract]:Security Multi - Party Computing ( SMPC ) is an important theoretical foundation and research branch in the field of modern cryptography . This paper mainly focuses on the basic theory of security two - party computing , the construction of efficient protocols and the cross - application research in other disciplines . i.e . , otn1 ) . In order to solve these new problems , this paper presents a new type of secure cut - and - choose technology , which is based on standard DDH . In this paper , the above - mentioned protocol is extended to a near - sightedness pattern matching protocol under the cloud - assisted model , and the protocol packs a large amount of computing tasks to the cloud server , and the protocol efficiency is greatly improved compared with the previous agreement .

【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP309
，

本文編號(hào)：1713375