Some remarks on how to hash faster onto elliptic curves

Some remarks on how to hash faster onto elliptic curves

18 March 2024 | Dmitrii Koshelev
This article proposes four optimizations for hashing onto elliptic curves over finite fields \(\mathbb{F}_q\). The first optimization is for elliptic curves without non-trivial automorphisms, provided \(q \equiv 2 \ (\text{mod} \ 3)\). The second optimization is for \(q \equiv 2, 4 \ (\text{mod} \ 7)\) and an elliptic curve \(E_7\) with a specific \(j\)-invariant. The third and fourth optimizations focus on pairing-friendly curves, particularly the subgroups \(\mathbb{G}_1\) and \(\mathbb{G}_2\). These optimizations reduce the number of required exponentiations and eliminate the need for direct hashing onto \(\mathbb{G}_1\) in certain scenarios, significantly improving performance. The article also discusses the application of these optimizations to popular curves like BLS12-381 and NIST SP 800-186, and provides a taxonomy of state-of-the-art hash functions for elliptic curves. Additionally, it explores hashing over highly 2-adic fields \(\mathbb{F}_q\). The author emphasizes the importance of clearing cofactors and the practical implications of these optimizations in real-world cryptographic protocols, such as aggregate BLS signatures.This article proposes four optimizations for hashing onto elliptic curves over finite fields \(\mathbb{F}_q\). The first optimization is for elliptic curves without non-trivial automorphisms, provided \(q \equiv 2 \ (\text{mod} \ 3)\). The second optimization is for \(q \equiv 2, 4 \ (\text{mod} \ 7)\) and an elliptic curve \(E_7\) with a specific \(j\)-invariant. The third and fourth optimizations focus on pairing-friendly curves, particularly the subgroups \(\mathbb{G}_1\) and \(\mathbb{G}_2\). These optimizations reduce the number of required exponentiations and eliminate the need for direct hashing onto \(\mathbb{G}_1\) in certain scenarios, significantly improving performance. The article also discusses the application of these optimizations to popular curves like BLS12-381 and NIST SP 800-186, and provides a taxonomy of state-of-the-art hash functions for elliptic curves. Additionally, it explores hashing over highly 2-adic fields \(\mathbb{F}_q\). The author emphasizes the importance of clearing cofactors and the practical implications of these optimizations in real-world cryptographic protocols, such as aggregate BLS signatures.
Reach us at info@study.space