Welcome to the resource topic for 2023/121
Title:
Hashing to elliptic curves over highly 2-adic fields \mathbb{F}_{\!q} with O(\log(q)) operations in \mathbb{F}_{\!q}
Authors: Dmitrii Koshelev
Abstract:The current article provides a new deterministic hash function \mathcal{H} to almost any elliptic curve E over a finite field \mathbb{F}_{\!q}, having an \mathbb{F}_{\!q}-isogeny of degree 3. Since \mathcal{H} just has to compute a certain Lucas sequence element, its complexity always equals O(\log(q)) operations in \mathbb{F}_{\!q} with a small constant hidden in O. In comparison, whenever q \equiv 1 \ (\mathrm{mod} \ 3), almost all previous hash functions need to extract at least one square root in \mathbb{F}_{\!q}. Over the field \mathbb{F}_{\!q} of 2-adicity \nu this amounts to O(\log(q) + \nu^2) operations in \mathbb{F}_{\!q} for the Tonelli–Shanks algorithm and O(\log(q) + \nu^{3/2}) ones for the recent Sarkar algorithm. A detailed analysis shows that \mathcal{H} is several times faster than earlier state-of-the-art hash functions to the curve NIST P-224 (for which \nu = 96) from the American standard NIST SP 800-186.
ePrint: https://eprint.iacr.org/2023/121
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .