Paper 2024/085

Simultaneously simple universal and indifferentiable hashing to elliptic curves

Abstract

The present article explains how to generalize the hash function SwiftEC (in an elementary quasi-unified way) to any elliptic curve $E$ over any finite field ${\mathbb{F}}_q$ of characteristic $>3$. The new result apparently brings the theory of hash functions onto elliptic curves to its logical conclusion. To be more precise, this article provides compact formulas that define a hash function $\{0,1{\}}^{\ast }\to E({\mathbb{F}}_q)$ (deterministic and indifferentible from a random oracle) with the same working principle as SwiftEC. In particular, both of them equally compute only one square root in ${\mathbb{F}}_q$ (in addition to two cheap Legendre symbols). However, the new hash function is valid with much more liberal conditions than SwiftEC, namely when $3\mid q-1$. Since in the opposite case $3\mid q-2$ there are already indifferentiable constant-time hash functions to $E$ with the cost of one root in $$, this case is not processed in the article. If desired, its approach nonetheless allows to easily do that mutatis mutandis.