整數(shù)上全同態(tài)加密方案分析報告(編輯修改稿)
2025-05-24 07:23 本頁面
【文章內(nèi)容簡介】 么呢？我想應(yīng)該是五花八門的功能，如果想用功能去描述它恐怕是一言難盡，但是如果用布爾電路的大?。╰he size of boolean circuit,即門電路的數(shù)量）來衡量，那么f就能夠被拆解成一些簡單的布爾電路：例如“與”電路、“或”電路、“非”電路。而這些電路是可以組合成任意電路的，也就是說可以表示任意功能的電路。同樣我們也可以選擇用AND電路和XOR電路，因為這兩個電路是具有完備性質(zhì)的，也就是說這兩個電路的組合也可以表出任意功能的電路（而且用這兩個電路來描述更加直觀，它們直接對應(yīng)的算術(shù)運算就是乘法和加法）。顯然AND電路和XOR電路是屬于permitted functions集合里的（為什么？因為AND電路是對應(yīng)的是兩個二進制位相乘，XOR對應(yīng)的是兩個二進制位相加，上述同態(tài)方案肯定能夠正確執(zhí)行這兩個運算，因為就是一次乘法或者一次加法，既然能夠正確執(zhí)行，所以它們就屬于permitted functions集合）。又由于AND電路和XOR電路是完備的，所以任意功能都可以用這兩個電路組合表出，也就是說該同態(tài)方案可以對密文做任意功能的運算，這不就是傳說中的全同態(tài)定義么！任意功能的問題解決了，但是還缺一點：必須是正確的才行。你一陣對密文蹂躪后，如果結(jié)果解密后不是同樣對明文蹂躪的結(jié)果，你有什么感覺？那么上述同態(tài)方案能夠保證計算的正確性么？上面我們已經(jīng)看到由于噪音的存在，該方案只能做有限次的運算，也就是說只能夠?qū)ermitted functions集合里的功能函數(shù)保證是正確的，在此之外保證不了，現(xiàn)在你知道permitted functions集合里有什么東西了吧。那如何能夠保證對密文做任意功能的運算還是正確的呢？前面說過可以通過重加密技術(shù)降低噪音呀！具體如何做呢？很簡單：給AND電路上接一個解密電路，給XOR電路上也接一個解密電路，任何密文在進入AND電路或XOR電路之前，先讓它進入解密電路進行重加密，之后從解密電路里出來的密文就是一個類似于新鮮密文的密文，噪音比進來前降低了，然后再讓這個新的密文進入AND電路或XOR電路，這樣我們就可以對密文正確的做任意功能的計算了！而接了解密電路的AND電路或XOR電路就稱為增強電路?？偨Y(jié)一下：任意函數(shù)功能拿來，先用增強型AND電路和增強型XOR電路表出，這樣就可以對密文做任意功能的計算了，由于是增強型的，我們不再害怕噪音的阻礙，可以無限運算下去。OK，全同態(tài)的藍圖終于在紙上實現(xiàn)了。但是還有一個問題（問題真多，難怪人說科學是由問題產(chǎn)生的，現(xiàn)在我才理解），解密電路是屬于permitted functions集合里的么？可能有人會說，方案中不是有解密電路么，Evaluate應(yīng)該可以運行它吧。另外還有人說，按照上面方法把解密電路表示成增強電路不就行了。別忘了，增強型電路是含有解密電路的，所以這樣說等于由果來推因了。AND電路、XOR電路、解密電路都可看成是“原電路”（這個名字是我自己取的），就是說它們是構(gòu)成任意功能函數(shù)的基石，permitted functions集合里含有它們就完全夠了。前面我們已經(jīng)解釋了AND電路和XOR電路屬于permitted functions集合的原因。唯一缺的就是沒有證實解密電路也在permitted functions集合里。下面就來分析分析。解密電路的深度上面有一個人說對了一半，其實我們可以把解密電路用AND電路和XOR電路表出，計算一下電路的深度（電路的深度代表著運算的次數(shù)），然后再和permitted functions中功能電路所允許的最大深度做個比較，就知道解密電路是否屬于permitted functions集合了。首先來分析permitted functions集合所允許的電路深度。由于permitted functions集合里的任一功能函數(shù)f 都可以用AND電路和XOR電路表出，而AND電路和XOR電路可以看做對輸入的二進制位做乘法和加法，所以f電路的深度可以用輸入位的對稱多項式來衡量（用多項式衡量是因為多項式里恰好是變元的乘法和加法），又由于乘法是噪音的主要來源，所以可以用多項式中乘法次數(shù)來做電路深度的主要衡量指標。有：c* = f ( c1, c2, …， ) = f ( m1+2r1+pq, m2+2r2+pq, …，mn+2rn+pq ) = f ( m1+2r1, m2+2r2, …，mn+2rn ) +p(……)密文c*的噪音為：c* mod p = f ( m1+2r1, m2+2r2, …，mn+2rn ), 要想c*解密正確必須有：f ( m1+2r1, m2+2r2, …，mn+2rn ) p/2, 其中mi+2ri 是密文ci的噪音。不妨令mi+2ri = xi, 且xi B, B是密文ci噪音的上界，則有：f ( x1, x2, …，xn ) p/2。我們的目標是衡量f 的運算次數(shù)d，所以可以用初等對稱多項式來表達f ，有：f ( x1, x2, …，xn ) = x1x2…xd + x1x3…xd + ……；其中d=nf ( x1, x2, …，xn )的每一項就是從n個變元( x1, x2, …，xn )里選取d個變元，因此有C（n, d）個項（C表示組合運算），由C（n, d） nd 得：f ( x1, x2, …，xn ) Bd nd p/2 = d log p / log Bn , 也就是說f 最多運算次數(shù)為 log p / log Bn 。下面再看看解密電路的運算次數(shù)：Dec(c): (c mod p) mod 2=（c – p*「c/p」）mod 2 = Lsb(c) XOR Lsb(「c/p」)仔細端詳解密電路的公式，發(fā)覺其復雜性主要來源是c/p，所以我們主要看c/p所需的運算次數(shù)。c/p=c* p1 , p1是小數(shù)，為了保證c* p1取整之后的的精確度，p1要取log c 位的。例如 12345678 * 和 12345678 * 。那么兩個數(shù)相乘的次數(shù)如何衡量呢？有如下結(jié)論: 乘兩個t位數(shù)相當于加t個數(shù): 輸出位是關(guān)于輸入位的一個2次多項式a3 a2 a1b3 b2 b1a3b1 a2b1 a1b1a3b2 a2b2 a1b2a3b3 a2b3 a1b3 加t個數(shù)可以應(yīng)用“3for2 trick” :3個數(shù)相加得到兩個數(shù)相加，輸出位是關(guān)于輸入位的一個次數(shù)最多為2次的多項式a3 a2 a1b3 b2 b1 c3 c2 c1 a3+b3+c3 a2+b2+c2 a1+b1+c1a3b3+a3c3+b3c3 a2b2+a2c2+b2c2 a1b1+a1c1+b1c1 一次 二次那么t個數(shù)應(yīng)用這個技巧經(jīng)過log3/2 t 次相加后得到兩個數(shù)，輸出位的次數(shù)為2log3/2 t = tlog3/2 2= 。再看兩個t位數(shù)相加：進位：a2b2+a2a1b1+b2a1b1 a1b1
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1