Searchable Encryption
Searchable Encryption
对称可搜索加密 SSE
1. Practical Techniques for Searches on Encrypted Data
Dawn Xiaodong Song, David Wagner, Adrian Perrig
University of California, Berkeley
2000年S&P
对称可搜索加密(Symmetric Searchable Encryption,SSE)
第一篇可搜索加密的论文,总结概括下来就是摘要里的这几句话:
“untrusted server cannot learn anything about the plaintext when only given the ciphertext”
”untrusted server cannot learn anything more about the plaintext than the search result“
“untrusted server cannot search for an arbitrary word without the user’s authorization”
“user may ask the untrusted server to search for a secret word without revealing the word to the server”
论文从一个basic scheme开始,逐步改进,最终提出自己的方法
(1) Basic Scheme
Alice将一个文档分割(可以按照段落分、按照句子分、按照单词分、按照任意长度bit分),这些单元叫做
加密的方法是用一个G(伪随机生成器)生成的随机数据流
这里的
是用户自己挑选的,可以全是一样的,也可以不一样
这时Alice想查询W,要告诉服务器W和W可能出现在哪里(也就是一堆
缺点:这并不是全文搜索,而是从Alice给出的一个小范围内进行搜索,如果给的范围大了就会泄露更多的信息。
(2) Controlled Searching
上面这个只能在一个小范围内进行搜索的原因是,服务器没法知道查询的这个W的密文长什么样,不得不给他一个解密的范围
用一个新的伪随机生成函数
这样的好处是服务器可以根据W算出来T,(用户也就知道每个明文的密钥是谁,不再像前面那个密钥和明文对不上)因此可以对明文为W的密文进行解密,明文不是W时这个密钥也不好使
缺点:还是一个明文搜索,需要传过去明文W
(3) Hidden Searching
首先对明文进行加密,使用ECB模式的分组密码,把每一个单元都加密从
(4) Final Scheme
3中的问题在于,服务器搜索出来一堆
加密时把X分为左右两部分(左半部分和S相同长度)
这时查询返回来一个
然后用得到的
2. Secure Indexes
2003年,作者Eu-Jin Goh,斯坦福大学
https://eprint.iacr.org/2003/216.pdf
和第1篇Song的文章一样,也是一个SSE,主要思想在于提出了一个基于索引的可搜索加密,在Song的文章中没有涉及关于“服务器如何查找”这方面的内容。
他们提出了Z-IDX,是一种基于Bloom过滤器的安全索引机制,它允许用户在不泄露文件内容的情况下,对加密的文件执行关键词搜索。
初始化Bloom过滤器:对于每个文件,初始化一个m位的二进制向量(Mem),所有位初始设为0。这个向量将用于构建Bloom过滤器,用于跟踪文件中的关键词。
选择哈希函数族:定义一个哈希函数族
,其中每个 函数将输入映射到{1, 2, …, m}的整数范围内。这些函数用于将关键词映射到Bloom过滤器的位上。构建索引:
- 对于文件中的每个关键词
,首先使用伪随机函数族 生成一个代码字(codeword)。这里的 是主密钥 的子密钥。 - 然后,对于每个生成的
(伪随机函数输出结果),使用另一个伪随机函数 ,其中id是文件的唯一标识符,生成最终的码字 。 - 将码字的每个位
映射到Bloom过滤器的相应位置,如果位置为0,则将其置为1。 - 为了增加安全性,还会向Bloom过滤器中随机插入若干个1,这样即使攻击者知道某些关键词的存在,也无法准确判断出文件中确切的关键词数量。
构建索引的过程就是:关键词通过两次伪随机函数作用形成codeword存储于索引中
第1次伪随机函数以关键词
为输入,分别在子密钥 作用下生成 ; 第2次伪随机函数分别以
为输入,在当前文件标识符id作用下生成码字 确保了相同关键词在不同文件中形成不同码字.
当用户想要搜索文件
服务器基于
服务器判断
缺点
空间代价上,服务器除存储密文文件本身外,还需记录文件索引,当文件较短时,其索引可能是文件长度的数倍,空间利用率较低;时间代价上,服务器检索需逐个文件地计算和判断,整个关键词查询操作时间消耗为O(n)(n为服务器上存储文件数目)
3. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions
作者:Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky
发表在CCS 2006上
https://eprint.iacr.org/2006/210.pdf
这篇文章和第2个类似,都是在服务器上构建索引来查找
索引构建
首先扫描全部文档
创建一个链表,每个节点都代表
节点的表示为:
目的是用
这一个链表的每一项的加密结果存在一个数组里,叫做数组A。
即
构建一个速查表
即
查询
用户查询包含
这个方法避免了查询关键词时需要便利每个文件进行检索的缺陷
非对称可搜索加密 ASE
1. Public Key Encryption with Keyword Search
Dan Boneh,Giovanni Di Crescenzo,Rafail Ostrovsky,Giuseppe Persiano
Stanford University
2004年欧密 International Conference on the Theory and Applications of Cryptographic Techniques
非对称可搜索加密(asymmetric searchable encryption,ASE)
处理多个用户使用同一个服务器的情况时比较方便
场景假设:Bob用Alice的公钥加密了一个邮件,在这段密文之后拼接了几个加密的关键词:
这个邮件存在服务器上,Alice可以通过发送一个
服务器是如何检验的
双线性映射(Bilinear Map)是一种特殊的函数,它在两个循环群的元素之间定义,并且满足以下性质:
- 可计算性:给定两个群元,可以有效地计算它们的双线性映射。
- 双线性:对于所有群元g1,g2∈G1和所有整数x,y,有
。 - 非退化性:如果g是G1的生成元,则e*(*g,g)是G2的生成元。
服务器接收一个加密的关键词
计算
依赖的难题是计算性Diffie-Hellman问题(Computational Diffie-Hellman Problem,简称CDH):给定循环群G1中的生成元g和
关键词的布尔表达式检索
Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries
David Cash 等,Rutgers University
2013年,International Cryptology Conference
也是对称可搜索加密,但是支持连接搜索和一般的布尔查询
场景描述:一个数据库(比如一个邮件服务器)
EDBSetup
初始化:
对于每个
-
对关键词进行了加密 - 对于
相关的所有ind 作为 的伪随机表示, ,c是与w相关的文档计数器,z是生成的盲化因子 ,把 加到 中 ,加到 中
输出
EDB就是给服务器存储的一种加密之后的DB,存储与关键词相关联的数据元组,XSet存的辅助后面搜索的信息
Search
客户端有一个
把e(stag, xtoken[1], xtoken[2],…) 发送给服务器
服务器计算
客户端计算