Page 439 - 《软件学报》2025年第8期

3862 软件学报 2025 年第 36 卷第 8 期

2 基础知识

本节就本文提出的 RFBC 方案中所涉及的相关概念和基本知识进行介绍.

2.1 伪随机函数
定义 1. 函数 f: {0, 1} ×X→Y 表示在安全参数 k 下集合 X 映射到集合 Y 的函数. 如果对于任意多项式时间敌
k
手 A, 等式
k
ADF prf (k) = |Pr[A f K (·) : K ← {0,1} ]−Pr[A s(·) : s ← F(x, y)]| ⩽ negl(k)
f, A
都不成立, 那么函数 f 是伪随机函数 (pseudo-random function, PRF), 其中 ADF prf (k) 表示在安全参数 k 下, 敌手 A
f, A
成功攻破函数 f 的概率, F 是随机函数, negl(k) 表示敌手 A 能够区分函数 f 的值与随机函数 F 的值的概率是可忽
略的.

2.2 布隆过滤器

布隆过滤器 (Bloom filter) [49] 是一种空间和时间高效的数据结构, 常用于快速检测一个元素是否在某个集合中.
布隆过滤器由 m 比特的数组和 j 个独立的哈希函数构成, 在初始化阶段, 数组的每一位均置 0. 给定集合
,
Y = {b 1 ,b 2 ,...,b n }, 调用哈希函数 H 0 ,H 1 ,...,H j−1 计算值 H i (b k ) ∈ [1,m], 其中 i ∈ [0, j−1] k ∈ [1,n], 并通过将数组中
第 H i (b k ) i ∈ [0, j−1] k ∈ [1,n]) 位设置为 1 将集合 Y 插入到布隆过滤器中. 当要检测元素 p 是否在集合中, 调用 j
,
(
,
个哈希函数得到 H i (p) i ∈ [0, j−1], 若数组中所有哈希值对应的位均为 1, 则元素 p 在集合 Y 中; 否则, 元素 p
不在集合 Y 中. 需注意的是, 布隆过滤器存在假阳性 (false positive), 即由于哈希函数的碰撞性以及位数组大小的
限制, 布隆过滤器判定属于集合的元素可能不在集合中, 但其能准确判断某个元素一定不在集合中. 布隆过滤器的
) 与集合的大小
误判率 y = (1−e (−jn)/m j n、哈希函数个数 j 及为数组大小 m 有关, 故可通过选取合适的参数获得可
接受的错误率.

2.3 对称加密
对称加密是一种加密和解密使用相同密钥的密码体制算法中, 常用的对称加密算法有 AES (advanced
encryption standard) 等. 在同等安全级别下, 对称加密算法的计算速度快于非对称加密, 被广泛应用于可搜索加
密中.
一个对称加密算法 SKE 主要包括密钥生成算法 Gen、加密算法 Enc 与解密算法 Dec, 即 SKE = (Gen, Enc,
Dec), 其中,
1) SKE.Gen: 给定安全参数 λ, 生成加密密钥 sk.
2) SKE.Enc: 在密钥 sk 的控制下对明文 m 进行加密, 生成密文 c, 即 c = Enc sk (m).
3) SKE.Dec: 在密钥 sk 的控制下对密文 c 进行解密, 恢复相应的明文 m, 即 m = Dec sk (c).

2.4 对称可搜索加密
本节主要介绍对称可搜索加密的形式化定义、安全性定义及前向隐私和后向隐私的形式化定义.
(1) 对称可搜索加密的形式化定义
在对称可搜索加密方案中, 客户端首先将包含关键词的文件加密后上传到服务器, 当客户端需要搜索文件时,
发送相应的关键词令牌给服务器, 服务器根据令牌返回对应的文件, 最后, 客户端解密返回的文件.
对称加密算法主要包括密钥生成算法 Gen、加密算法 Enc、陷门算法 Trap、搜索算法 Search 与解密算法
Dec, 即 SSE = (Gen, Enc, Trap, Search, Dec), SSE 过程如图 1 所示, 详细说明如下.
1) K ← Gen(λ): 算法由客户端执行, 接收安全参数 λ, 该算法输出密钥 K.
2) (I, c) ← Enc(K, F): 算法由客户端执行, 接收密钥 K 和包含关键词的文件集合 F = {F 1 , F 2 , …, F n }, 该算法输
出一个加密索引 I 和加密文件集合 c = {c 1 , c 2 , …, c n }.
3) tkn ← Trap(K, w): 算法由客户端执行, 接收密钥 K 和关键词 w, 该算法输出陷门 tkn.