💻 computer science

Plausible Deniability in Fully Homomorphic Computation

本文介绍了 PD-FHC，这是一个用于全同态计算的可否认性框架，它利用 RGB 图像上的单 Fredkin 门布线来同时执行一个真实的布尔电路和多个诱饵，从而允许用户在向不受信任的云端外包计算的同时，保持信息论层面的位置隐私，并具备在受胁迫时揭示可验证诱饵的能力。

原作者： Shahzad Ahmad, Stefan Rass, Zahra Seyedi

发布于 2026-07-13

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Shahzad Ahmad, Stefan Rass, Zahra Seyedi

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

想象一下，你是一名照片实验室的技术员，需要对一批图像进行一项秘密、私人的计算。也许你需要检查照片中的某个特定测量值是否高于某个限值。但问题在于：你必须把这些照片发送给一台你并不完全信任的云端计算机。

通常，如果你想保持数据秘密，你会使用全同态加密（FHE）。把它想象成把你的照片放进一个坚不可摧、闪闪发光的玻璃盒子里。云端仍然可以对这个盒子进行数学运算，但它看不见里面的内容。问题是，这个发光的盒子是一个明显的破绽。如果一个强势、具有胁迫性的对手（比如政府特工或严厉的老板）想要知道你在做什么，他们可以指着那个发光的盒子说：“你肯定在做秘密运算！把密钥交出来！”你无法否认，因为盒子本身就在大喊“秘密！”

这篇论文介绍了一个聪明的新技巧，叫做 PD-FHC（全同态计算中的合理可否认性）。与其使用发光的盒子，不如将你的秘密计算隐藏在一个庞大且看起来普通的图像滤镜之中。

魔术技巧：一种布线，多种故事

以下是这个魔术是如何运作的，我们使用一个有趣的类比：

想象你有一个由 12,000 个微小开关（这些是图像中的像素）组成的巨大网格。你想使用特定的开关模式（你的“真实”电路）来执行一项秘密计算。但你也希望在有人强迫你解释你的行为时，能够讲述一个不同的故事。

作者使用了一种特殊类型的开关，称为 Fredkin 门。把 Fredkin 门想象成一个管理三条数据车道的神奇交通警察。它有一个控制位（一个小旗子）来决定它的行为：

如果旗子是放下的状态，它会让车辆直接通过。
如果旗子是竖起的状态，它会交换两条侧边车道的车辆。

现在，天才之处在于：云服务提供商只能看到交通警察的指令（布线），看不到旗子。

设置： 你将你的秘密计算转化为一种特定的旗子模式。同时，你也发明了几个“诱饵”计算（比如检查图像亮度和色彩平衡），并将它们转化为不同的旗子模式。
嵌入： 你将用于秘密计算的旗子隐藏在一些特定的开关中。你将用于诱饵计算的旗子隐藏在其他开关中。对于剩下的每一个开关，你都用随机噪声来填充。
云端的任务： 你将图像发送到云端。你告诉他们：“请对图像中的每一个开关运行这个特定的交通警察模式。”云端不知道哪些开关持有你的秘密，哪些持有诱饵，哪些只是随机噪声。他们只是对所有人、同时应用相同的规则。
结果： 因为旗子（控制位）对于每一组开关都是不同的，所以交通警察会对秘密开关执行你的秘密数学运算，对诱饵开关执行诱饵数学运算，而对剩余部分执行随机噪声运算。

“合理可否认”时刻

现在，想象着胁迫性的对手出现了。“你在计算什么？”他们质问道。

你不能说“我在做秘密运算”，因为那是事实。但你可以说：“噢，我刚才是在检查这些特定像素的亮度！”你指向了你的其中一个诱饵电路。

对手检查了数学运算。他们看到了你隐藏的旗子，看到了结果，并验证了数学运算是完全正确的。他们无法得知这仅仅是一个诱饵。你的“真实”秘密计算仍然隐藏在随机噪声和其他诱饵之中，看起来与其余部分完全一样。

这篇论文证明了什么（以及它没能证明什么）

作者非常谨慎地界定了他们声称解决的问题以及仍然存在的谜团。

已证明的内容：

“位置”秘密： 如果你用与你的秘密数据统计模式相匹配的随机噪声填充图像，云服务提供商无法辨别你的秘密开关在哪里。这就像是在沙滩上寻找一颗特定的沙粒，而每一颗沙粒看起来都一模一样。论文证明，在这些特定条件下，云端猜中正确位置的概率并不比随机猜测更高。
“存在”秘密： 如果你被迫揭示某些电路，你可以揭示诱饵。论文证明，对手无法证明除了你揭示的电路之外还存在更多的电路。这就像魔术师向你展示几个空口袋；你无法证明除了展示出来的口袋之外，还有隐藏的口袋。

被排除或未解决的内容：

并非“隐形”数学： 论文明确指出，这并不能隐藏正在进行计算这一事实。云端知道正在运行计算，因为他们正在执行它。魔术仅在于隐藏计算的内容以及计算发生的位置。
并非“神奇”的混淆： 作者拒绝使用复杂的密码学技巧来隐藏电路的结构（布线）。他们承认布线对云端是可见的。唯一被隐藏的是门的含义，而这来自于隐藏的旗子。
并非适用于任何图像的“完美”掩护： 你不能直接拿一张随机的度假照片来隐藏你的秘密。论文认为，如果照片的自然“噪声”与你添加的随机噪声不匹配，聪明的检测器可能会发现差异。你需要一个预期会有高随机性的掩护故事（如抖动服务或噪声注入工具）。如果你试图将秘密隐藏在普通照片中，你可能会被抓到。

他们有多确定？

作者对他们的数学逻辑非常有信心，但也诚实地说明了局限性。

数学层面： 如果你遵循他们的规则（完美匹配随机噪声），他们已经证明了云端找到你秘密的优势恰好为零。这不是一种猜测；这是基于 Fredkin 门属性的数学确定性。
现实世界： 他们运行了模拟（计算机测试），图像范围从 128x128 像素到 512x512 像素，电路包含 5 到 302 个门。这些测试表明该系统运行速度足够快，具有实用性，可以与现有的加密工具竞争。
弱点： 他们唯一没有硬性证明的是“语义”部分。你是否总能发明一个听起来合理的诱饵故事？例如，如果你声称你在检查“图像亮度”，那么数学运算看起来真的像是一个亮度检查吗？论文承认这需要人类的创造力和领域知识。这是一个“合理”的故事，但论文并没有证明你可以完美地实现自动化。

底线

这篇论文提供了一种将秘密计算外包给云端的方法，而不会留下一个闪烁的“我正在做秘密运算！”的标志。它将你的秘密计算变成了一堆草垛中的一根针，而草垛里充满了看起来完全一样的其他针。如果有人强迫你展示一根针，你可以展示一根经过测试的假针。

它不是一个让数学运算变得不可见的魔法盾牌，如果你试图在错误的图片中隐藏它，它也不会起作用。但对于正确的设置，它赋予了你一种强大的新超能力：能够说，“我只是在做这件无聊的事”，并且让数学运算证明你是对的。

技术摘要：全同态计算中的可否认性 (PD-FHC)

1. 问题陈述

将计算任务外包给不可信的云服务提供商，使用户面临两个现有技术无法同时解决的截然不同的威胁：

计算隐私 (Computational Privacy)： 保护数据免受“诚实但好奇”的服务提供商的窥探（由全同态加密 (FHE) 和可信执行环境 (TEE) 处理）。
可否认性 (Plausible Deniability)： 当面对强大的对手进行胁迫时，能够可靠地否认计算的存在或其意图。

目前的解决方案存在关键缺陷：

FHE： 虽然它隐藏了数据值，但密文的传输是显眼的。胁迫性的对手可以要求解密密钥，且仅仅使用 FHE 这一行为本身就证实了正在进行私密计算。
TEE： 它们会产生作为执行证明的不可否认的归属日志 (attestation logs)。此外，它们容易受到侧信道泄露的影响。
安全多方计算 (MPC)： 虽然对单个参与方的份额具有鲁棒性，但它并不允许参与者否认计算曾经发生过，或者无法用另一个不同的计算来替代原有的计算。
可否认加密/存储 (Deniable Encryption/Storage)： 这些技术解决了静态数据（消息或文件）的问题，但未能扩展到动态的计算意图。

本文识别出一个空白领域：用户需要在外包布尔计算的同时，保持能够向外部观察者否认“正在进行何种计算”，甚至在某种程度上否认“发生了计算”的能力。

2. 方法论

作者提出了 PD-FHC，这是一个将布尔计算嵌入到覆盖介质（具体为 RGB 图像）中的框架，并利用了 Fredkin 门 和 最低有效位 (LSB) 隐写术。

核心机制：

共享布线，可变语义 (Shared Wiring, Variable Semantics)： 该框架使用单一、固定的通用 Fredkin 门布线。Fredkin 门是一种可逆的三输入三输出门，其中一个控制位决定是否交换两个数据位。
- 如果控制位为 0，该门充当直通门（pass-through）。
- 如果控制位为 1，该门交换两个数据位。
- 通过由嵌入数据设置的控制位，相同的物理布线可以在不同位置实现不同的逻辑函数（例如 AND、OR、NOT 或复杂的电路）。
多位置嵌入 (Multi-Location Embedding)： 用户（Alice）将一个“真实”电路和 $L-1$ $L - 1$ 个“诱饵”电路嵌入到图像的 LSB 中。
- 真实电路： 嵌入在秘密的位置集合 $\Lambda_{j^*}$ 。
- 诱饵电路： 嵌入在其他不相交的位置集合 $\Lambda_j$ 。
- 填充位 (Fill Bits)： 所有剩余的 LSB 位置都由符合特定分布 $\pi$ 的比特填充。
统一处理 (Uniform Processing)： 云服务提供商（Carol）接收图像和布线规范 ( $C_{obf}$ )。她对每个像素位置并行地应用 Fredkin 门。她不知道哪些位置包含真实数据、诱饵数据或填充噪声。
胁迫响应 (Coercion Response)： 如果受到胁迫，Alice 会公开一组位置集合、输入和输出，用于展示一个诱饵电路。由于布线是完全一致的，且诱饵电路产生的计算结果与云端输出的结果一致，因此对手无法区分该诱饵与真实的计算。

理论基础：

可否认计算介质 (Deniable Computation Medium, DCM)： 一个抽象框架，定义了一个具有可寻址比特位置、读写能力以及应用统一门族的介质。
匹配边缘条件 (Matched-Marginal Condition)： 为了实现信息论安全性，真实位置、诱饵位置和填充位置的比特必须提取自相同的逐位置概率律 $\pi$ 。在此条件下，LSB 平面是“可交换的”，这意味着图像的统计分布对于位置的置换具有不变性。

3. 核心贡献

抽象框架： 定义了 可否认计算介质 (DCM) 和 可否认计算方案 (DCS)，将安全模型与具体的覆盖介质（如图像、音频、数据包）分离。
威胁模型形式化： 定义了一个两阶段模型，区分了：
- 诚实但好奇 (HBC) 的云端： 关注计算隐私（隐藏数据）。
- 胁迫性对手 (Coercive Adversary)： 关注可否认性（隐藏存在的意图）。
  作者定义了新型的多轮胁迫博弈，用于衡量“存在性区分度”（对手能否证明隐藏电路的存在？）和“电路发现能力”（对手能否在揭示的诱饵中识别出真实的电路？）。
基于图像的实例化： 使用 RGB 图像和 Fredkin 门进行的具体实现。
- 位置隐私证明： 在满足匹配边缘条件的情况下，本文证明了云服务提供商在定位真实电路位置方面获得的优势为零（信息论意义上），其表现与随机猜测无异。
- 部分电路隐藏： 布线是可见的，但门语义是隐藏的。本文证明，在不知道控制位的情况下，布线不会透露正在计算何种函数。
实现与基准测试： 一个 Python 实现，并在不同电路规模（5–302 个门）和图像维度（ $128^2$ 至 $512^2$ ）下进行了基准测试。

4. 结果

安全保证：
- 计算隐私： 只要门族能够保持非秘密位置的统计分布（这是 Fredkin 门通过比特置换实现的特性），云端就无法获知秘密数据值或所计算的具体函数。
- 存在性隐藏： 在满足匹配边缘条件时，存在性优势精确为零。对手无法区分一个仅包含填充位的图像与一个包含隐藏电路的图像。
- 电路发现： 在诱饵电路的语义合理性和侧信道泄露限制下，识别真实电路的优势是受限的。位置向量和布线向量对对手的优势贡献为零。
性能： 实现结果显示，在处理布尔电路时，其性能与 TFHE（领先的 FHE 库）相当，同时提供了 FHE 无法提供的可否认性。
视觉不可察觉性： 对 LSB 的修改导致每个通道的最大偏移仅为 $\pm 1$ ，使得 PSNR > 50 dB，这种变化在视觉上是无法察觉的。

5. 重要性与声明

本文声称是第一个同时满足计算隐私、存在性隐藏（针对外部观察者）和部分电路隐藏（针对云服务提供商）的框架。

适度的声明与局限性：

覆盖物合理性的范围： 作者明确指出 PD-FHC 并不适用于任意图像（例如度假照）。覆盖服务必须预期高熵的 LSB 输入（例如抖动、噪声注入或加密域处理）。如果声明的服务预期的是自然图像，那么实现安全所需的均匀 LSB 平面将会变得可检测。
真实输入约束： 只有当用户的真实输入比特也遵循与诱饵及填充比特相同的分布 $\pi$ 时，信息论零优势保证才严格成立。对于结构化程度较高的真实输入，优势将受限于真实输入分布与 $\pi$ 之间的统计距离 ( $\Delta$ )。
语义合理性： 针对电路发现的安全依赖于诱饵电路的 $\epsilon$ -合理性。论文承认，构建语义上可信的诱饵（例如：亮度检查 vs. 加密哈希）是一个手动的、特定领域的任务，目前尚未实现自动化。
主动攻击： 该框架假设云端是诚实但好奇的，且外部观察者是被动的。它并不防御修改图像或拒绝计算的主动攻击者。
无密码学混淆： 本文明确避免声称实现了密码学意义上的电路混淆（这受限于不可能结果）。其“混淆”纯粹是隐写术性质的，依赖于隐藏的控制位来改变门的语义。

总而言之，PD-FHC 提供了一种全新的外包计算方法，用户可以通过呈现一个可验证的、与真实函数不可区分的替代函数，从而在受到胁迫时，能够可靠地否认特定的计算意图，前提是满足覆盖介质的统计条件。