cover_image

如何从 FRI-IOPP 构造多项式承诺

Kurt Pan XPTY
2025年05月28日 08:03

原文：https://building-babylon.net/2025/02/03/building-a-polynomial-commitment-scheme-from-the-fri-iopp/

作者：Benjamin Wilson

译者：Kurt Pan

本文将介绍如何基于 FRI 交互式预言机邻近性证明 (FRI-IOPP) 构造多项式承诺方案 (PCS)。具体来说，我们将解释如何将求值证明归约到邻近性证明。假设读者已经理解 FRI-IOPP。本文所有内容均源于阅读《具有多对数通信复杂度的透明 PCS》(Vlasov & Panarin, 2019)，以及（坦白说）大量的思考和讨论。

  • https://eprint.iacr.org/2019/1020

我们假设 FRI 的通常设置。令 表示一个有限域，  表示单位群  的子群，其中 是 2 的幂。令  表示函数  的向量空间，视为具有通过  的某个固定枚举进行索引的条目的向量（我们将  的元素称为“码字”）。令  表示求值映射，即

将  上的相对汉明距离记为  ，令  表示次数界为  的 Reed－Solomon码。在整个次数界内固定为  。我们将关注两个独立的 Reed－Solomon 码，即和 （请注意，它们都使用相同的求值点  ）。  表示  的唯一解码半径，即  是使得对于任何  和  ，以及下式成立的最大值，

次数界为  的 FRI－PCS 中承诺的数据是码字 （更准确地说：  的预言）。现在假设证明者是诚实的。在最简单的情况下，对某些  有  。然而，至关重要的是，我们需要比这更弱的承诺  ：只要  在某些码字  的唯一解码半径内就足够了，即

任何这样的  都被视为对其对应  的有效承诺。为什么需要这种微妙之处？因为如果需要更严格的条件  ，那么将求值证明归约到对 FRI－IOPP 的调用（很快就会解释）将是不可能的。FRI－ IOPP 不够敏感，无法可靠地区分码字和附近的非码字（有关明确演示，请参见[[FRI 是鄰近性證明，而非低次測試]]）。

假设证明者已向验证者发送承诺  ，则求值证明的流程如下。验证者选择一个求值点  并将其发送给证明者，证明者则回应承诺的多项式的声称的求值值 （对于诚实证明者，为  ，其中  由（UDR）确定）。证明者希望建立

因为  当且仅当  能被  整除，并且次数在多项式乘法下是可加的，所以这两部分断言等价于以下统一断言：

因此，我们感兴趣的是承诺  与  的特定子集（即由形式为  的码字组成的子集）的接近程度。但请注意，我们不能立即应用 FRI－IOPP 来建立此断言，因为此子集本身不是 Reed－Solomon码（它甚至不是  的线性子空间）。好消息是，只需少量工作，就可以看出断言（Unified）等价于可以使用 FRI－IOPP 建立的断言（次数界为  ）。此断言涉及从  派生出的向量  ，我们将在下面对其进行定义。因此，FRI－PCS 求值证明将通过一个邻近性证明来建立！

首先，关于预言机的说明。重要的是，验证者不需要接收或读取所有  的承诺  。由于求值证明归约为对 FRI－IOPP 的调用，因此只需为验证者提供一种机制，使其能够查询任意索引  处  的条目  。在信息论的表达中，此机制被抽象为预言机。在实现中，预言机通常通过对以  为叶子节点（以某种约定的方式枚举）的树的 Merkle 承诺来实例化。证明者通过将 Merkle 根发送给验证者，将自身绑定到  ，而验证者通过向证明者询问从根节点到相应叶子节点的 Merkle 路径来查询条目  。

现在让我们将求值证明归约为 FRI－IOPP 的一个实例。给定每个  的双射  ，所有码字空间的双射  可以定义为

将这样的映射  称为“逐部分双射”；对于任何这样的映射，立即有

对于任何  和  ，定义一个逐部分双射  ，由

给出它的逆，由

给出，由此立即得出

结合（HDInv）和（DrcInverse），我们得到

并将其代入断言（Unified），我们得到等价的断言

，证明者和验证者可以使用 FRI－IOPP 来建立该断言！（FRIable）这只不过是一个证明  与  接近的语句。

作弊失败（以高概率）

现在考虑一下在将此归约到 FRI－IOPP 时证明者的两种可能的作弊策略，这将大有裨益。第一种策略是，第一个断言（TwoPart）不成立，即对于所有  都不在某个  的唯一解码半径内。换句话说，这只是说  ，即＂ 距离码  有  的距离＂。因此，根据（StepDown），对于任何  ，有

，因此断言（FRTable）为假，并且会被 FRI－IOPP 的可靠性界捕获。证明者唯一的另一种作弊策略是，对于某些  在  的唯一解码半径内，但声称的求值是假的，即  。然后，对于任意的  ，我们都有 （因为否则  处的求值将会匹配），从而 和  是不同的码字。因此，由（StepDown）可知，由于  最多只能位于一个码字（即  的 （唯一解码半径）内，因此

成立。

如何进行次数为  的 FRI－IOPP？

FRI－IOPP 的定义是次数界  为 2 的幂。但是，如果  是 2 的幂，那么如何执行第二个使用次数界  的 FRI－IOPP 呢？简而言之，只需将其替换为另一个使用次数界  的 FRI－IOPP 调用即可。具体如下：

  • 验证者将使用预言机  来模拟预言机  到  。
  • 证明者希望证明  在  的唯一解码半径（UDR）范围内。  的 UDR 大于  的 UDR  ，因此只需证明  即可。
  • 证明者和验证者使用 FRI－IOPP 来证明  。这表明存在某个  使得  。
  • 根据方程（StepDown），可知  。
  • 但我们在 UDR 范围内，所以  ，其中  是第一次 IOPP 调用的多项式。因此 。第一个 FRI－IOPP 表明 ，因此是  。因此（Unified）成立，我们完成了。


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