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?
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.