基于身份的无对密文等值测试公钥加密方案*

丁宾宾,曹素珍,丁晓晖,窦凤鸽,马佳佳

(西北师范大学计算机科学与工程学院，甘肃 兰州 730070)

1 引言

云存储技术[1]的普及帮助用户降低了存储成本,同时打破了地理位置和时间的限制，实现了用户之间的数据共享。考虑到数据的敏感性，数据需要被加密后存储在云端，传统的数据加密技术[2]虽有效地保护了用户隐私，但加密操作会破坏数据的自然结构，使得云服务器检索密文数据变得困难。

2004年，Boneh等人[3]首次提出了带关键字检索的公钥可搜索加密PEKS(Public key Encryption with Key word Search)方案，该方案允许用户提供关键字陷门去查找云端包含特定关键字的密文。基于公钥基础设施PKI(Public Key Infrastructure)的可搜索加密方案，需要证书颁发机构发布和管理用户证书，当用户量较大时存在复杂的证书管理问题。基于身份密码体制[4]的公钥可搜索加密方案虽有效地解决了证书管理问题，但同时又带来了密钥托管的难题。2014年，Peng等人[5]提出了基于无证书密码体制的公钥可搜索加密方案，该方案中的私钥由用户选取的秘密值和密钥生成中心KGC(Key Generation Center)产生的部分私钥组成，解决了密钥托管的问题。在查找云端密文时，传统的PEKS方案要求待检索的密文必须由同一公钥加密而来，而云端多用户环境下密文通常是由不同用户使用不同的公钥加密产生的，第三方不能直接对使用了不同公钥加密的密文进行比较。比如在公司电子邮件系统中，每封电子邮件都带有关键字密文标签(普通、紧急和机密等)，这些关键字密文标签都是由不同发送者使用不同接收者的公钥加密得来的，若要对这些邮件按标签进行分类管理，则传统的PEKS方案已无法满足此类应用需求。

针对这一局限，Yang等人[6]在CT-RSA(Cryptographers’ Track at the RSA)会议上首次提出了具有密文等值测试功能的公钥加密PKEET(Public Key Encryption with Equality Test)方案，给定密文C1=Enc(M1,PK1)和C2=Enc(M2,PK2)，该方案通过Test(C1,C2)算法判断M1=M2是否成立，实现了对不同公钥加密所得密文间的比较。不足的是，PKEET未提供授权机制，任何人获得密文后都可以执行等值测试操作，对用户隐私安全构成了威胁。随后，Tang等人[7-11]在PKEET方案基础上进行拓展，提出了支持授权的密文等值测试加密方案。2016年，Ma[12]提出了基于身份的密文等值测试加密方案。在该方案中，用户不用提前确认彼此的公钥，而是基于对方公开的身份信息生成公钥，解决了复杂的证书管理问题。2017年，吴黎兵等人[13]指出现有的密文等值测试加密方案多数基于单服务器构建，存在恶意服务器关键字猜测攻击KGA(Keyword Guessing Attacks)[14]的风险，为此设计了一个基于身份的双服务器密文等值测试公钥加密方案，并对方案的计算开销和通信开销进行了评估，确保其能够在资源受限的移动设备上运行。

现有的具有等值测试功能的公钥加密方案多数借助于双线性对实现，计算量大、效率偏低。本文设计了一个基于身份的无对密文等值测试公钥加密PF-IBEET(Pairing-Free Identity-Based Encryption with Equality Test)方案。该方案利用直线实现加密、解密、授权和等值测试过程，摆脱了双线性对的限制，提高了计算效率。同时，该方案是基于身份密码体制构建的，解决了基于PKI体系构建的密文等值测试方案中所存在的证书管理问题。最后通过仿真实验将本文方案与具有密文等值测试功能的方案进行了性能分析和比较，结果表明，所提方案具有良好的计算性能表现。

2 PF-IBEET方案模型

2.1 PF-IBEET方案系统模型

PF-IBEET方案包括密钥生成中心(KGC)、用户和云服务器3类实体，系统模型如图1所示。

(1)密钥生成中心KGC：负责生成系统参数paramas和系统主密钥s，并为用户和云服务器提供私钥SK。

(2)用户：生成密文并上传到云端，同时上传一个陷门给云服务器，用于执行等值测试操作。

(3)云服务器：存储用户上传的密文，同时接收用户的测试请求，对授权的密文执行等值测试操作。

Figure 1 System model

2.2 PF-IBEET方案形式化定义

PF-IBEET方案包括以下6个算法：

(1)Setup(1k):KGC输入安全参数k，输出系统参数paramas和系统主密钥s，公开系统参数paramas，自身保留主密钥s。

(2)密钥提取算法：①用户密钥提取：KGC输入主密钥s和身份IDi，返回密钥对(PKi,SKi)；②云服务器密钥提取：KGC输入系统参数paramas，返回云服务器的密钥对(PKc,SKc)。

(3)加密算法：用户运行该算法，输入系统参数paramas、公钥PKi和明文Mi，得到密文Ci。

(4)解密算法：用户运行该算法，输入系统参数paramas、私钥SKi和密文Ci，得到明文Mi。

(5)授权算法：用户运行该算法，输出陷门Tdi。

(6)测试算法：云服务器运行该算法，输入任意2个密文/陷门对(Ci,Tdi)和(Cj,Tdj)，判断Ci和Cj是否对应同一明文。若是，返回1，否则返回0。

2.3 PF-IBEET方案安全模型

PF-IBEET方案的安全模型考虑以下2种类型的敌手：

(1)Type-I。该类型的敌手A1可以获得陷门，但不能从密文恢复出明文。

(2)Type-II。给定2段明文M0和M1，敌手A2在未获得陷门的情况下，不能判断出密文是对其中哪段明文进行的加密。

针对上述2种类型的敌手，下面将通过挑战者β与敌手A1和A2之间的游戏来给出本文方案的安全模型。

游戏1:

(1)Setup(1k)：β输入安全参数k，生成系统参数paramas并将其发送给A1，自身保留主密钥s。

(2)查询阶段1。

A1进行以下查询：

①Hash查询：A1向β提交所要查询的身份IDi,β返回对应身份的哈希值。

②密钥提取查询：A1向β提交所要查询的身份IDi,β运行密钥提取算法，返回密钥对(PKi,SKi)给A1。

③解密查询：A1向β提交IDi的密文Ci,β运行解密算法，返回明文Mi给A1。

④授权查询：A1向β提交所要查询的身份IDi,β运行授权算法，返回陷门Tdi给A1。

(3)挑战阶段。

A1结束查询阶段1查询后，β随机选择明文M∈{0,1}*，输入用户ID*的公钥和明文M，运行加密算法，输出挑战密文C*给A1。

(4)查询阶段2。

该阶段与查询阶段1类似，但存在以下限制：

①ID*不允许出现在密钥提取查询中；

②(ID*,C*)不允许出现在解密查询中。

(5)猜测阶段。

A1猜测C*对应的明文M*，若M*=M，则赢得游戏1，获胜的优势如式(1)所示：

(1)

定义1对任意的Type-I敌手A1，若赢得游戏1的优势可忽略，则方案是OW-ID-CCA安全的。

游戏2:

(1)Setup(1k)：β输入安全参数k，生成系统参数paramas并将其发送给A2，自身保留主密钥s。

(2)查询阶段1。

A2进行以下查询：

①Hash查询：A2向β提交所要查询的身份IDi,β返回对应身份的哈希值。

②密钥提取查询：A2向β提交所要查询的身份IDi,β运行密钥提取算法，返回密钥对(PKi,SKi)给A2。

③解密查询：A2向β提交IDi的密文Ci,β运行解密算法，返回明文Mi给A2。

④授权查询：A2向β提交所要查询的身份IDi,β运行授权算法，返回对应的陷门Tdi给A2。

(3)挑战阶段。

A2结束查询阶段1查询后，选择2段明文M0,M1∈{0,1}*给β，β随机选择b∈{0,1}，输入用户ID*的公钥和明文Mb，运行加密算法，输出挑战密文Cb给A2。

(4)查询阶段2。

该阶段与查询阶段1类似，但存在以下限制：

①ID*不允许出现在密钥提取查询中；

②(ID*,C*)不允许出现在解密查询中；

③ID*不允许出现在授权查询中。

(5)猜测阶段。

A2输出猜测值b*∈{0,1}，若b*=b，则在游戏2中获胜，获胜的优势如式(2)所示：

(2)

定义2对任意的Type-II敌手A2，若赢得游戏2的优势可忽略，则方案是IND-ID-CCA安全的。

3 PF-IBEET方案

3.1 PF-IBEET具体方案

PF-IBEET具体方案如下所示：

(5)授权算法：用户运行该算法，输入私钥SKi=(xi,yi)、系统参数paramas和云服务器公钥PKc，输出陷门Tdi=xi。

(6)测试算法：假设用户A的密文为Ci=(Ci,0,Ci,1,Ci,2,Ci,3)，A运行授权算法生成陷门Tdi=xi；用户B的密文为Cj=(Cj,0,Cj,1,Cj,2,Cj,3)，B运行授权算法生成陷门Tdj=xj。

云服务器运行Test(Ci,Tdi,Cj,Tdj)算法得到如下结果：

xi,1‖xi,2‖yi,1‖yi,2=

Ci,3⊕H2(Ci,0,H1((Ci,0)Tdi),Ci,2)

xj,1‖xj,2‖yj,1‖yj,2=

Cj,3⊕H2(Cj,0,H1((Cj,0)Tdj),Cj,2)

点P1,i(xi,1,yi,1)和P2,i(xi,2,yi,2)确定直线方程fi(x)，点P1,j(xj,1,yj,1)和P2,j(xj,2,yj,2)确定直线方程fj(x)，验证直线方程fi(x)=fj(x)是否成立。若成立输出1，否则输出0。

3.2 正确性

(1)加/解密一致性。

①Ci,0=gr;

②Y=gy;

③Ci,2=M⊕H1(Yr)。

Ci,2⊕H1((gr)y)=

Ci,2⊕H1(Yr)=

M⊕H1(Yr)⊕H1(Yr)=M

(2)授权/测试算法。

①对于任意2段密文Ci和Cj，如果Dec(Ci,SKi)=Dec(Cj,SKj)≠⊥，给定陷门Tdi和Tdj，则测试算法Test(Ci,Tdi,Cj,Tdj)=1成立；

②对于任意2段密文Ci和Cj，如果Dec(Ci,SKi)≠Dec(Cj,SKj)≠⊥，给定陷门Tdi和Tdj，则测试算法Test(Ci,Tdi,Cj,Tdj)=1可忽略。

4 安全性分析

定理1PF-IBEET方案在随机预言模型下基于CDH困难假设达到了OW-ID-CCA安全。

证明对于Type-I敌手A1，构造一个多项式时间算法λ来解决CDH困难问题，给定三元组〈g,ga,gb〉，λ的目标是计算gab。在λ和A1的交互过程中，λ记录A1的所有查询和得到的回复。具体过程如下所示：

(1)Setup(1k)：对λ输入安全参数k，返回系统参数paramas={G,g,q,H1,H2,H3,H4,H5,H6,H7}给A1，其中Hi(i=1,2,3,4,5,6,7)是λ控制的随机预言机。

(2)查询阶段1。

A1进行多项式次查询：

①Hash查询：

②密钥提取查询：A1向λ提交所要查询的身份IDi，λ返回SKi并发送给A1。

③解密查询：A1向λ提交IDi的密文Ci,λ运行解密算法，返回明文Mi给A1。

④授权查询：当A1查询用户IDi的陷门时，λ运行授权算法，返回陷门Tdi=xi给A1。

(3)挑战阶段。

A1结束查询阶段1查询后，λ随机选择明文M∈{0,1}*，输入ID*的公钥PK=(gx,ga)和M并运行加密算法计算：Ci,0=gb，Ci,1=H1(gxb)，Ci,2=M⊕H1(gab)，Ci,3=(x1‖y1‖x2‖y2)⊕H2(Ci,0,Ci,1,Ci,2)，λ将挑战密文C*=(Ci,0,Ci,1,Ci,2,Ci,3)发送给A1。

(4)查询阶段2。

该阶段与查询阶段1类似，但存在以下限制：

①ID*不允许出现在密钥提取查询中；

②(ID*,C*)不允许出现在解密查询中。

(5)猜测阶段。

A1猜测输出M*，若M*=M，λ输出1，否则输出0。

在上述模拟交互中，如果最终返回1，说明λ有能力计算出M←Ci,2⊕H1(gab)。即λ能够解决CDH困难问题，这与CDH假设相矛盾，因此PF-IBEET方案是OW-ID-CCA安全的。

□

定理 2PF-IBEET方案在随机预言模型下基于DDH困难假设达到了IND-ID-CCA安全性。

证明对于Type-II敌手A2，构造一个多项式时间算法λ来解决DDH困难问题，给定的四元组〈g,ga,gb,gc〉，λ的目标是计算gab=gc是否成立。在λ和A2交互的过程中，λ记录A2的所有查询和得到的回复。具体过程如下所示：

(1)Setup(1k)：对λ输入安全参数k，返回系统参数paramas={G,g,q,H1,H2,H3,H4,H5,H6,H7}给A2，其中Hi(i=1,2,3,4,5,6,7)是λ控制的随机预言机。

(2)查询阶段1。

A2进行多项式次查询：

①Hash查询：

②密钥提取查询：A2向λ提交所要查询的身份IDi，λ返回SKi发送给A2。

③解密查询：A2向λ提交IDi的密文Ci,λ运行解密算法，返回明文Mi给A2。

④授权查询：当A2查询用户IDi的陷门时，λ运行授权算法，返回陷门Tdi=xi给A2。

(3)挑战阶段。

A2结束查询阶段1查询后，λ随机选择明文M0,M1∈{0,1}*和随机数n∈{0,1}，输入ID*的公钥PK=(gx,ga)和Mi运行加密算法计算：Ci,0=gb，Ci,1=H1(gxb)，Ci,2=Mi⊕H1(gc)，Ci,3=(x1‖y1‖x2‖y2)⊕H2(Ci,0,Ci,1,Ci,2)，λ将挑战密文C*=(Ci,0,Ci,1,Ci,2,Ci,3)发送给A2。

(4)查询阶段2。

该阶段与查询阶段1类似，但存在以下限制：

①ID*不允许出现在密钥提取查询中；

②(ID*,C*)不允许出现在解密查询中；

③ID*不允许出现在授权查询中。

(5)猜测阶段。

A2输出猜测值n*，若n*=n，λ输出1，否则输出0。

5 性能分析

本节从计算开销和通信开销2个方面对本文方案和文献[12,15,16]方案进行了性能分析和比较。

为了对各方案进行性能评估，在实验环境为Lenovo笔记本(AMD Ryzen 5 4600U with Radeon Graphics @2.10 GHz,16 GB内存,Linux操作系统)的平台上进行了仿真模拟实验，采用C语言编程，加密函数库由PBC[17]提供。表1为基本运算耗费时间，其中TH为HashToPoint时间，Th为普通哈希运算时间，TE为指数运算时间，TM为点乘时间，TP为双线性对运算时间。表2为各方案在加密、解密和测试阶段的计算开销对比。

Table 1 Time spent on basic operations

从表1可以看出，双线性对运算时间最长，然后依次是HashToPoint运算、指数运算、点乘运算和普通哈希运算。从表2可以看出，在加密阶段，本文方案和文献[16]方案比文献[12]和文献[15]方案少了2个双线性对运算，计算开销较小；在解密阶段，文献[12]和文献[15]方案比本文方案多出了2个双线性对运算，同时本文方案比文献[16]方案少了2个指数运算，本文方案计算开销最小；在测试阶段，文献[12]方案有4个双线性对运算，文献[15]方案有2个双线性对运算，文献[16]和本文方案指数运算个数相同，但本文方案多出了3个普通哈希运算，由于普通哈希运算计算开销较小，因此在该阶段本文方案和文献[16]方案计算开销基本相同。从总耗时来看，本文方案的计算开销要低于其他方案的，具有良好的性能表现。

表3为各方案在通信开销方面的对比，|G|表示为G群中元素的比特长度，|Zq|表示Zq群中数的比特长度。在密钥生成阶段，本文方案与文献[12]方案具有相同的公钥长度，为G群中元素比特长度的2倍；在加密阶段，文献[12]方案和文献[15]方案密文长度相同，同时本文方案的密文长度小于文献[16]方案的密文长度；在陷门生成阶段，各方案的通信开销几乎相同。

Table 3 Comparison of communication costs of each scheme

6 结束语

本文PF-IBEET方案通过直线实现消息加解密和密文等值测试过程，摆脱了双线性对的限制，提高了方案计算效率。同时，本文PF-IBEET方案基于身份密码体制构建，解决了基于传统PKI体系的密文等值测试方案中所存在的复杂证书管理问题。不足的是本文PF-IBEET方案存在密钥托管和密钥撤销的缺陷。针对该问题，未来将直线密文等值测试与无证书密码体制相结合，利用无证书的优势解决密钥托管的问题。

Table 2 Comparison of calculation costs of each scheme