Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?
share|improve this question
    
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 at 23:09

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.