Σ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_0, ST_1, cdots, ST_c中,服务器可以从后往前(从已有的ST_c到​​​​​​​最早的ST_0)计算ST,而只有用户可以从前往后生成(从最新的ST_c生成更新的ST_{c+1}),以控制服务器可以搜索的索引范围,确保前向安全。

1. 核心思想

旧的搜索令牌不能用于搜索新添加的文档,因此保证了前向安全。

为每个关键字/文档对(w, ind)生成对应的搜索令牌(search token, ST),每个关键字w对应一个令牌序列ST_0, ST_1, cdots, ST_c, c=n_w-1. 初始时令ST_0为一个随机数,c=-1;以后每当添加了一个w上的对(w, ind),就用ST_c生成ST_{c+1},同时c自增1.这个过程只能由用户使用陷门密钥SK进行。而为了减少存储开销,TDP应该满足这样的要求:使用公钥PK可以很方便地从ST_i计算ST_{i-1},而只有使用密钥SK才能从ST_i计算ST_{i+1},这样用户和服务器都只需要存储ST_c;当需要检索时,用户把最新的ST_c发给服务器。 

2. 具体方案

方案伪代码如下图所示,即Σoφoς-B。这个方案只能实现对文档的添加;不过想要实现删除也很容易,只需要再增加一个Σoφoς-B实例用于删除,每当一个删除操作到达,把对应的(w, ind)添加到删除实例中,并在返回搜索结果时返回两个实例的差。但需要注意的是,这样从用户的角度来看,(w, ind)已经从数据库中删除;但对服务器来说它还存在,因此并不能实现后向安全。想要实现后向安全,即对服务器来说删除的(w, ind)不存在于数据库中,还需要一些其他的技术,比如穿刺加密。

方案主要使用了两个映射W、T和两个哈希函数H1、H2。

  • H1:使用公钥K_w和搜索令牌ST作为输入,输出一个与ST对应的长度为μ的更新令牌UT。

  • H2:使用公钥K_w和搜索令牌ST作为输入,输出一个与ST对应的长度为l的位串。l是ind的长度。  

  • W:用户使用的映射,它把关键字w映射到对应的搜索令牌ST_c和一个整数c=n_w-1,其中n_w是关键字的数量。如果不存在这样的ST和c,则随机生成一个ST_0,设c为-1。需要注意,w对应的ST并不是只有一个,而是有一个序列。为了节省开销,只存储了一个最新的ST_c

  • T:服务器使用的映射,它把更新令牌UT_i映射到对应的索引加密e。e是ind和H2(K_w, ST_i)的异或,也就是加密形式的索引ind。当需要取出ind时,只需要计算H2(K_w, ST_i)T[UT_i],并把结果相异或。 

[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

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
)">
< <上一篇
下一篇>>