.png){kind=icon}
返回
Computing multi-scalar multiplication on memory-constrained devices
.png){kind=icon}
PRE
AI
DOI：10.1007/s13389-026-00393-z.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
多标量乘法是大多数配对基零知识证明中的关键操作。在许多研究中，内存限制常被报道是阻止计算更大规模多标量乘法（MSM）的主要瓶颈。本文特别关注在内存受限设备上加速此操作。Pippenger算法（也称为桶方法）是计算多标量乘法最高效且因此最广泛使用的方法。我们提出了一种Pippenger算法的优化方法，其效率至少不低于原始算法，在内存受限条件下效果显著更优。主要思想是根据可用内存使用自适应数量的桶，而非固定的2(W)-1。我们在BLS12-381曲线上对2(8)至2(14)点的多标量乘法进行了测试。结果表明，在极低内存下我们获得了非常显著的增益（最高达40%），随着内存增加增益逐渐减小，直至内存不再受限时性能与Pippenger算法相当。例如，在2(13)点的多标量乘法中，仅1 KB内存时增益为40%，15 KB时为20%，35 KB时为15%，依此类推，直至内存不再受限时与Pippenger算法等效。
Keyword:
Multi-scalar Multiplication
Pippenger algorithm
Bucket method
zk-SNARK
期刊
J
IF:
1.4
论文数:
19
被引数:
649
机构
引用论文
.png){kind=icon}
cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUscuZK: 在gpu上使用更快的并行多标量乘法算法加速零知识证明
OAAI
OAAI分享收藏
查看更多内容