Compressed sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics学习笔记

1. 引言

Thomas Attema等人2020年论文《Compressed sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics》发表于CRYPTO 2020。

主要关注3种类型的assumption：

• Discrete Logarithm assumption：Bulletproofs中是基于Discrete Logarithm assumption构建的。
• Strong-RSA assumption：《Transparent snarks from DARK compilers》可看成是基于Strong-RSA assumption下对Bulletproofs进行改进实现的polynomial commitment。
• Knowledgeof-Exponent assumption，known to be unfalsifiable，目前仍有争议的安全假设。

本文主要介绍基于Discrete Logarithm assumption的$\sum$-protocol，Strong-RSA assumption可采用类似方式构建。

1.1 核心的$\sum$-Protocol

basic $\sum$-Protocol ${\Pi }_0$：

• public info: commitment $P$，arbitrary public linear form $L$。
• private info：secret vector $\vec{x}\in {\mathbb{Z}}_q^n$，$y$。
• relation：$P=Com(\vec{x})\wedge y=L(\vec{x})$

basic $\sum$-Protocol ${\Pi }_0$ 证明过程为：

• Prover：选择secret random vector $\vec{r}$，计算commitment $A=Com(\vec{r})$和$y^{\prime }=L(\vec{r})$。
  将$A,y^{\prime }$发送给Verifier。
• Verifier：发送random challenge $c\in {\mathbb{Z}}_q$ 给Prover。
• Prover：计算$\vec{z}=c\vec{x}+\vec{r}$。
  将vector $\vec{z}$ 发送给Verifier。
• Verifier：验证$Com(\vec{z})=A{P}^c$以及$L(\vec{z})=cy+y^{\prime }$是否成立即可。

以上basic $\sum$-Protocol ${\Pi }_0$的communication cost主要为$\vec{z}$——the opening of $A{P}^c$，其communication complexity为$O(n)$，其中$n$为vector length。

本文在basic $\sum$-Protocol ${\Pi }_0$ 的基础上实现了amortized版本${\Pi }_0^{Am}$，针对的场景为：

• public info: commitments $P_1,?,P_s$，arbitrary public linear form $L$。
• private info：secret vector ${\vec{x}}_1,?,{\vec{x}}_s\in {\mathbb{Z}}_q^n$，$y_1,?,y_s$。
• relation：$P_1=Com({\vec{x}}_1)\wedge ?\wedge P_s=Com({\vec{x}}_s)\wedge y_1=L({\vec{x}}_1)\wedge ?\wedge y_s=L({\vec{x}}_s)$

amortized版本${\Pi }_0^{Am}$的communication cost应只比basic版本多$s?1$个elements——实际即为 the evaluations at the $s?1$ additional input vectors。

借助Bulletproofs算法，可将basic $\sum$-Protocol ${\Pi }_0$ 的communication cost压缩为$O(\log n)$，Prover与Verifier之间的交互次数也增加为了$O(\log n)$。技术上来说，这种压缩将degrade the soundness from unconditional to computational, and protocols with computational soundness成为argument of knowledge。（注意Bulletproofs方案不具有zero knowledge，最终prover会reveal $z$。）

本文考虑的是针对amortized版本${\Pi }_0^{Am}$的压缩。与Bulletproofs方案不同，不再发送整个vector $\vec{z}$，改为要求Prover知道相应的$\vec{z}$，使得$Com(\vec{z})=A{P}^c$成立。