【正文】 12345678 * 和 12345678 * 。下面再看看解密電路的運(yùn)算次數(shù)：Dec(c): (c mod p) mod 2=（c – p*「c/p」）mod 2 = Lsb(c) XOR Lsb(「c/p」)仔細(xì)端詳解密電路的公式，發(fā)覺(jué)其復(fù)雜性主要來(lái)源是c/p，所以我們主要看c/p所需的運(yùn)算次數(shù)。不妨令mi+2ri = xi, 且xi B, B是密文ci噪音的上界，則有：f ( x1, x2, …，xn ) p/2。由于permitted functions集合里的任一功能函數(shù)f 都可以用AND電路和XOR電路表出，而AND電路和XOR電路可以看做對(duì)輸入的二進(jìn)制位做乘法和加法，所以f電路的深度可以用輸入位的對(duì)稱(chēng)多項(xiàng)式來(lái)衡量（用多項(xiàng)式衡量是因?yàn)槎囗?xiàng)式里恰好是變?cè)某朔ê图臃ǎ?，又由于乘法是噪音的主要?lái)源，所以可以用多項(xiàng)式中乘法次數(shù)來(lái)做電路深度的主要衡量指標(biāo)。解密電路的深度上面有一個(gè)人說(shuō)對(duì)了一半，其實(shí)我們可以把解密電路用AND電路和XOR電路表出，計(jì)算一下電路的深度（電路的深度代表著運(yùn)算的次數(shù)），然后再和permitted functions中功能電路所允許的最大深度做個(gè)比較，就知道解密電路是否屬于permitted functions集合了。唯一缺的就是沒(méi)有證實(shí)解密電路也在permitted functions集合里。AND電路、XOR電路、解密電路都可看成是“原電路”（這個(gè)名字是我自己取的），就是說(shuō)它們是構(gòu)成任意功能函數(shù)的基石，permitted functions集合里含有它們就完全夠了。另外還有人說(shuō)，按照上面方法把解密電路表示成增強(qiáng)電路不就行了。OK，全同態(tài)的藍(lán)圖終于在紙上實(shí)現(xiàn)了。那如何能夠保證對(duì)密文做任意功能的運(yùn)算還是正確的呢？前面說(shuō)過(guò)可以通過(guò)重加密技術(shù)降低噪音呀！具體如何做呢？很簡(jiǎn)單：給AND電路上接一個(gè)解密電路，給XOR電路上也接一個(gè)解密電路，任何密文在進(jìn)入AND電路或XOR電路之前，先讓它進(jìn)入解密電路進(jìn)行重加密，之后從解密電路里出來(lái)的密文就是一個(gè)類(lèi)似于新鮮密文的密文，噪音比進(jìn)來(lái)前降低了，然后再讓這個(gè)新的密文進(jìn)入AND電路或XOR電路，這樣我們就可以對(duì)密文正確的做任意功能的計(jì)算了！而接了解密電路的AND電路或XOR電路就稱(chēng)為增強(qiáng)電路。又由于AND電路和XOR電路是完備的，所以任意功能都可以用這兩個(gè)電路組合表出，也就是說(shuō)該同態(tài)方案可以對(duì)密文做任意功能的運(yùn)算，這不就是傳說(shuō)中的全同態(tài)定義么！任意功能的問(wèn)題解決了，但是還缺一點(diǎn)：必須是正確的才行。同樣我們也可以選擇用AND電路和XOR電路，因?yàn)檫@兩個(gè)電路是具有完備性質(zhì)的，也就是說(shuō)這兩個(gè)電路的組合也可以表出任意功能的電路（而且用這兩個(gè)電路來(lái)描述更加直觀，它們直接對(duì)應(yīng)的算術(shù)運(yùn)算就是乘法和加法）。但是功能函數(shù)f又是什么呢？我想應(yīng)該是五花八門(mén)的功能，如果想用功能去描述它恐怕是一言難盡，但是如果用布爾電路的大?。╰he size of boolean circuit,即門(mén)電路的數(shù)量）來(lái)衡量，那么f就能夠被拆解成一些簡(jiǎn)單的布爾電路：例如“與”電路、“或”電路、“非”電路。顯然Evaluate的復(fù)雜度依賴(lài)于所運(yùn)算的功能f。正確性當(dāng)然是必須的?？梢杂孟率秸f(shuō)明： 上式太重要了，我覺(jué)得只要把上面的式子牢記在心，那么全同態(tài)的概念就裝在心里了。并不是說(shuō)沒(méi)有這種方案，估計(jì)只是現(xiàn)在還沒(méi)有找到。電路復(fù)雜度前面的方案中大家看到了是按“位”來(lái)加密的（即m∈ {0,1}），加密后得到的是一個(gè)整數(shù)，密文膨脹的很厲害，那么為什么明文不取整數(shù)來(lái)加密呢？例如取明文m∈Z。好了，到這里似乎全同態(tài)實(shí)現(xiàn)了（有種共產(chǎn)主義立馬實(shí)現(xiàn)的感覺(jué)）。從上面的解決思路可以看到?jīng)]有特別繞彎子的地方，就是碰到問(wèn)題解決問(wèn)題，解決不了的，創(chuàng)造條件也要解決。要證明前面的方案是circular security的還很困難，但是目前可以認(rèn)為不會(huì)帶來(lái)攻擊的。如果全同態(tài)的加密方案是circular security的話(huà)，就不需要這么多公鑰與私鑰，所有電路層都共用一個(gè)公鑰與加密的私鑰就可以了。這種情況下公鑰與私鑰的數(shù)量與電路的深度成線(xiàn)性的依賴(lài)關(guān)系。同理在電路第二層進(jìn)行重加密時(shí)，將用pk3對(duì)該層密鑰sk2加密得到sk2*，,以及對(duì)來(lái)自第一層電路的輸出密文進(jìn)行加密；然后輸入解密電路，解密電路將輸出一個(gè)密文，該密文是對(duì)明文用pk3進(jìn)行加密的結(jié)果。第一層對(duì)應(yīng)的是pk1和sk1，第二層對(duì)應(yīng)的是pk2和sk2……。如圖：由于重加密在每次執(zhí)行前都需要一個(gè)公鑰來(lái)加密私鑰和密文，要進(jìn)行多次重加密就需要一個(gè)公鑰序列{pk1,pk2,…,pki}，對(duì)應(yīng)于公鑰序列也有一個(gè)加密私鑰鏈{sk1*,sk2*,…,sk(i1)*}（其中ski*是用pk(i+1)加密ski得到的密文）。運(yùn)算電路可以反復(fù)遞歸此過(guò)程，就可以達(dá)到無(wú)限次密文運(yùn)算的目的了。）這一手法稱(chēng)之為：重加密技術(shù)，它為我們提供了降低噪音的一個(gè)方法。 那么同態(tài)解密對(duì)于降低噪音又有什么關(guān)系呢？ 當(dāng)密文運(yùn)算后，噪音會(huì)被迅速放大，如果我們對(duì)運(yùn)算后的密文做一次同態(tài)解密，是不是相當(dāng)于得到了一個(gè)新鮮密文呢，而新鮮密文的噪音是最小的，所以達(dá)到了降噪的目的。如果我們輸入的是s*（是用pk2對(duì)私鑰s加密得到的密文），以及對(duì)運(yùn)算密文c*（是用pk2對(duì)c再加密的密文，原密文c是用pk1進(jìn)行加密的)，那么執(zhí)行Evaluate(pk2, Dec, s*,c*)；所得結(jié)果為一個(gè)新的密文，該密文是明文在pk2下加密的密文，是不是有點(diǎn)像魔術(shù)，就像原來(lái)一個(gè)人穿的是西裝，現(xiàn)在你沒(méi)有看到這個(gè)人換衣服的情況下，魔術(shù)師只是施了一下魔法，這個(gè)人立刻就換了一身運(yùn)動(dòng)服，人還是原來(lái)那個(gè)人，只是包裝變了。）。在Evaluate算法中能夠?qū)γ芪膱?zhí)行函數(shù)功能f的運(yùn)算，其中f是屬于permitted founctions 集合的任一founction（這里稍微解釋一下，permitted founctions 集合也稱(chēng)permitted circuit，例如有兩個(gè)函數(shù)功能f1和f2，運(yùn)行Evaluate(pk, f1, c1,c2,…，)和Evaluate(pk, f1, c1,c2,…，)，就是分別對(duì)密文執(zhí)行f1運(yùn)算和f2運(yùn)算，如果f1運(yùn)算的結(jié)果解密后恰好是f1對(duì)相應(yīng)明文運(yùn)算的結(jié)果（同態(tài)成立），那么f1就屬于permitted founctions。二、方案參數(shù)分析 Bootstappable：一個(gè)生硬的思路噪音阻礙了我們的目標(biāo)，那么如何消除噪音這個(gè)敵人呢？一個(gè)直觀的方法就是對(duì)密文解密，密文解密后噪音就沒(méi)有了，但是要解密必須要知道私鑰，要想通過(guò)獲得私鑰來(lái)消除噪音是不現(xiàn)實(shí)的。估計(jì)多少英雄好漢到了這里就覺(jué)得沒(méi)戲了，于是另尋他路，于是一個(gè)突破就擦肩而過(guò)。到這里我們只得到了一個(gè)運(yùn)算時(shí)噪音范圍不能超過(guò)p/2的同態(tài)方案（Somewhat 同態(tài)方案），看來(lái)似乎用這個(gè)方案實(shí)現(xiàn)全同態(tài)是行不通的。 c* mod p=5, Dec(c*)=1≠m1*m2=0, 解密錯(cuò)誤，錯(cuò)誤的原因是噪音c* mod p= 6 不在（p/2，p/2）范圍內(nèi)。c1和c2稱(chēng)之為新鮮密文,就是直接由明文生成的密文，在新鮮密文中噪音是在一定合理的范圍內(nèi)的。 c1 mod p= 2, Dec(c1)=0.c2=Enc(m2)=m2+2r2+pq=1+2*1+11*5=58