云边端环境下可验证的轻量化可搜索加密.pdf

第 41 卷 第 4 期2023 年 8 月石河子大学学报(自然科学版)Journal of Shihezi University(Natural Science)Vol.41 No.4Aug.2023收稿日期:2023-02-23 基金项目:河北省重点研发计划项目(22340701D),河北省自然科学基金项目(F2022201005)作者简介:杜瑞忠(1975)男,教授,从事可信计算与信息安全方向的研究,e-mail:durz 。DOI:10.13880/ki.65-1174/n.2023.23.024文章编号:1007-7383(2023)04-0507-12云边端环境下可验证的轻量化可搜索加密杜瑞忠1,2,蒋浩宇1,2,李明月1,2(1 河北大学网络空间安全与计算机学院,河北 保定 071002;2 河北省高可信信息系统重点实验室,河北 保定 071002)摘要:传统公钥可搜索加密方案中,大多采用分布式双陷门公钥密码系统分发密钥,通过子集决策机制实现密文检索,但是系统之间通信开销较大。本文提出了 1 种新的可验证的云边端环境下的公钥可搜索加密方案 VSE-EPOMFC(Verifiable Searchable Encryption-Efficient Privacy-preserving Outsourced calculation framework with Multiple keys Filtering Computing,VSE-EPOMFC)。方案 VSE-EPOMFC 设计了 1 种基于部分同态加密的能在密文下计算的过滤算法筛选无意义任务来降低通信开销。针对客户端设备资源受限的缺点,采用阈值签名机制,将客户端签名、验证的任务委托给边缘结点,轻量化了客户端的验证开销与存储开销。仿真实验结果表明,方案 VSE-EPOMFC 在任务集匹配度 II 的情况下通信时间节省了 25.46%,在任务集匹配度 I 的情况下通信时间节省了 62.21%。关键词:公钥可搜索加密;可验证;轻量化;云边端中图分类号:TP309.7文献标志码:AVerifiable lightweight searchable encryption in cloud edge environmentDU Ruizhong1,2,JIANG Haoyu1,2,LI Mingyue1,2(1 School of Cyber Security and Computer,Hebei University,Baoding,Hebei 071002,China;2 Hebei Key Laboratory of Highly Trusted Information System,Baoding,Hebei 071002,China)Abstract:In the traditional public key searchable encryption schemes,the distributed two-trapdoor public key cryptosystem is mostly used to distribute the key,and the ciphertext retrieval is realized through the subset decision mechanism,but the communication over-head between systems is relatively large.This paper proposes a new verifiable public key searchable encryption scheme on cloud-edge-end environment(Verifiable Searchable Encryption Efficient Privacy-preserving Outsourced calculation framework with Multiple keys Filtering Computing,VSE-EPOMFC).Scheme VSE-EPOMFC designs a filtering algorithm based on partial homomorphic encryption that can be calculated under ciphertext to filter meaningless tasks to reduce communication overhead.In view of the limitation of client device resources,the threshold signature mechanism is used to entrust the task of client signature and verification to the edge node,which lightens the verification and storage overhead of the client.The simulation results show that the communication time of VSE-EPOMFC is saved by 25.46%in the case of task set matching degree II and 62.21%in the case of task set matching degree I.Key words:PEKS;verifiable;lightweight;cloud-edge-end environment近些年,随着物联网和大数据的迅速发展,据GSMA 预测,2025 年全球物联网终端连接数量将达到 250 亿,物联网设备数量将爆发式增长。由于物联网设备计算能力较弱,只能处理轻量级的任务,并且需要将复杂任务外包,因此逐渐形成了云边端模型。在云边端模型中,各方实体都是半可信的,边缘节点能够在数据所有者不知道的情况下窃取他们的信息并执行恶意操作。为了保护数据隐私,数据持有人需要在敏感数据外包之前对其加密。一种方法是用户可以下载全部数据并解密,但是这种方法下载了大量不必要的数据,显然不具备可用性2。为了解决上述问题,提出了云边端环境下的可搜索加密方案,轻量化客户端的存储与计算开销,解决了客户端设备资源受限的问题。另一方面,由于半可信的云端可能返回不正确的搜索结果,设计基于可验证的可搜 索加密方案 是近 年 来 的 另 一 个目标。本文提出了可验证的轻量化 VSE-EPOMFC 方508 石河子大学学报(自然科学版)第 41 卷案,设计了 1 种过滤算法来降低系统开销。贡献主要体现在以下 3 个方面:(1)引入了边缘结点代替客户端执行计算签名及验证的任务,轻量化了客户端验证与存储开销。边缘结点解决了客户端计算、存储资源匮乏的问题。(2)利用分布式双陷门公钥密码系统(Distrib-uted Two-Trapdoor Public-Key Cryptosystem,DT-PKC)、子集决策机制、部分同态加密 3 种技术,本研究设计了 1 种搜索前过滤搜索任务的算法,整个过程在密文下计算,保障用户隐私,能在任务集有较多的无意义任务的情况下,减少系统的通信开销。(3)仿真实验评估了方案 VSE-EPOMFC 与 SE-EPOM 在搜索时的通信开销,与方案 CP-ABKS 比较了客户端的验证开销。实验结果 表明方案 VSE-EPOMFC 在搜索性能与验证性能方面都有一定程度的提升。对称可搜索加密(Symmetric Searchable Encryp-tion,SSE)计算速度快,但是存在严重的密钥管理问题。为了解决以上问题,Boneh 等3首先提出了基于公钥的可搜索加密方案(Public Key Encryption with Keyword Search,PEKS),减少了多用户场景下的密钥数量。为了保证搜索结果的正确性,Zhang等4提出了 1 种可验证的无证书的公钥可搜索加密方案,解 决 了 密 钥 托 管 和 证 书 管 理 问 题。Liu等5设计了 1 种在多用户环境下的可验证的动态SSE 方案,云服务器使用 RSA 累加器返回验证信息给用户。文献4-5方案需要用户或者数据持有人执行一定的验证操作,对于多用户下资源受限的客户端设备是 1 个挑战。Chen 等6在车载社交网络的背景下,使用智能合约代替云服务器进行搜索和验证,降低了客户端的验证开销。从安全角度出发,Du 等7通过引入区块链实现了数据持有人与用户之间的双向认证,同时满足前向和后向安全。Song等8通过利用重加密密码系统和索引洗牌协议保护搜索模式和访问模式。为了降低客户端的压力,Wang 等9提出了 1 种基于工业物联网环境下的轻量级 PEKS 方案,将复杂的任务委托给边缘结点,消除了大部分方案由于双线性配对运算带来的沉重的计算开销。He 等10提出了 1 种新颖的鱼骨链结构,保证了客户端的存储开销与关键字数量无关。PEKS 面临 KGA(Keyword Guess Attack)这一固有问题,主要原因是关键字空间远远小于密文空间,在实际搜索过程中,恶意用户通常会选择一些使用频率较高的热词进行搜索。Chen 等11提出了 1 种新的服务器辅助的 PEKS 方案 SA-PEKS。使用辅助的服务器作为中介,数据持有人和用户在生成可搜索密文和搜索陷门之前必须向关键字服务器(Key-word Server,KS)验证身份并运行交互协议才能返回二次处理的可搜索密文、陷门。通过这种方法,将可搜索密文、陷门的生成过程变成了 1 种在线的方式,从而防止了恶意的内部服务器的攻击。Chen 等12紧接着提出了 1 种双服务器测试的 DS-PEKS 方案,与前者设计思路类似,使用前端服务器预处理并发送状态信息、密文,后端服务器产生最终的陷门、可搜索密文并测试。2019 年,Hwang 等13提出了基于ElGamal 密码系统的无通道安全 PEKS 方案,同时防止了内部、外部的攻击。文献14 中,利用 2 个非共谋的服务器抵抗内部 KGA,免双线性对运算的结构轻量化了客户端的开销。Huang 等15构建了 1 个具有多关键字搜索的PEKS 方案 PE-MKS,但是没有支持恒定大小的搜索陷门、可搜索密文,它们的大小与关键字数量呈线性关系。Wu 等16提出了 1 种多用户环境下基于同态加密的可验证的 PEKS 方案。对于现有的公钥可搜索加密方案,构建主要依赖于双线性配对。但是,PEKS 在客户端的计算较为复杂17。因此,常见的设计轻量级 PEKS 方案的思路就是用某些操作替换昂贵的双线性配对。我们还可以像 Liu 等18提出的方案一样,设计 1 种在线、离线加密,将完整的过程划分成 2 部分,离线部分可以预先计算,从而减少了复杂的客户端加密开销。2020 年,Liu 等19提出了在分布式系统中执行搜索的多关键字 PEKS 方案,攻击者想要执行 KGA 需要获取多个服务器的密钥,因此方案 SE-EPOM 成功抵抗了来自内部、外部攻击者的攻击。但是该方案在半可信云服务器环境下构建,缺乏对搜索结果的验证。此外,还存在系统之间通信开销过大的问题。Zhang 等20提出了 1 种双向的公钥可搜索加密方案。文献21-22构建了基于密文策略的可搜索加密方案,提供了细粒度的访问控制,在文献23 中,客户端需要计算额外的验证过程,对于资源受限的设备是 1 个很大的挑战。针对以上问题,本文提出了云边端环境下可验证的轻量化可搜索加密方案。1 资料与方法1.1预备知识1.1.1DT-PKC分布式双陷门公钥密码系统(DT-PKC)可以将第 4 期杜瑞忠,等:云边端环境下可验证的轻量化可搜索加密509 1 个强私钥 SK=分成 2 部分,使得方案不仅支持弱私钥 ski解密,还可以通过分解强私钥 SKi=i进行分布式解密,本文工作主要用到以下算法24:(1)(SK,N,g,ski,pki)KeyGen(k)。输入安全参数 k,输出强私钥 SK=,N=pq,g=-a2N,以及每一部分实体对应的密钥对 ski,pki。(2)mpki Enc(m,pki)。输入消息 m 和公钥 pki,输出密文 mpki。(3)m WDec(mpki,ski)。mpki可以通过解密算法使用弱私钥 ski解密。(4)(SK1,SK2)SkeyS(SK)。使用中国剩余定理将强私钥 SK=分成两部分 SK1=1,SK2=2,递归的执行算法输出更多分解密钥。(5)CT(1)i PSDec1(SK1,mpki)。输入密文mpki和部分强私钥 SK1,运行部分解密算法输出部分解密密文 CT(1)i。(6)m PSDec2(SK2,CT(1)i)。输入部分解密密文 CT(1)i和部分强私钥 SK2,运行部分解密算法输出明文消息 m。(7)Ciphertext Refresh(mpki)。输入密文mpki,输出明文消息 m 的另一个密文。1.1.2跨域安全计算协议DT-PKC 仅支持处在同一公钥下的同态加密,但是在实际分布式搜索时,为了保护用户、数据持有人隐私,需要对使用不同公钥的密文做部分同态加密,给出公钥 pkMDU,pkMDO密文m1pkMDU,m2pkMDO,满足以下协议:(1)m1m2pkMDUSMD(m1pkMDU,m2pkMDO)。安全位乘法协议给出密文m1pkMDU,m2pkMDO,输出m1m2pkMDU。(2)m1+m2pkMDUSAD(m1pkMDU,m2pkMDO)。安全位加法协议给出密文m1pkMDU,m2pkMDO,输出m1+m2pkMDU。(3)TimpkMDO,Ti-1mpkMDO,T1mpkMDO SBD(TiT1mpkMDO)。安全位分解协议25给出密文二进制形式TiT1mpkMDO,输出对单个二进制位的密文TimpkMDO,Ti-1mpkMDO,T1mpkMDO。同态运算性质:E(x+y)E(x)E(y)modN2,E(xy)E(x)ymodN2。1.1.3子集决策机制本文采用了子集决策机制19,可以用来判断某个子集是否属于另一个集合。它的设计思路是将关键字集合之间的关系通过二进制串来表示,类似邻接矩阵,从而减少了复杂的加密运算开销。缺点是需要存储一个较大的通用关键字集合,且不支持动态更新。假设有 2 个二进制串 W1=111 001 和 W2=100 001,n 表示二进制串长度,需要判断 2 个二进制串的包含关系,可以执行以下运算:(1)取二进制串 W1=111 001,计算它的反码W1=000 110;(2)当 j n 时,执行:按位加法得到 cj=-W1+W2;用 2 减去 cj得到 dj;对 dj进行累乘得到 R;循环while 结束;(3)如果 R=0,W2 W1,否则,W2 W1。1.2模型构建1.2.1系统模型在方案 VSE-EPOMFC 中,系统由 6 部分实体组成,包括密钥生成中心 KGC(Key Generate Center,KGC)、多 数 据 持 有 人 MDO(Multi Data Owners,MDO)、边缘结点 EN(Edge Node,EN)、多用户 MDU(Multi Data Users,MDU)、云服务器 CP(Cloud Plat-form,CP)和提供辅助计算服务的 CSP(Cloud Serv-ice Provider,CSP)。图 1 描述了系统模型,例如,企业将敏感数据外包给云服务器 CP,方便授权的公司员工能够随时随地访问这些数据。在外包存储到云服务器之前,应当选择一部分结点作为管理人 ENM(Edge Node Manger,ENM),为上传的密文数据签名,避免了以往方案中必须全部数据持有人同时在线签名的限制。(1)密钥生成中心 KGC 负责产生并分发公共参数给多用户 MDU 和多数据持有人 MDO,分发部强私钥给 CP 和 CSP(实际生活中可以由政府等公信力强的机构担任),为边缘结点管理人 ENM 产生密钥对。(2)多用户 MDU 和多数据持有人 MDO 依靠从KGC 产生的公共参数产生属于自己的密钥对,使用各自的公钥产生可搜索密文 SC 和陷门 TD,使用对称密钥加密文件,分别将加密文档、可搜索密文和搜索陷门上传至边缘结点。(3)边缘结点主要由两部分组成:代理边缘结点 ENM 和普通边缘结点 EN。签名由 EN 和 ENM完成,ENM 将多个边缘结点产生的签名进行整合,510 石河子大学学报(自然科学版)第 41 卷缩短了签名长度。边缘结点将加密文档、可搜索密文和搜索陷门以及签名上传至 CP。(4)CP 将加密文档、可搜索密文、搜索陷门以及签名在 CSP 备份。CP 和 CSP 交互式的执行子集决策机制、跨域安全计算协议,完成过滤和搜索,计算一个加密值。(5)CP 将加密值交给 MDU。由 MDU 判断对应的加密文档是否属于最终的搜索结果。MDU 向 CP申请获取满足条件的加密文档。(6)CSP 收到 MDU 获取加密文档的请求之后,通过与 ENM 交互对相关加密文档进行结果验证,删除其中被半可信云服务器增加的恶意文档。CSP 返回经过搜索和验证的加密文档给 MDU,MDU 通过以上步骤获取与感兴趣关键字相关结果文档。注:与为同一步骤。图 1系统模型1.2.2威胁模型在方案 VSE-EPOMFC 中,密钥生成中心 KGC被假设为是完全可信的,诚实的遵循协议去产生公共参数或者分发密钥到各个实体。CP 和 CSP 以及EN 被假设为半可信的,即会诚实的遵循协议完成工作,但是会尝试从加密的信息中推断敏感信息。CP 和 CSP 在过滤和搜索 2 个阶段被假设为非共谋的 2 个实体。多用户 MDU 和多数据持有人 MDO 同样是半可信的实体,会诚实的遵循协议完成工作。但是MDO 可能会窃听其他实体之间的通信,或者尝试了解陷门信息。MDU 可能会尝试了解可搜索密文的信息或者由其他 MDU 上传的陷门信息。1.2.3安全性定义Kamara 等26表示处在多方协议计算之间的共谋攻击是 1 种有用信息的交换。这种有用信息指的是可信实体在整个协议计算过程中未规定过的输入信息。只要多方参与者(敌手)能了解到这部分信息,那么共谋攻击成立。方案 SE-EPOMFC 假设处在非共谋敌手攻击模型下。安全多方计算的安全性通过 1 种理想/现实世界模型来定义的。在当前模型中,必须首先设置集合 P=(PMDO,PMDU,PCSP,PCP)表示各方执行协议的实体对象,各方实体之间只能交互非协议信息。这里的各方实体主要包含 4 部分,包括 MDO,MDU,还有负责过滤和搜索的 CP 和 CSP。相应的会有敌手A=(AMDO,AMDU,ACSP,ACP)负责攻击各个实体。在现实世界中,执行各种协议发生在各个实体 P=(PMDO,PMDU,PCSP,PCP)之间,我们让 H P表示实体中完全可信的实体集合,让 J P-H 表示实体中受到非共谋敌手攻击并被破坏的实体集合。再执行过程的初始阶段,P=(PMDO,PMDU,PCSP,PCP)中的实体 PMDO或 PMDU会收到输入 xMDO和 xi,以及辅助输入 ZMDO和 Zi,CP 和 CSP 仅仅收到辅助输入 ZCP和 ZCSP。当 P 是可信实体时,P H,outp是实体 Pi的输出。当 P 属于被破坏的实体时,P I,outp输出产生的是 P 执行协议之后产生的新的输出(被破坏的实体可能产生攻击者伪造的输出)。第 4 期杜瑞忠,等:云边端环境下可验证的轻量化可搜索加密511 某一部分实体 Pi在现实世界中多方实体 P=(PMDO,PMDU,PCSP,PCP)之 间,同 时 存 在 敌 手 A=(AMDO,AMDU,ACSP,ACP)的情况下,执行协议 所产生的结果定义为:IDEALPi,z(k,x)=outp:P I outpi。(1)在理想世界中,所有的实体都会与完全可信的评估实体交互,在模拟器 S=(SMDO,SMDU,SCSP,SCP)存在的情况下产生评估实体,我们用 表示完全可信的评估实体。挑战者会发送 xi给。如果 xi是,那么 返回。否则,返回(x1,xi)给挑战者。当 P 是可信实体时,P H,outp是完全可信实体 返回给实体 Pi的输出。当 P 是属于被破坏的实体时,P I,outp输出的是实体 P 的新输出。某一部分实体 Pi在理想世界中多方实体 P=(PMDO,PMDU,PCSP,PCP)之间,同时存在模拟敌手 S=(SMDO,SMDU,SCSP,SCP)的情况下,执行协议 所产生的结果定义为:REALPi,z(k,x)=outp:P I outpi。(2)假如协议 在现实世界中模拟了对理想世界的评估,那么它在非共谋半可信的敌手攻击下是安全的。定义 1 让 表示确定性 n 方函数,表示 n 方协议。令 H=,这样每一部分实体 P=(PMDO,PMDU,PCSP,PCP)都是半可信且非共谋的。如果在概率多项式时间内,存在一个模拟 S=(SMDO,SMDU,SCSP,SCP),使得对于所有的半可信且非共谋的敌手A=(AMDO,AMDU,ACSP,ACP),其中 x 0,2-1,z 0,2-1,P P,有如下公式成立:REALPi,z(k,x)kN IDEALPi,z(k,x)kN。(3)那么协议(P)能被安全计算。同时,基于这些协议构建的方案能被安全实现。密文不可区分性指的是上传到 CP 和 CSP 的加密的可搜索密文不会泄露隐藏的关键字信息。同理,陷门隐私与密文不可区分性具有相似的概念,指的是产生的搜索陷门不会泄露隐藏的关键字信息。不可区分性游戏模型可以这样定义:敌手选择 2 个不同的关键字集发送给挑战者,挑战者随机选择一个计算可搜索密文并返回给敌手,此时,敌手尝试猜测哪一个关键字集与挑战者返回的密文对应。假如不存在敌手 A 能在概率多项式时间内从可搜索密文和搜索陷门中推断出敏感的关键字信息,则关键字隐私能够得到保障。定义的安全隐私游戏如下:(1)初始化。通过输入指定的 k,挑战者运行KeyGen 算法产生 SKCP,SKCSP,PKMDO,PKMDU,SKMDO,将 SKCP,PKMDO,PKMDU发送给敌手 A,私钥 SKCSP,SKMDO自己保留。(2)挑战。敌手 A 选择了两对不同的关键字集合W0和 W1,发送给挑战者 C。挑战者从 r 0,1 中随机选择一个值,运行算法 Searchcp 产生可搜索密文SC,发送给敌手 A。(3)输出。敌手 A 做出猜测 r=0 或 1,当 r=r时,敌手 A 赢得游戏胜利。定义 2 对于任何在概率多项式时间内的敌手A,假如优势AdvSCPVSE-EPOMFC,()=|PrAb=0wins-PrAb=1wins|,(4)是可以忽略的。那么方案 VSE-EPOMFC 在上面的游戏中满足可搜索密文的隐私。对于陷门关键字信息的隐私性研究,与前面的密文隐私安全性相似。(1)初始化。通过输入指定的 k,挑战者运行KeyGen 算法产生 SKCP,SKCSP,PKMDO,PKMDU,SKMDO,将 SKCP,PKMDO,PKMDU发送给敌手 A,私钥 SKCSP,SKMDO自己保留。(2)挑战。敌手 A 选择了两对不同的关键字集合 W0和 W1,发送给挑战者 C。挑战者从 r 0,1中随机选择一个值,运行算法 Trapdoor 产生搜索陷门 TD,发送给敌手 A。(3)查询。根据过滤和搜索算法,我们让挑战者 C 扮演 CSP 与敌手 A 进行交互。(4)输出。敌手 A 做出猜测 r=0 或 1,当 r=r时,敌手 A 赢得游戏胜利。定义 3 对于任何在概率多项式时间内的敌手A,假如优势AdvTDPVSE-EPOMFC,()=|PrAb=0wins-PrAb=1wins|,(5)是可以忽略的。那么方案 VSE-EPOMFC 在上面的游戏中满足搜索陷门的隐私。1.3VSE-EPOMFC本节从验证轻量化、任务过滤 2 个小节简单介绍了创新之处,首先将客户端签名和验证的任务委托给边缘结点降低客户端的计算和存储开销,然后在搜索之前对任务进行过滤,筛选一部分不匹配的任务,降低系统之间的通信开销。最后,具体方案构512 石河子大学学报(自然科学版)第 41 卷造描述了算法细节。在表 1 中定义了论文使用的符号。表 1参数符号含义W通用关键字集Wid某个文档包含的关键字列表Wt用户上传的关键字集WT数据持有人上传的关键字集Did明文文档SC可搜索密文TD搜索陷门T,t可搜索密文、陷门的十进制形式Ti,ti可搜索密文、陷门的二进制形式ENi边缘结点小组成员L()比特串长度阈值pki使用公钥加密的关键词密文TipkMDO使用数据持有人公钥加密的二进制串SUM=2-1通用关键字集的十进制整数1.3.1验证轻量化SE-EPOM 通过引入通用关键字集 W,将多关键字用二进制串形式加密,保证可搜索密文和陷门的大小与关键字数量无关。但是考虑到恶意的多数据持有人 MDO、云服务器 CP、CSP 可能上传错误的密文或者返回错误的搜索结果,通常是由 MDO 对密文进行签名,MDU 负责对搜索结果验签,此时客户端将承担计算密文、签名、验证签名的任务,对于资源受限的客户端设备,显然是不可取的。因此,引入了边缘结点代替 MDO 对密文执行签名,代替 MDU验证签名,轻量化客户端的验证开销。使用 1 种阈值签名机制,先由边缘结点 EN1,EN2,ENi代替阈值数量的 MDO 对密文分别签名,设置 1 个管理人ENM,根据多个签名为每个文档生成唯一的阈值签名,缩短了签名长度。1.3.2任务过滤由于实际搜索过程中,需要用到大量的交互式算法,通信较为复杂,为了解决通信过程中由于大量不匹配的任务产生的不必要的通信开销的问题,在子集决策机制的基础上设计了 1 个过滤算法用于过滤完全不匹配的任务。方案在搜索过程中用到了 SE-EPOM 中的子集决策机制,在密文的基础上使用 CP 和 CSP 进行搜索。但是,当任务集中存在大量完全不匹配的加密二进制串时,方案 SE-EPOM 会产生多余的通信开销。VSE-EPOMFC 在搜索过程中增加了 1 个过滤算法,负 责 筛 选 完 全 不 匹 配 的 二 进 制 串,如 图 2所示。图 2过滤算法流程只有当 2 个二进制串完全不匹配时,过滤算法生效。对密文进行计算,只能使用安全位加法和安全位乘法运算。为了便于理解,本文使用明文下的例子进行说明,实际情况下则需要在加密的二进制串上运行各种复杂的通信协议。过滤算法用于判断两个二进制串是否完全不匹配。首先当每个对应的加密位都不相同时,运用安全位乘法协议必定产生全为 0 的加密二进制串,接着使用安全位加法协议,对所有位累加,最后将结果交给多用户 MDU 解密,如果结果为零表示 2 个二进制串必定完全不匹配,将其从任务集中删除。1.3.3具体方案构造(1)初 始 化。(SK,SK1,SK2,PP,H0,H1)Setup(k)。KGC 首先执行 KeyGen 得到强私钥 SK=,N=pq,s=-a2N(其中 a ZN2是随机选取的)。然后KGC 执行 SKeys 对强私钥 进行拆分,得到 2 个部分强私钥 SK1=1,SK2=2。G 和 GT是 2 个大素数p 阶循环群,g 是循环群 G 的生成元,e:G G GT是 1 个双线性映射,选择双线性对参数 BP=G,GT,e,p,g,选择 2 个抗碰撞哈希函数,H0:0,1 Zp,H1:0,1 G。最后,KGC 将产生的参数PP=N,s,BP,发送给多用户 MDU 和多数据持有人 MDO。将部分强私钥 SK1=1,SK2=2分发给CP 和 CSP,强私钥 秘密保存。(2)生成密钥。(pkMDU,skMDU,pkMDO,skMDO,pkm,skm)KeyGen(SK,SK1,SK2,PP,ENi,ENM)。MDU 和 MDO 拿到公共参数 PP=(N,s,BP)后执行 KeyGen 产生属于自己的密钥对 pkMDU,skMDU,第 4 期杜瑞忠,等:云边端环境下可验证的轻量化可搜索加密513 pkMDO,skMDO。将 ENM 管理的边缘结点小组设 为EN=EN1,EN2,ENi,KGC 会为 ENM 产生密钥对(pkm=gb,skm=b),b Zp,管理人会输出 1 个 -1次的多项式 f(x)=c-1x-1+c1x+c0,这里 cjZp(j 1,-1),c0=b,i 2-1。管理人选择i 个满足多项式的元素对(x1,y1),(x2,y2),(xi,yi),y1,yi 值发送给 剩余 边 缘 结 点 EN1,EN2,ENi用于签名。(3)加密并签名。(Cm,SCm,)Searchcp(Did,W,WT,pkMDO,pkm)。执行表 2 算法 1,分别使用 AES 和 DT-PKC 计算加密文档和可搜索密文,然后计算至少阈值数量的签名,管理人 ENM 将全部的签名整合成唯一阈值签名,从而缩短了签名长度。表 2加密并签名算法 1加密并签名输入:Did,W,WT,pkMDO,skm=b输出:加密文档、签名 1:MDO 对 m 个文档计算可搜索密文:SCm=(T1pkMDO,T2pkMDO,TmpkMDO)2:MDO 对 m 个文档使用对称密钥 K GT计算:C1,Cm3:为了验证搜索结果,MDO 委托 EN1,EN2,ENi计算签名:j=H1(id)gH0(Cm)yj,j 1,i4:ENM 将全部的签名整合成唯一阈值签名:=k=1kLk(0)=H1(id)gH0(Cm)v,Lk(0)=1l,lk-xlxk-xl注:上标 m 表示 m 组密文,本文取第 m 组密文进行计算。(4)产 生 陷 门。TDm Trapdoor(W,Wt,pkMDU)。MDU 对 Wt使用 Enc 加密二进制表示的关键字,产生搜索陷门,对于 m 个可搜索密文,产生 m 个搜索陷门 TDm=(t1pkMDU,t2pkMDU,tmpkMDU)。(5)过滤。(01)Filtering(SCm,TDm,pkMDU,pkMDO,SK1,SK2)。如表 3 算法 2 所示,最后得到了 2 个所有位都被加密的二进制串 SCm,TDm。在这 2 组子串中,使用 SMD 协议相乘得到ftimpkMDU,使用 SAD 协议对ftimpkMDU中的每一位进行累加,结果记为ftmpkMDU,交给用户使用弱私钥 skMDU解密得到 fmt,若 fmt=0,则用户返回“需要过滤”,否则返回“不需要过滤”。表 3密文过滤算法 2密文过滤输入:SCm=TmpkMDO,TDm=tmpkMDU,pkMDU,pkMDO,SK1=1,SK2=2 输出:“需要过滤”或“不需要过滤”1:CP 计算-TmpkMDO=SUMpkMDO(TmpkMDO)N-1,SUM=2-1 2:CP 与 CSP 运行 SBD 协议,输出第 m 组密文:-SCm=-TimpkMDO,-Ti-1mpkMDO,-T1mpkMDOTDm=timpkMDU,ti-1mpkMDU,t1mpkMDU3:CP 与 CSP 交互运行 SBD 协议:SBD(TmpkMDO)(SCm=TimpkMDO,Ti-1mpkMDO,T1mpkMDO)4:CP 与 CSP 运行 SMD、SAD 协议:5:初始化 sum=0pkMDU 6:whilei ndo SMD(TimpkMDO,timpkMDU)ftimpkMDU sum=SAD(ftimpkMDU,sum)7:endwhile 8:用户对 sum 使用弱私钥 skMDO解密:D(sum)=fmt9:iffmt=0then return“需要过滤”10:else return“不需要过滤”11:endif注:上标 m 表示第 m 组密文的过滤结果。(6)测试。(01)Test(-SCm,TDm,pkMDU,pkMDO,SK1,SK2)。执行 搜 索 需 要 获 取 公 钥 pkMDU,pkMDO,CP 和CSP 提供部分强私钥 SK1,SK2以及经过过滤的可搜索密文 SCm和陷门 TDm,CP 和 CSP 执行表 4 算法3,用户最终获得 fmpkMDU后使用弱私钥 skMDU解密。若结果输出 0,表示陷门与可搜索密文不匹配;若结果输出 1,表示陷门与可搜索密文匹配,用户向 CP 申请获取相关的文档 Cm。(7)结果验证。(Cm)Verfiy(Cm,PP)。用 表示搜索结果 Cm的数量,每一个结果文档 C都会关联一个 id(1,)。首先,ENM随机选择 e Zp,发送,e 给 CSP,CSP 计算:v=1eH0(C),=1()e,=H1(id)gH0(C)b。(6)CSP 发送证明信息给 ENM。如果满足以下等514 石河子大学学报(自然科学版)第 41 卷式,那么搜索结果经过验证是正确的:e(,g)=e(=1H1(id)egv,pkm)。(7)用户收到经过验证的结果文档后,使用对称密钥 K GT解密。表 4测试算法 3测试输入:-SCm,TDm,pkMDU,pkMDO,SK1,SK2输出:“匹配”或“不匹配”1:CP 和 CSP 计算:cimpkMDU,ci-1mpkMDU,c1mpkMDU SAD(TimpkMDO,timpkMDU)dimpkMDU,di-1mpkMDU,d1mpkMDU2mpkMDU(cimpkMDU)N-12:CP 和 CSP 运行 SMD 协议,计算:RmpkMDU SMD(dimpkMDU,di-1mpkMDU,d1mpkMDU)3:加入随机化种子得到:fmpkMDU=(RmpkMDU)rm4:用户对fmpkMDU使用弱私钥 skMDU解密:D(fmpkMDU)=fm5:if fm=1then return“匹配”6:else return“不匹配”7:end if注:上标 m 表示 m 组密文,省略号表示要计算 i 个加密值。2 结果与分析2.1安全性分析本节是安全性证明,需要证明 2 个部分:首先,证明方案 VSE-EPOMFC 能被安全实现。然后证明如果方案能安全实现(各方之间的协议是安全的),那么方案满足密文不可区分性以及陷门隐私性。定理 1 方 案 VSE-EPOMFC 在 满 足 敌 手 A=(AMDO,AMDU,ACSP,ACP)存在的情况下能被安全的实现。证明 SimMDO收到输入 x,通过执行以下的算法模拟敌手 AMDO:首先计算 TpkMDO Enc(T,pkMDO),将结果返回给 AMDO。因为 DP-PKC 满足语义安全(在 VI-A 定理 1 有详细描述),所以敌手 AMDO在现实世界和理想世界输出的结果是难以区分的。SimCP通过执行以下算法模拟敌手 ACP:首先随机的 从(0,2n-1)中 选 择 T,t,加 密 产 生(TpkMDO,tpkMDU)Enc(T,t,pkMDO,pkMDU),计算tpkMDU,TpkMDO,-TpkMDO,2 个加密二进制串中对应的位使用 SMD 协议相乘得到ftipkMDU。使用SAD 协议对ftipkMDU中的每一位进行累加,结果记为ftpkMDU。SMD 和 SAD 的安全性在 VI-C 定理 2中有详细证明。SimMDO与 SimCP交互后确定过滤的任务,接下来使用与 VI-C 定理 3 证明过程相同的方法计算搜索过程中用到的加密中间值c ipkMDU,dipkMDU,RipkMDU,fipkMDU。最后 SimCP发送全部的加密中间值给 ACP,如果 ACP返回,那么 SimCP同样返回。因为 DT-PKC 是满足语义安全的,MDO 是诚实的,敌手 ACP在现实世界和理想世界输出的结果是难以区分的。SimCSP通过执行以下的算法模拟敌手 ACSP:随机选择一些数字,使用与 VI-C 定理 3 证明过程相同的方法计算加密中间值。SimCSP发送全部的加密中间值给 ACSP,如果 ACSP返回,那么 SimCSP同样返回。因为 DT-PKC 是满足语义安全的,MDO 是诚实的,敌手 ACP在理想世