生成式隐写典型工作

引言：隐写术的“不可能三角”

在生成式 AI 爆发的今天，文本隐写术（Text Steganography）面临着一个极其苛刻的挑战。我们需要在语言模型（LLM）生成的文本中隐藏信息，同时满足三个互相拉扯的目标：

1. 安全性 (Security)： 生成的文本分布必须在统计学上与模型原始分布严格一致（KL散度为0）。
2. 容量 (Capacity)： 每一个 Token 能嵌入多少比特？能否接近香农熵（Shannon Entropy）的理论极限？
3. 鲁棒性与效率 (Robustness & Efficiency)： 解码是否快速？是否需要复杂的同步机制？

为了解决这个“不可能三角”，学术界经历了从 编码（Coding） 到 采样（Sampling） 的范式转移。

---

预设场景：Alice 的挑战

为了对比不同算法，我们全篇使用同一个标准实验环境：

• 模型预测 ($D$)： 假设 LLM 在当前时刻预测下一个词的概率分布如下：
  • $t_1$: “excellent” ($p=0.5$)
  • $t_2$: “good” ($p=0.25$)
  • $t_3$: “bad” ($p=0.25$)
• 秘密消息 ($M$)： Alice 需要发送二进制序列 10。
• 共享密钥 ($Key$)： Alice 和 Bob 拥有共享种子（用于生成伪随机数）。

---

第一阶段：基于编码的启发式方法 (Heuristic Coding)

早期的思路非常朴素：既然我们要选词，不如把词映射成二进制编码。这直接借鉴了数据压缩技术。

1. 霍夫曼编码隐写 (Huffman Coding Steganography)

【核心思想】
利用霍夫曼树（Huffman Tree）的最优前缀码特性，将概率大的词赋予短码（如0），概率小的词赋予长码（如10）。

【算法流程拆解】

1. 构建树： 根据概率 $D$，自底向上构建二叉树。
   • 左子树代表比特 0，右子树代表比特 1。
   • 根节点 $\rightarrow$ 左: “excellent” (0.5)
   • 根节点 $\rightarrow$ 右: (中间节点 0.5) $\rightarrow$ 左: “good” (0.25) | 右: “bad” (0.25)
2. 编码映射：
   • “excellent”: 0
   • “good”: 10
   • “bad”: 11
3. 嵌入操作：
   • Alice 读取秘密 1 (对应右分支) $\rightarrow$ 到达中间节点。
   • Alice 读取秘密 0 (对应左分支) $\rightarrow$ 到达叶子节点 “good”。
   • 输出 Token： “good”。

【深度批判】

• 致命缺陷：分布失配 (Distribution Mismatch)
  霍夫曼树强制将概率量化为 $1/2^k$ 的形式。假设真实分布是 $P(\text{cat})=0.33, P(\text{dog})=0.67$。霍夫曼编码只能将其强制映射为 1位(0) 和 1位(1)，即 $0.5$ 对 $0.5$。
  后果： 隐写文本中 “cat” 出现的频率变成了 50%，而正常文本是 33%。这种统计偏差在大量文本下会被卡方检验（Chi-square Test）瞬间识破。
• 变长编码导致的同步问题：
  “excellent” 消耗 1 bit，“good” 消耗 2 bits。Bob 收到 “good” 后，不知道 Alice 到底发送了多少比特，这需要额外的结束符或长度头，降低了信道利用率。

---

2. 算术编码隐写 (Arithmetic Coding Steganography)

【核心思想】
为了解决霍夫曼树“颗粒度太粗”的问题，算术编码将离散的 Token 映射为连续区间 $[0, 1)$ 上的累积分布函数（CDF）。

【算法流程拆解】

1. 区间划分 (Interval Partitioning)：
   计算 CDF，将 $[0, 1)$ 切割给各个 Token：
   • $I(\text{excellent}) = [0.00, 0.50)$
   • $I(\text{good}) = [0.50, 0.75)$
   • $I(\text{bad}) = [0.75, 1.00)$
2. 消息映射：
   将秘密消息 10 视为二进制小数 $0.10_2$。
   • $0.10_2 = 1 \times 2^{-1} + 0 \times 2^{-2} = 0.5$ (十进制)。
   • (注：实际算法通常会引入一个自适应缩放的区间，这里简化为静态映射)。
3. 嵌入操作：
   • 数值 $0.5$ 落在哪个区间？
   • 恰好落在 $[0.50, 0.75)$ 的起始点。
   • 输出 Token： “good”。

【深度批判】

• 精度溢出 (Finite Precision Error)：
  这是算术编码的死穴。计算机无法处理无限精度的浮点数。当概率分布非常复杂（例如 $p=1/3$），区间边界变成了无限循环小数。为了运算，计算机必须截断（Truncate）末尾。
  后果： 这种截断会导致某些极小概率的词永远选不到，或者某些词的选择概率发生了微小的偏移（如 $0.3333$ 变成了 $0.3332$）。这就是 “经验安全” (Empirical Security) —— 在短文本上看不出来，但在长文本大数据分析下，KL 散度不为 0。

---

第二阶段：基于采样的可证明安全 (Provably Secure Sampling)

为了彻底解决精度和分布失配问题，学界引入了可证明安全的概念。其核心逻辑是：不要试图去编码概率，而是用密码学安全的随机数去模拟采样。

3. Meteor (CCS 2021) —— 破局者

【核心思想】
利用拒绝采样 (Rejection Sampling) 和 逆变换采样 (Inverse Transform Sampling)。如果我能用一个加密伪随机数 (PRG) 来代替普通的随机数 random()，那么生成的 Token 分布在数学上就是完美的。

【算法流程拆解】

1. 共享随机性：
   Alice 和 Bob 共享密钥 $K$。
2. 生成伪随机数 (PRG)：
   Alice 将当前上下文 $H$ 和秘密消息 $S$（的一部分）作为种子，输入 PRG。

   $$r = \text{PRG}(K, H, S_{\text{candidate}})$$

   假设对于秘密候选 10，生成的随机数 $r = 0.62$。
3. 逆变换采样：
   • 区间划分同算术编码：excellent $[0, 0.5)$, good $[0.5, 0.75)$, bad $[0.75, 1.0)$。
   • 检查 $r=0.62$ 落在哪里？$\rightarrow$ “good”。
4. 输出 Token： “good”。

【解码流程 (Bob)】
Bob 收到 “good” (区间 $[0.5, 0.75)$)。
Bob 不知道秘密是啥，但他有 $K$。他开始穷举（或使用优化搜索）：

• 试秘密 00: $r = \text{PRG}(K, \dots, 00) = 0.12$ $\rightarrow$ 对应 “excellent” (不匹配 ❌)
• 试秘密 10: $r = \text{PRG}(K, \dots, 10) = 0.62$ $\rightarrow$ 对应 “good” (匹配 ✅)
  结论： 秘密是 10。

【深度批判】

• 优点： 真正实现了 Provably Secure。只要 PRG 是安全的，$r$ 就是均匀分布的，那么选出来的 Token 就严格服从 $D$。
• 缺点： 解码效率低。 Bob 可能需要试错很多次才能找到匹配的随机数。此外，为了保证能“解出来”，有时 Alice 需要丢弃某些无法映射的秘密比特，导致嵌入效率（Bits per Token）受损。

---

4. Discop (S&P 2023) —— 效率之王

【核心思想】
分布耦合 (Distribution Coupling)。与其在 [0,1] 区间上乱撞，不如直接把概率分布 $D$ 拆分成两个互斥的“平行宇宙” $D_0$ 和 $D_1$。

【算法流程拆解】

1. 分布拆分 (Splitting)：
   Discop 算法通过优化规划，将原始分布 $D$ 拆解为：

   $$D(t) = \frac{1}{2} D_0(t) + \frac{1}{2} D_1(t)$$

   • $D_0$ (比特 0 专用分布):
     • $P_0(\text{excellent}) = 1.0$ (归一化后)
     • $P_0(\text{good}) = 0$
     • $P_0(\text{bad}) = 0$
   • $D_1$ (比特 1 专用分布):
     • $P_1(\text{excellent}) = 0$
     • $P_1(\text{good}) = 0.5$
     • $P_1(\text{bad}) = 0.5$

   (注：验证一下 $\rightarrow 0.5 \times 1.0 + 0.5 \times 0 = 0.5$，excellent 的原始概率确实保住了)

2. 嵌入操作：

   • Alice 想要发送 1 (秘密的第一个比特)。
   • Alice 切换到 $D_1$ 分布。
   • 在 $D_1$ 中随机采样（掷骰子）：50% 概率选 good，50% 概率选 bad。
   • 假设选中 “good”。
   • 输出 Token： “good”。

3. 解码操作 (Bob)：

   • Bob 收到 “good”。
   • Bob 查看两个平行宇宙：
     • 在 $D_0$ 中，“good” 概率为 0 $\rightarrow$ 不可能来自这里。
     • 在 $D_1$ 中，“good” 概率为 0.5 $\rightarrow$ 必然来自这里。
   • 结论： 嵌入的比特是 1。

【深度批判】

• 优点：
  1. 解码 $O(1)$： 不需要像 Meteor 那样穷举，查表即知。
  2. 高容量： 它最大化了熵的利用率。
• 缺点：
  • 构造复杂： 对于非常复杂的长尾分布，如何完美拆分 $D_0$ 和 $D_1$ 且保证两边概率和为1，是一个复杂的图论/优化问题（Discop 使用了基于最大流的算法或贪心算法）。
  • 稳定性： 在低熵（Low Entropy）环境下，可能无法构建出有效的 $D_0, D_1$（例如某个词概率 0.99，拆不动）。

---