Discop：基于分布副本的可证明安全隐写

source. 6月 07, 2023

本文介绍了 Discop: Provably Secure Steganography in Practice Based on “Distribution Copies” (IEEE S&P ’23) 。

Title

隐写安全性

在隐写领域，可证明安全的追求由来已久。

1949年，Claud Shannon 在其经典论文 Communication Theory of Secrecy Systems 中开宗明义地指出了构建隐蔽系统的困难性。直到二十世纪九十年代，学界开始模仿密码学中的安全性定义来定义隐写的安全性。1998 年，Christian Cachin 给出了隐写的信息论安全 (information-theoretic security) 定义，使用载体数据分布 $P_{\mathrm{c}}$ 和载密数据分布 $P_{\mathrm{s}}$ 之间的 KL 散度 $D_{\mathrm{KL}}\left(P_{\mathrm{c}}|P_{\mathrm{s}} \right)$ 来建模隐写安全性——KL 散度越小，$P_{\mathrm{c}}$ 和 $P_{\mathrm{s}}$ 越接近，敌手做出错误判断的概率就越大，隐写系统也越安全。如果 $D_{\mathrm{KL}}\left(P_{\mathrm{c}}|P_{\mathrm{s}} \right)\le\epsilon$，则称隐写系统是 $\epsilon$-安全的；如果 $\epsilon=0$ ，则称隐写系统是绝对安全的 (perfectly secure) ，在这种情况下，$P_{\mathrm{c}}$ 和 $P_{\mathrm{s}}$ 严格相等，敌手判断一个对象是载体还是载密的能力无法好于随机猜测。2002 年，图灵奖得主 Manuel Blum 团队的 Hopper 等人在美密会上给出了隐写的计算安全 (computational security) 定义，他们假设敌手在玩一个判断某个对象是载体还是载密的区分游戏，如果所有概率多项式时间 (PPT) 敌手的攻击优势都关于安全参数可忽略 (negligible) ，则认为隐写系统是安全的。

Definitions:

载体 (cover) : an object without a secret message embedded
载密 (stego) : an object with a secret message embedded

References:

C. E. Shannon. Communication Theory of Secrecy Systems. BSTJ ’49
C. Cachin. An Information-Theoretic Model for Steganography. IH ’98
N. J. Hopper et al. Provably Secure Steganography. CRYPTO ’02

为什么需要可证明安全隐写

现有可证明安全隐写构造及其在实践中的问题

自隐写安全性的定义提出以来，研究者们相继提出了几种追求可证明安全的隐写构造。我们分析了它们在实践中的问题。

基于拒绝采样的构造：时间消耗的期望随着嵌入消息长度呈指数增长；当分布的最小熵非常小时，拒绝采样算法极易失败。
基于算术编码的构造：任意消息的概率都有 $2^{-l}\left(l\in \mathbb{N} \right)$ 的形式，相应地，载密也有 $2^{-l}$ 的形式。然而，模型预测出的载体数据分布几乎不可能与这种载密数据分布恰好匹配，这使得消息嵌入算法需要对载体数据分布进行调制，从而引入失真。为了减少失真，可以简单地通过填充来增加消息长度，使得载体数据的概率变得更小，更接近某个 $2^{-l}$ ；随着消息长度接近无穷大，失真趋于 0 ，这显然是不切实际的；即便如此，引入的失真是关于消息长度 (而非安全参数) 的可忽略函数，使得这种构造无法达到预期的安全性。
基于分组的构造：当且仅当分组是完美平衡时，这种构造是安全的。然而，离散概率分布难以平衡分组，使得这种构造无法达到预期的安全性。

Previous methods

References:

N. J. Hopper et al. Provably Secure Steganography. CRYPTO ’02
L. von Ahn and N. J. Hopper. Public-Key Steganography. EUROCRYPT ’04
M. Backes and C. Cachin. Public-Key Steganography with Active Attacks. TCC ’05
T. V. Le. Efficient Provably Secure Public Key Steganography. Cryptology ePrint Archive ’03
K. Yang et al. Provably Secure Generative Steganography Based on Autoregressive Model. IWDW ’18
Z. Ziegler et al. Neural Linguistic Steganography. EMNLP ’19
K. Chen et al. Distribution-Preserving Steganography Based on Text-to-Speech Generative Models. TDSC ’21
G. Kaptchuk et al. Meteor: Cryptographically Secure Steganography for Realistic Distributions. CCS ’21
S. Zhang et al. Provably Secure Generative Linguistic Steganography. ACL Findings ’21

基于分布副本的可证明安全隐写构造

在本文中，我们提出新的基于分布副本的可证明安全隐写构造。

我们以文本生成任务为例来介绍提出的隐写构造，这类任务一般使用自回归模型 (auto-regressive model) 如 GPT 系列模型，一个 token 一个 token 地生成文本。具体地，给定一个上文 (context) 作为输入，自回归模型会预测下一个 token 的概率分布 $\mathcal{P}^{(t)}=\Pr \left[x_{t}\mid x_{<t} \right]$ ，然后从这个概率分布中随机采样 (random sampling) 出一个 token，作为下一个 token 追加到上文的尾部。重复预测和随机采样，直至达到终止条件。

Auto-regressive model

随机采样一般通过以下步骤实现：

在 $\left[0,1 \right)$ 上，根据 $\mathcal{P}^{\left(t \right)}$ 为所有候选 token 分配互不相交的左闭右开区间，每个 token 对应的区间长度等于这个 token 被选中的概率；
消耗一个由伪随机数生成器 (PRNG) 生成的伪随机数 (PRN) $r^{\left(t \right)}$ ，选取 $r^{\left(t \right)}$ 落入的区间对应的 token 作为下一个 token 。

举例：假设 $r^{\left(t \right)}=0.937$ ，因为其落入 dear 对应的区间，所以选取 dear 作为下一个 token 。

Random sampling

在生成过程中，如何安全地嵌入消息？

我们认为这个问题的答案是，在秘密消息的控制下进行采样，这种采样需要满足两个条件：

不可区分 (indistinguishable) ：隐写采样应与随机采样不可区分；
可逆 (reversible) ：接收方可以将收到的 token 译码为秘密消息。

Sampling under control

基础构造

我们观察到，对于一个候选 token 数量大于 1 的概率分布来说，区间分配方案并不是唯一的。

这样，给定一个概率分布，我们可以为其创建多个分布副本 (distribution copies) ，然后使用分布副本的索引值 (index) 来表达消息。

我们通过循环移位 (rotate) 来创建分布副本。为了方便理解，这里给出一个实例。

假设概率分布为：

不妨以 a-b-c-d 顺序排列的分配方案作为作为初始区间分配方案，即分布副本 0。

若要嵌入 1 比特消息，则需要创建 $2^{1}=2$ 个分布副本，对应的移位步长为 $1/2=0.5$ 。

将分布副本 0循环移位 0.5 ，可得到分布副本 1。

Embedding

假设 PRNG 生成的 PRN $r^{\left(t \right)}=0.2$ 。

若消息 $m=0$ ，则从分布副本 0 采样，因为 $r^{\left(t \right)}$ 落入 b 对应的区间，所以采出 b 作为下一个 token ；
若消息 $m=1$ ，则从分布副本 1 采样，因为 $r^{\left(t \right)}$ 落入 d 对应的区间，所以采出 d 作为下一个 token 。

🤔️接收方如何提取消息？

如果接收方与发送方共享相同的上文、生成模型，他就可以拿到相同的概率分布；相似地，如果接收方与发送方共享相同的种子、PRNG，他就可以拿到相同的 PRN 。

这样，接收方可以与发送方同步相同的状态，并通过判断收到的 token 是从哪个分布副本采样得到的来提取消息。

Extraction

唯一译码条件、争议区间与嵌入率

如何保证接收方能正确提取消息？能嵌入多长消息？

不难推出，当且仅当消耗的 PRN 在所有分布副本中落入的区间对应的 token (下文简称“落入的 token ”) 互不相同时，这次采样可以唯一地表达消息。

沿用上面的例子，只嵌入 1 比特消息时，无论 PRN 是多少，其在所有分布副本中落入的 token 是互不相同的，因此可以唯一地表达消息；试图嵌入 2 比特消息时，需要创建 $2^{2}=4$ 个分布副本，对应的移位步长为 $1/4=0.25$ ，如下图所示。会出现 PRN 在多个分布副本中落入的 token 相同的情况，我们将这些交集称为争议区间 (disputed ranges) ，如下图中的灰色遮罩覆盖区域所示。当 PRN 不幸落入争议区间中，则无法嵌入 2 比特消息，只能回退到嵌入 1 比特消息的情况。

注意，争议区间的存在并不会影响消息提取的正确性，因为接收方与发送方同步相同的状态，可以计算出争议区间并判断 PRN 是否落入争议区间。因此，他知道发送方嵌入了多少比特消息，可以创建与发送方相同的分布副本来提取消息，并正确地提取消息。

我们推导出，这种构造的嵌入率约等于分布的最小熵 (minimum entropy) 。

通过递归提升嵌入率

提出的基础构造的嵌入率太低，仅约为分布的最小熵，与其理论极限 (分布的熵) 的差距较大，因此，我们进一步研究了如何提高嵌入率。

考虑一个简单的例子，假设有 a、b、c 三种 token ，概率分别为 0.5、0.25、0.25 。如果使用基础构造，那么只能嵌入 1 比特消息。

For this example, the basic construction can only embed 1 bit of information

但如果提前将 b 和 c 放入一个分组 $G$ 中，a 和 $G$ 的概率分别为 0.5 和 0.5 ，使用基础构造一定可以嵌入 1 比特消息。如果选择 $G$ (概率为 0.5 ) ，因为其中的 b 和 c 在归一化后的概率分别为 0.5 和 0.5 ，那么可以再次通过这种构造额外嵌入 1 比特消息。提升后的嵌入容量的期望为 1.5 比特。

For this example, the improved construction may embed longer message

这样，我们可以通过递归分组构建一棵二叉树 (实际选用的是 Huffman 树) ，然后在从根节点走到一个叶子节点的过程 (即若干次子节点选择的过程) 中嵌入消息。实际上，这相当于将原先的一轮多元分布采样分解为多轮二元分布采样，每次采样都可能可以嵌入 1 比特消息。

我们取分布副本的英文 (distribution copies) 中的部分字母，将提升后的构造称为 Discop 。

部署

理论上，Discop 可以部署于任何能给出显式概率分布的生成模型上。为了展示 Discop 对不同媒体生成任务的支持，我们选择了几种典型的生成任务和相应的公开预训练模型来部署 Discop 。

任务	描述	模型
文本生成	输入上文，生成其续写。	GPT-2, DistilGPT-2, Transformer-XL
图像补全	输入图像的上半部分，将其补全为完整图像。	Image GPT
语音合成	输入一段文本，合成其对应的语音。	Tacotron + WaveRNN

Deployments

实验评估

实验设置

考虑已在生成任务中广泛使用的 top-$p$ 采样，在截断参数 $p$ 取不同值的情况下开展实验。

在 GPT-2 124M 模型上，将 Discop 与现有的追求可证明安全的隐写方法 ADG、Meteor 进行对比。

Meteor 的初始版本 (下文称为 Meteor w/o sort) 嵌入率较低，因此，其作者设计了一种用于提升嵌入率的启发式排序算法 (下文将提升后的版本直接称为 Meteor) 。我们对 Meteor 的这两种版本都进行了实验。

评估指标

我们主要从安全性和效率 (包括时间效率和容量效率) 进行评估。

安全性：$P_{\mathrm{c}}$ 和 $P_{\mathrm{s}}$ 之间的 KL 散度，关注平均值 (Ave KLD) 和最大值 (Max KLD) ，越小越好。
时间效率：嵌入一比特消息需要的平均时间，总时间 / 消息总长度，越小越好。
容量效率：由于生成过程涉及随机采样，所以嵌入容量的理论极限并不是固定不变的。为了更好地刻画嵌入容量与其理论极限之间的距离，我们提出了一种全新的度量指标——对熵的利用率 (Utilization) ，越大越好。

Utilization

此外，我们还希望与正常生成相比，隐写的消息嵌入和提取引入的额外时间消耗尽可能少。

实验结果与分析

对比实验

Comparison

注：Meteor 有两个版本，表中 “Meteor w/o sort” 对应初始版本，“Meteor” 对应引入启发式排序算法提升后的版本。“Discop w/o recursion” 对应我们提出的基础构造。Random Sampling 对应随机采样，即不嵌入消息的正常生成。

总体来看，Discop 在几乎所有指标上都好于之前的方法。

安全性：ADG、Meteor 和 Meteor w/o sort 的 KL 散度远远达不到“可忽略”，这可能导致敌手获得区分载体与载密的不可忽略的优势。而 Discop 可以很好地保持分布。
时间效率：在 $p$ 取大多数值时，除 Meteor 外的隐写构造都不会引入过多的额外时间。Meteor 引入的启发式排序算法过于复杂，大大增加了其消息嵌入时间——若要嵌入相同长度的消息，Meteor 所需时间是 Discop 的 3.45~144.88 倍，这在需要实时隐写通信的场景可能是无法接受的。
容量效率：ADG 和 Meteor 的 Utilization 相当，约为 0.77~0.87 。Meteor w/o sort 的 Utilization 只有约 0.67~0.76 。而 Discop 可以比较充分地利用熵，其 Utilization 达到约 0.92~0.95 。

Discop 引入的额外时间

对于候选元素数为 50,257 的 GPT-2 而言，top-$p$ 截断 ($p\ne 1.00$) 去除了大量候选元素，使得额外时间很小。而对于候选元素数为 512 的 Image GPT 和候选元素数为 1024 的 WaveRNN ，不管 $p$ 的取值如何，Discop 引入的额外时间都相对较小。

总结

本文的主要贡献为：

分析了之前追求可证明安全的隐写方法在实践中的问题。
提出了全新的基于分布副本 (distribution copies) 的可证明安全隐写构造。
通过递归将嵌入容量提升至其理论极限的约 0.95 ，将提升后的方法命名为 Discop 。
将 Discop 部署于三种典型生成任务上，从安全性和效率两方面开展实验。

我们希望这个工作能为后续的隐私增强技术研究提供基础和灵感。

Jinyang Ding, Kejiang Chen, Yaofei Wang, Na Zhao, Weiming Zhang, and Nenghai Yu. “Discop: Provably Secure Steganography in Practice Based on ‘Distribution Copies’ ”, in 2023 IEEE Symposium on Security and Privacy (SP), IEEE Computer Society, May 2023, pp. 2238–2255. doi: 10.1109/SP46215.2023.10179287.

论文作者：丁锦扬，陈可江，王垚飞，赵娜，张卫明，俞能海

Personal homepage: https://dingjinyang.github.io/

Corrections

Fig. 2

In Fig. 2, the method rotate all intervals to the right by $d$, which is equivalent to rotating the consumed pseudo-random number to the left by $d$. However, in rest of this paper, the rotation direction is opposite: rotating all intervals to the left by $d$, which is equivalent to rotating the consumed pseudo-random number to the right by $d$.

Considering that the rotation direction is irrelevant to the correctness of the method description, there is nothing factually wrong with Fig. 2 itself. However, to prevent any potential confusion for readers due to the inconsistency, it would be advisable to modify Fig. 2 to align it with the rest.

Before modification:

corr_fig2_before

After modification:

corr_fig2_after

Accordingly, Paragraph 1 on Page 6 (the paragraph on the left of Fig. 2) requires an amendment: in the “distribution copies” with index 0 and 1 → in the “distribution copies” with index 0 and 3.

Minor

Page 2, inconsistent format: c) Efficient Attempts to Provably Secure Steganography → c) Efficient attempts to provably secure steganography.

Page 10, Algorithm 3:

$r_0\le\mathrm{separator}$ → $r_0<\mathrm{separator}$
$r_1\le\mathrm{separator}$ → $r_1<\mathrm{separator}$

Q&A

Q1. Detailed description of embedded rate calculation

On the bottom left corner of Page 6, you mentioned:

We denote the maximum token probability at time step $t$ as $p_{\max}^{(t)}$ , and the theoretical upper bound of $\beta^{(t)}$ as $\mathrm{B}^{(t)}$. According to the condition for unique decoding, it can be deduced that $p_{\max}^{(t)}/2<2^{-\mathrm{B}^{(t)}}\le p_{\max}^{(t)}$ , and $\beta=\lfloor \mathrm{B}^{(t)} \rfloor\in \mathbb{N}$, so

$\lfloor\log_{2} \frac{1}{p_{\max}^{(t)}} \rfloor\le \beta^{(t)} \le \lceil\log_{2} \frac{1}{p_{\max}^{(t)}} \rceil.$

Can you give a more detailed description?

A1

To understand $p_{\max}^{(t)}/2<2^{-\mathrm{B}^{(t)}}\le p_{\max}^{(t)}$, you need some imagination. The instantaneous embedding rate must be in integer bits, so $\beta^{(t)}\in\mathbb{N}$. To facilitate derivation, here we denote its theoretical upper bound as $\mathrm{B}^{(t)}\in\mathbb{R}$.

Overall, the two parts of the inequality $p_{\max}^{(t)}/2<2^{-\mathrm{B}^{(t)}}\le p_{\max}^{(t)}$ correspond to two extreme cases respectively.

Perhaps it would be easier to comprehend this using a pie chart, where the central angle of each slice is directly proportional to a token probability. Suppose there are four tokens, namely “a”, “b”, “c”, and “d”, with probabilities of 0.1, 0.3, 0.3, and 0.3, respectively.

We use line segments (in red) with one end at the origin of the circle and the other end on the circumference of the circle to represent the consumed pseudo-random number and its rotated values.

Now please recall to the condition for unique decoding:

When the tokens sampled by the consumed pseudo-random number from all “distribution copies” are different from each other, the receiver can uniquely decode the message.

To satisfy the condition, there should not be two or more line segments on each slice of the pie chart. In fact, we only need to focus on the maximum probability $p_{\max}^{(t)}$, because if there is only one line segment on the slice corresponding to the most probable token, then there must not be two or more line segments on any other single slice. In the following, we denote the slice corresponding to the most probable token as $s$.

The key point is that if there is already a line segment placed on $s$, its adjacent line segments cannot also be on $s$. When $\mathrm{B}^{(t)}$ reaches its maximum, the corresponding theoretical rotation step $2^{-\mathrm{B}^{(t)}}$ is at its minimum. $2^{-\mathrm{B}^{(t)}}>p_{\max}^{(t)}/2$ corresponds to an extreme case where a line segment is precisely placed at the center of $s$. In this case, the line segment is equidistant from both the start and end points of the slice, with the distances of $p_{\max}^{(t)}/2$ each. To ensure that its adjacent line segments fall outside of $s$, it must hold true that $2^{-\mathrm{B}^{(t)}}>p_{\max}^{(t)}/2$. Please note that due to the intervals being left-closed and right-open, the equal sign cannot be achieved.

$2^{-\mathrm{B}^{(t)}}\le p_{\max}^{(t)}$ corresponds to the other extreme case where a line segment is precisely placed at the start point of $s$. In this case, $2^{-\mathrm{B}^{(t)}}$ reaches its maximum when the next line segment is precisely placed at the start point of the subsequent slice, so $2^{-\mathrm{B}^{(t)}}\le p_{\max}^{(t)}$.

It crucial to emphasize that $\mathrm{B}^{(t)}$ signify the maximum value of the amount of information that can be embedded at time step $t$, since it is meaningless to discuss a scenario where the method allows embedding $m$ bits but only $n$ bits are embedded ($m>n$). If you speak Chinese, you can understand it as “应嵌尽嵌” (meaning “embed as much as possible”). Without a line segment on $s$, there would be an underutilization of the embedding rate.

Given $\beta^{(t)}=\lfloor \mathrm{B}^{(t)} \rfloor\in \mathbb{N}$, it readily follows that

$\lfloor\log_{2} \frac{1}{p_{\max}^{(t)}} \rfloor\le \beta^{(t)} \le \lceil\log_{2} \frac{1}{p_{\max}^{(t)}} \rceil.$

Any other questions?

If you have any questions about this paper, please don’t hesitate to contact me via email!

Jinyang Ding (source@mail.ustc.edu.cn)

本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2023/06/07/discop-sp23/