文章背景：
数据外包（outsource）是现在研究的一个大的方向，然而外包的第三方服务器（sp）不可信很可能泄露一些信息，需要使用密码学技术保护隐私。
解决的问题：
该文章解决的是空间数据下（这篇文章研究的是地理位置坐标，比如（2，4）坐标）的外包隐私保护问题，具体的说即：一个解决方案需要解决以下几个问题，注意这几个问题都是在密文下进行的：
- 点查询：在多项式时间内，给定一个空间点，找出所有和查询点包含的空间位置一样的数据对象（这里指的是点）。
- 窗口查询：在多项式时间内，找出和d维查询窗口w有至少一个公共点的数据对象（这里的数据对象指的就是窗口）
- KNN查询：在多项式时间内，给出一个查询点q和一个点集P，在点集P中，找出距离查询点q最近的k个点。
- 满足安全需求，该文章定义了两个攻击,tailor attack, general attack
该文章是给出了四个解决方案。
一般的解决方案：
将数据全部发送给客户端，客户端再解密。
本文的解决方案：
之前有一些文章的研究成果是针对关系数据库，因为地理位置坐标的蕴含着某些特殊性（比如需要有一些最近邻查询的需求），所以觉得此类问题，需要研究另外一种数据库-空间数据库。
- 挑战
-
空间数据需要加密,且加密后支持安全搜索，即用户给定一个关键字，服务器返回一个数据对象，且服务器不知道关键字是什么。如图：
Paste_Image.png - 需要防止敌手攻击，该文章定义的攻击模型如下：
-
攻击模型.png
-
本文的四个解决方案（HSD,ERB,HSD*,CRT）
-
HSD：坐标转换方法，利用坐标变换的思想
-
构造&&解释
构造
解释
对应的点转换公式：
Paste_Image.png -
窗口查询
Paste_Image.png
二叉树的数据结构，时间复杂度较低。
- 攻击分析
通过对应点转换公式可知，如果知道密文上的同一区域的两个点，可以通过点大体确定密文子区域的范围，便能通过控制变量求得明文中该区域的对应的范围，实现了单区域的tailored attack。如果实现全区域的tailored attack则需
S至少要有2^E-1个点，且这些点都分布在独立的区域，所以一个好的HSD应该是每个区域分布的点的数量相同。
-
-
ERB:一种坐标转换方法
-
构造
Paste_Image.png
说明：SHA返回[0,1]，error threshold范围也在[0,1]，x,y也在[0,1],可证明x',y'也在[0,1]，id是每个坐标点的标识符
-
窗口查询：
窗口表示法：
Paste_Image.png
窗口转换：
Paste_Image.png - 攻击分析
安全性取决于SHA,所以不能实现上述两个攻击 -
时间复杂度分析
根据窗口查询的概念，返回的是一个数据对象，所以此处返回的是一个矩形，假设查询窗口边长为r，很明显，明文上的查询复杂度为
Paste_Image.png
根据
Paste_Image.png
得到密文窗口查询复杂度为：
Paste_Image.png
-
-
HSD*转换：也是基于坐标的转换方法
由于HSD缺点即安全性问题而其时间复杂度较低，ERB的缺点即时间复杂度较高而安全性较好，所以提出了一个两者结合的坐标转换方法，转换公式如下：
Paste_Image.png
合理性分析：
Paste_Image.png
-
-
几个变换的KNN搜索
Paste_Image.png
Paste_Image.png -
CRT变换：直接加密点，然后建立对应的索引查询
-
窗口查询
CRT的窗口查询 - KNN查询：跟在明文上的R树增量查询一样，只不过要通过加密索引去向服务器请求节点，客户端解密节点，如果树的深度很长，这里时间复杂度会很高
-
