第一章 绪论
1.1研究背景和意义
1.1.1研究背景
当前业界对于云计算（Cloud computing）有多种定义。以网络技术、虚拟化技术、分布式计算技术为基础，以按需分配为业务模式，具备动态扩展、资源共享、宽带接入等特点的新一代网络化商业计算模式[1]；一种能够简易地、按需地从网络访问可配置共享计算资源的模型，能够将这些资源快速供应和发行，并且以最简便的管理工作和最少的服务交互为代价[2]；一种新近提出的计算模式，是分布式计算（Distributed computing）、并行计算（Parallel computing）和网格计算（Grid computing）的发展，具有分布式的计算和存储特性，高扩展性，用户友好性，良好的管理性，用时付费等特性[3]。从本文的角度，我们认为云计算是面向服务的模型，云服务提供商（Cloud provider，CP）依靠互联网向各个终端按需提供多种计算资源，并且随着产品和技术的优化，服务质量也不断地得到提升。
云计算系统向用户提供多种服务[4]：1）硬件服务（Hardware as a Service，Haa S），提供可调用的硬件资源，如可扩展的服务器、远程服务终端等；2）软件服务（Software as a Service，SaaS），提供基于云的软件服务，例如智能手机中的同步软件、电子邮箱等；3）平台服务（Platform as a Service，PaaS），在硬件的基础之上提供完整的软件支持，可以满足用户的特殊开发平台的需求；4）基础架构服务（Infrastructure as a Service, IaaS），通过互联网提供基础架构的软硬件资源，提供服务器、操作系统、数据库等资源，例如 Amazon AWS，阿里云等。 许多公司开发并提供基于云计算平台的产品和服务，但没有适当考虑云端共享和虚拟化环境对数据处理、存储和访问的影响。
许多从事云计算软件开发的工程师都在努力将安全性纳入考虑范围。云计算在海量的规模上共享资源，这与成本效益和位置无关。云服务器上的资源可以由客户端调用，并由 Amazon、Google、IBM、salesforce、Microsoft 等供应商部署。云计算给人们带来巨大的效益，客户不需要从第三方供应商那里购买资源，相反地，他们可以使用资源并将其作为服务付费，从而帮助客户节省金钱和时间。云计算在多个领域都有所应用，如表 1.1 所示。
.......................
1.2 课题研究现状
现有的隐私保护排序方法的研究成果主要分为两类：一类是基于保序加密技术实现的隐私保护排序；另一类是基于全同态加密技术实现的隐私保护排序。
（1）保序加密（Order Preserving Encryption）是一种明文偏序关系与对应密文的偏序关系保持一致的数据加密方法，最早由 Agrawal R 等人于 2004 年提出[7]。2014 年，Jaiman V 等人提出云环境下的保序加密策略[8]。黄汝维等提出一种基于随机树的保序加密算法OPEART(Order-preserving Encryption Algorithm based on Random Tree)[9]，支持数据库的索引创建和快速检索。周雄等对 OPEART 算法进行改进，提出一种基于随机间隔的保序加密算法（OPERI）[10]。
（2）全同态加密（Fully Homomorphic Encryption，
FHE）是指能够在不知道密钥的情况下，对密文进行任意计算，即对于任意有效的 f 及明文 m，有性质 f(Enc(m))=Enc(f(m))[23]。由于这种特殊的性质，全同态加密有广泛的理论与实际应用，如云计算安全、密文检索、安全多方计算等。Gentry 等[11-13]提出全同态加密算法。Melchor 等提出将 FHE 用于实现针对整型数据隐私保护排序的思想[14]。Chatterjee等在此基础上提出了基于 FHE的密文排序算法[15]，
该方法通过降低重加密次数来获得更高排序效率，并将全同态密文排序算法应用到现实云计算环境中[16-17]。
对于保序加密算法而言，由于其密文本身就可以进行秘密比较，从而利用保序加密就可以实现云环境下的隐私保护排序，而不需要在意加密算法的具体实现过程；对于全同态加密算法而言，只要其重加密过程可以完全在 CS 端执行，则该算法就可应用到云环境中进行秘密比较，从而实现隐私保护排序。
本文针对云环境下的隐私保护排序问题，提出了两类解决方法，第一类是基于安全比较码的隐私保护排序方法；第二类是基于混沌映射的隐私保护排序方法。方法均由两部分组成：DO 端的数据预处理和 CS 端的隐私保护排序。两类方案均能实现无需明文参与的隐私保护排序，同时在保证安全性的前提下，相对于现有的同类方法具有时空效率的优势。
..........................
第二章 相关工作
2.1云环境下的隐私保护排序概述
2.1.1 云环境下的外包存储模式
随着云计算的快速发展，以节省计算、存储等资源配置和维护的成本，基于云计算的外包服务模式被越来越多的公司和个人接受和采用。
云计算系统不但能对数据进行处理和运算，系统中还有大量的存储阵列设备，以实现对计算数据的保存和管理[18]。随着垂直磁记录（Perpendicular Magnetic Recording）等存储技术的不断发展，磁盘存储密度接近极限，普通机械硬盘的单碟容量可达 1.5TB。但在面对 ZB 级的存储需求时，传统的存储区域网络（Storage Area Network）和网络附属存储（Network Attached Storage）在性能扩展上存在瓶颈，无法满足新形势下对数据存储高性能、高容量、易扩展的需求。随着云计算的蓬勃发展，云服务也逐渐成为存储系统的新发展模式。云服务模式的资源外包存储系统不仅可以突破传统存储系统的性能瓶颈，而且可以轻松实现性能与容量的线性扩展。相对于传统的集中存储系统，集群的高效云外包存储具有以下优势：
（1）方便扩容
当用户需要增加容量时，可按照需求采购服务器的存储容量或网络带宽，通过简单增加即可实现容量、带宽的扩展。如，当用户需要扩容时，采购大容量的存储设备即可；当需要扩展带宽时，采购网络吞吐量较大的服务器即可。扩容过程较为简单，新设备在安装操作系统和应用软件后，打开电源并连接至计算机网络，云存储系统便能自动识别，自动把容量加入存储池中完成扩展。相对于传统的存储扩容方式而言，云存储架构采用的是并行扩容，即当存储容量不够时，采购新的存储服务器即可，在扩容环节中无任何的限制。
（2）管理简便
在以往的存储系统管理中，管理人员需要面对不同厂商的存储设备，而不同厂商的设备均有不同的管理软件和 UI 界面，这使得管理人员的工作变得复杂而繁重。而且，传统的存储硬盘或是存储服务器损坏时（如出现坏道、坏扇区、磁盘逻辑错误等），其读写效能会降低很多甚至导致数据丢失；而云存储不会遇到这样的问题，由于云服务器多采用 RAID 磁盘阵列，具有数据冗余的功能，当阵列中某一个磁盘损坏，数据会自动从镜像中恢复，不再需要人工手动操作，从而大大降低了管理人员的工作负担。管理人员只需要在剩余存储容量即将耗尽时，从资源池中调用更多的存储资源即可。管理人员可以通过管理软件进行存储服务器使用情况的统一监控。
（3）成本更低
在云外包存储系统中所使用的设备都具有较高的性价比。由于云服务提供商和硬件厂商实现长久合作关系，便于控制成本和服务质量。传统的存储系统要求存储设备必须具有相同的生产商和型号，否则系统将变得不稳定。在产品高速迭代更新的信息技术行业，普通硬盘在使用三到五年后很难找到型号和厂商完全相同的产品进行更换。
.........................
2.2背景知识介绍
为方便读者理解本文，我们给出相关背景知识的介绍，主要包含：保序加密、全同态加密、混沌现象与 Logistic 映射、哈希消息认证码等内容。
2.2.1 保序加密
保序加密是范围数据加密查询的一种常见解决方案[7,20-21]。它允许用户加密数字（如 x，y）并提交到服务器，而对应的密文数据的比较关系与明文相同，即 x>y 等价于密文 x*>y*。它这样的保序方式使得服务器在不知道查询的具体数据的情况下能对密文进行比较判定。保序加密的基本原理是将一个具有较小定义域的明文映射到一个具有较大定义域的密文，同时添加一些随机因素作为密文噪音[9-10]。
保序对于唯密文攻击和统计型攻击的抵御能力仍然较弱，例如在文献[22]中，作者使用频率分析、唯密文攻击、排序攻击等手段，成功地还原出总占比 80%的医院病患数据信息。
2.2.2 全同态加密
全同态加密问题早在 1978 年就由 Rivest 等人[24]提出，之后成为密码学界的一个开放难题，被誉为密码学界的“圣杯”[25]。随后相继产生过许多同态加密方案[26-33]，这些方案要么满足加法同态，要么满足乘法同态，还有一些能够同时满足有限次加法与乘法的同态方案[34-38]。上述这些方案都不是全同态的，直到 2009 年 Gentry 构造出第一个全同态加密方案[11]。
从 2009 年至今产生了许多全同态加密方案及实现与优化[11-13,39-48]。第一代全同态加密方案[11-13,39-43]都是遵循 Gentry 复杂的构造方法。尽管同态解密是实现全同态加密的基石，但是同态解密的效率很低，其复杂度为?(λ4)[46]。第二代全同态加密方案[44-48]构造方法简单，基于 LWE（环-LWE）的假设[33]。尽管全同态加密方案的效率不断提高，但是全同态加密的构造方法并没有大的突破，离实际应用依然有距离，而低效率的根本原因与构造方法直接相关[23]。
............................
3.1问题描述 ...................... 12
3.2安全比较码机制 ........................... 13
第四章 基于 Logistic 映射的隐私保护排序方法 ................... 28
4.1问题描述 .................. 28
4.2基于 Logistic 映射的秘密比较方法 ....................... 29
第五章 总结与展望 .................. 45
5.1工作总结 ............................... 45
5.2研究展望 ...................... 45
第四章 基于 Logistic 映射的隐私保护排序方法
4.1问题描述
与第三章类似，本章提出的隐私保护排序方法所面向的云计算模型与现有研究工作[16, 17]类似，主要包含两个实体，分别为数据拥有者（Data owner）和云服务端（Cloud server），DO 和 CS 之间的交互方式如图 4.1 所示：1）DO 私有敏感明文数据，为寻求隐私保护对明文数据进行处理，使用预处理算法对明文数据处理并产生对应的密文数据，然后存储外包到 CS上；2）CS 接收并存储 DO 上传的数据并对其进行排序操作。
我们同样假设 CS 遵循“半诚实模型[62]”提供服务，即 CS 能够严格遵守既定协议和算法执行，但有窥探 DO 数据隐私的企图。DO 私有明文敏感数据，若不对这些明文数据进行处理而直接外包到 CS 上，数据不具有私密性可言。CS 在对数据进行排序的同时，将尝试对数据的私密性进行攻击：1）CS 已知 DO 的预处理算法，但不知道其初始的参数设定，尝试对外包数据进行穷举攻击以得到明文信息；2）由于外包数据的海量性，统计型攻击是一种常用方法。CS 尝试统计分析密文的分布规律并推测明密文间关系以获得明文信息。
......................
第五章 总结与展望
5.1 工作总结
随着云计算的蓬勃发展，国内外云服务提供商大量涌现，它们为用户提供强大的计算、存储能力。云服务体现了“网络即计算机”，它将大量计算资源、存储资源与软件连接在一起，形成巨大规模的虚拟共享资源池。不论是个人、公司还是政府，都越来越频繁地使用云服务。然而，云服务商并非值得完全信任，近年来多起隐私泄露事件为云时代敲响了警钟。
数据拥有者的隐私数据存储在云端，云服务提供商的内部工作人员可随意取得，云端存储数据的防护重心从防止外部入侵向组织内部泄露转移。实现隐私保护的主要技术手段就是对数据加密。然而，传统的加密算法在数据库服务场景中有很大局限，如何保证用户数据隐私性的前提下可对密文进行排序操作是主要问题所在。
本文提出的两种隐私保护排序方法均与现有方法有所不同，为密文排序带来新思路。本文主要研究面向云环境的密文排序方法。首先收集、概述了现有的密文排序研究成果，并主要阐述、分析了现有方法的优缺点，然后提出了第一个创新点——基于安全比较码的隐私保护排序 SCPS。安全比较码机制基于前缀成员验证 PMV 和哈希消息认证码 HMAC 技术。CS端利用安全比较码可以实现无需明文参与的密文排序，同时还分析了安全性并在实验中与现有 FHE 方法对比时空效率，结果显示，SCPS 方法在时空效率方面均优于 FHES 方法。
紧接着，本文提出了基于 Logistic 映射的隐私保护排序方法 LMPS。在数据预处理中，DO 端产生预处理数据，然后提交给 CS 端，此时 CS 端使用提出的基于 Logistic 映射的秘密比较方法完成隐私保护排序。我们对该方法进行了安全性分析，并与 SCPS 进行时空效率的实验对比。结果显示，LMPS 在排序时间效率和存储空间占用上优于 SCPS。
参考文献（略）