C COMPIN BLOG

COMPIN TECHNICAL NOTE

压缩与加密一体化：从 Homophonic Coding、Arithmetic Coding 到 ANS Compcrypt 与 ENCORE

梳理联合压缩与加密从 Homophonic Coding、随机化算术编码到 ANS Compcrypt 与 ENCORE 的研究路线、理论边界和开放问题。

更新于
  • 数据压缩
  • 密码学
  • Huffman
  • ANS
  • 信息论

压缩和加密通常被视为两个独立步骤：

$$ \text{Original Data} \rightarrow \text{Compression} \rightarrow \text{Encryption} \rightarrow \text{Ciphertext}. $$

这样做非常自然。压缩首先消除数据中的统计冗余，而加密随后隐藏剩余的信息结构。

但从信息论角度看，两者之间存在一个很有意思的共同点：一个理想的压缩输出应该接近高熵比特流，而一个理想的密文同样应该在攻击者看来接近随机比特流。

于是很自然地会产生一个问题：

既然压缩和加密最终都在试图消除输入数据中可以被利用的统计结构，是否可以设计一个统一的编码过程，同时完成压缩和加密？

这个问题很漂亮，但并不新。从 20 世纪 80 年代的 Homophonic Coding，到随机化 Arithmetic Coding，再到近年来基于 ANS 的 Compcrypt，以及 2025 年提出的 ENCORE，已经形成了一条相当长的研究路线。

本文试图回答三个问题：

  1. 为什么人们反复试图把压缩和加密融合？
  2. 历史上已经有哪些主要技术路线？
  3. 这个问题今天到底解决了没有？

本文的基本判断是：

“联合压缩与加密”已经是一个历史悠久的研究方向，但这个问题仍然没有一个像 AES 或现代压缩算法那样干净、普适且令人信服的统一答案。很多方案实现的是“压缩器中加入某些密码学特征”，而不是从理论上证明压缩和加密真正成为同一个操作。

一、为什么压缩和加密似乎天然相关？

设数据源随机变量为 $X$，概率分布为 $P(X)$。

对于一个理想无损压缩器，符号 $x$ 最理想的编码长度约为

$$ L(x)\approx-\log_2P(x). $$

高概率事件使用短码，低概率事件使用长码。

如果一个编码后的比特流仍存在明显的统计规律，例如

$$ P(0)\gg P(1), $$

或者某些 bit pattern 大量重复，那么理论上说明其中仍然存在可以被进一步利用的冗余。

因此，好的压缩输出通常具有很高的熵。

密码学则从另一个方向追求类似的表象：攻击者即使观察密文，也不能从其中提取能够预测明文的信息。

这就产生了一个很诱人的想法：

$$ \boxed{ \text{Compression Randomness} \stackrel{?}{=} \text{Cryptographic Randomness} } $$

遗憾的是，这个等号通常并不成立。

一个序列完全可以满足

$$ P(Z_i=0)=P(Z_i=1)=\frac12, $$

却仍然完全可以预测。

例如随机选择下面两个序列之一：

010101010101...
101010101010...

对于任意固定位置，

$$ P(Z_i=0)=\frac12, $$

但只需要知道前一个 bit，下一个 bit 就可以被完全预测。

因此：

$$ \text{高熵} \neq \text{密码安全}, $$

更准确地说：

$$ \text{边缘分布均匀} \not\Rightarrow \text{不可预测} \not\Rightarrow \text{语义安全}. $$

这是所有“压缩即加密”思想首先需要跨越的一道理论鸿沟。

二、Huffman Coding 本身并不是“英文压缩算法”

谈到压缩与加密结合，Huffman 经常出现。但需要首先澄清：Huffman coding 并不是针对英文设计的。

它只要求存在一个离散符号集合

$$ \Omega=\{\omega_1,\omega_2,\ldots,\omega_n\} $$

以及对应概率 $P(\omega_i)$。

高概率符号获得短码，低概率符号获得长码。

所谓“symbol”可以是英文字符，也可以是：

  • 一个汉字；
  • 一个 UTF-8 byte；
  • 一个中文词；
  • 一条机器指令；
  • 一个协议字段值；
  • 一个 timestamp delta；
  • 一个图像符号。

因此真正决定压缩效果的，通常并不是 Huffman 本身，而是源模型。

可以把压缩简单理解成：

$$ \boxed{ \text{Compression}=\text{Modeling} + \text{Entropy Coding} } $$

例如一个 64 bit timestamp 如果直接作为符号进行编码，几乎没有意义；但如果先计算

$$ \Delta t_i=t_i-t_{i-1}, $$

而绝大多数情况下都有

$$ \Delta t_i=1, $$

那么数据立即变得高度可压缩。

现代压缩技术真正困难的一部分，因此往往是如何得到好的

$$ P(X_i\mid X_{而不仅仅是最后选择 Huffman、Arithmetic Coding 还是 ANS。

三、第一条历史路线：Homophonic Coding

早在 1988 年，Christoph Günther 就发表了 A Universal Algorithm for Homophonic Coding。

Homophonic coding 的目标之一，就是把具有非均匀概率分布的消息映射成频率更加均匀的表示。

其基本思想可以理解为：一个源符号不再只有唯一表示，而是可以对应多个不同 codeword。

例如：

$$ A\rightarrow \{c_1,c_2,c_3,\ldots\}. $$

编码器随机选择其中一个表示。

这样可以把原始数据明显的概率偏差“摊平”。

后续研究进一步尝试让输出趋近 independent and uniformly distributed bits。但这里有一个非常重要的边界：

Homophonic coding 本身并不是完整意义上的 encryption。

它更多是一种消除明文统计特征、提高后续密码系统抗统计分析能力的编码技术。

实际上，这已经提前揭示了后来很多 compression-encryption 工作都会遇到的问题：

$$ \boxed{ \text{把分布变均匀} \neq \text{获得密码学安全}. } $$

四、第二条路线：直接随机化 Arithmetic Coding

Arithmetic Coding 与 Huffman 最大的区别之一，是它不要求码长必须是整数 bit。

理论上一个概率为 $p$ 的事件携带

$$ -\log_2p $$

bit 信息。

Arithmetic Coding 可以更加精确地逼近这个值，因此在非 dyadic 概率上通常比简单 Huffman 更自然。

2006 年，Grangetto、Magli 和 Olmo 在 IEEE Transactions on Multimedia 中提出 Randomized Arithmetic Coding，用于 selective encryption。

核心做法不是：

$$ \text{Compression} \rightarrow \text{AES} $$

而是在 arithmetic coding 过程本身加入由密钥控制的随机化，并尽量不损失编码效率。

这条路线非常重要，因为它实际上已经提出了后来很多“联合压缩加密”的核心哲学：

$$ \boxed{ \text{不要先产生 compressed stream 再加密，} \text{而是在 entropy coder 内部完成随机化。} } $$

因此，如果今天只是提出：

“能不能修改 Huffman 或 Arithmetic Coding 的编码方式，同时达到加密效果？”

这已经远远算不上新问题。

五、第三条路线：ANS 让这个问题变得更加有趣

Asymmetric Numeral Systems，简称 ANS，是近年来非常重要的一类 entropy coding 方法。

ANS 可以获得接近 Arithmetic Coding 的压缩率，同时实现接近 Huffman 的高速编码和解码，因此已经进入很多现代压缩系统。

ANS 的一个特殊之处是：它实际上维护一个编码状态 $x$，然后根据当前 symbol 进行可逆的状态跳转：

$$ x'=C(x,s). $$

在 tabled ANS 中，这种状态跳转由编码表控制。

因此很自然地产生一个想法：

如果编码表或者 ANS state transition 由密钥控制，那么压缩过程本身是否就可以顺便承担 encryption？

Duda 与 Niemiec 在 2016 年系统讨论了这个问题。他们提出通过扰动 ANS coding table，将部分加密功能直接嵌入 entropy coding，并讨论减少传统密码算法计算量的可能性。

但后续研究发现，仅仅隐藏 ANS encoding table 并不够安全。

原因在于不同 ANS table 可能产生不同的内部状态统计分布，而足够长的 ciphertext 可以暴露这种“统计指纹”。

2022 年 Camtepe 等人进一步研究了 ANS-based compcrypt。他们首先分析简单隐藏编码表所面对的统计攻击，然后引入 randomized ANS state jumps，并结合 Keccak/MonkeyDuplex 一类密码学构件，进一步考虑 confidentiality、integrity、authentication 和 streaming。

这件事情非常有启发性。

它意味着，当真正要求现代密码学意义上的安全以后：

$$ \text{compression 本身产生的随机性} $$

通常还是不够。

最终仍然需要：

$$ \text{PRF/PRG} + \text{cryptographic state} + \text{authentication}. $$

换句话说：

$$ \boxed{ \text{联合设计可以减少系统边界，} \text{但密码学并不会凭空消失。} } $$

六、2025 年的 ENCORE：一个很漂亮的问题，但没有真正闭环

2025 年 Cooper 和 Fickes 在 arXiv 提出了 Cryptographic Compression，协议名为 ENCORE。

ENCORE 的出发点非常漂亮。

首先根据源分布 $\sigma$ 建立 Huffman code $C$，并定义该 Huffman tree 隐含的 dyadic distribution

$$ \pi(\omega)=2^{-|C(\omega)|}. $$

然后构造随机变换矩阵 $B$，满足

$$ \sigma B=\pi. $$

即先把真实源分布转换成与 Huffman tree 完全匹配的 dyadic distribution，再进行 Huffman 编码。论文将状态分成 overrepresented 和 underrepresented 两类，并通过 $B$ 在两类状态之间搬移概率质量。

这个构造依赖一个很漂亮的事实。

如果

$$ X_i\stackrel{iid}{\sim}\pi $$

且

$$ \pi(\omega)=2^{-|C(\omega)|}, $$

那么 Huffman 输出 bit stream 满足

$$ P(Z_j=0\mid Z_1,\ldots,Z_{j-1})=\frac12. $$

因此，在这个非常理想的 iid dyadic 情况下，Huffman 输出确实等价于 iid fair coin bits。

这是 ENCORE 中真正值得注意的理论观察。

问题出现在如何从这个理想结果跨越到真实数据。

七、ENCORE 的第一个结构性问题：为了随机化数据，又不得不把修改信息传回来

假设原始分布为

$$ \sigma=(0.6,0.25,0.15), $$

而 Huffman tree 对应的理想 dyadic distribution 是

$$ \pi=(0.5,0.25,0.25). $$

那么 ENCORE 需要随机把一部分第一个 symbol 修改成第三个 symbol，从而把概率质量从 $0.6$ 搬到 $0.5$。

问题是：

$$ X\rightarrow Y $$

改变了原始数据。

接收端要恢复 $X$，就必须知道哪些位置发生了 transformation。

因此 ENCORE 实际拥有两股数据：

$$ \text{encoded-transformed stream} $$

以及

$$ \text{transformation-reconstruction stream}. $$

论文明确提出，第二股 reconstruction stream 需要再次压缩并使用传统 cryptographic scheme 加密，然后再与主 stream 交织。

于是一个很自然的问题出现了：

$$ \boxed{ \text{既然仍然需要传统加密，} \text{整个复杂结构到底获得了什么净收益？} } $$

更重要的是，从信息论角度看，这种随机 transformation 不可能产生免费的压缩收益。

设

$$ X\rightarrow Y $$

为随机变换。

若发送 $Y$ 后还必须无损恢复 $X$，辅助信息理论上至少需要包含

$$ H(X\mid Y) $$

的信息。

因此总体信息量会出现

$$ H(Y)+H(X\mid Y). $$

根据 entropy chain rule：

$$ H(Y)+H(X\mid Y)=H(X)+H(Y\mid X). $$

只要 transformation 本身具有随机性：

$$ H(Y\mid X)>0, $$

就有

$$ H(Y)+H(X\mid Y)>H(X). $$

也就是说：

为了把源重新塑造成一个漂亮的 dyadic distribution 而引入的随机性，最终必须通过 reconstruction information 以某种形式偿还。

这构成了 ENCORE 非常根本的结构性困难。

八、ENCORE 的第二个问题：Markov 推广的关键证明存在问题

ENCORE 的理想 iid-dyadic 结果是漂亮的。

但真实数据通常不是 iid，于是论文试图把结果推广到 ergodic Markov source。

设 Markov chain 的 stationary distribution 为 $\sigma$。

mixing theory 能够得到的结论是

$$ P^n\rightarrow\sigma. $$

然而在 Proposition 3.7 的证明中，论文直接使用了

$$ |P^n-\pi| \le e^{-n/\tau}, $$

即把 Markov chain 的 mixing target 从 $\sigma$ 换成了 Huffman implied distribution $\pi$。

但 ENCORE 的整个 transformation 恰恰建立在一般情况下

$$ \sigma\neq\pi $$

这一事实上。论文前文明确定义 stationary distribution 为 $\sigma$，而 Proposition 3.7 的证明却直接将 mixing bound 用到了 $\pi$。

因此这一关键推导按论文当前形式并不成立。

而且即使修正这个问题，仍然还存在更深的一层：

$$ P(Z_j=0)\approx\frac12 $$

只说明单 bit 的边缘分布接近均匀。

真正类似 next-bit security 的条件应该接近

$$ P(Z_j=0\mid Z_{而密码学意义上的 semantic security 或 IND-CPA 又比 next-bit marginal/randomness 更强。

所以存在一条不能随意跳过的逻辑链：

$$ \boxed{ \text{Uniform Marginals} \not\Rightarrow \text{Next-bit Unpredictability} \not\Rightarrow \text{Cryptographic Security}. } $$

因此，把 ENCORE 称为一个已经完成的 compression-encryption protocol，并不充分。

更准确的评价是：

ENCORE 提出了一个有趣的信息论观察和一个协议构想，但并没有真正证明这个构想在一般数据源上同时实现了有效压缩和密码学安全。

九、另一个重要事实：联合压缩加密并不是 ENCORE 才提出的问题

近年来仍然有人继续研究 Huffman、Arithmetic Coding、ANS 等 entropy coder 与 cryptography 的结合。

这说明即使到了今天，“能否在 entropy coding 本身中嵌入 cryptographic transformation”仍然具有研究吸引力。

但另一方面，它也更加说明：

$$ \boxed{ \text{compression + encryption} } $$

本身已经不能算一个新的研究命题。

新的工作必须回答：

与几十年来的 homophonic coding、randomized arithmetic coding、secure compression 和 ANS compcrypt 相比，究竟新增了什么问题？

如果只是重新设计：

$$ \text{keyed Huffman tree}, $$

或者

$$ \text{keyed arithmetic coder}, $$

甚至

$$ \text{keyed ANS state transition}, $$

都很可能只是已有研究路线的另一种实现。

十、为什么这个方向一直没有彻底替代“先压缩、再加密”？

这可能是整个调研中最值得思考的问题。

传统系统：

$$ \text{Compress} \rightarrow \text{AES-GCM / ChaCha20-Poly1305} $$

虽然看起来做了两件事情，但它有三个巨大优势。

首先，两个模块的职责非常清楚：

$$ \text{compressor负责效率}, $$$$ \text{cipher负责安全}. $$

其次，现代对称密码非常快，而且真正需要的随机熵并不会随着数据长度按照 $1:1$ 增长。

一个较短的 secret key 和 nonce，可以通过现代 PRF、stream cipher 或 block cipher 产生很长的伪随机序列。

因此：

$$ \text{减少被加密的数据量} $$

并不意味着：

$$ \text{按相同比例减少真正随机熵需求}. $$

这是一些 compression-encryption 方案容易产生误解的地方。

第三，也是最关键的一点：

现代 authenticated encryption 不只是提供“看起来随机”。

它还同时提供：

$$ \text{Confidentiality}, $$$$ \text{Integrity}, $$$$ \text{Authentication}, $$

以及在正确协议设计下的 replay protection。

而一个 entropy coder 天然解决的只是：

$$ \text{redundancy removal}. $$

从“消除统计冗余”走到完整密码协议，中间还有很长的距离。

十一、这个问题真正困难的地方：安全与压缩目标并不完全一致

压缩希望充分利用源统计。

假设消息 $x$ 的概率很高，那么压缩器希望

$$ L(x) $$

尽可能短。

但是这意味着 ciphertext length 本身可能暴露

$$ P(x), $$

甚至暴露消息类别。

如果要求不同 plaintext 完全隐藏长度，就必须进行 padding。

而 padding 又必然损害 compression ratio。

因此存在一个非常根本的矛盾：

$$ \boxed{ \text{Compression Efficiency} \leftrightarrow \text{Metadata / Length Privacy}. } $$

这可能比“怎样重新排列 Huffman tree”更加值得研究。

换句话说，一个真正完整的 secure compression 理论不应该只问：

输出 bit 是否随机？

而应该明确问：

$$ \boxed{ \text{允许泄漏什么？} } $$

例如：

  • 是否允许泄漏 compressed length？
  • 是否允许泄漏消息边界？
  • 是否允许泄漏 source model？
  • 是否允许泄漏 packet type？
  • streaming 状态是否可观察？
  • chosen plaintext adversary 能否控制输入统计？

只有这些问题被明确以后，“安全压缩”才真正拥有密码学定义。

十二、当前技术路线可以怎样理解？

如果把几十年的研究压缩成一张图，大致可以得到：

源统计随机化
    │
    ├── Homophonic Coding
    │       └── 让非均匀源更加均匀
    │
    ├── Randomized Arithmetic Coding
    │       └── 在算术编码过程中引入密钥控制
    │
    ├── Secure / Keyed Huffman、LZW、BWT
    │       └── 利用多个等价编码结构作为密钥自由度
    │
    ├── ANS Compcrypt
    │       └── 在 entropy coder state transition 中加入密码随机化
    │           + Sponge / Authentication
    │
    └── ENCORE
            └── Source Distribution
                → Dyadic Distribution
                → Uniform Huffman Bits
                + Encrypted Reconstruction Stream

从历史演进看，一个趋势非常明显。

早期工作倾向于相信：

$$ \text{隐藏编码表} $$

或者

$$ \text{让输出统计上均匀} $$

就能够提供足够安全性。

后来的工作越来越不得不重新引入：

$$ \text{PRNG}, $$$$ \text{PRF}, $$$$ \text{sponge}, $$$$ \text{authentication tag}. $$

这似乎说明：

$$ \boxed{ \text{压缩可以贡献随机性，} \text{但目前并不能证明它可以完全替代现代密码学。} } $$

十三、那么这个方向今天还有没有研究价值？

如果研究题目只是：

“设计一种同时完成压缩和加密的方法。”

我的判断是：不够新。

如果只是：

“把密钥嵌入 Huffman tree。”

同样已经有很长的历史。

如果只是：

“利用 ANS state 做加密。”

这一方向也已经存在较系统的工作。

真正还值得研究的问题，我认为已经转向更基础的几个方向。

1. 压缩随机性究竟能替代多少密码学工作？

需要回答：

$$ \boxed{ \text{压缩所产生的高熵，} \text{究竟能够严格替代多少密码学随机化？} } $$

这里需要的是 theorem，而不是简单通过 NIST randomness test 证明输出“看起来很随机”。

2. Compression–privacy tradeoff 的理论边界

真正值得问的是：

$$ \boxed{ \text{在给定安全泄漏模型下，} \text{compression rate 与 privacy 的理论最优边界是什么？} } $$

特别是 ciphertext length、stream boundary 和 source-model leakage。

例如可以考虑：

$$ \min \mathbb E[L(X)] $$

subject to

$$ I(X;\mathcal L(X))\le\epsilon, $$

其中 $\mathcal L(X)$ 表示允许攻击者观察到的长度或 metadata。

这已经是一个比“随机修改 Huffman tree”更加基础的信息论问题。

3. 压缩态、受保护态和计算态能否成为同一种表示？

这可能是一个更有意思的方向。

传统系统是：

$$ \text{compressed ciphertext} \rightarrow \text{decrypt} \rightarrow \text{decompress} \rightarrow \text{compute}. $$

如果未来某些系统能够直接在某种受保护的压缩表示上执行：

$$ \boxed{ \text{Protected Representation}=\text{Compressed Representation} + \text{Executable Representation} }, $$

那么问题就已经不再是传统 compcrypt，而变成了表示、传输与计算的统一。

这可能比单纯重新设计一种 compression-encryption algorithm 更值得探索。

十四、总结

压缩和加密确实共享一个令人着迷的目标：

$$ \text{消除输入中可被利用的结构}. $$

但几十年的研究已经说明：

$$ \boxed{ \text{Compression Randomness} \neq \text{Cryptographic Security}. } $$

Homophonic coding 很早就开始研究如何把非均匀源转化为更加均匀的表示；

Randomized Arithmetic Coding 把密钥随机化嵌入 entropy coding；

ANS 又提供了更加灵活的 state-based entropy coder，并催生了 compcrypt 设计；

ENCORE 则重新从一个很漂亮的角度出发：

$$ \text{Source Distribution} \rightarrow \text{Dyadic Distribution} \rightarrow \text{Uniform Huffman Bits}. $$

但 ENCORE 同时也很好地说明了这个问题有多难。

一旦修改源 symbol，就需要 reconstruction information；

一旦 reconstruction information 泄漏，就可能暴露原始数据；

一旦真正保护 reconstruction stream，就又必须引入传统 encryption；

而从“输出接近均匀”到“真正密码安全”，又需要远比简单 bit-frequency analysis 更强的理论。

因此，对这个领域比较准确的评价可能是：

联合压缩与加密不是一个新问题，也不是一个已经彻底解决的问题。

它真正没有解决的部分，不是如何再发明一个带密钥的 Huffman 或 ANS，而是如何建立一个统一理论，回答压缩所消除的冗余究竟能在什么条件下转化为可证明的安全收益，以及这种收益的理论上限在哪里。

这也是这个方向今天仍然值得关注的地方。

参考文献

  1. C. G. Günther, A Universal Algorithm for Homophonic Coding, EUROCRYPT 1988, LNCS 330, pp. 405–414.
  2. M. Grangetto, E. Magli, G. Olmo, Multimedia Selective Encryption by Means of Randomized Arithmetic Coding, IEEE Transactions on Multimedia, Vol. 8, No. 5, 2006.
  3. J. Duda, M. Niemiec, Lightweight Compression with Encryption Based on Asymmetric Numeral Systems, arXiv:1612.04662, 2016.
  4. S. Camtepe et al., ANS-based Compression and Encryption with 128-bit Security, International Journal of Information Security, Vol. 21, pp. 1051–1067, 2022.
  5. J. Cooper, G. Fickes, Cryptographic Compression, arXiv:2501.16184, 2025.
  6. Y. Gross, S. T. Klein, E. Opalinsky, R. Revivo, D. Shapira, Compression Cryptosystem, The Computer Journal, Vol. 68, No. 8, pp. 1062–1073, 2025.