基于身份的具有否认认证的关键字可搜索加密方案

曹素珍 丁宾宾* 丁晓晖 窦凤鸽 王彩芬

①(西北师范大学 兰州 730000)

②(深圳技术大学 深圳 518118)

1 引言

云存储技术[1]的发展实现了资源共享，帮助用户降低了存储成本。考虑到云端数据的敏感性，数据需要被加密后存放在云端，传统数据加密技术[2]虽有效地保护了数据的隐私，但同时又带来了对云端密文数据检索的难题。可搜索加密技术[3]在保护用户的隐私的同时又支持密文检索，在云存储中得到了广泛的应用。

2004年，Boneh 等人[4]提出了第1个公钥可搜索加密方案(Public key Encryption with Keyword Search, PEKS)，该方案既支持密文检索又实现了数据共享，但搜索效率低，安全性较差。2006年，Byun等人[5]指出PEKS方案存在离线关键字猜测攻击(Keyword Guessing Attack, KGA)[6]的风险。传统的公钥可搜索加密方案需要证书颁发机构发布和管理用户的证书，基于身份密码体制[7]下的公钥可搜索加密方案解决了复杂的证书管理问题。2014年，Wu等人[8]在身份密码体制下提出了指定测试者的可搜索加密方案，该方案具有密文和陷门不可区分性，由于该方案并未完全定义在身份密码系统架构上，不能完全满足密文不可区分性。王少辉等人[9]在Wu等人方案基础上设计了一个具有更高效率可搜索加密方案，证明了密文不可区分性是抵御离线关键字猜测攻击的充分条件，故Wu等人方案也存在离线关键字猜测攻击的风险。2017年，Huang等人[10]提出了具有公钥认证的可搜索加密方案，通过对关键字认证和加密，以抵御内部离线关键字猜测攻击。但该方案存在一个缺点，若云服务器被外部攻击者攻破，用户的搜索隐私将被泄露。

为了保护用户的搜索隐私，Baek等人[11]提出在拥有陷门而没有接收者私钥的情况下，一个指定测试者无法完成云端密文数据的检索，但该方案无法抵御离线关键字猜测攻击。为了提高离线关键字猜测攻击下的安全性。2019年， Li等人[12]提出了指定服务器的基于身份认证的关键字可搜索加密方案，Lu等人[13]借鉴签密思想，实现了在关键字加密过程中，敌手不能试图通过产生合法关键字密文以达到匹配陷门的目的。普遍存在的缺陷是上述方案均没有考虑到对发送者身份隐私保护的问题。

如今，个人信息和隐私趋于透明化。在电子投票、医疗信息、电子邮件、行政和司法报告等应用环境中，如何保护发送者的身份隐私，使其能够否认发送消息的行为已成为研究热点。否认认证协议由Dwork等人[14]首次提出，该协议基于零知识证明来定义，接收者可以确认消息发送者的身份，但无法向第三方证明这一事实。 Li等人[15]在身份密码体制下提出了具有更高效率的否认认证加密方案，并在电子邮件系统中得到了很好的应用。 Wu等人[16]在身份密码体制下提出了同时具有认证性和否认性的否认认证加密方案。

在基于身份的密码体制下，本文提出了具有否认属性的关键字可搜索加密方案，将否认认证与关键字可搜索加密技术相结合，在随机预言模型下，基于双线性Diffie-Hellman(Bilinear Diffie-Hellman,BDH)和决策双线性Diffie-Hellman(Decisional Bilinear Diffie-Hellman, DBDH)数学困难问题，证明了方案满足不可伪造性、密文和陷门不可区分性，同时具有否认性，即第三方无法确认消息的真实发送者，从而保护了发送者的身份隐私。

2 IDAPKSE安全模型

2.1 IDAPKSE系统模型

基于身份的具有否认认证的关键字可搜索加密方案(Identity-based Public Key keyword Searchable Encryption scheme with Denial Authentication, IDAPKSE)中有密钥分发中心、发送者、接收者和云服务器4类实体，系统模型图如图1所示。

图1 系统模型图

(1) 密钥分发中心(Key Generation Center,KGC)：KGC生成系统参数params和主密钥s，并为发送者、接收者和云服务器提供私钥SKi。

(2) 发送者(Data Sender, DS)：D S对明文和所选关键字加密，将密文上传到云服务器。

(3) 接收者(Data Receiver, DR)：D R运行陷门生成算法，将生成的陷门上传到云服务器。

(4) 云服务器(Cloud Server, CS)：存储发送者上传的密文数据，并通过接收者上传的陷门，进行密文检索。

2.2 IDAPKSE形式化定义

IDAPKSE包括以下算法：

(1) Setup(k)：KGC 输入安全参数k，返回系统参数params和主密钥s。

(2) 密钥提取算法：(a)发送者和接收者密钥提取：KGC 输入主密钥s和身份标识I Di，返回公私钥对(PKi,SKi)；(b)云服务器密钥提取：KGC 输入系统参数params，返回云服务器的公私钥对(PKC,SKC)。

(3) 关键字否认认证加密算法：发送者输入参数params、关键字w、发送者身份I DS和私钥SKS、云服务器的公钥PKC、接收者的身份IDR和公钥PKR，返回密文C并上传到云服务器。

(4) 陷门生成算法：接收者输入系统参数params、关键字w、发送者身份I DS和接收者身份IDR，输出陷门Tw。

(5) 测试算法：云服务器输入系统参数params、服务器私钥SKC和陷门Tw，输出φ。若接收者上传的陷门与发送者上传的关键字密文中包含相同的关键字，则φ=1，否则φ=0。

2.3 IDAPKSE安全模型

IDAPKSE方案的安全性主要考虑为不可伪造性、密文和陷门的不可区分性、否认性。下面通过挑战者β和敌手αi(i=1,2,3,4)之间的游戏给出方案的安全模型。

游戏 1 不可伪造性。

(1) Setup(k)：β输入安全参数k，返回系统参数params给α1，自身保留主密钥s，运行密钥提取算法，返回云服务器公私钥对(PKC,SKC)。

(2) 私钥询问阶段：α1对目标身份外的用户进行私钥询问，β运行密钥提取算法返回私钥给α1。

(3) 关键字否认认证加密询问阶段：α1向β提交发送者身份IDS、接收者身份IDR和关键字w。β运行密钥提取算法得到发送者的私钥SKS，运行关键字否认认证加密算法，返回密文C给α1。

(4) 陷门询问阶段：α1可以对挑战关键字外的任意关键字进行陷门询问。β通过α1选取的关键字w，运行陷门生成算法生成陷门Tw，返回给α1。

游戏 3 陷门不可区分性。

(1) Setup(k)：私钥询问阶段、关键字否认认证加密询问阶段和陷门询问阶段同游戏1。

(2) 挑战阶段：α3向β提交发送者的身份I DS和接收者的身份IDR、挑战关键字(w0∗, w1∗)。β随机选择b ∈{0,1}，生成wb的陷门Tw∗返回给α3。

游戏 4 否认性。

(1) Setup(k)：假设β能够为系统中的任何诚实用户生成IDAPKSE方案下的合法密文，选择两个诚实的用户D0和D1。

(2) 挑战阶段：α4向β提交明文消息M，β随机选择b ∈{0,1}，并与Db交互，使Db能够将M生成IDAPKSE方案下的合法密文C∗返回给α4。

(3) 区分阶段：α4输出b′∈{0,1}，若b′=b，则α4在游戏4中获胜。

因游戏中D0和D1生成的密文的概率分布是相同的，所以对于区分者是不可区分的。

α4赢得游戏4的优势为

3 IDAPKSE方案

3.1 具体方案

(1) Setup(k)：输入安全参数k，KGC执行以下操作：(a)选择q阶循环群G1和G2，g为G1的生成元，再选择双线性映射e:G1×G1→G2；(b)在G1群中选择生成元U和h，KGC随机选择s ∈Zq∗作为主密钥，并计算公钥Ppub=sU；(c)定义3个抗碰撞的哈希函数：H1:{0,1}∗→G1；H2:G2×{0,1}∗→G1；H3:{0,1}∗→Zq∗。KGC保留主密钥s，公开系统参数params={k, q, G1, G2, U, h, g ,Ppub, H1, H2, H3}。

(2) 密钥提取算法：(a)发送者和接收者密钥提取：发送者和接收者将身份 IDi发送给KGC，KGC计算对应公钥Qi=H1(IDi)和私钥SKi=sQi，并通过安全信道将私钥返回给发送者和接收者；(b)云服务器密钥提取：KGC随机选择t ∈Zq∗作为云服务器私钥；输入t和系统参数params，计算云服务器公钥PKC=tg。

(3) 关键字否认认证加密算法：发送者输入系统参数params、关键字w、发送者身份I DS和公私钥对(PKS,SKS)、接收者身份IDR和公钥PKR、云服务器公钥PKC，按以下步骤加密关键字：

(a)计算：QS=H1(IDs),QR=H1(IDR),T=rQS，其中r ∈Zq∗；

3.2 IDAPKSE方案正确性分析

IDAPKSE方案的正确性当且仅当验证等式C1·e(SKCT1, C3)=e(SKCT2, C2)是否成立

4 安全性分析

4.1 不可伪造性

引理1 在随机预言模型下，若敌手α1在时间t内赢得游戏1，则存在算法C 可以解决BDH问题。

证明 挑战者β输入1个随机的BDH问题实例(P , aP , bP , cP)，目标计算e(P , P)abc。

(1) Setup(k)：β输入安全参数k，返回系统参数params给α1。设置公钥Ppub=cP，c为主密钥。

(2) 攻击阶段：β维护L1,L2,L3列表，将其初始化为空，分别作为α1对随机预言机H1,H2,H3的查询追踪，α1执行多项式有界次查询：

(a)公钥询问：α1向β提交任意用户身份IDi，β检查L1。

若未对IDi进行任何询问，IDi为⊥，β得到(IDi,ni)，随机选择xi ∈Zq∗作为私钥SKi，计算公钥PKi=xiP，返回PKi给α1并向列表L1中添加一个新的元组(IDi,PKi,SKi, ni)。

若IDi不为⊥，L1列表中存在相应的元组，则返回存在的结果。

(b)私钥询问：α1提交用户身份I Di，获取相应的用户私钥，若IDi=IDS或IDi=IDR，结束模拟。否则，β检查列表L1。

若未对IDi进行任何询问，IDi为⊥，β得到(IDi, ni)，随机选择xi ∈Zq∗作为私钥SKi，计算公钥PKi=xi P，返回SKi给α1，并向列表L1中添加一个新的元组(IDi,PKi,SKi, ni)。

若IDi不为⊥，L1列表中存在相应的元组，则返回存在的结果。

(c)关键字否认认证加密询问：α1向β提交选定的发送者身份 IDS和接收者身份IDR及关键字w,β执行以下操作：

若α1提交的IDi与β选择的两个身份不同，即IDi ̸=IDS和IDi ̸=IDR。β运行密钥提取算法得到发送者私钥SKS，运行关键字否认认证加密算法生成密文C返回给α1。

若α1提交发送者身份I Di是β选择的两个身份之一，即IDi=IDS或IDi=IDR，但接收者身份IDj ̸=IDS且IDj ̸= IDR。β不能计算发送者的私钥，但能计算接收者的私钥SKj=njPpub。β随机选择r ∈Zq∗，进行以下计算：

(a)计算：T=rQi,C1=e(H2(e(T,SKj), w),PKC)r；

(b)计算：C2=rg,C3=rh；

(c)计算：Y=H3(w||IDi||IDj, T)；

(d)计算：V=e(T+Y Qi),SKj)；

(e)C=(T, C1, C2, C3, V)，返回密文C给α1。

若α1提交发送者身份与β选中身份相同，即IDi=IDS且IDj= IDR或IDj=IDS且IDi=IDR。这时，β不能够计算发送者和接收者的私钥，β随机选择r,h ∈Zq∗，进行以下计算：

(a)计算：T=rP-hQi,Y=H3(w||IDR||IDS,T)，向列表L3中添加元组(w||IDR||IDS, T, h)；

(b)计算：C1=e(H2(e(SKS,QR),w),PKC)r，向列表L2中添加元组(PKS,PKR,C1,V)，其中V=e((r+Y)SKS, QR)；

目前没有公认的解决BDH困难问题的有效算法，因此α1不存在，方案满足密文的不可伪造性。证毕

4.2 密文不可区分性

引理2 在随机预言模型下，若敌手α2在时间t内赢得游戏2，则有算法C 可以解决DBDH问题。

证明 挑战者β输入一个随机的DBDH问题实例(G1, G2, e, q,g, xg, yg, zg, Z)，目标是解决DBDH问题。

(1) Setup(k)：β输入安全参数k，返回params={k, q, G1, G2, e, P, h, g ,Ppub}， 其中Ppub=ZP，Z为主密钥。计算云服务器公私钥对PKC=tg和SKC=t，将params和云服务器公私钥对(PKC,SKC)返回给α2。

(2) 攻击阶段：β维护L1,L2,L3列表，将其初始化为空，分别作为α2对随机预言机H1,H2,H3的查询追踪，α2执行多项式有界次查询：

(a)公钥询问，私钥询问和关键字否认认证加密询问同上文不可伪造性证明。

(b)陷门询问阶段：α2向β提交选择的发送者身份IDS、接收者身份IDR和关键字w，β执行以下操作：

若α2提交的发送者的身份与β选取的身份相同，即IDi=IDS且IDj= IDR或IDi=IDR且IDj=IDS，计算T1=ag,T2=H2(Z, w)+ah，返回陷门Tw=(T1, T2)给α2。

(4)α2继续执行上询问。

(5) 猜测阶段：α2输出b′∈{0,1}，若b′=b，输出1，否则输出0。

F表示对挑战身份的猜测是不正确的，挑战者β将中止。

若β中止，则β随机输出b的概率为1 /2。当β随机猜测时，F不发生的概率是1/(qH(qH-1))，即Pr(F) =1/(qH(qH-1))，qH为α2最多询问次数。

若β不被中止，α2最多赢得游戏2的概率1 /2，故β解决DBDH困难问题的优势为

4.3 陷门不可区分性

引理3 若DBDH假设为真，则本文方案满足陷门不可区分性。

4.4 否认性

5 分析和比较

5.1 安全功能分析

公开发表的文献显示，目前还没有基于身份的具有否认认证的关键字可搜索的加密方案。因此，本文的方案不能与同类方案进行比较。本文方案将在关键字加密、陷门生成和关键字密文检索3个方面与文献[8,10,12]的方案进行比较，表1为各方案功能对比。

表1 各方案功能对比

从表1可以看出本文方案和文献[8,12]的方案都是在基于身份密码体制下构建且指定测试者，文献[10,12]的方案和本文方案能够抵御内部和外部关键字猜测攻击，文献[8]的方案能够抵御外部关键字猜测攻击，但不能抵御内部关键字猜测攻击。

5.2 计算量分析

表2为各方案计算量对比， P为双线性对运算，E 为指数运算， M 为点乘运算， H为哈希运算。表3为基本运算所消耗的时间，在关键字加密阶段，本文方案有3个双线性对运算，文献[8,12]分别存在1, 2个双线性对运算，文献[10]没有对运算，计算量由大到小依次为：文献[12]、本文方案、文献[10]、文献[8]；在陷门生成阶段，本文方案与文献[10,12]都存在1个对运算，文献[8]没有对运算，计算量由大到小依次为：文献[12]、文献[10]、本文方案、文献[8]；在关键字密文检索阶段，各个方案都存在2个对运算，文献[8]多出1个哈希运算，文献[12]多出2个指数运算，计算量由大到小依次为：文献[12]、文献[8]、本文方案、文献[10]。综合以上分析，本文方案在关键字加密和生成陷门阶段，计算效率偏低，计算性能上并未占据优势。在关键字密文检索阶段，本文方案与文献[10]的计算效率相似，与文献[8,12]相比，具有更佳的计算性能表现。

表2 计算量对比

5.3 时间性能分析

本节通过仿真实验将本文方案与文献[8,10,12]的方案在关键字加密、陷门生成和关键字密文检索3个方面进行了对比，加密函数由PBC[18]提供，实验选取关键字Lenovo笔记本(AMD Ryzen 5 4600U with Radeon Graphics @2.10 Hz，16 GB内存和Linux实验选取关键字分别为：1, 50, 100, 300,500, 700, 900, 1000，实验结果如图2所示。从图2可以看出在关键字加密阶段，随着关键字数量的增加，关键字加密的时间也在增加，在关键字数量相同的情况下，本文方案在加密阶段加密时间小于文献 [12]，本文方案比文献[8]多出2个对运算，加密时间比文献[8]要长。在陷门生成阶段，本文方案与文献[10,12]均有1个对运算，但文献[12]存在2个指数运算，文献[10]存在1个指数运算，本文方案相较于文献[10,12]，优势在于在该阶段没有指数运算，生成陷门的时间相对较短，文献[8]在该阶段不存在对运算和指数运算，生成陷门时间比本文方案要短。在关键字密文检索阶段，各方案均有2个对运算，文献[12]多出了2个指数运算，运算时间相对于其他方案较长，本文方案在关键字密文检索阶段比文献[8,10]多出了2个点乘运算时间，文献[8]比本文方案和文献[10]多出1个哈希运算。由表3可以看出，点乘耗费时间最短，检索关键字密文所耗费的时间本文方案接近于文献[10]。本文方案在各个阶段的计算所消耗的时间相较于其他3种方案有长有短，但本文最大的优势在于实现了否认属性，对发送者的隐私有了很好的保护，在电子邮件、医疗信息等方面有着较好的应用前景。

表3 不同操作的基本运算耗费时间(ms)

图2 算法运行时间比较

6 结束语

本文方案将关键字可搜索加密与否认认证加密相结合，基于BDH和DBDH困难问题证明了方案满足不可伪造性、密文和陷门的不可区分性。本文方案中的否认属性，在保护发送者身份隐私上具有较高的实用性。不足的是本文方案基于身份密码体制构建，基于身份的密码体制虽解决了PKI中的证书管理问题，但也存在密钥托管和密钥撤销的缺陷，未来我们将否认认证加密迁移到无证书密码体制下，利用无证书优势解决密钥托管问题。