RLN on KZG Version A Vulnerabilities

问题描述

在 RLN on KZG协议中，证明者需要提交一个多项式

$f$ 的承诺以及公钥

$g^{f(0)}$。我们发现了一个漏洞，攻击者可以在不知道私钥的情况下伪造公钥。为了解决这个问题，我们提出了一个解决方案，使用 Schnorr 签名来验证公钥，可以有效地防止这种攻击。

漏洞详细信息

在原始的 RLN 协议中，证明者提交多项式承诺

$g^{f(\alpha )}$、公钥

$g^{f(0)}$ 和开放证明

$g^{{\psi }_0(\alpha )}$。验证者检查用户的公钥是否在提交的多项式上，通过验证开放证明

$g^{{\psi }_0(\alpha )}$：

$$e(g^{{\psi }_0(\alpha )},g^{\alpha })\cdot e(g,g^{f(0)})\stackrel{?}{=}e(g,g^{f(\alpha )})$$

然而，攻击者可以在不知道私钥的情况下伪造公钥。攻击者可以选择一个随机数

$\gamma$，然后修改公钥和开放证明，使它们满足以下等式：

$$e(g^{{\psi }_0(\alpha )}\cdot g^{\gamma },g^{\alpha })\cdot e(g,g^{f(0)}\cdot g^{\alpha \cdot -\gamma })\stackrel{?}{=}e(g,g^{f(\alpha )})$$

1. 将等式左边展开:

$$e(g^{{\psi }_0(\alpha )}\cdot g^{\gamma },g^{\alpha })\cdot e(g,g^{f(0)}\cdot g^{\alpha \cdot -\gamma })=e(g^{{\psi }_0(\alpha )},g^{\alpha })\cdot e(g^{\gamma },g^{\alpha })\cdot e(g,g^{f(0)})\cdot e(g,g^{\alpha \cdot -\gamma })$$

2. 使用Pairing的性质
   $e(g^a,g^b)=e(g,g{)}^{ab}$ 将等式做如下变换:

$$=e(g,g{)}^{{\psi }_0(\alpha )\cdot \alpha }\cdot e(g,g{)}^{\gamma \cdot \alpha }\cdot e(g,g{)}^{f(0)}\cdot e(g,g{)}^{-\gamma \cdot \alpha }$$

3. 合并指数:

$$=e(g,g{)}^{{\psi }_0(\alpha )\cdot \alpha +\gamma \cdot \alpha +f(0)-\gamma \cdot \alpha }$$

4. 已知
   ${\psi }_0(\alpha )\cdot \alpha =f(\alpha )-f(0)$, 替换到等式中:

$$=e(g,g{)}^{f(\alpha )-f(0)+\gamma \cdot \alpha +f(0)-\gamma \cdot \alpha }$$

5. 消除
   $f(0)$ 和
   $\gamma \cdot \alpha$:

$$=e(g,g{)}^{f(\alpha )}$$

通过这种方式，攻击者可以使验证者相信他们提交了一个有效的公钥，但实际上这个公钥并不与他们的私钥相匹配。

解决方案

我们提出了一个解决方案，使用 Schnorr 签名来证明证明者确实拥有与公钥匹配的私钥。这是有效的，因为攻击者无法获取私钥，因为他们没有办法计算

$g^{\alpha }$，因为

$\alpha$ 是从 SRS 中获得的，而没有人知道

$\alpha$ 的值。这意味着攻击者不能制作满足配对检查的

$\gamma$，除非他们知道私钥。

当证明者提交其公钥

$g^{f(0)}$ 时，他们还需要提交一个 Schnorr 签名作为知识证明，证明他们知道公钥对应的私钥。验证者可以通过验证该 Schnorr 签名来确保证明者确实知道与其公钥对应的私钥。这个步骤在 RLN 协议的设置步骤中进行，可以有效地防止攻击者提交伪造的公钥。

Schnorr签名是一种数字签名方案。它们具有可以证明安全性的优点，假设离散对数问题是难解的，并且相对简单且高效。

Schnorr签名算法涉及以下步骤：

1. 密钥生成:

   • 从小于预定质数
     $q$的整数集中随机选择私钥
     $x$。
   • 然后计算相应的公钥
     $y$，
     $y=g^x\mathrm{mod}p$，其中
     $g$是一个循环群
     $G$的生成器，
     $G$的阶为
     $q$，
     $p$是模数。

2. 签名:

   • 从小于
     $q$的整数集中随机选择
     $k$。
   • 计算
     $r=g^k\mathrm{mod}p$。
   • 计算
     $e=H(M||r)$，其中
     $H$是一个密码学哈希函数，
     $M$是信息，
     $||$表示连接。
   • 计算
     $s=k-xe\mathrm{mod}q$。
   • 签名是对
     $(s,e)$。

3. 验证:

   • 计算
     $r^{\prime }=(g^s\ast y^e)\mathrm{mod}p$。
   • 计算
     $e^{\prime }=H(M||r^{\prime })$。
   • 如果
     $e^{\prime }=e$，则签名已验证。

在RLN的上下文中，可以使用Schnorr签名来证明证明者知道与公钥

$g^{f(0)}$对应的私钥。证明者使用他们的私钥

$f(0)$签名一条信息（可以是随机挑战或已知值），验证者检查Schnorr签名。如果签名验证，这意味着证明者知道与

$g^{f(0)}$对应的私钥，所以公钥没有被伪造。

在RLN中，使用KZG承诺和Schnorr签名，需要知道

$g^{\alpha }$并面临离散对数(DL)问题的步骤包括：

1. 承诺：

   • 用户使用参考字符串计算KZG多项式承诺
     $C=g^{f(\alpha )}$。这里，用户需要知道
     $g^{\alpha }$来创建承诺。

2. 开放证明：

   • 为了发送消息，用户共享
     $(f(m),g^{{\psi }_m(\alpha )})$，其中
     $m$是消息值的哈希，
     $g^{{\psi }_m(\alpha )}$是开放证明。用户需要知道
     $g^{\alpha }$来创建开放证明。

离散对数(DL)问题在Schnorr签名和RLN协议的安全性中起着关键作用。假设在给定

$g^x\mathrm{mod}p$的情况下，计算离散对数

$x$在计算上是不可行的。在RLN的情况下，未知的离散对数是

$\alpha$，而

$g^{\alpha }$是共享参考字符串的一部分。

当攻击者尝试通过使用随机

$\gamma$来伪造公钥

$g^{f(0)}$时，他将需要知道

$\alpha$的值来操作等式

$g^{f(0)+\alpha \ast \gamma }$。然而，由于DL问题的困难性，攻击者无法从参考字符串计算

$\alpha$，因此在不知道相应私钥的情况下无法伪造公钥。

结论

在 RLN 协议中，存在一个漏洞，攻击者可以在不知道私钥的情况下伪造公钥。为了解决这个问题，我们提出了一个解决方案，使用 Schnorr 签名来验证公钥。这个解决方案有效地防止了攻击者提交伪造的公钥。然而，需要注意的是，这个解决方案需要修改 RLN 协议的设置步骤，使得证明者需要提交更多的信息，并且验证者需要进行更多的验证步骤。我们希望这个解决方案可以帮助 RLN 协议的开发者修复这个漏洞，进一步提高 RLN 协议的安全性。