论文 | 可搜索加密 · 开山之作

谨以此文，献给中华人民海军！生日快乐！
人民海军成立71周年，我的海洋我的舰！

搜索加密数据的实用技术-2000

本文系「人工智能安全」（微信公众号）原创，转载请联系本文作者（同博客作者）。
欢迎你转发分享至朋友圈，并给予「关注、星标、点赞」三连支持。互相欣赏，互相批判。

今天，你和我共读的一篇文章，她是可搜索加密的开山之作「Practical techniques for searches on encrypted data」。她首次研究用于支持加密数据搜索的密码技术，并由此开辟了密码学中的一个全新的研究方向「Searchable Encryption」。同时，该方向也受到学术界和工业界的持续密切关注。那么，她是如何实现「加密数据搜索」的呢？让我们一起来揭晓答案。

01 论文基本介绍

一、论文信息

作者姓名：Dawn Xiaoding Song, D. Wagner, and A. Perrig.

作者单位：University of California, Berkeley

作者通讯：{dawnsong, daw, perrig}@cs.berkeley.edu

发表刊物：Proceedings of the 2000 IEEE Symposium on Security and Privacy（国际顶级会议，中国计算机学会（CCF）推荐的 A 类网络与信息安全国际学术会议）

发表时间：2000 年 5 月

被引次数：3374（截至2020年4月23日，来源：Google Scholar）

二、摘要导读

我们期望将数据以加密的形式存储在诸如邮件服务器和文件服务器之类的数据存储服务器上，以提高数据的安全性和降低隐私泄露的风险。但这通常意味着必须为安全而牺牲某些功能（如搜索功能）。

例如，如果数据存储服务的用户只希望检索包含某些单词（关键词）的文档，则以前的工作不知道该如何让数据存储服务器执行搜索并回应用户的查询（返回与查询相关的加密文档），而又不会损害数据的机密性。

本文描述了针对加密数据搜索问题的密码方案，并给出方案的安全性证明。同时，经过分析表明，所提出的技术具有多项关键优势，并且这些技术是「可证明安全的」。具体如下：

（1）为加密提供了可证明的机密性，从某种意义上讲，对不受信任的服务器仅给出密文，它就无法或难以学习到有关明文的任何信息；

（2）为搜索提供查询隔离，这意味着不受信任的服务器除了搜索结果之外，无法了解到更多有关纯文本的信息；

（3）提供受控的搜索，因此不受信任的服务器无法在未经用户授权的情况下搜索任意单词；

（4）支持隐藏查询，因此用户可以要求不受信任的服务器搜索私密的单词，而无需向服务器透露该单词；

（5）所提出的算法简单而快速，对于长度为 n 的文档，加密和搜索算法仅需要 O(n) 个流密码和分组密码操作。并且几乎不引入空间和通信开销，因此这项技术是很实用的。（Jack：至少在 2000 年的时候是很实用的。）

02 论文核心内容

一、模型方法

Song 等人于 2000 年提出了第一个实用的可搜索加密方案 SWP。该方案通过使用特殊的两层加密结构来搜索加密数据，该结构允许使用顺序扫描来搜索密文。核心的想法是分别加密每个单词，然后将一个哈希值（具有特殊格式）嵌入密文中。为了进行搜索，服务器可以提取该哈希值并检查该值是否具有这种特殊格式（表示查询与加密数据的匹配）。

如图（a）所示，为了创建可搜索的密文，我们将消息拆分为固定大小的单词 并使用确定性加密算法 进行加密，必须使用确定性加密才能生成正确的陷门（Trapdoor）。然后将加密的单词 分为两部分 。借助流密码产生伪随机值 。使用伪随机函数 计算得到密钥 ，用于键控哈希函数 来对值 做哈希运算。这样操作的所得到结果是 ，用于将 加密为 ，其中 表示 XOR（异或）。

（Jack：如果微信能支持「LaTeX」就更完美了，这样我就可以直接写代码，然后输出漂亮的数学公式嵌入文中。这不，刚说完，来牛客就完美啦啊！竟然支持！非常的Amazing啊！）

为了实现搜索功能，我们需要一个陷门。该陷门包含用于搜索 的加密关键词，并且与密钥 相对应。有了这个陷***器就可以通过检查所有存储的密文 来搜索（如图（b）所示），如果 是 的 形式，则找到了关键字，从而也就可以找到与查询相关的加密文档。

二、效率分析

对于 SWP 方案，其加密算法和搜索算法的复杂度与每个文档的单词总数呈线性关系（即最坏的情况，需要全部遍历）。在执行加密操作时，必须为每个文档的每个单词计算一个加密，一个 XOR 和两个伪随机函数。陷门需要一个加密和一个伪随机函数。该方案的搜索需要每个文档每个单词一个 XOR 和一个伪随机函数。

三、安全性分析

SWP 是第一个可搜索加密方案，并且当时还没有正式的可搜索加密安全定义用于对做它安全性分析。但是，在基础元（如伪随机函数）被证明是安全或存在的假设下，SWP 是 IND-CPA 安全的。由于 IND-CPA 安全性不考虑查询，故对于可搜索加密而言，这项优势不大。SWP 泄漏了文档中查询关键字的潜在位置（如考虑到由于冲突导致的假阳性率），可能发生匹配的位置。在几次查询后，可以通过统计分析来学习文档中的单词。

03 论文精彩点评

SWP 方案的最大缺点是它必须使用固定大小的单词，与现有的文件加密标准不兼容，并且必须使用其特定的两层加密方法，该方法只能用于纯文本数据，而不能用于其他数据，如压缩数据。

虽然这项工作在今天看来，显然是难以满足丰富而严格的「安全性定义」。但应该注意到，正是她引起了业界对「加密数据搜索」的关注以及一系列经久不衰的研究。她在可搜索加密中开辟山头的地位，不可撼动。毕竟，任何做可搜索加密的学者，绝对不会不知道「Song 2000」，其影响力之大可见一斑。

此外，更重要的是，我们得到一个启示——「开创一种新方法或需要建设性的改进和关联性的锐思，但开辟一个新方向则需要变革性的创新和前瞻性的视野」。

为什么目前许多开创性的、核心的科学技术是在西方国家诞生的？难道我们国家培养不出创造、发展这些高新科技的杰出人才？「中国从最大的发展中国家走向最强大的发达国家，成为科技强国是充分必要条件」。中华伟大复兴使命，吾辈要勇于担当。

最后，留给你一道思考题。

钱学森之问：为什么我们的学校总是培养不出杰出人才？

恭喜你：你即将完成「四千字」的阅读量！快给自己点个赞吧！文末有惊喜哦！

参考文献

[1] Song, D.X., Wagner, D.A., Perrig, A.: Practical techniques for searches on encrypted data. In: Proceedings of the 2000 IEEE Symposium on Security and Privacy, S&P 2000, Berkeley, California, USA, May 14-17, 2000. pp. 44-55. IEEE Computer Society (2000).

推荐阅读

可搜索对称加密
[**] Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: Juels, A., Wright, R.N., di Vimercati, S.D.C. (eds.) Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, October 30 - November 3, 2006. pp. 79–88. ACM (2006).

动态的可搜索对称加密
[**] Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) Proceedings of the 19th ACM Conference on Computer and Communications Security, CCS 2012, Raleigh, NC, USA, October 16-18, 2012. pp. 965-976. ACM (2012).

带有关键词搜索的公钥加密
[**] Boneh, D., Crescenzo, G.D., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J. (eds.) Proceedings of the 19th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2004, Interlaken, Switzerland, May 2-6, 2004. Lecture Notes in Computer Science, vol. 3027, pp. 506-522. Springer (2004).

支持多关键词排名搜索的可搜索对称加密
[**] Cao, N., Wang, C., Li, M., Ren, K., jing. Lou, W.: Privacy-preserving multi-keyword ranked search over encrypted cloud data. In: Proceedings of the 30th IEEE International Conference on Computer Communications, INFOCOM 2011, Joint Conference of the IEEE Computer and Communications Societies, Shanghai, China, April 10-15,2011. pp. 829–837. IEEE (2011).

更多阅读
Searchable Encryption ——> https://dblp.uni-trier.de/

作者：水木清华

致力于人工智能与网络空间安全交叉融合研究事业，努力于服务国家安全战略。

©2020 AI-security

关注「人工智能安全」，我们一起学习和成长。

温馨提示：关注「人工智能安全」在后台回复「可搜索加密开山之作」，火速获取硬核的学习资讯。欢迎「点赞收藏关注」三连。