Mapping points between elliptic curves and the integers

My primary question is:

• Is there an easy way to create a bijective mapping from points on an elliptic curve E (over a finite field) to the integers (desirably to $\mathbb{Z}^*_q$ where $q$ is the order of E)?

To phrase it a second way, given a point on the curve that is chosen with uniform randomness, can you translate it into a uniformly random integer in some interval (or group)? I'm also interested in mappings that are statistically close to uniform.

(I thought of using a random extractor, but this generally requires 2m bits of min-entropy in the input to produce m bits of near-uniform randomness)

I was reminded of this question when reading the Telex paper, where they encounter this issue. Their solution is to use two specially selected curves, a curve and its twist, and only map the x-coordinate.

Secondary questions:

• Using a curve and twist, is there a way to use the y-coordinate to select which curve so that the mapping is one-to-one?
• If there is an approach, does it also work with pairing-friendly curves?
-
You mean to ask for a mapping that is easy to calculate in both directions, right? $F(x)=xG$, where $G$ is a generator point and $0 <= x < order(E)$, is bijective but it's only easily calculated in one direction. – Brock Hansen Mar 11 '14 at 23:09
Isn't this the whole premise of Elligator and, more generally, Elligator-Squared? When the curve meets specific criteria the mapping is complete, notably when q mod 4 = 1. – DBM Jul 11 '15 at 2:36

I do not know of any general way to create the mapping you want (and if there was, it might turn into an efficient point-counting algorithm, which would be great), but you can do this on some curves.

Consider a prime $p$ equal to $2$ modulo $3$. In $\mathbb{Z}_p$, every value has a single cube root (because $3$ is then invertible modulo $p-1$). Then, look at the curve $y^2 = x^3+1$. For any value of $y$, $y^2-1$ has a unique cube root $x$, so there is a one-to-one mapping between non-infinity points on that curve and their $y$ coordinate in $\mathbb{Z}_p$. For completeness, map the "point at infinity" to the integer $p$, and you are all set: an easy bijective mapping between the $p+1$ curve elements, and the integers modulo $p+1$.

Moreover, this curve is pairing-friendly, with an embedding degree of only $2$ (because $p+1$ divides $p^2-1$). It also allows a distortion map so that you can have a symmetric pairing: if $\mu$ is a cubic root of $1$ distinct from $1$ (so an element of $GF(p^2)$, the field extension), then the mapping $m$ from $(x,y)$ to $(\mu x,y)$ is a morphism over the curve. Then you can define a pairing $e(P, Q)$, where $P$ and $Q$ are both points on the original curve (in $\mathbb{Z}_p$) as the Tate (or Weil) pairing computed over $P$ and $m(Q)$. This allows you to stay on the base curve as much as possible; only the pairing output will need the field extension.

Ben Lynn shows some details in his PhD dissertation (he calls that curve a "type B"). Note that since there is a pairing of embedded degree $2$, then discrete logarithm on the curve is "reduced" to discrete logarithm in the $GF(p^2)$ field; so, for proper security, $p$ must be at least 512-bit long.

Edit: A similar trick works for "type A" curves with equation $y^2 = x^3 + ax$ in $\mathbb{Z}_p$ for $p = 3 \mod 4$ and a constant $a$. For a given $x$, then exactly one of the three following situations occurs:

• There are two distinct values $y$ such that $(x, y)$ is a valid point, and they are opposite of each other, so one is lower than $p/2$ and one is greater.

• There is no valid $(x, y)$ point, but there are two valid $(-x, y)$ points for two distinct values of $y$.

• $(x, 0)$ is a valid point, and so is $(-x, 0)$ (this one can happen only if $-a$ is a square modulo $p$).

So you can map the point $(x, y)$ to:

• $x$ if $1\leq y \lt p/2$
• $-x$ if $p/2 \lt y \lt p$
• $x$ if $y = 0$

Then map the point of infinity to $p$, and you're done.

-
Thanks! This is useful. Hopefully accepting this answer won't discourage other answers for other types of curves (e.g. ones that are not supersingular—Telex for example relies on DDH.) – PulpSpy Aug 4 '11 at 1:04
This is probably a silly question, but doesn't regular point compression almost do this? Granted, the output is not in $Z_p$, but it's guaranteed to be in $Z/(2p+1)Z$. – Samuel Neves Sep 9 '11 at 16:53
@Samuel: Point compression is not bijective: from a point $(x, y)$, you get $(x, b)$ where $b$ is a single bit, but not all pairs $(x, b)$ are the compression of a valid curve point. The difficulty in this question is to have a mapping to modular integers where every modular integer value can be mapped back. – Thomas Pornin Sep 9 '11 at 19:13