Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 7 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.