【OH问题点小结】Week1-Session1&Session3

[Mobius3-3]

Session1

Exercise1

Q：G3-COLORABLE（图3染色）问题中，原协议是否具有零知识性？如果将协议的规则修改为可以任选非一条Edge的两个Vertex验证是否会破坏零知识性？

A：根据G3-COLORABLE验证问题的定义，Prover先声明了一个染色方案 $\pi(V) $，但每次验证交互前Prover会随机选取一个染色的permutation $\sigma $作用于 $\pi(V) $得到一个新的染色结果 $\phi $, 即 $\phi(V):=\sigma(\pi(V)) $。

• 在原协议的交互过程中，由于verifier没有每次permutation的信息，在只揭露一条Edge对应2个Vertex的情况下，不会破坏零知识性。
• 修改协议规则后，由于非连接的Vertix染色信息可能被揭露，导致Prover染色方案信息泄露。

Exercise2

Q: Confidence计算公式是否为 $1-(1/E)^n $?

A: Confidence即当Verifier验证通过时，G是3-COLORABLE的最小概率。

• 由于每次验证是随机独立事件，先计算在单次交互中，当Verifier验证通过时，G不是3-COLORABLE的最大概率。相应的概率为 $P=1-1/|E| $。
• n次交互后，当Verifier验证通过时，G不是3-COLORABLE的最大概率为 $P=(1-1/|E|)^n $。相应的confidence为 $1-(1-1/|E|)^n $。

Zero-Knowledge Proofs for discrete logs

Q1: $s = (r + bx)(mod (p − 1)) $中为什么是 $p-1 $?
A1: 由数论中整数模素数 $p $乘法群的性质可得: $A^{p-1}=1 $，因此只需计算模 $p-1 $后的结果。
有同学也做了补充：#25

Q2: 勘误
A2: $m^r(mod p) = (m^x)^c × (m^r)(mod p)$ 应改为: $m^s(mod p) = (m^x)^c × (m^r)(mod p) $

Session2

Self-pairing implies failure of DDH

Q1: self-pairing如何高效打破DDH assumption？
A1: 根据 $e(\alpha g, \beta g)=e(\alpha\beta g, g) $，将 $αβg=y $代入前式即可判断其是否成立。

Q2: pairing映射是否可以多对一？
A2: 以 $e(\alpha g, \beta g)=e(\alpha\beta g, g) $为例，当 $\alpha\beta $的因式分解不唯一时就存在多对一映射。