💻 computer science

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

本文提出了一种在标准模型下具有紧密安全性（tightly secure）的新型广播认证加密关键词搜索（BAEKS）方案，该方案解决了现实中的多用户和多挑战场景，同时确保了强大的隐藏性和不可伪造性，并附带了一个高效的单接收者变体以及实验评估。

原作者： Sayantan Mukherjee

发布于 2026-09-01

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Sayantan Mukherjee

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在数字时代，敏感信息通常被锁在加密库中，既远离窥视之眼，也让需要查找其中特定细节的人无法直接获取。想象一家医院，为了保护隐私，患者记录被进行了乱序处理；医生需要查找一份关于特定过敏症的文件，但无法直接搜索这些乱序后的文本。为了解决这个问题，密码学家开发了一种称为“可搜索加密”的系统。这允许用户生成一种被称为“陷门”（trapdoor）的特殊密钥，它就像是特定关键词的独特指纹。持有加密文件的服务器可以使用这个指纹来检查文件是否包含该词，而无需看到该词本身或文件的内容。然而，这个系统有一个致命缺陷：由于加密密钥是公开的，恶意攻击者可以通过猜测常用词、创建自己的测试文件，并将其与陷门进行对比，从而逆向工程出隐藏的关键词。这被称为“关键词猜测攻击”，它威胁着要揭露该系统旨在保护的秘密。

研究人员曾试图通过引入身份验证来修复这一问题，以确保只有特定的发送者可以创建可搜索文件，且只有特定的接收者可以进行搜索。这演变成了一个更复杂的场景，称为“带关键词搜索的广播认证加密”，即单个发送者可能希望与一组授权的接收者共享秘密，例如医生向专家团队分享诊断结果。虽然这项技术的早期尝试提供了一些保护，但在现实的高风险环境中却表现不佳。它们往往未能考虑到攻击者可能破坏多个用户，或进行数千次同时猜测的情况，且其安全性证明依赖于数学上的简化，导致其在面对巧妙攻击时显得脆弱。现有的解决方案就像一把在实验室里表现完美的锁，但如果有人在人群推搡着破门而入时试图撬锁，这把锁可能会失效。

印度理工学院贾穆分校（Indian Institute of Technology, Jammu）的一位研究人员现在提出了一种新的构建方案，正面解决了这些弱点。他们设计的系统即使在攻击者可以破坏多个用户，并以混乱、交织的方式进行大量并发查询的情况下，依然能保持安全。他们的工作引入了一个严格的安全定义，确保即使在最激烈的攻击下，关键词、发送者身份和接收者身份都能完全隐藏。与以往依赖理想化假设的模型不同，这种新方案在“标准模型”（standard model）中被证明是安全的，这意味着其安全性在现实世界的数学审查下依然成立，而无需依赖那些在压力之下往往会崩溃的假设性“随机预言机”（random oracle）捷径。

该研究人员利用一种被称为“双线性配对群”（bilinear pairing groups）的特定数学结构构建了其解决方案，这种结构就像是一个复杂的多层数据过滤器。他们证明了该系统具有“紧凑安全性”（tightly secure），这是一个技术术词，意味着安全性保证不会随着用户数量或攻击次数的增加而下降。在许多旧系统中，用户越多，安全性就越弱，但这种新设计无论规模如何都能保持其强度。他们还证明了该方法可以防止攻击者伪造虚假的搜索密钥或加密文件，确保只有真实的发送者和接收者能够参与搜索。

为了验证其理论设计在实践中是否可行，研究人员在标准的虚拟机上实现了该系统。他们进行了实验，改变了用户数量和接收者组的大小，模拟了从单个医生搜索记录到大型医院网络在百名专家之间共享数据的各种场景。结果表明，该系统对于实际应用而言效率足够高。对于单次搜索，处理时间不到一秒；即使是在一百人的组内进行搜索，所需的时间仍然在可控范围内。计算成本呈线性扩展，这意味着随着组规模的扩大，搜索所需的时间会以一种可预测且稳定的方式增长，而不是出现无法使用的延迟。

这项工作代表了在保护加密数据免受复杂对手攻击方面迈出的重要一步。通过强化安全定义并提供一种能够抵御自适应攻击的构建方案，研究人员为隐私至关重要的环境提供了一个强大的工具。他们的研究结果表明，实现一个既能加密数据又能进行搜索和认证，且无需为了便利性或规模而牺牲安全性的系统是可能的。论文最后指出，虽然目前的实现仅是一个概念验证，但它为未来能够抵御积极尝试破解加密的恶意行为者的系统奠定了基础，确保敏感信息即使在拥挤的数字景观中也能保持真正的私密性。

技术摘要：在多用户、多挑战设置下具有紧密安全性的广播认证加密关键词搜索

1. 问题陈述

可搜索加密（Searchable Encryption, SE）允许用户对加密数据进行搜索。虽然公钥加密关键词搜索（PEKS）实现了这一功能，但它容易受到关键词猜测攻击（Keyword Guessing Attacks, KGA）的影响，即攻击者通过生成密文来测试陷阱（trapdoor），从而推断出关键词。为了缓解这一问题，引入了公钥认证关键词搜索（PAEKS），该技术要求发送者的私钥参与加密。随后，这被推广到了广播认证关键词搜索（BAEKS），以支持发送者为一组授权接收者对关键词进行加密。

尽管现有的 BAEKS 和 PAEKS 研究取得了进展，但仍存在几个关键空白：

安全模型： 现有的方案通常缺乏针对多用户、多挑战设置的安全定义，而这种设置对于部署系统更具现实意义。具体而言，它们未能考虑到自适应破坏（即攻击者获取用户的私钥）和交错查询（即攻击者同时对密文和陷阱发起挑战）。
紧密性（Tightness）： 当前的安全归约存在非平凡的多项式级安全损失（例如，与查询或用户的数量成正比），这意味着随着系统的规模扩大，其安全性保证会显著下降。
一致性： 先前关于 BAEKS 计算一致性的证明（特别是 Emura 的工作）被认为是不完整的，或缺乏形式化的归约论证。
匿名性： 许多方案无法在强对抗模型下，同时隐藏密文和陷阱中的关键词、发送者身份以及接收者身份。

2. 方法论与构造

作者提出了一种新的 BAEKS 方案，记作 baeks，该方案构建于双线性配对群（Type-3）之上。其方法论包括：

新的安全定义： 本文引入了 full-cpa 安全定义，该定义允许攻击者在密文、陷阱和私钥上进行交错的挑战查询（自适应破坏）。作者还定义了不可伪造性概念（ct-cma 和 trap-cma），并指出这些概念由 full-cpa 安全性所蕴含。
编码策略： 不同于以往使用 Boneh-Boyen 哈希编码（由于线性依赖关系，此类编码在多挑战设置下会失效）的构造，作者采用了受紧密安全的身份基加密（IBE）和分层身份基加密（HIBE）启发的设计，使用了随机化的 Naor-Reingold PRF 结构。
- 用户由矩阵 $U_j$ （发送者）和 $V_j$ （接收者）表示。
- 关键词通过矩阵 $K_{\iota, b}$ 进行编码。
- 元组 $(S, \omega, R)$ 被编码为这些组件的和： $\sum U_{S,i} + \sum K_{\omega,i} + \sum V_{R,i}$ 。
- 通过将随机函数 $RF(S||\omega||R)$ 注入密文和陷阱编码中来实现随机化。
证明技术： 安全性证明利用了一个涉及一系列游戏（ $G_0$ $G_{0}$ 到 $G_6$ $G_{6}$ ）的混合论证（hybrid argument）。其核心组成部分是一个核心引理（定理 2），该引理确立了系统在特定预言机查询下的不可区分性。证明依赖于横向矩阵 Diffie-Hellman（lat-MDH）假设。
- 证明通过确保即使在非挑战用户的私钥被泄露时，被挑战用户的密钥熵仍然足以注入随机性而不被检测，从而处理自适应破坏问题。
- 作者通过限制攻击者不得查询参与挑战密文或陷阱的用户私钥，解决了“非平凡性”条件问题。

3. 主要贡献

新型安全定义： 本文定义了适用于 BAEKS 的 full-cfa 安全，涵盖了具有交错查询的多用户、多挑战及自适应破坏设置。这是第一个实现紧密安全性（安全归约损失为常数，与查询数量无关）的 BAEKS（及 PAKS）定义。
紧密安全的构造： 作者提出了一个新的 BAEKS 构造，在标准模型下基于标准的 lat-MDDH 假设实现了自适应 full-cpa 安全性。将其限制为单个接收者即可得到紧密安全的 PAEKS。
不可伪造性： 本文证明了所提出的 full-cpa 安全性概念本质上蕴含了针对密文和陷阱的不可伪造性。
一致性分析： 作者对先前工作中（特别是 Emura 的工作）的一致性证明进行了严谨分析，指出了其中的缺陷，并为自己的方案提供了一个统计一致性的构造。
实现： 该方案使用 Charm 框架在 Python 中实现。通过在虚拟机上进行实验，评估了其在不同接收者数量 ( $\ell$ )、安全级别 ( $k$ ) 以及关键词/用户空间大小 ( $\alpha, u$ ) 下的性能。

4. 结果

安全性： 该方案在标准模型下基于 lat-MDDH 假设被证明是安全的。其安全归约是紧密的，避免了以往 BAEKS 和 PAEKS 方案中存在的乘法损失 ( $\Theta(|Q_{Ct}| + |Q_{Tr}|)$ )。
性能：
- Setup 和 KeyGen： 这些操作在每个系统/用户端仅运行一次。设置复杂度随关键词空间大小 $\alpha$ 线性扩展。
- SrchEnc 和 TrapGen： 这些操作非常高效。加密和陷阱生成的成本在很大程度上与用户数量 $u$ 无关，而是与关键词长度 $\alpha$ 和接收者数量 $\ell$ 呈线性关系。
- Test： 云服务器执行 $2\ell$ 次双线性配对以验证匹配。对于 PAEKS ( $\ell=1$ )，这仅需 2 次配对。
- 实验数据： 作者报告，对于 $\ell=1$ （PAEKS）的情况，该方案在效率上与现有工作相当，同时提供了更紧密的安全保障。对于较大的 $\ell$ ，虽然开销在可控范围内，但注意到该方案在密文/密钥大小方面略逊于 Mukherjee [42] 的统计一致性方案，但在安全性保证方面更为优越。

5. 重要性与主张

本文声称通过解决最现实的威胁场景，重塑了现有的 BAEKS 安全模型：即具有自适应破坏和交错挑战的多用户环境。其主要意义在于实现了在这些设置下的紧密安全性，这在此前是 BAEKS 和 PAEKS 领域的一个开放问题。

作者强调，其工作提供了第一个能够同时确保以下特性的 BAEKS 正式化方法：

关键词隐藏。
发送者和接收者匿名性。
对自适应破坏的抵抗力。
紧密的安全归约。

论文最后谦虚地指出，虽然目前的构造是一个实用的概念验证，但未来的工作可以致力于开发能够抵御生成自身密钥对的恶意攻击者的构造，并可能进一步优化密文大小。这项工作还强调，其 BAEKS 构造的紧密安全性可以直接转化为紧密安全的 PAEKS，填补了单接收者认证可搜索加密领域的文献空白。