1
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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"

$\endgroup$
5
  • $\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$ – user77340 Jan 27 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$ – poncho Jan 27 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$ – Geoffroy Couteau Jan 27 at 21:47
  • $\begingroup$ Some references in case you are interested to read about some applications of composite-order elliptic curves with a pairing: BGN DejaQ $\endgroup$ – Geoffroy Couteau Jan 27 at 21:49
  • $\begingroup$ So the conclusion is? Is there such a trapdoor to solve subgroup membership problem?@Geoffroy Couteau $\endgroup$ – user77340 Jan 28 at 5:17

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.