安全多方計(jì)算底層基本運(yùn)算研究.pdf

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

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

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

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

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

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

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)。借助于比特分解，我們可以得到這些問(wèn)題的輸入的按位分享，然后我們就可以使用“分而治之”技術(shù)來(lái)解決這些問(wèn)題。但是，有一個(gè)嚴(yán)重的問(wèn)題是，比特分解的復(fù)雜度較高。

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

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

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