5
$\begingroup$

In the elliptic curve encryption scheme, there is a cyclic group generated by a base point $G$ on the elliptic curve.

Given a random point on the elliptic curve, is there a way to decide if the random point is in the group or not?

$\endgroup$
5
  • $\begingroup$ If you know the order of the subgroup including the full group check $[k]G$. If equal to the identify element then it is on this group. Note that an element can be a member of more than one subgroup. $\endgroup$
    – kelalaka
    Oct 25, 2021 at 9:41
  • 2
    $\begingroup$ @kelalaka How could you be sure than there is no group of same order which are distinct? $\endgroup$
    – Ievgeni
    Oct 25, 2021 at 10:01
  • $\begingroup$ In genera, in ECC we want small cofactor die to the ladder, and some even prime curves. The question is about ECC, could you name one standard curve that have two large subgroup that has the same order? For small orders, it is easy to check, too. $\endgroup$
    – kelalaka
    Oct 25, 2021 at 10:08
  • 1
    $\begingroup$ @kelalaka you can have two independent groups of the same size on the same curve $\endgroup$
    – Fractalice
    Oct 25, 2021 at 11:04
  • $\begingroup$ @Fractalice Yes, could you name one EC that we use in ECC ( OP asking ECC schemes), that we have to large $k$ such that $k^i| n$, where $i>1$ and $k$ is a large number so that the computationally bounded adversary cannot solve DLog. $\endgroup$
    – kelalaka
    Oct 25, 2021 at 11:40

3 Answers 3

8
$\begingroup$

The answer really depends on the Cryptographic Elliptic Curves that we know!

  1. Prime order Cryptographic EC: Since the order of the subgroup generated by an element must divide the order, then there is the full group and the group of $\mathcal{O}$ of order $1$ ( NIST P curves P-192, P-224, P-256, P-384, P-521) curves has prime order listed in NIST.FIPS.186-4 and taken from Sec1).

  2. Cryptographic EC with a small factor: In Cryptography the curves have large order to be safe and we have to choose the base element from the largest subgroup. This is due to the

    1. Protecting from Pohlig-Hellman Algorithm that reduces the time to the largest factor and is very efficient when order is smooth i.e. all factors are small.

    2. To have a birational Montogmery equivalent of the curve like Curve25519 with cofactor $8$ and Ed448-Goldilocks with cofactor $4$. In this case, we have orders for the subgroups like; $2,4,8,p,2p,4p,8p$ (for Curve25519)*

      To see that a point $G$ is of order $2$ or $p$ is easy, check $2[G]$ or $[p]G$, if the result is identity, then they are in this group. They but they are also in the subgroup that contains the subgroups. There are elements in the subgroup of order $2p$ but not in the subgroup of order $2$ or $p$. Check $[2]G$ and $[p]G$ if they are not identity but $[2p]G$ is then it is on the subgroup of order $2p$.

      The Klein group is the smallest group that has two subgroups of order 2, it is isomorphic to $\mathbb Z_2 \times \mathbb Z_2$. This is may help to understand that the two different subgroups can have the same order.

      The NIST B curves have cofactor 2, and K curves have 4, and they are taken from Sec2.

  3. Twist of the Cryptographic EC: The twist of the well-known curves doesn't have a large quadratic factor, the same applies as in case 2.

  4. Random curve: I've no idea about the expected size of factors of randomly generated curves (seen some works). We can have a curve with an order such that it has a large factor of order 2 or more. In this case, the $[p]G$ will not reveal the subgroup membership. To solve it we need to find a generator for each of the subgroups and try to solve the DLog.

  5. Factorization of the order of the group is not known: In this case, we have a subgroup decision problem (as stated in the other answer)

    Given $(n, G, G1, e)$ and an element $x \in G$, output $1$ if the order of $x$ is $q_1$ and output $0$ otherwise; That is, without knowing the factorization of the group order $n$, decide if an element $x$ is in a subgroup of $G$. We refer to this problem as the subgroup decision problem

    While this problem sets interesting results in its context, this is not related to the Elliptic Curves used in ECDH, EdDSA, etc. In the elliptic curves, all parameters are public. Even if you don't provide the factorization of the order of the curve ( not clear how are you gonna sell your curve to the community) one can factor around 829 bits ( 512-bit has achieved around 20 years ego).

    If you consider curves in very large order we can say there is not much meaning of curve order larger than 512 bits ( even 256), since once the Shor's algorithm is set in Cryptographic Quantum Computer for 256-bit curves, it is a matter of time researchers will break the other. This can be seen from the table of Proos and Zalks's work

enter image description here

The post-quantum ECC, on the other hand, uses jumping on the isogenies instead of DH and this paper provides a good introduction to whoever wants to learn.

In the end, the only problematics cases are not cryptographic curves.


* There we used the Lagrange Theorem on Group theory;

  • If $H$ is a subgroup of a group $G$ then $ord(H) \mid ord(G)$

One should note that we used the reverse of the theorem, if $x|org(G)$ then there is a subgroup of order $x$. This is not always true, and alternating group of degree 4 $A_4$ is the smallest example.

$\endgroup$
2
  • 1
    $\begingroup$ Nit: NIST curves over $F_p$ taken from X9/SECG (P-#) which are widely used have prime order (cofactor 1); curves over $F_{2^m}$ (B-# and K-#) which almost noone uses have cofactor 2 or 4. Still-in-draft SP800-186 adds Curve25519 and Curve448 (in Montgomery, Edwards and Weierstrass forms!) which as you noted are 8 and 4, and the Brainpool P# curves also 1. $\endgroup$ Dec 7, 2021 at 0:24
  • $\begingroup$ I don't follow the claim in 4. Are you saying in such a setup finding membership is as hard as DLOG? That seems like a strong statement, if you can give an outline of a proof it would be great. $\endgroup$
    – Meir Maor
    Dec 12, 2021 at 6:13
5
$\begingroup$

In general no. For some specific instances, (if $\mathbb{G}$ is of order $q_1 q_2$ and $g$ of order $q_1$ with $q_1, q_2$ two big primes) the problem is even considered enough hard to be used as a cryptographic assumption called the subgroup decision assumption.

You can look more details in this paper.

But it could be different if you have some supply information. Let suppose you know the order $q_1$ of the generator $g$, and the order of the whole group $q_1 q_2$ (with $q_1, q_2$ two coprime numbers).

You can decide if $G'$ is in the group generated by $g$ by looking if $[q_1]G^{\prime}=0$.

$\endgroup$
0
0
$\begingroup$

For the case, the order of the generator $G$ is $q$, and the order of the whole group is $q\cdot m$, where $\gcd(q,m)=1$.

As long as $m$ is not too large, specifically $m<q+1$, according to the Sylow Theorem, there is only one subgroup of order $q$. So one can decide if a point $G'$ is in the group by looking if $q\cdot G'=0$

$\endgroup$

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.