高维数据密文检索论文阅读

一云下外包数据的检索和审计-王建峰

1.强调的安全点是：用户可以对检索结果进行正确性和完整性验证，当服务器返回的检索结果为空集时，用户需要能区分出是服务器不执行检索操作还是执行检索后确实无匹配数据。

2.三个创新点：

（1）检索结果为空集时的支持用户验证（这个可以暂时不细读）

（2）高效检索高维密文数据（video的数据就是高维的）

（3）数据去重时支持追踪恶意用户身份（这个可以暂时不细读）

3.数据库检索验证的研究现状：

（1）基于Merkel Hash Tree：树的根节点是用户签名，叶子节点是数据库中的每条记录，用户检索某一记录时，需首先由用户计算根节点的签名，再由服务器返回根节点到目标叶子节点路径上的所有节点的兄弟节点的hash值。

（2）基于间谍节点验证：插入少量间谍数据记录，检索时需要返回满足某个查询条件（这个条件可能和目标记录有关）的间谍数据，否则判定服务器作弊。

（3）基于签名链：聚合签名，为每条数据记录分配一个基于多项式的认证标签，该标签可用于检查聚合检索结果的正确性。

4.数据审计：外包数据的存储完整性认证

（1）开创性：

1）可证明数据持有性PDP，本科期间的专利NPDP就是对PDP方案的改进，PDP是Server向user证明文件完整性

2）可证明数据恢复POR

3）可证明所有权PoW，User向server证明文件完整性，因为PoW的挑战响应机制会要求用户返回MHT叶子节点的子集，所以仅仅拥有根节点签名并不能验证出用户身份。

这两个方案都支持用户在不下载数据的情况下对存储在云上的数据完整性进行审计。

（2）存储审计和检索审计区别：

1）存储审计用户已知database的相关数据信息，检索审计用户对database一无所知

2）存储审计关注返回结果的正确性（为什么不关注完整性？PDP不就是证明完整性的么），检索审计关注返回结果的正确性和完整性（？？）

5.近似最近邻检索ANN：找到一个与查询数据点足够接近的数据点（作为还是代替？）最近邻数据点

（1）K-means树

（2）LSH：局部敏感hash，基本思想是原始空间相邻的两个点经过相同映射后，在映射后的空间里也以很大概率相邻，而原先不相邻的点在新空间里的相邻概率较小。也就将在超大集合里找相邻点的问题转成了在较小集合里找相邻点的问题。（是高维数据近邻检索的主流技术）

6.密文SQL查询：保序加密（所以如果是针对非结构性数据如多媒体，就得先转成结构性存储在SQL中）

第一种能达到IND-OCPA安全性的保序加密方案（2013）：POPA

7.收敛加密：Key=Hash（加密消息），是一种对称加密，但是支持不同用户加密同一明文能得到相同密文，所以可用于数据去重，避免相同数据的重复存储。

新定义：MLE（Message-Locked Encryption）消息锁定加密

8.追踪恶意用户身份：

（1）群签名：组内任何一个用户的签名代表群组对消息的签名，只有群管理员能在必要时刻打开签名揭示签名者身份。基于双线性对的群签名具有更强匿名性。

（2）如果要追踪某个（恶意）用户的身份，该用户又在群组内的话，就得一一打开所有群签名，这会导致群内其他用户的隐私被揭露，所以需要能追踪用户身份的签名方案。给用户签名加上追踪令牌

9.密码学基础：

A.高维数据的密文检索涉及的密码学理论基础【重点】（考虑下能否用在视频密文检索）

（1）LSH：局部敏感HASH具有保距性，能高概率的将距离接近的数据映射为相同的hash值

改进的LSH方案：LSB,C2LSH,最近的是SortingKeys-LSH（Design by刘英帆），方案的思想是：

1）定义组合hash值间距离的度量规则

2）创建一个基于组合Hash值得顺序关系

3）依据上一步的顺序关系对数据点进行排序

4）彼此接近的数据点会被存到同一个索引文件中，这样可以减少检索时要访问的索引文件数量

SK-LSH的问题在于索引文件是本地存储，所以需要改进到支持云存储，即数据外包。（其实我在做视频密文检索时，可以先从本地存储的思路开始设计方案，然后再扩展到云计算环境）

（2）保序加密：2013年提出的mOPE引入密文可变的特性，是已知安全性最高的保序加密方案

B.返回空集时的验证问题涉及密码学：

（1）布隆过滤器

（2）布隆过滤器树

（3）Merkle Hash Tree

C.支持动态更新的SQL检索涉及密码学：

（1）可翻转布隆过滤器

D.可追踪签名技术：

（1）双线性对

10.高维密文数据检索方案：

【攻击模型】在阐述设计方案前，都会先给出攻击模型，对于云服务器的角色特性做出假设，例如“诚实且好奇”，也就是说云server会想方设法获取存储数据的敏感信息。包括内部攻击和外部攻击。

【设计目标】根据攻击模型要给出方案的设计目标，如果是工程项目，其实也就是工程的实践目标

【方案设计】

（1）数据排序：采用SK-LSH局部敏感hash（比如说是100部视频片段，假设一个视频片段能用一个特征表示，那就要将这些特征先逐个进行局部敏感hash）

1）组合hash值：对数据集中的一个数据点p（如一个视频K），它的组合hash值是：K=G(p)=(k1,k2,…,ki)=(hash1(p),hash2(p),…,hashi(p))；一组hash函数。

2）K的前L个元素称为k的（长度为L的）前缀，pref(K,L)

3）两个数据点p1,p2对应各自的组合hash值K1,K2，它们的L长前缀相等，他们的L+1长前缀不等，那么K1、K2的非前缀长度为：KL(K1，K2)=m-L

4）K1和K2的第L+1个元素间的距离被定义为：KD(K1,K2)=|k(1,l+1)-k(2,l+1)|

5）两个组合hash值得距离：dist(K1,K2)=KL(m-L)+KD(K1,K2)/C（C是一个标准因子）

6）对K1、K2等数据集中的所有点K按照上面规则排序

结论：if Ki

（2）对称加密：换成国密，然后就生成了具有顺序关系的密文数据（然后对这100个特征数据逐一对称加密，就得到了有序的密文特征）

（3）生成索引：采用mOPE方案，对有序的密文数据生成具有保序性质的索引结构。（也就是说索引结构中的100个索引点的顺序是保持了密文特征的顺序的，相应也就保持了明文特征的顺序）

索引结构是一棵OPE tree，节点上寸的是密文特征，而且密文特征是有序插入到树上的，保证树上任意节点v，v的左子树v.（云服务器是无法获得某个索引节点对应的明文特征的，因为特征是被用户密钥加密）User插入新数据时要先请求OPE树的根节点，server返回根节点后User解密，自行比较要插入的数据和根节点数据的大小，然后继续请求根节点的左孩子或右孩子，依次类推。

（4）检索：在索引结构上执行检索（检索其实是一些数值比较操作），相当于在明文上执行检索。