不可區分混淆的回顧與展望

郁 昱,姚 立

(1. 上海交通大學 計算機科學與工程系，上海 200240；2. 上海期智研究院，上海 200232)

1 程序混淆

一個程序代碼中有代碼的框架結構、組件間的調用關系和算法思想等信息，有時還包含一些硬編碼的字符，這些硬編碼的字符或算法都可以被看作程序中隱藏的一些秘密信息。顯然，軟件行業往往并不希望軟件中的算法隨著軟件的售賣而被泄露，也不希望軟件被任意修改(例如運用反編譯等手段對付費軟件進行破解)。程序混淆便可用于解決這一問題(也許有人聲稱一份寫得極為糟糕的代碼也能達到類似的效果，但這種做法的有效性無法被嚴格證明，同時也會增加軟件產生bug的風險)。

程序混淆(program obfuscation)保證了程序中確實能夠隱藏某些秘密信息，即使是擁有這個程序并且能夠任意運行這個程序的人也無法得知這些秘密信息。

1.1 正確性

實現程序混淆需要有程序混淆器(program obfuscator)。程序混淆器(記為Obf)可以被視為一個特殊的編譯器，這個編譯器的輸入(例如一段代碼)對應于某個程序，將輸入對應的這個程序記為P，編譯器將P編譯后會輸出一個混淆后的程序，記為。那么要求：

(1)這2個程序的功能完全一致;

(2)從實用性的角度出發，Obf和都應當是高效的。

1.2 安全性

1.2.1 虛擬黑盒混淆

1.2.2 不可區分混淆

不可區分混淆指對于2個功能完全一致的程序P1和P2，任何區分器都無法區分1和2。這個安全性的定義直覺上并沒有特別強(事實上即使P=NP，iO 仍然能夠存在，但這種情形下 iO 幾乎隱藏不了什么信息)，2007年，Goldwasser 等[2]證明了iO 是有可能被實現的最好的混淆器。為了簡述其思想，假設 VBBO 是可能存在的，并證明此時 iO 至少和 VBBO 一樣安全。對于程序P和VBBO(P)，顯然這二者功能一樣，于是，根據 iO 的定義，任何多項式的敵手都無法區分iO(P)和iO(VBBO(P))。VBBO(P)已經實現了虛擬黑盒安全，對其應用任何算法(包括iO)都無法打破虛擬黑盒混淆的安全性，因此，iO(VBBO(P))也實現了虛擬黑盒混淆安全；同時，iO(P)與O(VBBO(P))不可區分，因此，iO(P)自然也符合虛擬黑盒混淆的安全性定義。

1.3 應用

由于通用 VBBO 的不可實現以及 iO 具有很強的安全性，目前，已有大量根據 iO 來構造密碼學組件的研究成果，其中最早的是 Sahai 等[3]在 2014年通過 iO 和一些基礎的密碼學假設(例如單向函數(one-way function))構造了公鑰加密(public-key encryption)、數字簽名(digital signature)和可否認加密(deniable encryption)等組件。

綜合這些研究成果可以看到，iO 不僅能用于構造已經熟知的經典密碼學組件，更可以作為橋梁構造大量功能十分強大的“新”密碼學組件(其中一部分組件目前只能基于 iO 構造)。

1.4 構造

盡管在如何應用iO方面已經有了很多可喜的研究成果，但至今仍無法構造出安全且高效的iO。這并不意味著研究者止步不前，事實上，自2013年Garg等[4]提出第一個iO的候選方案以來，iO的構造方案已經經歷了多次演進。本文將這些年來iO構造的發展歷程大致分為4個階段，并選取有代表性以及突破性的工作逐一進行介紹。

2 第一代iO：基于多項式階多線性映射

自2013年起，有一系列工作基于多線性映射構造iO。相比于接下來的幾代iO構造，第一代iO的構造非常直接高效，且易于理解。但由于多線性映射候選方案在安全性方面的缺失，從第一個iO候選方案[4]被提出算起，這些方案已經經歷了多輪攻擊與修補[5-10]。時至今日，針對第一個iO候選方案的某些變體方案仍然沒有提出有效的攻擊，與此同時，也沒有人能夠用數學工具來證明這些變體的安全性，除非借助于一些非常強的理想化模型。

2.1 多線性映射

代數群是密碼學中常用的經典結構，RSA公鑰加密及DH密鑰交換等算法都運用了代數群以及群相關的困難假設。由于離散對數假設的存在，可以粗略地將ga視為a在群G上的編碼，而代數群的一個特點便是加法同態性，即ga·gb=ga+b，這也意味著可以利用代數群的結構安全地進行加法計算。由于環上的任意計算都可以分解為加法和乘法，因此，如果能夠進一步找到一類特殊的環，使得乘法同態也一并滿足，那么這一代數結構將在密碼學中具有極其廣泛的應用。

雖然Miller的這篇文章被計算機理論科學的頂級會議STOC以沒有應用為由拒稿，此后一直未公開發表，但是在20年后，基于雙線性映射的基于身份加密(Identity Based Encryption,IBE)、基于屬性加密(Attribute Based Encryption,ABE)和BLS 短簽名(BLS short signature)等密碼學原語相繼發表，證明了雙線性映射在密碼學領域有著廣泛的應用場景。

類似的，可以定義k階多線性映射G1×G2×…×Gk→GT(G1,G2…Gk可以是同一個群)。然而，當試圖將雙線性映射的構造推廣到三階時，得到的映射將不再是多項式時間可計算的[12]。這也說明，構造多線性映射需要新的技術和方法。

2013年，Garg等[13]提出了第一個多線性映射的備選方案，此后陸續有其他候選方案[14-15]被提出。這些多線性映射的備選方案有著一些共同特點：

(1)帶噪聲編碼：同一個元素在同一個群上的編碼很可能不相同，它們之間會相差一個較小的噪聲。

(2)零元素測試：由于同一個元素的編碼往往不同，當它們相減時，會得到某一個而非唯一的零元素編碼。因此，需要零元素測試算法來判斷編碼是否是零元素編碼。

(4)無法維持經典假設：在這些多線性映射群上，經典的假設(雙線性映射群上常見假設的推廣)，例如判定性線性(Decisional Linear,DLIN)假設等均不成立。

2.2 用于對數深度電路的iO

有了多線性映射，便可以著手進行iO的構造了。下面介紹最經典的構造，同時也是第一個iO候選方案[4]。這一方案首先構造了只能用于對數深度電路的iO，之后利用自舉技術將其適用性拓展為所有多項式大小的電路。盡管這一方案在理想的多線性映射代數系統中是可證明安全的，由于目前已有的多線性映射候選方案均無法維持經典假設，因此，這一類方案整體的安全性至今無法在標準模型中得到證明。

2.2.1 分支程序

早在1986年，Barrington[16]就證明了任意一個NC1的電路可以被表示為寬度為5的多項式大小的分支程序。這意味著一個NC1電路的計算可以被表示為多項式個五維矩陣的乘積，其中的每個矩陣都是從一對矩陣中依據某個輸入位的值選取的。例如對于一對矩陣(A1，A2)，其關聯的輸入位為xi，那么有一種可能的情況：如果xi為0，就選取A2，否則，選取A1。需要注意的是，一個輸入位可能會多次決定矩陣的選取。

2.2.2 類拼圖游戲

多線性映射允許計算多項式個矩陣的乘積，但是卻無法保證攻擊者能夠誠實地選取這些矩陣并誠實地進行運算。例如如果xi為0，應選取A2和B1參與運算，反之選取A1和B2參與運算，而敵手可能會選取A1和B1參與運算，這無疑會得到除電路正常輸出以外的信息，從而利用這一信息打破iO(iO的安全定義中要求2個程序的功能完全一樣，這也意味著往往只有正常的電路輸出才能保證不會泄露信息)。再比如，程序正常計算時，應該是C1/C2乘以D1/D2，而敵手可能會計算D1乘以C1，從而得到額外的信息(矩陣乘法不滿足交換律)。因此，仿照拼圖游戲去設計一些算法來避免這一點，例如針對第一種情況，可以把A2和B1設計為一塊拼圖，只能同時選或同時不選；針對第二種情況，可以讓C1/C2這2塊拼圖右側的鋸齒和D1/D2這2塊拼圖左側的鋸齒相吻合，這樣只有將C1/C2放在D1/D2左側才能使得拼圖呈現吻合的狀態。在密碼學中，這類操作通常通過添加噪聲來實現，當程序按照預定的方式計算時，這些噪聲的乘積剛好會相互抵消，得到正確的計算結果；總之，這些噪聲糅合在一起，將原本會被泄露的額外信息掩蓋起來。同時，也需要給這些拼圖添加一些隨機性，例如當C1和C2完全一樣時，它們的鋸齒也會完全一樣，那么此時會出現2塊完全一樣的拼圖。而對于另一個功能一樣的分支程序，可能不存在2塊完全一樣的拼圖，這樣敵手就可以輕易地區分這2個程序。所以，需要給拼圖注入隨機性，使得出現2塊完全相同拼圖的概率是可忽略的。

2.3 自舉

自舉(bootstrapping)技術最早出現在全同態加密(Fully Homomorphic Encryption,FHE)中，其核心思想是，當需要實現一個強大的功能時，也許只需要實現一個弱的版本，并利用這個弱的版本來構造出那個強大的功能。一個形象的例子是，當組裝一個機器人時，只需組裝出機器人的手，接下來便可以讓機器人的手去組裝機器人剩余的部分。為了實現iO的自舉，還需要用到全同態加密和通用電路。

相比于通常的加密，全同態加密允許在不知道明文的情況下直接對密文進行操作。同時，全同態加密的解密函數較為簡單，可以用一個NC1的電路表示。

通用電路(Universal Circuit,UC)可以用來模擬任意電路的計算過程，它將電路C的描述和電路C的輸入作為輸入，并得到電路C的輸出。通用電路也可以交換電路C和電路C的輸入立場，通過將電路C的輸入硬編碼在通用電路里，使UC(·,x)成為電路，而電路C的輸入成為該電路的輸入。

也就是說，要構造適用于所有多項式大小電路的iO，構造一個適用于NC1電路的iO就足夠了。NC1的電路可以表示為多項式個矩陣的乘積，多項式個矩陣的乘積需要多項式次乘法運算，因此，可以通過多項式階的多線性映射來完成這一任務。

3 第二代iO：基于常數(≥3)階多線性映射

目前，密碼學標準假設中只有雙線性映射，因此，自2015年起，有一系列工作[17-24]試圖將iO規約到(相較于iO)稍弱的密碼學組件中，從而最終只需要依賴三階多線性映射，這與雙線性映射已經十分接近了。

3.1 規約到亞線性簡明隨機化編碼

隨機化編碼(Randomized Encoding,RE)可以用來保護一次計算，例如混淆電路(Garble Circuit,GC)就可以視為RE，它包含有2個算法：

函數加密是一類特殊的加密方式，不同于傳統加密要么持有密鑰得到全部的秘密，要么沒有密鑰從而對秘密一無所知的加密模式，FE存在有一個主密鑰msk，通過主密鑰可以派生與某個函數f相關的密鑰skf，通過用該密鑰對消息m的加密進行解密，可以得到f(m)。公鑰FE(也可稱作非對稱FE或PKFE)包含4個算法：

(1)Setup(1λ)→(pk,msk):生成公鑰和主密鑰;

(3)KeyGen(msk,C)→skC:生成與電路C對應的解密密鑰skC;

私鑰FE(也可稱作對稱FE或SKFE)只需要將pk替換為msk，如果FE只支持執行一次KeyGen算法，則稱該FE是 1-key FE；如果支持執行任意次KeyGen算法，則稱其為抗合謀(collusion-resistance) FE。如非特殊說明，FE指PKFE。

那么通過GC，就可以實現iO了嗎？答案是否定的，這是因為GC的Encode算法的時間復雜度是ploy(λ)·s，將這一算法用電路表示，電路大小也是ploy(λ)·s,而GGM樹的倒數第二層需要輸出2個上述的RE，因此，耗時至少是ploy(λ)2·s，以此類推，每一層電路的大小都會增大ploy(λ)倍，根節點計算RE的耗時是ploy(λ)n·s。如果給定電路C，計算根節點的RE并輸出需要耗費指數大小的時間，則需要一個高效的RE。自2015年起的一些工作[17-19]證明了，當RE滿足亞線性簡明時，這一構造才是可用的。

3.2 規約到弱亞線性簡明隨機化編碼

由于構造亞線性簡明隨機化編碼過于困難，研究者們把目光暫時轉向了當時已有的最高效的FE/RE，即Goldwasser等[25]提出的succinct 1-key FE，該構造基于帶噪聲學習(Learning with Errors,LWE)假設，試圖通過利用這一構造進一步將iO規約到更弱的密碼學原語上。

3.3 規約到指數iO

指數iO (Exponential iO,XiO)進一步放寬了iO的要求，iO(C)的輸出長度應該是poly(λ,|C|)，而XiO則允許輸出長度達到poly(λ,|C|)·2n(1-)，一個電路的真值表可以看作一個平凡的混淆，其輸出長度至多為|C|·2n，因此，XiO僅僅要求我們能夠做得比直接輸出真值表好一點。同時注意到，這一定義并沒有對XiO的運行時間做任何規定，也就是說XiO運行的時間可以達到指數大小，這也是它被命名為指數iO的原因。2016年，Lin等[20]將iO規約到了LWE+XiO，這是一個比較反直覺的結論，只要能夠對將混淆程序的大小壓縮為亞指數，就能夠將其壓縮為多項式。這一規約的過程便是通過succinct 1-key FE和XiO構造weakly sublinear compact 1-key FE。

由于succinctness意味著FE的加密只和輸出長度有關，與電路大小無關，因此，當計算1比特輸出時，加密的復雜度將是poly(λ,|x|)(因為密文需要包含消息x的信息，所以必定與消息長度和安全參數有關)。對于一個n′比特輸出的電路，可以用n′個succinct 1-key FE 的實例分別計算C(x)的每個比特，即消息x分別用n′個FE實例加密，同時這n′個FE的實例各自生成一個密鑰，對應于計算電路C各個輸出位的電路。把這n′個FE的加密過程封裝進同一個電路D，當輸入i∈[n′]時，輸出x被第i個FE的實例加密的密文。將XiO(D)作為weakly sublinear compact 1-key FE加密算法的輸出，把n′個FE實例各自生成的密鑰作為密鑰生成算法的輸出。由于D的輸入總共有n′個，且n′一定不大于電路大小s，由XiO的定義，XiO(D)的輸出長度為poly(λ,|D|)·s，由于電路D的功能是計算x經由某個succinct 1-key FE加密的密文，而succinct 1-key FE加密的復雜度將是poly(λ,|x|)，因此，XiO(D)的輸出長度為poly(λ,|x|)·s，從而滿足weakly sublinear compactness。

3.4 對指數iO作進一步規約

從XiO繼續向下規約，有2條路線，分別基于函數編碼(functional encoding)和弱亞線性簡明單密鑰對稱函數加密(weakly sublinear compact 1-key SKFE)。

Functional encoding可以視為FE的弱化，它包含3個算法：

(2)Opening(C,x,r)→h:確定性算法，除了電路C，還會輸入x和r，其中，r是Encode時用到的隨機數，因此，該算法可以完全復現Encode的過程。輸出一個解碼提示hC。

可以將FE視為特殊的functional encoding。與FE相比，functional encoding弱在其提示hf可能與Encode過程綁定，即其不能支持解碼任意編碼，而只能用于解碼與其輸入對應的Encode(x;r)。因此，與1-key many-ciphertexts FE對應的，functional encoding類似于1-ciphertext many-keys FE，也就是多個解碼提示可對應于某一個編碼。

假設有一個電路D，它能輸出電路完整的真值表:D(C)=C(0)‖C(1)‖…‖C(2n-1)，這個電路可以看作通用電路的變體，那么可以設XiO(C)=(,hD)。根據functional encoding的定義，只能得到真值表的信息。

為了解決這一問題，可以將真值表拆分成2n1份，每份包含2n2項，其中，n1+n2=n。那么，總共需要一個和2n1個解密提示，分別解密每一份子真值表。因此，提示的數量是與2n1線性相關，而||與電路的輸出，即子真值表的大小2n2線性相關，由于這兩者都小于2n，因此，XiO(C)=(,hD1,hD2,…,hD2n1)關于2n亞線性相關，即實現了壓縮真值表的要求。

3.5 FE中的自舉技術

(1)混淆電路可以對電路的每個門分別生成真值表的混淆，生成混淆電路的過程可以用一個NC0電路表示，且這個電路可以表示為|C|個子電路，每個子電路用于混淆一個門，而混淆一個門的復雜度是與電路C無關的，這一特性被稱為可分解的(decomposable)。最初的這類自舉方案中需要使用PRF(NC0上不存在)，研究者們只將支持多項式大小電路的FE規約到支持NC1電路的FE[26]，后來才注意到能用PRG代替PRF[27]。

(2)AIK RE是一個作用于分支程序的RE[28]，只能支持將NC1上的電路進行編碼，生成AIK RE的過程同樣可以用一個NC0的電路表示。不僅如此，AIK RE的每個輸出比特至多只和輸入x的某一個比特及用到的隨機串r的某3個比特有關。

與此同時，Lin[23]基于常數階多線性映射的SXDH假設構造出了支持NC0電路的SKFE，由于NC0電路的每個輸出最多與c個輸入相關(c是常數)，因此至多需要進行c次乘法計算，才可以利用c階多線性映射。不僅如此，構造得到的FE還滿足線性效率，即加密的時間復雜度隨消息的長度|x|呈線性增長。這樣，只需要用這一SKFE去加密RE的輸入，似乎就可以構造得到用于任意多項式大小電路的SKFE。但是，RE的輸入除了消息x，還需要使用隨機串，隨機串的大小與電路大小|C|是線性關系，無法實現sublinear compactness。為此，可以將加密的內容由隨機串換成PRG的種子，并用PRG生成的偽隨機串來代替隨機串。為了實現 sublinear compactness，要求PRG的種子長度是輸出長度的亞線性，即PRG的拉伸度(stretch)是n。目前，NC0上具有超線性stretch的PRG只有Goldreich[29]提出的候選方案，而無法規約到現有的其他標準假設，因此，iO的構造中將NC0上存在具有超線性stretch的PRG作為一個假設提出。需要注意的是，目前已經證明了NC0上存在具有超線性stretch的PRG的locality必須大于等于5[30]。由于PRG的種子被FE加密在密文里，而PRG的種子被使用2次以上會影響安全性，雖然Lin[23]構造的是collusion-resistance的SKFE，但是當其用于計算NC0上的RE.Encode(C,·)時，就退化成了1-key SKFE，好在1-key sublinear compact SKFE已經足以構造iO。

下面進一步分析上述方案具體需要用到多少階的多線性映射。根據AIK RE的特性，每個輸出位與1個輸入位和3個隨機串位有關，隨機串又是由PRG生成的，且PRG的locality至少是5，即PRG每個輸出位與5個輸入種子位有關，則總共與1個輸入位和15個輸入種子位有關。由于在安全證明中，需要加入一些額外的行為，因此，還會引入一個額外的輸入比特b。當b=0時，電路會正常計算RE.Encode(C,·)；當b=1時，電路會進行一些其他計算，這個計算涉及的比特位少于計算RE.Encode(C,·)，且b=1這一情況只在安全證明中才會出現。上述方案每個輸出位至多會用到17個輸入位，即需要17階多線性映射。

3.6 降低至三階線性映射

為了進一步降低多線性映射的階數，Lin[23]同時指出可以賦予PRG特定的結構，并利用預處理的方法。由于GC具有decomposable的特性，因此，可以將RE.Encode(C,·)的計算拆分為|C|個計算，每個計算混淆C的一個電路門，每個計算的電路大小及需要用到的隨機串均為poly(λ)。之后再用AIK RE進一步Encode，則此時Encode過程只和一個電路門以及poly(λ)個隨機數相關。可以使用poly(λ)個完全相同的子PRG來生成隨機串，這些子PRG的輸出長度為|C|，這poly(λ)個子PRG輸出的第i個比特可以拼成長為poly(λ)的偽隨機串，用于混淆C的第i個電路門。在這種結構下，第i個AIK RE使用的隨機數是由這些子PRG的第i個比特的輸出拼成的，又因為這些子PRG完全相同，因此，子PRG第i個比特的輸出一定對應于某5個特定的輸入位置。雖然最終一個輸出位會關聯15個PRG輸入位，但這15個輸入位只來自于5個輸入位置，每個位置取3個輸入位。有了這一結構，就可以將每個輸入位置的輸入提前相乘，而不是使用多線性映射的能力計算乘法。由于總共有poly(λ)個子PRG，因此，每個輸入位置有poly(λ)個輸入，從中任取3個(也可以不取)，總共情況不超過(1+poly(λ))3。仍然是關于λ的與|C|無關的多項式，從而不會影響sublinear compactness。由于每個位置的輸入已經提前乘好，剩下的計算則是圍繞這5個位置進行的，b和x也可以用類似的預處理技術，因此，五階多線性映射就足夠了。

Lin等[24]又在2017年進一步降低了多線性映射的階數，由于NC0上存在具有超線性stretch的PRG的locality必須大于等于5，他們提出了一種新的PRG，即block-wise PRG，PRG的每個輸出對應的輸入可以來自于常數多個分塊，每個分塊含有log(λ)個比特，這樣通過預處理，可以將分塊內的乘法提前算好，總共2log( λ)種情況。由于每個分塊都含有大量比特，這樣似乎可以不受locality必須大于等于5的限制。最初，他們宣稱block-wise PRG的每個輸出可以只依賴2個block，因而可以將iO規約到雙線性映射這一標準假設，但是隨后攻擊這類PRG的方法被提出[31]，他們只得宣稱block-wise PRG的每個輸出至少要依賴3個block，最終iO被規約到三階線性映射，離標準假設的目標仍有一步之遙。

4 第三代iO：基于雙多線性映射

2015年，Gorbunov等[32]首次提出了部分隱藏(Partial Hiding,PH)的概念，并將其與FHE的部分解密結合，構造了謂詞加密(Predicate Encryption,PE)。PE是ABE的升級版，可以隱藏屬性attr的同時計算policy(attr)的值，從這個角度看，它也可以說是一個特殊的FE，對于構造FE有著借鑒意義。PH是指加密消息時，將消息分為2個部分，即公開部分P和秘密部分S，同時PHPE只支持對秘密部分S做一些輕量級的計算(內積計算)。可以將attr在同態加密下的密文作為公開信息，將同態加密的密鑰作為秘密信息。由于同態加密的密文是公開信息，因此，可以對它進行同態計算，得到policy(attr)的加密，而同態加密的解密算法正是計算內積并通過模數運算去除噪聲。如果只計算內積的話，會得到policy(attr)+noise，只計算內積也被稱作部分解密。在PE特殊的安全定義下，這個噪聲的泄露將不會影響安全性。

運用類似的思想，Jain等[33-35]提出了相似的SKFE構造。強化了Lin[23]在2017年構造出的FE，基于雙線性映射構造了PHFE。PHFE除了能夠對秘密部分進行一次乘法計算外，還能對公開部分進行常數深度的計算。由于只需要構造一個支持NC0電路的SKFE，因此不需要使用全同態加密，只需要支持NC0電路的同態加密。同樣的，會得到C(x)的加密，并用秘密部分的密鑰來解密，解密操作是內積計算，得到的結果是C(x)+noise，不同于PE，這里的噪聲會影響安全性，而模數操作又太復雜，無法依靠PHFE完成。為此，設想存在一個特殊的PRG，通過將種子加密在秘密部分和公開部分中，可以用PHFE計算得到PRG的輸出，并用這個輸出去掩蓋噪聲。也就是說，這個特殊的PRG輸出的每個比特可以表示為秘密部分的至多2個比特和公開部分的至多常數個比特的乘積和。至此，iO被規約到了一個特殊的PRG。

2021年，Jain等[36]最終構造出了這一PRG，完成了基于標準假設構造iO的最后一塊拼圖。為此引入LPN假設，LPN假設與LWE假設有相似之處，主要區別在于LPN中的噪聲雖然可能很大，但數量少；LWE中的噪聲都很小，但很少出現為0的情況。將PRG的種子用LPN加密，并同態計算一個NC0上的PRG，最終同樣得到PRG(seed)+noise。LPN的噪聲很稀疏，不同于LWE的噪聲，其可能被PHFE去掉。具體做法是提前計算出LPN的噪聲，并將其一并放在PHFE密文的秘密部分。解密時算出PRG(seed)+noise后，將其與PHFE中的噪聲相減以抵消噪聲。但是，噪聲向量長度為|PRG(seed)|，為了sublinear compactness，只能加密長度小于這個值的輸入(例如seed)。為此，需要將稀疏的噪聲向量壓縮后存儲在PHFE密文的秘密部分，同時又要能夠用一次乘法就將壓縮的噪聲向量還原回來(因為PHFE只支持對秘密部分計算一次乘法)。因此，用到了矩陣的分解，即將噪聲向量排列為矩陣形式。由于其稀疏性，矩陣的秩很低，一個秩很低的m×m的矩陣可以分解為一個m×rank的矩陣和一個rank×m的矩陣的乘積。就這樣，基于SXDH,LPN,LWE和NC0上存在PRG這4個假設的iO被構造了出來。之后，又利用LPN在NC0上的同態性去代替LWE(還包括一些其他技術)，將假設減少為3個，即去掉了LWE假設[37]。

5 新的目標：后量子安全

群的特殊結構使得在面對量子計算機時，群上的安全假設(DH、RSA等)都會被攻破，因此，也有一些工作試圖用LWE加上一些其他假設構造后量子安全的iO。這些候選方案有的是基于更強的循環安全 (circular security) 假設[38-40]，循環安全假設是用于構造FHE的重要假設，也是得到了較為廣泛認可的假設。雖然這類iO方案同樣使用了FHE及其相關的技術，但是它們所依賴的假設卻強于FHE所需的假設。與此同時，Wee等[41]也展示了不經意的 LWE 采樣可以蘊含 iO 并且給出了一個基于類似于循環安全的假設候選方案。然而，Hopkins等[42]針對上述候選方案的假設給出了反例。2021年，Wee等[43]進一步改進了他們先前的工作，基于一個更弱的密碼學原語 (緊湊 LWE 采樣 (succinct LWE sampling)) 構造出了 iO，同時也給出了一個緊湊 LWE 采樣的候選方案，該方案的安全性與求解多項式等式系統的困難性相關聯。除了基于循環安全方面的假設，也有一些工作試圖基于帶噪聲的線性函數加密 (noisy linear functional encryption) 來構造 iO[44-45]。除此之外有個特殊的用于仿射行列式程序的混淆方案[46]，它的效率相較于其他方案非常高，而且安全性沒有基于任何傳統的假設，目前的量子技術對于攻擊該方案也沒有表現出特別的優勢。但該方案的安全性無法規約到任何簡明的具體假設上，且目前僅有唯一一篇針對該方案的安全分析[47]。

在這些工作中，基于更強的循環安全假設的工作最具代表性，也是本章重點介紹的方案。這類工作都是通過構造functional encoding從而構造iO，與上一節類似的是，他們也使用FHE加密消息，并在解密階段對其進行解密。但是，FHE解密時不存在緊湊的解密提示，為此，使用了支持生成緊湊解密提示的線性同態加密(Linear Homomorphic Encryption,LHE)方案；同時，采用密鑰交換技術，能把消息在FHE下的加密轉換為消息在LHE下的加密。最初這類方案[38]使用的LHE基于的是DCR假設[48]，因而無法實現后量子安全，后來這類方案[40]中的LHE被替換為基于LWE的LHE。

其中,線性同態加密只能支持線性函數的同態加密，其中一些構造可以將解密分為2步：①根據密鑰和密文生成短的解密提示；②根據解密提示對密文進行解密。

密鑰交換技術最早出現在全同態加密的構造中，通常把解密過程視為用密鑰對密文進行操作，如果轉換視角，解密過程也可以理解為用密文對密鑰進行操作。假設有第一個同態加密方案的密鑰sk1，那么用x在第一個同態加密方案上的密文對該密鑰進行操作可以解密得到x；現在，將用第二個同態加密方案同態地進行這一操作，即最初持有地將不再是密鑰sk1，而是用第二個同態加密方案加密過的sk1；同理，此時的輸出也不再是x，而是x在第二個同態加密方案上的密文。這樣就完成了密鑰的切換，需要注意的是，切換能夠成功的前提是第二個同態加密方案支持同態地運行第一個同態加密方案的解密電路。FHE的部分解密是線性函數(計算內積)，因此,可以被LHE同態計算。但是，FHE部分解密得到的是C(x)+noise，至此，他們遇到了和之前的構造一樣的問題，即如何掩蓋噪聲。

針對噪聲的泄露通常只有2類方法：去除噪聲或者用一個更大的隨機噪聲去掩蓋。去除噪聲是一個十分復雜的功能，無法用線性函數去解決(LHE只支持線性函數)，因此，只剩下用一個更大的噪聲去掩蓋這條路可以走。理想情況下，有一個預言機(oracle)，它能夠產生一個LHE的密文，這個密文對應的明文是一個較大的隨機噪聲，通過LHE將兩者進行疊加(加法是一個十分簡單的線性函數,可以通過LHE的同態性完成)，就可以掩蓋FHE產生的噪聲。

現實情況下顯然沒有如此方便的oracle，但可以使用隨機預言機(random oracle)產生一個隨機數，前文提到的那幾種LHE方案還具有一個非常好的性質，它們的密文空間很“稠密”(這意味著隨機數有極大概率能被當成LHE的密文成功進行解密)。隨機數對應的明文可能是個非常大的數，而需要的僅僅是一個稍大的噪聲，這個噪聲能夠掩蓋FHE解密時產生的噪聲又不至于掩蓋解密后的明文。此時，需要將明文的高位設為0，這又是一個十分復雜的操作，無法用線性函數完成，因此，使用密鑰交換技術把LHE的密文轉為FHE的密文，通過FHE全同態的能力去除明文的高位，之后再次利用密鑰交換技術把FHE的密文轉回LHE的密文，這樣，就能得到一個經LHE加密的較大噪聲。到這里仍然有一個小問題，就是利用密鑰交換將FHE的密文轉回LHE的密文時又會產生一個小噪聲，這個小噪聲會引入一定的相關性，雖然這個相關性看上去很難被敵手利用，但是這給安全性證明帶來了困難。同時，由于密文需要在FHE和LHE之間互相轉換，因此，這一構造在證明時需要用到循環安全假設。各類方案的對比見表1。

Gay等[39]隨后對該方案做了進一步的改進，將random oracle替換為一串很長的CRS，并且發現FHE可以給密文附上新的噪聲(同態地加上一個0的加密)，因此，通過給FHE密文附上較大噪聲的方式去掩蓋會產生相關性的小噪音。同時，給出了安全證明，將方案的安全性規約到了一個更強的循環安全假設。各類方案的對比見表1。

表1 iO主流候選方案對比Table 1 Comparison among the popular iO candidates

6 總結與展望

經過了十年的發展，構造可證明安全的iO已經初步取得了成功，一些曾經質疑iO是否有可能存在的研究者也開始轉而投入相關的工作當中。盡管這一構造目前不是后量子安全的，但是研究者們也已經開始朝著這個方向前進。這類可證明安全的構造在安全性方面雖然更有保證，但是也會犧牲效率，而且完整的規約過程也十分復雜。除了實現后量子安全，這類方案未來可以朝著更少假設、更少規約和更高效實現這3個方向進一步前進。

另外，也有一些更為直接的構造，例如基于多線性映射以及矩陣隨機化的候選方案。這類方案效率更高，但是在安全性方面需要大量的安全分析，并經受多輪攻擊修復的循環才能得到較為廣泛的信任。未來可以嘗試提出各種直接構造iO的方案，并嘗試對這些方案進行分析、攻擊與修復。這類方案的高效性使得iO能更早地從理論世界進入應用領域。