Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
add comment

1 Answer 1

up vote 5 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 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.

share|improve this answer
add comment

Your Answer

 
discard

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.