Faster CGL Hash Function via Reduced Backtracking Checks

Inoue, Shota

doi:10.1587/transfun.2025CIP0002

Faster CGL Hash Function via Reduced Backtracking Checks

2026-03-01

0

PRE

AI

DOI：10.1587/transfun.2025CIP0002

原文链接

原文求助

摘要

En 中文

CGL哈希函数是一种基于同态的哈希函数，通过计算超奇异同态图上的非回溯路径来工作。由于CGL哈希函数的一个问题是其相对较慢的计算时间，许多加速方法已被研究，包括使用勒让德形式和根同态。在SAC'22上提出的计算CGL哈希函数的算法通过使用整数n = (R)(logp)（其中p是基础域的特征）的2n-同态，实现了几个数量级的加速。在该算法中，为确保哈希函数的安全性，必须阻止两个连续2n-同态之间的回溯2-同态，这称为回溯检查。在本文中，我们提出了两种算法，通过减少回溯检查的开销来进一步加速计算。第一种算法在不必要时跳过回溯检查，第二种算法完全消除了这些检查的必要性。此外，我们实现了我们提出的算法。我们对我们的算法以及先前提出的算法进行了详细而精确的复杂度分析，通过程序化地计算基础有限域上的实际操作次数。我们证明，对于256、512、1024、1536位素数，第一种算法相比SAC'22的原算法降低了7.6%、7.0%、7.6%、6.2%的成本，第二种算法降低了18.9%、17.8%、16.7%、16.1%。本文是[1]的扩展版本。我们添加了无需回溯检查的第二种算法，该算法比第一种算法更快，并通过实现证明了其效率。

Keyword:

post-quantum cryptography

isogeny-based cryptography

CGL hash function

Montgomery curve

Faster CGL Hash Function via Reduced Backtracking Checks

摘要

期刊

机构

引用论文