Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The RP in ECC would be to find $a_1,\ldots,a_n$ (integers) given $P$ and $Q_1,\ldots,Q_n$ (points in the EC) such that $P = a_1 \cdot Q_1 + \ldots + a_n \cdot Q_n$.
Is it hard when DH-like assumption holds in the EC? Is is hard in secp256k1 or Curve25519?
If RP is easy, then so is discrete logarithm.
Assume that you have a way to easily solve the RP for a given $n$. Now I give you $G$ and $P$ on the curve (of size $q$), and I want you to find $x$ such that $P = xG$. What you do is the following: you generate random integers $r_1, r_2, \cdots, r_n \mod q$, and compute $Q_i = r_iG$ for all $i$ from $1$ to $n$. Then you solve RP for P relatively to those $Q_i$, yielding the $a_i$. You then get $x = a_1r_1 + a_2r_2 + \cdots + a_nr_n \mod q$.
Since discrete logarithm is hard in elliptic curves, so must be RP.
