混淆電路與不可區(qū)分混淆*

張 正, 張方國

1.中山大學(xué)數(shù)據(jù)科學(xué)與計算機學(xué)院, 廣州510006

2.廣東省信息安全技術(shù)重點實驗室, 廣州510006

1 引言

隨著對稱密碼和公鑰密碼的不斷發(fā)展, 僅僅對消息的加密已經(jīng)不能滿足人類社會的安全需求.云計算、協(xié)同計算等新型計算模型的出現(xiàn), 也使得對函數(shù)或電路的加密變得越來越重要.在交給代理商進行計算之前, 用戶希望不僅僅對輸入加密, 對函數(shù)本身也進行加密, 從而達(dá)到保護函數(shù) “內(nèi)部信息” 的目的.例如若醫(yī)院將疾病的診斷外包, 那么不僅病人的信息涉及隱私, 疾病的診斷方法也是醫(yī)院需要保護的信息.因此,對于函數(shù)或電路的加密成為一個新的研究熱點, 許多相關(guān)的密碼學(xué)方案也被提出.其中, 包括混淆、函數(shù)加密(functional encryption)、混淆電路(又稱混亂電路, 加密電路等)、隨機編碼(randomized encoding)等等.其中, 有兩個相近的概念——混淆和混淆電路.

混淆是由程序混淆[1]發(fā)展而來.學(xué)者們最初為了保護代碼安全而提出混淆的概念.也就是說, 混淆的目的是在保持程序功能的前提下, 使得程序內(nèi)容 “不可讀”.電路混淆或者說函數(shù)混淆起始于 Hada 的研究[2].Hada 提出的混淆要求混淆后的程序相當(dāng)于一個黑盒預(yù)言機, 除非函數(shù)是可學(xué)習(xí)的, 否則這種混淆的構(gòu)造是不存在的.在 2001 年, Barak 等人[3]第一次提出了電路混淆的形式化定義, 并給出了可證明的安全定義——虛擬黑盒安全(virtual black box).這種安全定義除了電路輸出其他信息都不泄露.但是,Barak 等人在文章中表示, 虛擬黑盒混淆不具有通用構(gòu)造方案, 即存在一類函數(shù)無法達(dá)到虛擬黑盒混淆安全.同篇文章中提出了一種弱化的混淆方案, 稱為不可區(qū)分混淆(indistinguishability obfuscation).不可區(qū)分混淆是指兩個規(guī)模相同、功能相同的電路在混淆后不可區(qū)分, 而且保留其功能性.Garg 在2016 年[4]提出第一個利用多線性映射構(gòu)造通用不可區(qū)分混淆的方案.之后, Bitansky 等人[5]和Ananth 等人[6]又分別使用公鑰和私鑰函數(shù)加密構(gòu)造不可區(qū)分混淆.Lin 等人[7–10]在此基礎(chǔ)上, 利用低維的多線性映射(最低完成維度為3 的) 構(gòu)造函數(shù)加密從而完成不可區(qū)分混淆的構(gòu)造.但是現(xiàn)有文章中構(gòu)造的多線性映射方案均存在不同程度的安全性問題, 以及效率低下的缺點, 利用安全的密碼原語構(gòu)造高效的通用不可區(qū)分混淆方案依然是很多學(xué)者的研究重點.

混淆電路最初是由 Yao 在 1986 年[11]為解決安全兩方計算而提出的一種電路加密技巧.之后, 由Goldreich 等人[12]將此方案中兩個參與者擴展為多個.但是, 混淆電路一直是以協(xié)議中一種處理技巧進行描述, 沒有獨立的定義和證明.直到 2008 年, Lindell 等人[13]在對 Yao 的方案進行安全證明中第一次提出了混淆電路方案, 將混淆電路提取成一個獨立的方案.之后, 2012 年, Bellare 等人[14]給出混淆電路具體的形式化定義, 以及隱私性、健忘性、可靠性等安全定義.此項工作奠定了混淆電路做為一項獨立的密碼方案的基礎(chǔ).Hemenway 等人[15]在 2016 年提出自適應(yīng)安全的混淆電路方案.但是, 這些混淆電路的方案均有一個缺點——不可重用.可重用的混淆電路是否存在這個問題困擾了學(xué)者三十多年, 直到2013年, Goldwasser 等人[16]利用全同態(tài)加密以及基于屬性的加密方案構(gòu)造了第一個可重用的混淆電路方案.之后, Wang 等人[17]又對此進行改進, 舍棄原方案的安全性等級, 利用隨機線性碼構(gòu)造的混淆電路替換Goldwasser 方案中的全同態(tài)加密.然而這些可重用混淆電路方案都不高效, 是否存在更高效的可重用的混淆電路依然是人們關(guān)注的問題.除此之外, 可重用混淆電路是否可以構(gòu)造混淆也是一個待探索的問題.

從表面來看, 不可區(qū)分混淆和混淆電路存在很多相似的地方.比如說, 在功能上兩者都是對電路進行“加密” 以保護電路安全性為目的, 都要求 “加密” 后的電路保留其功能性.而在安全定義上, 不可區(qū)分混淆的不可區(qū)分性和混淆電路基于不可區(qū)分安全相似: 均要求功能相同、規(guī)模相同的電路在“加密” 后不可區(qū)分.

但是, 從已有的構(gòu)造方案來看, 混淆電路僅僅需要對稱加密方案和偽隨機函數(shù)即可完成構(gòu)造, 而不可區(qū)分混淆需要用到多線性映射這種效率不高且安全性不穩(wěn)定的工具.根據(jù)已有的實現(xiàn)方案對比, 不可區(qū)分混淆的方案在對于規(guī)模不超過100 的電路進行混淆需要的時間在小時級別[18–20], 而混淆電路抵抗半誠實的敵手可以達(dá)到每個門的平均加密時間為 10 微秒[21], 抵抗惡意的敵手可以達(dá)到每個門的平均加密時間為50 毫秒[22].也就是說, 現(xiàn)有的構(gòu)造方案, 混淆電路的效率遠(yuǎn)遠(yuǎn)高于不可區(qū)分混淆.

這兩者之間的效率差距如此之大, 使得我們開始思考不可區(qū)分混淆和混淆電路的區(qū)別到底在哪里？是否能夠利用現(xiàn)有的混淆電路去構(gòu)造不可區(qū)分混淆？如果不能, 屏障又在哪里？本文即是以這幾個問題為出發(fā)點, 對不可區(qū)分混淆和混淆電路進行研究.通過對定義、安全要求、應(yīng)用場景的分析, 得到兩者之間的區(qū)別與聯(lián)系.并試圖通過相互構(gòu)造, 為進一步的研究提供思路.

本文主要綜述基于混淆電路和混淆兩個密碼體制, 探索兩個密碼體制之間的區(qū)別與聯(lián)系.本文分為兩部分.第 2–4 節(jié)為第一部分, 首先介紹布爾電路, 接下來講混淆電路和混淆的語義定義、安全定義、構(gòu)造方案、應(yīng)用等; 第 5–6 節(jié)為第二部分, 主要講混淆電路與混淆的區(qū)別與聯(lián)系.首先探索混淆電路與混淆的區(qū)別, 從設(shè)計初衷、定義、安全要求、構(gòu)造難度等方面分析, 接下來探索混淆電路和混淆的相互構(gòu)造并分析難點所在, 為接下來的研究提供新思路.

2 布爾電路簡介

計算模型一般分為兩類, 一致性模型 (uniform models) 和非一致性模型 (non-uniform models).一致性模型包括單帶圖靈機(single-tape turing machines)、多帶圖靈機(multi-tape turing machines) 等,而非一致性模型包括布爾電路(boolean circuits)、接受建議的機器(machines that take advice).其中布爾電路是最為人們熟知的非一致性模型.布爾電路通過一些邏輯門操作完成函數(shù)的計算功能, 因此混淆和混淆電路對布爾電路的“加密” 即隱藏電路的門操作種類甚至電路邏輯圖.本節(jié)將對布爾電路這一計算模型進行簡單的介紹, 包括電路的定義與性質(zhì)、函數(shù)與電路之間的轉(zhuǎn)換、通用電路等.

2.1 電路的定義與性質(zhì)

布爾電路作為一種非一致性模型, 能夠為不同輸入規(guī)模的同一個函數(shù)設(shè)計不同的電路.而一個具體的布爾電路是一個有向無環(huán)圖, 其利用標(biāo)準(zhǔn)布爾操作與(∧)、或(∨)、非 (?) 作用到輸入的二進制串上產(chǎn)生輸出結(jié)果.而對于與和或操作, 要求點的入度為2, 對于非操作要求點的入度為1.其具體定義如下:

定義 1(布爾電路[23]) 對任意n∈N, 一個n輸入單輸出的布爾電路是具有n個源頂點和m個匯頂點的有向圖.其中:

? 源頂點也稱輸入頂點, 指的是入度為0 的頂點.匯頂點也稱輸出頂點, 指的是出度為0 的頂點.

? 每個非源頂點稱為一個邏輯門, 并用邏輯操作∧(與)、∨(或)、?(非) 中的一個操作進行標(biāo)記.

? 頂點的扇入度指的是進入該頂點的邊的條數(shù).標(biāo)記為∧和∨的頂點的扇入度等于2, 而標(biāo)記為?的頂點的扇入度等于1.

? 布爾電路C的規(guī)模 (或大小) 是C中頂點的個數(shù), 記為 |C|.

? 如果C是一個布爾線路而x∈{0,1}n是它的一個輸入, 則將C在x上的輸出記為C(x),C(x)可以自然的定義如下.形式上, 我們?yōu)镃中每個頂點v定義輸出值val(v): 如果v是第i個源頂點, 則定義 val(v) =xi; 否則, val(v) 遞歸的定義為將頂點v上的邏輯操作作用于v的所有入邊關(guān)聯(lián)的頂點的輸出值上得到的結(jié)果.C(x) 是C的輸出頂點的值.

在實際構(gòu)造過程中, 由于非門可以和與門、或門進行合并.例如電路?x1∧x2可以看作一個門電路g(x1,x2)=?x1∧x2.如果將電路中的非門均進行此修改, 那么布爾電路中所有邏輯門將被看作一個二元函數(shù)g: {0,1}×{0,1} →{0,1}.統(tǒng)一的結(jié)構(gòu)便于設(shè)計加密方案, 因此若不做特殊說明, 文章中出現(xiàn)的邏輯門不再局限于與門、或門, 而是看作一個二元函數(shù).由于輸出長度為m的電路可以拆分為m個子電路.因此, 在構(gòu)造方案中一般考慮輸出長度為1 的電路.

布爾電路一旦選定, 有向無環(huán)圖的結(jié)構(gòu)也被確定下來.常見的可以使用一個六元組f=(n,m,q,A,B,G) 表示一個布爾電路[14].其中n? 2 表示輸入長度,m? 1 表示輸出長度,q? 1 表示門的個數(shù).輸入頂點有n個, 每個門對應(yīng)一個頂點, 則圖中頂點共有n+q個.將輸出均用門頂點表示, 因此有向無環(huán)圖中共有r=n+q條線, 令輸入 (頂點) 標(biāo)記為 Inputs = {1,··· ,n}, 線 (邊) 標(biāo)記為 Wires = {1,··· ,n+q}, 輸出 (邊) 標(biāo)記為 OutputWires = {n+q?m+1,··· ,n+q}, 門 (頂點) 標(biāo)記為 Gates = {n+1,··· ,n+q}.A、B、G均為函數(shù).A: Gate → WiresOutputWires 輸出每個門的第一條輸入線標(biāo)號.B: Gate → WiresOutputWires 輸出每個門的第二條輸入線標(biāo)號.G:Gates×{0,1}2→{0,1} 表示門計算, 即表示門的種類.

布爾電路的規(guī)模是指其邏輯門的個數(shù), 記作|C|.另外一個衡量布爾電路計算規(guī)模的參數(shù)是深度.布爾電路的深度是指從輸入頂點到輸出頂點最長一條路的長度, 記作 depth(C).電路規(guī)模衡量一個電路的大小, 電路深度衡量的是一次計算需要的時間.

2.2 電路與函數(shù)

作為非一致性模型, 單個電路很難衡量一個問題的復(fù)雜度.因此, 將不同輸入長度的電路放入一個集合中, 以集合為單位即可描述一個任意輸入長度的問題.將不同輸入長度的電路放入一個集合中, 這樣的形式稱為電路簇.電路簇的形式化定義如下:

定義 2(電路簇[24]) 設(shè)T:N →N 是一個函數(shù),T(n) 規(guī)模的電路簇是一系列布爾電路 {Cn}n∈N, 其中Cn有n個輸入位和一個輸出位, 并且其規(guī)模 |Cn|T(n) 對任意n成立.

將同一問題的不同輸入規(guī)模的電路放入集合也可構(gòu)造一個電路簇, 這樣的電路簇 {Cn}n∈N可以計算一個函數(shù)f: {0,1}?→{0,1}?.若函數(shù)f輸入x, 從電路簇中選取電路C|x|用來計算C|x|(x).因此, 利用電路簇的規(guī)模復(fù)雜度可以度量函數(shù)的復(fù)雜度.電路簇的規(guī)模復(fù)雜度定義為函數(shù)s:N →N, 其中s(n) 是電路Cn的規(guī)模.函數(shù)f的電路復(fù)雜度 (circuit complexity), 記作sf, 是指能計算f的最小規(guī)模電路簇的規(guī)模復(fù)雜度.其形式化定義如下:

定義 3(電路復(fù)雜度[24]) 函數(shù)f: {0,1}?→ {0,1}?的電路復(fù)雜度定義為函數(shù)sf: N → N, 其中sf(n) 表示將f限定為n比特輸入串時, 能計算f的最小電路.

根據(jù)電路深度和電路規(guī)模, 可以將電路簇分為不同的 NCd類.最常用的為 NC0和 NC1兩類, 即深度為常數(shù)規(guī)模和對數(shù)規(guī)模的電路.Barrington[25]提出任意一個深度為d的電路都可以轉(zhuǎn)化為一系列大小為5×5、數(shù)量為4d的矩陣相乘形式的矩陣分支程序.這種方法稱為Barrington 定理.根據(jù)此定理, NC1級別的電路可以轉(zhuǎn)化為多項式規(guī)模的矩陣分支程序, 將電路的“加密” 轉(zhuǎn)化為對矩陣的“加密”.

定義 4(NC 類[24]) 對于任意d, 如果存在判定問題L的電路簇{Cn} 使得Cn的規(guī)模為poly(n) 且深度為O(logdn), 則稱L屬于 NCd類.

電路簇使得布爾電路對于輸入規(guī)模的限制放開, 成為了聯(lián)系一致性模型和非一致性模型的紐帶.如果給定n, 可以在 poly(n) 時間內(nèi)構(gòu)造出電路Cn, 那么此多項式規(guī)模的電路簇 {Cn}n∈N被稱為是一致的.一個函數(shù)可以由一致的多項式規(guī)模電路簇計算, 那么它可以由多項式時間算法計算.這個算法首先構(gòu)造出一個電路, 然后對給定輸入計算電路的輸出.因此, 多項式規(guī)模電路簇可以求解的判定問題屬于P/poly.

2.3 通用電路

將不同輸入規(guī)模的電路放入集合中稱為電路簇, 那么將相同規(guī)模的電路整合為一個電路稱為通用電路.一個通用電路可以計算規(guī)模相同的任意一個電路, 通過增加對電路的描述作為輸入使得通用電路的輸出為不同電路的計算結(jié)果.通用電路與通用圖靈機相似, 將函數(shù)轉(zhuǎn)化為數(shù)據(jù)作為程序的輸入.因此, 通用電路的深度問題與圖靈機的時空轉(zhuǎn)換問題相關(guān)[26].

若將一個函數(shù)的表述加到電路的輸入中, 使得電路的輸出結(jié)果等于函數(shù)的計算結(jié)果, 這樣的電路稱為通用電路 (universal circuits).通用電路可以計算規(guī)模相同的任意一個電路.即對任意一個通用電路UC(x,p), 輸入任意一個規(guī)模為n的電路C的描述p以及此電路的輸入x, 得到UC(x,p)=C(x).

valiant 在 1976 年[26]提出了一種有效的通用電路構(gòu)造方案.有效的是指通用電路的規(guī)模和深度是多項式級別擴展的.而valiant 的方案對電路規(guī)模為k的電路構(gòu)造的通用電路規(guī)模為O(klogk), 深度為O(k).Cook 等人在 1 985 年[27]提出了深度是線性的、規(guī)模為的通用電路構(gòu)造方案.之后又不斷有學(xué)者提出優(yōu)化的構(gòu)造方案[28–31].通用電路可以有效的隱藏計算電路的拓?fù)浣Y(jié)構(gòu), 因此在很多密碼方案中均有應(yīng)用.

3 混淆電路

混淆電路對于安全多方計算的意義重大, 而 Yao 構(gòu)造安全多方計算常用的混淆電路一直被看作一種構(gòu)造方法.直到 2012 年, 混淆電路才作為一個獨立的密碼方案出現(xiàn), 隨之給出其語義定義、安全定義等.本節(jié)將對混淆電路做出詳細(xì)地介紹.首先3.1 節(jié)整理對混淆電路的語義定義, 以及選擇性安全、適應(yīng)性安全、基于模擬安全、基于不可區(qū)分安全等不同安全級別的安全定義.此外簡單介紹一些混淆電路的性質(zhì)或擴展.接下來在3.2 節(jié)說明經(jīng)典的Yao 構(gòu)造混淆電路方案以及一些優(yōu)化方案.最后將簡述混淆電路的不同應(yīng)用場景.

3.1 語義定義及安全定義

混淆電路起源于Yao 在1982 年和1986 年[11,32]提出的關(guān)于安全兩方計算協(xié)議的構(gòu)造之中.在文章中, Yao 構(gòu)造一個安全兩方計算協(xié)議來解決著名的大富翁問題, 即有兩個大富翁Alice 和Bob, 他們想要在不泄露自己具體財富值的情況下得知誰更富有.這個問題相當(dāng)于對一個比較兩輸入大小的電路進行加密, 使得每個人都可以得到最終結(jié)果并且無法獲取他人的輸入.隨后在 1987 年, Glodreich 等人[12]具體描述了基于Yao 的方法構(gòu)造安全兩方計算協(xié)議.而Beaver 等人[33]則在1990 年首次提出混淆電路的定義.在1999 年, Naor 等人[34]利用偽隨機函數(shù)構(gòu)造混淆電路并應(yīng)用到隱私保護的拍賣過程中.

2008 年, Lindell 等人[13]在證明 Yao 的兩方安全計算協(xié)議中, 利用形式化的語言描述了混淆電路的構(gòu)造過程.2012 年, Bellare 等人[14]首次給出嚴(yán)謹(jǐn)?shù)男问交x和安全性定義.Bellare 等人提出的形式化定義中, 一個混淆電路方案由五個子函數(shù)組成GC = (Gb,En,Ev,De,ev), 分別用做混淆電路、加密輸入、計算輸出、解密輸出以及函數(shù)計算.除了混淆電路函數(shù)Gb 和加密輸入函數(shù) En 外, 計算函數(shù)Ev 和解密函數(shù)De 經(jīng)常看作一個函數(shù)使用, 而ev 函數(shù)是原始函數(shù)在未加密狀態(tài)下的計算過程.因此, 學(xué)者們普遍使用的混淆電路的定義是簡化后的三元組函數(shù)G=(Gb,En,Ev).

定義 5(混淆電路) 一個混淆電路方案可以看作一個三元組算法G= (Gb,En,Ev), 每個算法的功能如下:

? Gb(1λ,C) →(F,k).此算法用來對電路C進行加密.輸入函數(shù)C和安全參數(shù)k, 輸出 (F,k) 表示加密后的電路F以及一個密鑰k.

? En(k,x)→X.此算法用來加密輸入.輸入函數(shù)C的輸入x以及加密密鑰k, 加密得到輸入的密文X.

? Ev(F,X) →Y.此算法用來在密文狀態(tài)下計算電路C.輸入加密后的函數(shù)F以及加密后的輸入X, 得到輸出Y=f(x).

此定義要求滿足正確性, 即對于任意電路C和輸入x, 都有

混淆電路的安全定義分為四種: 基于模擬的選擇性安全, 基于不可區(qū)分的選擇性安全, 基于模擬的自適應(yīng)安全和基于不可區(qū)分的自適應(yīng)安全[15].基于模擬和基于不可區(qū)分是指在敵手區(qū)分加密函數(shù)的能力,而選擇性安全和自適應(yīng)安全則是要求敵手是否可以根據(jù)加密后電路選取輸入.四種安全定義分別對應(yīng)一個游戲SimSel, IndSel, SimAda, IndAda 如圖1 所示.四種安全的成立要求在對應(yīng)游戲中, 敵手區(qū)分的能力優(yōu)勢可忽略, 即

除此之外, 混淆電路還有一些其他相關(guān)的性質(zhì)特點.

圖1 SimSel, IndSel, SimAda, IndAda 游戲過程Figure 1 Game of SimSel, IndSel, SimAda and IndAda

首先是關(guān)于函數(shù)f的輔助函數(shù)——側(cè)信息函數(shù).加密的過程中, 雖然電路和輸入在符合安全定義情況下都得到了不同程度的保護, 但是不可避免地還是會產(chǎn)生一些關(guān)于明文的額外信息的泄露.我們稱這種關(guān)于明文的額外信息為側(cè)信息[14].側(cè)信息函數(shù)Φ(f) 就是用來表示對函數(shù)f的側(cè)信息泄露.常用的側(cè)信息函數(shù)有三種, 分別為 Φsize, Φtopo, Φcirc.其中 Φsize表示泄露函數(shù)f的電路大小, 包括輸入輸出長度、門的個數(shù)等信息.Φtopo表示泄露函數(shù)f的電路拓?fù)鋱D, 相當(dāng)于敵手可獲取到將輸入和輸出以及所有門看作圖的頂點, 電路的連接線看作圖的邊所構(gòu)成的有向無環(huán)圖.Φcirc則表示泄露函數(shù)f的整個電路圖, 即僅僅保護輸入而電路是公開的.側(cè)信息函數(shù)有利于將加密后所隱藏的信息和泄露的信息形式化的表示, 從而更加清晰地表現(xiàn)了加密函數(shù)功能性和信息隱藏的能力.一般來說, 對于側(cè)信息為Φtopo的混淆電路方案可借助于通用電路轉(zhuǎn)化為側(cè)信息為Φsize的混淆電路方案.

由于傳統(tǒng)的基于Yao 的加密函數(shù)方案都有一個通病, 即混淆電路的一次性.若多次使用不同的輸入計算混淆電路, 那么隱藏的電路信息和輸入信息將被泄露.因此, 有學(xué)者提出可重用混淆電路[16], 即對加密后的電路F, 可以使用多個不同的輸入計算 En(k,x) →X, 且不泄露電路和輸入的信息.此外, 如果加密輸入X的每個比特僅與輸入x的一個比特相關(guān), 那么我們稱此混淆電路是投射的[35].

3.2 常見構(gòu)造方法

2008 年, Lindell 等人[13]在證明 Yao 的安全兩方計算協(xié)議中, 描述了混淆電路的構(gòu)造過程.完整的構(gòu)造是從加密一個門開始到加密整個電路.假設(shè)g是布爾電路C的一個門, 那么g可以表示為一個函數(shù)g:{0,1}×{0,1}→{0,1}.其中兩個輸入線標(biāo)記為ω1,ω2, 輸出線標(biāo)記為ω3.隨機生成六個密鑰分別表示三條線的輸入為 0 和 1 兩種情況.接下來, 門g將會利用一個對稱加密方案E產(chǎn)生四個密文c0,0,c0,1,c1,0,c1,1.具體構(gòu)造方法如圖2 所示.

圖2 Yao 的混淆電路構(gòu)造方案Figure 2 Construction of garbled circuits from Yao

將四個密文進行一個隨機置換即得到門g的加密表c0,c1,c2,c3.在計算門g的時候, 利用對應(yīng)的密鑰解密c0,c1,c2,c3, 如果某個解密結(jié)果不是⊥, 那么得到的結(jié)果即為有了對一個門的加密方案之后, 對整個電路進行類似的加密方法, 即可得到整個加密方案.在Bellare 等人給出混淆電路的形式化定義后, 對于此種構(gòu)造方法可利用雙密鑰加密方案加密, 即可實現(xiàn)基于安全的密碼原語構(gòu)造混淆電路的工作.這些構(gòu)造均為選擇性安全的.2016 年, Hemenway 等人[15]提出了基于模擬自適應(yīng)安全的混淆電路, 通過對輸入密鑰進行對稱加密, 完成了由選擇性安全到自適應(yīng)安全的轉(zhuǎn)化.Jafargholi 等人[36]在此基礎(chǔ)上構(gòu)造了基于不可區(qū)分的自適應(yīng)安全混淆電路.

四個密文若按照真值表的順序公布可能會泄露信息.為了安全著想, 需要將四個密文c0,c1,c2,c3進行隨機置換.Beaver 等人[33]提出一種Point-and-permute 技術(shù)來優(yōu)化這一過程.在每條線的密文中都設(shè)置一個隨機的置換比特.的置換比特相反且沒有對應(yīng)關(guān)系, 即中置換比特與b無關(guān).而對于四個密文則可以用兩個密鑰的置換比特進行標(biāo)記, 這樣既不泄露信息而且在解密時僅需解密對應(yīng)置換比特的密文.這樣的話, 對稱加密方案也可替換為一個簡單的一次性加密方案其中H是一個帶種子的偽隨機函數(shù).Naor 等人[34]在此基礎(chǔ)上提出若適當(dāng)?shù)倪x擇可以使得置換比特對應(yīng)的第一個密文變?yōu)槿珵榱愕淖址? 這樣只需傳輸三個密文即可.

除此之外,Kolesnikov 和Schneider 在2008 年[37]提出了Free-XOR 技術(shù).Free-XOR 技術(shù)是選定一個共同的秘密值?∈{0,1}λ,此秘密值全局唯一.對于每條線的標(biāo)簽的選擇需滿足即這種構(gòu)造方式的優(yōu)點是對于異或門計算的簡化.若電路中存在異或門g= (ω1,ω2,ω3),那么無需再進行加密計算僅需直接計算即可.因此, 混淆電路僅需對非異或門僅需對稱加密即可, 實現(xiàn)了效率上的提高.這項技術(shù)還被Ball 等人[38]應(yīng)用在算術(shù)電路中, 使得在 Zm上加法和數(shù)乘的計算優(yōu)化.類似于Free-XOR 技術(shù), 首先選擇一個公共秘密值將每條線的標(biāo)簽設(shè)為其中是 Zm上的向量.因此, 對于加法計算滿足對于數(shù)乘計算滿足使得在算術(shù)電路中加法門和數(shù)乘門的計算簡化.

而 Zahur 等人在 2015 年的 EUROCRYPT 會議上提出了一種名為半門的設(shè)計思路[39], 此方法在Free-XOR 的基礎(chǔ)上減少了與門的密文數(shù)量.假設(shè)電路中存在一個與門ω3=ω1∧ω2, 且利用 Free-XOR技術(shù)給出每條線的標(biāo)簽為若按照原來的方案需要至少3 個密文的傳輸, 而半門的處理可以使密文數(shù)量減少到2 個.具體方法如下: 在加密過程中, 生成者隨機選擇一個比特r, 那么有ω3=ω31⊕ω32=(ω1∧r)⊕(ω1∧(r⊕ω2)).首先來看ω31=ω1∧r, 生成者已知r的取值, 可生成密文接下來考慮ω32=ω1∧(r⊕ ω2), 生成者可以公布r⊕ ω2的標(biāo)簽給對方 (并不泄露和b之間的關(guān)系).此時計算方可得到對應(yīng)的r⊕ω2的值, 因此生成者產(chǎn)生兩個密文當(dāng)r⊕ω2為 0 時, 計算方可根據(jù)第一個密文得到當(dāng)r⊕ω2為1 時, 計算方可根據(jù)第二個密文得到再與實際輸入的進行異或操作即可得到由于此方案基于Free-XOR, 因此使用四個密文計算ω31和ω32再進行異或操作也可完成對與門ω3=ω1∧ω2的加密, 再利用 Naor 等人的方法[34]對每對密文中第一個密文轉(zhuǎn)化為全零, 那么最終只需要傳輸兩個密文即可計算一個與門.此方法大大提高了與門的加密速度和計算速度.

3.3 應(yīng)用

混淆電路從 1986 年發(fā)展至今, 依然有大量學(xué)者為之努力和探索, 可見混淆電路強大的實用性和對密碼學(xué)的重要性.2006 年, Malkhi 等人[21]根據(jù) Yao 的方案構(gòu)造了一個安全兩方計算系統(tǒng)——Fairplay.作者對系統(tǒng)進行了測試, 64 比特輸入的大富翁游戲需要 254 個門計算, 一次計算需要大約 4 s 時間.從Fairplay 中看到混淆電路的計算時間較短, 效率較高, 可應(yīng)用在很多現(xiàn)實場景中.此小節(jié)將對混淆電路的應(yīng)用進行綜述.混淆電路起源于安全兩方計算, 之后被推廣到安全多方計算中去.除了在安全計算中的應(yīng)用, 混淆電路還在一次性編程(one-time program)[40]、可驗證計算、同態(tài)計算、函數(shù)加密甚至不可區(qū)分混淆的構(gòu)造中均有應(yīng)用.

安全兩方計算安全兩方計算分為兩種——SFE (secure function evaluation) 和PFE (private function evaluation).SFE 是指Alice 和Bob 兩個人均知道函數(shù)的功能, 而各自持有一部分輸入, 要求在計算過程中不泄露自己持有的輸入.PFE 是指Alice 和Bob 一方持有函數(shù), 一方持有輸入, 要求在計算過程中不泄露自己持有的輸入或函數(shù).由于通用函數(shù)的存在, 使得SFE 協(xié)議中構(gòu)造一個通用電路UC 是兩方均知道的, 再將持有函數(shù)的一方的函數(shù)描述作為通用電路的輸入進行計算.因此, 對于PFE 的計算可以歸結(jié)到SFE 的計算上.最早的SFE 方案是Yao 在1986 年提出的[11], 利用混淆電路和不經(jīng)意傳輸(oblivious transfer)[41]完成交互輪數(shù)為4 且敵手是誠實但好奇的安全兩方計算要求.不經(jīng)意傳輸是指A 有一對消息想要傳遞給B 其中一個, 但是 B 不希望A 知道他獲取的是哪一個, 而 A 希望B 僅獲取一個消息.不經(jīng)意傳輸和混淆電路構(gòu)成現(xiàn)有安全兩方計算的兩大基礎(chǔ)工具.SFE 通過混淆電路實現(xiàn)對計算過程的保密而通過不經(jīng)意傳輸保證輸入的隱私性.Goldwasser 等人[12]利用零知識證明系統(tǒng)將Yao 的方案擴展為可抵抗惡意的敵手.但是這種轉(zhuǎn)化是低效率的, 因此學(xué)者們[38,42–44]對利用混淆電路構(gòu)造更高效的抵抗惡意敵手安全兩方計算進行探索.還有學(xué)者為了追求高效, 定義相對弱的安全兩方計算協(xié)議[35,45,46].除此之外, Wang 等人[47,48]提出了帶認(rèn)證的混淆電路方案用以構(gòu)造高效的抵抗惡意敵手的安全兩方計算方案.

其他應(yīng)用安全多方計算是安全兩方計算的擴展,因此混淆電路在安全多方計算中也有廣泛的應(yīng)用[49].如: Patra 等人[50]構(gòu)造的安全三方計算, 以及一系列利用混淆電路作為基礎(chǔ)工具構(gòu)造的安全多方計算方案[44,51–53].Gennaro 等人[54]將混淆電路應(yīng)用在可驗證計算中, 而 Gentry 等人[55]則利用混淆電路進行同態(tài)計算.而在公鑰加密方案中的 KDM 安全[56,57]上, 混淆電路也能助一臂之力.除了在理論密碼學(xué)中的應(yīng)用之外, 混淆電路在現(xiàn)實生活中也有非常廣泛的應(yīng)用.首先混淆電路可以用在安全文本處理[58]中,其次在隱私保護拍賣[34]和隱私信用調(diào)查[59]中也使用到混淆電路.特別地, 混淆電路還可以用在隱私醫(yī)療診斷[60,61]中, 保護病人的隱私.

混淆電路由于其結(jié)構(gòu)簡單、快速高效的特點, 不僅在密碼學(xué)理論中有廣泛應(yīng)用, 還能在現(xiàn)實社會中有效保護個人隱私.混淆電路的強大功能性和廣泛的應(yīng)用場景引起了學(xué)者們的關(guān)注, 越來越多的學(xué)者為了構(gòu)造更加高效、更加安全、功能更加強大的混淆電路而開展研究工作.

4 混淆

混淆作為一個強大的密碼學(xué)工具, 其安全有效的構(gòu)造一直困擾著密碼界.在通用虛擬黑盒混淆被證明不存在之后, 學(xué)者們致力于通用不可區(qū)分混淆的構(gòu)造.但是, 目前通用不可區(qū)分混淆的構(gòu)造依然面臨著巨大問題.本節(jié)將對混淆進行詳細(xì)的介紹.首先4.1 節(jié)將概述包括虛擬黑盒混淆和不可區(qū)分混淆在內(nèi)混淆的語義定義和安全定義.此外還定義一些其他的混淆概念, 包括非一致輸入混淆、簡潔的混淆等.4.2 節(jié)簡述現(xiàn)有的不可區(qū)分混淆的通用構(gòu)造方案, 主要分為用多線性映射直接構(gòu)造和用函數(shù)加密構(gòu)造兩種方法.最后,介紹混淆的應(yīng)用.

4.1 語義定義及安全定義

混淆, 即將任意一個電路在保持其功能的前提下進行“加密”, 使得混淆后的電路 “不可讀”, 達(dá)到保護電路內(nèi)部信息的目的.也就是說, 混淆相當(dāng)于將程序或者函數(shù)放入一個盒子中, 人們可以 “使用” 這個盒子, 但是不能“打開” 盒子.2001 年, Barak 等人[3]首次給出了具有虛擬黑盒安全混淆的形式化定義.虛擬黑盒混淆除了功能性和多項式規(guī)模擴展的要求之外, 還要求除了輸出其他信息都不泄露.也就是說, 調(diào)用混淆后的程序和使用預(yù)言機的效果相同.這是一個基于斷言的安全性極強的定義.

定義6(電路混淆) 一個概率多項式時間算法O可以看做是一個電路混淆, 需要滿足以下三個條件:

? (功能性) 對任意一個電路C,O(C) 表示的電路與電路C的功能相同.

? (多項式效率) 對任意一個電路C, 存在多項式P且滿足|O(C)|P(|C|).

? (“虛擬黑盒” 特性) 對任意一個概率多項式時間敵手A, 存在一個概率多項式時間模擬器S和一個可忽略函數(shù)α, 使得對任意一個電路C滿足

但是, 在Barak[3]和 Goldwasser 的文章中都有指出, 存在一類函數(shù)無法達(dá)到虛擬黑盒混淆.也就是說, 不存在通用的虛擬黑盒混淆方案.為了構(gòu)造通用的混淆方案, 學(xué)者們試圖對虛擬黑盒混淆的安全要求放寬, 使得通用構(gòu)造也保持具有實際意義的安全性.2007 年, Hohenberger 等人[62]提出了一個平均情況虛擬黑盒混淆的定義.而 D?ttling 等人在 2011 年[63]提出使用可信硬件中存儲全同態(tài)加密算法的解密密鑰來構(gòu)造基于硬件的程序混淆.但是, 不基于硬件假設(shè)的情況下, 直到2013 年才提出第一個通用混淆的方法.

Garg 等人[4]在2013 年提出了一個弱化的安全性定義——不可區(qū)分混淆, 并且給出了第一個通用不可區(qū)分混淆的構(gòu)造方案.不可區(qū)分混淆相較虛擬黑盒混淆, 僅要求對兩個功能相同, 規(guī)模相同的電路在混淆后不可區(qū)分.不可區(qū)分混淆雖然比虛擬黑盒混淆安全性較弱, 但是具有通用構(gòu)造.通用不可區(qū)分混淆的出現(xiàn), 使得密碼界許多待解決的問題出現(xiàn)了新的解決方案.因此, 不可區(qū)分混淆的強大引得學(xué)者們頻頻回顧.

定義 7(不可區(qū)分混淆) 一個一致的概率多項式算法iO被稱為一個對電路簇{Cλ} 的不可區(qū)分混淆,需要滿足以下兩個條件:

? 對任意安全參數(shù)λ∈N, 任意電路C∈Cλ以及任意輸入x, 有

? 對任意概率多項式區(qū)分器D, 存在一個可忽略函數(shù)α, 滿足要求: 對任意安全參數(shù)λ∈N, 任意電路對C0,C1∈Cλ, 且滿足C0(x)=C1(x), 那么有

在構(gòu)造混淆的過程中, 也構(gòu)造了一些具有特殊性質(zhì)的混淆.非一致輸入混淆 (differing-inputs obfuscation)[64]是不可區(qū)分混淆的一種變形, 此定義不再要求兩個電路功能相同, 允許兩個電路存在相同輸入且輸出不同, 但是找到這個輸入的概率可忽略.非延展混淆 (non-malleable obfuscation)[65]是指從一個函數(shù)混淆結(jié)果不可以得到關(guān)于另一個相關(guān)函數(shù)的混淆.簡潔的(succinct) 混淆[66]是指混淆后的電路規(guī)模與原電路規(guī)模無關(guān), 僅與輸入長度、安全參數(shù)等相關(guān).

除了對電路的混淆, 有學(xué)者對于其他計算模型的混淆也展開了研究, 包括對圖靈機的混淆, 對 RAM的混淆等等.對于圖靈機的混淆, 由于 Pippenger 等人[67]證明任意一個圖靈機都可轉(zhuǎn)化為一個電路, 因此對圖靈機的混淆將歸結(jié)到對電路的混淆.但是 Pippenger 等人的轉(zhuǎn)換方法使得電路規(guī)模不僅與圖靈機的規(guī)模相關(guān), 還與圖靈機的計算時間和內(nèi)存占用相關(guān), 近期的文章[68–70]著重于研究構(gòu)造混淆電路規(guī)模僅與圖靈機規(guī)模相關(guān)的方案, 構(gòu)造常數(shù)級乘法界定的圖靈機混淆方案, 即混淆后的電路規(guī)模僅與原始電路規(guī)模線性相關(guān).

4.2 常見構(gòu)造方法

現(xiàn)有的對于任意P/poly 電路的通用不可區(qū)分混淆的構(gòu)造方法主要分為兩種.一種是由Garg 等人[3]在2013 年提出的, 使用多線性映射和分支程序?qū)C1電路完成不可區(qū)分混淆, 再利用自舉技術(shù)構(gòu)造對任意多項式級別電路的混淆.另一種方法是Bitansky 等人[5]和Ananth 等人[6]分別提出的利用公鑰的和私鑰的函數(shù)加密構(gòu)造對任意多項式級別電路的通用不可區(qū)分混淆.

第一種構(gòu)造方法如圖3 所示,第一步利用多線性映射等基礎(chǔ)工具構(gòu)造對NC1電路的不可區(qū)分混淆.首先, Barrington[25]提出任意一個深度為d的電路都可以轉(zhuǎn)化為一系列大小為5×5、數(shù)量為 4d的矩陣相乘形式的矩陣分支程序.這種方法稱為Barrington 定理.使用此方法將NC1電路轉(zhuǎn)化成矩陣相乘的形式, 并對矩陣進行填充隨機數(shù)和 Kilian 的隨機矩陣相乘[71]的方法, 實現(xiàn)分支程序隨機化.為了抵抗部分輸入攻擊, 再進行乘法綁定(multiply bunding).最后, 為了抵抗其他非線性攻擊手段, 利用多線性映射或者由多線性映射構(gòu)造的分級編碼程序就行編碼, 即完成了對任意NC1電路的不可區(qū)分混淆方案.

得到NC1電路的不可區(qū)分混淆方案后, 再利用自舉技術(shù)構(gòu)造對任意多項式級別電路的不可區(qū)分混淆.自舉技術(shù)如圖4 所示, 利用對全同態(tài)加密技術(shù)的解密算法進行 NC1級別的混淆從而完成對任意多項式電路的混淆.具體來說, 首先利用全同態(tài)加密構(gòu)造兩對公私鑰, 并分別對任意多項式規(guī)模電路C進行加密,得到(g1,PK1,g2,PK2).再構(gòu)造一個NC1級別的電路PSK2,g1,g2.此電路的功能為: 輸入密文與非交互式承諾不可區(qū)分證明.如果對此承諾驗證通過, 則用 SK1解密密文, 否則終止.對此電路進行 NC1級別的混淆得到最終的對任意多項式規(guī)模電路C的不可區(qū)分混淆:

圖3 Garg 提出的通用混淆構(gòu)造方案Figure 3 Construction of iO from Garg

圖4 P/poly 電路混淆過程Figure 4 Construction of P/poly circuits’ obfuscation

另一種方法則是利用簡潔的或者緊致的函數(shù)加密方案完成對任意多項式電路的通用不可區(qū)分混淆的構(gòu)造.簡潔的是指函數(shù)加密中加密電路的大小是poly(n,λ), 即關(guān)于輸入電路的規(guī)模n和安全參數(shù)λ的多項式規(guī)模擴展.Bitansky 和 Vaikuntanathan[5]利用對稱加密方案和簡潔的公鑰函數(shù)加密方案按混淆電路的輸入比特數(shù)遞歸定義了對任意多項式規(guī)模電路的不可區(qū)分混淆構(gòu)造.對輸入長度為i的電路Ci, 首先利用兩次對稱加密方案加密電路Ci得到CT0和CT1, 并構(gòu)造新函數(shù):

通過將輸入xi的最后一位拆分為0 和1 兩種情況完成遞歸定義需要接下來混淆的輸入長度為i?1 比特的函數(shù).這種構(gòu)造方法是遞歸定義的, 因此要求函數(shù)加密是簡潔的.

而 Ananth 和 Jain[6]則是利用緊致的公鑰函數(shù)加密方案構(gòu)造對任意多項式電路的不可區(qū)分混淆方案.緊致的(compact) 是指函數(shù)加密的加密函數(shù)的運行時間必須是關(guān)于安全參數(shù)和輸入長度多項式時間.第一步利用歸納的思想由c元輸入的函數(shù)加密方案 (FEc) 構(gòu)造c+1 元輸入的函數(shù)加密方案 (FEc+1).利用一個緊致的公鑰函數(shù)加密 FE 的 KeyGen 函數(shù)加密c+1 元函數(shù)f, 生成 FEc+1.skf.并構(gòu)造電路G如圖5 所示.若 FEc+1.Enc 函數(shù)接收到輸入為 (msk,x,1) 時, 利用 FEc.KeyGen 函數(shù)加密電路G得到 FEc.skG; 若 FEc+1.Enc 函數(shù)接收到輸入為 (msk,x,i) 且 2ic+1 時, 利用c元函數(shù)加密的FEc.Enc 函數(shù)加密 (x,x,1,τ,i) 即可.由此可構(gòu)造任意元輸入的函數(shù)加密方案, 再通過 Goldwasser 等人[72]的方法構(gòu)造不可區(qū)分混淆.首先通過以輸入比特長度為單位遞歸構(gòu)造多輸入函數(shù)加密方案.多輸入的函數(shù)加密方案如果滿足輸入為n+1 元, 那么對輸入為n比特的電路C混淆, 只需構(gòu)造通用電路U(x1,··· ,xn,C)=C(x1,··· ,xn) 并將x1,··· ,xn和C當(dāng)作多輸入函數(shù)加密的n+1 元輸入進行加密.

由于緊致的和簡潔的函數(shù)加密方案的構(gòu)造都需要用到多線性映射.其他不可區(qū)分混淆的構(gòu)造方案也均需要多線性映射的幫助.因此目前通用不可區(qū)分混淆的構(gòu)造依然離不開多線性映射.而多線性映射在 2003 年由 Boneh 和 Silverberg 提出[73].之后相繼提出的多線性映射方案 GGH13[74]、CLT13[75]、GGH15[76]等, 不僅效率不高, 安全性還受到了不同程度的攻擊[77–81].因此是否存在安全高效的多線性映射方案還不得而知[82,83].除此之外, 利用Garg 等人的方法需要的多線性映射維度為多項式級別的, 降低多線性映射維度也成為學(xué)者優(yōu)化不可區(qū)分混淆構(gòu)造的一個方向.2015 年, Zimmerman 提出對算術(shù)電路直接進行混淆[66], 從而避免了分支程序帶來的多線性映射維度的增加, 使得多線性映射的操作數(shù)量從深度d指數(shù)級別降為多項式級別.2017 年, Lin 等人[7–10]將不可區(qū)分混淆的構(gòu)造需要的多線性映射維度從多項式降到常數(shù)階, 之后通過構(gòu)造特別的偽隨機生成器使得多線性映射維度降低到3.尋找高效安全的三線性映射去構(gòu)造不可區(qū)分混淆稱為新的問題.三線性映射甚至多線性映射的發(fā)展也直接影響到不可區(qū)分混淆的發(fā)展.因此, 越來越多的學(xué)者試圖跨越從三線性映射到雙線性映射的鴻溝或者拋棄之前的構(gòu)造方法,利用已有的安全的密碼原語, 尋求更有效可行的構(gòu)造方案.

圖5 電路G 的具體內(nèi)容Figure 5 Details of circuit G

4.3 應(yīng)用

混淆之所以受到如此廣泛的關(guān)注和研究, 是因為混淆其強大的功能性.混淆不僅僅是實現(xiàn)了保護函數(shù)“內(nèi)容” 的目的, 還解決了許多困擾密碼學(xué)界多年的問題.本節(jié)將對不可區(qū)分混淆在密碼學(xué)中的應(yīng)用進行介紹, 包括對于函數(shù)加密方案, 多方密鑰協(xié)商方案, 自線性對方案等的構(gòu)造.

對通用電路構(gòu)造安全的函數(shù)加密方案一直是一個未解決困難問題, 大多數(shù)的構(gòu)造僅能實現(xiàn)內(nèi)積加密函數(shù)這樣簡單電路的函數(shù)加密方案.但是, Garg 在提出第一個通用不可區(qū)分混淆方案的文章中就提出了利用不可區(qū)分混淆構(gòu)造對于任意多項式規(guī)模電路的函數(shù)加密方案.由于函數(shù)加密要求對函數(shù)輸入的保護, 此方案需要構(gòu)造一個特殊函數(shù)Pf,sk1,CRS(e1,e2,π)=f(x) 用以解密加密后的輸入并進行計算.此函數(shù)將計算函數(shù)f, 一個公鑰加密方案的私鑰 sk1以及零知識證明的參數(shù) CRS 作為固定參數(shù), 輸入使用公鑰 pk1加密輸入x的密文e1和公鑰pk2加密輸入x的密文e2以及一個零知識證明π, 此證明表明e1和e2是合法構(gòu)造的.當(dāng)函數(shù)P得到輸入后, 先驗證證明π是否有效, 若有效則使用私鑰sk1解密e1得到輸入x,最后計算f(x).將函數(shù)P混淆后的程序作為函數(shù)加密函數(shù)KeyGen(msk,f) 的輸出skf, 而函數(shù)加密函數(shù) Enc(mpk,x) 則使用公鑰加密x得到e1和e2并構(gòu)造其零知識證明π作為輸出c= (e1,e2,π).這樣就保證了函數(shù)加密需要的對輸入加密的安全要求.因此, 使用不可區(qū)分混淆可以構(gòu)造選擇性不可區(qū)分安全的函數(shù)加密方案.

非交互無需可信第三方的多方密鑰協(xié)商方案也是密碼學(xué)的一個難題.2014 年Boneh 等人[84]提出了使用混淆構(gòu)造無需可信第三方非交互的多方密鑰協(xié)商方案, 并且此方案每個成員公布的信息大小與總成員數(shù)量無關(guān).同樣地, 此構(gòu)造也依賴于構(gòu)造一個特殊的函數(shù)PE.此函數(shù)內(nèi)置一個偽隨機函數(shù)PRF, 在輸入成員集合S, 成員i公布的信息 pki(一個簽名方案的公鑰) 以及一個簽名σ之后, 首先驗證簽名正確性,若驗證通過, 那么輸出PRF(S,{pkj}) 作為協(xié)商的密鑰.每個成員i除了要生成自己的簽名私鑰ski和公布的簽名公鑰 pki之外, 還需要公布對函數(shù)PE的混淆程序iO(PE).在計算協(xié)商密鑰時, 成員j使用自己的私鑰skj對S進行簽名σi, 選取同一個iO(PE) (一般選擇最小號成員生成的混淆程序) 計算得到協(xié)商密鑰.這樣就完成了無需可信第三方的多方密鑰協(xié)商方案的構(gòu)造.

此外, Boneh 在此文章中還利用類似的技術(shù)實現(xiàn)了支持分布式初始化的廣播加密方案, 以及抗勾結(jié)的叛徒追蹤系統(tǒng)等方案的構(gòu)造.2014 年, Sahai 等人[85]利用混淆構(gòu)造了可否認(rèn)加密方案(deniable encryption).同年, Garg 等人[86]利用不可區(qū)分混淆構(gòu)造兩輪的安全多方計算模型.從這些應(yīng)用可以看出, 不可區(qū)分混淆在解決一些問題的關(guān)鍵在于構(gòu)造一個定制的函數(shù), 將需要隱藏的信息作為函數(shù)的固定參數(shù)或者利用函數(shù)判定某些性質(zhì), 再完成計算.將此定制的函數(shù)進行混淆, 達(dá)到隱藏信息和打包的作用.

除了以上提到的應(yīng)用方法之外, 2016 年, Yamakawa 等人[87]利用不可區(qū)分混淆構(gòu)造自線性對, 從而構(gòu)造安全的多線性映射.與其他應(yīng)用不同的是, 自線性對的構(gòu)造利用的是不可區(qū)分混淆中兩個功能相同、規(guī)模相同的函數(shù)在混淆后不可區(qū)分的關(guān)系.利用Blum 整數(shù)N構(gòu)造一個群在未知整數(shù)N分解的情況下無法求取群的階從而無法有效計算映射函數(shù)e(gx,gy) →gcxy.因此構(gòu)造一對功能相同的函數(shù)τy和其中τy←e(·,y) 而由于order 未知因此可以保護y不被泄露, 而τy則在order 未知的情況下可有效構(gòu)造.借助于不可區(qū)分混淆使得不可區(qū)分, 方案即可使用iO(τy) 既保證y的安全又能夠有效構(gòu)造.借助于不可區(qū)分混淆, Yamakawa 等人解決了自線性對的構(gòu)造問題.

可以看出, 不可區(qū)分混淆在密碼學(xué)中應(yīng)用廣泛.借助于其不可區(qū)分性以及對函數(shù)整體的打包和保護,不可區(qū)分混淆解決了很多密碼學(xué)中困擾許久的問題.

5 混淆電路與混淆的關(guān)系

從前兩節(jié)的介紹中可以看到, 不可區(qū)分混淆和混淆電路在安全定義上有很多相似之處.除此之外, 兩者在密碼學(xué)領(lǐng)域都占有重要地位, 具有強大的功能, 為其他密碼方案的構(gòu)造提供了有效的工具.但是, 從構(gòu)造中我們也發(fā)現(xiàn), 兩種方案的構(gòu)造方式天差地別, 并且效率也相差甚遠(yuǎn).因此, 我們在本節(jié)著重分析兩個密碼工具的區(qū)別與聯(lián)系, 探究其中的差距到底在哪里.在 5.1 節(jié), 我們分析傳統(tǒng)Yao 方式的混淆電路與通用混淆即不可區(qū)分混淆的關(guān)系.接下來, 我們將在5.2 節(jié)探索可重用混淆電路與不可區(qū)分混淆的相互構(gòu)造.

5.1 混淆電路與混淆的區(qū)別

在之前的介紹中, 不可區(qū)分混淆和混淆電路有著很多相似之處, 在構(gòu)造的過程中, 都需要對函數(shù)進行“加密”, 使得敵手無法從加密后的函數(shù)中獲取自己想要的信息.而在安全性定義上, 不可區(qū)分混淆的不可區(qū)分性和加密函數(shù)基于不可區(qū)分的安全性(包括選擇性和自適應(yīng)的), 都是要求對兩個功能相同、規(guī)模相同的函數(shù)任意選取一個進行混淆或加密, 再讓敵手進行猜測區(qū)分.不可區(qū)分混淆和混淆電路從表面上看似乎可以看作一個密碼工具, 但是在現(xiàn)實的研究中又具有很大的差別.到底不可區(qū)分混淆和混淆電路的區(qū)別在哪里呢？

接下來我們將從設(shè)計初衷、定義、安全要求、構(gòu)造難度四個方面進行對比.目的是分析不可區(qū)分混淆和傳統(tǒng)混淆電路的根本區(qū)別, 為將來的密碼研究探索新思路.

設(shè)計初衷從設(shè)計初衷上來說, 混淆最初是由程序混淆、代碼混淆發(fā)展而來, 混淆電路則是從安全多方計算所衍生出的一個密碼方案.混淆最初的目的是保護程序和代碼內(nèi)容的安全.經(jīng)過近十年的演變, 不可區(qū)分混淆的主要作用也是保護電路或者函數(shù)的內(nèi)部信息不被泄露.對比混淆電路, 他最初的目的是保護輸入信息, 由于輸入信息加密而衍生的需要在加密條件下進行電路計算.在混淆電路的三十年發(fā)展中, 其主要作用是為了保護每一位參與者的輸入安全, 使參與者之間的輸入互不可知.因此, 可以明顯看出不可區(qū)分混淆必須加密和保護的是電路本身的安全和隱私, 而混淆電路必須加密和保護的是輸入信息的安全.

定義從定義上, 不可區(qū)分混淆只有兩個函數(shù) Obf 和 Eval, 分別用來混淆程序和計算輸出.而混淆電路則由三個函數(shù)組成Gb、En、Ev, 分別擁有加密電路、加密輸入、計算輸出的功能.函數(shù)中加密電路函數(shù)Gb 可以看作和不可區(qū)分混淆的混淆函數(shù)Obf 相似, 計算函數(shù)Ev 和不可區(qū)分混淆的計算函數(shù)Eval 相似.剩下的函數(shù)是用來加密輸入.也就是說, 從定義上看到, 加密函數(shù)比不可區(qū)分函數(shù)在加密電路和保證加密電路的功能之外, 還增加了對輸入的加密.

安全要求從安全要求上, 由于傳統(tǒng)的 Yao 的構(gòu)造是選擇性安全的構(gòu)造, 因此我們將不可區(qū)分混淆和混淆電路基于不可區(qū)分選擇性安全都統(tǒng)一為圖6 所示的游戲進行比較.不可區(qū)分混淆的不可區(qū)分性要求在此游戲后, 敵手猜測成功的優(yōu)勢是一個可忽略函數(shù), 混淆電路的基于不可區(qū)分的隱私性同樣的要求在此游戲后, 敵手猜測成功的優(yōu)勢是一個可忽略函數(shù).

對比兩個游戲的過程, 在電路的選擇、計算、交互上是相同的.兩個游戲均是由敵手先選擇兩個功能相同、規(guī)模相同的電路C0和C1, 并將這兩個電路一起發(fā)送給挑戰(zhàn)者.挑戰(zhàn)者在收到兩個電路之后, 先隨機生成一個比特b∈{0,1}, 并對對應(yīng)的電路Cb進行操作(不可區(qū)分混淆運行混淆函數(shù) Obf, 混淆電路運行加密函數(shù)Gb), 在加密或者混淆完成后將結(jié)果返回給敵手.敵手收到之后可以進行電路的計算(不可區(qū)分混淆運行計算函數(shù) Eval, 加密函數(shù)運行計算函數(shù)Ev), 并猜測挑戰(zhàn)者選取的比特b.如果敵手不能以超過的概率猜測正確, 則說明此方案是安全的.

圖6 不可區(qū)分混淆和加密電路的安全定義Figure 6 Security definition of iO and garbled circuits

但是可以看到在兩個游戲中對電路輸入的操作是不同的.不可區(qū)分混淆的輸入是在挑戰(zhàn)者返回混淆后的程序之后, 由敵手任意次選擇輸入并帶入電路進行計算.而 Yao 的混淆電路的輸入則是要求敵手必須在發(fā)送兩個電路C0和C1之前選擇好并發(fā)送給挑戰(zhàn)者, 由挑戰(zhàn)者統(tǒng)一進行加密返回給敵手.在此方面上, 混淆更接近適應(yīng)性安全的混淆電路.此外, 敵手只能使用發(fā)送給挑戰(zhàn)者的輸入對加密后的電路進行計算, 不能再選擇新的輸入.也就是說, 不可區(qū)分混淆完成的混淆程序在敵手任意多次選擇輸入并計算之后,仍然無法區(qū)分.混淆電路加密后的電路則是限制在一次輸入計算過程中不可區(qū).如果對加密后的電路進行多次不同輸入的計算, 我們可以通過局部輸入攻擊(partial evaluation attacks)[4]進行區(qū)分.

構(gòu)造難度從構(gòu)造難度上, 不可區(qū)分混淆需要多線性映射或者分級編碼系統(tǒng)構(gòu)造, 混淆電路需要雙密鑰密碼進行構(gòu)造.2017 年, Halevi 等人[18]實現(xiàn)了基于 GGH15 多線性映射的不可區(qū)分混淆方案.在文章中, 分支函數(shù)長度為20 時, 混淆時間已經(jīng)超過四萬秒.雖然在之后Lin 等人[7–10]的工作使得不可區(qū)分混淆方案可以基于三線性映射構(gòu)造, 但是一方面還沒有相關(guān)實現(xiàn)展示其具體效率, 另一方面沒有突破多線性映射的禁錮.由于多線性映射至今無法確定是否存在安全的構(gòu)造, 現(xiàn)有的構(gòu)造都收到不同程度的攻擊并且效率極低, 因此不可區(qū)分混淆的實現(xiàn)效率也很低.而在 2004 年 Dahlia 等人[88]基于 Yao 的混淆電路實現(xiàn)的安全多方計算平臺Fairplay 上, 64 比特輸入、電路規(guī)模為256 的大富翁游戲僅需要4 秒時間.在使用Free-XOR、半門、row-reduction 的操作后, 混淆電路的效率進一步得到提升.可以看到混淆電路比起不可區(qū)分混淆來看更加高效.

綜上所述, 我們可以看到不可區(qū)分混淆和混淆電路兩個概念還是存在相當(dāng)大的區(qū)別.不可區(qū)分混淆構(gòu)造要求更高, 效率較低, 但是對電路的安全性保護更加全面.混淆電路的構(gòu)造要求低, 效率較高, 對輸入也有不可區(qū)分混淆沒有的加密機制, 但是對電路本身的安全性保護較低, 在實際使用過程中受限, 混淆電路不可重復(fù)使用.

5.2 混淆電路與混淆的聯(lián)系

本節(jié)將探討混淆電路與混淆之間的聯(lián)系, 試圖通過混淆構(gòu)造可重用混淆電路, 并探索構(gòu)造混淆所需的混淆電路的安全等級.需要說明的是, 我們期望構(gòu)造的混淆電路和混淆均為通用構(gòu)造, 特殊函數(shù)的構(gòu)造暫不考慮.因此, 我們探索的是混淆電路與通用混淆即不可區(qū)分混淆之間的關(guān)系.通過相互構(gòu)造, 期望發(fā)現(xiàn)其相互關(guān)系, 為混淆電路和混淆的發(fā)展提供思路.

由5.1 節(jié)的討論可知混淆電路與混淆最大的障礙在于可重用性, 也就是說對于同一個混淆電路, 可以實現(xiàn)多組不同輸入的計算并保證其安全性.Goldwasser 等人[16]給出第一個可重用混淆電路的構(gòu)造.可重用混淆電路是在原有的混淆電路方案中加入可重用, 即在加密函數(shù)En 中, 要求可以選擇不同的輸入進行加密.同時在使用同一個加密后的電路F時不泄露電路和輸入信息.其形式化定義如下:

定義 8(可重用混淆電路) 一個混淆電路方案uGC=(uGC.Gb,uGC.En,uGC.Ev) 被稱為可重用混淆電路, 那么:

? uGC.Gb(1λ,C)→(F,sk).此算法用于對輸入的電路C, 在安全參數(shù)λ下加密得到加密后的電路F以及一個密鑰sk.

? uGC.En(sk,x) →X.此算法利用密鑰 sk 將電路C的一個輸入x進行加密, 得到X.對于同一個C加密后得到F和sk, 可以利用 sk 構(gòu)造多組輸入x的加密輸入X, 稱為可重用的.

? uGC.Ev(F,X) →Y.此算法對加密后的電路F以及輸入X進行計算, 得到Y(jié), 且Y的值等于C(x).

Goldwasser 等人[16]使用全同態(tài)加密和基于屬性的加密方案構(gòu)造了可重用混淆電路.文章中使用的基于屬性的加密方案 ABE = (ABE.Setup,ABE.KeyGen,ABE.Enc,ABE.Dec) 與一般的 ABE 方案不同.普通的 ABE 方案, 在解密過程斷言為真則解密, 斷言為假則停機.而 Goldwasser 所使用的 ABE是加密兩個消息m0和m1, 若斷言為真則解密m1, 反之則解密m0.使用這種 ABE 方案和 Yao 的混淆電路方案 GC 結(jié)合, 即可解密 Yao 輸入密鑰對的其中一個.而斷言則是使用全同態(tài)加密方案 FHE =(FHE.KeyGen,FHE.Enc,FHE.Eval,FHE.Dec) 的計算函數(shù)判定.為保證函數(shù)安全性, 額外選取一個對稱加密方案Sym=(Sym.KeyGen,Sym.Enc,Sym.Dec) 將函數(shù)加密即可.具體構(gòu)造方法如算法1 所示.

若我們希望找到通用混淆和可重用混淆電路的關(guān)系, 就需要對現(xiàn)有的可重用混淆電路進行改造.首先,目前存在的通用混淆方案為不可區(qū)分混淆方案.不可區(qū)分混淆在兩個功能相同規(guī)模相同的電路對C0,C1滿足:因此, 我們需要定義基于不可區(qū)分安全性的可重用混淆電路.可重用混淆電路的基于不可區(qū)分的自適應(yīng)安全定義在一個游戲uAdaInd.游戲過程為: 敵手任意的選擇一對規(guī)模相同、功能相同的電路C0,C1, 將此電路對發(fā)送給挑戰(zhàn)者.挑戰(zhàn)者隨機選取b∈{0,1},計算 uGC.Gb(1λ,Cb) →(Fb,sk), 得到后將Fb發(fā)送給敵手.敵手根據(jù)Fb, 任意的循環(huán)以下步驟: 選擇一個輸入x, 詢問挑戰(zhàn)者, 挑戰(zhàn)者計算 uGC.En(sk,x) →X并返回X給敵手, 計算 uGC.Ev(Fb,X) →Y.最后敵手猜測則稱此混淆電路方案滿足基于不可區(qū)分的自適應(yīng)安全.

有了可重用混淆電路的定義和構(gòu)造, 我們嘗試使用不可區(qū)分混淆構(gòu)造滿足可重用性的混淆電路方案.假設(shè)存在一個不可區(qū)分混淆iO= (iO.obf,iO.Eval), 以及一個對稱加密方案 Sym =(Sym.KeyGen,Sym.Enc,Sym.Dec), 構(gòu)造一個可重用混淆電路方案uGC:

? uGC.Gb(1λ,C): 計算 sk←Sym.KeyGen(1λ).構(gòu)造電路Csk,C(X).電路Csk,C(X) 首先計算x←Sym.Dec(sk,X),然后計算并返回C(x).將電路Csk,C(X)混淆得到Γ←iO.obf(1λ,Csk,C).返回 (Γ,sk).

? uGC.En(sk,x): 計算X←Sym.Enc(sk,x).返回X.

? uGC.Ev(Γ,X): 計算Y←iO.Eval(Γ,X).返回Y.

如此構(gòu)造的可重用混淆電路方案是滿足基于不可區(qū)分性的自適應(yīng)性安全的.即可構(gòu)造由基于不可區(qū)分性自適應(yīng)安全的可重用混淆電路到不可區(qū)分混淆的規(guī)約.對任意一個不可區(qū)分混淆的挑戰(zhàn)者, 敵手首先選擇兩個功能相同、規(guī)模相同的電路C0和C1, 計算 sk←Sym.KeyGen(1λ).接下來, 利用電路C0,C1以及sk 構(gòu)造兩個新的功能相同且規(guī)模相同的電路Csk,C0(X),Csk,C1(X).敵手將Csk,C0(X),Csk,C1(X)作為挑戰(zhàn)電路對發(fā)送給不可區(qū)分混淆的挑戰(zhàn)者得到一個回答iO(Csk,Cb(X)).此回答也是對于基于不可區(qū)分性的自適應(yīng)安全的可重用混淆電路方案的挑戰(zhàn)密文.若對此密文可區(qū)分那么對不可區(qū)分混淆的密文也可區(qū)分, 即此可重用混淆電路方案是滿足基于不可區(qū)分性的自適應(yīng)性安全的.

接下來, 我們將探索使用混淆電路構(gòu)造不可區(qū)分混淆的方法.從 3.1 節(jié)可以看到, 傳統(tǒng)的混淆電路是選擇性安全的, 且是 “一次性” 的.因此, 學(xué)者們構(gòu)造了可重用的混淆電路.那么, 可重用混淆電路與不可區(qū)分混淆又是否相等呢？

首先回顧一下Goldwasser 等人[16]提出的可重用混淆電路的安全定義.可重用混淆電路的安全定義是基于模擬的, 稱為可重用的輸入和電路隱私性(input and circuit privacy with reusability).其具體定義如下.

定義 9(可重用的輸入和電路隱私性) 令uGC 是電路簇{Cn}n∈N的可重用混淆電路方案.對于一對概率多項式時間算法A= (A1,A2) 以及一個概率多項式時間模擬器S= (S1,S2) 來說, 考慮圖7 的兩個游戲:

圖7 可重用輸入和電路隱私性游戲Figure 7 Game of input and circuit privacy with reusability

其中O(·,C)[[stateS]]是一個運行S2的預(yù)言機, 輸入x,C(x), 1|x|以及S的狀態(tài), 返回S2的輸出結(jié)果.如果在這兩個游戲中,兩個分布是計算不可區(qū)分的, 那么稱此可重用混淆電路方案滿足可重用的輸入和電路隱私性.

從安全定義來看, 可重用混淆電路的安全性是基于模擬的自適應(yīng)安全.類比混淆來說, 相當(dāng)于虛擬黑盒混淆的安全定義.但是由于其加密函數(shù) En 是使用私鑰sk 進行計算的, 和不需要限制使用明文進行計算的混淆不同.而Goldwasser 等人的文章中[17]有這樣一段話: “加密輸入需要私鑰是必須的.如果可以公開加密, 那么敵手的能力將和傳統(tǒng)的混淆相同.而這種混淆已經(jīng)被證明不存在通用構(gòu)造.” 這段話從側(cè)面印證了如果在此安全定義下構(gòu)造不需要私鑰的可重用混淆電路方案, 就相當(dāng)于完成了通用虛擬黑盒混淆的構(gòu)造.

由于基于模擬的自適應(yīng)安全也可滿足此定義下的基于不可區(qū)分的自適應(yīng)安全, 所以現(xiàn)有的基于模擬的自適應(yīng)安全的可重用混淆電路均滿足基于不可區(qū)分的自適應(yīng)安全.但是, 是否存在不需要私鑰的可重用混淆電路方案暫時是一個未解之謎.即敵手在獲取到Fb后可自行計算函數(shù), 無需再向挑戰(zhàn)者獲取輸入x的加密密文X.

假設(shè)存在不需要私鑰的可重用混淆電路方案, 那么構(gòu)造不可區(qū)分混淆將是簡單的.假設(shè)存在一個滿足基于不可區(qū)分自適應(yīng)性安全的不需要私鑰的混淆電路方案uGC.構(gòu)造一個不可區(qū)分混淆方案如下:

?iO.obf(1λ,C): 計算 uGC.Gb(1λ,C)→ (F,pk), 返回O=(F,pk).

?iO.Eval(x,O): 分離O=(F,pk), 計算 uGC.En(pk,x)→X, uGC.Ev(F,X)→Y, 返回Y.

綜上可知, 利用不可區(qū)分混淆構(gòu)造基于不可區(qū)分的自適應(yīng)安全的可重用混淆電路方案是簡單的, 而利用基于不可區(qū)分的自適應(yīng)安全的可重用混淆電路方案構(gòu)造不可區(qū)分混淆則是未知的.通過探索可知, 構(gòu)造不可區(qū)分混淆相當(dāng)于構(gòu)造一個不需要私鑰的基于不可區(qū)分自適應(yīng)性安全的混淆電路方案.因此, 利用混淆電路方案構(gòu)造混淆也許是一個新的發(fā)展方向.

6 總結(jié)

混淆電路與混淆作為對函數(shù)本身的保護是密碼研究領(lǐng)域兩個非常重要的工具.混淆電路在安全多方計算、同態(tài)計算、可驗證計算等方面均有應(yīng)用, 而混淆也在可否認(rèn)加密、廣播加密、自線性映射等方面均有應(yīng)用.他們不僅在密碼學(xué)理論研究中起到重要作用, 在現(xiàn)實生活中也有廣泛的應(yīng)用空間.由于混淆電路和混淆均是對電路的保護, 將來可能應(yīng)用到人類社會的創(chuàng)作、發(fā)明、作品等技術(shù)保護.但是, 混淆電路和混淆都還存在很多問題值得被探索和研究.

首先, 混淆電路特別是可重用混淆電路方案的有效實現(xiàn)暫時缺失.可重用混淆電路相較于不可重用的方案來說大大提高了構(gòu)造的復(fù)雜度, 在現(xiàn)實應(yīng)用過程中也降低了構(gòu)造速率.但是現(xiàn)有的相關(guān)可重用混淆電路的研究依然很少, 僅僅停留在理論分析上.目前可重用混淆電路在擺脫了同態(tài)加密的重負(fù)后, 使用的方案僅基于 LWE、隨機線性碼以及對稱加密方案.但是安全性也大大降低.可重用混淆電路的效率以及安全參數(shù)的選擇依然是一個待探索的領(lǐng)域.此外, 是否存在更加有效的可重用混淆電路的構(gòu)造方案或優(yōu)化方案也是一個待探索的方向.又或者, 是否存在效率接近不可重用的混淆電路而重用次數(shù)有限次的混淆電路方案？關(guān)于可重用混淆電路, 依然等待著學(xué)者們的探索與發(fā)現(xiàn).

其次, 混淆的有效構(gòu)造依然困擾著密碼界.傳統(tǒng)的基于多線性映射的混淆由于多線性映射的不安全性導(dǎo)致構(gòu)造的混淆方案不安全, 是否存在安全有效的多線性映射方案依然是迷.而現(xiàn)有的GGH13、CTL13以及 GGH15 均被攻破, 構(gòu)造多線性映射的問題停滯不前.對于使用較為成熟的雙線性對方案構(gòu)造混淆,近兩年成為學(xué)者們努力的目標(biāo), 現(xiàn)有的研究顯示有完成的可能性.但是這種構(gòu)造方式的效率和參數(shù)也將成為下一個關(guān)心的問題, 以及這些構(gòu)造是否存在可攻擊的漏洞也未可知.對于不可區(qū)分混淆的構(gòu)造和實現(xiàn)依然值得深入研究.

最后, 關(guān)于混淆電路和混淆之間的關(guān)系, 通過本文的探索, 問題糾結(jié)在于是否存在不需要私鑰的基于不可區(qū)分的自適應(yīng)性安全可重用混淆電路方案.是否可以通過現(xiàn)有的基于模擬的可重用混淆電路方案進行修改, 得到基于不可區(qū)分的方案并解放私鑰.又或者對現(xiàn)有的可重用混淆電路作為基礎(chǔ), 結(jié)合密碼學(xué)其他工具解放私鑰是否可以完成混淆的構(gòu)造？而這種構(gòu)造方式相較于現(xiàn)有的混淆構(gòu)造是否能夠提高效率？此外, 關(guān)于可重用混淆電路的構(gòu)造, 可否利用對具體函數(shù)的虛擬黑盒混淆進行構(gòu)造.由于現(xiàn)有的對具體函數(shù)的混淆效率相較通用混淆較高, 因此嘗試使用對具體函數(shù)的混淆來構(gòu)造可重用混淆電路或許可行.

雖然混淆電路和混淆還有很長的路要走, 但是這兩個密碼方案已經(jīng)顯示其強大的功能.相信經(jīng)過無數(shù)學(xué)者的努力和奮斗, 終有一天我們會突破這些難題, 讓混淆電路和混淆為人類社會安全添磚加瓦.