0%

零知识证明

交互式零知识证明

性质

  • 完整性(Completeness):给遵循协议的 Prover 和 Verifier,协议能以压倒性的概率成功
  • 完备性(Soundness):不知道这个秘密的人,没有人能以不可忽略的可能性说服验证者(不可骗过验证者)
  • 零知识性(Zero knowledge):proof 不会泄露任何额外的信息

Fiat-Shamir Protocol for Proving Quadratic Residues(Uriel Feige, Amos Fiat, and Adi Shamir in 1988.)

声明:Prover 知道 \(w\) 满足 \(w^2=x \mod n\)

证明:重复下面协议 \(t\)

One-round Protocol:

  • P to V:\(y = r^2 \mod n\)\(r\) 为随机数
  • V to P:随机选取\(b←\{0,1\}\)
  • P to V:\(z=rw^b\) ,即 \(z=r,b=0;z=rw,b=1\)
  • V 验证:\(z^2=yx^b\) ,即 \(z^2=y,b=0;z^2=yx,b=0\)

Schnorr Id protocol (ZK Proof of Discrete Log)

系统参数: 素数 \(p\)\({Z_p}^*\) 生成元 \(g\)

声明:知道 \(s\),满足 \(v = g^s \mod p\)

证明:

  • A: 选择随机数 \(r\)\(r \in [1,...,p-1]\),计算并发送 \(x = g^r \mod p\)
  • B: 发送随机挑战 \(e\),$e $ ,\(2^t>\log n\)
  • A: 发送 \(y=r-se \mod (p-1)\)
  • B: 验证 \(x = g^yv^e \mod p\)

承诺

性质

  • 阶段
    • Commit 阶段:发送方将消息锁在一个盒子中,并将这个锁住的盒子发送给接收方
    • Reveal 阶段:发送方向接收方证明框中的消息是特定的消息
  • 安全属性
    • Hiding:Commit 阶段敌手不能获取承诺消息的任何信息
      • Unconditional hiding:信息论上完全隐藏
      • Computational hiding:计算能力有限的敌手无法获取信息
    • Binding:Commit 阶段结束时,敌手不能用让两个不同的值在 Reveal 阶段被成功 Reveal。
      • Unconditional binding
      • Computational binding
  • 哈希承诺

Pedersen承诺

初始化

可信第三方 T 选取 \(q\) 阶有限循环群 \(G\)\(G\) 上存在 CDH 难题(Computational binding)。

T \(G\) 中选取生成元 \(g\in G\) 和元素 \(h\in G\)

计算承诺(Commit)

实体 U 的消息 \(x\)U 从有限域 \({\mathbb{Z}}_q\) 中选取随机数 \(r\in{\mathbb{Z}}_q\)(致盲因子),计算 \(M=g^xh^r\in G\)\(M\) 为消息 \(x\) 的承诺。

打开承诺(Reveal / Open)

U 能够通过运行一个如下所示的知识的零知识证明协议来打开承诺同时不暴露其隐私消息\((x,r)\)\[ PK\{(x,\;r):\;M=g^xh^r\} \]

交互式零知识方案

实体 U (证明方)让验证方 V 验证承诺 \(M\),但无需泄漏 \(m\)\(r\)

image-20210622142125904

公开参数:\((G,q,g,h)\)

Prover 输入:承诺 \(M\) 和消息 \((m,r)\) 使得 \(M=g^mh^r\) 成立。

  1. 证明方从有限域 \({\mathbb{Z}}_q\) 中选择随机参数 \(y,s\in{\mathbb{Z}}_q\)。,计算 \(d=g^yh^s\),并将 \(d\) 发送给验证方。
  2. 验证方从有限域\({\mathbb{Z}}_q\) 中选择随机参数 \(c\in{\mathbb{Z}}_q\) ,并将 \(c\) 作为挑战发送给证明方。
  3. 证明方计算:\(u=cx+y \mod q\)\(v=cr+s \mod q\),并将 \(u\)\(v\) 作为应答发送给验证方。
  4. 验证方验证等式 \(g^uh^v=dM^c\mod p \in G\),若等式成立,则证明成功,否则失败。

乘法同态

Pedersen 承诺的同态性是指,如果comm1,comm2分别是使用盲因子r1,r2的对v1,v2的承诺,则comm (comm=comm1*comm2)是使用盲因子 r1+r2 对 v1+v2 的承诺。

加法同态

椭圆曲线上的 Pedersen 承诺,形式为:\(P = r · G +v·H\)\(G\)\(H\) 是椭圆曲线上的不同的点,\(r\) 是致盲因子,\(v\) 为消息。

\[ \begin{align} comm(v_1,r_1) =& r_1 · G +v_1·H \\ comm(v_2,r_2) =& r_2 · G +v_2·H \\ comm(v_3,r_3)=&comm(v_1,r_1)+comm(v_2,r_3)\\ =&r_1 · G +v_1·H+r_2 · G +v_2·H\\ =&(r_1 + r_2)· G + (v_1 + v_2)·H \end{align} \] 验证 \(v_3=v_1 + v_2\) ,只需 \(r_3=r_1 + r_2\)

Pedersen_exchange

双线性对

定义三个素数 \(p\) 阶群乘法循环群\((G_1,·)、(G_2,·)、(G_T,·)\) ,并且定义在这三个群上的一个映射关系 \(e:G_1 \times G_2 \rightarrow G_T\),并且满足以下的三个性质:

  • 双线性性:对任意的 \(g_1\in G_1,g_2 \in G_2\)\(a,b \in {\mathbb{Z}}_p\) ,均有 \(e({g_1}^a,{g_2}^b)=e(g_1,g_2)^{ab}\);
  • 非退化性:\(\exist g_1\in G_1,g_2 \in G_2\),满足 $e({g_1},{g_2}) G_T $;
  • 可计算性:映射 \(e\) 的可计算性,存在有效的多项式时间算法计算双线性对的值

CL签名(Jan Camenisch and Anna Lysyanskaya,2004)

Scheme A: 对消息签名

密钥生成

初始化,生成参数 \((q,G,\mathbf G,g,\mathbf g,e)\)\(e:G \times G \rightarrow \mathbf G\), 取 \(x ← {\mathbb{Z}}_q\)\(y ← {\mathbb{Z}}_q\),计算\(X = g^x\)\(Y = g^y\),私钥为 \(sk = (x,y)\),公钥为 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y)\)

签名算法

输入:消息 \(m\), 私钥 \(sk = (x,y)\),公钥 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y)\)

计算:

  • 选择随机数 \(a \in G\)
  • \(b=a^y\)
  • \(c=a^{x+mxy}\)

输出:签名 \(σ = (a,b,c)\)

验签算法

输入:公钥 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y)\), 消息 \(m\), 签名 \(σ = (a, b, c)\)

验证: \[ e(a,Y)=e(g,b) \\ e(X,a)·e(X,b)^m =e(g,c) \]

proof

\[ \begin{align} e(a,Y)=& e(a,g)^y\\ =& e(g,a)^y\\ =&e(g,b) \\ \\ e(X,a)·e(X,b)^m =& e(g, a)^x · e(g, a)^{mxy}\\ =& e(g, a)^{x+mxy}\\ =& e(g, c) \end{align} \]

Scheme B: 对承诺签名

密钥生成

初始化算法生成 \((q,G,\mathbf G,g,\mathbf g,e)\), 取 \(x ← {\mathbb{Z}}_q\)\(y ← {\mathbb{Z}}_q\)\(z ← {\mathbb{Z}}_q\),计算\(X = g^x\)\(Y = g^y\)\(Z = g^z\),私钥为 \(sk = (x,y,z)\),公钥为 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y,Z)\)

签名算法

输入:消息 \((m,r)\),私钥 \(sk = (x,y,z)\),公钥 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y,Z)\)

计算:

  • 选取随机数 \(a ← G\)
  • \(A=a^z\)
  • \(b=a^y\)\(B=A^y\)
  • \(c = a^{x+xym}A^{xyr}\)

输出: 签名 \(σ = (a,A,b,B,c)\)

验签算法

输入:公钥 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y,Z)\),消息 \((m,r)\),签名 \(σ = (a,A,b,B,c)\)

验证:

  • \(A\) 的正确性:\(e(a,Z) = e(g,A)\)

  • \(b\)\(B\) 的正确性:\(e(a,Y) = e(g,b)\)\(e(A,Y ) = e(g,B)\)

  • \(c\) 的正确性:\(e(X, a) · e(X, b)^m · e(X, B)^r = e(g, c)\)

Proof

\(A\) 的正确性: \[ \begin{align} e(a,Z) =& e(a,g)^z \\=& e(g,a)^z \\=&e(g,A) \end{align} \] \(b\)\(B\) 的正确性: \[ \begin{align} e(a,Y) =& e(a,g)^y \\=& e(g,a)^y \\=& e(g,b) \\ \\ e(A,Y ) =& e(a,g)^{zy} \\=& e(g,A)^y \\=& e(g,B) \end{align} \] \(c\) 的正确性: \[ \begin{align} e(X, a) · e(X, b)^m · e(X, B)^r =&e(g,a)^xe(g,a)^{xym}e(g,a)^{xyzr} \\=& e(g,a)^{x+xym}e(g,a)^{xyzr} \\=& e(g,a)^{x+xym}e(g,A)^{xyr} \\=&e(g, c) \end{align} \]

Scheme C: 分组消息

密钥生成

初始化算法生成 \((q,G,\mathbf G,g,\mathbf g,e)\), 取 \(x ← {\mathbb{Z}}_q\)\(y ← {\mathbb{Z}}_q\),对于\(1≤ i ≤ l\)\(Z_i ← {\mathbb{Z}}_q\)

计算\(X = g^x\)\(Y = g^y\),对于 \(1≤ i ≤ l\)\(Z_i = g^{z_i}\)

私钥为 \(sk = (x,y,z_1,...,z_l)\),公钥为 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y,\{Z_i\})\)

签名算法

输入:消息 \((m^{(0)}, m^{(1)}, . . . , m^{(l)})\),私钥 \(sk = (x,y,z_1,...,z_l)\),公钥 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y,\{Z_i\})\)

计算:

  • 选取随机数 \(a ← G\)
  • \(A_i=a^{z_i}\)\(1≤ i ≤ l\)
  • \(b=a^y\)\(B_i={A_i}^y\)
  • \(c = a^{x+xym^{(0)}}\textstyle\prod_{i=1}^l{A_i}^{xym^{(i)}}\)

输出:签名 \(σ = (a,{A_i},b,{B_i},c)\)

验签算法

输入:公钥 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y,\{Z_i\})\),消息 \((m^{(0)}, m^{(1)}, . . . , m^{(l)})\),签名 \(σ = (a,{A_i},b,{B_i},c)\)

验证:

  • \({A_i}\) 的正确性:\(e(a,Z_i) = e(g,A_i)\)

  • \(b\)\(B_i\) 的正确性:\(e(a,Y) = e(g,b)\)\(e(A_i,Y ) = e(g,B_i)\)

  • \(c\) 的正确性:\(e(X, a) · e(X, b)^{m^{(0)}} ·\textstyle\prod_{i=1}^l e(X, B_i)^{m^{(i)}} = e(g, c)\)

匿名凭据系统(Anonymous Credential System)

Structure

为了构建一个匿名证书系统,有必要展示:

  • 一个承诺方案(对消息加锁)
  • 一个签名-性质方案和有效的协议:
    • (1)证明两个承诺值的相等性;
    • (2)在承诺值上获得签名(不向签名者透露承诺的消息内容);
    • (3)证明签名对承诺值的知识。

在 Scheme A 上构造

丢失 Information-Theoretic Hiding,\(M=g^m\)

在 Scheme B 上构造

输入:承诺 \(M=g^mZ^r\),私钥 \(sk = (x,y,z)\),公钥 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y,Z)\)

计算:

  • 选取随机数 \(\alpha ← {\mathbb{Z}}_q\)\(a=g^\alpha\)
  • \(A=a^z\)
  • \(b=a^y\)\(B=A^y\)
  • \(c=a^xM^{\alpha xy}\)\(c = a^{x+xym}A^{xyr}\)

原理: \[ \begin{align} c=&a^xM^{axy} \\=&g^{\alpha x}g^{\alpha xym}Z^{\alpha xyr} \\=&g^{\alpha x}g^{\alpha xym}g^{\alpha xyzr} \\=&a^{x}a^{xym}a^{xyzr} \\=&a^{x+xym}A^{xyr} \end{align} \]

在 Scheme C 上构造

共同输入:公钥 \(pk = (q,G,\mathbf G,g,\mathbf g,e,X,Y,\{Z_i\})\),承诺 \(M\)

用户:消息 \((m^{(0)}, m^{(1)}, . . . , m^{(l)})\),计算 \(M=g^{m^{(0)}} ·\textstyle\prod_{i=1}^l {Z_i}^{m^{(i)}}\)

签名者输入:私钥 \(sk = (x,y,z)\)

协议:

  1. 用户通过零知识证明打开承诺: \[ \textstyle PK\{(\mu^{(0)},...,\mu^{(l)}):M=g^{u^{(0)}} ·\textstyle\prod_{i=1}^l {Z_i}^{u^{(i)}}\} \]

  2. 签名者签名:

    • 选取随机数 \(\alpha ← {\mathbb{Z}}_q\)\(a=g^\alpha\)
    • \(A_i=a^{z_i}\)\(1≤ i ≤ l\)
    • \(b=a^y\)\(B_i={A_i}^y\)\(1≤ i ≤ l\)
    • \(c=a^xM^{\alpha xy}\)
image-20210622191745344

盲签名

性质

盲签名允许消息者先将消息盲化,而后让签名者对盲化的消息进行签名,最后消息拥有者对签字除去盲因子,得到签名者关于原消息的签名。盲签名就是接收者在不让签名者获取所签署消息具体内容的情况下所采取的一种特殊的数字签名技术,它除了满足一般的数字签名条件外,还必须满足下面的两条性质:

  • 签名者对其所签署的消息是不可见的,即签名者不知道他所签署消息的具体内容。

  • 签名消息不可追踪,即当签名消息被公布后,签名者无法知道这是他哪次的签署的。

CL盲签名方案

取随机数 \(r\) 作为盲因子,随机数 \(a\) 变为 \(a^r\)

Scheme A

签名:\(σ = (a^r,b^r,c^r)\)

验签: \[ \begin{align} e(a^r,Y)=&e(g,b^r) \\ e(a,Y)^r=&e(g,b)^r \\ \\ e(X,a^r)·e(X,b^r)^m =&e(g,c^r) \\ e(X,a)^r·e(X,b)^{rm} =&e(g,c)^r \\ {(e(X,a)·e(X,b)^m)}^r=&e(g,c)^r \end{align} \]

Scheme B

签名:\(σ = (a^r,A^r,b^r,B^r,c^r)\)

验签:

  • \(A\) 的正确性:\(e(a^r,Z) = e(g,A^r)\)

  • \(b\)\(B\) 的正确性:\(e(a^r,Y) = e(g,b^r)\)\(e(A^r,Y ) = e(g,B^r)\)

  • \(c\) 的正确性:\(e(X, a^r) · e(X, b^r)^m · e(X, B^r)^r = e(g, c^r)\)

Scheme C

签名: \(σ = (a^r,{A_i}^r,b^r,{B_i}^r,c^r)\)

验签:

  • \({A_i}\) 的正确性:\(e(a^r,Z_i) = e(g,A_i^r)\)
  • \(b\)\(B_i\) 的正确性:\(e(a^r,Y) = e(g,b^r)\)\(e(A_i^r,Y ) = e(g,B_i^r)\)
  • \(c\) 的正确性:\(e(X, a^r) · e(X, b^r)^{m^{(0)}} ·\textstyle\prod_{i=1}^l e(X, {B_i}^r)^{m^{(i)}} = e(g, c^r)\)

优点

  • 适用于证书方案,\(a\) 签名者随机选取,很容易生成另一个签名。(just choose a random r ∈ Zq and let a ̃ = ar , ̃b = br , c ̃ = cr )
  • 群签名
  • 聚合签名

欢迎关注我的其它发布渠道