原文标题： Blockchain-Enabled Public Key Encryption with Multi-Keyword Search in Cloud Computing
原文作者： Zhenwei Chen,Axin Wu,Yifei Li,Qixuan Xing and Shengling Geng
原文机构： 西安邮电大学，暨南大学，青海师范大学，青海省西宁市高原科学与可持续发展研究所
原文地址： https://doi.org/10.1155/2021/6619689
发表日期/期刊： 21 January 2021/Security and Communication Networks
笔记整理： doxbwx@163.com

1. 简介

为了确保用户在检索数据时的安全，针对云环境的可搜索加密技术被广泛采用。作者针对目前已有的可搜索加密（SE）方案进行改进，提出了支持区块链的多关键词搜索的公钥加密方案（BPKEMS）
该方案的优势在于：

• 支持文件更新
• 利用智能合约确保data owner 和data user之间的交易公平性
• 对文件编号来实现可验证性
• 可以抵御内部关键字猜测攻击（KGAs），并且具有更好的计算开销

1.1 预备工作

1.1.1 双线性配对

设G1，G2是两个乘法循环群。一个映射e。G1 × G1 ⟶ G2，如果它具有以下性质，则称为对称双线性配对。

1. 双线性。e(u^a, v^b) = e(u, v)^ab, ∀u, v∈G1, 和 ∀a, b∈Zp。
2. 非生成的。e(g, g)≠1。让1∈G2是G2组的身份元素。
3. 可计算。∀u, v∈G1，e(u, v)；有一个多项式时间算法可以轻易计算e。

1.1.2 决策性Diffie-Hellman（DDH）问题

给定G1的一个生成器g，则g、ga、gb、gc∈G1，其中a、b、c∈Zp。DDH问题是要确定g^c是否等于gab。假设DDH问题是困难的，这意味着没有对手能以不能忽略的概率解决这个问题。

2、方案构建

该方案的具体系统模型如下图所示：

图中DO表示data owner，DU表示data user，TA为值得信任的权威机构TA，CS为云服务器，SC是智能合约。

2.1 算法

2.1.1 Setup(1^λ)

输入安全参数λ，生成系统参数SP=（g，h，H1）
g为G1的生成器，h和H1是两个抗碰撞的哈希函数，h: 0, 1∗ ⟶ Zp， H1: 0, 1∗ × 0, 1∗ ⟶ 0, 1

2.1.2 KeyGen(SP）

1. KeyGeno：随机选a∈ Zp作为DO的私钥sko，计算公钥pko = g^a
2. KeyGenu：随机选b∈ Zp作为DU的私钥sku，计算DU的公钥pku = pku1, pku2 ， where pku1 = e(g, g)^(1/b) ，pku2 = g^b
3. KeyGens：随机选c∈ Zp作为CS的私钥sks，计算公钥pks = g^c

2.1.3 Enc (SP, pku, sko, F)

file set F = f1，…，ft，keyword dictionary W=w1，…，wn

1. DO从F中提取出各个文件的keyword index Ii=I0，I1，I2，Ij 其中i ∈ [1, t]。DO随机挑选r∈ Zp，计算Ii,0=e(g,g)^r，Ii,1=pku2^r，Ii,2=e(g,g)^(ar/b)，Ii,j=g^(-rh(wj))，其中j ∈ [1, n]
2. DO用对称加密算法加密每个fi ∈ F，计算DO和DU的共享密钥K=pku2^(sko) = g^ba。对每个文件加密，加密文件称为Ci。
3. DO对文件进行编号，用共享密钥K加密文件索引，加密文件索引称为Ni，将Ci和Ni存储起来，进行哈希操作得到Mi=H1(Ni,Ci).

Ni和Mi打包和keyword index set一起上传给SC，file index set和密文C传给CS

2.1.4 Trap(W′, pks, pko,sku)

Trap算法是由DU运行的，DU查询操作时，需要为关键字产生一个trapdoor TW′。然而trapdoor包含两个部分，TW′,1和TW′,2

1. DU随机挑选一个数φ ∈ Zp ，让TW′,1=φ。
2. DU再计算TW′,2

关键字位置L=ρ(1)，…，ρ(l)，表示从W '到W的位置，
其中ρ：wπ ′ = wρ(π)。W '表示搜索的关键字集，W表示关键字字典
DU设置一个time limit节点T1 。

把L位置的trapdoor传给SC，SC执行deposit操作。然后DU发送trapdoor TW′和time limit节点T1给SC，再上传userID，请求SC执行Search服务。

2.1.5 Search (I, TW′ , L,sks).

owner：DO账户
user：DU账户
userdeposit：区块链中的当前deposit
DU将账户余额deposit给user
gasprice：gasline的单位价
cost：每个完整查询操作总成本
Gaslsrch：表示gas limit
Gassrch，调用搜索算法的成本

在收到DU的ID并请求搜索服务后，执行以下算法：

2.1.6 Verification and Decryption (SP, C, C′, Ns)

DU执行该算法，当SC将满足搜索要求的file index set Ns和DU的id发送给CS。然后CS返回file密文set C和加密index set Ns按照Ni发给DU。
当SC成功检索后，打包的密文就会发送给DU，

1. 然后DU验证由SC发送的file index 和由CS发送的 file index。如果两者相等，则说明CS没有发送错误的文件。
2. 再验证Mi是否等于M。如果相等，则CS没有修改密文数据
3. DU再用共享密钥K，解密密文，然后DU就可以得到解密的file set F’。

2.1.7 正确性

以下公式可以证明index和trapdoor成功配对

3. 分析

3.1 安全分析

3.1.1 公平性

每个操作都会消耗SC上的gas，提供数据的DO会得到相应的奖励，DU也需要为检索到的文件而支付gas。没有引入第三方就可以保证正确的结果。DU也设置了一个限制时间来确保交易的公平性，因为交易都需要在特定的时间内完成，如果超时了，用户就会停止查询服务。

3.1.2 可靠性

SC上的操作都是透明的，不能够被修改的。可以完全信任SC返回的数据是可靠的，并且他能有效的阻止服务器恶意的行为，区块链以及用户端的核查都可以确保结果的正确性。可以连接到区块链中查看任意节点的行为。

3.1.1 机密性

该方案理论上可以抵抗KGAs。
**定理：**如果对手在博弈1和博弈2中以可忽略的概率解决了相应的难题，那么我们的方案是可以抵抗KGA
也就是说，只要以下两个条件满足，方案就是安全的。

在博弈1中，如果DDH假设成立，则方案达到index不可区分。
在博弈2中，该方案能够保证在随机oracle模型下抵抗所选关键字攻击

1. 在博弈1中，DU和DO的共享密钥K是用对称密钥来加密的。CS必须要在公共传输过程中截取或者在生成共享密钥之前获取到DU或者DO的私钥。然而方案没有公共传输过程，所以CS只能在生成密钥之前获取到DU或DO的私钥来解开file fi的密文。因此，K是安全的。
2. 方案的安全性分析可以分为两个部分。第一个部分是keyword index的生成。第二部分是要查询的keyword set。

第一部分： 假设DU想要查询一个keyword set W’。CS要想猜到的话，就必须生一个有效的keyword index I，但是根据加密算法Enc (SP, pku, sko, F)，CS必须要先获取到DO的私钥sko，但是sko是私密的，CS只能猜测，猜中的概率为1/p。所以只要p足够大，CS就猜不中
第二部分： 假设CS直接猜测要查询的keyword set，假设一共有l个元素，关键字字典里有n个元素，那CS猜中的概率为
所以只要n足够大，猜中的概率几乎可以忽略。

3. 在博弈2中，给定一个有效的keyword index I ，那CS就需要生成一个匹配的有效的trapdoor。根据Trap(W′, pks, pko,sku)，生成一个trapdoor需要sku。CS猜中sku值的概率为1/p，所以这个概率几乎可以忽略。

所以只要关键字字典中的关键字数量n足够大，以及素数p的值取得足够大，该方案是可以抵抗内部KGAs的。

3.2 性能分析

3.2.1 理论分析

与其他两个方案进行对比。TM代表乘法操作，TH代表哈希操作，TE代表指数操作，TP代表对操作。G1、G2和Zp的元素长度定义为|G1|、|G2|、|Zp|。
下图表示本文方案与其他两个方案的功能对比。

各方案的计算开销如下图所示：
在Enc和Trapdoor阶段，三种发哪敢的计算量会随着加密关键字和被查询关键字的数量增加而增加，但是本文的方式是效率最高的。

各方案的通信开销如下图所示：
Enc阶段本文方案和[5]方案几乎一致，但比[37]要小。Trapdoor阶段，[37]方案随被查询的关键字数量增加而增加，而本文和[5]方案是恒定的。

3.2.2 实证分析

下图为Enc算法计算开销：
作者方案的斜率最小，随着关键字的增加，优势越来越明显。

下图为Trapdoor生成算法计算开销：
作者的方案指数运算和乘法运算的系数是常数，而哈希运算随着关键词的增加而线性增加。由图可知，哈希到Zp的时间比哈希到G的时间明显短了非常多。

下图表示Search算法的计算开销：
作者的方案与其他两个方案之间的效率差距并不明显。但是还是存在一些优势。

4. 结论

作者提出了一个区块链场景下的BPKEMS方案，它支持多关键词的安全检索、文件的动态更新和密码文本的验证。此外，作者的方案可以抵御KGAs。在效率方面，作者通过模拟实现了这个方案，并与其他方案[5, 37]进行了比较，结果表明作者方案更加实用。

[5]基于区块链的多关键字无证书可搜索公钥认证加密方案 2020
[37] Tcpedcks:时间控制的公钥加密与可委托的连接关键字搜索物联网 2019-11-20