密码学中的sigma-protocol

1. sigma-protocol的定义

在论文《On Σ-protocols》中，有如下定义：

• relation DL，其中的 w w w可称为a witness for x x x: D L = { ( x , w ) ∣ x = ( p , q , g , h ) , o r d ( g ) = o r d ( h ) = q , h = g w } DL=\{(x,w)|x=(p,q,g,h), ord(g)=ord(h)=q,h=g^w\} DL={(x,w)∣x=(p,q,g,h),ord(g)=ord(h)=q,h=gw}

其中， p , q p,q p,q为素数， g , h ∈ Z p ∗ , w ∈ Z q g,h\in Z_p^*,w\in Z_q g,h∈Zp∗​,w∈Zq​，R为二进制relation，R表示为 { 0 , 1 } ∗ × { 0 , 1 } ∗ \{0,1\}^*\times \{0,1\}^* {0,1}∗×{0,1}∗。 满足上面条件的 ( x , w ) ∈ R (x,w)\in R (x,w)∈R成立。

以上， x x x对于Prover P和Verifier V均可见，为public input，而满足 ( x , w ) ∈ R (x,w)\in R (x,w)∈R的 w w w为Prover P的private input，对Verifier V不可见。 场景描述为， p p p为素数， q q q为 p − 1 p-1 p−1的最大素数因子， g 为 Z p ∗ g为 Z_p^* g为Zp∗​中order为 q q q的元素，某 w w w仅P可知， h = g w   m o d   p h=g^w\ mod\ p h=gw mod p， x = ( p , q , g , h ) x=(p,q,g,h) x=(p,q,g,h)对P/V均可见，为public input。在实际应用时， p , q p,q p,q通常长时间固定不变，关于 p , q p,q p,q的素数性V可以鉴定一次即可，不需要每次都鉴定。

详细的流程分为三大步：

• 1） P选择随机数 r ∈ Z q r\in Z_q r∈Zq​， r r r仅P知，对V不可见，P计算 a = g r   m o d   p a=g^r\ mod\ p a=gr mod p，P将 a a a值发送给V；
• 2） V选择 t − b i t t-bit t−bit的随机数challenge e ∈ Z 2 t e\in Z_{2^t} e∈Z2t​（此处的 t t t为固定的，且 2 t < q 2^t