Parano1d 达到 NIST PQC Category 1

摘要

本文在量子随机预言机模型中，将 Parano1d 实际部署的证明参数与 NIST Category 1 的 AES-128 密钥穷举资源基准进行比较。证明从钱包与 HistoryStep 的精确关系出发，把所有已提交的根对象组合成一个接受无效状态的事件，再将类型化并行预言机访问换算为逻辑门数与电路深度，并计入见证提取与碰撞的有限规模修正项。在 NIST 的门数与深度资源边界上，理想模型中的完整成功概率上界为 0.053364140323608411。成功概率达到二分之一时，门数与深度乘积的主导下界为 173.273866314232 比特，比 2^170 基准高 3.273866314232 比特。

NIST Category 1 把攻击所需资源与 AES-128 密钥穷举进行比较。评估同时计算量子逻辑门数并限制电路深度，以判断攻击能否在给定的资源边界内达到目标成功概率。

对 Parano1d 而言，目标事件是验证器接受一个位于有效创世执行可达集合之外的终端状态。实际部署的证明配置达到 NIST Post-Quantum Cryptography Category 1 资源目标。在完整的 NIST 资源边界上，理想量子随机预言机模型中的上界为 $0.053364140323608411$ 。成功概率达到二分之一时，门数与深度乘积的主导下界为 $2^{173.273866314232}$ ，比 NIST 的 $2^{170}$ 基准高 $3.273866314232$ 比特。

安全性结论	实际部署结果
对手目标	使验证器接受无效终端状态
参考原语	AES-128 密钥穷举
NIST 门数与深度基准	$GD=2^{170}$
已计算的 NIST MAXDEPTH	$2^{40}$ 、 $2^{64}$ 与 $2^{96}$
成功概率为二分之一时的门数与深度乘积主导下界	$2^{173.273866314232}$
高于 NIST 基准的余量	3.273866314232 比特
NIST 资源边界上的理想模型完整成功概率上界	$0.053364140323608411$
固定 Poseidon2b 置换的充分条件	$\Delta_{\mathrm{P2b}}^{\mathrm{Cat1}} \lt 0.446635859676391589$
NIST Post-Quantum Cryptography 类别	Category 1

可靠性游戏

每个被 Parano1d 接受的区块都携带一份名为 HistoryStep 的递归证明。它证明区块关系、从已认证父状态到子状态的精确转换，以及前一份 HistoryStep 证明的验证结果。区块所使用的钱包授权证明与 sidecar 辅助关系也属于同一语句。

可靠性游戏的公开实例是终端 HistoryStep 状态。当实际部署验证器接受一个位于有效创世执行可达集合之外的状态时，能够跨查询保留状态的量子对手获胜。钱包授权、区块关系、父链接、状态转换、递归验证或所声明证明链中的任何失效，都属于同一个获胜事件。

构造终端证明及对手生成的全部前驱证明时产生的所有预言机交互，共享同一个资源预算。压缩预言机数据库一旦被测量，见证提取与证明图遍历就完全确定，后续过程不再发出预言机查询。该定理覆盖完整的已接受状态，包括每一次 FRI 打开和每一条递归依赖。

顺序查询与 Category 1 资源

实际部署参数支持两种互补的评估方式。顺序理想 QROM 定理给出按查询预算计的 $64.707407428576$ 比特边界。它把每次预言机调用计为一次查询，并覆盖显式上界保持在二分之一以下的预算。

Category 1 定理进一步加入回答每次查询所需的可逆电路。对实际部署 Poseidon2b 交互记录进行一次相干查询，需要执行包含大量二进制域乘法的电路。并行化可以降低电路深度，但逻辑门总数仍计入资源。计算同时使用两项资源，并直接导出门数与深度乘积下界。

实际部署参数

计算固定到 Parano1d 修订版 afdce21b6125ae0487c71a9093ab089cb8e88d5a。独立的实际部署参数快照记录全部安全输入，参数来源映射则把每个值关联到对应的 Rust 定义。

输入	实际部署值
钱包查询数	65
History 查询数	133
代数挑战值取值集合大小	$2^{255}$
摘要位宽	256 比特
History 码率	1/4
初始 History 码字	$2^{20}$ 或 $2^{21}$
联合 sidecar 关系组数	9
Poseidon2b	$t=4$ 、速率 2、 $x^7$ 、8 个全轮、58 个部分轮

两种初始码字长度对应两种实际部署 History 轨迹规模。B64 用于不超过 64 个用户交易页面的区块，B255 用于 65 至 255 个页面。二者证明同一个 HistoryStep 关系，使用相同的码率、查询数、挑战值分布与局部定理，仅执行轨迹长度不同。

代数挑战值位于 GF(2²⁵⁶) 中迹为 1 的仿射子集，该集合恰有 $2^{255}$ 个元素。256 比特摘要位宽是另一项独立输入。必须区分两者：代数例外集合使用分母 $2^{255}$ ，全局绑定性碰撞使用分母 $2^{256}$ 。

局部可靠性定理

分析首先把 Fiat–Shamir 生成的每个挑战值替换为对应的验证者随机币，并把已认证数组暴露为理想预言机。由此得到一个公开随机币 IOP，并在其上证明局部广义逐轮知识误差。局部定理省略最终的工作量证明 nonce 判定，从而为证明者提供更大的接受集合，因此挖矿难度不计入额外的可靠性余量。

钱包授权

钱包包含一个查询未命中被修改位置的逃逸项，以及一个汇总全部不利代数挑战值的项：

\kappa_{W,q}=\left(\frac{15}{64}\right)^{65}, \qquad \kappa_{W,f}=\frac{29\,163\,918\,888}{2^{255}}.

它们属于不同的验证者步骤。广义逐轮误差取最大的条件逃逸概率：

\kappa_W=\max\{\kappa_{W,q},\kappa_{W,f}\}.

HistoryStep

对整数 Johnson 重数参数 $m\ge3$ ，定义

h=m+\frac12, \qquad \gamma=\frac{m-1}{2m}, \qquad s_N=\frac{N-4}{2N}.

对于长度为 $N$ 、码率为四分之一的 Reed–Solomon 层，有限邻近性上界与严格初始列表界为

A_N(m)=\left\lfloor N\frac{2h^5+3h\gamma s_N^2}{3s_N^3}+\frac{h}{s_N} \right\rfloor,

L_N(m)=\left\lceil\frac{h}{s_N}\right\rceil-1, \qquad L_{\max}(m)=\max\{L_{2^{20}}(m),L_{2^{21}}(m)\}.

列表相关 Reed–Solomon 定理给出 $A_N(m)$ ，BaseFold 分析把它带入实际部署折叠序列。对于 133 个独立查询位置，剩余逃逸项为

E_q(m)=\left(\frac{m+1}{2m}\right)^{133}.

初始的 32 条交织行被打包成扩域上的一个 Reed–Solomon 码字，并共享同一个有限初始列表。每次非例外折叠都把后续候选恢复到同一列表中的相关前驱候选。后续代数恒等式再对完整列表取并集，因此候选切换始终处于该界之内。

最大的普通代数恒等式对每个候选最多有 127 个根。九组联合 sidecar 恒等式最多有 36 个根。合并查询逃逸、全部实际部署折叠层与候选切换，得到

\begin{aligned} \kappa_H(m)=\max\{&E_q(m), \max_N A_N(m)/2^{255},\\ &127L_{\max}(m)/2^{255}, 36L_{\max}(m)/2^{255}\}. \end{aligned}

邻近性最大值遍历 $N\in\{2^8,\ldots,2^{20}\}\cup\{2^9,\ldots,2^{21}\}$ ，覆盖两种实际部署轨迹规模的全部折叠层。

无需重绕的提取器对打包码字进行列表译码，恢复 32 条基域行，执行加性 NTT 的逆变换，并保留满足精确 History 关系的候选。沿验证流程作逆向归纳可知，无见证的接受交互记录必然落入 $\kappa_H(m)$ 中的四类事件之一。顺序分析和考虑资源成本的分析都使用这条局部知识提取定理。

顺序定理的精确最优值为 $m=861824$ 。Category 1 在考虑资源成本时的精确最优值为 $m=318983$ ，原因是一次 History 查询响应需要十二次顺序 Poseidon2b 置换。

从局部证明到一个无效状态事件

类型化、按语句分域的预言机命名空间把全部交互记录族和自适应语句吸收到一个事件中。测量唯一的压缩预言机数据库 $D$ 后，定义 $\mathsf{BadAll}(D)$ 为以下事件：存在某个已提交且被接受的钱包根或 History 根，使得确定性见证提取失败。

还需显式保留两个边界事件。所需子对象可能未表示在数据库中，或者碰撞、歧义编码或域混淆可能改变类型化语义图。因此

\mathsf{BadState} \subseteq \mathsf{BadAll}\cup\mathsf{MissRep}\cup\mathsf{BadTypedBind}.

在封闭的类型化理想编译器中，规范嵌套对象表示在同一个数据库内，因此 $\mathsf{MissRep}$ 不会发生。类型化交互记录与承诺的绑定性由下文的有限规模修正项和碰撞项覆盖。把理想接口替换为固定 Poseidon2b 时，只在最后加入一次实际部署偏差项。

数据库成为经典数据后，确定性遍历从已接受的终端状态开始，检查每个局部关系，沿唯一的较低高度 History 父节点继续，并加入所需的钱包与 sidecar 证明义务。每条递归边都会降低秩，所以遍历最终到达创世块。随后，有效的已提取见证按照逆拓扑顺序推出协议定义的精确状态转换。

统一处理所有根对象的构造把递归归入一个概率事件。链高度会改变确定性提取工作量，更大的证明图也要求对手付出更多资源，而所有已提交的根对象始终处于同一个坏事件和同一个总预算之内。

顺序 QROM 复核

令

\kappa_*=\max\{\kappa_W,\kappa_H(861824)\}.

将 Chiesa、Manohar 与 Spooner 的压缩预言机提升论证专门化，再结合 FRACTAL 中按语句分域的自适应组合，得到完整的顺序理想 QROM 上界

\varepsilon_{\mathrm{ideal}}(T)=\min\left\{1, 6T^2\left(\kappa_*+\frac{2T+1}{2^{255}}\right) +\frac{6T^3}{2^{256}} \right\}.

精确整数搜索找到该表达式小于二分之一时的最后一个 $T$ ：

顺序边界	精确值
最大已证明查询预算	30,121,082,641,781,720,121
首个超出证明范围的查询预算	30,121,082,641,781,720,122
用于表述的二进制对数	64.707407428576 比特
$T=2^{64}$ 时的上界	$0.187528937938435742$

首个边界预算精确标出这条上界达到二分之一的位置。Category 1 计算将单位查询计数替换为实现相干响应所必需的逻辑资源。

NIST Category 1 资源基准

NIST 第 4.A.5 节把 Category 1 定义为：任何攻击都需要与 AES-128 密钥搜索相当或更多的资源。考虑电路深度的评估为 AES-128 给出

G=\frac{2^{170}}{D}, \qquad GD=2^{170},

其中 $G$ 是逻辑门数， $D$ 是最大电路深度。NIST 列出 $D=2^{40}$ 、 $2^{64}$ 与 $2^{96}$ 。证书逐一计算全部三个取值。

类型化并行 QROM 资源

对每一种类型化坏响应事件 $j$ ，令 $\kappa_j$ 表示局部密度， $g_j$ 表示一次相干响应所需的逻辑门数， $d_j$ 表示其逻辑深度。Chung、Fehr、Huang 与 Liao 的并行压缩预言机转移界专门化到全根事件后，给出

\Pr[\mathsf{BadState}]_{\mathrm{main}} \le 10GD\max_j\frac{\kappa_j}{g_jd_j}.

该资源步骤也覆盖同一并行轮中存在多种响应类型的情况。若 $k_{s,j}$ 是第 $s$ 轮中的 $j$ 型查询数，并令 $\delta_s=\max\{d_j:k_{s,j}\gt0\}$ ，则

\sum_{s,j}g_jk_{s,j}\le G, \qquad \sum_s\delta_s\le D.

对压缩预言机转移振幅应用加权柯西–施瓦茨不等式（Cauchy–Schwarz），得到

\begin{aligned} \Pr[\mathsf{BadState}]_{\mathrm{main}} &\le10\left(\sum_s\delta_s\right) \left(\sum_s\frac{\sum_j\kappa_jk_{s,j}}{\delta_s}\right)\\ &\le10D\sum_{s,j}\frac{\kappa_jk_{s,j}}{d_j}\\ &\le10GD\max_j\frac{\kappa_j}{g_jd_j}. \end{aligned}

自适应选择的语句与递归根共享同一个 $\mathsf{BadAll}$ 事件及其资源计数。

Poseidon2b 相干响应成本

资源计算采用一个可逆 GF(2¹²⁸) Karatsuba 乘法器电路，其逻辑成本为：

资源	数量
CNOT	29,340
单量子比特 Clifford 门	4,374
T	15,309
逻辑门总数	49,023
逻辑深度	43

实际部署的 Poseidon2b 置换包含

4\cdot8+58=90

个 S-box。 $x^7$ S-box 使用两次顺序域乘法，相干计算与反计算合计使用四次。全轮中的 S-box 并行执行。因此，一次相干置换响应具有

g_0=90\cdot4\cdot49\,023=17\,648\,280,

d_0=(8+58)\cdot4\cdot43=11\,352,

g_0d_0=200\,343\,274\,560.

一次钱包查询通过速率为 2 的双工结构输出七个 128 比特元素，需要四次顺序置换。一次 History 查询需要十二次置换，只含一个域元素的响应需要一次。

Category 1 结论包含一项明确前提：对手获得相应的实际部署相干响应时，至少支付上述逻辑门数与深度成本。该电路省略了额外的路由、线性运算和控制门开销，因此对这项构造而言是保守的。定理把最小成本明确列为前提，而适用于所有可逆电路的普遍下界需要独立结果。

Category 1 计算

资源定理同时计算钱包查询事件与域上挑战值事件，以及 History 查询、邻近性、候选切换和联合 sidecar 事件。在考虑资源成本时的精确最优值 $m=318983$ 处，最大的 $\kappa_j/(g_jd_j)$ 来自钱包查询事件。

令主项成功概率等于二分之一，得到

GD_{1/2}^{\mathrm{main}} =\frac{1}{20\max_j(\kappa_j/(g_jd_j))}.

其精确有理数值的二进制对数为

\log_2 GD_{1/2}^{\mathrm{main}} =173.273866314232\ldots

在 NIST 资源边界 $GD=2^{170}$ 上，主项不超过 $0.051693750450980417$ 。还需加入两项有限规模修正。

对于 NIST 的每个深度点，计算器由下式导出最便宜相干响应的最大数量与顺序轮数：

G=2^{170}/D, \qquad N=\left\lfloor\frac{G}{g_0}\right\rfloor, \qquad R=\left\lfloor\frac{D}{d_0}\right\rfloor.

类型化有限规模修正项覆盖见证提取不稳定性与交互记录不稳定性。全局碰撞项使用完整的并行压缩预言机碰撞振幅，并对整个正表达式平方，交叉项也包含在内。最坏的有限规模上界出现在 $D=2^{40}$ 。

Category 1 项	上界
类型化主项	$0.051693750450980417$
见证提取与交互记录的有限规模修正项	$0.000199022715317804$
全局 256 比特碰撞项	$0.001471367157310191$
理想模型完整上界	$0.053364140323608411$

\boxed{ \varepsilon_{\mathrm{ideal}}^{\mathrm{Cat1}} \le0.053364140323608411\lt\frac12.}

固定 Poseidon2b 边界

理想定理把类型化交互记录接口建模为允许量子查询的随机预言机。实际部署系统使用固定公开的 Poseidon2b 置换，并采用精确帧编码与域分离。令 $\Delta_{\mathrm{P2b}}^{\mathrm{Cat1}}$ 表示用实际部署构造替代理想接口后，编译器整体坏事件概率增加量的上界。则

\Pr[\mathsf{BadState}]_{\mathrm{production}} \le \varepsilon_{\mathrm{ideal}}^{\mathrm{Cat1}} +\Delta_{\mathrm{P2b}}^{\mathrm{Cat1}}.

距离成功概率二分之一的剩余余量给出以下充分的实际部署条件：

\boxed{ \Delta_{\mathrm{P2b}}^{\mathrm{Cat1}} \lt0.446635859676391589.}

这是针对公开固定 Poseidon2b 置换、精确交互记录帧编码与域分离的事件级编译器偏差。Poseidon2b 论文给出固定置换参数与相应密码分析；上式则陈述端到端定理采用的附加量子实例化条件。

可执行、绑定源码的证书

完整推导与计算器发布在 Parano1d 可靠性分析仓库中。仓库内嵌实际部署参数快照并固定源码修订版。若钱包轨迹规模及其参数登记表、History 与 BaseFold 查询数、挑战值取值集合、两种 History 码率、摘要位宽或固定 Poseidon2b 配置不一致，参数加载会直接拒绝执行。

所有用于结论判定的概率与优化阈值均使用任意精度整数和既约有理数计算。上界向上取整，固定置换的充分余量向下取整。浮点对数只用于展示，不参与结果判定。

克隆证书仓库并复现实际部署报告：

git clone https://github.com/ignotusnemo/parano1d-soundness.git
cd parano1d-soundness
cargo run --release --locked

输出全部既约有理数与优化阈值：

cargo run --release --locked -- --exact

运行参数快照、精确算术与规范阈值回归测试：

cargo test --release --locked

证明文档、源码符号映射、精确计算器与测试共同组成可复核的证据链，Category 1 结论由其中最后一次资源比较得到。

主要来源

NIST Post-Quantum Cryptography 安全评估标准第 4.A.5 节，Category 1 的 AES-128 基准与 MAXDEPTH 取值。
Alessandro Chiesa、Peter Manohar 与 Nicholas Spooner，Succinct Arguments in the Quantum Random Oracle Model，顺序压缩预言机提升论证。
Kai-Min Chung、Serge Fehr、Yu-Hsuan Huang 与 Tai-Ning Liao，On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work，并行转移界与碰撞界。
Alessandro Chiesa、Dev Ojha 与 Nicholas Spooner，FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography，按语句分域的自适应组合。
Eli Ben-Sasson、Dan Carmon、Ulrich Haböck、Swastik Kopparty 与 Shubhangi Saraf，On Proximity Gaps for Reed–Solomon Codes，列表相关邻近性上界。
Ulrich Haböck，BaseFold in the List Decoding Regime，实际部署折叠序列的专门化。
Lorenzo Grassi、Dmitry Khovratovich、Katharina Koschatko、Christian Rechberger、Markus Schofnegger、Verena Schröppel 与 Zhuo Wu，Poseidon(2)b: Binary Field Versions of Poseidon/Poseidon2。
Kyungbae Jang、Wonwoong Kim、Sejin Lim、Yeajun Kang、Yujin Yang、Hwajeong Seo 与 Ilsun You，Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion，可逆二进制域乘法器电路。