2
$\begingroup$

I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (\times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product. (btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)

So lets say it's $Z_m \times Z_n \times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)

I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$

It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure. I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?

Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)? Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.

$\endgroup$

1 Answer 1

7
$\begingroup$

Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $\mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $\mathbb{Z}_r \times \mathbb{Z}_r$. This is probably not what you want.

For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $\mathbb{Z}_n$ is cyclic, but it is also isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_q \times \mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.

It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as: $$ uP = ((qr)^{-1} \bmod p)(qrT) $$ but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.

Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $\mathbb{Z}_e$ with $e$ prime and $e = 2 \bmod 3$, the curve $y^2 = x^3 + B$ (for some $B \neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 \bmod 3$, and an integer $g$ such that: $$ 4e - (e+1-n)^2 = 3g^2 $$ then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $\mathbb{Z}_e$ (for constants $B \neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.

In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.

$\endgroup$
2
  • $\begingroup$ So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon $\endgroup$
    – J. Doe
    Jan 18, 2019 at 22:38
  • $\begingroup$ Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user. $\endgroup$
    – J. Doe
    Jan 18, 2019 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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