前言

看Sonic的时候看到的Kate多项式承诺，之前在看zk-STARK的时候也有看到过这个玩意，打算深入学一下

Abstract

本文引入并正式定义了多项式承诺方案，并给出了两个有效的构造

多项式提交方案允许提交者提交具有短字符串的多项式，该短字符串可由验证者用于确认提交多项式的声明评估，虽然文献中的同态承诺方案可以用来实现这一目标，但其承诺的大小在承诺多项式的次数上是线性的

另一方面，方案中的多项式承诺具有恒定大小（单个元素），承诺揭示的开销也是恒定的，即便是打开多个评估也只需要恒定的开销，因此本文提出的方案可以有效降低密码协议通信成本

1 Introduction

承诺方案是许多密码协议的基本组成部分，承诺方案允许提交者发布一个称为承诺的值，该值将她绑定到消息（绑定），而不显示（隐藏），稍后，她可能会打开承诺并向验证者显示承诺的消息，验证者可以检查消息是否与承诺一致

先简单看一下承诺者承诺消息的三种普遍的方式

  1. 令$g,h$为阶为$p$的群$\mathbb G$的两个随机生成元，承诺方对消息$m\in_R\Z_p$进行承诺$\mathcal C_{<g>}(m)=g^m$，该方案在群$\mathbb G$的DLOG假设下为无条件绑定和计算隐藏的
  2. Pedersen承诺：承诺值为$\mathcal C_{<g,h>}(m,r)=g^mh^r$，其中需要随机性$r\in_R\Z_p$，Pedersen承诺在DLOG假设下是无条件隐藏和计算绑定的
  3. 承诺方可能会公开$H(m)$或$H(m||r)$，其中$H$为单向函数（实际实现时会采用抗碰撞函数），该承诺方案具体可以看Damgard的paper$[2]$

秘密共享中最常用的就是多项式，此时考虑对多项式$\phi(x)\in_R\Z_p[x]$的承诺，假设多项式的度为$t$，系数分别为$\phi_0,...,\phi_t$，一个简单的承诺方案是对串$(\phi_0|\phi_1|...|\phi_t)$进行承诺，根据不同的承诺方案，此类方法可能具有和多项式一样大小的承诺值，但是对于承诺的揭示，承诺者必须揭示整个多项式，这在很多密码应用中并不现实，尤其是秘密共享方案中（秘密共享要求不同的参与方在该多项式不同的点上进行评估，但不揭示整个多项式）

对于这个问题，一个解决方案是对系数进行承诺，比如$C=(g^{\phi_0},...,g^{\phi_t})$，此时多项式在某个点$i$揭示承诺$\phi(i)$时可以根据承诺值验证承诺的正确性，但是这么做仍然具有很大的承诺值（需要$t+1$个群元素）

2 Preliminaries

  • $PPT$：概率多项式时间，本文所有敌手均为PPT敌手
  • $k$：安全参数，不额外声明则默认为$k$
  • $static$：静态的表示在实例启动前选择节点
  • $e:\mathbb G\times \mathbb G\rarr \mathbb G_T$：I型双线性配对，其中群的阶$p\geq 2^{2k}$（选择I型群的目的是便于表示，II型和III型群同样适用）

此外本文采用DLOG假设和t-SDH假设$[3]$来证明安全性，两个额外的安全性证明利用了t-DHI假设$[5]$和t-SDH的双线性版本t-BSDH$[4]$

  • Definition 1（Discrete Logarithm Asumption）：给定群$\mathbb G^*$的生成元$g$（$\mathbb G^*$可以是$\mathbb G$或$\mathbb G_T$）和随机元素$a\in_R\Z_p$，任意敌手$\mathcal A_{DL}$攻破该问题的概率$Pr[\mathcal A_{DL}(g,g^a)=a]=\epsilon (k)$

一个用途很广泛的DLOG假设，此外还有一个更强的假设，称为t-DHI假设，简单来说就是给定元组$(g,g^\alpha,...,g^{\alpha^{t}})\in\mathbb G^{t+1}$，要求输出$g^{1/\alpha}$或$g^{\alpha^{t+1}}$，本文采用了普遍化的t-DHI假设，其中敌手$\mathcal A$需要输出$<\phi(x),g^{\phi(\alpha)}>\in \Z_p[x]\times \mathbb G$，满足$2^k>deg(\phi)>t$，本文将该普遍化的假设称为t-多项式DH假设（t-polyDH），具体如下

  • Definition 2（t-polynomial Diffie-Hellman Assumption）：令$\alpha\in_R\Z^*_p$，给定元组$(g,g^\alpha,...,g^{\alpha^{t}})\in\mathbb G^{t+1}$，任意敌手$\mathcal A_{t-polyDH}$在满足条件$2^k>deg(\phi)>t$下的任意多项式$\phi(x)\in\Z_p[x]$，其攻破该问题的概率为$Pr[\mathcal A_{t-polyDH}(g,g^\alpha,...,g^{\alpha^{t}})=<\phi(x),g^{\phi(\alpha)}>]=\epsilon(k)$

还有更强的假设，Boneh和Boyen定义的t-SDH假设比t-DHI更强，具体如下

  • Definition 3（t-Strong Diffie-Hellman Assumption）：令$\alpha\in_R\Z^*_p$，给定元组$(g,g^\alpha,...,g^{\alpha^{t}})\in\mathbb G^{t+1}$，任意敌手$\mathcal A_{t-SDH}$，其攻破该问题的概率$Pr[\mathcal A_{t-SDH}(g,g^\alpha,...,g^{\alpha^{t}})=<c,g^{\frac{1}{\alpha+c}}>]=\epsilon (k)$，其中$c\in\Z_p\backslash\{-\alpha\}$

本文的承诺方案的安全性主要依赖于t-SDH假设和其双线性版本t-BSDH

  • Definition 4（t-Bilinear Strong Diffie-Hellman Assumption）：令$\alpha\in_R\Z^*_p$，给定元组$(g,g^\alpha,...,g^{\alpha^{t}})\in\mathbb G^{t+1}$，任意敌手$\mathcal A_{t-BSDH}$，其攻破该问题的概率$Pr[\mathcal A_{t-BSDH}(g,g^\alpha,...,g^{\alpha^{t}})=<c,e(g,g)^{\frac{1}{\alpha+c}}>]=\epsilon (k)$，其中$c\in\Z_p\backslash\{-\alpha\}$

3 Polynomial Commitments

本节介绍多项式承诺的定义，并给出两种构造方案，第一种方案满足计算隐藏性，第二种方案满足无条件隐藏性

3.1 Definition

多项式承诺方案由六种算法组成：$(Setup,Commit,Open,VerifyPoly,CreateWitness,VerifyEval)$

  • $Setup(1^k,t)$：对于需要承诺的度小于$t$的多项式，算法生成适当的代数结构$\mathcal G$和对应的承诺公私钥对$(PK,SK)$，该算法由可信方或分布式生成
  • $Commit(PK,\phi(x))$：输出关于多项式$\phi(x)$的承诺值$\mathcal C$和关于承诺揭示的辅助信息$d$
  • $Open(PK,\mathcal C,\phi(x),d)$：输出用于承诺的多项式$\phi(x)$
  • $VerifyPoly(PK,\mathcal C,\phi(x),d)$：验证在辅助信息$d$下，承诺值$\mathcal C$确实是关于多项式$\phi(x)$的承诺
  • $CreateWitness(PK,\phi(x),i,d)$：输出$(i,\phi(i),w_i)$，其中$w_i$为$\phi(x)$在点$i$的值的witness
  • $VerifyEval(PK,\mathcal C,i,\phi(i),w_i)$：验证在承诺值$\mathcal C$下，$\phi(i)$确实是多项式$\phi(x)$在点$i$的值

这里注意一个点，对于长度为$t+1$的消息序列$(m_1,...m_{t+1})$，可以将其关联至一个唯一的值（索引）$(k_1,...,k_{t+1})\in\Z_p$，然后通过多项式插值法找到对应的多项式，既满足$deg(\phi)\leq t$，又有$\phi(k_i)=m_i$
对于方案的安全性，要求恶意的承诺者不能将$\mathcal C$揭示为两个可通过验证的$\phi(i)\neq\phi(j)$，进一步的，在超过$deg(\phi)$个值被揭示之前，多项式应该保持隐藏

多项式承诺具体的安全性和正确性定义如下

  • Definition 5：若算法六元组满足下列性质，则其为安全的多项式承诺

    • 正确性（Correctness）：由$Open$算法揭示的承诺值一定会通过$VerifyPoly$算法的验证，同时由$CreateWitness$算法生成witness一定会通过$VerifyEval$算法的验证
    • 多项式绑定性（Polynomial Binding）：对于任意敌手$\mathcal A$，有

$$ Pr\Big[ PK\larr Setup(1^k),(\mathcal C,<\phi(x),\phi'(x)>)\larr \mathcal A(PK):VerifyPoly(PK,\mathcal C,\phi(x))=1\wedge VerifyPoly(PK,\mathcal C,\phi'(x))=1 \wedge \phi(x)\neq\phi'(x)\Big]=\epsilon(k) $$

  • 评估绑定性（Evaluation Binding）：对于任意敌手$\mathcal A$，有

$$ Pr\Big[PK \larr Setup(1^k) , (\mathcal C,<i,\phi(i),w_i>,<i,\phi(i)',w'_i>) \larr \mathcal A(PK):VerifyEval(PK,\mathcal C,i,\phi(i),w_i)=1\wedge VerifyEval(PK,\mathcal C,i,\phi(i)',w'_i)=1 \wedge\phi(i)\neq \phi(i)' \Big]=\epsilon(k) $$

  • 隐藏性（Hiding）：对于任意多项式$\phi(x)\in_R\Z_p[x]$，给定$(PK,\mathcal C),\{<i_j.\phi(i_j),w_{\phi_{i_j}}>:j\in[1,deg(\phi)]\}$，且对于所有的$j$，均满足$VerifyEval(PK,\mathcal C,i_j,\phi(i_j),w_{\phi_{i_j}})=1$，则没有任意敌手可以以不可忽略的概率对未查询的$\hat i$确定对应的$\phi(\hat i)$，同时也没有任何计算有界的敌手$\mathcal {\hat A}$可以对未查询的$\hat i$获得对应的$\phi(\hat i)$的任何信息

正确性很好理解，就是正确执行算法一定能够得到通过验证的承诺值

多项式绑定性说的是，敌手不能将同一个承诺值揭示为两个不同的多项式，且这两个揭示值都可以通过验证

评估绑定性说的是，敌手不能讲承诺值揭示为两个不同的评估值，且这两个揭示值都可以通过验证

隐藏性有两段，前半句话是计算隐藏性，后半句话是无条件隐藏性

3.2 Construction：$PolyCommit_{DL}$

构建多项式承诺方案用到了之前提到的特殊的代数性质，对于任意多项式$\phi(x)\in_R\Z_p[x]$，对于$i\in\Z_p$，都满足$(x-i)$可以整除$\phi(x)-\phi(i)$，接下来看一下如何基于DLOG假设构建多项式承诺

  • $Setup$：算法生成对应的双线性群$\mathcal G=(e,\mathbb G,\mathbb G_T)$，然后随机选择生成元$g\in_R\mathbb G$，随机选择私钥$SK=\alpha\in_R\Z^*_p$，然后根据私钥计算公钥$PK=(\mathcal G,g,g^\alpha,...,g^{\alpha^t})$
  • $Commit$：对于多项式$\phi(x)=\sum^{deg(\phi)}_{i=0} \phi_ix^i$，输出多项式承诺值

$$ \mathcal C=g^{\phi(\alpha)}=\prod^{deg(\phi)}_{i=0}(g^{\alpha^i})^{\phi_i}\in \mathbb G $$

  • $Open$：揭示多项式$\phi(x)$
  • $VerifyPoly$：验证是否有$\mathcal C==g^{\phi(\alpha)}$，验证通过输出1，否则输出0
  • $CreateWitness$：计算

$$ \psi_i(x)=\frac{\phi(x)-\phi(i)}{x-i} $$

输出$(i,\phi(i),w_i)$，其中$w_i=g^{\psi_i(\alpha)}$，计算方法和$Commit$算法类似

  • $VerifyEval$：验证

$$ e(\mathcal C,g)==e(w_i,g^\alpha/g^i)e(g,g)^{\phi(i)} $$

验证通过输出1，否则输出0

这里看一下$VerifyEval$的验证等式

$$ \begin{aligned}e(w_i,g^\alpha/g^i)e(g,g)^{\phi(i)}&=e(g^{\psi_i(\alpha)},g^{\alpha-i})\cdot e(g,g)^{\phi(i)}\\ &=e(g,g)^{\psi_i(\alpha)(\alpha-i)+\phi(i)}\\ &=e(g,g)^{\phi(\alpha)}\\ &=e(\mathcal C,g) \end{aligned} $$

这里有个定理

  • Theorem 1：若在$\mathcal G$上有DLOG假设和t-SDH假设成立，则$PolyCommit_{DL}$为满足Def 5安全性的多项式承诺方案

具体的证明可以看论文的完整版本$[6]$

3.4 Features

讨论一下方案的一些特殊性质

Homomorphism

3.3节种介绍的多项式承诺方案满足加法同态，具体可以看论文的完整版本，基于Pedersen的构造方式$PolyyCommit_{Ped}$也满足加法同态性（因为Pedersen承诺本身就具有加法同态）

Unconditional Hiding

$PolyCommit_{DL}$方案在$t'<deg(\phi)$个评估点的承诺值揭示之前都具备无条件隐藏性，而对于$t'>deg(\phi)$个点的承诺值被揭示时，根据拉式插值法可以还原该多项式，此时无条件隐藏性不再成立

Indistinguishability of Commitments

若承诺方案是完全随机（真随机）的，则无界敌手也无法辨别承诺值，此时称方案满足承诺不可区分性

如果上述承诺方案用于承诺一系列的键值对$<k_1,m_1>,...,<k_{t+1},m_{t+1}>$，若要求其满足不可区分性，则必须令其中至少一个$m_i$为随机的

基于Pedersen的构造方式$PolyyCommit_{Ped}$本身满足该性质，因为Pedersen承诺自带一个随机性

Trapdoor Commitment

上述方案同时还是个陷门承诺，具体可以看论文的完整版本$[6]$

Batch Opening

上述方案可以批量揭示，从而减少承诺方和验证方的计算开销和通信量

令$B\subset \Z_p$表示需要揭示的值的索引构成的集合，满足$|B|<t$，则对于承诺值$\mathcal C=g^{\phi(\alpha)}$和对应的witness $\phi(i),i\in B$，计算对应的$w_B=g^{\psi_B(\alpha)}$，其中

$$ \begin{aligned} \psi_B(x)&=\frac{\phi(x)-r(x)}{\prod_{i\in B}(x-i)} \end{aligned} $$

$r(x)$为$\frac{\phi(x)}{\prod_{i\in B}(x-i)}$的余项，也即$\phi(x)=\psi_B(x)\cdot({\prod_{i\in B}(x-i)})+r(x)$，此时有$\phi(i)=r(i)$

接下来定义两个算法

  • $CreateWitnessBatch(PK,\phi(x),B)$：输出$(B,r(x),w_B)$
  • $VerifyEvalBatch(PK,\mathcal C,B,r(x),w_B)$：验证下列三项

$$ \begin{aligned} 1.&e(\mathcal C,g)=e(g^{\prod_{i\in B}(\alpha-i)},w_B)\cdot e(g,g^{r(\alpha)})\\ 2.&deg(r)=|B|\\ 3.&\forall i\in B,r(i)=\phi(i) \end{aligned} $$

当且仅当验证均通过时输出1，否则输出0

分析一下批量揭示的安全性，由于承诺的计算方式和$PolyCommit_{DL}$方案种承诺的计算方式先提供，且$CreateWitnessBatch$算法提供的信息并没有必独立多次运行$PolyCommit_{DL}$提供的信息多，因此Thm 1种的隐藏性仍然满足

而对于绑定性，任意敌手进行批量揭示时的索引值不应与独立多次揭示的索引值冲突，也即批量揭示的集合和独立多次揭示的集合是同一个集合，具体的绑定性定义如下

$$ Pr\Big [ PK\larr Setup(1^k,t),(\mathcal C,<B,w_b,r(x)>,<i\in B,w_i,\phi(i)>)\larr \mathcal A(PK):VerifyEvalBatch(PK,\mathcal C ,B,w_B,r(x))=1\wedge VerifyEval(PK,\mathcal C ,i,w_i,\phi(x))=1 \wedge \phi(i)\neq r(i)\Big]=\epsilon (k) $$

  • Theorem 3：若群$\mathbb G$满足t-BSDH假设，则上述$CreateWitnessBatch,VerifyEvalBatch$构成的批量揭示方案满足绑定性

具体的证明可以看论文的完整版本$[6]$

由于$PolyCommit_{DL}$的同态性质，可以针对$PolyCommit_{Ped}$修改批处理构造

还有一点需要注意，即便是采用了批量揭示承诺值的$PolyCommit_{DL}$方案，其通信开销也是恒定的

Strong Correctness

可验证秘密共享需要多项式承诺的额外性质：要求被承诺的多项式的度不能大于$t$，该性质称为强正确性（Strong Correctness）

事实上对多项式承诺定义强正确性并不简单，因为有很多度大于$t$的多项式$\phi'$，其承诺值$\phi'(\alpha)=z\in_R\Z_p$是某个度为$t$的多项式的承诺值，此类情况称为其平凡性

为了避免平凡性，要求敌手$\mathcal A$必须使得挑战者$\mathcal B$相信其知道一个多项式$\phi$，具体的安全游戏定义如下

$\mathcal A$为一个度为$t'$的多项式$\phi'$创建承诺，然后$\mathcal B$用一个大小为$t'+1$的索引集$I\subset \Z_p$挑战$\mathcal A$
若$\mathcal A$可以生成$\{<i,\phi(i),w_i>\}_{i\in I}$，其中对于所有的$i\in I$，$VerifyEval$算法均输出1，则这$t'+1$个witness可以用拉式插值法构造一个度为$t-1$的多项式

对于$PolyCommit_{Ped}$方案，强正确性的定义类似，具体可以看论文的完整版本$[6]$

  • Theorem 4：若$\mathcal G$上有t-polyDH假设成立，则$PolyCommit_{DL}$方案和$PolyCommit_{Ped}$方案均满足强正确性

Practicality and Efficiency Improvements

在没有单一可信方的情况下，$Setup$算法可以分布式执行，此时私钥$SK=\alpha$由分布式方式生成（也即多个参与方都持有$\alpha$的一部分，生成方式可以采用Pedersen的可验证秘密共享$[7]$），而公钥同样以分布式的方式（也可以用VSS）生成

由于协议后续不再需要私钥，且根据VSS的性质，任何人都可以利用配对验证公钥的正确性，此时可以将公钥视为可重用的系统全局参数

计算承诺值时需要线性次数的群乘法，验证承诺时需要三次配对和常量次数的乘法

4 Applications

这一节简单介绍了本文的多项式承诺在其他方案中的应用，包括可验证的密钥共享（Verifiable Secret Sharing，VSS）、零知识集（Zero-Knowledge Sets，ZKS）、基本数据库（Elementary Databases，ED）和选择性揭示签名数据及凭证（Selective Disclosure of Signed Data and Credentials）

具体可以看原文的第四节，这里不再介绍

5 Open Problems

本文还有若干个亟待解决的问题

  1. 是否可以基于更弱的假设构建多项式承诺
  2. 本文的多项式承诺还可以用于改进哪些协议
  3. 尽管本文将承诺值减小到了单个群元素，也即本文重点关注通信量，但是计算和揭示承诺需要大量开销，是否有确保通信量的同时进一步减少计算量的多项式承诺方案

总结

通过配对的方式构造了一个对多项式的承诺，使得承诺值仅为一个群元素，安全性依赖于强DH假设和基于双线性群的强DH假设，方案本身满足计算隐藏性和无条件绑定性

这篇paper有几个值得关注的点，第一是多项式承诺，如果说多项式不需要保密，则可以在揭示阶段公开该多项式，如果需要对多项式保密，则方案还可以对多项式上的某一点进行承诺，同时得到一个witness，用于在揭示阶段证明承诺值确实是多项式在该点的值

第二个点是承诺方案是可以批量揭示，对于同一个多项式的承诺，承诺阶段对其承诺至不同的点，只要承诺的点的数量小于多项式的度，揭示阶段就满足绑定性，否则可以通过拉式插值法还原出多项式，此时意味着敌手可以攻破承诺方案

此外还有一些其他的零碎但是比较重要的点，比如说方案满足加法同态、陷门承诺和承诺不可区分性

对于安全性而言，不能将同一个多项式在多于$deg(\phi)$个点承诺，否则根据拉式插值法，敌手可以还原出该多项式，因此对于度比较小的多项式，其具有一定局限性

但是从承诺和验证等式可以看出来方案本身需要的计算量还是不少的，尤其是需要的乘法和指数运算与多项式的度呈线性关系，因此如果多项式的度很大的时候，承诺着和验证者的计算开销也不少

文章后面还介绍了多项式承诺用于优化其他方案的例子，具体没有细看，方案主要是在通信量上进行优化，因为承诺值只为一个群元素，这对一些大型分布式系统或者去中心化的系统很是友好，但是多项式很大的话计算开销还是不小的

后记

看完了，对自己的门限方案又进了一步，争取这周写个简单的demo出来给老师看看

Kate多项式承诺好像上个月期末考之前就说要看了，但是一直拖到了现在

主要还是最近看的论文里面频繁出现，于是打算填个坑，当然也可能会对自己的方案有所帮助就是了

References

$[1]$ Aniket Kate, Gregory M. Zaverucha, Ian Goldberg:Constant-Size Commitments to Polynomials and Their Applications. ASIACRYPT 2010: 177-194

$[2]$ Damgård, I.: Commitment schemes and zero-knowledge protocols. In: Damgård, I.B. (ed.) EEF School 1998. LNCS, vol. 1561, pp. 63–86. Springer, Heidelberg (1999)

$[3]$ Boneh, D., Boyen, X.: Short Signatures Without Random Oracles. In: Cachin, C.,Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer,Heidelberg (2004)

$[4]$ Goyal, V.: Reducing Trust in the PKG in Identity Based Cryptosystems. In: Menezes, A.(ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 430–447. Springer, Heidelberg (2007)

$[5]$ Mitsunari, S., Sakai, R., Kasahara, M.: A New Traitor Tracing. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E85-A(2), 481–484(2002)

$[6]$ Kate, A., Zaverucha, G., Goldberg, I.: Polynomial commitments. Technical report, CACR 2010-10, Centre for Applied Cryptographic Research, University of Waterloo (2010)

$[7]$ Pedersen, T.P.: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer,Heidelberg (1992)