Impossibility of Surjective Icart-Like Encodings

Many cryptographic protocols based on elliptic curves rely on the possibility of representing integer values or bit strings as elliptic curve points, or vice versa, in an invertible way. The most practical approach proposed to achieve this for an elliptic curve

$E/\mathbb{F}\/_q$

has been the use of (piecewise) algebraic maps

$f\colon \mathbb{F}\/_q\to E(\mathbb{F}\/_q)$

called (deterministic, constant-time) “encoding functions”, for which numerous constructions have been proposed in recent years, starting with the very simple encoding of Boneh and Franklin (CRYPTO 2001), which maps a value

$u\in\mathbb{F}\/_q$

to

$\big((u^2-b)^{1/3}, u\big)$

on the elliptic curve

E

 :

y

2

 = 

x

3

 + 

b

over

$\mathbb{F}\/_q$

,

$q\equiv2\bmod 3$

. That encoding is almost a bijection between

$\mathbb{F}\/_q$

and

$E(\mathbb{F}\/_q)$

, which makes it very convenient for security proofs, as well as for applications like covertness, but it is only defined for a very limited class of elliptic curves, all of them supersingular, and hence quite inefficient.

Since then, many other encoding functions have been proposed, and constructions are known for all elliptic curves. They fit into two broad families: Icart-like encodings, which are generalizations of the original Boneh–Franklin encoding starting with a construction due to Icart (CRYTPO 2009), and SWU-like encodings, related to the Shallue–van de Woestijne construction (ANTS 2006). So far, however, almost none of these numerous encodings has replicated the very useful bijectivity property of the Boneh–Franklin encoding.

In this paper, we focus on Icart-like encodings, and investigate the possibility of constructing such encodings

$f\colon \mathbb{F}\/_q\to E(\mathbb{F}\/_q)$

that are almost bijective like Boneh and Franklin’s, or achieve a weaker property like “almost surjectivity” (in the sense that

$\#f(\mathbb{F}\/_q) = q + o(q)$

). And we show that the lack of such constructions is no wonder: almost surjective Icart-like encoding cannot exist to non-supersingular elliptic curves.