Comprehensive Analysis and Implementation of Isogeny-Based Hash Functions

Abstract

This paper analyzes the security and performance of the isogeny-based hash functions. The isogeny-based hash function was first proposed by Charles, Goren, and Lauter, and is referred to as the CGL hash function. However, Lauter and Petit demonstrated that a collision could be found if the endomorphism ring of the starting curve is known. Subsequently, isogeny hash functions that mitigate the Lauter-Petit attack have been proposed. This paper analyzes three methods that counter the Lauter-Petit attack: the methods proposed by Panny, Zaman and Min, and Larsson. In particular, we propose a new isogeny-based hash function SHH, which exploits Panny’s method with Hessian curves. We then analyze the security and performance of the proposed SHH along with the methods by Zaman and Min (SCH) and Larsson (SLH). More specifically, the security was analyzed in the context of the Lauter-Petit attack, collision resistance, and fault tolerance. The analysis in this paper shows that all three algorithms can counter the Lauter-Petit attack. However, for SCH, we demonstrated that collision pairs could be found with carelessly chosen parameters. This paper also provides guidelines for selecting parameters to make SCH collision-resistant. From a fault-tolerance perspective, SCH and SLH are not fault-tolerant. We also present the results of implementing the three algorithms in SageMath. The implementation results show that at the 128-bit security level, hashing a 256-bit message takes 0.130s for SCH, 0.125s for projective-SLH, and 0.162s for SHH. As can be seen from the implementation results, projective-SLH is the most efficient, while SHH performs slower due to the use of a larger finite field.

Keywords

• Supersingular isogeny
• provably secure hash
• post-quantum cryptography