安全多方計算及其擴展問題的研究.pdf

1、安全多方計算是分布式系統(tǒng)和密碼學(xué)及其應(yīng)用的研究基礎(chǔ)，幾乎所有的密碼學(xué)裝置（如加密、認(rèn)證、協(xié)商、簽名等）和分布式場景（如電子投票、電子拍賣、隱私信息檢索、隱私保護數(shù)據(jù)挖掘等）都可視為安全多方計算的特例。在安全多方計算中，擁有隱私信息的兩個或多個參與方想要聯(lián)合完成由他們的隱私信息所決定的某種計算。該計算不僅要保證各方都能夠得到正確的輸出（正確性），而且還要保證任何一方都得不到除了自己的合理輸出之外的任何信息（安全性）。
　　 本文主

2、要討論了映射比較問題、數(shù)據(jù)比較問題和分布式線性代數(shù)問題這三類具體的安全多方計算問題，提出了安全多方計算的一個擴展問題（即代理多方計算問題）并作了進一步的相關(guān)的研究。本論文的創(chuàng)新工作如下：
　　 （1）提出了一個新的安全雙方計算問題，即映射相等問題（在保護隱私的情況下判斷兩個映射是否相等）。利用全變換半群基礎(chǔ)理論作為基本的分析工具，將可交換的確定型加密體制作為基本的密碼學(xué)原語，構(gòu)建了求解映射相等問題的安全計算協(xié)議。由此看出全變換半

3、群基礎(chǔ)理論在安全計算協(xié)議的研究中有一定的應(yīng)用，進一步的，本論文在數(shù)學(xué)意義下對全變換半群基礎(chǔ)理論作了一些研究：提出了全變換半群的一類子半群，即保E-序全變換半群，并對有限的情形研究了此類半群的正則性和Green關(guān)系。另外，考慮了映射相等問題的特殊問題，即變換相等問題（在保護隱私的情況下判斷兩個變換是否相等），并分別將健忘傳輸協(xié)議和同態(tài)加密體制作為基本的密碼學(xué)原語，構(gòu)建了此問題的兩個解決方案。
　　 （2）Yao氏百萬富翁問題（在保

4、護隱私的情況下比較兩個整數(shù)的大?。┖蛷V義百萬富翁問題（在保護隱私的情況下比較兩個實數(shù)的大?。┦莾蓚€主要的安全雙方計算問題。最近，解決這兩個問題的對稱密碼解分別被提出：通過構(gòu)建集合包含問題的一個對稱密碼解并將其作為基本的構(gòu)建模塊，提出了Yao氏百萬富翁問題的一個對稱密碼解；通過構(gòu)建成員判定問題的一個對稱密碼解并將其作為基本的構(gòu)建模塊，提出了廣義百萬富翁問題的一個對稱密碼解。本論文對上述對稱密碼解進行了分析，證明了集合包含問題的對稱密碼解和

5、成員判定問題的對稱密碼解都是不完善的（即嚴(yán)格執(zhí)行協(xié)議之后，可能會輸出錯誤的判斷結(jié)果），從而說明了Yao氏百萬富翁問題的對稱密碼解和廣義百萬富翁問題的對稱密碼解都是不完善的（即嚴(yán)格執(zhí)行協(xié)議之后，可能會輸出錯誤的比較結(jié)果）。將語義安全的同態(tài)加密體制作為基本的密碼學(xué)原語，分別構(gòu)建了求解集合包含問題（從而求解Yao氏百萬富翁問題）和求解廣義百萬富翁問題的解決方案。
　　 （3）研究了兩個分布式線性代數(shù)問題：（3-1）提出了一個新的安全多

6、方計算問題，即向量組秩和極大線性無關(guān)組問題（在保護隱私的情況下計算向量組的秩和全部極大線性無關(guān)組），并分別將健忘傳輸協(xié)議和同態(tài)加密體制作為基本的密碼學(xué)原語，構(gòu)建了此問題的兩個解決方案；（3-2）研究了仿射子空間交問題（在保護隱私的情況下計算有限域F上的兩個仿射子空間的交），并將健忘傳輸協(xié)議和同態(tài)加密體制作為基本的密碼學(xué)原語，構(gòu)建了此問題的一個解決方案。
　　 （4）提出了安全多方計算的一個擴展問題，即代理多方計算問題（僅涉及兩方

7、時稱為代理雙方計算問題）：在安全多方計算的一次執(zhí)行中，每個參與者都可以在不不失隱私性的情況下將其計算能力委托給它的代理人，從而達到安全計算的目的。定義了代理多方計算的相關(guān)模型，特別地，在半誠實攻擊者模型下定義了代理多方計算的安全模型。作為具體實例，研究了兩個代理分布式線性代數(shù)問題：（4-1）將安全多方向量組秩和極大線性無關(guān)組協(xié)議（例如在（3-1）中構(gòu)建的協(xié)議）作為誘導(dǎo)協(xié)議，構(gòu)建了求解向量組秩和極大線性無關(guān)組問題的Input（ε）-Out

8、put（1）安全的代理多方計算協(xié)議，其中ε=1/|F|-1且|F|表示有限域的階；（4-2）將安全雙方仿射交協(xié)議（例如在（3-2）中構(gòu)建的協(xié)議）作為誘導(dǎo)協(xié)議，構(gòu)建了求解線性方程組公共解問題（在保護隱私的情況下計算兩個線性方程組的公共解）的Input（ε）-Output（1）安全的代理雙方計算協(xié)議，其中ε≦1/|F|-1。
　　 （5）研究了一類特殊的代理多方計算問題，即帶公共參數(shù)的代理多方計算問題。該模型中，代理多方計算的原始參