Join Log in
Score:5
mactep Cheng avatar Crypto

How to decide if a point on a elliptic curve belongs to a group generated by a generator g?

za flag
mactep Cheng

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?

712
0 + 0
kelalaka avatar
in flag
kelalaka
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.
0
Reply
Ievgeni avatar
cn flag
Ievgeni
@kelalaka How could you be sure than there is no group of same order which are distinct?
2
Reply
kelalaka avatar
in flag
kelalaka
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.
0
Reply
Fractalice avatar
in flag
Fractalice
@kelalaka you can have two independent groups of the same size on the same curve
1
Reply
kelalaka avatar
in flag
kelalaka
@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.
0
Reply
Score:8
kelalaka avatar Crypto
in flag
kelalaka

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.

0 + 0
dave_thompson_085 avatar
cn flag
dave_thompson_085
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.
1
Reply
Meir Maor avatar
in flag
Meir Maor
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.
0
Reply
Score:5
Ievgeni avatar Crypto
cn flag
Ievgeni

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

0 + 0
Score:0
mactep Cheng avatar Crypto
za flag
mactep Cheng

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$

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.