PCS简要介绍

Posted on Edited on

之前听师兄讲PCS（多项式承诺方案），听不懂一点，甚至有一次差点睡着（bushi

今天看Siniel，又遇到PCS了，故而通俗理解记录一下，也没时间看相关论文了浅学一下，够用即可~

图一

Motivation：证明者有一个多项式 ，验证者指定一个数 来验证，通过承诺确保原多项式不会改变

图二

这里，我们介绍 KZG。更具体的：

KZG 方案是基于双线性对（bilinear pairing）和加法同态加密（homomorphic encryption）的密码学技术。它允许一个发送方承诺（commit）一个多项式，并稍后提供证明（proof），以便验证者确认多项式在某个点的值是否正确。

前置知识：双线性映射

  • 设 是两个循环群，阶为素数
  • 设 ，满足 对所有 成立，其中 是群 和 的生成元

KGC的四个步骤：（对应图二）

  1. Setup（设置）： 生成公钥参数。
  2. Commit（承诺）： 证明者使用私有多项式生成并公开该多项式的承诺。
  3. Open（打开）： 验证者指定在某个点，而后要求证明者公开该多项式的值并提供一个证明。
  4. Verify（验证）： 验证者检查提交的值和证明是否有效。

具体流程

2.1 设定（Setup）

由可信第三方（或 MPC ）选取一个私有值 ，并计算： 作为公共参数；这些值是椭圆曲线群上的元素并公开发布。

2.2 承诺（Commit）

证明者需验证多项式

计算并公开承诺

2.3 证明（Open）

验证者想知道证明者的多项式在 处的值

证明者计算商多项式：；因为 可被 整除，所以 是一个比 低 1 阶的多项式。

计算承诺 ：；并将其作为证明 发送给验证者。

2.4 验证（Verify）

验证者通过以下等式检查证明是否有效：

即：

若等式成立，则说明证明者提供的 是正确的。

示例

①设公共参数为：

②证明者私有多项式：

计算承诺并将其公开：

③验证者指定一个点：

证明者计算:

证明者计算商多项式:

证明者计算证明：

④验证者执行验证：

如果等式成立，则证明 是正确的。

进一步的，关于验证阶段

验证者需要验证 是否成立 左式

右式

故只需 成立，则验证通过

此时 （此过程为逆向过程）

即最一开始的公开参数 时，则 成立，证明通过

后记：补充说明

和上面的算法相呼应，在论文的后半部分找到的具体算法，本质相同