Is the Representation Problem hard on elliptic curves?

Question

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?

Answer 1

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₁, r₂,... r_n modulo 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₁r₁ + a₂r₂ + ... + a_nr_n mod q.

Since discrete logarithm is hard in elliptic curves, so must be RP.