Skip to main content

协议-离散对数证明（DlnProof）

离散对数证明（DlnProof）是一种零知识证明协议，用于证明某人知道某个数值 xx，使得 y=gxmod  py = g^x \mod p，其中 gg 是一个生成元，pp 是一个大素数，yy 是已知的值。DlnProof 可以通过交互式和非交互式两种方式实现。

交互式离散对数证明（基于 Sigma 协议）​

在交互式的离散对数证明中，证明者和验证者通过三次消息传递来完成证明过程。具体步骤如下：

  1. 承诺阶段：

    • 证明者选择一个随机数 rr，计算 t=grmod  pt = g^r \mod p，并将 tt 发送给验证者。

  2. 挑战阶段：

    • 验证者选择一个随机挑战 cc，并将 cc 发送给证明者。

  3. 响应阶段：

    • 证明者计算响应 s=r+c⋅xmod  (p−1)s = r + c \cdot x \mod (p-1)，并将 ss 发送给验证者。

  4. 验证阶段：

    • 验证者检查 gs=?t⋅ycmod  pg^s \stackrel{?}{=} t \cdot y^c \mod p。如果等式成立，验证成功；否则验证失败。

以下是交互式离散对数证明的示例代码：

import random

# 公共参数
p = 23  # 一个大素数
g = 5   # 生成元
x = 6   # 秘密值
y = pow(g, x, p)  # y = g^x mod p

# 承诺阶段
r = random.randint(1, p-2)
t = pow(g, r, p)
print(f"承诺值 t: {t}")

# 挑战阶段
c = random.randint(1, p-2)
print(f"挑战值 c: {c}")

# 响应阶段
s = (r + c * x) % (p-1)
print(f"响应值 s: {s}")

# 验证阶段
if pow(g, s, p) == (t * pow(y, c, p)) % p:
    print("验证成功")
else:
    print("验证失败")

非交互式离散对数证明（基于 Fiat-Shamir 变换）​

非交互式离散对数证明使用 Fiat-Shamir 变换，将交互式的证明过程转换为非交互式。具体步骤如下：

  1. 设置阶段：

    • 生成公共参数 pppp，包括 pp、gg 和 yy。

  2. 证明生成阶段：

    • 证明者选择一个随机数 rr，计算 t=grmod  pt = g^r \mod p。
    • 证明者计算挑战 c=H(t)c = H(t)，其中 HH 是一个哈希函数。
    • 证明者计算响应 s=r+c⋅xmod  (p−1)s = r + c \cdot x \mod (p-1)。
    • 证明者将 tt 和 ss 发送给验证者。

  3. 验证阶段：

    • 验证者计算挑战 c=H(t)c = H(t)。
    • 验证者检查 gs=?t⋅ycmod  pg^s \stackrel{?}{=} t \cdot y^c \mod p。如果等式成立，验证成功；否则验证失败。

以下是非交互式离散对数证明的示例代码：

import random
import hashlib

# 公共参数
p = 23  # 一个大素数
g = 5   # 生成元
x = 6   # 秘密值
y = pow(g, x, p)  # y = g^x mod p

# 设置阶段
def setup():
    return g, p

# 证明生成阶段
def generate_proof(x):
    r = random.randint(1, p-2)
    t = pow(g, r, p)
    c = int(hashlib.sha256(str(t).encode()).hexdigest(), 16) % (p-1)
    s = (r + c * x) % (p-1)
    return t, s

# 验证阶段
def verify_proof(t, s):
    c = int(hashlib.sha256(str(t).encode()).hexdigest(), 16) % (p-1)
    return pow(g, s, p) == (t * pow(y, c, p)) % p

# 示例使用
g, p = setup()
t, s = generate_proof(x)
if verify_proof(t, s):
    print("验证成功")
else:
    print("验证失败")

总结​

离散对数证明（DlnProof）可以通过交互式和非交互式两种方式实现。交互式证明基于 Sigma 协议，通过三次消息传递完成；非交互式证明使用 Fiat-Shamir 变换，将交互式过程转换为非交互式。两者各有优缺点，适用于不同的应用场景。