Given an elliptic curve $E$ over a finite field q(q is a prime), and $<G>$, the cyclic subgroup of $E$, where G is the generator. Is there any trapdoor $T$, that given a random group element $P\in E$, we can decide if $P\in <G>$ in probabilistic polynomial time with the help of $T$?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Here is one (somewhat impractical) possibility:
We pick an Elliptic Curve that has a group size $n$ that is a secret factorization $n = pr$ (I'd say $pq$, except you already gave a separate meaning to $q$)
As our generator $G$, we pick an element of order $p$.
The trapdoor information is the value $p$
It would appear to be a hard problem to determine whether a random element $P$ is in the subgroup $<G>$; however with the knowledge of $p$, we can compute $pP$; that will be the null element iff $P$ is in the subgroup.
Now, $n$ has to be large enough for factorization to be infeasible (as anyone looking at the elliptic curve can run a point counting algorithm to obtain $n$); that means that $q$ (the prime the curve is based on) must be 2048 bits (or larger); hence computations on this curve will be expensive. It also begs the question "why are you using an elliptic curve at all, rather than (say) the group of quadratic residues in $\mathbb{Z}_{2pr+1}^*$ with $2pr+1$ prime"
-
$\begingroup$ Thanks for your answer. But in the elliptic curve, the number of group elements in the p-torsion group is p^2, which means you can not simply verify if pP=O, and justify P is in the <G> if the answer is yes. There are p^2-p group elements outside the <G> which times p also equals to O. This conclusion is refered in Corollary 6.4 in page 86,《The Arithmetic of Elliptic Curves》, Joseph H. Silverman $\endgroup$– Eric_QinCommented Jan 27, 2021 at 3:32
-
$\begingroup$ @user77340: actually, if the total number of points is in the form $pq$, then the group is isomorphic to $\mathbb{Z}/pq$ (as that's the only finite abelean group of that size), hence that test does work in that case. Now, I did consider a group size of $p^2$ (where that test does not work), however I could not think of a usable trap door (perhaps you could do something with a pairing operation; nothing came to my mind...) $\endgroup$– ponchoCommented Jan 27, 2021 at 4:05
-
$\begingroup$ About your last question, hard subgroup membership problems over elliptic curves (based exactly on your description, where the order is a hard to factor modulus) have been used quite a lot in pairing-based cryptography. Subgroup membership hardness + pairing gives a nice tool which combines both strong structures and a hard problem with an associated trapdoor. This was used for example for the Boneh-Goh-Nissim degree-2 homomorphic encryption scheme, or for some identity-based encryption schemes. Of course, while this shows feasibility for cool primitives, the schemes are quite inefficient. $\endgroup$ Commented Jan 27, 2021 at 21:47
-
-
$\begingroup$ So the conclusion is? Is there such a trapdoor to solve subgroup membership problem?@Geoffroy Couteau $\endgroup$– Eric_QinCommented Jan 28, 2021 at 5:17