# ECFP harder than ECDLP?

Given two points $P$ and $Q = \sum_{i=1}^{n} x_i.P$ over $E_p(a, b)$ for $x_1,x_2,...,x_n \in \mathbb F_p$. The Elliptic Curve Factorization Problem (ECFP) is to find the points $x_1.P,x_2.P,...,x_n.P$

Is ECFP harder than ECDLP ? Can anyone provide me the proof ?

• Solve the DL problem to get $x$ in $Q=x.P$.
• $Q = \sum_{i=1}^{n} x_i.P = (\sum_{i=1}^{n} x_i).P= x.P$
=> any set of $x_i$ that sums to $x$ (modulo the group order) is a solution to ECFP.
• The question would be rather how it is used and whether you have the correct set of $x_i$ values. I see this similar to how Shamir's Secret Sharing is information-theoretically perfectly secure. – Artjom B. May 4 '16 at 9:08
• @CodesInChaos how will you find the correct set of $x_i$ values ? You will find $x$ by DL problem and then break $x$ into set of $x_i$. So don't you think it is harder than ECDLP ? – Sandy May 4 '16 at 12:06
• @CodesInChaos suppose $x_1 = 2$ and $x_2 = 8$ then $x = 10$. So you have $P$ and $Q = 10.P$. By DL problem we can get back $x = 10$. But how to find $x_1$ and $x_2$ ? – Sandy May 4 '16 at 12:12