本文是一篇电子商务论文，本文基于可分离数据管理权与索引树的同态加密技术，分别提出了满足不同安全要求的范围索引方案，解决在轻客户端条件下数值型密文数据在云存储上的范围搜索问题。
第一章 绪论
1.1 研究背景与意义
随着网络技术的快速革新，特别是5G时代的来临，物联网(Internet of Things)将得到快速发展，在智慧城市、车联网、智慧农业和智能家居等方面得到广泛应用[1-4] ，由此引发新一轮的数据增长呈井喷态势，受到越来越多的关注和重视。针对数据爆炸的大数据(Big Data)时代，云计算(Cloud Computing)通过并行计算技术、虚拟化技术、网络技术或分布式技术对设备和数据进行整合管理，已成为一种广泛使用的计算范式，有着按需付费、动态可扩展、高稳定性等特点，用户可以随时随地连接到云获取服务，同时不需要用户自行采购与管理设备，可解决对现有硬件资源分配不均衡、利用不充分等问题，大大节约了企业和用户的运营维护成本。当前，云计算服务发展得如火如荼，如国外有亚马逊的Amazon Web Services、微软的Azure Services Platform、谷歌的Google Cloud Platform等，国内有阿里巴巴的Aliyun、腾讯的QCloud、百度的百度智能云、京东的JDCloud，其中提供包括弹性计算、各类云存储(如文档存储、云数据库)、智能计算等服务，能够为企业快速地提供IT基础设施服务，方便用户实现数据的采集、存储和处理等大数据应用。据权威机构预计，至2023年中国的云计算产业规模将超过3000亿元，越来越多的企业和政府部门将逐步采用各类云服务器架构。
云计算在为企业和用户提供各种便利的同时，也引发了用户对数据安全性的担忧。云存储是云计算的重要组成部分，为后续的智能计算、数据挖掘等云处理提供数据来源，其中难以避免地会包含一些敏感数据，例如企业的财务信息、职工客户信息、医疗系统的病历信息等。若这些数据被竞争对手或其它违法人员获取，可能会造成严重的商业损失甚至法律责任。云计算除了面临着常规的网络攻击风险外，由于引入了云服务器使得数据的所有权与管理权分离，用户还需考虑来自云服务管理者配置出错或恶意攻击等内部威胁[5]。2017年亚马逊S3泄露了大约47GB的医疗数据，涉及了15万病人的验血结果和姓名住址等个人隐私数据。IMB和Ponemon联合发布的《2019年度数据泄露成本调研报告》指出，在过去5年中数据泄露所造成的成本上升了12%，云迁移、IT复杂性和第三方泄露是使成本损失放大的重要因素，而使用加密技术是节约成本的重要手段之一。将数据迁移到云服务器上，用户失去了对它们的直接控制，而直接管理这些数据的云服务器并不完全可信，有可能会窃取或伪造用户的数据，而这些安全问题也阻碍着云计算的广泛应用[6]。所以，对于不可信的云服务器，研究云存储的安全服务具有重要意义[7]，提升云服务的安全性，有利于云计算的进一步推广应用。
1.2 国内外研究现状
本节内容首先介绍同态加密技术，然后综述密文范围搜索技术的现状，最后分析现状得出当前有待解决的问题。
1.2.1 同态加密
同态加密，又称隐私同态[11] (Privacy Homomorphisms)最早由Rivest等人在1978年提出，在“隐私数据银行(Private Data Banks)”的场景中，不可信的服务器为用户提供密文数据的存储和管理服务，可以在密文数据上直接操作而无需解密，正确地响应用户的查询和处理请求。根据密文运算所支持的操作类型，同态加密可被划分为：部分同态加密(Partly Homomorphic Encryption, PHE)和全同态加密(Fully Homomorphic Encryption, FHE)。以Grentry于2009年在其博士论文中首次提出全同态加密方案取得重大突破为标志，同态加密的发展可由此划分为两个阶段：自1978年至2009年的部分同态加密阶段和2009年至今的全同态加密阶段。
1978年，Rivest等人基于大整数分解困难性构造了RSA公钥加密算法被，该加密方案具有乘法同态性，两密文的乘积解密后等于相应明文的乘积，但不支持加法同态。1984年，Elgamal基于离散对数问题的困难性实现了一种ElGamal公钥加密体制[12]，也同样支持乘法同态性。1999年，Paillier在复合剩余类的困难问题的基础上，设计了一种Paillier概率公钥加密体制[13]，可支持任意次同态加法操作和密文与明文的乘法操作，但不支持密文的乘法同态。2005年，Boneh等人提出基于双线性对性质的BGN加密体制[14]，可支持任意次加法同态和一次乘法同态操作。针对部分同态加密的应用，徐文玉等人[15]为解决在区块链智能合约中医疗理赔的隐私问题，基于Paillier同态加密实现了一种电子健康记录的隐私保护方案，保险公司与医院在交互过程中可在密文状态下判断是否需要理赔，从而保护病人的隐私信息。文献[16]针对智能电网中安全的数据聚合问题，利用Paillier密码体制加法同态的特性在汇聚设备中对智能终端的密文数据进行聚合，能够保护各用户的用电隐私。
第二章 相关的理论知识
2.1 保序加密
为了保护数据的机密性，同时保留密文数据可比较的功能，Agrawal等首次提出了针对数值型数据的保序加密[41]。若存在一个加密算法𝐸𝑛𝑐,使任意一对存在大于等于的关系明文X和Y(X≥Y)，其相应的密文𝐸𝑛𝑐(𝑋)和𝐸𝑛𝑐(𝑌)也保持大于等于的关系(𝐸𝑛𝑐(𝑋)≥𝐸𝑛𝑐(𝑌))，这样满足式(2-1)描述的加密方案被称为保序加密。其中，保序加密最理想的安全性为选择保序明文攻击下的不可区分安全性IND-OCPA，除数据的顺序信息外不暴露明文其它的任何信息。
∀ 𝑥≤𝑦→𝐸𝑛𝑐(𝑥)≤𝐸𝑛𝑐(𝑦) (2-1)
针对理想安全性的要求，Popa等人提出了一种可变的保序编码方案[43] (mutable Order Preserving Encoding，mOPE)，与常规的保序加密不同，该方案是对敏感数据进行顺序编码，如将{12,7,31,16}编码为{2,1,4,3}，编码除与敏感数据的顺序信息相关外与其它信息无关，则敌手只能获取敏感数据的顺序信息，无法从编码中获取数据的其它明文信息。为了确定敏感数据的顺序编码，服务器维护了一棵以敏感数据的确定性密文为索引关键字的平衡二叉搜索树，密文在索引树的位置可转换成该数据的顺序编码，如图 2-1所示。
2.2 同态加密
同态加密可以在密文上直接执行某种有效运算而无需解密，这使得不受用户直接控制的云计算服务能够保证数据的安全性。继2009年Gentry首次提出全同态加密方案后，许多研究者投入到了全同态的研究中，全同态方案的效率得到了较大的提高[24]。
具体地说，全同态加密方案是指在无需解密的条件下，全同态密文𝐶可以执行任意的计算得到密文结果，对该密文结果解密得到的明文与在明文𝑀上执行相应计算的结果一致。在全同态加密方案中，加解密函数分别为𝐸𝑛𝑐()和𝐷𝑒𝑐()，对于明文数据𝑀1,𝑀2,⋯,𝑀𝑛和任意的有效函数𝑓，存在一个密文上相应的操作函数𝑓′，满足以下形式：
𝐷𝑒𝑐(𝑓′(𝐸𝑛𝑐(𝑀1),𝐸𝑛𝑐(𝑀2),⋯,𝐸𝑛𝑐(𝑀𝑛)))→𝑓(𝑀1,𝑀2,⋯,𝑀𝑛) (2-2)
其中，若有效函数𝑓只支持加法运算，则将其称为加法同态；若效函数𝑓为只支持乘法运算，则将其称为乘法同态；若有效函数𝑓都支持加法和乘法运算，但运算次数受限，则将其称为Somewhat同态(也称浅同态)。只有当有效函数𝑓都支持加法和乘法运算，且运算次数不受限制，这样的加密方案才称为全同态加密方案。值得注意的是，由于全同态加密是一个概率加密方案，相同的明文在每次的加密过程中会生成不同的密文。
第三章 轻量客户端理想保序密文范围索引方案 ............................ 17
3.1 改进的理想保序加密 ........................... 17
3.2 双服务器结构的方案模型 ................................ 18
3.3 同态保序方案的算法描述 ........................... 19
第四章 隐藏顺序的密文范围搜索方案 ..................................... 28
4.1 索引结构分析与改进 ........................... 28
4.2 隐藏顺序的方案模型 ................................ 30
4.3 二阶段的范围索引算法描述 ........................... 32
第五章 总结与展望 ................................. 41
5.1 工作总结 ..................................... 41
5.2 未来展望 ....................................... 42
第四章 隐藏顺序的密文范围搜索方案
4.1 索引结构分析与改进
本节将分析云存储系统在搜索处理中的信息泄露，以及攻击敌手对泄露信息利用的大致流程，继而提出云存储的安全模型及索引结构的改进思路。
图 4-1描述了内部敌手对范围搜索泄露信息的利用流程。在常规云存储系统中，云服务器存储可以访问图中的不可区分密文记录，在响应用户搜索请求后，向用户返回对应的搜索结果。当不同的搜索结果存在交集时，内部敌手可从中获取密文的偏序信息。例如，搜索1结果A包含密文{𝐶𝑖,𝐶𝑗}，而搜索2结果B包含密文{𝐶𝑗,𝐶𝑘,𝐶𝑙}，其中交集𝐴∩𝐵={𝐶𝑗}，可推出密文的顺序偏序关系：{𝐶𝑖}≼{𝐶𝑗}≼{𝐶𝑘,𝐶𝑙}。
第五章 总结与展望
5.1 工作总结
云存储可降低用户对大数据收集和管理维护的开销，使得各种业务系统能够更快速地搭建，但由于数据的安全问题，用户对云存储的使用有所保留。为了保护数据的安全性，用户需要将数据加密后再上传至云端保存，而常规的加密技术使得数据难以检索。如何既保证数据的安全性同时又保留数据的可检索性，一直是云存储领域的研究热点。保序加密方案使密文保留了明文的顺序关系，使得数据在密文上可比较的同时，在一定程度上保护了数据的安全性。在密文的范围搜索中，达到理想安全性的保序编码方案需要持有私钥的用户持续地参与到编码的更新、维护与搜索中，这增加了用户的计算和带宽开销。另外，保序加密所泄露的顺序信息，容易让敌手基于统计攻击对数据的安全性造成威胁，不能用于较高的安全级别。如何在不泄露密文的顺序信息以及数据访问模式的条件下仍支持数值型数据的比较，也是一个值得研究的问题。
(1) 针对理想保序编码方案𝑚𝑂𝑃𝐸需要客户端全程介入的问题，本文基于同态加密技术可在密文上直接运算的特性，将密文的数据索引分割成两部分：敏感数据的原始密文和敏感数据的顺序关系。敏感数据的原始密文存储在云存储服务器上，云存储服务器可对密文进行运算操作但无法获取相应的明文数据；敏感数据的顺序关系以平衡二叉树的方式存储在云搜索服务器上，云搜索服务器可以通过云存储服务器的密文运算获取两个密文的比较结果，解密后得到密文的大小关系，但无法获取到原始的密文，从而无法得到明文数据。用户将操作请求提交给云存储系统后，等待两服务器交互合作得到的处理结果，无需额外的交互开销。
(2) 针对索引树泄露敏感数据顺序信息和访问模式的问题，本文通过引入模分组，使范围搜索划分为两个阶段：第一阶段，云存储服务器在云搜索服务器的指导下，查找包含搜索请求数据的所有分组，得到一个包含错误记录的密文记录集合，这使得云存储服务器无法获取到真实准确的顺序信息和数据访问模式，只能获取到以分组为单位的顺序信息和访问模式；第二阶段，云存储服务器对第一阶段结果密文记录集合进行混淆，云搜索服务器进行过滤，向用户返回真实的搜索结果。云存储服务器的混淆操作使得云搜索服务器无法区分在不同搜索处理中的相同密文记录，也无法对历史搜索结果进行关联，继而无法获取不同搜索结果的交集信息。
参考文献（略）