#离散 #对数 #等式 #证明 #曲线 #实验性 #跨曲线

无std dleq

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

8个不稳定版本 (3个破坏性)

0.4.1 2023年8月8日
0.4.0 2023年8月8日
0.3.1 2023年3月21日
0.2.0 2022年11月11日
0.0.0 2021年3月6日

#271 in 密码学

24 每月下载量
用于 5 个crate (3直接)

MIT 许可证

88KB
2K SLoC

离散对数等式

实现了使用ff/group实现的曲线的离散对数等式证明。

还有一个高度实验性的跨组DLEq证明,位于experimental特性下,尚未提供正式证明,但在此处可用。

除了experimental特性外,该库于2023年3月由Cypher Stack进行了审核,最终提交为669d2dbffc1dafb82a09d9419ea182667115df06。后续的任何更改都没有经过审核。

跨组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.8–1.8MB
~37K SLoC