可搜索加密技术，你学会了吗？
一、绪论
随着云服务的快速发展，越来越多的用户将个人数据存储在云服务器上，这在方便自身的同时也导致了数据泄露事件的增加。为了保护数据隐私，加密技术成为了当下的重要手段。然而，随着数据的增多和分散，传统的加密方式已经不能满足大规模数据的使用需求。在这种情况下，可搜索加密（Searchable Encryption, SE）技术应运而生。
可搜索加密技术是一种新兴的密文检索方式，它可以在不暴露明文的情况下，将数据进行加密后存储到云端，然后对密文进行查询。为了实现加密数据检索，Song等人[1]利用对称加密算法加密关键词，并用关键词密文与流密文异或的方式加密数据信息获得Ciphertext，实现方式如图1-1所示。当需要查询关键词时，用户可以先生成一个流密文A，然后用查询关键词密文和存储的Ciphertext进行异或获得流密文B。若流密文A与流密文B相同，则表示检索成功，反之则表示检索失败。
图1-1 密文检索实现方案
之后，又有人提出了使用安全索引的可搜索加密[2]、基于非对称加密算法的公钥可搜索加密[3]、支持模糊检索的模糊可搜索加密[4]等方案。当前的可搜索加密主要研究属性如图1-2。
图1-2 可搜索加密主要研究属性
随着可搜索加密技术的发展，人们能够更加方便地进行数据检索和共享，同时避免了敏感数据被恶意泄露和滥用的风险。按照实现方式，可搜索加密技术可以分为对称可搜索加密（Symmetric searchable encryption, SSE）和非对称可搜索加密（Asymmetric searchable encryption, ASE），下文也将从这两个角度进行介绍。
二、对称可搜索加密技术
对称可搜索加密主要依靠对称加密算法实现，其基本操作包括初始化、数据加密、陷门生成、搜索和数据解密等[5]。在对称可搜索加密技术中，加密和解密过程使用相同的密钥，陷门生成也需要密钥的参与。因此，该技术通常适用于单用户模型，具有计算开销小、实现简单和执行速度快的特点。
在Song等人提出第一个对称可搜索加密方案后，陆续有人对其进行了改进。在2019年，Kermanshahi等人[6]提出了一种基于单用户协议的多客户端对称可搜索加密方案。该方案允许用户通过与一定数量的“帮助”用户来生成查询，保护数据库内容不会被服务器泄露，同时隐藏查询内容不被“帮助”用户知晓。通过伪随机函数，可以实现对搜索关键字的隐私保护。另外，该方案支持用户撤销和快速更新加密密钥，并对服务器和子集用户之间的被动和主动串通攻击提供安全保障。在Zheng[7]的研究工作中，针对现有的动态可搜索加密方案无法保护搜索模式隐私，导致泄漏部分关键信息的问题，他们首先利用k-匿名和加密技术设计了一个混淆技术。假设存储在服务器中的索引为键值对，每个键值对关联一个关键词w，c表示加密的文件ID，loc表示c的存储位置，混淆技术的实现方式如图2-1所示。然后，基于混淆技术、伪随机函数和伪随机生成器，Zheng等人设计了一个动态可搜索加密方案。该方案支持单关键字查询，同时实现了搜索模式隐私和增强后向隐私。此外，该方案还扩展到支持更有效的布尔查询。安全分析表明，该方案能够实现所需的隐私属性，并且在通信开销和计算成本方面也是高效的。
图2-1 k=3时的混淆方式
Wang [8]则实现了一种支持搜索结果验证的对称可搜索加密技术。在使用Trie树构造索引的方案中，可以通过将每个关键字标签分段并将它们存储在Trie树中来提高搜索性能，但这也带来了高存储的代价。另外，当所有关键字标签的前缀相同，但最后一个段不同时，索引还将退化为线性链表，极大地影响了搜索效率。为了解决这个问题，他们提出了一种基于AVL树的可验证对称可搜索加密方案，简称VSSE-AVL。与Trie树索引相比，VSSE-AVL不仅平衡了存储和搜索性能，而且避免了退化现象。安全分析表明，VSSE-AVL满足隐私和可验证性，并且与其他具有相同安全性的可验证可搜索加密方案相比，该方案在存储、搜索和验证方面的表现均更好。
三、非对称可搜索加密技术
非对称可搜索加密主要依靠非对称加密算法实现，也称为公钥可搜索加密（Public key encryption with searching, PEKS），其基本操作包括初始化、公钥加密数据、私钥生成陷门和搜索等[3]。在非对称可搜索加密技术中，加解密过程采用公钥对明文信息加密和目标密文的检索，使用私钥解密密文信息和生成关键词陷门。相比对称可搜索加密，非对称可搜索加密算法较为复杂，加解密速度较慢，通常适用于多对一模型。
在Zhang[9]的工作中，就提出了一种安全的公钥加密关键字搜索方案，称为SEPSE。该方案采用多个专用密钥服务器，协助用户加密关键词，而不会学习任何关键词信息。同时，SEPSE支持在密钥服务器上进行密钥更新，以抵御密钥泄露。此外，他们还提出了一种基于区块链的速率限制机制，并将其集成到SEPSE中。每个用户由服务器派生的关键词请求被集成到公共区块链上的一个交易中，密钥服务器可以通过检查由该用户创建的交易数量来检查该用户的关键词请求数量，并在达到阈值后停止响应，以抵御在线关键词攻击。之后，为了解决大多数公钥加密可搜索加密方案不适用于多用户场景的问题，Chenam[10]等人提出了一种基于指定云服务器的多用户无证书公钥认证加密与联合关键词搜索方案（dmCLPAECKS）。该方案保证了相同的文档或电子邮件只需加密一次，就可以被不同的接收者检索，且支持联合关键词搜索。dmCLPAECKS的实现框架如图3-1所示。
图3-1 dmCLPAECKS的框架图
由于采用了认证加密技术，该方案可以防止攻击者在不知道数据所有者的私钥的情况下伪造有效的密文并发送给数据接收者。此外，该方案采用了指定云服务器技术，即使攻击者检索到数据接收者的陷门，也无法执行关键词搜索，因为攻击者不知道指定云服务器的私钥。基于此，该方案可以在随机预言模型下防止内部关键词猜测攻击。
四、安全威胁和防御方式
4.1 关键词猜测攻击
关键词猜测攻击[11]是由于关键词空间远小于密钥空间，并且用户通常使用常用关键词进行检索，这为攻击者提供了一个字典攻击的“捷径”。导致关键词猜测攻击的原因可归结为：
（1）关键词空间较小，且用户集中于使用常用词汇，给攻击者提供了遍历关键词空间的可能；
（2）算法一致性约束，使攻击者拥有对本次攻击是否成功的预先判定：执行Test算法，返回1说明本次攻击成功；否则，可以再继续猜测。
预防措施：为了抵御关键字猜测攻击，先后有人提出了多种抗关键字猜测攻击的可搜索加密方案[9,10]。通过限制查询请求频率或用户查询能力等方式，防止恶意敌手猜测出准确的关键字。
4.2文件注入攻击
在执行文件注入攻击[12]时，攻击者会向客户端发送一些文件，然后客户端会将这些文件使用可搜索加密方案进行加密并上传至服务器。攻击者可以通过注入少量的文件来了解客户端所搜索的大量关键词。这是一种比较隐蔽的攻击方式，因为攻击者并不需要直接获取到客户端的私钥或者陷门，而只需要观察客户端上传的加密文件即可。图4-1说明了文件注入攻击的思想。
图4-1 |K|=8时文件注入攻击用例
假设关键字集合K中有8个关键字，攻击者注入文件File1、File2、File3，每个文件都包含4个关键字，即图中阴影部分。如果File2响应某个令牌而返回，但File1和File3未返回，则该令牌对应的关键字是k2。基本的观察结果是，如果服务器注入一个文件F，其中恰好包含关键字集合K中的一半关键字，那么通过观察客户端发送的令牌t是否与之匹配文件，服务器可以学习关于t对应的关键字的一位信息。基于此，通过注入少量文件，服务器就能准确地确定关键字。
预防措施：Bost等人先后提出了前向隐私[13]和后向隐私[14]的概念以及实现方案。通过减少文件更新和历史查询信息泄露，避免了用户遭受文件注入攻击的风险。
五、总结
可搜索加密技术具有广泛的应用场景，可以在保护数据隐私的同时，实现高效的数据搜索和管理。在云计算领域，可搜索加密技术可以帮助用户在云中存储和管理敏感数据，同时保护数据隐私。在数据共享领域，可搜索加密技术可以提供更佳的数据安全性和隐私保护能力，同时实现高效的数据检索和共享。在位置隐私保护领域，可搜索加密技术可以帮助用户在保护个人位置隐私的同时，获得需要的服务和信息。
尽管可搜索加密技术已经取得了显著的进展，但仍然存在一些改进方向。例如，现有的可搜索加密技术仍然存在一些安全漏洞，需要研究新的算法和协议来提高可搜索加密技术的安全性和隐私保护能力。此外，现有的可搜索加密技术在性能方面还存在一些限制，需要研究新的技术和算法，以提高可搜索加密技术的性能和效率。最后，还可以将可搜索加密技术与其他安全技术，如区块链、差分隐私等相结合，以更好地满足实际应用的需求。
参考文献
[1] Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C]//Proceeding 2000 IEEE symposium on security and privacy. S&P 2000. IEEE, 2000: 44-55.
[2] Goh E J. Secure indexes[J]. Cryptology ePrint Archive, 2003.
[3] Boneh D, Di Crescenzo G, Ostrovsky R, et al. Public key encryption with keyword search[C]//Advances in Cryptology-EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 2004: 506-522.
[4] Li J, Wang Q, Wang C, et al. Enabling efficient fuzzy keyword search over encrypted data in cloud computing[J]. Cryptology ePrint Archive, 2009.
[5] Curtmola R, Garay J, Kamara S, et al. Searchable symmetric encryption: improved definitions and efficient constructions[C]//Proceedings of the 13th ACM conference on Computer and communications security. 2006: 79-88.
[6] Kermanshahi S K, Liu J K, Steinfeld R, et al. Multi-client cloud-based symmetric searchable encryption[J]. IEEE Transactions on Dependable and Secure Computing, 2019, 18(5): 2419-2437.
[7] Zheng Y, Lu R, Shao J, et al. Achieving practical symmetric searchable encryption with search pattern privacy over cloud[J]. IEEE Transactions on Services Computing, 2020, 15(3): 1358-1370.
[8] Wang Q, Zhang X, Qin J, et al. A verifiable symmetric searchable encryption scheme based on the AVL tree[J]. The Computer Journal, 2023, 66(1): 174-183.
[9] Zhang Y, Xu C, Ni J, et al. Blockchain-assisted public-key encryption with keyword search against keyword guessing attacks for cloud storage[J]. IEEE Transactions on Cloud Computing, 2019, 9(4): 1335-1348.
[10] Chenam V B, Ali S T. A designated cloud server-based multi-user certificateless public key authenticated encryption with conjunctive keyword search against IKGA[J]. Computer Standards & Interfaces, 2022, 81: 103603.
[11] Byun J W, Rhee H S, Park H A, et al. Off-line keyword guessing attacks on recent keyword search schemes over encrypted data[C]//Secure Data Management: Third VLDB Workshop. Springer Berlin Heidelberg, 2006: 75-83.
[12] Zhang Y, Katz J, Papamanthou C. All your queries are belong to us: The power of file-injection attacks on searchable encryption[C]//USENIX Security Symposium. 2016: 707-720.
[13] Bost R. ∑ oφoς: Forward secure searchable encryption[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 1143-1154.
[14] Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 1465-1482.
