余卿斐 涂廣升 李寧波 周潭平

摘 要：為解決單策略屬性基全同態(tài)加密方案無法對(duì)不同策略函數(shù)對(duì)應(yīng)的屬性向量下的密文進(jìn)行同態(tài)運(yùn)算和訪問控制，并且新的參與方密文無法動(dòng)態(tài)地加入同態(tài)運(yùn)算的問題，提出了一個(gè)基于誤差學(xué)習(xí)（LWE）問題的高效的多跳多策略屬性基全同態(tài)加密方案。首先，對(duì)單策略屬性基全同態(tài)加密方案適當(dāng)變形;其次，將方案對(duì)應(yīng)到多用戶場(chǎng)景;最后，利用多跳多密鑰全同態(tài)轉(zhuǎn)化機(jī)制來實(shí)現(xiàn)新的參與方密文加入后的同態(tài)運(yùn)算。結(jié)果表明，該方案在功能上兼具屬性基加密和多跳多密鑰全同態(tài)加密的優(yōu)勢(shì)， 并被證明為選擇屬性下的選擇明文攻擊不可區(qū)分性（IND-CPA）安全。與利用目標(biāo)策略函數(shù)集合構(gòu)造的多策略屬性基全同態(tài)加密方案相比，該方案在不改變單個(gè)參與方私鑰尺寸的情況下，密文/明文比明顯降低，效率更高。

關(guān)鍵詞：多跳;多策略;多密鑰;屬性基加密;全同態(tài)加密

中圖分類號(hào)：?TP309.7

文獻(xiàn)標(biāo)志碼：A

Multi-hop multi-policy attributed-based fully homomorphic encryption scheme

YU Qingfei1， TU Guangsheng2，3*， LI Ningbo2， ZHOU Tanping2，3

1.Staff Headquarters， The Anhui Provincial Corps of Chinese Peoples Armed Police Force， Hefei Anhui 230031， China ;

2.Key Laboratory of Network and Information Security of the Chinese Peoples Armed Police Force （Engineering University of the Chinese Peoples Armed Police Force）， Xian Shaanxi 710086， China ;

3.College of Cryptographic Engineering， Engineering University of the Chinese Peoples Armed Police Force， Xian Shaanxi 710086， China

Abstract：?The single-policy attribute-based fully homomorphic encryption scheme cannot perform homomorphic operation and access control of ciphertexts under different attribute vectors corresponding to different policy functions， and new participant ciphertexts cannot dynamically join into the homomorphic operation. In order to solve the above problems， an efficient multi-hop multi-policy attribute-based fully homomorphic encryption scheme based on Learning with Error （LWE） problem was proposed. Firstly， the single-policy attribute-based fully homomorphic encryption scheme was appropriately modified. Secondly， the scheme was mapped to multi-user scenarios. Finally， a multi-hop multi-policy fully homomorphic transformation mechanism was used to realize the homomorphic operation after adding new participant ciphertexts. The proposed scheme is proved to be INDistinguishability under Chosen Plaintext Attack （IND-CPA） secure under the chosen attribute， and has advantages of attribute-based encryption and multi-hop multi-key fully homomorphic encryption. Compared with multi-policy attribute-based fully homomorphic encryption scheme constructed by using target policy function set， the ciphertext/plaintext ratio of the proposed scheme is significantly reduced without changing the size of the individual participants secret key.

Key words：?multi-hop; multi-policy; multi-key; Attribute-Based Encryption （ABE）; Fully Homomorphic Encryption （FHE）

0 引言

屬性基加密（Attributed-Based Encryption， ABE）[1-4]屬于公鑰加密體制范疇，能夠?qū)崿F(xiàn)對(duì)密文數(shù)據(jù)的靈活訪問控制。ABE可以分為密鑰策略屬性基加密（Key-Policy ABE， KP-ABE）和密文策略屬性基加密（Ciphertext-Policy ABE， CP-ABE）[2]。在KP-ABE中，密文與屬性向量 x 有關(guān)，密鑰與策 略函數(shù)f有關(guān)，當(dāng)且僅當(dāng)屬性向量滿足f（ x ）=0時(shí)，密文可以被正確解密。本文研究對(duì)象為KP-ABE方案。

隨著云計(jì)算的發(fā)展，全同態(tài)加密（Fully Homomorphic Encryption， FHE）[5-8]因其在密文處理的優(yōu)良性質(zhì)成為研究熱點(diǎn)。然而，以往的FHE方案都只能對(duì)同一公鑰下加密的密文進(jìn)行同態(tài)運(yùn)算，這在很大程度上限制了FHE方案的實(shí)際應(yīng)用。2012年，Lpez-Alt等[9]首次提出多密鑰全同態(tài)加密（Multi-Key FHE， MKFHE）的概念，實(shí)現(xiàn)了對(duì)不同公鑰下加密的密文進(jìn)行同態(tài)運(yùn)算;2015年，Clear等[10]基于誤差學(xué)習(xí) （Learning with Error， LWE）問題構(gòu)造了一個(gè)隨機(jī)預(yù)言機(jī)（Random Oracle， RO）模型下選擇明文攻擊（Chosen Plaintext Attack， CPA）安全的多密鑰全同態(tài)加密方案;2016年，Mukherjee等[11]對(duì)文獻(xiàn)[10]方案進(jìn)行優(yōu)化，提出了新的基于LWE問題的MKFHE方案，該方案密文尺寸小、運(yùn)算復(fù)雜度低。

上述的MKFHE方案雖然實(shí)現(xiàn)了對(duì)不同公鑰下密文的同態(tài)運(yùn)算，但都只滿足單跳（Single-Hop）[10-11]性質(zhì)，即所有參與方的密鑰在同態(tài)運(yùn)算時(shí)要事先確定，并且新加入?yún)⑴c方的密文無法與以往的密文進(jìn)行有效的同態(tài)運(yùn)算。2016年，Peikert等[12]提出了兩個(gè)滿足多跳（Multi-Hop）性質(zhì)的MKFHE方案，即新參與方的密文可以直接與以前參與方的密文進(jìn)行同態(tài)運(yùn)算，任何參與方的密文都可以動(dòng)態(tài)地加入到同態(tài)運(yùn)算中。

研究將ABE與MKFHE相結(jié)合，是近幾年的熱點(diǎn)問題。2013年，Gentry等[7]結(jié)合文獻(xiàn)[3]中的ABE方案，構(gòu)造了一個(gè)屬性基全同態(tài)加密方案（Attributed-Based FHE， ABFHE），然而該方案限定在策略函數(shù)與屬性向量為一一對(duì)應(yīng)的關(guān)系，并且只能對(duì)在同一屬性下加密的數(shù)據(jù)進(jìn)行同態(tài)運(yùn)算。2016年，Brakerski等[13]提出了一個(gè)單策略屬性基全同態(tài)加密（Single-Policy ABFHE， SP-ABFHE）方案，該方案的策略函數(shù)與屬性向量為一對(duì)多的關(guān)系，即不同的屬性向量對(duì)應(yīng)的策略函數(shù)相同，對(duì)應(yīng)相同的解密密鑰。因此該方案可以對(duì)同一策略函數(shù)對(duì)應(yīng)的不同屬性向量下加密得到的密文進(jìn)行同態(tài)運(yùn)算。同時(shí)，文獻(xiàn)[13]利用文獻(xiàn)[10-11]中的MKFHE轉(zhuǎn)化機(jī)制，將SP-ABFHE方案轉(zhuǎn)化為多策略屬性基全同態(tài)加密（Multi-Policy ABFHE， MP-ABFHE）方案，實(shí)現(xiàn)了對(duì)不同策略函數(shù)對(duì)應(yīng)的不同屬性向量下加密密文的同態(tài)運(yùn)算。

考慮這樣的實(shí)際場(chǎng)景：病人到醫(yī)院就診，利用ABE的性質(zhì)，醫(yī)院使用病人的屬性集合為病人建立病歷檔案，加密后上傳至服務(wù)器。每個(gè)醫(yī)生擁有自己的策略函數(shù)，醫(yī)院根據(jù)策略函數(shù)為每個(gè)醫(yī)生分配密鑰，只有當(dāng)醫(yī)生的策略函數(shù)與病人的屬性集合滿足一定關(guān)系時(shí)，醫(yī)生才可以解密該密文，查看病歷。利用MKFHE的性質(zhì)，醫(yī)院可以對(duì)不同屬性下加密的病歷檔案進(jìn)行同態(tài)操作，得到新的同態(tài)密文，并使用所有醫(yī)生的密鑰對(duì)同態(tài)密文進(jìn)行解密。

利用多跳多密鑰全同態(tài)加密（Multi-Hop MKFHE）的性質(zhì)，當(dāng)有新的病人加入時(shí)，更新病歷檔案，新的病歷檔案可以直接與以前的病歷檔案進(jìn)行同態(tài)操作，并正確解密。場(chǎng)景中，病人檔案可以被多個(gè)滿足一定策略函數(shù)關(guān)系的醫(yī)生查看，一個(gè)醫(yī)生也可以查看多個(gè)滿足關(guān)系的病歷檔案。并且，對(duì)于所有的屬性，至少存在一個(gè)策略函數(shù)滿足關(guān)系。

上述方案均無法完全滿足該應(yīng)用場(chǎng)景，為此，本文以ABE方案和多跳MKFHE方案為研究對(duì)象，提出了一個(gè)基于LWE問題的、高效的多跳多策略屬性基全同態(tài)加密方案。首先，對(duì)文獻(xiàn)[13]中的SP-ABFHE方案進(jìn)行適當(dāng)變形，該方案可以對(duì)同一策略函數(shù)對(duì)應(yīng)的不同屬性向量下的密文進(jìn)行同態(tài)運(yùn)算，但必須滿足對(duì)所有的屬性向量，都有f（ x ）=0成立。其次，將第一步方案對(duì)應(yīng)到k個(gè)參與方的場(chǎng)景中。最后，利用文獻(xiàn)[12]的多跳多密鑰同態(tài)轉(zhuǎn)化機(jī)制，考慮擁有新的屬性向量和密鑰策略的參與方加入時(shí)的場(chǎng)景，對(duì)密文進(jìn)行擴(kuò)展并正確解密。據(jù)此，可以將第二步方案進(jìn)一步理解為在k-1個(gè)參與方的情況下，新加入一個(gè)參與方的場(chǎng)景，由此遞歸地得到從單個(gè)參與方到多個(gè)參與方的多跳多策略場(chǎng)景。通過一系列假設(shè)游戲，得到本文方案在選擇屬性下的選擇明文攻擊不可區(qū)分性（INDistinguishability under Chosen Plaintext Attack， IND-CPA）安全性。 結(jié)果表明，本文方案在功能上兼具屬性基加密和多跳多密鑰全同態(tài)加密的優(yōu)勢(shì)，即實(shí)現(xiàn)了對(duì)不同策略函數(shù)對(duì)應(yīng)的不同屬性向量下的密文的同態(tài)運(yùn)算和訪問控制，并且新加入?yún)⑴c方的密文可以直接與以前參與方的密文進(jìn)行同態(tài)運(yùn)算。同時(shí)，與文獻(xiàn)[13]中的MP-ABFHE方案相比，本文方案在具有功能優(yōu)勢(shì)的前提下，密文/明文比明顯降低，效率更高。

1 相關(guān)理論基礎(chǔ)

1.1 工具矩陣

1.2 幾個(gè)重要函數(shù)

定義5 [4，7，15] 設(shè)n，q∈ N ，? B 1， B 2，…， B η $?? Z n×Nq， N=n，?? B ?=[ B 1‖ B 2‖…‖ B η]。 假設(shè)策略函數(shù)f∈{0， 1}η→{0， 1}的電路深度為df，并且只包含與非門電路。將 B 1， B 2，…， B η接入電路的線路端口，對(duì)f中的每個(gè)線路端口，u和v表示其左右輸入，定義 B w= G - B u G -1（ B v）， B f=Eval（f， B ?）∈ Z n×Nq，則可以遞歸得到最終輸出矩陣 B f。

推論1 [4，7，15] 考慮 B 1，? B 2，…， B η $?? Z n×Nq，屬性向量 x ∈{0，1}η，? B ?=[ B 1‖ B 2‖…‖ B η]，? xG ?=[ x 1 G n‖ x2 G n‖…‖ x η G n]，那么存在一個(gè)多項(xiàng)式時(shí)間算法，令 H =EvRelation（f， x ， B ?）∈ Z ηN×Nq，滿足[ B f-f（ x ） G ]T= H T·[ B ?- xG ?]T， ‖ H ‖∞≤（N+1）df。

推論2 [16，17] 存在一個(gè)有效的算法TrapGen（1n，q，m），對(duì)于所有的m≥m0=O（n），輸出一個(gè)陷門矩陣對(duì)（ A ， A -1τ0），? A ∈ Z n×mq在統(tǒng)計(jì)上接近于均勻分布，并且對(duì)于任意的τ≥τ0，給定 A -1τ0∈ Z m×nq，可得到 A -1τ。

1.3 KP-ABE方案安全模型

KP-ABE方案的安全模型可以通過攻擊者和挑戰(zhàn)者游戲來定義[13]：

1）攻擊者選擇屬性向量 x 并返還給挑戰(zhàn)者。

2）挑戰(zhàn)者對(duì)參數(shù)初始化，得到公共參數(shù)（Public Parameter， PP）和主私鑰（Master Secret Key， MSK），并將PP返還給攻擊者。

3）攻擊者發(fā)送策略函數(shù)f給挑戰(zhàn)者，發(fā)起詢問;挑戰(zhàn)者接收f后，通過密鑰生成算法得到skf，并將結(jié)果返還給攻擊者。

4）攻擊者將一對(duì)等長(zhǎng)消息μ0、 μ1發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇b∈{0，1}，通過加密算法對(duì)μb進(jìn)行加密，得到屬性向量 x *下的密文，并將密文返還給攻擊者。

5）攻擊者重復(fù)步驟3），進(jìn)行任意多次的詢問，得到skf。

這里是ABE方案的安全性模型，表示攻擊者在獲得挑戰(zhàn)密文后仍然可以向預(yù)言機(jī)進(jìn)行詢問。此處不用修改。

6）攻擊者通過skf對(duì)密文進(jìn)行解密，得到b′。

7）如果對(duì)于所有的fi都滿足fi（ x *）=1，則游戲輸出結(jié)果為b′;否則輸出結(jié)果為一個(gè)隨機(jī)的位數(shù)。

定義攻擊者的優(yōu)勢(shì)為Adv= | Pr[b′=b]-2-1 | 。

2 多跳多策略屬性基全同態(tài)加密方案

方案構(gòu)造分為三步：第一步對(duì)文獻(xiàn)[13]中基于LWE問題的單策略屬性基全同態(tài)加密方案適當(dāng)變形; 第二步將第一步方案對(duì)應(yīng)到k個(gè)參與方的場(chǎng)景;第三步利用文獻(xiàn)[12]中的多跳多密鑰同態(tài)轉(zhuǎn)化機(jī)制將單策略屬性基全同態(tài)加密方案轉(zhuǎn)化為多跳多策略屬性基全同態(tài)加密方案。

本文中，矩陣用大寫字母斜體加粗表示，如 A 、 B 、 C 、 D 、 E 、 F 、 G 、 H 、 I 、 R 、 S 、 V 、 X 等;矢量用小寫字母加粗斜體表示，如 b 、 c 、 d 、 e 、 g 、 r 、 t 、 v 、 w 、 x 等;變量用字母斜體表示，如b、d、i、j、k、m、n、q、u、v、B、M、N、λ、η、、 μ等;函數(shù)用斜體表示，如同態(tài)運(yùn)算電路函數(shù)p、策略函數(shù)f等;上標(biāo)T表示矩陣的轉(zhuǎn)置，上標(biāo)t表示矢量的轉(zhuǎn)置; B 1‖ B 2‖…‖ B η表示矩陣的水平級(jí)聯(lián);對(duì)于整數(shù)k，[k]表示集合{1，2，…，k};對(duì)于安全參數(shù)λ，negl（λ）表示值可忽略的函數(shù)。

2.1 對(duì)SP-ABFHE方案適當(dāng)變形

2.2 將第一步方案對(duì)應(yīng)到k個(gè)參與方場(chǎng)景

對(duì)每個(gè)屬性向量 x ，至少存在一個(gè)策略函數(shù)f，滿足f（ x ）=0。假設(shè)有k個(gè)參與方，對(duì)應(yīng)k個(gè)策略函數(shù)，所得密文對(duì)應(yīng)同態(tài)運(yùn)算電路的k個(gè)輸入，每個(gè)策略函數(shù)至少對(duì)應(yīng)一個(gè)滿足條件的屬性向量。

2.3 采用多跳多密鑰同態(tài)轉(zhuǎn)化機(jī)制

本步驟具體分析了當(dāng)有新的參與方（對(duì)應(yīng)新的屬性向量和新的策略函數(shù)）加入時(shí)密文的擴(kuò)展，并利用新加入的密鑰級(jí)聯(lián)實(shí)現(xiàn)對(duì)擴(kuò)展密文的正確解密，將單策略屬性基全同態(tài)加密方案轉(zhuǎn)化為多跳多密鑰屬性基全同態(tài)加密方案。利用同樣的方法，第二步中k個(gè)參與方的場(chǎng)景同樣可以視為在k-1個(gè)參與方的情況下，新加入一個(gè)參與方的情況，由此遞歸地得到從單個(gè)參與方到多個(gè)參與方的多跳多策略場(chǎng)景。

3 方案分析

3.1 同態(tài)運(yùn)算分析

假設(shè)密文組ct1=（ C 1， F 1， D 1）， ct2=（ C 2， F 2， D 2）分別為對(duì)消息μ1、 μ2的加密，對(duì)應(yīng)的承諾隨機(jī)性分別為 S 1、 S 2。在有k個(gè)參與方的情況下， C ∈ Z k（m+N+1）×kMq，? D ∈ Z knM×Mq，? F ∈ Z （m+N+1）×Mq。

3.1.1 同態(tài)加法運(yùn)算

均滿足同態(tài)加法性質(zhì)。

3.1.2 同態(tài)乘法運(yùn)算

3.2 安全性分析

本文方案的安全性可以利用KP-ABE的安全性模型來證明。通過一些列假設(shè)，對(duì)方案的密文組ct=（ C ， F ， D ）進(jìn)行分析，得出結(jié)論：在標(biāo)準(zhǔn)的選擇游戲中，任何多項(xiàng)式時(shí)間敵手都無法以不可忽略的概率區(qū)分密文組ct和同等維度的均勻矩陣集合。即在LWE假設(shè)下，方案為選擇屬性下的IND-CPA安全。對(duì) C 、 F 的分析又有以下轉(zhuǎn)化：

1）對(duì)密文矩陣 C 、 F 的分析可以轉(zhuǎn)化為對(duì)矩陣組（ C ?A ， C 0， c v， C ?x ）的分析。

2）定義：

C??? ～?? =?? F ?C ?x?? =

A??? ～?? T x ?S + E??? ～? +? μ G ?0

（18）

3） S ， E ?A ， e v， R i， j為均勻選取，且 E i[j]= R Ti， j· E ?A [j]，i∈[η]，? S 和 E??? ～? 的各列為相同的獨(dú)立分布。

由以上分析可知，對(duì)密文矩陣 C 、 F 的分析最終可以轉(zhuǎn)化為對(duì) C??? ～?? 的任意一行的前半部分的分析，即 c ?= A??? ～?? T x ?s + e ?，其中 s 為 S 的任意列， e ?=[ e T A ‖ e T0‖ e v‖ e T1‖ e T2‖…‖ e T]T， e i= R Ti e ?A ，均勻選取 R i $? {0，1}m×N。即在標(biāo)準(zhǔn)的選擇游戲中，多項(xiàng)式時(shí)間敵手無法以不可忽略的概率區(qū)分 c ?和同等維度的均勻選取的向量。

因此，方案的證明轉(zhuǎn)化為對(duì) c ?和 D 的證明，即多項(xiàng)式時(shí)間敵手無法以不可忽略的概率區(qū)分 c ?， D 和同等維度的完全均勻選取的向量、矩陣。具體證明過程如下：

設(shè) x *為選擇的屬性向量，則對(duì)于所有的策略函數(shù)都有fi（ x *）=1。設(shè)Game i表示第i個(gè)游戲，Adv[i]表示多項(xiàng)式時(shí)間敵手在第i個(gè)游戲中的優(yōu)勢(shì)，敵手最終優(yōu)勢(shì)可表示為Adv= | Pr[b′=1 | ?c ?， D ]-Pr[b′=1 | uniform] | 。

Game 0：標(biāo)準(zhǔn)的選擇游戲，Adv=Adv[0]。

Game 1：與Game 0相比，不同之處在于改變 B 0和 B ?的生成方式，即令 B i= AR i+xi G n。

引理1 [4，18] 假設(shè)m>（n+1）+ω（），且q為素?cái)?shù)。均勻選取矩陣 A ， B? $?? Z n×mq，? R? $? {-1，1}m×m，那么對(duì)于所有的向量 ω ∈ Z mq，分布（ A ， AR ， R T ω ）統(tǒng)計(jì)接近分布（ A ， B ， R T ω ）。

文獻(xiàn)[13]中指出，當(dāng)矩陣 A 統(tǒng)計(jì)接近于均勻分布，q為任意正整數(shù)時(shí)，上述引理仍然成立。因此，由引理可知，Game 0和Game 1游戲中的 B 0、? B ?具有不可區(qū)分性，

即 | Adv[1]-Adv[0] | =negl （λ）。

Game 2：與Game 1相比，不同之處在于改變私鑰 t 的生成方式，即令：

[ r f‖ r ′f] $? [ A ‖ B 0+ B f]-1P（- v ）

P= D ?Z m，τ×{0，1}N

由Game 1可知：

B ?= AR ?+ x? G

R ?=[ R 1‖ R 2‖…‖ R ]

H = H f，x， B

[ B f-f（ x ） G n]=[ B ?- x? G ?] H

則

B f- G n=[ A ?R ?+ x? G ?- x? G ?] H = A ?R ??H + G n

[ A ‖ B 0+ B f]=[ A ‖ A （ R 0+ R ??H ）+ G n]

推論3 [13，19] n、m、q、N為選取參數(shù)，滿足m>nlogq， N=nlogq，矩陣 A? $?? Z n×mq統(tǒng)計(jì)接近于均勻分布，對(duì)于所有矩陣 R ∈ Z m×N，可以得到分布[ A ‖ AR + G n]-1P，其中P= D ?Z m，τ×{0，1}N， τ=O（N mn ·‖ R ‖∞）。另外，對(duì)于所有的 v ，[ A ‖ AR + G n]-1P的最后N個(gè)坐標(biāo)的邊緣分布統(tǒng)計(jì)接近于{0，1}N上的均勻分布。

由推論3可知，給定 R 0、 R 、 H ，可以得到分布[ A ‖ B 0+ B f]-1P，其中P= D ?Z m，τ×{0，1}N， τ≥τ′=O（N mn ·‖ R 0+ R ??H ‖∞）。由‖ H ‖∞≤（N+1）df，‖ R i‖∞=1可知，‖ R 0+ R ??H ‖∞≤N（N+1）df， τ′=O（N2 mn ·（N+1）df）。Game 1中邊緣分布 r ′f $? {0，1}N， r Tf= A -1τ[-（ B 0+ B f） r f′T- v ]，條件分布[ r f‖ r ′f]在整數(shù)格的適當(dāng)陪集上是離散高斯分布。由推論和Game 1中的分析可知，Game 2通過適當(dāng)設(shè)置參數(shù)τ， 可以得到與Game 1統(tǒng)計(jì)接近的分布，即 | Adv[2]-Adv[1] | =negl （λ）。

Game 3：與Game 2相比，不同之處在于改變矩陣 A 的分布，即均勻選取矩陣 A? $?? Z n×mq。

由推論2可知，Game 2和Game 3得到的矩陣 A 具有不可區(qū)分性，即： | Adv[3]-Adv[2] | =negl （λ）。

Game 4：與Game 3相比，不同之處在于改變密文 c ?的形式。令 d = A T s + e A，dv= v Ts+ e v。由 B i= AR i+xi G n，? E i= R Ti· E ?A ，可知：

R T0 d = R T0 A T s + R T0 e ?A = B T0 s + e 0

R T1 d = R T1 A T s + R T1 e ?A =（ B 1- x 1 G n）Ts+ e 1，

R Td= R T A T s + R T e ?A =（ B - xG n）T s + e

c ?= A??? ～?? T x ?s + e ?=?? A T· s + e ?A

B T0· s + e 0

v T· s +ev

（ B ?- x? G ?）T· s + e ?x?? =

d

R T0 d

dv R T1 d

R T2 dR T d??? （19）

因此，Game 4與Game 3中的 c ?只在形式上不同，內(nèi)容上完全相同，即Adv[4]=Adv[3]。

Game 5：與Game 4相比，不同之處在于改變 d 、dv的分布，即令 d 、dv為均勻分布。

定理1 [14，20-22] n為格的維度，q=q（n）， χ為B有界的高斯分布，B≥ω（logn）· n 。對(duì)于參數(shù)n、 q、 χ，如果存在一個(gè)有效的算法能夠解決平均情況下的LWE問題，那么：

1）對(duì)任意n維格，存在一個(gè)有效的量子算法，能夠解決近似因子為O （nq/B）的GapSVP（Gap Version of Shortest Vector Problem）。

2）對(duì)任意n維格，如果q=q（n）≥O （2 n 2 ），則存在一個(gè)有效的經(jīng)典算法，能夠解決近似因子為O （nq/B）的GapSVP。

由定理1可知，Game 5與Game 4中的 d 、 dv具有不可區(qū)分性。即 | Adv[5]-Adv[4] | =negl （λ）。

Game 6：最終，改變 c ?的分布，即令其為均勻分布。由引理1可知，分布（ A ， d T， AR i， d T R i）統(tǒng)計(jì)接近于均勻分布。則， ?| Adv[6]-Adv[5] | =negl （λ）。同時(shí)，由以上游戲可知， c ?的各部分都為均勻分布，則在本游戲中 c ?也為均勻分布，即有Adv[6]=0。因此，得到 | Pr[b′=1 | ?c ?]-Pr[b′=1 | uniform] | =negl （λ）。

Game 7：與Game 6相比，不同之處在于改變矩陣 D 的生成方式，即隨機(jī)均勻選取矩陣 D ?，則 D 也為均勻獨(dú)立分布。由上述定理1可知，Game 7與Game 6中的 D 在計(jì)算上具有不可區(qū)分性，即Adv[7]= | Adv[7]-Adv[5] | =negl （λ）， | Pr[b′=1 | ?D ]-Pr[b′=1 | uniform] | =negl （λ）。

由Game 6和Game 7中的結(jié)論可知，Adv= | Pr[b′=1 | ?c ?， D ]-Pr[b′=1 | uniform] | =negl （λ）。

證畢。

3.3 性能分析

下面從方案的工作環(huán)境、困難性假設(shè)、密文/明文規(guī)模比和單個(gè)參與方的私鑰大小方面，將本文方案與文獻(xiàn)[12-13]中的方案進(jìn)行對(duì)比。其中，n為L(zhǎng)WE問題的維度變量，=「logq， m≥O（n）， N=n， η表示屬性向量的長(zhǎng)度。文獻(xiàn)[13]#1表示文獻(xiàn)[13]中的SP-ABFHE方案;文獻(xiàn)[13]#2表示文獻(xiàn)[13]中的MP-ABFHE方案;文獻(xiàn)[12]表示該文獻(xiàn)中的第一個(gè)多跳多密鑰全同態(tài)加密方案。具體分析如表1和表2所示。

對(duì)比分析可知：

1）與文獻(xiàn)[13]中的MP-ABFHE方案對(duì)比，本文方案允許新的參與方密文直接加入同態(tài)運(yùn)算，實(shí)現(xiàn)了多跳功能;而且在不改變單個(gè)參與方的私鑰尺寸的同時(shí)，密文/明文比明顯降低，效率更高。

2）與文獻(xiàn)[13]中的SP-ABFHE方案對(duì)比，在不改變單個(gè)參與方私鑰尺寸的情況下，本文方案實(shí)現(xiàn)了多跳和多策略功能;同時(shí)由于允許更多參與方的動(dòng)態(tài)運(yùn)算，因此方案密文/明文比有所增加。

3）與文獻(xiàn)[12]中的多跳MKFHE方案相比，本文方案將屬性基加密與多跳多密鑰全同態(tài)加密相結(jié)合，能夠?qū)崿F(xiàn)對(duì)密文更加靈活的細(xì)粒度訪問控制;同時(shí)由于引入屬性向量和策略函數(shù)，單個(gè)參與方的私鑰尺寸和密文/明文比都有所增加。

4 結(jié)語(yǔ)

本文提出了一個(gè)基于LWE問題的、高效的多跳多策略屬性基全同態(tài)加密方案，并證明了該方案為選擇屬性下的IND-CPA安全。與以往方案相比，本文方案在功能上兼具屬性基加密和多跳多密鑰全同態(tài)加密的優(yōu)勢(shì);并且本文方案在不改變單個(gè)參與方私鑰尺寸的情況下，密文/明文比明顯降低，效率更高。然而不足之處在于本文方案的密文規(guī)模和運(yùn)算復(fù)雜度依然很大，其主要原因在于SP-ABE方案的構(gòu)造復(fù)雜，下步工作將對(duì)底層的SP-ABE方案進(jìn)行優(yōu)化，以降低運(yùn)算復(fù)雜度，提高效率;其次，支持隱私保護(hù)和用戶撤銷的屬性基加密方案能夠解決云環(huán)境中用戶屬性更新和隱私安全問題[23]，下步工作考慮將其與MKFHE相結(jié)合，更好地保護(hù)用戶隱私;最后，生物特征認(rèn)證與屬性基加密在模式對(duì)應(yīng)關(guān)系上具有很大的相似性，與同態(tài)加密的結(jié)合也是近幾年的研究熱點(diǎn)[24]。下步工作將從以上三個(gè)方面進(jìn)行研究，擴(kuò)展多密鑰全同態(tài)加密的應(yīng)用場(chǎng)景。

參考文獻(xiàn)

[1]??SAHAI A， WATERS B. Fuzzy identity-based encryption [C]// ?Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques， LNCS 3494. Berlin： Springer， 2005： 457-473.

[2]?GOYAL V， PANDEY O， SAHAI A， et al. Attribute-based encryption for fine-grained access control of encrypted data [C]// Proceedings of the 13th ACM Conference on Computer and Communications Security. New York： ACM， 2006： 89-98.

[3]?GORBUNOV S， VAIKUNTANATHAN V， WEE H. Attribute-based encryption for circuits [C]// Proceedings of the 45th ACM Symposium on Theory of Computing. New York： ACM， 2013： 545-554.

[4]?BONEH D， GENTRY C， GORBUNOV S， et al. Fully key-homomorphic encryption， arithmetic circuit ABE and compact garbled circuits [C]// Proceedings of the 2014 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 8441. Berlin： Springer， 2014： 533-556.

[5]??GENTRY C. Fully homomorphic encryption using ideal lattices[C]// Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York： ACM， 2009： 169–178.

[6]?BRAKERSKI Z， GENTRY C， VAIKUNTANATHAN V. （Leveled） fully homomorphic encryption without bootstrapping [C]// Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York： ACM， 2012： 309–325.

[7]??GENTRY C， SAHAI A， WATERS B. Homomorphic encryption? from learning with errors： conceptually-simpler， asymptotically-faster， attribute-based [C]// Proceedings of the 33rd Annual Cryptology Conference， LNCS 8042. Berlin： Springer， 2013： 75-92.

[8]?ALPERIN-SHERIFF J， PEIKERT C. Faster bootstrapping with polynomial error [C]// Proceedings of the 34rd Annual Cryptology Conference， LNCS 8616. Berlin： Springer， 2014： 297-314.

[9]?LPEZ-ALT A， TROMER E， VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption [C]// Proceedings of the 44th Annual ACM Symposium on Theory of Computing. New York： ACM， 2012： 1219-1234.

[10]?CLEAR M， MCGOLDRICK C. Multi-identity and multi-key leveled FHE from learning with errors [C]// Proceedings of the 35th Annual Cryptology Conference， LNCS 9216. Berlin： Springer， 2015： 630-656.

[11]??MUKHERJEE P， WICHS D. Two round multiparty computation? via multi-key FHE [C]// Proceedings of the 35th Annual International Conference on Theory and Applications of Cryptographic Techniques， LNCS 9666. Berlin： Springer， 2016： 735-763.

[12]?PEIKERT C， SHIEHIAN S. Multi-key FHE from LWE， revisited [C]// Proceedings of the 13th Theory of Cryptography Conference， LNCS 9986. Berlin： Springer， 2016： 217-238.

[13]?BRAKERSKI Z， CASH D， TSABARY R， et al. Targeted homomorphic attribute-based encryption [C]// Proceedings of the 13th Theory of Cryptography Conference， LNCS 9986. Berlin： Springer， 2016： 330-360.

[14]??MICCIANCIO P， PEIKERT C. Trapdoors for lattices： simpler， tighter， faster， smaller [C]// Proceedings of the 31th Annual International Conference on Theory and Applications of Cryptographic Techniques， LNCS 7237. Berlin： Springer， 2012： 700-718.

[15]??GORBUNOV S， VAIKUNTANATHAN V， WICHS D. Leveled fully homomorphic signatures from standard lattices [C]// Proceedings of the 47th Annual ACM Symposium on Theory of Computing. New York： ACM， 2015： 469-477.

[16]?GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions [C]// Proceedings of the 40th Annual ACM Symposium on Theory of Computing. New York： ACM， 2008： 197-206.

[17]??BRAKERSKI Z， LANGLOIS A， PEIKERT C， et al. Classical? hardness of learning with errors [C]// Proceedings of the 45th Annual ACM Symposium on Theory of Computing. New York： ACM， 2013： 575-584.

[18]??AGRAWAL S， BONEH D， BOYEN X. Efficient lattice （H） IBE in the standard model [C]// Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 6110. Berlin： Springer， 2010： 553-572.

[19]?LYUBASHEVSKY V， WICHS D. Simple lattice trapdoor sampling from a broad class of distributions [C]// Proceedings of the 18th IACR International Workshop on Public Key Cryptography， LNCS 9020. Berlin： Springer， 2015： 716-730.

[20]?REGEV O. On lattices， learning with errors， random linear codes， and cryptography [C]// Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York： ACM， 2005： 84-93.

[21]?PEIKERT C. Public-key cryptosystems from the worst-case shortest vector problem： extended abstract [C]// Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York， ACM， 2009： 333-342.

[22]?MICCIANCIO D， MOL P. Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions [C]//Proceedings of the 31st Annual Cryptology Conference， LNCS 6841. Berlin： Springer， 2011： 465-484.

[23]?閆璽璽，葉青，劉宇. 云環(huán)境下支持隱私保護(hù)和用戶撤銷的屬性基加密方案[J]. 信息網(wǎng)絡(luò)安全，2017，17（6）：14-21. （YAN X X， YE Q， LIU Y. Attribute-based encryption scheme supporting privacy preserving and user revocation in the cloud environment[J]. Netinfo Security， 2017，17（6）：14-21.）

[24]??游林，梁家豪. 基于同態(tài)加密與生物特征的安全身份認(rèn)證研究[J]. 信息網(wǎng)絡(luò)安全，2018，18（4）：1-8.? （YOU L， LIANG J H. Research on secure identity authentication based on homomorphic encryption and biometric [J]. Netinfo Security， 2018，18（4）： 1-8.）