一个群元素解密一整区块：Crypto 2026 用"部分分式"重做加密内存池

TL;DR

内存池公开可见是 MEV 的根源，加密内存池则要求验证者阈值解密——但传统方案里每个验证者要为 ℓ 笔交易各发一个解密份额，每区块 O(Nℓ) 通信。Crypto 2026 的这篇论文给出了第一个”三无”方案：无 epoch（不用按区块高度预估解密轮次）、无 index 依赖（不怕审查攻击）、参数全面最优（密文、预解密密钥、公共参数都是同类最小）。核心技巧是高中数学里的部分分式分解：定义 $p_i(X)=1/(X+i)$，把整批 ℓ 个密文的”一次性垫”全部编织进一个群元素 $sbk = \sum_i p_i(x)\cdot ct_i[1]$ 里，解密时靠分式乘积的线性无关性把每个垫单独剥出来。实测 512 个密文：预解密 50ms、解密 3.6s（短密文变体）。

论文信息卡

• 标题：Efficient Batch Threshold Encryption Using Partial Fraction Techniques
• 作者：Dan Boneh（Stanford）、Rohit Nema（Stanford）、Arnab Roy（Mysten Labs）、Ertem Nusret Tas（a16z Crypto Research）
• 会议：CRYPTO 2026（已接收；ePrint 首页未印会议脚注，接收信息经同行论文引用与作者 2026 年演讲幻灯片交叉确认）
• 原文链接：https://eprint.iacr.org/2026/674
• 实现代码：https://github.com/entrohpy/batch-enc-partial-fractions（Rust + arkworks，拼写照论文原文）

背景

问题先说清楚。区块链的内存池是公开的：你的交易还没上链，全世界已经能看到你要买什么。抢跑机器人和三明治攻击就吃这碗饭，这就是 MEV。缓解思路之一是加密内存池：交易先加密进池，解密密钥由验证者们阈值共享；区块落定之后，验证者们各自发布解密份额，交易内容才公开，抢跑者无从下手。

但这里有个工程痛点：传统方案里，每个验证者要为 ℓ 笔交易各发一个解密份额，一个区块就是 N 个验证者 × ℓ 笔交易 = O(Nℓ) 的通信量。批量阈值加密（batch threshold encryption）要解决的正是这个：每个验证者只发一个”预解密密钥的份额”，ℓ 笔交易一次解密完，通信降到 O(N)。

前人工作卡在哪？论文梳理了四条线，各有各的毛病：

第一条线是 batch IBE，它是 epoch 制的：每个 epoch（区块高度区间）只能发布一个预解密密钥。交易加密时得先猜自己会落在哪个 epoch，猜错了就得重新加密提交，可用性很差。

第二条线是 BEAT-MEV（USENIX Security ‘25），它是 epochless 的，但要求同一批次里每个密文的发送者自选的 index 互不相同——这就是 index 依赖。攻击者只需提交 $O(\log \ell)$ 个和目标交易同 index 的密文，就能把目标交易挤出批次（审查攻击）；而对 batch IBE 发动同类攻击需要 $O(\ell)$ 个密文 flooding，贵了指数级。雪上加霜的是，它的公共参数是二次方的：$(\ell+1)|G_1| + \ell^2|G_2|$。

第三条线是 TrX，第一个 BFT 场景的加密内存池实现，但仍有 epoch，且公共参数随批次数 κ 线性增长（$\kappa\ell|G_1|+|G_2|$）。

第四条线是 Boneh-Laufer-Tas 的 LWE 格基方案：第一个无 epoch 且公钥简洁的后量子路线，但格密码的参数在实践中大得多，工程上不划算。

所以局面是：要么被 epoch 绑死，要么被 index 绑死，要么参数爆炸。这篇论文的目标就是把三副枷锁一次性摘掉。

方法拆解

第一步：数学武器——部分分式

全文的数学地基只有两行，来自 Jutla-Nema-Roy（Eurocrypt 2026）形式化的观察。定义 $p_i(X) := 1/(X+i)$，$q_i(X) := p_i(X)^2 = 1/(X+i)^2$。

观察 1（分解）：$p_i(X)\cdot p_j(X) = (p_i(X) - p_j(X))/(j-i)$，$i \neq j$。有理函数的乘积可以化成同类分式的线性组合，系数是简单的差商，极好算。

观察 2（线性无关）：形如 $(\sum c_i p_i(X) + \sum c_i/(j-i))\cdot p_j(X)$ 的有理函数族是线性无关的。这保证了解密时能解出满秩的线性方程组——没有这条，后面”剥垫”的每一步都不成立。

直觉上可以这么理解：不同的分式 $p_i$ 像是不同”频率”的信号，乘起来会混频（观察 1 告诉你混频结果恰好能分解回各频率的线性组合），而观察 2 保证这些频率互不干扰。整篇论文就是把这个数学事实玩出了花。

第二步：热身——带 index 依赖的批量加密

先看一个简化版（论文 §2.2），理解”一个群元素编码整批”的核心手法。

Setup 采样随机数 $x$ 作为主密钥，公钥里放 $\{p_i(x), q_i(x)\}$ 的群编码。加密第 $i$ 个消息：$ct_i = ([r_i]_1,\ m_i + r_i\cdot [q_i(x)]_T)$——消息被二次分式 $q_i(x)$ 做成一次性垫（one-time pad）盖住。

预解密密钥长这样：

$sbk := \sum_i p_i(x)\cdot ct_i[1]$

注意它只有一个群元素，却编码了整批 ℓ 个密文的随机数信息。这就是全文最漂亮的想法。

解密第 $j$ 个密文时，做配对 $e(sbk, [p_j(x)]_2)$，得到 $\sum_i r_i[p_j(x)p_i(x)]_T$。用观察 1 把 $i \neq j$ 的交叉项全部拆成线性分式的差，再用 $\ell-1$ 个配对把线性部分”减掉”，最后剩下的就是二次项 $r_j\cdot[q_j(x)]_T$——一次性垫到手，$m_j$ 自然解出。

这个热身方案的缺陷也很明显：如果两个密文用了相同的 index $i$，它们的一次性垫就混在一起解不开了——这就是 index 依赖，也是 BEAT-MEV 被审查攻击打穿的根因。

第三步：关键一跃——把 index 当作”当事人”

去 index 依赖是全文最妙的一跃（§2.3）。作者把 Jutla-Nema-Roy 的阈值加密构造和上面的热身方案拼起来：把 ℓ 个 index 看成 ℓ 个”当事人”，Setup 直接公布每个 index 的”公钥” $[p_i(x)]_1$ 和”私钥” $[p_i(x)]_2$。

等等——私钥公开？这正是视角转换的精妙处：在阈值加密的语义里，密文的”未授权集”就是全部 index，配对产生的是二次项而非线性方程，攻击者拿着这些”私钥”也解不出任何东西。公开无妨，index 分配问题彻底消失：index 不再需要发送者协调，直接用 0,1,2,…,ℓ 当编号就行。

新的密文结构：$ct = ([r]_1,\ r\cdot\sum_{i=-1}^{\ell}[p_i(x)]_1,\ r\cdot[p_0(x)]_T + m)$。一次性垫改用线性分式 $p_0(x)$；$p_{-1}(x)$ 是引入的额外”哑元分式”，后面解方程要用。

PreDec 不变，还是 $sbk = \sum_i p_i(x)\cdot ct_i[1]$。解密第 $j$ 个密文分三步走：

1. 按热身方案，配对 $sbk$ 与 $[p_j(x)]_2$，剥离出二次项 $[r_j q_j(x)]_T$（论文公式 2）；
2. 配对 $ct_j[2]$ 与 $[p_j(x)]_2$，减去二次项和 ℓ 个 $p_i(x)$ 的倍数，得到方程（3）：$r_j\cdot([p_{-1}(x)]_T/(j+1) + [p_0(x)]_T/j)$；
3. 配对 $ct_j[2]$ 与 $[1]_2$ 并剥离，得到方程（4）：$r_j\cdot([p_{-1}(x)]_T + [p_0(x)]_T)$。

两个独立的线性方程、两个未知量（$[p_{-1}(x)]_T$ 和 $[p_0(x)]_T$ 的 $r_j$ 倍数），解出一次性垫 $R_j = r_j\cdot[p_0(x)]_T$，$m_j = ct_j[3] - R_j$。整个流程如下：

flowchart LR
    A[用户：加密交易<br/>ct = (rG, ..., m + r·pad)] --> B[加密内存池<br/>ℓ 个密文公开可见]
    B --> C[各验证者：发布份额<br/>sbk_j = Σ s_ij·ct_i[1]<br/>（单个群元素）]
    C --> D[聚合：Lagrange 加权求和<br/>得预解密密钥 sbk]
    D --> E[任意人：用 sbk 逐个解密<br/>分式技巧剥出一次性垫<br/>还原 m_j]

第四步：效率优化——配对摊销 + FFT

朴素实现每解密一个密文要 $O(\ell)$ 个配对，全批就是 $O(\ell^2)$，512 个密文要 26 万次配对，不可接受。论文做了两层优化（§2.4/§4.1.2）：

• 配对摊销：预计算 $tm_j = e(ct_j[1], [p_j(x)]_2)$，在同批解密之间复用，把每密文的配对数摊销到 5 个；
• FFT 加速：解密里的三个多标量乘法形如 $\sum_i ct_i[1]/(j-i)$，把 index 换成单位根 $\{\omega,\dots,\omega^\ell\}$ 后变成循环卷积，用 FFT 做到 $O(\ell \log \ell)$ 群运算（要求 ℓ 是 2 的幂）。

第五步：CCA-2 安全——模拟可抽取的 Schnorr NIZK

批量加密必须抗 CCA-2：攻击者可能篡改、复制密文来套取信息。每个密文附一个 Schnorr 型 NIZK，证明”密文格式正确且我知道随机数 $r$“。精妙之处在于：承载消息的第三分量 $ct[3]$ 不受关系约束，只作为 tag 进入 Fiat-Shamir 哈希——改动密文的任何一个比特都会让证明失效。

但这里有个证明技术上的代价：要求 NIZK 是模拟可抽取的，且抽取器是直线的（不 rewind），所以证明只能放在 AGM + ROM 里做。作为回报，它的 NIZK 比 BEAT-MEV 的小一个群元素：$2|G_1|+|F_p|$。

第六步：阈值化

把上面的非阈值方案变成真正的阈值方案（§2.6/§4.2）：每个 $p_i(x)$ 做 t-of-N Shamir 分享得到 $s_{ij}$；第 $j$ 方的密钥 $sk_j = (s_{ij})_i$（ℓ 个域元素）；份额 $sbk_j = \sum_i s_{ij}\cdot ct_i[1]$——还是单个群元素；Combine 用 Lagrange 系数加权求和即得 $sbk$。每区块通信量正是 O(N)：每个验证者发一个群元素。

鲁棒版（Construction 3）加了验证密钥 $vk_{ij} = [s_{ij}]_2$，Combine 时检查 $\sum_i e(ct_i[1], vk_{ij}) \stackrel{?}{=} e(sbk_j, [1]_2)$，失败就 blame 该方，满足 accurate blaming + consistency。阈值安全归约到非阈值版本，对抗的是静态敌手（敌手预先选定 t−1 个腐化方）。

第七步：更短密文的变体

论文 §2.7/§5 还给了一个短密文变体：去掉密文的第二个分量，密文只剩 $|G_1|+|G_T|$（两个群元素）；代价是解密密钥增加 $(\ell+1)$ 个 $G_2$ 元素：$[p_{-1}(x)+p_0(x)]_2$（直接算出方程 4）和掩码元素 $[w_j(x)]_2 = [q_j(x) + p_{-1}(x)/(j+1) + p_0(x)/j]_2$（配对后减去二次项即得方程 3）。此时 NIZK 退化为对离散对数的普通 Schnorr 证明（$|G_1|+|F_p|$）。安全基于新假设 q-QuadRankDef（在 GBGM 中证明成立）。

安全基础总结一下：主构造基于新的静态 q 型假设 q-StatRankDef（AGM+ROM 下证明 CCA 安全），论文把它归约到 JNR 的 q-RankDef（已在 GBGM 中成立）。

实验与数据

实验设计很实在：Rust + arkworks 实现两个构造（Construction 1 = BE，Construction 5 = BEshort），代码未做显著优化；曲线 BLS12-381；2024 款 MacBook Pro（M4 Pro，12 核，24GB，单线程模式）。测加密 / 预解密 / 解密随批量 ℓ 增长的墙钟时间。

论文 Table 2 的关键数字（每格为 BE / BEshort）：

几个解读点：

• 加密与 ℓ 无关（BEshort 少一次 $G_1$ 标量乘，略快），这符合直觉——加密是逐笔独立的。
• PreDec 就是一次 ℓ 规模的 $G_1$ MSM，512 批次 50ms 量级。
• BEshort 解密比 BE 快约 1.6 倍：少一次 $G_2$ 上的 FFT、全批少 ℓ 个配对，还共享了两个 Miller loop 的一次 final exponentiation。
• 解析对比（Table 1）：本工作 §4 的 CRS 是 $2|G_1|+\ell|G_2|$、sbk 为 $|G_1|$、密文 $2|G_1|+|G_T|$；§5 的 CRS 是 $|G_1|+(2\ell+1)|G_2|$、sbk 为 $|G_1|$、密文 $|G_1|+|G_T|$——即使对比有 epoch 的 batch IBE，这四项也是最小的。BEAT-MEV 的 CRS 是二次方的 $(\ell+1)|G_1|+\ell^2|G_2|$，被全方位碾压。

诚实注记：没有和前人方案做实测对比（只有解析式对比），实现是原型级、未优化。所以”快 1.6 倍”是对自家两个变体而言，别外推成”比 BEAT-MEV 快多少倍”。

相关工作对比

这篇论文的创新点可以归纳为四条。

第一，首次同时做到 epochless + index-independent + 具体高效，终结了”batch IBE 被 epoch 绑死、BEAT-MEV 被 index 绑死”的两难。最实在的收益是审查攻击成本回到了 $O(\ell)$ flooding——和没有加密内存池的区块链同级，攻击者再也占不到协议本身的便宜。

第二，技术路线的原创性。它把 Jutla-Nema-Roy 的部分分式阈值加密技巧扩展到了批量场景：“一个群元素编码整批”是全文最漂亮的想法，“把 index 当作当事人、公开它的公私钥对”的视角转换是第二漂亮。

第三，参数全面最优。CRS、密文、预解密密钥、NIZK 证明尺寸四项都是同类最小，且证明在 AGM+ROM 而非更强的理想模型假设下完成，没有为了好看的数据偷偷加假设。

第四，应用直接。加密内存池通信 O(Nℓ)→O(N)；时间锁加密存储（密封拍卖、链上 ML 模型竞赛、链上选举/治理）去掉 epoch 之后可用性大幅提升。论文也诚实记录了”后发先至”的竞争：初稿公开后出现了 BTX（ePrint 2026/754）和 Simple BTE（ePrint 2026/760）两个独立的同类工作，§5 的短密文变体正是受它们启发而来。

局限与开放问题

• 安全证明在 AGM + ROM 理想模型下；plain model 的批量加密仍是开放问题（Gong 等在 plain model 只做到了 selectively-secure 的 batch IBE）。
• 阈值安全只针对静态敌手；自适应敌手下的安全留作未来工作。
• 每方密钥是 ℓ 个域元素（O(ℓ) 存储），不是常数（Remark 2 提到的两轮压缩法未纳入主构造）。
• 密文仍含 NIZK 证明（§4 为 $2|G_1|+|F_p|$），解密是 $O(\ell \log \ell)$ 计算；超大批次（ℓ≫512）的实测数据论文未披露。
• 格基/后量子版本缺席：Boneh-Laufer-Tas 的 LWE 方案参数偏大，本工作的配对路线不抗量子——后量子批量阈值加密仍是空白。
• 实现是原型，未做工程优化，无生产部署评估。

一点思考

加密内存池是 MEV 缓解路线里最接近”根治”的工程方向，这篇论文把它的通信瓶颈从 O(Nℓ) 打到 O(N) 且不再绑 epoch，可用性是质变。但要清醒：证明还在 AGM+ROM 里，敌手还是静态的，真要落进以太坊客户端，还得过”更强的证明”和”生产级优化”两关。我的判断：对做加密内存池、时间锁加密的团队，这是今年必读的一篇；对纯理论读者，它是”部分分式”这个数学工具在密码学里最漂亮的工程化示范之一。

原文链接

• 论文：https://eprint.iacr.org/2026/674（Efficient Batch Threshold Encryption Using Partial Fraction Techniques，CRYPTO 2026）
• 实现：https://github.com/entrohpy/batch-enc-partial-fractions（Rust + arkworks）
• 同期竞争工作：BTX（ePrint 2026/754）、Simple BTE（ePrint 2026/760）