Given a EC with cardinality $C=P^3+c$ with $P$ a prime $P \approx \sqrt[3]{C}$ and $c>0$. Out of a given generator $G$ we generate two additional generator $F,H$ with $$F = P \cdot G$$ $$H = P^2 \cdot G$$

(all would still generate a sequence of length $P^3+c$)
Given now a random member $M_1$ of that EC we can generate a $P\times P \times P$ cube of different members with $$ M_1 +i\cdot G+j\cdot F+k\cdot H = V_{M_1ijk}$$ $$ i,j,k \in [0,P-1]$$ $$|\{V_{M_1ijk}\}| = P^3$$

Every other random member $M_2$ can be produced out of $M_1$ with: $$M_2 = M_1+i\cdot G+j\cdot F+k\cdot H $$ $$ i,j,k \in [0,P]$$

Given now two random members $M_1,M_2 $ how many steps are needed to find the related $i,j,k$ (on average time)? How would that work?
Would it be (much) safer if we pick $P = 2\cdot p+1$ with $p$ a prime?
Would it be (much) safer if we pick three (secret) prime factors $P_1,P_2,P_3$ instead? with $P_1 \cdot P_2 \cdot P_3 \approx C$

(I'm looking for rough estimates related to $C,P$ in ($O$-notation). We can e.g. ignore the different bit-length-related impact at 2 number multiplication )

The adversary does know about the used EC, the generators $G,F,H$ and their inverses $G^{-1},F^{-1},H^{-1}$, the random members $M_1,M_2$ and the internal structure. He does not know about $P,d$ but as there are not too many options we assume he does know this as well.
He want to find unknown $i,j,k$ for random known $M_1,M_2$.

Side-question: Are there any restrictions of safe EC which can be used for this? E.g. would M-221 with $y^2 = x^3+117050x^2+x$ $\bmod p = 2^{221} - 3$ work for this?

If we just have a single generator $G$ it should take $O(\sqrt{C})$ using baby-step-giant-step. If $P$ is known $i,j,k$ can be constructed out of this.
With $F,H$ we could do a surface around $M_1$ and a straight line with $G$ at $M_2$ until an intersection of those. This would take $O(P^2+P)\rightarrow O(P^2)$ which would be larger than $O(\sqrt{C})=O(P\sqrt{P})$. So $F,H$ no help here.
Could those generators $F,H$ help to make it somehow faster?


1 Answer 1


Given now two random members $M_1, M_2$ how many steps are needed to find the related $i,j,k$ (on average time)?

The problem of finding $i, j, k$ is equivalent to the discrete log problem:

  • If you can solve the discrete log problem, you can compute $i, j, k$ (by computing the discrete log of $M_2 - M_1$, and then expressing that discrete log in base $P$)

  • If you can compute $i, j, k$, you can solve the discrete log problem (to compute the discrete log of a point M, you would pick an arbitrary point $M_1$, set $M_2 = M + M_1$, compute $i, j, k$; then, the discrete log of $M$ is $i + jP + kP^2$

For a curve with no known weaknesses, computing the discrete log is believed to take $O(\sqrt{C})$ time; if you select a curve with known weaknesses (e.g. a pairing friendly curve that has a pairing operation into a finite field where the discrete log is easier), then the time to solve your problem also drops accordingly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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