量子訪問控制問題的可混淆性*

陳然一鎏, 尚濤, 劉建偉

1.北京航空航天大學電子信息工程學院, 北京100083

2.北京航空航天大學網絡空間安全學院, 北京100083

1 引言

混淆(obfuscarion)的概念最早誕生于軟件工程, 用于保護軟件不被反編譯等手段得到程序底層實現邏輯.由于理想的混淆器與密碼學中的安全性有形式上的相似之處, 2001年Barak 等人[1]首次將混淆的概念引入密碼學, 并提出第一個(同時也是最強的)混淆器的定義: 虛擬黑盒(virtual black-box, VBB)混淆.虛擬黑盒混淆需要滿足三個特性, 即(1)功能保持性: 混淆后的線路保留原線路的功能; (2)多項式減緩: 混淆后的線路規模不超過原來線路規模多項式級別的大小; (3)虛擬黑盒性: 通過混淆后線路計算出的所有信息, 一定可以通過對原線路的預言式訪問有效計算.同時Barak 也指出, 通用的虛擬黑盒混淆器是不存在的.在通用性無法得到滿足的前提下, 混淆理論發展出了一個新的分支, 即對于特定功能的線路的混淆.其中對于點函數的混淆性研究格外引人矚目[2].2004年Lynn 等人提出了點函數的可混淆性結論[3], 這是首個混淆領域的積極結論.他們指出基于有限自動機和正則表達式的功能是可以被虛擬黑盒混淆的; 2005年Hoeteck[4]在一個稍弱的定義下構造了點函數的標準模型混淆器, 并且指出構造基于強單向置換; 針對多比特輸出的點函數, Ran 等人[5]分析了線路的組合問題, 給出了正確的混淆器組合方式;在應用方面, Ran 等人[6]討論了使用多比特輸出點函數混淆在對稱加密方向的應用, 指出具有不同屬性的混淆器可以用于分別構造滿足不同安全性要求的對稱加密方案.最新的研究結果包括利用混淆構造可驗證可搜索的對稱加密方案[7].

量子計算機被證明對某些函數(特別是經典密碼學感興趣的困難函數)有強大的計算能力[8]之后,量子密碼學成為密碼學家關注的新興領域.量子混淆的概念最早起源于Scott 的“用量子比特保護線路信息” 的思想[9].嚴格的量子混淆定義建立在量子計算的理論基礎之上.直到2014年之前, 都沒有人公開發表過對于量子混淆的研究.在2014年的量子計算通信密碼理論會議(Conference on the Theory of Quantum Computation, Communication and Cryptography)上, Alagic 等人[10]首次提出了基于量子拓撲計算的量子混淆器.他們利用辮群的特定高維表達將線路編譯成辮, 然后再將其轉化成標準形式.但該混淆不符合之前混淆器的定義, 它的應用也未經過嚴格論證.2016年, Alagic 等人正式提出了量子混淆的定義[11].他們首先定義了量子黑盒混淆器, 并認為量子的黑盒混淆比經典的黑盒混淆更加可行; 隨后,Alagic 等人定義了量子不可區分混淆器并且指出了量子混淆器可用于構造量子單向函數、長信息公鑰量子加密、公鑰量子錢幣.2019年, Shang 等人發表了關于量子點函數混淆的研究[12,13].訪問控制通過權限規定資源是否可以被訪問, 實現對資源的管理, 是信息系統安全的基本要求, 而量子訪問控制解決量子計算機相應的問題.目前, 量子密碼學中的量子密鑰分配、量子安全直接通信等解決通信過程的安全問題,而量子訪問控制則按照用戶身份及其所歸屬的用戶組來限制用戶對量子比特的訪問或限制對量子線路的使用, 從而實現對量子計算機系統的資源管理.隨著量子信息技術的快速發展, 量子計算機的研究也初現成果[14], 量子訪問控制可以逐步應用到量子計算機和量子網絡上, 提供有效的資源管理功能, 這一方面的研究成果將對量子密碼學的發展提供重要的理論基礎.

本文深入研究了以往國內外經典混淆和量子混淆的積極結果, 發展了量子點函數混淆方法, 并基于量子點函數以及基于圖的訪問控制問題的抽象模型, 定義了量子訪問控制問題.通過定義的量子訪問控制問題的輔助問題, 解決了量子訪問控制問題的可混淆性證明過程中的有效輸入指數發散問題, 證明了量子訪問控制問題的可混淆性.

本文結構如下.第2 節回顧了量子混淆以及經典的基于圖的訪問控制問題.第3 節定義量子訪問控制問題和量子點函數, 并論證量子訪問控制問題的可混淆性.最后, 在第4 節總結全文, 并討論未來可能的研究方向.

2 相關知識

2.1 量子混淆

Alagic 等人[11]最先明確了量子混淆的定義, 并且完成了一些基礎的證明工作.在量子混淆理論中,一個量子線路混淆器按如下方式定義:

定義1(可重復)量子線路混淆器

一個(可重復)線路混淆器滿足以下條件:

– (功能保持性)輸入n 量子比特的量子線路C, 輸出m 量子比特的量子態O(C)滿足

– (多項式減緩)

– (虛擬黑盒性)對任意QPT A, 都有QPT SUC使得對所有的線路C 滿足

– (可重復)使用δ 后, 功能保持性依然滿足.

在式(1)中可以看到,量子混淆與經典混淆最大的不同在于,為了使用戶能夠完成一些特定的功能[11],量子混淆器的輸出不再是一個量子線路的描述, 而是一個量子態.因為混淆器輸出的是量子態, 所以解釋器δ 是必要的.值得注意的是盡管解釋器算法δ 必須是多項式時間的, 混淆算法O 本身并不需要是多項式時間的.在混淆器的實現上要求混淆算法多項式時間可實現, 但在理論上非多項式時間的混淆算法得到的結論更強.定義1 中關于解釋器的定義可以有多種形式, 例如對于同一個量子線路族, 可以設置一個共同的量子混淆解釋器; 或者混淆算法本身就由一個量子態和一個量子線路構成, 終端用戶可以在量子線路上執行量子態和需要的輸入.容易證明這兩種解釋器的定義是等價的, 當其中一種量子混淆器存在時另一種也存在.

本文采用如定義1 所示的量子混淆定義.這里可做一個直觀的解釋: 混淆算法O 計算線路C 在所有可能的輸入下可能得到的輸出值, 并記錄在O(C)中; 解釋器δ 僅起到一個選擇的作用, 根據混淆線路的輸入, 選擇相應的輸出.這樣盡管混淆算法O 本身可能不再是多項式時間的, 解釋器δ 一定是多項式時間的.再次強調解釋器是經典混淆器向量子混淆器擴展時自然且必要的補充, 為了使定義有效, 必須存在一個有效的算法來使用O(C)計算UC的功能.無論這個有效的算法是什么, 本文將其定義為解釋器, 用δ表示.

另一個量子混淆相較于經典混淆器新引入的性質是可重復性, 顯然可重復的量子混淆器要比不可重復的量子混淆器更強, 因為可重復性實際上允許量子敵手擁有更強攻擊能力[11].本文中所有的討論都將基于可重復的量子混淆器.

2.2 基于圖的訪問控制

基于圖的訪問控制問題[15,16]中, 安全策略由系統圖決定, 系統圖由安全策略框架生成.安全策略框架是一個四元組SP = (TG,RS,Pos,Neg).其中, TG 是一個類型圖, RS 是規則集合, Pos 是肯定約束,Neg 是否定約束.所有的系統圖由類型圖根據規則集合變換得到, 并且必須包含肯定約束中的圖作為子圖,且不得包含否定約束中的圖.

一個典型的訪問控制系統圖如圖1 所示.圖中U 代表用戶, R 代表角色, T 代表任務, t 代表行為.用戶到角色的邊代表用戶與角色的從屬關系; 角色到角色的邊代表角色之間的從屬關系; 角色與任務之間的邊代表角色與任務的分配關系; 用戶與行為之間的邊代表用戶與行為的執行關系.系統通過系統圖對用戶權限進行判定.當用戶向系統提出一個行為申請時, 系統根據用戶判斷所屬角色, 并判斷申請的任務與角色之間是否有分配關系; 在執行過程中, 由具體的用戶來執行任務相應的行為.

圖1 典型系統圖Figure 1 Typical system graph

3 量子訪問控制問題及其可混淆性

3.1 量子訪問控制問題的定義

如前文所述, 一個基于圖的訪問控制系統依據系統圖進行各種操作.系統圖中的信息可以被再次抽象.圖中的節點可以是用戶、角色、任務、行為, 統稱為節點秘密; 圖中的邊可以是用戶與角色的從屬關系、角色與角色的階層關系、角色與任務的分配關系、用戶與行為的執行關系, 統稱為鄰邊口令.節點秘密和臨邊口令以量子態的形式存儲.在系統執行過程中, 用戶向系統提出一個行為申請, 在圖上反映為從當前節點前進到目標節點: 當且僅當該用戶能夠提供兩個節點之間的臨邊口令時, 系統接受該申請, 并返回目標節點秘密.

量子訪問控制問題包括圖的拓撲結構、鄰邊口令以及節點秘密.對量子訪問控制問題的安全混淆要求隱藏量子訪問控制問題的全部信息, 包括圖的拓撲結構、所有的臨邊口令以及節點秘密.本節給出訪問控制問題的形式化定義.

定義2量子訪問控制問題

一個基于圖的量子訪問控制問題XG定義如下:

(1)考慮一個具有k 個節點的有向圖G.每個節點u ∈k 有最多d 個有序鄰邊(注意可能存在多條鄰邊指向同一個節點的情況), 定義E ={(u,v,i):v =} 為所有鄰邊的集合.

那么

注意到量子訪問控制問題在形式上與經典的點函數有相似之處.這啟發我們從量子點函數的可混淆性入手, 研究量子訪問控制問題的可混淆性.

3.2 量子訪問控制問題的可混淆性

3.2.1 量子點函數和量子多點函數的可混淆性

定義3量子點函數

其中α,β ∈{0,1}n.

設功能Uα,β由某個特定的線路Cα,β實現.定義Cn={Cα,β:α,β ∈{0,1}n}, 以及

量子點函數在隨機預言模型下是可混淆的.使用文獻[17]中定義的量子隨機預言機(QRO)Rq:其中R:{0,1}2n{0,1}2n.按如下方式構造一個點函數Uα,β的混淆: OR(Uα,β)隨機選取訪問隨機預言機Rq并得到結果其中R1, R2分別是R 的前n 個和后n 個比特(即隨后, 丟棄寄存器|α,將保存下來; 然后對于輸入以訪問隨機預言機Rq得到結果并保存下來; 最后OR(Uα,β)比較是否有R1(r,x)= R1(r,α), 如果是則輸出否則輸出

定義4一般輸出的量子多點函數

其中αi,βi∈{0,1}n.設功能U(α1,β1),···,(αt,βt)由某個特定線路C(α1,β1),···,(αt,βt)實現.定義αi,βi∈{0,1}n}, 以及

C?的可混淆性可以通過將C?中的每個元素視作C 中元素的結合來證明.下面證明C?是可混淆的.

引理1量子線路族C?是可混淆的.

證明:考慮結合線路{C1#···#Ct:Ci∈C}.線路有輸入兩個寄存器(一個log k 位的控制位寄存器和一個n 位的輸入位寄存器), 在第一個寄存器的值的控制下, 將第二個寄存器應用在對應的量子線路上.即

首先Ci是可混淆的, 于是存在O(C1),O(C2),··· ,O(Ct).由于t 是n 的多項式級別, 線路O(C1)#O(C2)#···#O(Ct)中任意兩個混淆器使用同樣的r 的概率是可忽略的.因為混淆器是隨機算法, 在所有的r 都不相同的情況下, 對C1#C2#···#Ct具有預言式訪問的模擬器可以模擬任意獲得O(C1)#O(C2)#···#O(Ct)的敵手.因此O(C1)#O(C2)#···#O(Ct)是一個對C1#C2#···#Ct的有效混淆.

考慮對C1#C2#···#Ct具有預言式訪問的線路MC1#C2#···#Ct.M 按如下方式工作: 對任意輸入ρ,M 將|ρ,0輸入C1, 得到再依次得到最后返回顯然M = C(α1,β1),···,(αt,βt).那么將C1#C2#···#Ct替換為混淆O(C1)#O(C2)#···#O(Ct)并置于M 內部, 得到的也是的有效混淆.即是可混淆的.

3.2.2 量子訪問控制問題輔助問題的可混淆性

利用C?和引理1可以證明量子訪問控制問題的可混淆性.但存在以下問題: 有向圖中有k 個節點,所以nk; 最壞的情況下, 問題XG可能會有dk種有效輸入(輸出不為0 的輸入), 而C?對t 要求t=ploy(k), 所以不能直接證明該問題可混淆.

為解決規模的指數發散問題, 引入如下訪問控制問題的輔助問題.

定義5輔助問題

該定義下的訪問控制問題最多只有kd 個有效輸入(輸出不為0 的輸入).定義問題WG(u,z,i,x), 對于v ∈[k], 隨機選取κu←{0,1}k, 對于輸入(u,z,i,x)返回定義

由引理1可知輔助問題W 可混淆.顯然, 這個混淆器的安全性并不會因為引入的“密鑰” κ 而有所降低, 因為除非敵手經歷過節點v, 否非他不會得到任何有關κv的信息.而經歷節點v 的唯一條件是易知鄰邊上的口令πe.

3.2.3 量子訪問控制問題的可混淆性

現在通過證明量子訪問控制輔助問題的可混淆性證明量子訪問控制問題是可混淆的.

定理1量子線路X 是可混淆的.

證明:首先, 論證量子訪問控制問題和輔助問題的關系.任取XG∈X, WG∈W, 存在線路M 使得且存在線路N 使得按如下方式工作: 對于輸入M 以訪問WG,如果WG返回則以訪問WG, 如此繼續直到其返回⊥或者完成所有輸入得到不論何種情況輸出返回的結果.N 按如下方式工作: N 在內部維護兩個表: 一個用于存儲“密鑰”κi, 一個用于存儲經歷過的鄰邊以及鄰邊口令.初始化時設其他的“密鑰” 置為⊥.對于輸入|u,z,i,x, N 檢查是否有z = κu⊥, 如果是則說明N 已經記錄了節點1到節點u 的路線, 將其發送給XG.如果XG返回了v,σv, N 還要檢查是否已經分配了κv, 如果不是則隨機選擇“密鑰” 并分配給節點v.注意N 模擬WG成功的前提是在N 經歷節點u 的領邊e之前沒有以有效的口令和“密鑰”訪問過u 和e, 而該事件的概率是可以忽略的, 所以滿足

其次, 利用M 和N 構造XG∈X 的混淆.

由于W 是可混淆的, 設O(WG)是W ∈W 的一個混淆.構造線路按如下方式運作: 首先它將輸入傳給M; 然后每當M 需要以ρ 預言式訪問WG時, M′計算δ(O(WG)?ρ)并返回給M; 最后輸出M 的輸出值.

又因為混淆O(WG)滿足虛擬黑盒性質:

接下來通過S′UWG 構造SUXG.SUXG 按如下方式運作: SUXG 得到輸入后, 將傳給S′UWG; 每當S′UWG 需要以ρ 預言式訪問UWG時, SUXG 計算并返回給S′UWG; 最后輸出S′UWG 的輸出值.這樣, 有

4 總結

本文在Alagic 等人[11]工作的基礎之上補充了量子混淆理論的關鍵引理和概念.本文給出了在量子隨機預言模型下的一個可混淆的函數族: 量子點函數, 證明了量子多點函數的可混淆性.本文定義了量子訪問控制問題, 通過量子訪問控制問題的輔助問題給出量子訪問控制問題的可混淆性證明.

相較于密碼學的其他領域, 混淆理論的獨特性和重要性是不言而喻的; 與此同時, 量子通信和量子計算在本世紀也得到了長足的發展.本文將混淆理論與量子密碼學兩個前沿方向相結合, 是對量子密碼學理論基礎的重要補充.

對量子混淆理論的研究目前甚少, 主要的研究方法還是沿襲經典混淆理論的研究軌跡, 將經典混淆理論的結果擴展到量子情形.本文認為, 量子混淆未來的研究重點有以下幾項:

(1)信息論安全的量子黑盒混淆器的量子力學機制實現以及用戶對混淆量子態多項式次數的使用.這樣的量子混淆器將非常強力, 也將成為量子力學在密碼學領域能發揮更大作用的有力佐證.

(2)對經典線路的量子混淆.因為經典線路的輸出是經典比特串, 所以這樣做的巨大好處是可以用量子態進行經典計算, 保留經典輸出之后通過逐一撤銷酉門還原原來的混淆結果, 可以使混淆結果多次使用.

(3)不可重復使用的量子混淆.在現實中經常需要混淆器的輸出不能被復制.Broadbent 等人曾討論過量子一次程序[18], 這也將在密碼學中發揮重要作用.

(4)量子隨機預言機的刪除.量子隨機預言機相對于經典隨機預言機, 針對疊加態提問做出了大量調整.而量子混淆輸出的量子態也可以是疊加態.如何利用量子混淆機制刪除量子隨機預言機將成為量子密碼學可證明安全的研究熱點.