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 .