Searchable Encryption


本篇文章以小简看过的文献以及查阅的资料为基础,归纳和总结了可搜索加密(Searchable Encryption,SE)的相关知识点。

SE介绍

以下内容是小简阅读可搜索加密的两篇综述论文所总结,论文介绍如下

序号 论文名称 作者
年份
单位 来源 链接
1 Survey on the Searchable Encryption 李经纬 2015 南开大学 Journal of Software 原文
2 Research Advances on Secure Searchable Encryption 董晓蕾 2017 华东师范大学 Journal of Computer Research and Development 原文

可搜索加密(SE):旨在将数据文件进行加密后存储到云端,然后对密文进行检索的一种技术。

例如:用户为节约自身的资源开销,将文件外包给云服务器,但又不想云服务知道存储的文件内容,因此需要对文件采用某种加密方式加密后存储。此外,用户若想从云服务器中查询文件中的特定数据,只有合法的用户基于关键词检索对应的密文数据。

可搜索加密解决两类基本问题:

  • ① 不可信赖服务器的存储问题

  • ② 不可信赖服务器的路由问题

SE过程

  • ①加密过程。用户使用密钥在本地对明文文件进行加密,并将其上传至服务器。

  • ②陷门生成过程。具备检索能力的用户,使用密钥生成待查询关键词的陷门,要求陷门不能泄露关键词的任何信息。

  • ③检索过程。服务器以关键词陷门为输入,执行检索算法,返回所有包含该陷门对应关键词的密文文件,要求服务器除了能知道密文文件是否包含某个特定关键词外,无法获得更多信息。

  • ④解密过程。用户使用密钥解密服务器返回的密文文件,获得查询结果。

可搜索加密过程

SE分类

按照应用模型分类

  • ①一对一模式
    • 用户加密个人文件并将其存储到不可信的服务器。只有该用户具备基于关键词检索的能力,服务器无法获取明文文件和待检索关键词的信息。
  • ②多对一模式
    • 多个发送者加密文件后,将其上传至不可信的服务器,以达到与单个接收者传送数据的目的。只有接收者具备基于关键词检索的能力,服务器无法获取明文文件信息,不同于单用户模型,多对一模式要求发送者和接收者不能是同一用户。
  • ③一对多模式
    • 单个发送者将加密文件上传至不可信服务器,然后多个接收者共享数据。
  • ④多对多模式
    • 在多对一模式的基础上,任意用户都可成为接受者,通过访问控制和认证策略后,具备关键词的密文检索方式提取共享文件的能力。只有合法的用户具备基于关键词检索的能力,服务器无法获取明文文件信息,具备广阔的应用前景。

按照解决策略分类

  • ①对称可搜索加密(Symmetric searchable encryption, SSE)
    • 旨在加解密过程中采用相同的密钥之外,陷门生成也需要密钥的参与,通常适用于单用户模型,具有计算开销小、算法简单、速度快的特点。
  • ②非对称可搜索加密(Asymmetric searchable encryption, ASE)
    • 旨在加解密过程中采用公钥对明文信息加密和目标密文的检索,私钥用于解密密文信息和生成关键词陷门。非对称可搜索加密算法通常较为复杂,加解密速度较慢,其公私钥相互分离的特点,非常适用于私钥生成待检索关键词陷门,通常适用于多对一模型。
  • ③对称+非对称可搜索加密
    • 由于非对称SE本身支持最基本形式的隐私数据共享,可通过共享密钥拓展到多对多的应用场景。对称SE虽然使用单用户模型,但计算开销小、速度快,更适用于大型文件数据的加密和共享。通过混合加密与基于属性加密技术相结合,或与代理重加密结合,也可构造共享方案。
  • ④属性基加密(Attribute-based encryption, ABE)
    • 它是指通过对用户私钥设置属性集(或访问结构)为数据密文设置访问结构(或属性集),由属性集和访问结构之间的匹配关系确定其解密能力。特别是密文策略的属性基加密(CP-ABE),其密文上的访问策略本身就是一种搜索策略,访问策略的表达能力从一定程度上反映了可搜索能力。

按照关键词数分类

  • ①单关键词搜索:旨在用户在检索的过程中使用单关键词进行检索。
  • ②多关键词搜索:旨在用户在检索的过程中使用多个关键词进行检索。

按照检索精度分类

  • ①精确搜索:旨在搜索的过程中,只有当输入的关键词完全等于文件的索引值时才能检索出结果。
  • ②模糊搜索:旨在搜索的过程中,用户输入的关键词与数据或索引中存在的关键词之间存在某种模糊的关系,并以这种模糊关系进行关键词匹配。模糊搜索分为以下两种架构:
    • 使用编辑距离(edit distance):利用通配符和编辑距离构造一组与原始关键字相似的模糊关键字。不支持多关键字排序搜索、搜索效率低
    • 使用局部敏感哈希(LSH)和布隆过滤器(BF):通过LSH为每个文件生成Bloom过滤器。搜索精度最多87%

SE用途

  • ①外包数据库字段加密
  • ②云计算中隐私数据的保护和共享
  • ③密文直接操作的相关应用

SE构造

  • 基于索引:对于每一个关键字 W,建立一个索引,索引中包含所有含有该关键字的文件的指针。由于这种方案在更新数据的时候会对索引进行大量的修改,因此适合大量只读模式。
    • Z-IDX方案

    • SSE-1方案

  • 基于存储结构:这种情况下没有索引,每次查询都是对文件进行一次扫描来寻找符合查询条件的文件。无疑,这种模式的查询效率会低很多,但是却更适合经常更新的存储系统。
    • SWP方案

SE历史

  • 2000年——D.Song等人首次提出了SE,有效地解决了对加密数据的搜索问题,保证了数据
    的隐私不被泄露。论文链接
  • 2010年——Jin Li等人提出了第一个支持模糊关键词搜索的解决方案。该方案使用编辑距离来表示关键字的相关性,并利用通配符*来构造模糊关键字集。论文链接
  • 2012年——Qi Chai等人首次提出了采用基于树的索引和哈希链技术实现了可验证的SE方案论文链接
  • 2014年——Bing Wang等人提出了利用LSH和BF的体系结构提出了MFSE(加密数据上的多关键字模糊搜索)方案。该方案可以在不预先定义模糊关键字集的情况下对返回的结果进行排序。论文链接
  • 。。。。。。

SE基础知识

如下是阅读论文所涉及到的基础知识

1.局部敏感哈希(LSH)

Locality Sensitive Hashing主要用于高效处理海量高维数据的最近邻问题 ,使得 2 个相似度很高的数据以较高的概率映射成同一个hash 值,而令 2 个相似度很低的数据以极低的概率映射成同一个 hash 值。

LSH详细内容请看:LSH原理与实现LSH(局部敏感哈希)深入浅出LSH

Locality Sensitive Hashing (LSH) Home Page (mit.edu)

一文了解局部敏感哈希(LSH)的前世今生

2.布隆过滤器(BF)

Bloom filter主要用于检索一个元素是否在一个集合中,1970年由布隆提出,它实际上是一个很长的二进制向量(位图)和一系列随机映射函数(哈希函数)。存储的数据是 0 或 1 ,默认是0,0代表不存在某个数据,1代表存在某个数据。

存入过程

布隆过滤器上面说了,就是一个二进制数据的集合。当一个数据加入这个集合时,经历如下洗礼:

  • 通过 K 个哈希函数计算该数据,返回 K 个计算出的 hash 值
  • 这 K 个 hash 值映射到对应的 K 个二进制的数组下标
  • 将 K 个下标对应的二进制数据改成 1 。

例如,将“你好”存入布隆过滤器,第一个哈希函数返回 3,第二个第三个哈希函数返回 5 与 7 ,那么布隆过滤器对应的下标3,5,7的位置改成1。

查询过程

布隆过滤器主要作用就是查询一个数据,在不在这个二进制的集合中,查询过程如下:

  • 通过 K 个哈希函数计算该数据,对应计算出的 K 个 hash 值
  • 通过 hash 值找到对应的二进制的数组下标
  • 判断:如果存在一处位置的二进制数据是 0,那么该数据不存在。如果都是1,该数据存在集合中。

我们假设 BF 是一个 12bit 的二进制向量,{h1,h2}是两个哈希函数,{x,y,z}是一个集合。 用户想查询关键字 w,查询结果显示 w 在集合中不存在。

优缺点

它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率删除困难

添加数据是通过计算数据的 hash 值,那么很有可能存在这种情况:两个不同的数据计算得到相同的 hash值。这样查询的时候就会造成错误识别,同样如果已经存在有两个相同 hash 值的数据,删除时就会同时删除两个。

BF详细内容请看:最牛一篇布隆过滤器详解

Bloom filter 假阳性
  • Bloom filter 存在假阳性(false positive)的可能

    • 假阳性表示实际是假但误辨为真的情况
  • Bloom filter 不存在假阴性(false negatives)的可能

    • 假阴性表示实际是真但误辨为假的情况

也就是说,一次查询返回的结果是可能在集合里或者绝对不在集合里


3.对偶编码函数

给定字符串 S1 = C1C2 … Cn 和二进制向量 S2 = b0b1 … bm-1 , S2 中每位元素的初始值为 0,其中 n < m .通过 Hash 函数 H,把 S1 中相邻 2 个字符散列映射为 0~(m -1) 之间的数,当且仅当 H ( Cj , Cj +1 ) = i 时,bi = 1。把 S1 → S2 的函数称为对偶编码函数。

在面向密文的多关键字模糊搜索方案中,构建索引、构建陷门和关键字查询的过程都是基于向量的操作过程。数据拥有者输入的关键字都由字符组成,由于字符的不可计算性,需要将其转换成向量的形式。


4.倒排索引

正排索引(forward index)

正排索引是指以文档 ID 为 Key,文档内容为 Value

倒排索引(inverted index)

倒排索引是指以文档内容为 Key,文档 ID 为 Value

举个例子🌰

例如,有 3 个文档及其对应关键词

ID 文档 关键词
id1 《手机》 苹果、小米
id2 《水果》 香蕉、苹果
id3 《粮食》 小米、玉米

正排索引:

{id1,苹果,小米}、{id2,香蕉,苹果}、{id3,小米,玉米}

倒排索引:

{苹果,id1,id2}、{小米,id1,id3}、{香蕉,id2}、{玉米,id3}

两种索引优缺点

索引 优点 缺点
正排索引 易维护、构建方便 搜索耗时长
倒排索引 搜索耗时短 构建耗时、维护成本较高

5.安全最近邻算法(kNN)

KNN(k-nearest neighbour):就是 K 个最近的邻居的意思,说的是每个样本都可以用它最接近的 K 个邻近值来代表

安全K最近邻计算是 Wong 等人在2009年论文 Secure kNN computation on encrypted databases 提出的,用于计算两个加密数据库记录之间的距离。在一个安全的 KNN 计算中,所有的数据库记录都被扩展到 m 维的向量,并由 m位的向量 S 和两个 m × m 可逆矩阵 M1 和 M2 加密。

举个🌰

下图中,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?
KNN的算法过程是是这样的:

  • 最小的圈K=3,第二个圈K=5
  • 如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形。
  • 如果K=5,那么离绿色点最近的有2个红色三角形和3个蓝色的正方形,这5个点投票,于是绿色的这个待分类点属于蓝色的正方形。

6.词频-逆文档频度(TF-IDF)

词频-逆文档频度(Term Frequency - Inverse Document Frequency)是一种用于信息检索文本挖掘的常用加权技术,用来评估一个词对于一个文档集或语料库中某个文档的重要程度,主要用在自动提取关键词算法中。

词频 (TF)

指的是某一个给定的词语在该文件中出现的次数。

逆文档频率(IDF)

以统计一篇文档的关键词为例,最简单的方法就是计算每个词的词频,出现频率最高的词就是这篇文档的关键词,但是一篇文章中出现频率最高的词肯定是“的”、“是”、“在”……这样的词,这些词显然不能反应文章的意思,此时就需要对每个词加一个权重,最常见的词(”的”、”是”、”在”)给予最小的权重,较少见的但能反应这篇文章意思的词给予较大的权重,这个权重叫做逆文档频率

IDF 是一个词语普遍重要性的度量。如果一个词越常见,那么分母就越大,逆文档频率就越小越接近0。分母之所以要加1,是为了避免分母为0(即所有文档都不包含该词)。

TF-IDF

知道了 TF 和 IDF 以后,将这两个值相乘,就得到了一个词的 TF-IDF 值。某个词对文章的重要性越高,它的 TF-IDF 值就越大。所以,排在最前面的几个词,就是这篇文章的关键词。

可以看到,TF-IDF 与一个词在文档中的出现次数成正比,与该词在整个语言中的出现次数成反比。所以,自动提取关键词的算法就很清楚了,就是计算出文档的每个词的 TF-IDF 值,然后按降序排列,取排在最前面的几个词。

总结

字词的重要性随着它在文件中出现的次数成正比增加 ,但同时会随着它在语料库中出现的频率成反比下降 。如果某个词比较少见,但是它在这篇文章中多次出现,那么它很可能就反映了这篇文章的特性,正是我们所需要的关键词。

TF-IDF详细内容请看:TF-IDF(词频-逆文档频率)介绍


7.波特词干算法(Porter stem)

从数据集中提取出的关键字集合进行“词根” 过滤,例如“walks”、“walking”、“walked”等近似的关键字,词根均为“walk”。后续的检索操作基于词根进行,大幅减少了计算量,且由于该操作只是在索引生成时执行一次,对整个系统的运行效率不会产生过大的影响。

8.分词算法(N-gram)

N-gram 模型是一种语言模型(Language Model,LM),N-gram 的基本思想是将文本里面的内容按照字节进行大小为 N 的滑动窗口操作,形成了长度是 N 的字节片段序列。每个字节片段即为 gram 。

  • 当N=1 时称为 uni-gram
  • 当N=2 时称为 bi-gram
    • P(我帮你) = P(我) * P(帮|我) * P(你|帮)
    • {“我帮”:1, “帮你”:2, “你帮”:3, “帮我”:4}
    • 我帮你→[1,1,0,0]
    • 你帮我→[0,0,1,1]
  • 当N=3 时称为 tri-gram

例如输入为西安交通大学

  • uni-gram 形式为:西/安/交/通/大/学

  • big-ram形式为: 西安/安交/交通/通大/大学

  • tri-gram形式为:西安交/安交通/交通大/通大学

中文文本处理大多采用 bi-gram 进行分解,因为双字词出现概率比较大,即以大小为2的滑动窗口进行操作,切成长度为 2 的字节片段。


9.Top-k检索

旨在获取相似度后,将其作为打分结果,根据匹配到的文件的分数,按照顺序返回给用户分数排名最高的K份数据,是搜索引擎中最常见的模式。简而言之,就是使用户快速找到最相关的 k 个结果。

10.向量内积(点乘)

  • a = [a1,a2,…,an]
  • b = [b1,b2,…bn]

a 和 b 的内积公式为:a∙b = a1b1 + a2b2 + … + anbn

内积的几何意义

内积的几何意义是可以用来表征或计算两个向量之间的夹角,以及在 b 向量在 a 向量方向上的投影。

11.PRF&PRP

PRP(pseudo random permutation,伪随机置换)和PRF(pseudo random function,伪随机函数)之间的区别,可以从定义来看

PRF

  • F:K × X → Y

取一个密钥和集合 X 中的元素作为输入,输出值在集合 Y 中,现在唯一要求的是存在一个有效的算法来实现这个函数。也就是说,要有一个有效的函数来实现 K × X → Y 的映射。

PRP

  • E:K × X → X
  • 存在求解 E(K,X) 的高效确定性算法
  • 函数 E(k,·) 是一对一的
  • 存在高效的“逆算法” D(K,X)

与 PRF 不同的是,多了一个条件,那就是要有一个算法 D 可以实现逆运算。

在PRP中,存在一个有效算法,能够实现 K × X → X 映射关系,也就是说该算法能够将随机密钥 K 与集合 X 中的元素作为输入,同时输出值也是集合 X 中的元素,那么就要求每个元素一一对应。从本质上来说,E(K,X) 是对元素 x 的置换,为了解密的需要,就要求 E 是可逆的。

12.Homomorphic MAC

同态MAC:任何消息 mi 被加密为一个 degree-1 多项式 y(x)

  • 即 y(0) = mi 和 y(α) = γi,其中 α 和 γi 只有验证者知道
  • 即 y(x) = mi + ( γi −mi)∙x/α 成立。
  • 由于云服务器在计算函数 f 时需要进行一些基本的算术运算,因此需要引入同态加密,对加密后的数据进行直接计算。
    • f(γ1,···, γn) = y(α) —①
    • f(m1 ,···, mn) = y(0) —②
  • 在方程①建立的条件下,验证器可以验证方程②。因此,该技术可以验证云服务器是否诚实地执行用户定义的搜索算法

由于传统同态 MAC 仅支持有限域的计算,论文 VRFMS 采用了 realhomm-MAC,realhomm-MAC 的改进是将所有消息作为实数来处理,其编码格式类似于 IEEE 754 标准中定义的双精度浮点格式。也就是说,新算法在保留原算法同态的前提下能够处理实数。

Sponsor❤️

您的支持是我不断前进的动力,如果你觉得本文对你有帮助,你可以请我喝一杯冰可乐!嘻嘻🤭

支付宝支付 微信支付

文章作者: 简简
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 简简 !
评论
填上邮箱会收到评论回复提醒哦!!!
 上一篇
Java-学习路线 Java-学习路线
哈喽,大家好呀!安全出身的小简做出了人生中又一重大的决定,那就是从安全方向逐渐转为开发方向,小简自己也纠结了很久,尽管知道这样会很难,但最终还是做下了这个决定,至于原因嘛,应该是我对开发更有兴趣一些,也想去尝试一些新的东西,当然我也不是完全
2022-02-01
下一篇 
版本管理-Git 版本管理-Git
一直只会常用的那几个 Git 命令,每次遇到不会的操作都是现去Google,十分不方便,今个得空咋就仔仔细细的学习学习 Git ! Git简介 Git是目前世界上最先进的分布式版本控制系统。 工作流程 工作区:你在电脑里能看到的目录。
2022-01-05
  目录