0
$\begingroup$

For discrete logarithm we can pick a random number $n$ and project it to a subgroup. E.g. given a prime $p$ with
$p-1 = 2\cdot a \cdot b +1$
we can compute
$n^{((p-1)/a)} \equiv n_a \mod p$
after this $n_a$ is an element of a subgroup with size $a$
$(n_a)^a \equiv 1 \mod p$

Is there a way to do something like this for elliptic curves?


Target use case scenario:
1.)random number $r$ is picked
2.)element of elliptic curve $e$ out of $r$ with some function gets computed: $e_r=f(r)$
3.)element which lies in subgroup with size $k$ gets computed: -> $e_{r,k}$ (how?)
4.)repeat 1.-3. for another random number $r$ --> $e'_{r',k}$
target result: A possible attacker who has access to source code and runtime variables should not know how to compute $e'_{r',k}$ out of $e_{r,k}$ with given EC generator $g$.

The subgroup with size $k$ likely (if exists) also has a generator $g_k$. There should be some way to produce $e'_{r',k}$ out of $e_{r,k}$, e.g. with $e'_{r',k} = e_{r,k} \odot g_k^i$. In case multiple subgroups with size $k$ exist which have disjoint elements this only need to be true for elements in same group. The amount of disjoint groups should not be larger than a low number (<1000).

In case that is possible whould it have a significant impact at security?

$\endgroup$
  • $\begingroup$ You might want to explain what you're doing with the use case clearer - I can't figure out what you're trying to accomplish. For example, using my algorithm, both $e_{r,k}$ and $e'_{r', k}$ are both random elements of the subgroup (assuming $f$ is equidistributed), which nothing else tying them together. Why would you expect the attacker to be able to guess a random element $e'_{r',k}$ with no information other than "it's somewhere in the subgroup"? $\endgroup$ – poncho May 10 at 17:26
  • $\begingroup$ "nothing else tying them together"? also no generator for that group? "Why would you expect the attacker to be able to guess a random element" In case finding an element in same subgroup reduces the solving time to subgroup size instead of group size. In use case the attacker and the user are the same. Each ciphertext (here $e_{(r,k}$) is some kind of secret message at the same time. Every user has one and another user should not know how to compute it out of its own and vice versa. $\endgroup$ – J. Doe May 10 at 18:14
3
$\begingroup$

Is there a way to do something like this for elliptic curves?

Of course; if we have an elliptic curve with order $q = a \cdot b$, then we can make an element $H$ into the subgroup of order $a$ by computing $H_a = (q/a)H$. And, we have $a H_a = 0$ (the neutral element) precisely as requested.

Now, we typically don't use elliptic curves with an order with two large prime factors; they are usually selected with an order $q = hr$, where $h$ is a small integer (most often 1, 4 or 8) and $r$ is a large prime. We do this because that makes the ECDLP problem as hard as possible; with your order $q = a \cdot b$, you could compute discrete logs in time $\sqrt{ \max( a, b ) }$, and so we'd have to use a larger elliptic curve that we would otherwise need.

$\endgroup$
  • $\begingroup$ Thanks again. So its about the same problem as with discrete logarithms. Would it be a 2D elliptic curve then? Do exist $b$ groups with size $a$ each then? $\endgroup$ – J. Doe May 10 at 18:27
  • 1
    $\begingroup$ @J.Doe: no, it'd be a single elliptic curve that happens to have a composite order. As for the number of subgroups, as long as $q$ is square-free (that is, does not have an repeated prime factors), then there is guaranteed to be precisely one subgroup for any order $r$ that is a factor of $q$ (and each such subgroup will always have at least 1 generator) $\endgroup$ – poncho May 10 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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