#证明 #字节 #离散 #等式 #标量 #对数 #

已撤回 dleq-serai

实现单曲线和跨曲线离散对数等式证明

0.1.0 2022年7月12日

#39 in #标量

MIT 许可证

50KB
1K SLoC

离散对数等式

实现支持 ff/group 的曲线的离散对数等式证明。还有一个高度实验性的跨组 DLEq 证明,在 experimental 功能下,尽管尚未提供正式证明,但仍然可用。此库尚未经过审计。

跨组 DLEq

当前的跨组 DLEq 基于 MRL-0010,尽管它在证明两个密钥的 G'/H' 组件具有相同的离散对数时是正确的,但它没有证明没有 G/H 组件。因此,它增加了一对 Schnorr 证明,以证明已知的 G'/H' 组件,确保没有 G/H 组件(假设 G/HG'/H' 之间是未知的)。

环签名也合并了挑战,从每个位的证明中删除了一个元素,这仅略微降低了挑战安全性(因为它们不是在每一个标量场上均匀分布,而是在每个标量场的相互位容量上均匀分布)。这种减少与应用于所证明标量的减少相同,因此不应降低整体安全性。这确实会创建一个域分离的缺乏,但那不应成为一个问题。

以下变体可用

  • ClassicLinear。这仅用于参考目的,是上述描述的证明,没有进一步的优化。

  • ConciseLinear。这每次证明 2 位,不增加两位的签名大小,但减少总的承诺/挑战的数量。

  • EfficientLinear。它提供环签名,形式为 ((R_G, R_H), s),而不是 (e, s),因此可以批量验证其最终步骤。这是性能最高的选项,也是最大的选项。

  • CompromiseLinear。这提供了如下形式的签名:((R_G, R_H), s) 并且一次证明2位。虽然这增加了环签名的验证步骤(这些步骤不能批量验证),并减少了批量处理的项数(这是一个随着数量增加而增长效率的操作),但它权衡了速度和大小。

以下数据来自在Intel i7-118567上使用k256/curve25519_dalek进行的基准测试。

算法 大小 验证时间
ClassicLinear 56829字节 (+27%) 157ms (0%)
ConciseLinear 44607字节(参考) 156ms(参考)
EfficientLinear 65145字节 (+46%) 122ms (-22%)
CompromiseLinear 48765字节 (+9%) 137ms (-12%)

CompromiseLinear 是最佳选择,因为它在大小上仅略逊一筹,但仍然实现了大多数期望的性能改进。尽管如此,原始的假设(存在缺陷)以及这里的任何构造都尚未得到证明或审计。因此,它们仅是实验性的,不推荐使用。

所有证明都附加了 "Linear",希望有对数证明可用,这可能会立即成为最有效的方法。

依赖项

~0.7–1.3MB
~28K SLoC