主页

索引

模块索引

搜索页面

Proof of knowledge

  • In cryptography, a proof of knowledge is an interactive proof in which the prover succeeds in ‘convincing’ a verifier that the prover knows something.

  • What it means for a machine to ‘know something’ is defined in terms of computation.

  • As the program of the prover does not necessarily spit out the knowledge itself (as is the case for zero-knowledge proofs), a machine with a different program, called the knowledge extractor is introduced to capture this idea.

  • We are mostly interested in what can be proven by polynomial time bounded machines. In this case the set of knowledge elements is limited to a set of witnesses of some language in NP.

A proof of knowledge for relation R with knowledge error k is a two party protocol with a prover P and a verifier V with the following two properties:

  1. Completeness: If (x,w) in R, then the prover P who knows witness w for x succeeds in convincing the verifier V of his knowledge.

  2. Validity: Validity requires that the success probability of a knowledge extractor E in extracting the witness, given oracle access to a possibly malicious prover P, must be at least as high as the success probability of the prover P in convincing the verifier. This property guarantees that no prover that doesn’t know the witness can succeed in convincing the verifier.

术语

  • Witness: the value being proven knowledge of。待证明的信息，仅 Prover 知道，不对 Verifier 泄露。

  • Instance: 描述关系中除 witness 外的所有其它元素，均统称为 instance。instance 为 public information，对于 Prover 和 Verifier 均已知。

  • Prover: the entity proving the knowledge of the witness。用于证明其知道 witness 的一方叫做 Prover，Prover 提供 proof。

  • Verifier: the other party that the prover needs to convince of the knowledge of witness。验证 proof 的一方叫做 Verifier。

Protocols

Schnorr protocol

  • One of the simplest and frequently used proofs of knowledge, the proof of knowledge of a discrete logarithm, is due to Schnorr.

  • The protocol is defined for a cyclic group G_q of order q with generator g.

Sigma protocols

  • Protocols which have the above three-move structure (commitment, challenge and response) are called sigma protocols.

  • The Greek letter Sigma visualizes the flow of the protocol.

  • Sigma protocols exist for proving various statements, such as those pertaining to discrete logarithms.

  • Using these proofs, the prover can not only prove the knowledge of the discrete logarithm, but also that the discrete logarithm is of a specific form.

  • 又称为 3 phase protocols，用于证明 knowledge of values in some relation，但是又不泄露 values 的具体值。

  • 如用于证明 knowledge of discrete log：given g and y，prove knowledge of x 满足 g^x=y without revealing x。

Sigma protocol 可分三步描述:

1. Commitment:
  The prover generates a random number, creates a commitment to that randomness
    and sends the commitment to the verifier.

2. Challenge:
  After getting the commitment, the verifier generates a random number as a challenge and sends it to the prover.
  It is important that the verifier does not send the challenge before getting the commitment or else the prover can cheat.

3. Response:
  The prover takes the challenge and creates a response using the `random number chosen in step 1)`, the `challenge` and the `witness`.
  The prover will then send the response to the verifier who will do some computation and will or will not be convinced of the knowledge of the `witness`.

以 proof of knowledge of discrete log 为例：(y=g^x)

该协议也可称为 Schnorr identification protocol 或 Schnorr protocol
1. Commitment:
Prover 选择随机数 `r`，创建 commitment `t=g^r`，将 `t` 值发送给 Verifier

2. Challenge:
Verifier 存储`t`值，生成随机 challenge `c`，将`c`值发送给 Prover

3. Response:
Prover 根据收到的 challenge `c` 值，创建 response `s = r + x ∗ c`，将`s`值发送给 Verifier


Verifier:
Verifier 只需要验证 `g^s = y^c ∗ t` 成立，即可相信 Prover 确实知道相应的 `x` 使得`y = g^x ` 成立

  • 注意事项一：Prover 应每次使用新的``随机数r``

  • 注意事项二：Prover 应无法预测 challenge c

基于 Sigma protocol 实现基础协议

Equality of discrete logs

备注

证明 Prover 知道 witness x，使得 g^x = y 且 h^x = z

Prover:

1. 生成随机数r，采用相同的r 创建 2 个 commitment `t_1=g^r`, `t_2=h^rt`
2. 以 g,h,y,z,t_1,t_2为输入，生成 challenge `c=Hash(g,h,y,z,t_1,t_2)`
3. 创建 response `s=r+c*x`
4. 发送 (t_1,t_2,s)给 Verifier

Verifier:

验证 `g^s=y^c*t` 和 `h^s=z^c*t` 是否同时成立即可

Conjunction (AND) of discrete logs

证明 Prover 知道 witness a, b 使得 g^a=P 且 h^b=Q

Disjunction (OR) of discrete logs

证明 Prover 知道 witness a 使得 g^a=P，或者，知道 witness b 使得 h^b=Q，但是，无法同时知道 a,b 使得 g^a=P 且 h^b=Q 同时成立。不能暴露 Prover 到底知道的是a 还是b。

Knowledge of the opening of Pedersen commitment

P=Com(m;r)=g^m*h^r，其中``(m,r)`` 称为 the opening of the commitment。证明 Prover 知道 witness(m,r)，使得P = g^m*h^r

Equality of the opening of 2 Pedersen commitment

证明 Prover 知道 witness(a,b)，使得 P=g_1^a*h_1^b 且 Q=g_2^a*h_2^b

Equality of message in 2 Pedersen commitment

证明 Prover 知道 witness(a,b,d)，使得 P=g_1^a*h_1^b 且 Q=g_2^a*h_2^d

Inequality of discrete logs

  • 该协议首次在 Jan Camenisch 和 Victor Shoup 2003 年论文`《Practical Verifiable Encryption and Decryption of Discrete Logarithms∗》 <https://www.shoup.net/papers/verenc.pdf>`_中第 6 节提及

  • 证明 Prover 知道 witness(a)，使得``P=g^a``，Q=h^b，且 a!=b

参考

主页

索引

模块索引

搜索页面