安全多方計算底層基本運算研究.pdf

1、安全多方計算(Secure Multi-party Computation，SMPC)是密碼學(xué)領(lǐng)域里一個基礎(chǔ)性研究方向。借助于安全多方計算協(xié)議，網(wǎng)絡(luò)上一些互不信任的實體能夠以自己的秘密信息為輸入共同完成預(yù)定的計算任務(wù)；計算完成以后，所有參與方得到自己期望的輸出，并且不泄漏自己所輸入的秘密信息。廣義上說，任何密碼學(xué)協(xié)議都可以看成是安全多方計算的特殊情況，因而安全多方計算可以視為密碼學(xué)協(xié)議的一般性研究。能夠完成任意計算的通用安全多方計算協(xié)議

2、已經(jīng)存在；這些通用協(xié)議從理論上說明任何多方計算都可以安全實現(xiàn)。但是這些通用協(xié)議的效率都非常低下，因而不可能在實際應(yīng)用中使用。
　　 為了解決這個問題，我們致力于為特定的計算任務(wù)設(shè)計高效的安全多方計算協(xié)議；我們將探討一些典型而重要的基礎(chǔ)問題在安全多方計算背景下的協(xié)議實現(xiàn)及復(fù)雜度，這既是能夠促進安全多方計算協(xié)議實用化的研究，又是一項具有重要理論意義的工作。大致來講，安全多方計算的研究可以分為兩種：基于秘密分享的安全多方計算和基于門限

3、同態(tài)加密的安全多方計算。在基于秘密分享的安全多方計算中，協(xié)議是以線性秘密分享方案為基礎(chǔ)的；協(xié)議的輸入和(絕大部分)中間結(jié)果都被分享在參與方之間，以分享的方式參與運算。而在基于門限同態(tài)加密的安全多方計算中，協(xié)議是以(具有同態(tài)性的)Paillier公鑰加密方案為基礎(chǔ)的；協(xié)議的輸入和(絕大部分)中間結(jié)果都處于加密狀態(tài)，以密文的方式參與運算；而用來解密的私鑰則使用門限秘密分享的方式分享在各參與方之間。我們主要關(guān)注的是基于秘密分享的安全多方計算；

4、我們的工作中所使用的一些方法也可以被應(yīng)用到基于門限同態(tài)加密的安全多方計算中，來設(shè)計一些功能類似的協(xié)議。在基于秘密分享的安全多方計算的研究中，通常假設(shè)所基于的秘密分享方案是建立在素域Zp上的，其中p是一個l比特長的素數(shù)(即l=[log p])。另外，對于域中的元素x=(xl-1，…，x1，x0)∈Zp，我們使用[x]p來表示對x的分享，而用[x]B來表示對x的按位分享(即對x的每個比特的分享)；也就是說，我們有[x]B=([xl-1]p，

5、…，[x1]p，[x0]p)。我們的工作是以安全多方計算領(lǐng)域里一個重要工具“比特分解(Bit-Decomposition)”為基礎(chǔ)的；此工具是由Damgard等人在TCC2006上提出的。給出對x的分享，比特分解能夠輸出對x的按位分享。也就是說，我們有。[x]B←Bit-Decomposition([x]p)。借助于比特分解的幫助，我們可以為許多安全多方計算問題構(gòu)造協(xié)議。具體說，一方面，借助于比特分解我們可以實現(xiàn)一些重要的布爾運算，如求

6、一個分享的秘密值的海明重量或者求兩個分享的秘密值的海明距離、按位異或等。另一方面，一些重要的、相對較復(fù)雜的算術(shù)操作也可以借助于比特分解來實現(xiàn)；下面列舉的，是比特分解的4個主要應(yīng)用：⑴比較分享的秘密值(Comparing Shared Values)，即在分享狀態(tài)下，比較a、b的大小。⑵測試分享的秘密值是否相等(Testing the Equality of Shared Values)，即在分享狀態(tài)下，測試a、b是否相等。⑶公開模歸約(

7、Public Modulo Reduction)；[x mod m]p←Public-Modulo-Reduction([x]p，m)。⑷秘密求冪(Private Exponentiation)，[xα mod p]p←Private-Exponentiation([x]p，[α]p)。借助于比特分解，我們可以得到這些問題的輸入的按位分享，然后我們就可以使用“分而治之”技術(shù)來解決這些問題。但是，有一個嚴重的問題是，比特分解的復(fù)雜度較高。

8、具體說，比特分解的漸進交互復(fù)雜度是D(l log l)(l是輸入值的比特長度)，高于線性，這就使得所有借助于比特分解來實現(xiàn)的協(xié)議的交互復(fù)雜度都是高于線性的。在最近的一項工作中，Nishide等人為比特分解的其中兩個重要應(yīng)用，大小比較和相等測試，設(shè)計了避免使用比特分解來實現(xiàn)的協(xié)議；這兩個協(xié)議的主要優(yōu)勢是其交互復(fù)雜度被降到了線性(即O(l)。那么，自然就出現(xiàn)一個公開問題：對于比特分解的另外兩個重要應(yīng)用，公開模歸約和秘密求冪，是否可以得到類似

9、的結(jié)論?在本文中，我們解決了此公開問題；我們證明，公開模歸約和秘密求冪都可以避免使用比特分解來實現(xiàn)，而且協(xié)議的交互復(fù)雜度都可以被降到線性。
　　 為了解決公開模歸約問題，我們首先給出了對比特分解的一個擴展。此一擴展包含兩個協(xié)議：m進制數(shù)位分解和m進制數(shù)位一比特.分解。輸入一個秘密值x的分享，我們的m進制數(shù)位分解能夠輸出對x的所有m進制位的分享；而我們的數(shù)位一比特.分解則能夠輸出對x的所有m進制位的按位分享。而我們的線性公開模歸約

10、協(xié)議則基于以下事實：給出x的m進制形式，其中的最低m進制位的值就是(x mod m)。也就是說，要解決公開模歸約問題(即已知[x]p和m，求[x mod m]p)，我們只需提取x的最低m進制位；這正是我們所設(shè)計的避免使用比特分解的、具有線性交互復(fù)雜度的公開模歸約協(xié)議所采取的做法。所以公開模歸約協(xié)議可以看作是數(shù)位分解協(xié)議的一個簡化。進一步地，我們還將前述的(對比特分解的)擴展進一步擴展到混合進制情形；而且更重要的是，作為對這個“進一步擴展