# Is the Representation Problem hard on elliptic curves?

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 r1, r2,... rn modulo q, and compute Qi = riG for all i from 1 to n. Then you solve RP for P relatively to those Qi, yielding the ai. You then get x = a1r1 + a2r2 + ... + anrn mod q.

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

-