可搜索公钥加密研究进展

宋文帅，邓淼磊，马米米，李昊宸

（河南工业大学 信息科学与工程学院，郑州 450001）

0 引言

随着互联网用户数量的增加以及云计算技术的不断成熟，全球数据量呈爆炸式增长趋势。在当下大数据的时代背景下，云存储服务［1］因具有数据的可伸缩性、共享性、可访问性和高效备份性等特点而被广泛应用。近年来，众多云服务提供商纷纷涌现，从最初的亚马逊、谷歌到现在的百度云、阿里云等。云服务器在给人们带来便利的同时，云上数据安全［2］和用户隐私也面临极大挑战。加密能够有效保护数据安全和隐私，但数据被加密后，原有的结构将发生改变，已有的针对明文数据的检索算法将不再适用，如何在密文数据上进行检索成为亟待解决的难题。一种简单的方法是用户先下载全部数据，解密后再在明文数据上检索。然而，下载全部数据一方面将占用大量网络带宽，另一方面将造成本地资源浪费。为实现对密文数据的高效检索，可搜索加密技术被提出。可搜索加密的工作流程如下：1）数据拥有者首先对数据和关键词加密并上传到云服务器；2）数据使用者使用私钥产生关键词搜索陷门并发送给云服务器；3）云服务器进行检索匹配，匹配成功后把密文返回给数据使用者；4）数据使用者对密文进行解密。

2000 年，Song等［3］首次提出可搜索对称加密概念。但基于对称密码体制的加密技术需要使用同一个密钥进行加密和解密，不适合复杂的多用户应用场景。为了解决该问题，Boneh等［4］首次提出可搜索公钥加密（Public-key Encryption with Keyword Search，PEKS）并应用在邮件路由场景中。发送方通过接收方的公钥对数据集和关键词信息进行加密；接收方利用自身的私钥产生关键词搜索陷门并发送给服务器；服务器对关键词进行检索并返回包含关键词的加密数据给接收方；接收方利用私钥对密文进行解密。PEKS 通过公私钥对实现明文的加密和密文检索功能，适用场景比可搜索对称加密更多、前景也更广阔［5-8］。

本文关注近几年PEKS 技术研究现状，探讨可搜索公钥加密技术的安全性和扩展性，并进行各方案的安全和性能的对比分析，最后对未来可搜索公钥加密技术领域进行展望。

1 可搜索公钥加密定义

加密技术的本质是破解某个“极微本源”，即破解某个数学困难问题，分析算法构造时所用的数学知识和嵌入的困难问题。本章给出PEKS 的多项式时间算法构造、算法一致性描述和安全模型。

1.1 形式化定义

定义1PEKS 算法描述［9］。PEKS 方案一般由4 个概率多项式时间算法构成：

PEKS=(KeyGen，Encrypt，Trapdoor，Test)

KeyGen(λ)=(pk，sk)：输入安 全参数λ，输出公 私钥对(pk，sk)。

Encrypt(pk，w)=Cw：输入公钥pk和关键词w，输出关键词密文Cw。

Trapdoor(sk，w′)=Tw′：输入私钥sk和用户感兴趣的关键词w′，输出用户关键词搜索陷门Tw′。

Test(pk，Cw，Tw′)=0/1：输入公钥pk，关键词密文Cw，用户搜索陷门Tw′。若w=w′，输出“1”；若w≠w′，则输出“0”。

PEKS 系统模型如图1 所示。

图1 PEKS系统模型Fig.1 PEKS system model

定义2双线性对［4］。设G1、G2是以素数q为阶的循环群，g是G1的一个生成元。若映射e：G1×G2→G2满足下列性质，则称e为双线性对。

2）非退化性：∃g，∃G1，使e(g，g)≠1。

3）可计算 性：对任意u，v∈G1，存在有 效的算法可计算e(u，v)。

定义3计算双线性Diffie-Hellman（Computation Bilinear Diffie-Hellman，CBDH）困难问题［10］。给定g，ga，gb，gc∈G1，其中：a、b、c是属于的随机数，计算e(g，g)abc∈G2是困难的。

1.2 算法一致性描述

传统PEKS 算法的一致性被定义为加密算法与解密算法互为逆过程。对PEKS 的完美一致性的定义描述为：随机的任意两个关键词w1、w2，通过陷门生成关键词w1的搜索陷门Tw1，由加密 算法生成关键词w2的密文Cw2，如果w1≠w2，Pr[ Test(Cw2，Tw1)=1 ]=0。文献［11］中指出PEKS 方案［4］只满足计算一致性，并不满足完美一致性和统计一致性，并给出三种一致性的定义。

定义4假设存在一名敌手A，定义算法一致性的安全游戏。

敌手A赢得上述游戏的优势为：AdvA(λ)=

当任意的敌手A赢得上述安全游戏的概率AdvA(λ)=0，即视为该PEKS 方案具有完美一致性。

当任意的敌手A赢得上述安全游戏的概率AdvA(λ)关于ε可忽略，即视为该PEKS 方案具有统计一致性。

对任意的敌手A在多项式时间内赢得上述游戏的概率AdvA(λ)是关于ε可忽略的，即视为该PEKS 方案满足计算一致性。

1.3 安全模型

Boneh 基于身份加密（Identity-Based Encryption，IBE）［12］定义了PEKS 的安全性并提出了选择关键词攻击下的不可区分性（INDistinguishability against Chosen Keyword Attack，INDCKA）安全模型，安全模型通过挑战者C和敌手A之间的博弈游戏进行定义［13］。

如图2 所示：1）挑战者C执行KeyGen(λ)算法生成公钥pk和私钥sk，并把公钥pk发送给敌手A。2）敌手A自适应地查询搜索陷门预言机OTrapdoor，获得关键词w∈{0，1}*的陷门Tw。3）敌手A随机选取两个关键词w0、w1发送给挑战者C，要求选取两个未被询问的关键词。挑战者C随机选取一个比特b∈{0，1}，通过算法Encrypt(pk，wb)生成挑战密文C并发送给敌手A。4）当A再次询问搜索陷门预言机OTrapdoor时不能询问关键词w0、w1的陷门信息。5）敌手A针对关键词进行猜测，选取一个比特b′∈{0，1}输出：如果b=b′则敌手A攻击成功；否则敌手A攻击失败。

图2 PEKS安全模型中的博弈过程Fig.2 Game process in PEKS security model

敌手A赢得博弈游戏的攻击优势为：AdvA(λ)=

定义5如果敌手A赢得博弈游戏的优势关于ε可忽略，即AdvA(λ) ＜negl(ε)，则PEKS 方案是语义安全的。

2 PEKS典型构造方案

本章对三个具有代表性的PEKS 方案进行分析陈述，列出它们的算法模型，最后对三者的通信量、服务端存储量、性能效率以及安全性进行对比分析。

2.1 BDOP-PEKS方案

2004 年Boneh等［4］基于BF-IBE（Boneh-Franklin IBE）系统构造了适用于邮件路由系统的PEKS 方案BDOP-PEKS（Boneh-Di-Ostrovsky-Persiano PEKS），并在双线性Diffie-Hellman（Bilinear Diffie-Hellman，BDH）困难问题假设下证明了方案的安全性。具体构造如下：

1）KeyGen(λ)：输入安 全参数λ，生成公钥pk=[g，h=gα]和私钥sk=α。其中是循环群；g是循环群G1的生成元。

2）PEKS(pk，w)：输入公钥pk和关键词w，生成关键词密文，其中；H为哈希函数。

3）Trapdoor(Sk，w′)：输入私钥sk和用户待查询的关键词w′，输出关键词搜索陷门Tw′=H1(w′)α∈G1。

4）Test(pk，Tw′，Cw)：令Cw=[A，B]，验证H2(e(Tw′A))=B是否成立，成立则输出1 并返回密文给用户，否则输出0。

BDOP-PEKS 方案存在一些缺点［13］：1）双线性对运算导致算法计算开销大、效率低，不适合用于大批量加密数据的检索查询；2）需要建立安全信道来抵御网络攻击者获取搜索陷门信息；3）由于搜索陷门生成算法不满足陷门不可区分性，所以无法抵抗关键词猜测攻击。

2.2 KR-PEKS方案

2006 年，Khader等［14］基于BDOP-PEKS 方案进行改进，设计出基于K-Resilient IBE 的PEKS 方案（KR-PEKS），并在标准模型下证明了方案的安全性。具体构造如下。

1）KeyGen。

步骤1 选取q阶群G，其中：g1，g2∈G。

步骤4 随机选取抗碰撞的哈希函数H：G→{0，1}λ和H′：G→{ 0，1}k。

步骤5 输出公钥PkR=(g1，g2，A0，…，Ak，B0，…，Bk，D0，…，Dk，H，H′)和私钥SkR=(f1，f2，h1，h2，p1，p2)。

2）KR-PEKS。

KR-PEKS 方案避免了双线性对的使用，显著减小了计算开销。但是此方案生成的搜索陷门数量不能大于K，所以K值的选取十分重要。

2.3 DS-PEKS方案

2007 年，Di Crescenzo等［15］基于二次剩余问题的变体构造了DS-PEKS（Di-Saraswat PEKS）方案，具体构造如下。

1）M-KeyGen(1m)：输入一元参数1m，其中：m∈Z*，随机选取长度为2/m的素数p、q，使p和q模4 同余3，令n=pq。生成公钥ui∈，私钥Apriv=(p，q)。

DS-PEKS 方案的构造形式使关键词密文长度较短，提高了加密和查询的效率，但该方案在服务器和用户之间进行通信时会占用大量带宽。

以上三种方案都通过计算关键词陷门对关键词进行匹配的基本PEKS 构建策略，测试文件是否包含待查询的关键字。表1 是三种方案的性能对比，其中：k为安全参数；|g|为G中元素所占用的存储空间；p为循环群G的阶；n为数据总数目；li为第i个数据中的关键词个数；N为关键词字典中的关键词字数。表中假设包括二次不可区分性问题（Quadratic Indistinguishability Problem，QIP）、BDH 与决策Diffie-Hellman（Decisional Diffie-Hellman，DDH）问题。

表1 PEKS典型方案对比Tab.1 Comparison of typical PEKS schemes

3 安全性扩展研究

3.1 关键词猜测攻击

Byun等［16］指出当用户选取的关键词是对自己有特殊意义的单词时，关键词信息熵就会变小，而用户在实际应用中大多会如此选择，导致关键词空间不够大。当关键词字典的空间远小于密钥空间且用户喜欢用跟自己有关联的关键词进行检索时，攻击者利用穷举策略就能实现关键词猜测攻击（Keyword Guessing Attack，KGA）。外部攻击者发起的攻击称为外部关键词猜测攻击，而由云服务器代理商或服务器中其他任意角色发起为内部关键词猜测攻击。此外，恶意云服务器为识别陷门和关键字之间的关系，利用关键词统计分布概率知识和常用谓词进行统计关键词猜测攻击也被包含在KGA 中。Jeong等［17］证明了在KGA 下不存在PEKS 方案满足算法一 致性和 安全性。为了抵 抗KGA，Baek等［18］、Rhee等［19-20］先后进行研究，证明了PEKS 方案抗击KGA 的充分条件是关键词搜索陷门的不可区分性。

Baek等［18］提出的指定服务器的PEKS（designated server PEKS，dPEKS）方案可以保证除用户指定的服务器以外所有服务器都无法判断关键词密文和陷门是否匹配，但安全性提高甚微。随后抗外部离线关键词猜测攻击的dPEKS 方案［21-25］陆续被提出。2011 年，Wang等［26］指出Rhee 的dPEKS方案只能抵抗从外部发起的关键词猜测攻击，无法抵抗从恶意服务器内部引发的关键词猜测攻击。2014 年，Wang等［27］提出双服务器概念模型以实现抵抗内部关键词猜测攻击，但由于双服务器的计算开销非常大，所以没有广泛应用。2016年，Chen等［28］提出DS-PEKS（Dual-Server PEKS）方案，由两个独立的服务器联合执行测试算法，能有效抵抗恶意的内部关键词猜测攻击。Huang等［29］在2017 年设计出一种可认证的PEKS 方案，采用发送方的私钥和接收方的公钥进行关键词加密，通过发送方的公钥和接收方的私钥生成关键词搜索陷门，有效抵抗了内部关键词猜测攻击。2019 年王少辉等［30］基于变形线性决策困难问题（modified Decisional LINinear assumption，mDLIN）构建了满足陷门和密文不可区分性的加密算法，并在随机预言机模型下证明了方案的安全性。虽然文献［30］的方案具有更小的开销，但是不具有普适性，密文和搜索陷门生成算法一样，即采用对称双线性对，被破解的概率增大，并且方案在标准模型下的安全性亟须解决。2018年，徐海琳等［31］构造一个无安全信道的PEKS 方案，并在标准模型下证明了方案的安全性，但该方案基于双线性，计算开销很大，所以实用性不强。2020 年，Yu等［32］为抵御内部KGA 提出了一种基于格的PEKS 方案，采用基于格的签名技术对关键词加密，以防止恶意服务器伪造有效密文。对于离线的内部/外部KGA 已有大部分研究，但在线的KGA 却较少，文献［33］采用密文随机化技术设计出可以抵抗在线和离线的KGA 方案，并在随机模型下证明了方案的安全性。

将KGA 设计在内已是现在PEKS 方案必须要考虑的内容。从最初的使用双服务器，指定服务器到使用私钥和认证联合加密关键词再到基于格和区块链的技术，抵抗恶意关键词猜测攻击一直没有得到有效解决。未来面对高性能计算机和庞大个人隐私数据，设计出通用并且可以抵抗全面KGA 的方案值得深究。

3.2 文件注入攻击

文件注入攻击（File-Injection Attack，FIA）是可搜索公钥加密要面临的另一个安全性挑战。Zhang等［34］首次发现了可搜索加密中的文件注入攻击形式，并对此展开研究。文件注入攻击通过恶意服务器向客户端注入一组文件以获取关键词的搜索陷门信息，文件注入攻击会对数据隐私产生不可逆的破坏，攻击者很容易获取大量跟用户相关的、特定的敏感 关键词信息。Li等［35］为解决FIA 对保序加密（Order-Preserving Encryption，OPE）和逆序加密（Order-Revealing Encryption，ORE）的威胁，通过逆向思维首先针对两类加密技术的FIA 方案进行挑战，敌手在只拥有明文空间和一些之前的加密顺序或查询范围时实现了FIA，并由此提高加密算法的安全性。Huang等［36］就非自适应文件注入攻击（Non-Adaptive File Injection Attack，NAFIA）进行研究，设计了一种新型文件更新模式，对文件存储和关键词索引进行调整，采用随机数异或的方法设计密钥。该方法兼顾文件存储和索引安全性，有效防止服务器识别文件插入的时间和位置，在抵抗FIA 的同时提高了通信效率。

4 应用性扩展性研究

4.1 查询方式扩展

关键词查询方式一直是重点问题，针对单关键词不连续的问题，Boneh等［10］提出支持连接关键词查询和关键词比较查询的PEKS 方案，通过使用隐藏向量加密技术检索关键词密文。出现多关键词查询后，关键词之间的联系又出现一系列难题，如关键字之间的顺序、多关键字存储结构、关键词集合子集查询等。为了提高用户得到密文的正确率并提高云服务器的效率，Hu等［37］提出支持排序的多关键词PEKS 方案，对查询结果进行排序，返回给用户最相关的k个文件，节约了大量的计算开销。但基于双线性对的加密方案效率提升较小，杨宁滨等［38］提出一种无需双线性对且无需安全信道的多关键词可认证PEKS 方案，在减少计算双性对时产生的大量开销的同时也省去了建设安全信道付出的通信代价，并证明了方案满足密文不可区分性。

为了进一步提高检索能力，Li等［39］首次提出支持模糊关键词查询的可搜索加密方案，通过使用编辑距离测量关键词的相似度并构造模糊关键词集合，使用户在错误拼写或者相近单词下也能搜索到想要的内容。Liu等［40］在文献［39］的基础上进一步减小索引空间的大小。Vaanchig等［41］基于模糊函数和加密树技术提出一种支持模糊关键词查询的PEKS方案，并在随机预言机模型下证明该方案可以抵抗关键词猜测攻击，保证了服务端和用户端更高效的检索操作。树形结构在检索关键词时能够极大降低检索时间，Shen等［42］为了实现多关键字搜索和搜索结果排序的目标，采用B+树的索引结构，为关键词集建立相似的集合作为树的节点，与线性搜索相比效率更加出色。

除上述方式外，目前主流的检索方式还有可验证关键词搜索［43］、相似度关键词搜索、语义关键词搜索、范围查询、子集查询［44］等高效的查询方式。

4.2 结构扩展

云时代环境下，大量无接触、便携式物联网设备与互联网融合导致大量数据在云端存储。传统PEKS 方案在面对当下热点应用场景如电子医疗、视频直播、区块链、元宇宙时，方案的效率以及适用性捉襟见肘。本节针对PEKS 方案在新背景下归纳出的三大热点需求，即：用户权限代理分发、密钥管理问题、细粒度搜索和访问控制能力，给出相应功能扩展方案介绍，并对列出的方案进行性能和安全分析。

4.2.1 代理可搜索公钥加密方案

当用户A给用户B发送一个由用户B公钥加密的密文邮件，但是用户B由于某种原因无法接收到密文邮件，于是B通过授权服务器把搜索和解密密文邮件的权限授权给用户C，C就可以使用自己的私钥进行搜索和解密A发送给B的密文邮件。因此，数据之间的授权和共享功能在PEKS 方案中成为热点。在过去共享数据明文信息时，需要授权服务器全程参与，导致效率低下。“代理”的概念首次由Blaze等［45］提出，代理指通过一个可信的代理服务器将数据所有者上传至云服务器的密文运用包含被授权用户密钥的信息进行二次加密，数据所有者就可以授权给他想要分享的数据使用者，数据使用者可以通过自己私钥产生搜索陷门。Shao等［46］在2010 年基于“代理”的概念首次结合PEKS 加密特性，提出可搜索代理重加密（Proxy Re-Encryption with Keyword Search，PREKS）概念，PREKS 模型如图3 所示。与原始的代理重加密方案不同，PREKS 模型中被授权的数据使用者可以给云服务器提供关键词搜索功能，发送关键词陷门对重加密密文进行关键词检索。文献［46］中构造了一种能够从发送方到接收方和从接收方到发送方的双向代理PREKS 方案，并在随机预言机模型下证明了方案的安全性。

图3 PREKS系统模型Fig.3 PREKS system model

Wang等［47］进一步扩展文献［46］的研究，提出了支持连接关键词搜索的受限单向代理重加密的方案，查询能力显著提高，并在随机预言机模型下证明了方案的安全性。Guo等［48］又进一步在标准模型而并非随机预言机模型下设计了双向的指定服务器代理重加密方案，该方案支持搜索结果正确性的验证。如今量子计算机的出现对密码安全性产生极大挑战，为进一步提高方案安全性，能够抵抗量子计算机攻击，Yang等［49］也在标准模型下给出安全证明，提出一个新的抗量子的PREKS 方案。对以往只针对指定亲近的单个用户授权的场景下，Hong等［50］提出一种基于属性的PREKS 方案，提高了在多用户场景下的灵活性。牛淑芬等［51］和Xu等［52］就电子医疗应用场景，提出了具有指定关键词的代理重加密方案，数据方通过指定的关键词进行代理共享，而不是把权限全部移交给被授权用户。在授权多用户的同时还指定每个用户的权限范围，提高了密文数据的安全性。PREKS 中涉及到三个实体，构造者通过实施不同目标的安全模型以更好地抵御安全攻击，但针对不同目标的安全性缺少通用的方案。未来PREKS 的研究趋势是设计一个通用的安全模型以抵抗现有的攻击，并在不进行重加密的模式下对被授权用户撤销权限。

表2 为比较有代表性的方案之间的性能对比。其中：E为模幂运算时间；e为双线性对运算时间；h为一般哈希运算时间；H为哈希到点运算时间；l为关键词数量；n为密文数量；m为用户查询关键词数量。表中的假设包括：决策双线性Diffie-Hellman（Decisional Bilinear Diffie-Hellman，DBDH）、q-双线性Diffie-Hellman反演（q-Bilinear Diffie-Hellman Inversion，q-BDHI）、商决策 双线性Diffie-Hellman（quotient Decisional Bilinear Diffie-Hellman，qDBDH）、哈 希Diffie-Hellman（Hash Diffie-Hellman，HDH）、改进双线性Diffie-Hellman（modified Bilinear Diffie-Hellman，mBDH）、qDBDHI（q-Decisional Bilinear Diffie-Hellman Inversion）、l-ABDHE（l-Augmented Bilinear Diffie-Hellman Exponent）、wIND-CCA（weakly IND Chosen Ciphertext Attack）。

表2 PREKS方案对比Tab.2 PREKS scheme comparison

4.2.2 基于身份的可搜索公钥加密方案

基于身份加密（IBE）的概念最早由Shamir［53］在1984 年提出，“身份”的概念指加密公钥中包含能够证明用户身份的信息，这些信息可以是电子邮箱、电话号码、IP 地址、或者身份识别码等，私钥则可以通过密钥生成中心根据用户的身份信息生成。基于身份的可搜索公钥加密（PEKS based on Identity-Based Encryption，PEKS-IBE）解决了传统的基于PKI（Public Key Infrastructure）加密中的证书管理问题。PEKSIBE 的基本模型如图4 所示。

图4 PEKS-IBE系统模型Fig.4 PEKS-IBE system model

Boneh等［4］设计出BF-IBE 系统构造了实用的PEKS-IBE方案，为证书管理提供了缓解方案；但该方案基于双线性对构造，在性能上达到实际生产比较困难。Di Crescenzo等［15］在文献［54］的基础上提出第一个不需要双线性对的PEKSIBE 方案，并在随机预言机模型下证明了方案的安全性。针对通信上带来的开销，Wang等［25］给出了无安全信道的PEKS-IBE，允许多用户在点对点组中共享云服务器的数据，降低了网络中的通信代价。Emura等［55］提出了一种支持关键词可撤销的匿名身份加密的PEKS 方案，在一定程度上抵抗陷门泄露带来的安全隐患。Wu等［56］首先提出支持连接关键词的PEKS-IBE，但该方案不满足密文的不可区分性。王少辉等［57］基于文献［56］提出了指定测试者的PEKS-IBE 方案，解决了不完全满足密文不可区分性的问题，证明了抵抗离线关键词猜测攻击的充分条件是密文不可区分性。牛淑芬等［58］针对电子邮件加密系统中存在的离线关键词猜测攻击问题，采用加密关键词和生成搜索陷门同时认证的方式，提出了具有陷门和密文不可区分性安全的指定服务器的PEKS-IBE。IBE 对密钥和证书管理提供解决策略，但目前PEKS-IBE 面对动态更新的密钥，如何设计出计算代价更小、更适合便携式物联网设备的方案成为新的需求。

表3 为上述几种方案的计算开销对比。其中：Tsm为标量乘法运算时间；l为关键词数量；n为共享数据的用户数；λ为安全参数；J为雅可比符号。表中假设包括：QIP、DBDH、BDH 和计算性Diffie-Hellman（Computational Diffie-Hellman，CDH）。

表3 PEKS-IBE方案对比Tab.3 PEKS-IBE scheme comparison

4.2.3 无证书可搜索公钥加密方案

AI-Riyami等［59］在2003 年首次提出无证书公钥密码体制。在无证书公钥密码体制中，用户私钥由密钥生成中心（Key Generate Center，KGC）和用户共同生成，是另一种有效解决基于公钥的密码体制中存在的密钥托管和证书管理问题的途径。无证书PEKS 模型如图5 所示，私钥由KGC 和用户共同生成，数据拥有者将密文上传者至云中，拥有检索权限的数据用户根据想搜索的关键词生成陷门，云服务器执行匹配操作返回给数据用户。

图5 无证书PEKS系统模型Fig.5 Certificateless PEKS system model

Peng等［60］首次将无证书密码体制引入PEKS 方案中，提出一种不需要安全信道的无证书PEKS 方案。Zheng等［61］基于线性决策问题提出一种高效的标准模型下可证明安全的无证书PEKS 方案。面对关键词查询功能的扩展问题，Ma等［62］提出无安全信道的支持多关键词的无证书可搜索加密方案，并在随机预言机模型下证明了方案的安全性。随后Ma等［63-64］在智慧医疗和移动医疗背景下又提出两种高效的无证书加密方案，解决了密钥托管难题，并在随机预言机模型下证明该方案可以抵抗关键词猜测攻击。Wu等［65］在医疗物联网（medical Internet of Things，mIoT）应用场景下，提出一种指定服务器的可认证的无证书可搜索公钥加密方案，在医疗云物联场景下给出了密钥和证书管理的新思路。Lu等［66］提出了一种无需双线性对的无证书可搜索公钥加密方案，极大提高了方案的计算效率，并在随机预言机模型下证明了方案的安全性。张玉磊等［67］基于公钥加密等值测试，实现密文的等值比较，提出支持关键词搜索的无证书密文等值测试加密方案。方案在检索时自动判断是否接收者需要的信息，根据判断结果进行等值测试，避免了无效测试，提高了检索效率。

表4 给出了上述几种无证书PEKS 方案的性能比较。其中：CI 是Ciphertext Indistinguishability假设，DLIN 是Decisional Linear 假设。

表4 无证书PEKS方案对比Tab.4 Certificateless PEKS scheme comparison

4.2.4 基于属性的可搜索公钥加密方案

Sahai等［68］在2005 年提出基于属性的加密（Attribute-Based Encryption，ABE）概念，把用户的信息元素作为属性，形成一系列属性集。PEKS 方案大多采用传统公钥加密实现，需要发送方使用每一个接收方的公钥加密数据，生成多个密文，造成资源浪费，如图6（a）所示。在ABE 中，发送方将满足所有用户的访问策略嵌入密钥，然后通过满足所有用户的公共参数对数据加密生成唯一的密文，如图6（b）所示。接收方私钥和属性相关联形成新的私钥，如果接收方的属性与访问策略集中的信息匹配时，就可以解密。根据与访问策略集相关的是密文还是私钥，基于属性加密还可分为密钥策略属性基加密（Key-Policy Attribute-Based Encryption，KPABE）和密文策略属性基加密（Ciphertext-Policy Attribute-Based Encryption，CP-ABE）两种方式。

图6 传统公钥加密和ABE的对比Fig.6 Comparison of traditional public key encryption and ABE

Han等［69］基于弱匿名ABE 的概念设计了一个多用户下的基于属性公钥可搜索加密（PEKS bsed on Attribute-Based Encryption，ABEKS）方案。Zheng等［70］引入可验证属性基，设计了可以通过访问策略进行检索外包数据和验证服务器是否进行正确检索的ABEKS。但是此方案需要建立安全信道，开销成本较大。Li等［71］设计了将密钥分发外包的ABEKS 方案，只有当用户的访问策略满足相应的属性时，用户才能解密密文，减少了开销成本。2017 年Zhu等［72］设计实现支持模糊关键词搜索和密文策略属性基的ABEKS 方案。Cao等［73］提出基于模糊密文策略属性的可搜索加密方案，减小了抵抗服务器提供商和数据用户之间碰撞攻击程度，提高了安全性。Miao等［74］设计了可以抵抗离线关键词猜测攻击的ABEKS 方案。ABE 的引入给PEKS 方案提供了细粒度的访问控制功能，在会员付费频道、用户权限控制、移动物联网等场景都有很好的应用前景。目前ABEKS 大多基于CPABE 提出，未来针对KP-ABE 的方案应用也是一种趋势。

表5 给出了上述方案的性能和安全性的分析比较。其中：BDH 是双线性 Diffie-Hellman 假设；SeS 为Selective Security；N为数据所有者的访问控制策略中涉及的属性数量；S为数据用户的属性编号。

表5 ABEKS方案对比Tab.5 ABEKS schemes comparison

4.3 应用领域扩展

4.3.1 区块链

由于区块链的去中心化、透明、可溯源、不可篡改等特性，越来越多的学者将可搜索公钥加密技术与区块链技术结合以提高加密的安全性。2019 年，刘格昌等［75］提出一种基于可搜索加密的区块链数据隐私保护机制，把加密数据放在链上，在交易单中增加关键词的加密信息以进行关键词检索，用户使用私钥生成关键词搜索陷门。将此方案运用到个人医疗数据区块链系统的应用场景中，解决了个人医疗隐私信息的泄露等问题。同年，高梦婕等［76］也针对医疗场景提出了一种结合区块链的可搜索加密方案，在密钥分发时嵌入Shamir 秘密共享技术，利用智能合约技术进行密钥的验证和恢复，并给出了方案的安全性证明。牛淑芬等［77］针对密文检索效率低的问题，提出一种基于B+树结构的密文排序可搜索加密方案。通过区块链技术解决多方信任的问题，利用B+树的索引结构结合加权统计算法实现了多关键词查询结果的排序，提高了链上密文数据检索的效率，并在随机预言机模型下证明了该方案的安全性。

2020 年，杜瑞忠等［78］针对可搜索公钥加密方案中常见的陷门安全问题，结合智能合约技术与PEKS 方案提出了基于区块链的可搜索公钥加密方案，解决了陷门不可区分性问题，证明了方案可以抵抗内部关键词猜测攻击。同年，闫玺玺等［79］提出了基于区块链的可验证的属性基可搜索加密方案，实现了检索结果的可验证性，并依据区块链的不可篡改性，保证了用户不需要额外的验证操作就可以得到正确结果，大幅提高检索效率并降低计算开销。Yang等［80］在加密文件上传至云上的同时将加密索引放在区块链中，保证了加密索引的防篡改、完整性和可追溯性；同时也保证了用户在不需要任何第三方验证的情况下即可获得准确的搜索结果；此外，该方案在随机预言机模型下证明可以抵抗内部关键词猜测攻击。2021 年，Sun等［81］为了在保护物流信息隐私安全的同时快速查询物流信息，提出了可搜索和加密的物流信息区块链数据查询算法，解决了在时间更新后无法查询加密数据的问题。PEKS 方案将密文、公钥、用户关键词集或关键词陷门等内容进行上链，将它扩展功能与区块链领域技术相结合是当下和未来研究的热点之一［82-83］。

4.3.2 智能电网

智能电网作为物联网的新型应用受到学术界的广泛关注。智能电网系统不仅可以通过传感器和智能电表测量和收集用户用电量数据，还可以通过强大的云计算平台存储和利用能源使用数据。随着电力信息上传到云端，这些数据的安全性和隐私性至关重要，于是越来越多的公司选择将数据加密后外包到云服务器。2013 年，Wen等［84］提出一种基于加密计量数据的隐私保护范围查询（Privacy-preserving Range Query，PaRQ）方案以解决智能电网财务审计中的隐私问题。PaRQ 构造了基于隐藏向量加密的范围查询谓词来加密数据的可搜索属性和会话密钥。2014 年，Li等［85］提出一种支持多关键词范围查询的可搜索加密方案，解决了智能电网能源拍卖中买家和卖家的信息隐私和能源数据加密检索的问题。2019 年Uwizeye等［86］为智能电网场景设计了一种新的连接关键词搜索的无证书可搜索公钥加密方案，降低了通信成本并在随机预言机模型下证明了方案的安全性。同年，Eltayieb等［87］提出一种基于属性的可搜索加密方案。此方案的加密阶段和生成属性控制策略阶段均在离线状态下执行，并且证明了能够抵抗关键词猜测攻击。2021 年，Tur等［88］将混沌密码和搜索加密技术嵌入电力系统之间的通信指令，实现了在线抵御网络攻击和关键词猜测攻击。

5 结语

本文对现有PEKS 方案的典型构造、安全问题、表达方式、功能扩展和应用领域展开叙述。在云计算和物联网的时代大背景下，PEKS 的研究越来越成熟，但依然是学者们研究的热点。各种PEKS 方案仍然有许多缺点或问题待解决。

1）搜索表达方式：在现有的PEKS 方案上构造更加高效且复杂的搜索查询方式，不仅支持单关键词，还要支持多关键词、字符串、模糊关键词、语义关键词、子集搜索等检索方式。然而大多数搜索方式的改进都是以效率和安全性为代价，致力于协调统一将是未来研究的重点之一。

2）安全性和效率：现有的PEKS 方案大都在随机预言机模型下进行安全性证明，具有局限性，在实际应用中不一定安全。未来的PEKS 方案将着重在标准模型下给出安全性证明，不仅要求满足离线关键词猜测攻击，还要满足在线的关键词猜测攻击。同时，现有的大部分PEKS 方案都基于双线性对困难问题设计，计算开销较大，如何构建一个高效的无双线性对的PEKS 方案且在标准模型下给出普适的安全性证明仍是一个亟待解决的问题。

3）抗量子安全：随着量子计算机的发展，许多基于传统数学困难问题的PEKS 方案的安全性将受到威胁。如何设计能够抵抗量子攻击的PEKS 方案将是未来重点研究的方向。

面对中央处理器（Central Processing Unit，CPU）算力不断提升和数据量飞速增长，对PEKS 技术进行几个方面的展望。

1）多源数据：随着多媒体信息以爆炸式的速度增长，尤其是以视频和图像为代表的多媒体信息。为了保护数据隐私，包含敏感内容的数据信息在上传到云端之前需要进行加密。然而，如何在加密数据上查询所需的视频或图像成为一个棘手的问题，未来可以考虑应用PEKS 处理此类问题。

2）基于格的PEKS：随着量子计算的发展，传统的密码算法将面临巨大的挑战，很容易被量子计算机攻击，因此，有必要设计一种能够抵抗量子攻击的密码算法。基于格的密码系统由于效率和概念上的简单性，在后量子算法中变得越来越流行。学术界对此已有研究［89-90］，未来迫切需要构建一种高效、安全的基于格的PEKS 方案。

3）轻量级的PEKS：在实际的工业物联网应用中，大多数的设备均为轻量级的物联网设备，例如，传感器、集线器或微型移动设备等，这些设备大多仅具有有限的硬件计算能力和信号传输能力。考虑到这些轻量级设备的计算能力，加入加密算法时必须采用轻量级的加密标签生成算法，使算法具备较低的计算开销和通信开销，从而达到降低能耗、延长电池使用时间的目的。因此，设计出符合物联网环境下的轻量级可搜索加密方案将是可搜索加密未来的研究任务之一。