cover_image

【论文速递】论基于功能承诺简洁论证的Fiat-Shamir安全性

Kurt Pan XPTY
2025年05月25日 09:47

https://eprint.iacr.org/2025/902.pdf

摘要

本文针对一种构建 SNARG 的通用范式——先在标准模型中通过功能交互式预言证明（FIOP）与功能承诺（FC）框架构造简洁交互式论证，再在随机预言模型（ROM）中通过 Fiat–Shamir 变换获得非交互式 SNARG——填补了此前分析中的关键安全空缺。作者提出并形式化了 状态恢复安全性（state‐restoration security）与 功能绑定（function binding）两大核心概念，证明只要所用 FIOP 与 FC 满足对应的状态恢复安全性与功能绑定变体，即可确保 Fiat–Shamir 变换后的非交互式论证在 ROM 中的可信性。

基于该主定理，文章进一步验证了多种 FC 架构（包括 KZG、多项式承诺等）满足功能绑定性质，并从而在 ROM 中首次给出了 Plonk SNARG 的 Fiat–Shamir 安全性证明（依赖可验证 RSA 分解困难性假设 ARSDH）。

背景

SNARG 与 Fiat–Shamir 变换

  • SNARG（Succinct Non-Interactive Argument of Knowledge）是一种非交互式、论证长度远小于见证大小的零知识论证框架，广泛应用于区块链与可信计算。
  • Fiat–Shamir 变换 是将公开硬币交互式证明"去交互化"的经典技术，通过哈希（在 ROM 中视为随机 预言）模拟 Verifier 的质询，从而生成非交互式论证。
  • 随机预言模型 (ROM) 假设哈希函数为真正的随机函数，简化安全分析但需谨慎使用。

功能承诺与交互式预言证明

  • 功能承诺（Functional Commitment）：委托者可以承诺一个功能，并在后续高效揭示该功能在任意输入处的输出且保持隐私，通用建构包括向量承诺与多项式承诺。
  • 交互式预言证明 (Interactive Oracle Proof, IOP)：结合交互式证明（IP）与可验证随机访问证明（PCP），Verifier 对 Prover 消息具备预言查询能力，兼具 IP 与 PCP 优势。
  • 多项式承诺（Polynomial Commitment）：其中典型方案如 KZG，将待承诺向量视作多项式，通过双线性对实现高效开证明与批量验证。

Funky 协议概述

Funky 协议定义如下：

  1. 使用 FIOP 生成对实例 、见证  的 功能性交互式论证，允许 Verifier 对 Prover 的预言响应进行少量随机查询；
  2. 对 Prover 在不同轮次的输出应用 FC 承诺，每次承诺后进行有限次公币交互；
  3. 最后在 ROM 中对所有交互轮次应用 Fiat–Shamir 变换，输出非交互式论证。

主要贡献

1. 状态恢复安全性与功能绑定定义

  • 状态恢复安全性（State‐Restoration Soundness）：在模拟 Fiat–Shamir 后，若敌手能在限制次数内生成接收器接受的论证，则可通过重置 Verifier 随机状态并重复交互抽取有效见证。此性质强于传统公开硬币可靠性。
  • 功能绑定（Function Binding）：FC 的自然安全性变体——当同一承诺针对不同输入可被开证明至不同输出时，需保持所有查询结果一致，否则可解承诺提取冲突见证。此性质推广了 VC 的位置绑定 (position binding)。

2. 通用安全性定理

定理 1（非正式）：令 Funky[FIOP, FC] 为基于 FIOP（轮次 , 论证长 , 查询数 ）及 FC 的 Funky 协议。若 FIOP 满足状态恢复安全性误差 ，FC 满足功能绑定误差 ，则在 ROM 中，对任何  轮交互、时间绑定  的 Adversary，其 Fiat–Shamir 后的论证接受概率上界为

3. 示例：KZG 与 Plonk 安全性

  • 文章验证了基于双线性对的 KZG 多项式承诺满足所需功能绑定性质，并给出相应证明。
  • 结合 ARSDH 假设，首次在 ROM 中呈现了 Plonk SNARG 的 Fiat–Shamir 安全性证明，填补了实践中 Plonk ROM 安全性空白。

技术细节

FIOP 与 FC 的组合

在 Funky 协议中，FIOP 定义了一组在交互式论证中对 Prover 消息进行预言查询的函数族

其中每个查询  接受 Prover 在第  轮发送的消息  并返回答案  。

FIOP 本身由  构成，具有  轮交互，每轮交互后 Verifier 从相应查询类  中随机选取若干  并获得响应。

功能承诺 (FC) 在此基础上提供对函数  及其求值结果  的承诺能力。令

其中  为承诺串， 为辅助输出。

关键在于，FC 是三同态（triply homomorphic）的：若

则必有

此性质（Definition 8.5）使得在交互式论证中，来自多个 预言查询的承诺与证明可以线性组合并批量验证。

在 Funky 协议的每轮中，Prover 对于所选查询  先生成 FIOP 消息 ，再计算 ，最后调用

并将  与  一并发送给 Verifier，从而实现 FIOP 与 FC 的无缝集成。

批量与线性化优化

  • 批量消息传递（Batching）
    定义 BatchMsg[FC, s]（Construction 8.6）：对  个独立函数  同时承诺，得到向量承诺  和原函数数组  。
    在开证明阶段，Verifier 发送标量挑战 ，Prover 计算
    并一次性验证：

由此 BatchMsg[FC, s] 对查询类  满足批量状态恢复函数绑定（Lemma 8.2）：

  • 线性化技巧（Linearization）
    对于结构化多项式查询族 ，引入参数 ，构造 （见 Lemma 8.3），将  个子查询承诺  和响应  线性化为单一承诺与响应：
    验证时同样仅需一次  调用，且满足线性化状态恢复函数绑定：

性能与效率

在 Funky 协议中，交互式阶段包含  轮交互，每轮 Prover 发送  位的 FIOP 消息和一个 FC 承诺 。
因此，交互式协议的总通信量为  位，其中  取决于所用承诺方案（如 KZG 中为单个群元） 。
应用 Fiat–Shamir 变换后，非交互式 SNARG 的证明大小为

位，其中附加的  部分源于 ROM 中对每轮质询的随机预言响应 。

Verifier 验证过程中，需要进行  次 FIOP 验证和  次  调用 。

因此，Verifier 总时间复杂度为

当  为常数时，上述复杂度仍为常数阶，保持了 SNARG 的“简洁性” 。

结论与未来工作

本文建立了 Funky 协议在 ROM 中的 Fiat–Shamir 安全性，填补了此前构造的关键安全空缺 。

证明了状态恢复 soundness 错误  与 FIOP 及 FC 安全误差之间的精确关系，为后续框架设计提供了理论指导 。

实例分析表明，常用 FC 架构（例如 KZG）和 FIOP 架构（例如 Plonk IOP）可直接套用本框架，并获得 ROM 下的 Fiat–Shamir 安全证明 。

未来可探索将 Funky 协议与递归证明结合，实现多层 SNARG 的高效递归压缩 。

另外，可研究功能绑定在其他承诺方案（如 Bulletproofs 类承诺）中的应用，以进一步优化证明大小和验证开销 。


Kurt Pan: 即日起提供有偿「密码学论文代码实现和 benchmarking 服务」，语言侧重Rust / Python / C++，密码学侧重零知识证明系统和格密码方案。欢迎有需要的老师同学以及对密码学感兴趣的朋友联系我，邮箱kurtpan666 at pm dot me 或微信 cryptokurt(此號已因加過多好友被封，且無法解禁，抱歉），也可关注公众号后留言。