🔢 mathematics

Implementation of Oblivious Transfer over Binary-Input AWGN Channels by Polar Codes

本文提出了一种基于极化码的 BI-AWGN 信道 1-out-of-2 不经意传输协议，通过利用极化变换的自同构群随机选择编码器并结合信道极化与隐私放大，在任意码长下实现了 Bob 的完美保密以及 Alice 的渐近保密，并推导了适用于有限码长的优化速率。

原作者： Pin-Hsun Lin, Hadi Aghaee, Christian Deppe, Eduard A. Jorswieck, Holger Boche

发布于 2026-02-13

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Pin-Hsun Lin, Hadi Aghaee, Christian Deppe, Eduard A. Jorswieck, Holger Boche

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

这篇文章介绍了一种利用**极化码（Polar Codes）在嘈杂的无线信道中实现“不经意传输”（Oblivious Transfer, OT）**的新方法。

为了让你轻松理解，我们可以把这项技术想象成一场**“高智商的密室寻宝游戏”**，发生在两个角色之间：发送者（Alice）和接收者（Bob）。

1. 什么是“不经意传输”？（游戏规则）

想象 Alice 手里有两把钥匙（消息 $M_0$ 和 $M_1$ ），而 Bob 手里只有一把能打开其中一把锁的钥匙（选择位 $B$ ，要么是 0，要么是 1）。

Bob 的目标：拿到他想要的那把钥匙（比如 $M_0$ ），并且不能知道另一把钥匙（ $M_1$ ）长什么样。
Alice 的目标：把钥匙给 Bob，但不能知道 Bob 到底选了哪一把。

这就像 Alice 把两封信放在两个盒子里，Bob 选了一个盒子拿走，Alice 不知道他拿的是哪个，而 Bob 打开盒子后，发现另一封信的内容完全无法从他的视角推断出来。

2. 核心挑战：嘈杂的信道

在现实中，他们通过一个**“充满噪音的无线信道”**（比如手机信号，受到干扰）来传递信息。

以前的做法：要么靠复杂的数学计算（假设黑客算力有限），要么需要特殊的“完美”信道。
本文的突破：利用物理世界的噪音本身作为安全工具。就像在嘈杂的房间里说话，只有特定的人能听清，其他人只能听到乱码。

3. 他们是怎么做到的？（三大魔法）

这篇论文用了三个巧妙的“魔法”来达成目标：

魔法一：极化码——“分门别类”的魔法

极化码是一种很聪明的编码方式。它能把一个嘈杂的信道，神奇地分裂成两类通道：

好通道（GBCs）：像高速公路，信号清晰，几乎没噪音。
坏通道（BBCs）：像泥泞的沼泽，信号完全混乱，全是噪音。

传统用法：通常大家只把重要信息放在“好通道”上，把“坏通道”直接废弃（填 0）。
本文的创新：他们故意在“坏通道”里塞入一些随机的乱码。

比喻：Alice 把真正的信放在“高速公路”上，但在“沼泽地”里扔了一堆假消息。Bob 因为只能看清“高速公路”，所以能拿到真信；但他看“沼泽地”时，看到的只是一团乱码，完全猜不出里面藏了什么秘密。这就制造了信息不对称。

魔法二：自动同构（Automorphisms）——“旋转迷宫”的魔法

这是论文最精彩的部分。Alice 和 Bob 使用了一种特殊的“旋转矩阵”（数学上的排列组合）。

场景：Alice 和 Bob 手里都有一张地图，但 Bob 偷偷把地图旋转了一下（通过一个只有他自己知道的排列规则）。
效果：
- 在 Alice 眼里，某些位置是“好通道”（高速公路）。
- 在 Bob 眼里，经过旋转后，同样的位置可能变成了“坏通道”（沼泽地），或者反过来。
- 关键点：Alice 不知道 Bob 把地图旋转了多少度。她只能看到 Bob 公开的一张“混合地图”。因为旋转是随机的，Alice 无法判断 Bob 到底想看哪条路，从而无法推断 Bob 选了哪把钥匙（保护了 Bob 的选择）。
- 同时，Bob 因为知道旋转规则，他能把自己看到的“沼泽地”还原成“高速公路”来解码，但他无法还原 Alice 没选的那条路的信息。

魔法三：隐私放大——“碎纸机”

虽然“坏通道”里全是噪音，但物理上可能还残留了一点点微弱的信息。为了彻底安全，他们最后用了一个通用哈希函数（可以想象成一台碎纸机）。

Bob 把从“好通道”和“坏通道”里收集到的所有信息（包括那些随机乱码）扔进碎纸机。
碎纸机输出一把最终的密钥。
结果：即使 Bob 从“坏通道”里偷听到了一点点噪音，经过碎纸机处理后，这些信息也彻底变成了毫无意义的乱码，无法还原出另一把钥匙的内容。

4. 为什么这个研究很重要？

不需要超级计算机：它的安全性不依赖于“黑客算不出来”，而是依赖于物理定律（噪音和概率）。即使未来有了量子计算机，这种基于物理噪音的安全依然有效。
利用噪音：以前大家觉得无线信号里的噪音是坏事，这里把它变成了保护隐私的“盾牌”。
实际可行：论文不仅提出了理论，还给出了具体的算法和参数，证明了在真实的 5G/6G 无线环境（高斯白噪声信道）中，这种方法是行得通的，并且能计算出最高能传输多少数据。

总结

这篇论文就像设计了一套**“基于物理噪音的盲盒交换系统”：
Alice 把两个盲盒（消息）通过一条充满干扰的传送带发给 Bob。
Bob 戴着一副特制的“旋转眼镜”（自动同构），让他只能看清其中一个盲盒的内容，而另一个盲盒在他眼里是一团模糊的乱码。
最后，Bob 用一把“碎纸机”**（哈希函数）把看到的乱码彻底粉碎，确保他绝对猜不到另一个盲盒里是什么。
而 Alice 因为不知道 Bob 戴的是哪副眼镜（旋转角度），所以完全不知道 Bob 拿到了哪个盲盒。

这就是利用极化码和物理噪音实现的完美“不经意传输”。

这篇论文提出了一种基于**极化码（Polar Codes）的2-1 不经意传输（Oblivious Transfer, OT）协议，该协议运行在二进制输入加性高斯白噪声（BI-AWGN）**信道上。文章解决了在物理层安全（Physical Layer Security）背景下，如何利用信道噪声和极化码的特性来实现信息论安全的 OT 协议，并特别关注了有限码长下的性能优化。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

OT 的重要性：2-1 OT 是安全多方计算的基础构建模块，允许接收方从发送方的两个消息中选择一个，而发送方不知道接收方选择了哪一个，同时接收方也不能获取另一个消息的信息。
现有挑战：
- 传统的 OT 通常基于计算假设（如公钥密码），而信息论安全的 OT 需要利用物理信道的噪声。
- 现有的基于极化码的方案多用于离散信道（如 BSC 或 BEC），或者仅将极化码作为可靠性编码工具，未充分利用极化码中“好信道”（GBCs）和“坏信道”（BBCs）的内在结构差异来构建 OT。
- 在 BI-AWGN 信道上，如何设计协议以同时满足接收方隐私（SfA）（Bob 无法得知未选消息）和发送方隐私（SfB）（Alice 无法得知 Bob 的选择），并在有限码长下保持高可靠性，是一个开放问题。
核心难点：在有限码长下，坏信道（BBCs）并非完全不可用（存在泄露），好信道（GBCs）也非完美可靠。如何平衡可靠性、泄露控制和 OT 速率是一个复杂的优化问题。

2. 方法论 (Methodology)

A. 核心思想：虚拟擦除信道（Virtual BEC）与自动同构

作者提出了一种将 BI-AWGN 信道视为“虚拟二进制擦除信道（BEC）”的框架：

好信道（GBCs）：用于传输 Bob 选择的消息。
坏信道（BBCs）：用于传输随机比特（对 Bob 未知），在 Bob 的视角下，这些位置相当于“擦除”了未选消息的信息。
自动同构（Automorphisms）：利用极化变换矩阵 $T$ 的自动同构群 $\text{Aut}(T)$ 。Bob 选择一个隐藏的自动同构变换 $P_1$ ，Alice 仅知道复合变换 $F = P_1^T T_B$ 。这导致 Alice 和 Bob 对 GBCs 和 BBCs 的索引集合有不同的“视图”，从而隐藏了 Bob 的选择。

B. 协议流程

设置：Bob 选择两个极化矩阵视图 $T_1$ （对应选择 $B=0$ ）和 $T_2 = A T_1$ （对应选择 $B=1$ ），其中 $A \in \text{Aut}(T)$ 。Bob 随机选择一个 $P_1 \in \{A^k\}$ 并公开 $F = P_1^T T_B$ 。
索引选择：Bob 根据 $T_B$ 确定好/坏信道集合，并公开一对索引集 $(\tilde{J}_0, \tilde{J}_1)$ 。如果 $B=0$ ，则 $(\tilde{J}_0, \tilde{J}_1) = (J_0, J_1)$ ；否则交换。
编码与传输：Alice 在公开索引集上生成随机比特，其余冻结，形成码字 $x^n$ 并通过 BI-AWGN 信道发送。
解码与密钥生成：Bob 利用私有 $P_1$ 对接收信号进行重排，匹配到 $T_B$ 进行解码。他提取选定索引上的比特生成密钥，解密对应的消息。
隐私放大：利用通用哈希函数（Universal Hashing）处理泄露，确保未选消息的信息论安全。

C. 关键理论工具

$\text{Aut}(T)$ 的完全刻画：论文证明了极化变换矩阵 $T = F^{\otimes m}$ 的自动同构群 $\text{Aut}(T)$ 同构于对称群 $S_m$ （即 $m!$ 个元素）。每一个自动同构都对应于对 $m$ 个比特位置的一个唯一置换。这一发现使得搜索空间从所有排列缩小为仅 $m!$ 个，极大地降低了优化复杂度。
交叉切割约束（Cross-cut Constraint）：设计自动同构 $A$ ，使得 $A$ 将 $T_1$ 的好信道映射为 $T_2$ 的坏信道，反之亦然。这确保了无论 Bob 选择哪个视图，Alice 看到的索引集结构在统计上是不可区分的。
有限码长可靠性分析：由于在 BBCs 上注入随机比特会干扰解码，作者提出了基于蒙特卡洛模拟的置信度可靠性准则，而非传统的确定性上界。

3. 主要贡献 (Key Contributions)

首个基于极化码的 BI-AWGN OT 协议：利用极化码的 GBC/BBC 分裂特性，结合自动同构，在连续输入 AWGN 信道上实现了信息论安全的 OT。
$\text{Aut}(T)$ 的完整表征：证明了 $\text{Aut}(T) \cong S_m$ ，即自动同构完全由比特位置的置换诱导。这为协议中随机化生成矩阵提供了可计算且高效的搜索空间。
有限码长优化框架：
- 提出了一个联合优化问题，同时选择自动同构 $P$ 和索引集 $(J_0, J_1)$ 。
- 利用高斯近似（Gaussian Approximation, GA）递归计算互信息，将问题转化为离散优化。
- 导出了闭式的“最大 k 选择规则”，使得在固定置换下能快速找到最优索引集，从而最大化 OT 速率。
安全性与可靠性证明：
- SfB（发送方隐私）：证明了在诚实但好奇的 Bob 假设下，SfB 是完美的（ $\delta_B = 0$ ），因为公共矩阵 $F$ 的分布独立于 Bob 的选择位 $B$ 。
- SfA（接收方隐私）：利用隐私放大和坏信道的有限泄露上界，证明了未选消息的泄露可以被控制在任意小。
- 可靠性：提出了基于蒙特卡洛模拟的统计可靠性保证，允许在有限码长下通过注入随机比特来换取安全性，同时控制误码率。

4. 实验结果与性能 (Results)

仿真设置：在 $n=512$ 和 $n=1024$ 的码长下，针对 BI-AWGN 信道进行了仿真。
可靠性权衡：实验表明，即使在部分坏信道上注入随机比特（未知给 Bob），解码器仍能保持可控的性能下降（误码率 BER 可控），这验证了“用可靠性换取擦除”的设计思路是可行的。
速率优化：通过优化算法（Algorithm 1），论文展示了在不同信噪比（SNR）下，如何选择最佳的自动同构和索引集来最大化 OT 净速率。例如，在 $n=16$ 的示例中，计算出了具体的可达速率。
对比：与之前基于 Schur 平方或广义擦除信道（GEC）的方案相比，本方案直接利用极化码的内在结构，无需字母表扩展，且针对通用 BIMC（特别是 AWGN）进行了优化。

5. 意义与影响 (Significance)

理论突破：将极化码的自动同构理论首次系统地应用于物理层安全协议（OT）的设计中，揭示了极化码结构在安全通信中的新潜力。
实用价值：提出的有限码长优化框架和蒙特卡洛可靠性评估方法，使得该协议在实际通信系统（如 5G/6G 物理层安全）中具有可实施性。
安全性增强：通过物理层噪声和极化特性实现信息论安全，减少了对计算复杂度的依赖，为后量子时代的隐私保护提供了新思路。
通用性：虽然主要针对 AWGN，但其基于互信息和自动同构的框架可推广至其他二进制输入记忆信道。

总结：
这篇论文通过深入挖掘极化码的数学结构（特别是自动同构群），设计了一种在 BI-AWGN 信道上高效、安全的 OT 协议。它不仅解决了有限码长下的可靠性与安全性权衡问题，还提供了一个可计算的优化框架，为物理层安全技术的实际应用奠定了坚实基础。