Σoφoς:简单但有效的前向安全对称可搜索加密
本文是阅读了论文[1]之后写的笔记,为了能对论文提出的方案和核心思想有更透彻的了解。
0. 一些定义
可搜索加密
Searchable Encryption, SE
当数据存储在一个不可信的服务器时,为了让服务器不能够了解到数据内容,需要对数据加密后再存储。为了实现在加密后的数据上进行关键词检索,提出了可搜索加密的思想。
对称可搜索加密
SE分为两种:对称可搜索加密(Symmetric Searchable Encryption, SSE)和非对称可搜索加密(Asymmetric Searchable Encryption, ASE),后者也称公钥可搜索加密(Public Key Encryption With Searching, PEKS)。两者的区别在于前者使用对称加密算法,加密和解密的密钥一样;后者使用非对称加密算法。
SSE相比于ASE,优势在于计算开销小、算法简单、速度快。通常使用在单用户模型中,检索方和数据拥有者是同一个。
前向安全
forward privacy/security
通俗来说,前向安全是指更新操作不会泄露之前的查询的信息,也就是说,服务器不知道更新的关键字是否在之前被查询过。
形式化的定义在论文的4.1节给出了。
与之相对的是后向安全。简单来说,是指如果一个关键字/文档对(w, ind)已经被删除,那么之后的在关键字w上进行的搜索都不能包含这个ind。形式化的定义在Bost等人于2017年的一篇论文[2]中给出了,这篇论文提出的几个方案都是基于Σoφoς实现的。
陷门置换
TrapDoor Permutation, TDP
本文方案的核心思想之一。如第四节中的图1所示,简单来说就是,在搜索令牌序列中,服务器可以从后往前(从已有的到最早的)计算ST,而只有用户可以从前往后生成(从最新的生成更新的),以控制服务器可以搜索的索引范围,确保前向安全。
1. 核心思想
旧的搜索令牌不能用于搜索新添加的文档,因此保证了前向安全。
为每个关键字/文档对(w, ind)生成对应的搜索令牌(search token, ST),每个关键字w对应一个令牌序列, . 初始时令为一个随机数,c=-1;以后每当添加了一个w上的对(w, ind),就用生成,同时c自增1.这个过程只能由用户使用陷门密钥SK进行。而为了减少存储开销,TDP应该满足这样的要求:使用公钥PK可以很方便地从计算,而只有使用密钥SK才能从计算,这样用户和服务器都只需要存储;当需要检索时,用户把最新的发给服务器。
2. 具体方案
方案伪代码如下图所示,即Σoφoς-B。这个方案只能实现对文档的添加;不过想要实现删除也很容易,只需要再增加一个Σoφoς-B实例用于删除,每当一个删除操作到达,把对应的(w, ind)添加到删除实例中,并在返回搜索结果时返回两个实例的差。但需要注意的是,这样从用户的角度来看,(w, ind)已经从数据库中删除;但对服务器来说它还存在,因此并不能实现后向安全。想要实现后向安全,即对服务器来说删除的(w, ind)不存在于数据库中,还需要一些其他的技术,比如穿刺加密。
方案主要使用了两个映射W、T和两个哈希函数H1、H2。
-
H1:使用公钥和搜索令牌ST作为输入,输出一个与ST对应的长度为μ的更新令牌UT。
-
H2:使用公钥和搜索令牌ST作为输入,输出一个与ST对应的长度为l的位串。l是ind的长度。
-
W:用户使用的映射,它把关键字w映射到对应的搜索令牌和一个整数,其中是关键字的数量。如果不存在这样的ST和c,则随机生成一个,设c为-1。需要注意,w对应的ST并不是只有一个,而是有一个序列。为了节省开销,只存储了一个最新的。
-
T:服务器使用的映射,它把更新令牌映射到对应的索引加密e。e是ind和的异或,也就是加密形式的索引ind。当需要取出ind时,只需要计算和,并把结果相异或。
[1] Σoφoς – Forward Secure Searchable Encryption, Bost R. CCS 2016
[2] Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives, Bost R. et al. CCS 2017