密码学承诺之原理和应用 - Kate多项式承诺

合集 - 高级密码学(4)

1.密码学承诺之原理和应用 - sigma承诺09-262.密码学承诺原理与应用 - 概览09-233.密码学承诺之原理和应用 - pedersen承诺09-27

4.密码学承诺之原理和应用 - Kate多项式承诺10-11

收起

主页

微信公众号：密码应用技术实战
博客园首页：https://www.cnblogs.com/informatics/
GIT地址：https://github.com/warm3snow

简介

多项式承诺是一种实用性比较强的密码学承诺方案，允许一个方（承诺者）向另一个方（验证者）承诺一个多项式的值，而不泄露多项式的具体形式。在零知识证明、可验证密码共享等领域有广泛应用，常见的多项式承诺有Kate多项式承诺、FRI多项式承诺，IPA多项式承诺等。本文将重点介绍Kate多项式承诺的构造和应用。

在阅读下文之前，了解基础的密码学承诺原理和应用是非常有必要的，读者可以参考以下几篇文章：
《密码学承诺之原理和应用 - 概览》
《密码学承诺zhi原理和应用 - Sigma承诺》
《密码学承诺之原理和应用 - Pedersen承诺》

前言

多项式

在详细介绍Kate多项式承诺之前，我们先来简单介绍一下多项式的基本概念。多项式一般表示为：

$$f(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_d{x}^d=\sum _{i=0}^d{a}_i{x}^i$$

上述多项式中，$a_0,a_1,a_2,...,a_d$是多项式系数，$x$是多项式的变量，$d$是多项式的次数(或多项式的度)。多项式的次数是指多项式中最高次幂的指数，例如上述多项式的次数为$t$,因此上述$f(x)$我们也称作d次多项式。多项式系数$a_0,a_1,a_2,...,a_d$是多项式的重要组成部分，它们决定了多项式的形状和性质，也是需要保护的重要信息。

多项式的值是指将变量x代入多项式后的结果，例如$f(\beta )$表示将$x=\beta$代入多项式中，计算出的结果。

多项式的根是指多项式的值为0的点，即$f(x)=0$的点。

多项式有两个重要的性质：

• 一元n次多项式最多有n个根，假设根为${\beta }_1,{\beta }_2,...,{\beta }_d$，则多项式可以表示为：$f(x)=(x-{\beta }_1)(x-{\beta }_2)...(x-{\beta }_d)$
• 商多项式，多项式减去在某一个点的多项式值(如点：<$a,f(a)$>), 可以被另一个多项式整除，这个多项式称为商多项式。商多项式表示为$h(x)=\frac{f(x)-f(a)}{x-a}$

注：在零知识证明中，通常会将要证明的问题转化为多项式表达，并通过多项式与商多项式的等式关系来进行证明。

双线性映射

在多项式承诺验证中，会用到双线性映射的概念。双线性映射（Bilinear Map）是数学中一种重要的映射，尤其在密码学和数论中有广泛的应用。它是一种特殊的函数，具有以下性质：

定义

设$G$是一个乘法循环群, $g$是一个生成元, $G_T$是另一个群。一个映射$e:G\times G\to G_T$被称为双线性映射，如果满足以下条件：

• 双线性：对于任意的$a,b\in Z_p$和$g,h\in G$，有$e(g^a,h^b)=e(g,h{)}^{ab}$
• 非退化性：对于任意的$g\in G$，$e(g,g)\ne 1$
• 可计算性：对于任意的$g,h\in G$，$e(g,h)$可以在多项式时间内计算

重要性质：

• 可交换性：对于任意的$g,h\in G$，$e(g,h)=e(h,g)$
• 分配性：对于任意的$g,h1,h2\in G$，$e(g,h1\cdot h2)=e(g,h1)\cdot e(g,h2)$
• $e(g,g)\mathrm{为}{G}_T$的一个生成元

多项式承诺

多项式承诺主要流程如下：

• [00] Setup初始化阶段：承诺者和验证者共享公共参考串CRS
  • CRS：common reference string，是一个公开的字符串，一般通过可信的第三方生成，用于多项式承诺的构造
• [01] Commit承诺阶段：承诺者计算多项式承诺$C=Commit(CRS,f(\alpha ))$，并发送$C$给验证者。
  • C的计算依赖于多项式$f(x)$和公共参考串CRS
  • 注在多项式承诺中，多项式的度需要满足$d\le t$，其中$t$是公共参考串中的最高幂次
• [02] Open打开阶段：承诺者揭示多项式$f(x)$
  • f(x)是多项式的具体形式，承诺者直接揭示多项式$f(x)$，如多项式参数和系数
• [03] VerifyPoly验证阶段：验证者重新计算多项式承诺$C^{{}^{\prime }}=Commit(CRS,f(\alpha ))$
  • 验证者重新计算多项式承诺$C^{{}^{\prime }}$，并验证$C^{{}^{\prime }}$和$C$是否相等

以上方式的多项式承诺打开阶段是明文揭示，即承诺者直接揭示多项式$f(x)$，验证者重新计算多项式承诺$C^{{}^{\prime }}=Commit(CRS,f(x))$，并验证$C^{{}^{\prime }}$和$C$是否相等。
明文揭示的方式简单直接，但存在以下问题：

• 多项式阶数较高时，明文揭示的方式会导致通信量较大
• 明文揭示的方式无法保护多项式，必须公开

Kate多项式承诺

为了解决明文揭示多项式承诺存在的问题，Kate多项式承诺基于多项式点打开的方式，实现了多项式的承诺和验证。点打开方式指的是承诺者不直接揭示多项式$f(x)$，而是揭示多项式在某个点的值$f(\beta )$，并提供一个witness证明，验证者通过双线性映射验证多项式在β点的值是否正确。通过点打开的方式，Kate多项式承诺解决了明文揭示的问题，同时保护了多项式的隐私。

Kate多项式承诺的构造一般有两种方案，两种方案在安全性上有所不同：

• 计算隐藏的Kate多项式承诺：承诺的值在计算上是隐藏的，意味着对于任何多项式时间的攻击者，无法有效区分两个不同的承诺。换句话说，攻击者在计算上无法从承诺中推断出承诺的内容。
• 无条件隐藏的Kate多项式承诺：承诺的值在计算上是无条件隐藏的，意味着对于任何攻击者，无法从承诺中推断出承诺的内容。

定义上比较抽象，简单来说就是无条件隐藏通过引入随机性，使得承诺的值在计算上无法被推断出来，而计算隐藏仅使用离散对数困难性假设，使得承诺的值在计算上无法被推断出来。

计算隐藏的Kate多项式承诺

计算隐藏的Kate多项式承诺的构造如下:

[00] Setup初始化阶段

Kate多项式承诺需要初始化阶段，主要是生成和公开CRS，以及双线性映射$e:G\times G\to G_T$。在Kate多项式承诺中CRS如下：

$$CRS=(G,g^{\alpha },g^{{\alpha }^2},...,g^{{\alpha }^t})$$

其中，$G$代表乘法群，$g$是$G$的一个生成元，$\alpha$是一个随机数，$t$是最高幂次。注：在零知识证明中，$\alpha$是一个私密的值，不会公开，需要被安全销毁（通常被称为有毒废料）。

注：在Kate论文中，CRS被叫做PK，即公钥。

[01] Commit承诺阶段

承诺者计算多项式的承诺值$C=Commit(CRS,f(x))$，并发送$C$给验证者。多项式的承诺值计算方式如下：

$$C=g^{f(\alpha )}=g^{\sum _{i=0}^d{a}_i{\alpha }^i}=\prod _{i=0}^d{g}^{a_i{\alpha }^i}=\prod _{i=0}^d(g^{{\alpha }^i}{)}^{a_i}$$

• $a_i$是多项式的系数, 承诺者已知
• CRS是公共参考串，CRS中包含了$g^{{\alpha }^i}$的值，因此承诺者可以在不知道$\alpha$的情况下计算$C$

[02] CreateWitness点打开阶段

承诺者计算多项式在某个点的值$f(\beta )$，并提供一个witness证明$w$，其中$w$是多项式在β点的承诺，计算方式如下：

• 首先计算商多项式

$$\phi (x)=\frac{f(x)-f(\beta )}{x-\beta }=\sum _{i=0}^{d-1}{b}_i{x}^i$$

• 计算$f(x)$在β点的值

$$f(\beta )=\sum _{i=0}^d{a}_i{\beta }^i$$

• 计算商多项式在α点的承诺值

$$w=Commit(CRS,\phi (x))=g^{\phi (\alpha )}=g^{\sum _{i=0}^{d-1}{b}_i{\alpha }^i}=\prod _{i=0}^{d-1}{g}^{b_i{\alpha }^i}=\prod _{i=0}^{d-1}(g^{{\alpha }^i}{)}^{b_i}$$

承诺者将$(\beta ,f(\beta ),w)$发送给验证者。

[03] VerifyEval点验证阶段

验证者使用双线性映射验证多项式在β点的打开值是否正确，验证方式如下：

$$e(C,g)\stackrel{?}{=}e(w,g^{\alpha }/g^{\beta })\cdot e(g,g{)}^{f(\beta )}$$

正确性验证：

$$e(w,g^{\alpha }/g^{\beta })\cdot e(g,g{)}^{f(\beta )}=e(g^{\phi (\alpha )},g^{\alpha -\beta })\cdot e(g,g{)}^{f(\beta )}=e(g,g{)}^{\phi (\alpha )\cdot (\alpha -\beta )+f(\beta )}$$

根据商多项式的定义，有：$f(\alpha )-f(\beta )=\phi (\alpha )\cdot (\alpha -\beta )$，因此：

$$e(w,g^{\alpha }/g^{\beta })\cdot e(g,g{)}^{f(\beta )}=e(g,g{)}^{f(\alpha )-f(\beta )+f(\beta )}=e(g,g{)}^{f(\alpha )}=e(g^{f(\alpha )},g)=e(C,g)$$

因此，$e(C,g)=e(w,g^{\alpha }/g^{\beta })\cdot e(g,g{)}^{f(\beta )}$，验证通过。

无条件隐藏的Kate多项式承诺

无条件隐藏的Kate多项式承诺构造与计算隐藏的Kate多项式承诺流程类似，区别在于：

• 初始化阶段的CRS不同
• 承诺值的生成和验证方式不同（承诺值生成基于Pedersen承诺）

初始化阶段

CRS的构造如下：

$$CRS=(G,g^{\alpha },g^{{\alpha }^2},...,g^{{\alpha }^t},h,h^{\alpha },h^{{\alpha }^2},...,h^{{\alpha }^t})$$

其中，$h$是$G$的另一个生成元。

Commit承诺阶段

承诺者计算多项式的承诺值$C=Commit(CRS,f(x))$，计算方式如下：

$$C=g^{f(\alpha )}\cdot h^{\widehat{f(\alpha )}}f(\alpha )=\sum _{i=0}^d{a}_i{\alpha }^i\widehat{f(\alpha )}=\sum _{i=0}^d{b}_i{\alpha }^i=\prod _{i=0}^d(g^{{\alpha }^i}{)}^{a_i}\cdot \prod _{i=0}^d(h^{{\alpha }^i}{)}^{b_i}$$

CreateWitness点打开阶段

承诺者计算多项式在某个点的值$f(\beta )$，并提供一个witness证明$w$，计算方式如下：

• 计算商多项式

$$\phi (x)=\frac{f(x)-f(\beta )}{x-\beta }\widehat{\phi (x)}=\frac{\widehat{f(x)}-\widehat{f(\beta )}}{x-\beta }$$

• 计算点打开值

$$w=Commit(CRS,\phi (x))\cdot Commit(CRS,\widehat{\phi (x)})=g^{\phi (\alpha )}\cdot h^{\widehat{\phi (\alpha )}}$$

$g^{\phi (\alpha )}$和$h^{\widehat{\phi (\alpha )}}$计算方式基于CRS（方式与上文相同，略），承诺者将$(\beta ,f(\beta ),\widehat{f(\beta )},w)$发送给验证者。

VerifyEval点验证阶段

验证者使用双线性映射验证多项式在β点的打开值是否正确，验证方式如下：

$$e(C,g)\stackrel{?}{=}e(w,g^{\alpha }/g^{\beta })\cdot e(g^{f(\beta )}\cdot h^{\widehat{f(\beta )}},g)$$

正确性验证：

$h$是$G$中的一个群元素，因此不是一般性可设$h=g^{\lambda }$，其中$\lambda$是一个随机数。因此：

$$e(w,g^{\alpha }/g^{\beta })\cdot e(g^{f(\beta )}\cdot h^{\widehat{f(\beta )}},g)=e(g^{\phi (\alpha )}\cdot h^{\widehat{\phi (\alpha )}},g^{\alpha -\beta })\cdot e(g^{f(\beta )}\cdot h^{\widehat{f(\beta )}},g)=e(g^{\phi (\alpha )+\lambda \widehat{\phi (\alpha )}},g^{\alpha -\beta })\cdot e(g^{f(\beta )+\lambda \widehat{f(\beta )}},g)=e(g,g{)}^{\phi (\alpha )\cdot (\alpha -\beta )+\lambda \widehat{\phi (\alpha )}\cdot (\alpha -\beta )+f(\beta )+\lambda \widehat{f(\beta )}}=e(g,g{)}^{\phi (\alpha )\cdot (\alpha -\beta )+f(\beta )+\lambda \cdot (\widehat{\phi (\alpha )}\cdot (\alpha -\beta )+\widehat{f(\beta )})}$$

根据商多项式的定义，有：$f(\alpha )-f(\beta )=\phi (\alpha )\cdot (\alpha -\beta )$，$\widehat{f(\alpha )}-\widehat{f(\beta )}=\widehat{\phi (\alpha )}\cdot (\alpha -\beta )$，因此：

$$e(w,g^{\alpha }/g^{\beta })\cdot e(g^{f(\beta )}\cdot h^{\widehat{f(\beta )}},g)=e(g,g{)}^{\phi (\alpha )\cdot (\alpha -\beta )+f(\beta )+\lambda \cdot (\widehat{\phi (\alpha )}\cdot (\alpha -\beta )+\widehat{f(\beta )})}=e(g,g{)}^{f(\alpha )-f(\beta )+f(\beta )+\lambda \cdot (\widehat{f(\alpha )}-\widehat{f(\beta )}+\widehat{f(\beta )})}=e(g,g{)}^{f(\alpha )+\lambda \cdot \widehat{f(\alpha )}}=e(g^{f(\alpha )}\cdot g^{\lambda \cdot \widehat{f(\alpha )}},g)=e(g^{f(\alpha )}\cdot h^{\widehat{f(\alpha )}},g)=e(C,g)$$

因此，$e(C,g)=e(w,g^{\alpha }/g^{\beta })\cdot e(g^{f(\beta )}\cdot h^{\widehat{f(\beta )}},g)$，验证通过。

结语

Kate多项式承诺是一种实用性比较强的多项式承诺方案，通过点打开的方式，可以在保护多项式隐私的同时，有效减少通信量。Kate多项式承诺在零知识证明、可验证密码共享等领域有广泛应用。了解Kate多项式承诺的原理和构造，对于学习zk-snarks、zk-starks等零知识证明协议是非常有帮助的。通过本文的介绍，希望读者能够对Kate多项式承诺有一个初步的了解，并为进一步学习零知识证明协议打下基础。

参考文献

• 【1】Polynomial Commitment
• 【2】Non-interactive zero-knowledge proof
• 【3】Commitment_scheme