適應性安全的可追蹤叛徒的基于屬性加密方案

馬海英，曾國蓀，陳建平，王金華，王占君

?

適應性安全的可追蹤叛徒的基于屬性加密方案

馬海英1，曾國蓀2，陳建平1，王金華3，王占君3

(1. 南通大學計算機科學與技術學院，江蘇南通226019； 2. 同濟大學計算機科學與技術系，上海201804；3. 南通大學理學院，江蘇南通 226007)

針對基于屬性加密(ABE, attribute-base encryption)機制存在的密鑰濫用問題，為每個用戶增加唯一的身份標識符，將聯合安全編碼和叛徒追蹤機制引入到ABE方案中，給出適應性安全的可追蹤叛徒ABE的定義、安全模型和可追蹤模型，提出一種適應性安全的可追蹤叛徒的ABTT方案，該方案允許適應性追蹤指定策略盜版解碼器中的叛徒。基于合數階群上的子群判定假設和DDH假設，證明所提方案是適應性安全和適應性可追蹤的。因此，所提方案不僅可以適應性追查指定策略盜版解碼器中的叛徒，而且進一步增強了ABE系統的安全性，具有一定的理論和應用價值。

基于屬性加密；叛徒追蹤；雙系統加密；適應性安全；聯合安全編碼

1 引言

基于屬性加密(ABE, attribute-base encryption)機制作為一種新型的一對多的公鑰加密機制，實現了對加密數據的細粒度訪問控制[1,2]。然而，在ABE系統中，用戶的訪問權限與其私鑰直接關聯[3,4]。一個密文可以被滿足訪問策略的多個用戶解密，如果合法用戶泄露自己的私鑰構造盜版解密設備，并將其分發給非法用戶，則系統的訪問控制策略將被打破[5,6]。特別的，用戶私鑰僅與其屬性相關，不同用戶可能會有相同屬性，而與用戶的任何特定信息(如身份)無關，即使盜版密鑰被發現，也無法將其與任何合法用戶相關聯。因此，惡意用戶可以輕易地與他人共享自己的私鑰而不用擔心被追究責任[5]，稱這些惡意用戶為叛徒。

針對基于屬性加密中的密鑰濫用問題，學者們進行了深入的研究，提出了不同的解決方案。2008年，Hinek等[3]提出一種基于標號的ABE方案。在該方案中，當用戶需要解密密文時，利用在線的可信第三方，如果惡意用戶拷貝或代理生成私鑰，并分發給他人時，則將會導致該用戶的個人隱私信息被泄露。該方案有效地抵制了ABE中密鑰拷貝或密鑰代理攻擊，對預防密鑰濫用起到威懾作用。但是，該方案不能追究密鑰濫用者的責任。2009年，Yu等[7]和Li等[6]基于DBDH和D-Linear假設分別提出了防密鑰濫用密鑰策略ABE方案和可追責的匿名密文策略ABE方案，可追查到叛徒的真實身份，解決了ABE中叛徒非法行為的責任追究問題。2011年，Wang等[5]將聯合安全編碼[8]和叛徒追蹤技術[9]引入到ABE機制中，提出了基于屬性的叛徒追蹤方案。然而，上述方案僅滿足較弱的選擇安全模型，即攻擊者必須在生成系統公鑰之前選擇攻擊目標。在實際應用的ABE系統中，系統公鑰生成之后，攻擊者可以適應性地選擇攻擊目標，構造盜版解碼設備。因此，上述方案均不能滿足實際密碼系統對適應性安全的應用需求。同時，Wang等[5]將如何構建適應性安全的基于屬性加密的叛徒追蹤方案作為一個公開問題被提出。2013年，Liu等[10]提出了適應性安全的可追蹤叛徒的密文策略ABE方案，將盜版解碼器分為2種：1) 類密鑰盜版解碼器，顯式地給出一個屬性集，并將相應的私鑰固化在盜版設備中，只要該屬性集滿足密文中訪問策略，就能以不可忽略的概率解密密文；2) 指定策略盜版解密器，明確給出一個訪問策略，該盜版解碼器能以不可忽略的概率解密在該訪問策略下加密的密文。該方案能夠適應性追蹤類密鑰盜版解碼器，但僅能選擇性追蹤指定策略盜版解密器。

為了構造出可適應性追蹤指定策略盜版解密器中叛徒的ABE方案，本文需要解決以下2個問題。1) 由于在ABE機制中，可能存在多個用戶具有相同屬性集合，所以，ABE機制不能根據屬性集合來嚴格區分用戶。然而，叛徒追蹤方案要求必須能夠嚴格區分每一個用戶。因此，每個用戶除了擁有一個屬性集合，還引入一個身份信息，即采用一對值(,)來標識每個用戶。此外，為了使用戶身份具有唯一性，本文利用聯合安全編碼[9]技術，將每個用戶身份映射到一個碼字。2) 授權中心根據用戶的身份屬性對(,)生成相應私鑰，該私鑰必定包含與身份對應的成分。為了保證本方案仍然是ABE方案，還需要解決另一個問題，即解密能否成功僅與用戶擁有的屬性集合相關，而與用戶身份無關。本文在密文中引入一個向量，通過合理設計解密算法，使解密時能將密文和用戶私鑰中的身份信息相互抵銷，不影響解密的前提條件。

本文通過修改Lewko等[11]提出的適應性安全的密文策略ABE方案，采用非對稱的雙線性對技術，將聯合安全編碼技術和Abdalla等[9]提出的叛徒追蹤算法引入到該密文策略ABE方案中，提出一種適應性安全的可追蹤叛徒的ABE方案。基于合數階群上的子群判定假設和DDH假設，利用雙系統加密技術[12]，通過一系列混合討論，證明本方案是適應性安全和適應性追蹤指定策略盜版解密器中的叛徒。因此，本方案不僅可以適應性追查叛徒，而且進一步增強了ABE系統的安全性，具有一定的理論和應用價值。

2 預備知識

2.1 聯合安全編碼

本節將簡述聯合安全編碼的相關概念和結論，結合本文所提方案，采用文獻[9]的符號來描述其定義。一個聯合安全編碼可以用(, N,)-聯合安全碼來表示，其中，表示叛徒追蹤算法可允許的串謀用戶的最大取值，N表示系統中用戶的最大數目，表示追蹤算法出錯的概率值, 這樣的一個聯合安全碼可以由長度為=(2(log(N)+log()))的碼字和一個長度2的字母表來生成。

一個字母表為，長度為的聯合安全編碼由一個集合和一個追蹤算法T組成。集合= {w(i)| 1 ≤≤N,?{0,1}l}，記作編碼本，其中，是長度為l的0和1的字符串，對1≤≤N,w(i)是索引的碼字。對于最多為個串謀用戶集合C?{1, ???, N}，= { w(i),?C }，和所有的多項式時間算法A，聯合安全碼滿足Pr[T(,)?C?();A();{0,1}l]1。

這個概率值是由隨機數、隨機算法A和追蹤算法T來決定的，A()表示當隨機算法A在輸入集合時，把輸出結果賦值給；{0,1}l表示根據均勻分布選擇的隨機值?{0,1}l。聯合安全編碼的詳細資料可以參考文獻[9]。

2.2 非對稱合數階雙線性群和困難問題假設

下面給出非對稱合數階群上的困難問題假設，假設給定一個群生成器G，輸入系統安全參數，輸出非對稱合數階雙線性群的描述(=123,1,2,G,)，其中，1,2,G均是階為=123的循環群，雙線性映射：1×2→G滿足下列條件。1)雙線性：1∈1,1∈2;,∈Z;(1-,1)(1,1)。2)非退化性：1∈1,1∈2使(1,1)在G中的階為。3)可計算性：群1,2,G中的運算以及雙線性映射都是在多項式時間內可計算的。4)正交性：令1, pi表示群1的p階子群，2, pj表示群2的p階子群(= 1, 2, 3;= 1, 2, 3)，如果1, p,2, p, 且時,(g, h) =1為G的單位元，則稱其為群1和2上的正交性。令1,和2,分別表示群1和群2的pp階子群，下面給出非對稱合數階群上子群判定困難問題假設。

2.3 訪問結構和線性秘密共享方案(LSSS)

定義1 (訪問結構[11])。假定P ={P1, P2, P3, ??, P}是個參與者的集合，由P的某些非空子集構成的集族，稱其為訪問結構，其中，集族2，且是單調的，即對任意集合,，均有：如果且，那么。中的所有集合稱為授權集，不在中的集合稱為非授權集。

定義2 (LSSS[11])。在參與者集合P={P1, P2, …, P}上構造一個秘密共享方案Π是線性的，如果有：1)將Z上的一個向量構造成參與者的秘密分享值；2)對于這個秘密共享方案Π，存在一個1×2的秘密份額生成矩陣和行標號函數: {1, …,1}→P，假定∈Z是待共享的秘密值，隨機選擇2,3, …,r2∈Z，構成向量= (,2, …,r2)，設'為的轉置，則'是1個秘密份額構成的向量，根據標號函數將秘密份額λ= ()(1≤≤1)分配給參與者()。

將LSSS引入到本文所提方案中，將屬性作為參與者，則所有的授權屬性集均包含在訪問結構。

3 適應性安全ABTT定義和安全模型

本節描述適應性安全的可追蹤叛徒的基于屬性加密(ABTT, adaptively secure attribute-based encryption for traitor tracing)的形式化定義、安全模型和可追蹤模型。在本方案中，每個用戶使用一個對(,)來標識，其中，表示用戶的身份，表示用戶擁有的屬性集合，且不同用戶可以具有相同的屬性集合。

3.1 適應性安全ABTT的定義

一個可追蹤叛徒的基于屬性加密方案形式上可以由以下5個概率多項式時間算法來構成。

1) 初始化算法。該算法輸入安全參數和系統全部屬性集合，輸出系統公鑰和主密鑰。

2) 私鑰生成算法。該算法輸入主密鑰和用戶的身份屬性對(,)，輸出該用戶的私鑰K,ω。

3) 加密算法。該算法輸入消息訪問結構(,)和系統公鑰，輸出一個密文。

4) 解密算法。該算法輸入一個密文、一個用戶私鑰K, ω和公鑰，僅當私鑰中的屬性集合能夠滿足密文中的訪問結構時，輸出明文；否則，輸出^表示解密失敗。

5) 叛徒追蹤算法。針對訪問結構(,)的盜版解密設備，該算法擁有對該設備的訪問權限，輸出一組用戶的身份，與這些身份對應的用戶被認為是叛徒。

本方案的正確性可以描述為。系統運行初始化算法生成和，對于所有消息∈{0,1}*, 用戶身份，當滿足(,)時,Dec(KeyGen(,,), Enc(, (,),)) =的概率為1。

3.2 安全模型

本方案的適應性安全模型是通過挑戰者S和攻擊者A之間的交互性游戲來定義的。

1) 初始化：挑戰者S運行本方案的初始化算法，并將生成的公鑰發送給攻擊者A。

step1 A適應性地詢問用戶(,)的私鑰，挑戰者生成私鑰并其發送給A，A可以重復多次詢問私鑰。

2) 挑戰階段：A向挑戰者S提交訪問結構(,)、等長消息0和1，S拋擲一枚公平硬幣∈ {0,1}, 計算= Enc(M, (,),)，并將發送給A。

step2 重復執行step1。

3) 猜測階段：A輸出對挑戰密文的一個猜測值'∈ {0,1}。

若'=，且攻擊者A在step1和step2中從未詢問這類用戶(,)的私鑰，其中，滿足挑戰訪問結構(,)，則稱A贏得了這個游戲。攻擊者A在上述游戲中獲勝的優勢定義為：AdvA=|Pr['=]?|。

定義3 如果任意多項式時間攻擊者A贏得上述游戲的優勢都是可以忽略的，則稱這個可追蹤叛徒的基于屬性加密方案是適應性安全的。

3.3 可追蹤模型

本節將構造出一種適應性安全的可追蹤模型。在該模型下，攻擊者可以自適應的選擇挑戰訪問結構，且擁有一個針對該訪問結構的盜版解密設備的訪問權限。令,表示相關的2個安全參數，可追蹤模型可以通過挑戰者S和攻擊者A之間的交互性游戲進行如下描述。

1) 初始化。挑戰者S運行本方案的初始化算法，將生成的公鑰發送給攻擊者A。

2) 私鑰生成詢問。A可以多次詢問屬性身份對(ω, ID)的解密私鑰，其中，下標表示第次詢問。

3) 生成盜版解密設備。A構造一個針對挑戰訪問結構(,)的盜版解密設備，是一個概率電路的描述，當向輸入隨機密文時，輸出消息。

令T表示攻擊者A提交的私鑰詢問的用戶身份集合，且要求在該集合中的任意身份ID對應的屬性集合ω滿足挑戰訪問結構(,)，如果同時滿足如下3個條件，則說攻擊者A在可追蹤游戲中獲勝。

2) Q =?或Q?T。

3) 攻擊者A提交的所有私鑰生成詢問中最多有個不同用戶的身份，且與這些身份一起詢問的屬性集合滿足挑戰訪問結構(,)。對于不滿足挑戰訪問結構(,)的屬性集合，攻擊者的私鑰生成詢問次數不需要限制。

攻擊者A在上述游戲中獲勝的概率可定義為A打破本方案可追蹤性的優勢。如果任意多項式時間的攻擊者A在上述追蹤游戲中的優勢是關于的可忽略函數，那么可追蹤叛徒的基于屬性加密方案是-TT-CPA安全的。

4 適應性安全ABTT方案

本方案采用非對稱雙線性對技術來構建，即：1×2→G, 存在一個可有效計算的同構映射：2→1，且要求該同構映射是不可逆的。本方案利用Z*中的部分元素來表示系統所有屬性的集合，假定= {1,2, ···,N}表示所有用戶的集合，表示符號字母表的大小，用長度為的字符串來表示一個碼字，選擇一個集合{1, 2, ···, N}上的隨機置換。可信授權中心維持從用戶ID到碼字w(j)的映射，其中，是聯合安全編碼的隨機串。對于非二進制的字母表，可以使用一個長度為=élbù的位串表示一個碼字，?{0,1}表示一個碼字的位串編碼，cw表示中的第位。選擇一個長度為(+1)的向量= (0,1, ···,f)，其中，f?2, p1，令(f) =e，向量= (0,1, ···,e)是同構映射作用在向量上的映像。設f=(= 0,1, ···,), 則e=(f) =。利用向量和定義Waters散列函數[5,8]

其中，是滿足cw=1的所有的集合。

Setup(,)→(,)該初始化算法根據系統安全參數生成階=123的乘法循環群1、2和G,令1, p1和2, p1分別是群1和2的1階子群，1,1,3分別是1, p1,2, p1,2, p3的生成元，且滿足1=(1)。可信授權中心(TA)隨機選擇,?Z，對每個屬性?，隨機選擇s?Z。此外，TA生成如上所述的2個向量和，選擇秘密隨機置換和用于聯合安全編碼的秘密值?{0,1}l，將每個用戶的映射到各自的碼字，生成系統公鑰和主密鑰為

KeyGen(,,) →SK, ω假定用戶擁有身份和屬性集合，該私鑰生成算法隨機選擇,'?Z，0,0',0"?2, p3, 對每一個屬性?，隨機選擇R?2,p3, 令對應的碼字為，計算用戶私鑰SK, ω為

Enc((,),,) →該加密算法利用訪問結構(,)和公鑰對消息進行加密，其中，是一個1×2的矩陣，是一個從的每一行到一個屬性()的映射。該算法隨機選擇,2, …,vZ，組成隨機向量= (,2, …,v2)。對矩陣的每個行向量，隨機選擇, 計算密文如下

Dec(,SK, ω,) →假定密文中的訪問結構是(,)，僅當用戶私鑰SK, ω中的屬性集合滿足(,)時，該解密算法可以成功解密密文，否則，解密失敗。解密密文需要執行如下過程，首先計算，其中，是使cw=1的所有的集合。然后，計算一組常量c?Z，使得。計算

T((,),) →Q可信授權中心執行該叛徒追蹤算法，該算法擁有一個對訪問結構(,)的盜版解密設備的訪問權限。令()表示關于的一個不可忽略函數，能以概率()成功解密在(,)下加密的密文。令表示4中的第(élbù(?1)+)個元素。對每一個1≤≤和1≤≤élbù，該算法初始化計數器ctr,j=0，執行次下面的測試過程。

1) 選擇一個隨機消息。

2) 用訪問結構(,)加密消息，并生成一個密文((,),0,1,2,x,3,x,4,)

3) 從1中隨機選擇一個元素代替。

4) 使用替換后的密文訪問。

5) 若D輸出，則計數器的值ctr,j←ctr,j+1。

完成以上循環，位串'可以按如下規則重新構成，讓',j表示'的第élbù(?1)+位，如果ctr,j≤4則',j=1，否則',j= 0。然后，把位串解碼為長度是的符號串，最后利用聯合安全編碼的追蹤算法計算QTC(,)，并輸出叛徒的身份的集合。

上述方案的正確性計算過程如下

5 安全性和追蹤性證明

為了證明本方案的安全性和追蹤性，需要首先定義半功能密文和半功能私鑰，然后將半功能私鑰進一步分為1型半功能私鑰和2型半功能私鑰，但它們不會被應用在真實的系統中。為了構造半功能密文和半功能私鑰，需要選擇一些共用的參數2?2, p2，2=(2)，對每個屬性?，隨機選擇z?Z。對= 0, 1,…,, 隨機選擇δ?Z。

半功能密文：半功能密文算法首先利用加密算法生成正常密文((,),0,1,2,x,3,x,4,")，選擇隨機值?Z和隨機向量?，對訪問矩陣的每一行，隨機選擇γ?Z, 計算半功能密文如下

1型半功能私鑰：該算法隨機選擇,,,'?Z,0,0',0'',R?2, p3，計算1型半功能私鑰為

2型半功能私鑰：該算法隨機選擇,,'?Z,0,0',0'',R?2, p3，選擇子群2, p2的生成元2，計算2型半功能私鑰為

值得注意的是，2型半功能私鑰相當于將1型半功能私鑰的指數= 0。當使用半功能私鑰解密半功能密文時，得到多余項為，其中，1是向量的第一個分量，即<1, 0,…, 0>。此時，半功能密文和1型半功能私鑰中的z是相同的，當用半功能私鑰解密半功能密文時，這些z值將會被消掉，從而不影響解密。相反地，這些z是用來隱藏半功能密文在子群1, p2中被共享1的值。這里要求訪問結構中的每個屬性只能使用一次，當攻擊者有一個不能解密挑戰密文的1型半功能私鑰時，根據信息理論可知，它能獲知關于z的信息是可忽略的。如果在訪問結構中每個屬性可以多次使用，則z的值將會多次暴露給攻擊者。在下列定義的每個游戲中，1型半功能私鑰至多出現一次，其他半功能私鑰都是2型的，這樣就可以避免多次泄露z的值。

如果?1=0，則稱該1型半功能私鑰是名義半功能私鑰，即名義半功能私鑰可以成功解密相應的半功能密文。

5.1 安全性分析

本文所提方案是通過修改文獻[11]的密文策略ABE方案而構造的，本文方案的安全性證明過程與這個密文策略ABE方案類似，基于假設1～假設3，可以證明本文方案是適應性安全的。由于篇幅有限，本文不做詳細說明，其具體安全性證明過程可以參考文獻[11]。

5.2 可追蹤性證明

基于子群1,1上的DDH假設和合數階群2上的靜態假設1、2、4、5，利用混合爭論技術，借助一系列相鄰游戲(TraceReal, Trace0, Trace1,1, Trace1,2,…, Trace?1,2, Trace,1, Trace,2,…, Trace?1,2, Trace,1, Trace,2)的不可區分性，證明本文方案的可追蹤性，其中，是攻擊者詢問私鑰的最大次數。

TraceReal：一個真實的本方案的可追蹤性游戲，私鑰和密文都是正常的。

Trace0：與TraceReal類似，除了挑戰者S生成半功能密文發送給盜版解碼器。

Trace,1：與Trace0類似，除了前?1次詢問的私鑰是2型半功能的，第次詢問私鑰是1型半功能的，剩余的私鑰是正常的。

Trace,2：與Trace0類似，除了前次詢問的私鑰是2型半功能的，剩余的私鑰是正常的。

Trace,2：在這個可追蹤性游戲中，所有詢問私鑰都是2型半功能的，且挑戰者S生成半功能密文發送給盜版解碼器。

定理1 如果所有串謀者C的碼字中cw′, j′= 0，那么成功解密一個(′,′)位置被篡改的密文的優勢為0，有

其中，S1是一個依賴于攻擊者A的概率多項式時間算法。

算法S1接收到DDH假設的輸入(1,1,)，令′=élb2ù(′?1) + (?1)。S隨機選擇,?Z，對每個屬性?，隨機選擇s?Z。此外，對= 0, 1, ···,且≠時，隨機選擇θ?Z，計算e=, f=；當=時，令e=1,f=^。S1選擇秘密隨機置換和用于聯合安全編碼的秘密值?{0,1}l，將每個用戶的映射到各自的碼字，生成系統公鑰和主密鑰為

當A提交身份和屬性集合時，S1隨機選擇,'?Z，0,0',0"?2, p3, 對每一個屬性?，隨機選擇R?2,p3, 令對應的碼字為，計算用戶私鑰SK, ω為

注意：由條件cw= 0，可知()與f無關，所以S1在不知道f的情況下仍然可以計算該用戶的私鑰。然后，攻擊者A構造出一個針對挑戰訪問結構(,)的盜版解密設備。

S1產生一個隨機消息，隨機選擇2′, …,v2′Z，組成隨機向量′= (1,2′, …,v2′)，對訪問矩陣的每個行向量，隨機選擇, 計算密文如下

如果=1，那么該密文是正確生成的隨機密文，此時，正確解密密文的概率為()。如果是隨機的，該密文是4中的第′位被篡改的密文，那么正確解密篡改密文的概率為()?。所以算法S1以

的優勢解決1,p1中的DDH假設。

引理1 當所有串謀者C的碼字中cw, j'=1時，如果存在一個概率多項式時間攻擊者A使TraceRealAdvA– Trace0AdvA=，那么可以構造一個概率多項式時間挑戰者S，以的優勢攻破假設1。

證明 挑戰者S接收到假設1的條件{1,3,}，能夠模擬TraceReal或Trace0。S隨機選擇,?Z，對每個屬性?，隨機選擇s?Z。此外，對= 0, 1, ···,, 隨機選擇θ?Z，計算1=(1), 向量= ()=0,1,···,,向量=()=0,1,···,,選擇秘密隨機置換和用于聯合安全編碼的秘密值?{0,1}l，將每個用戶的映射到各自的碼字，生成系統公鑰和主密鑰為

當A詢問私鑰時，S利用和密鑰生成算法給A頒發正規私鑰。然后，攻擊者A構造出一個針對挑戰訪問結構(,)的盜版解密設備。

S產生一個隨機消息，隨機選擇2′, …,v2′Z，組成隨機向量′= (1,2′, …,v2′)，對訪問矩陣的每個行向量，隨機選擇r′Z, 利用挑戰訪問結構(A,)計算第位被篡改的密文如下。

其中，上述密文隱式的設置=(,2, ···,),r=sr,是隨機向量，其第一個分量為，且r是隨機值。當?2,1時，，該密文是第′位被篡改的正規密文。當?2,12時，令=, 此時，該密文是半功能密文，其中，=，γ=?cr，z(x)=s(x),,δ=θ。盡管半功能密文中重復使用了2,1部分的值，但是，由中國剩余定理可知，, r',2', ···,, s(x),θmod1與, r',2', ···,, s(x),θmod2是無關的，上述密文是第′位被篡改的半功能密文。因此，S可以根據A的輸出，以優勢攻破假設1。

引理2 當所有串謀者C的碼字中cw', j'=1時，如果存在一個概率多項式時間攻擊者A使Trace1,2AdvA–Trace,1AdvA=，那么可以構造一個概率多項式時間挑戰者S，以幾乎為的優勢攻破假設2。

證明 挑戰者S接收到假設2的條件{1,12,3,23,}，能夠模擬Trace?1,2或Trace,1。S隨機選擇,?Z，對每個屬性?，隨機選擇s?Z。此外，對= 0, 1, ···,, 隨機選擇θ?Z，計算1=(1), 向量= ()=0,1,···,,向量=()=0,1,···,，選擇秘密隨機置換和用于聯合安全編碼的秘密值?{0,1}l，將每個用戶的映射到各自的碼字，生成系統公鑰和主密鑰為

下面將A的私鑰詢問分為以下3種情況：1)當A詢問私鑰次數大于時，S利用和私鑰生成算法給A頒發相應正規私鑰；2)當A詢問私鑰次數小于時，S隨機選擇,'?Z,0,0',0'',R?2, p3，計算2型半功能私鑰為

其中，2,3和1的值是不相關的，因此，該私鑰是一個均勻分布的2型半功能私鑰；3)當A進行第次私鑰詢問時，令的G1部分為1，S隨機選擇'?Z,0,0',0'',R?2, p3，計算

S產生一個隨機消息，隱式地設置1=，2=，隨機選擇r',2,…, u2?Z, 生成向量'=(1,2,…, u2), 用挑戰訪問結構(,)對消息進行加密，計算第′位被篡改的密文

其中，上述密文隱式地設置=?1,=, 因此，是1,1部分被分享的值，是1,2部分被分享的值，且r=sr',γ= ?cr'，z(x)=s(x),此時，當第個私鑰是1型半功能時，z(x)在半功能密文和密鑰中是一致的，δ=θ。

當第個私鑰是1型半功能時，1與mod2相關，密文中的第一個分量為，?1=–= 0 mod2，此時該1型半功能私鑰是名義半功能私鑰。因此，第個私鑰可能是名義半功能的或正規的。

為了證明挑戰密文1,2中被分享的值1=在信息理論上是隱藏的，需要限制訪問結構(,)中每個屬性在中至多出現一次。因為第個私鑰無法解密挑戰密文，所以中()的所有行生成的行空間不包含1。因此，存在一個向量使正交于，但不正交于1，即1?≠0。固定一個包含的基，則存在, 使=+'' mod2，其中，''屬于除外的基向量擴張的空間中，注意到''是均勻分布的，且無法揭露的任何信息。由于·1=?1?+1?''，且1?≠0，所以''·1與相關。

由于僅出現在+γz(x)中，當()時，=A?(?+'')=?u''，與無關。當()時，若γ≠0 mod2，每項''+γz(x)都引入一個新的未知量z(x)，且z(x)不出現在其他項中，因此，A無法從這些項中得知的任何信息。準確的說，無論的第一個分量為何值，上述方程都有相同個數的解，因此，當所有的γmod2都不為0時，在A看來，挑戰密文和第個私鑰以幾乎為1的概率均勻分布。

引理3 當所有串謀者C的碼字中cw', j'= 1時，如果存在一個概率多項式時間攻擊者A使Trace,1AdvA–Trace,2AdvA=，那么可以構造一個概率多項式時間挑戰者S，以幾乎為優勢攻破假設2。

證明 挑戰者S接收到假設2的條件{1,12,3,23,}，能夠模擬Trace,1或Trace,2。S隨機選擇,?Z，對每個屬性?，隨機選擇s?Z。此外，對= 0, 1, …,, 隨機選擇θ?Z，計算1=(1), 向量= ()=0,1,···,,向量= ()=0,1,···,, 選擇秘密隨機置換和用于聯合安全編碼的秘密值?{0,1}l，將每個用戶的映射到各自的碼字，生成系統公鑰和主密鑰為

下面將A的私鑰詢問分為以下3種情況。1)當A詢問私鑰次數大于時，S利用和私鑰生成算法給A頒發相應的正規私鑰。2)當A詢問私鑰次數小于時，2型半功能私鑰與引理2的構造方法相同。3) 當A進行第次私鑰詢問時，與引理2的構造方式類似，但需要增加一個隨機值?，計算

唯一不同的是，1中增加了一項(23)，該項重新隨機化了1的2,2部分。然后，攻擊者A構造出一個針對挑戰訪問結構(,)的盜版解密設備。第′位被篡改的密文的構造方式與引理2相同，注意此時，第次私鑰不再是名義半功能的。如果用第次私鑰解密挑戰密文，?1≠ 0，解密將會失敗。

引理4 當所有串謀者C的碼字中cw, j'= 1時，如果存在一個概率多項式時間攻擊者A使Trace,2AdvA=，那么可以構造一個概率多項式時間算法S，以的優勢攻破假設4。

證明 挑戰者S接收到假設4的條件{1,,3,,2}，能夠攻破Trace,2。S隨機選擇?Z，計算，對每個屬性?，隨機選擇s?Z，計算。此外，對= 0, 1,···,, 隨機選擇θ?Z，計算1=(1)，向量= ()=0,1,···,,向量= ()=0,1,···,, 選擇秘密隨機置換和用于聯合安全編碼的秘密值?{0,1}l，將每個用戶的映射到各自的碼字，生成系統公鑰

為了生成2型半功能私鑰，S隨機選擇,'?Z,0,0',0'',R?2, p3，計算

然后，攻擊者A構造出一個針對挑戰訪問結構(,)的盜版解密設備。

S產生一個隨機消息，隱式的設置指數來自于項，隨機選擇值r',2,…, u2?Z, 生成向量'=(,2,…, u2),用挑戰訪問結構(,)對消息進行加密，計算第′位被篡改的密文

其中，上述密文隱式設置=?1',='，因此，是1,1部分被分享的值，是1,2部分被分享的值，且r=sr',γ=?cr'，z(x)=s(x), δ=θ。

如果盜版解密設備成功解密上述密文的概率為2，則算法S可以以相同的概率計算出=(1,1)作為假設4的解，所以1≤Adv4G,A()是可以忽略的。

定理2 如果所有串謀者C的碼字中cw', j'= 1，那么成功解密一個(',')位置被篡改密文的優勢2是可忽略的。

證明 如果假設1、2、4、5成立，根據引理1~引理4可知，追蹤性游戲TraceReal和Trace,2是不可區分的，由于在Trace,2中攻擊者A成功解密一個(,)位置被篡改密文的優勢是可忽略的，所以，在TraceReal中成功解密一個(,)位置被篡改密文的優勢2是可忽略的。

定理3 本文適應性安全的ABTT方案滿足-TT-CPA可追蹤性，如果下面3個條件同時成立：1)本文方案采用的編碼是字母表長度為、字符串長度為的(,,)聯合安全編碼；2)假設在1,1上成立；3)假設1~假設4在2上成立。即任意概率多項式時間的攻擊者A生成一個不可追蹤的盜版解密設備的優勢。≤élbù(2e?λ)。其中，至多利用個串謀者的私鑰以()的概率成功解密密文，且

證明 假定A是本方案可追蹤性的攻擊算法，輸入系統公鑰，輸出一個盜版解密設備。利用A構造針對聯合安全編碼的攻擊算法A′，輸入個隨機代碼字= {1,…,cw}，輸出一個字符串。下面證明，如果A能夠以不可忽略的概率避免被追蹤，那么A′能以不可忽略的概率輸出一個不能被追蹤的代碼字。

A′隨機選擇1,…,i?{1,…,N}，設置串謀集合C= {1,…,i}，輸入對應的碼字

= {,=1, 2,…,}

A′運行本方案的初始化算法，生成系統公鑰

A至多進行次私鑰生成詢問，設A第次進行私鑰詢問時的輸入為(,)，A′用為其生成相應的私鑰。因為包含隨機串謀集C的代碼字，因此是一個隨機置換，所以，A′返回給A的私鑰是均勻分布的。然后，A構造出一個針對挑戰訪問結構(,)的盜版解密設備。A′運行本方案的追蹤算法，輸出字符串，根據定理1、定理2和文獻[8]中的Chernoff界，可知追蹤算法輸出的字符串不屬于可行集()的概率，至多為Pr[?()]≤élbù(2e)。由(,,)聯合安全編碼的性質可知，定理3成立。

5.3 仿真實驗的結果分析

為了驗證本方案能夠適應性追蹤叛徒，基于雙線性對程序庫PBCL，通過適當修改libfenc程序庫[13]中密文策略ABE的部分代碼，實現了本方案，并對其進行仿真實驗。假定系統安全參數=159，最多串謀叛徒個數=2，用戶總數為1 024，追蹤算法出錯概率為10?6，則可以將聯合安全碼字長度取值為60位。一個具體的聯合安全編碼的構建是比較復雜的，由于篇幅有限，下面簡單介紹聯合安全編碼工作原理，重點介紹本文叛徒追蹤算法的實驗結果。在本文方案中，有1 024個碼字1,2, …,1024，并將其分配給所有用戶。利用這些碼字，任何2個用戶均可定義一個可行集合，分別記為FS1,2, FS1,3, …, FS1 023,1 024，此處FS,j表示由碼字w和w定義的可行集合。令該實驗中，2個串謀用戶的碼字為1和2，他們的可行集合為FS1,2。根據本文叛徒追蹤算法，對碼字二進制串的每位運行404 496次測試，經過大量實驗可得如下結果：1) 當所有叛徒位串的第(,)位cw,j都是1時，從1中隨機選擇一個元素代替密文4中的第(élbù(?1)+)個元素，此時解密成功的次數ctr為0次或1次，遠遠小于4=636次，由追蹤算法可知，其重構位的值是1；2) 當所有叛徒位串的第(,)位cw,j都是0時，從1中隨機選擇一個元素代替密文4中的第(élbù(?1)+)個元素，此時解密成功的次數ctr為2 543次，遠遠大于636次，由追蹤算法可知，其重構位的值是0；3) 當所有叛徒位串的第(,)位cw,j不相同時，修改密文中相應位置的元素為隨機值時，解密成功的次數將在0~2 544次隨機取值，由追蹤算法可知，該位可能被重構為0或1，但這些位不影響叛徒碼字的可行集合。由上述3種情況可以構造出叛徒碼字的可行集FS12，利用聯合安全編碼的追蹤算法，可追蹤到叛徒的一組身份。總之，本文的追蹤算法能夠成功追查叛徒。

5.4 性能比較

表1列出本文ABTT方案和相關方案在效率和追蹤性方面的詳細比較，其中，1表示密文中訪問矩陣的行數，||表示集合中屬性的個數，||表示解密鑰中滿足訪問策略的屬性個數，N表示系統中用戶的最大數目，表示聯合安全編碼中一個碼字的二進制位數。

表1 本文ABTT方案與相關方案的性能比較

與文獻[11]的LOS方案相比，雖然密文長度增加了個群中的元素，但本方案實現了適應性叛徒追蹤的功能。與文獻[10]的LCW方案相比，盡管本方案只能容忍指定個數叛徒構造盜版解碼器，但是實現了指定策略盜版解密器的適應性追蹤。

6 結束語

為了增加可追蹤叛徒的基于屬性加密機制的安全性，本文修改了適應性安全的密文策略ABE方案[11]，將叛徒追蹤機制和聯合安全編碼引入到該方案中，給出了適應性安全的ABTT的定義、安全模型和追蹤模型，提出了一個適應性安全的ABTT方案。基于合數階群上的靜態假設和DDH假設，證明本方案是適應性安全和適應性可追蹤的。因此，該方案不僅可以適應性追查指定策略盜版解碼器中的叛徒，而且進一步增強了ABE系統的安全性，具有一定的理論和實用價值。

[1] SAHAI A, WATERS B. Fuzzy identity based encryption[C]//The EUROCRYPT. Aarhus, Denmark, c2005: 457-473.

[2] GOYAL V, PANDEY O, SAHAI A, et al. Attribute-based encryption for fine-grained access control of encrypted data[C]//The 13th ACM Conference on Computer and Communication Security. Alexandria, Virginia, USA, c2006: 89-98.

[3] HINEK M J, JIANG S, SAFAVI-NAINI R, et al. Attribute-based encryption with key cloning protection[EB/OL]. http://eprint.iacr.org/ 2008/478.pdf.

[4] 馬海英, 曾國蓀. 可追蹤并撤銷叛徒的屬性基加密方案[J]. 計算機學報, 2012, 35(9):1845-1855.

MA H Y, ZENG G S. An attribute-based encryption scheme for traitor tracing and revocation together[J]. Chinese Journal of Computers, 2012, 35(9):1845-1855.

[5] WANG Y T, CHEN K F, CHEN J H. Attribute-based traitor tracing[J]. Journal of Information Science and Engineering, 2011, 27(1):181-195.

[6] LI J, REN K, KIM K. A2BE: accountable attribute-based encryption for abuse free access control[EB/OL]. http://eprint.iacr.org/2009/ 118.pdf.

[7] YU S C, REN K, LOU W J, et al. Defending against key abuse attacks in KP-ABE enabled broadcast system[C]//The Security and Privacy in Communication Networks. Athens, Greece, c2009: 311-329.

[8] BONEH D, SHAW J. Collusion-secure fingerprinting for digital data[C]//The CRYPTO’95. Santa Barbara, California, USA, c1995: 452-465.

[9] ABDALLA M, DENT A W, MALONE-LEE J, et al. Identity-based traitor tracing[C]//The public Key Cryptography. Beijing, China, c2007: 298-314.

[10] LIU Z, CAO Z, WONG D S. Blackbox traceable CP-ABE: how to catch people leaking their keys by selling decryption devices on eBay[C]//The 20th Conference on Computer and Communication Security. Berlin, Germany, c2013: 475-486.

[11] LEWKO A, OKAMOTO T, SAHAI A, et al. Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption[C]//The EUROCRYPT. c2010: 62-91.

[12] WATERS B. Dual system encryption: realizing fully secure ibe and hibe under simple assumptions[C]//TheCRYPTO’09. Santa Barbara, California, USA, c2009:619-636.

[13] GREEN M, AKINYELE A, RUSHANAN M. Libfenc: The Functional Encryption Library[EB/OL]. http://code.google.com/p/libfenc.

Adaptively secure attribute-based encryption for traitor tracing

MA Hai-ying1, ZENG Guo-sun2, CHEN Jian-ping1, WANG Jin-hua3, WANG Zhan-jun3

(1. College of Computer Science and Technology, Nantong University, Nantong 226019, China; 2. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China; 3. School of Science, Nantong University, Nantong 226007, China)

For the key abuse problem in attribute-based encryption (ABE), each user was identified by his unique identity, and the collusion secure codes and the traitor tracing mechanism were introduced to the ABE scheme. The definition, security model and tracing model for adaptively secure attribute-based encryption for traitor tracing (ABTT)were formalized, and an adaptively secure ABTT scheme was proposed, which may trace traitors in policy-specific pirate decorders. Under these subgroup decision assumptions in composite order groups and the DDH assumption, adaptively secure and can adaptively trace traitors were proved. Therefore, the scheme not only was capable of tracing adaptively traitors in policy-specific pirate decorders, but also further strengthens the security of ABE system, which has theoretical and practical values.

attribute-based encryption, traitor tracing, dual system encryption, adaptive security, collusion secure code

TP309

A

10.11959/j.issn.1000-436x.2016009

2014-12-20；

2015-03-19

國家自然科學基金資助項目(No.61402244, No.61272424, No.61202006, No.61272107, No.61202173, No.61103068)；NSFC-微軟亞洲研究院聯合基金資助項目(No.60970155)；上海市優秀學科帶頭人計劃基金資助項目(No.10XD1404400)；教育部博士點基金資助項目(No.20090072110035)；上海自然科學基金資助項目(No.13ZR1443100)；南通大學校級自然科學基金資助項目(No.15Z06)

The National Natural Science Foundation of China (No.61402244, No.61272424, No.61202006, No.61272107, No.61202173, No.61103068), The Joint of NSFC and Microsoft Asia Research (No.60970155), The Program of Shanghai Subject Chief Scientist(No.10XD1404400), The Ph.D Programs Foundation of Ministry of Education China(No.20090072110035), ShanghaiNaturalScienceFoundationProgram(No.13ZR1443100), TheNatural Science Foundation of Nan tong University(No.15Z06)

馬海英（1977-），女，河南衛輝人，博士，南通大學副教授，主要研究方向為公鑰密碼學和網絡安全。

曾國蓀（1964-），男，江西吉安人，同濟大學教授、博士生導師，主要研究方向為網格計算、可信軟件。

陳建平（1960-），男，江蘇南通人，南通大學教授、碩士生導師，主要研究方向為信息安全、數值計算等。

王金華（1963-），男，江蘇南通人，博士，南通大學教授、博士生導師，主要研究方向為信息安全、組合數學等。

王占君（1978-），男，河南鶴壁人，南通大學講師，主要研究方向為公鑰密碼學和Hopf代數。