實(shí)用安全兩方計(jì)算理論研究.pdf

1、隨著物聯(lián)網(wǎng)、移動(dòng)計(jì)算、云計(jì)算等技術(shù)的快速興起及迅猛發(fā)展，人們的生活方式正在發(fā)生巨大改變。這些新的數(shù)據(jù)處理技術(shù)為整個(gè)社會(huì)提供了極大的便利。與此同時(shí)，隱私信息和保密數(shù)據(jù)的泄露事件也在頻繁發(fā)生，制約著新型數(shù)據(jù)處理技術(shù)的應(yīng)用和普及。因而，構(gòu)建隱私保護(hù)的數(shù)據(jù)處理方式成為當(dāng)前亟待解決的工作，信息安全的重要性被提上一個(gè)新的高度。密碼學(xué)是信息安全領(lǐng)域的核心技術(shù)，貫穿于信息安全保障的各個(gè)層面，為數(shù)據(jù)的隱私性、完整性和認(rèn)證性等方面提供理論基礎(chǔ)和技術(shù)支撐。<

2、br>　　作為密碼學(xué)領(lǐng)域的重要基礎(chǔ)理論研究，安全多方計(jì)算(Secure Multi-PartyComputation)討論了分布式計(jì)算場(chǎng)景下數(shù)據(jù)擁有者各方以一種安全的方式進(jìn)行合作計(jì)算的問題。簡(jiǎn)單來說，在安全多方計(jì)算場(chǎng)景中，兩個(gè)或多個(gè)參與方持有各自的秘密輸入，想要聯(lián)合計(jì)算關(guān)于這些輸入的某個(gè)功能函數(shù)(Functionality)，其安全性要求每個(gè)參與方除得到其預(yù)定的輸出外不能獲得任何額外信息。研究安全多方計(jì)算促進(jìn)了密碼學(xué)基礎(chǔ)理論的發(fā)展。一方

3、面，構(gòu)造安全多方計(jì)算協(xié)議需要基于很多重要的密碼學(xué)原語，針對(duì)安全多方計(jì)算的研究促進(jìn)了這些底層基本原語的發(fā)展;另一方面，安全多方計(jì)算是密碼協(xié)議的一般性理論研究，為密碼協(xié)議的研究提供理論基礎(chǔ)，推動(dòng)現(xiàn)代密碼學(xué)的進(jìn)步。
　　針對(duì)安全多方計(jì)算的研究，早先的關(guān)注點(diǎn)主要集中于安全多方計(jì)算中安全模型建立、可行性探究以及復(fù)雜性分類等基礎(chǔ)理論方面。近些年，伴隨著計(jì)算能力和通信能力的大幅提升，在安全計(jì)算基礎(chǔ)理論研究持續(xù)多年不衰的基礎(chǔ)上，實(shí)用安全多方計(jì)算又

4、得到更加廣泛的關(guān)注。實(shí)用安全多方計(jì)算主要關(guān)注安全多方計(jì)算通用協(xié)議的效率問題，從協(xié)議的計(jì)算代價(jià)、通信代價(jià)及交互輪數(shù)等方面綜合考慮，研究提高通用協(xié)議效率的方法和技術(shù)。通用協(xié)議指的是可以安全計(jì)算任意功能函數(shù)的一般化協(xié)議。構(gòu)造通用協(xié)議的思想一般是將所要計(jì)算的功能函數(shù)表示成算術(shù)電路或布爾電路，然后再利用秘密共享、同態(tài)加密、不經(jīng)意傳輸和混亂電路等密碼學(xué)工具對(duì)每個(gè)電路門進(jìn)行處理，最終以一種安全的方式完成整個(gè)電路的計(jì)算。
　　安全兩方計(jì)算作為安全

5、多方計(jì)算的特殊情況，刻畫了許多重要的密碼學(xué)任務(wù)，如零知識(shí)證明、不經(jīng)意傳輸、擲幣協(xié)議以及承諾方案等，研究安全兩方計(jì)算具有其特殊的理論價(jià)值;同時(shí)，在安全兩方計(jì)算中，由于參與計(jì)算的實(shí)體為兩方，安全模型中不存在誠(chéng)實(shí)方占大多數(shù)的情況，因此研究安全兩方計(jì)算具有其特有的困難性與特殊性。
　　本文以實(shí)用安全兩方計(jì)算為主要研究?jī)?nèi)容，致力于研究面向?qū)嵱没陌踩珒煞接?jì)算中所涉及的基礎(chǔ)理論。在該研究領(lǐng)域，目前構(gòu)造惡意模型下通用協(xié)議的最高效方法是對(duì)混亂電路

6、采用cut-and-choose技術(shù)。通過該技術(shù)可以構(gòu)造出理想/現(xiàn)實(shí)模擬范例下可證安全的高效通用協(xié)議，達(dá)到現(xiàn)實(shí)中最理想的安全性等級(jí)。但是，其中仍有許多問題沒有很好地解決，比如參與方的輸入一致性問題、不經(jīng)意傳輸?shù)倪x擇性失敗攻擊問題以及兩輸出函數(shù)計(jì)算問題等。本文以上述三個(gè)問題中的其中兩個(gè)為切入點(diǎn)，從兩個(gè)方面對(duì)實(shí)用安全兩方計(jì)算進(jìn)行了深入研究:一方面，本文研究了安全兩方計(jì)算的核心基礎(chǔ)工具——不經(jīng)意傳輸，拓展不經(jīng)意傳輸?shù)墓δ?，提出了兩個(gè)新的密碼學(xué)

7、原語，并利用新原語來降低安全兩方計(jì)算通用協(xié)議的交互輪數(shù)，提高協(xié)議效率;另一方面，本文研究了兩輸出函數(shù)計(jì)算問題，提出了一個(gè)實(shí)現(xiàn)兩輸出函數(shù)安全計(jì)算的最優(yōu)范例，以該范例為基礎(chǔ)可以設(shè)計(jì)具有最優(yōu)錯(cuò)誤概率的高效兩輸出安全計(jì)算協(xié)議。
　　具體來說，本文主要做了以下幾個(gè)方面的工作:
　　研究安全兩方計(jì)算基礎(chǔ)工具
　　本文研究了安全兩方計(jì)算的核心基礎(chǔ)工具——不經(jīng)意傳輸，針對(duì)用來構(gòu)造惡意模型下高效安全協(xié)議的cut-and-choose范例

8、，提出cut-and-choose場(chǎng)景下的兩個(gè)新密碼學(xué)原語——“cut-and-choose逆向不經(jīng)意傳輸”和“cut-and-choose雙向不經(jīng)意傳輸”。這些新原語是基礎(chǔ)性的密碼學(xué)工具，具有密碼學(xué)基礎(chǔ)理論上的重要性。新原語不僅提供了以安全的方式傳輸數(shù)據(jù)的新方法，使參與者能夠在網(wǎng)絡(luò)上安全地完成不同需求的傳輸任務(wù)，而且為提升高層次安全協(xié)議的效率提供底層的理論基礎(chǔ)和技術(shù)支撐。特別地，cut-and-choose雙向不經(jīng)意傳輸是一個(gè)功能強(qiáng)大

9、的基本工具，當(dāng)其應(yīng)用在基于混亂電路和cut-and-choose范例的安全計(jì)算協(xié)議中時(shí)，不僅能用來傳輸混亂電路構(gòu)造方在所有混亂電路中相關(guān)的混亂密鑰，也可以將另一個(gè)參與方相關(guān)的所有數(shù)據(jù)一同傳輸，不再需要多輪交互來完成數(shù)據(jù)的傳輸任務(wù)，進(jìn)而極大簡(jiǎn)化高層安全計(jì)算協(xié)議的框架，大大降低協(xié)議的交互輪數(shù)。
　　對(duì)于本文提出的新密碼學(xué)原語cut-and-choose逆向不經(jīng)意傳輸和cut- and-choose雙向不經(jīng)意傳輸，以及此前研究者提出的c

10、ut-and-choose不經(jīng)意傳輸，除形式化定義其功能函數(shù)外，本文基于同態(tài)加密正式給出相應(yīng)的實(shí)例化構(gòu)造，并基于標(biāo)準(zhǔn)的安全性證明范例——理想/現(xiàn)實(shí)模擬范例，在惡意模型下給出嚴(yán)格的安全性證明，理論上證明這些構(gòu)造達(dá)到現(xiàn)實(shí)中最高的安全等級(jí)。
　　研究?jī)奢敵龊瘮?shù)安全計(jì)算
　　本文研究了安全兩方計(jì)算中的兩輸出函數(shù)計(jì)算問題，期望在cut-and-choose范例下找到能以最優(yōu)錯(cuò)誤概率解決兩輸出函數(shù)計(jì)算問題的方法。Cut-and-choo

11、se技術(shù)能以很高的效率實(shí)現(xiàn)惡意模型下安全的通用協(xié)議構(gòu)造，但其是以一定的錯(cuò)誤概率為代價(jià)的。錯(cuò)誤概率的大小是影響協(xié)議效率的關(guān)鍵因素，實(shí)現(xiàn)錯(cuò)誤概率的最優(yōu)化是實(shí)用安全兩方計(jì)算中的一項(xiàng)重要研究課題。目前已有計(jì)算單輸出函數(shù)最優(yōu)錯(cuò)誤概率的技術(shù)，但對(duì)于兩輸出函數(shù)如何獲得最優(yōu)錯(cuò)誤概率仍是未知。本文首次提出兩輸出函數(shù)計(jì)算的最優(yōu)范例，該范例為設(shè)計(jì)具有最優(yōu)錯(cuò)誤概率的兩輸出函數(shù)安全計(jì)算協(xié)議提供了有效途徑。基于該范例，本文給出兩輸出函數(shù)安全計(jì)算通用協(xié)議的高效構(gòu)造，