Join Log in
Score:0
J. Doe avatar Crypto

EC cardinality $P^3+c$ with 3 gen $G$, $F = P\cdot G,H=P^2\cdot G$ and 2 random members $M_1+iG+jF+kH=M_2$. How long would it take to find $i,j,k$?

at flag
J. Doe

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

Question:
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?

Trial:
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?

27
0 + 0
Score:1
poncho avatar Crypto
my flag
poncho

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.

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.