基于合数阶双线性群的多用户陷门不可区分可搜索加密方案∗

梁哲华 佟国香

（上海理工大学光电信息与计算机工程学院 上海 200093）

1 引言

云存储服务的不断发展完善极大便利了人们的存储需求，传统的数据加密已无法满足云存储服务的效率需要，文献［1～2］对信息时代及云服务的安全需求进行了详尽的阐述。由于可搜索加密技术可以为云存储服务提供针对密文数据进行检索的方案，而成为近年来的研究热点。Song 等［3］首先提出一种用于检索加密数据文档的算法，将明文分割成多个关键词进行依次加密，但效率较低且容易暴露搜索信息。Boneh等［4］结合公钥密码提出一种PEKS 技术可以实现高效可搜索加密，该方案通过验证邮件密文和陷门是否一致，提高了检索效率。Waters 等［5］在此基础上提出带关键字的搜索公钥加密技术，并应用于检索加密日志。Golle等［6］进一步进行扩展，提出了查询加密数据连接关键字的方案。Fang 等［7］提出一种无需使用随机预言机而可以抗关键字猜测攻击的可搜索加密算法。此外，针对PEKS方案存在消息传递依赖于预先构造传输信道的不足，Baek等［8］针对使用公钥的可搜索加密去除传输过程中的信道，构造出一种方案SCF-PEKS，但该方案依赖于随机预言机，安全性假设过强。Emura 等［9］根据匿名基于身份加密（Identity-Based Encryption，IBE）机制划分密文结构，与SCF-PEKS 方案结合构造出更高效的无安全信道方案。徐磊等［10］构建了基于合数阶的PEKS 方案，由于其方案的提出是基于静态假设，而缺乏现实安全性。Li 等［11］在IBE 机制基础上提出了一种无安全信道的高效可搜索加密算法。Deng 等［12］设计出一种可抵抗外部关键字攻击的可搜索加密实现算法，具有良好的陷门尺寸。Emura 等［13］提出了一种基于隐向量加密、标签加密和一次性签名的多关键字SCF-PEKS通用构造方法。WU等［14］提出了一种无通道、无证书、可搜索的公钥认证加密方案，并证明了使用内部关键字情况下，该方案在增强的安全模型中可以有效抵抗猜测攻击。Deng 等［15］根据去除安全的消息传输通道的可搜索加密方案展开补充，建立了多用户注册机制方案，并满足抗选择关键字攻击安全，然而该方案不能满足陷门不可区分性，存在一定的安全缺陷。

本文针对Deng 等提出的多用户注册方案，在陷门设计方面进行了安全性分析，改进了陷门设计算法和验证算法，提出一种陷门不可区分的多用户注册可搜索加密方案，并基于判定性子群假设和DBDH 假设，证明了敌手攻击无法有效区分构造的陷门。实验结果表明，提出的改进方案效率高，陷门空间小。

2 预备知识

2.1 合数阶双线性群

将安全参数λ输入双线性群的生成算法G中，可以得到阶为N=p1p2p3的两个群G和GT，其中p1、p2、p3为互不相同的素数。设双线性映射为e:G×G→GT，其可以满足下列性质：

1）双线性：

∀g,ℎ ∊G,a,b∊ZN,e(ga,gb)=e(g,g)ab；

2）非退化性：

∃g∊G使得GT中e(g,g)有n阶；

3）可计算性：映射e:G×G→GT可以被有效计算。

假设在群G和GT上，以及与其相关的双线性映射e:G×G→GT在多项式时间内是可计算的，令Gp1，Gp2，Gp3分别表示G中阶分别是p1，p2，p3的子群，对于i≠j，则有e(ℎi,ℎj)为GT中的一个单位元，其中ℎi∊Gpi，ℎj∊Gpj。且该群中每一个子群Gp1，Gp2和Gp3两两之间正交。

2.2 判定性子群假设

构造一个群生成器G ，定义如下分布：

其中D为一个公共的元组，如果有敌手A在某一多项式时间内产生，且机率不限，则这一敌手能够辨别T0和T1的概率如式（1）所示。

式（1）中λ的相关性是可忽略的。

2.3 DBDH假设

以素数q 为阶，构造出两个循环群G1和G2，e:G1×G1→G2为其中的双线性映射。使用g 设置成群G1初始生成元，则有以下公式表示敌手区分e(g,g)abc和e(g,g)r的优势：

其中随机选取a,b,c,r∊Zp。

假如对任意概率多项式时间内敌手A其优势可忽略，则DBDH假设成立。

2.4 SCF-PEKS基本概念

SCF-PEKS 在PEKS 的基础上提出，弥补了PEKS 的安全性不足。主要包含三方参与者：发送者、服务器、接收者。发送者将关键词加密并发送给云服务器，接收者对于将要查询的目标关键词生成陷门并发送给服务器。服务器接收两方的信息对其进行匹配，执行搜索操作，将匹配的关联文档发送给接收者。在这一过程中，公私钥对由服务器保管，发送者在加密过程中同时用到服务器和接收者的公钥，接收者发送陷门的过程中不需要专用信道，可通过公开信道发送。服务器在收到陷门后，根据私钥进行检测和匹配。其模型定义如下。

定义1 不依赖可靠消息传递通道的公钥可搜索加密方案（SCF-PEKS）由下列子算法步骤构成：

1）Setup（λ）。输入可靠参数λ，构造出全局参数gp。

2）KeyGenS（gp）。将全局参数gp 作输入，生成用于服务器使用的公钥及私钥组合（pks，sks）。

3）KeyGenR（gp）。输入gp，输出接收者密钥对（pkR，skR）。

5）Trapdoor（gp，skR，w）。将全局参数gp，接收者私钥skR，要搜索的关键字w 作为输入，输出陷门Tw。

6）Test（gp，C，skS，Tw）。将gp，关键字密文C，陷门Tw，服务器私钥输入，服务器将根据自身私钥进行查找匹配。若存在对应值输出1，否则输出0。

3 可搜索加密方案分析

本节对文献［15］中以合数阶双线性对为理论基础，构造出的服务于信息登记用户公钥可搜索加密方案进行分析，考虑方案安全性与陷门相关性较强，故主要分析Trapdoor算法。

4 陷门不可区分可搜索加密方案

4.1 方案设计

本文方案具体构造如下：

1）GlobalSetup（λ）。以λ为 安 全 参 数，(N,G,GT,e)为双线性映射的参数，N=p1p2p3为G和GT的阶，且g 为G 的生成元。e 是G×G→GT的双线性映射。选取一个抗碰撞的哈希函数H:{0,1}*→ZN。设关键词空间为KSw={0,1}*，可得全局参数为GP=｛N，G，GT，e，H，KSw｝。

2）KeyGenKGC（GP）。用户注册中心生成公私钥对，首先随机选取β=ZN，g1,u∊Gp1，计算X=e(g1,g1)β，Y=uβ，得到公私钥分别为公钥pkK={g1,X,Y,u}，私钥skK=β。

由上式（4）、（5）证明可知，服务器通过自身私钥可以计算出t 值，从而得以验证密文和陷门是否相互匹配。通过前面的证明步骤可以发现，使用优化的算法步骤加强了基础方案的计算过程，通过构造安全高效的算法幂次，能够让关键字陷门在被受到外部敌手尝试破解的环境下，仍难以获取陷门信息，无法对陷门进行区分，攻击者破解幂次值后方可计算关键字，而这一数值需得知服务器私钥才能获取，从而保证了在多用户注册情况下密文检索的安全性。

4.2 安全性证明

本节在抗选择关键字攻击等安全性依赖于判定性子群假设和DBDH 假设前提下［15］，对关键字陷门不可区分性进行证明。

定义2 选择关键字攻击（indistinguishability of SCF-PEKS against chosen keyword attack，IND-SCF-CKA）游戏。

以λ为安全参数，建立起关于敌手A 和模拟者B之间的攻击游戏模型。

Game1：假设A为内部攻击者（服务器）。

1）Setup：运行初始化算法GlobalSetup（λ），生成系统参数GP，随后运行三个密钥生成算法，得到用户密钥中心、计算中心、接受者这三种角色的密钥组合（pkK，skK），（pkS，skS）以及skR，随后模拟者B把（pkS，skS）和pkK传输给攻击者敌手A。

2）Queryphase1：对任意关键词w，敌手A 向B询问关键字陷门，B 运行陷门生成算法Tw=Trapdoor（GP，skR，w），并将结果返回给敌手A。

3）Challenge：A 向B 发 送 挑 战 关 键 词 对（w0,w1），其中w0,w1都不能出现在Queryphase1中，B 随机选取b∊(0,1)，计算C*=SCF-PEKS（GP，pkS，pkK，wb），并将其作为挑战密文发送给A。

4）Queryphase2：敌手A继续对关键词进行陷门询问，但不能选择w0和w1。

5）Guess：A 将猜测b′输出，若b′=b，则敌手A获得胜利，否则A失败。

A攻破Game1的优势为

Game2：假设A为外部攻击者，则模拟攻击游戏如下。

1）Setup：给定安全参数λ，运行GlobalSetup（λ）算法生成系统参数gp，随后运行三个密钥生成算法，得到用户密钥中心、服务器、接受者的公私钥对（pkK，skK），（pkS，skS）和skR，模拟者B 将pkS和pkK发送给敌手A。

2）Queryphase1：A 自适应的选择接收者的密钥x∊Z*N，在密钥生成中心执行用户密钥生成操作，得到skR。

3）Challenge：敌手A 发送关键词对（w0,w1），B随机选取b∊(0,1)，计算C* =SCF-PEKS（GP，pkS，pkK，wb），并将其作为挑战密文发送给A。

4）Guess：A 将猜测b′输出，若b′=b，则敌手A获得胜利，否则A失败。

A攻破Game2的优势为

假设1 敌手的随机询问wi(i=1,2,…,q)每次都是不同的，且给定的R3可以完美的将陷门随机化。

假设2 密钥注册中心不能成为敌手，其必是安全且忠诚的。

引理1 若DBDH为困难性的理论假设，则攻击者敌手A 无论处于何种概率，当其使用的算法时间复杂度处于多项式级别，那么其可以辨别陷门内关键词的攻击优势可视为0。

敌手和挑战者的攻击游戏如下：

4）Guess：敌手A 在获取陷门后进行猜测，输出猜 测b′ 。 若b′=b，则 有t=H(e(T1,Q)α)=H(e(g1,g1)abc)，T=e(g1,g1)abc，则T*w是正确的结果，返回“Yes”；否则T为GT中的任意组成成员，返回“No”。

若攻击敌手A 可以辨别出关键词陷门，则挑战者B 能够破解出DBDH 假设。综合以上证明，本算法方案中针对不同关键词构造的陷门对外部敌手不可区分，针对关键字能够有效防御外部发起的猜测攻击。同样的，本方案可抗选择关键字攻击，满足IND-SCF-CKA安全。

4.3 性能分析

接下来列举出一些经典的可搜索加密方案，在各个方案之间，相互比较陷门尺寸大小、算法复杂度和陷门是否可以区分等，其中以 |G|、|GT|、|ZP|各指代G、GT、ZP中组成成员的空间尺寸，P指代双线性对相关的运算，E 代表为模幂情况下的运算，H 指代hash 函数类型的计算，S-M 表示标准模型，表1为各方案对比结果。

表1 各方案对比数据表

从表1 可以看出，本文和文献［11］、［15］方案陷门尺寸差距较小，密文尺寸接近，表现较为良好，而文献［11］、［15］不满足陷门不可区分性，虽然文献［7］可满足，但在验证复杂度、密文结果获取的复杂性程度、陷门以及密文的空间大小性能上都不如本文方案。综合比较，本文中所提出的加密方案在陷门和验证中的算法复杂度更优、陷门和密文安全性高，尺寸良好，在满足多用户注册的同时，提高了可搜索加密方案的安全可靠程度。

5 结语

1）对于合数阶的双线性群理论基础上提出的可注册用户公钥可搜索加密方案进行了陷门安全性研究，改进了现有方案防御外部敌手使用选择关键词攻击时的不足。

2）提出了合数阶双线性群理论基础上，改进安全性的多用户的可搜索加密方案。方案性能对比表明，其陷门、密文尺寸良好、算法复杂度低、可多用户使用。在无需安全信道传输的基础上可保证密文关键字的陷门不可区分性，可抗选择关键字攻击。

3）后续将在本文的基础上扩展应用范围，研究多关键字情况下的无安全信道可搜索加密方案。