2
$\begingroup$

I would like to know how to compute multiplication of two valid EC points over a curve E with generator G.

i.e. Given only P and Q points then how to compute R = P * Q

where $P = p G$, $Q = q G$ and $R = (p \cdot q)G$.

$\endgroup$
7
  • $\begingroup$ @CodesInChaos, the output R is a EC point. If integers p and q are given then R = pG * qG = (p*q)G can be computed but here only points P and Q given. $\endgroup$
    – user25573
    Jul 12 '15 at 15:55
  • $\begingroup$ AFAIK, you can only multiply one point by an integer or add two points. Meaning that $P=pG$ is possible, but $R=PQ$ isn't. Did you mean $R=P+Q$? Or could you maybe mention the context of your question? (ECDSA?) $\endgroup$
    – SEJPM
    Jul 12 '15 at 15:57
  • $\begingroup$ @SEJPM, No. I mean R = P*Q (there is no specific context just I am exploring) $\endgroup$
    – user25573
    Jul 12 '15 at 16:01
  • $\begingroup$ ... and please note $R=pG * qG = (pq)G^2 \neq (pq)G$ $\endgroup$
    – SEJPM
    Jul 12 '15 at 16:04
  • $\begingroup$ @CodesInChaos, there is no specific context but it is a doubt I got. $\endgroup$
    – user25573
    Jul 12 '15 at 16:05
1
$\begingroup$

There is no standard "multiply two group elements" operation in an additive group. So you first need to define what you mean by $P*Q$. From the comments I gather that you want $P*Q = q P = p Q = (p \cdot q) G$.

The computational Diffie-Hellman (CDH) problem is:

Given $P=pG$ and $Q=qG$ compute $(p\cdot q)G$.

which is clearly equivalent to your problem.

If the discrete logarithm (DL) problem is easy for the group, you can first solve $P=pG$ for $p$ and then compute $P*Q=pQ$. But on the curves we use in cryptography both DL and CDH are believed to be hard. While such groups may exist, I'm not aware of any groups in which DL is hard but CDH is easy.

Another problem of interest is the decisional Diffie-Hellman problem:

Given three group elements $P=pG$ and $Q=qG$ and $R$ decide if $R = (p \cdot q) G$.

There are some curves for which the decisional Diffie-Hellman problem is easy while the computation Diffie-Hellman problem and the discrete logarithm problem are hard. These groups are know as gap-groups and are useful in cryptography, for example they're used in the BLS signature scheme.

$\endgroup$
0
0
$\begingroup$

Well the equation $R = P * Q$ simply isn't possible on an elliptic curve. The group of points on the EC is an additive group. Meaning it is only possible to compute $P + Q$ or $[m] P$ for some integer m. Taken $P=p \cdot G$ and $Q=q \cdot G$ you already got the answer yourself: $R=(p \cdot q)G$. Simply add the point $G$ to itself $(p \cdot q)$-times.

$\endgroup$
4
  • $\begingroup$ You mean to say that given only points P and Q it is not possible to compute R = P*Q $\endgroup$
    – user25573
    Jul 12 '15 at 16:18
  • $\begingroup$ @user25573 "Well the equation R=P∗Q simply isn't possible on an elliptic curve. The group of points on the EC is an additive group." This means that R=P*Q usually isn't defined on elliptic curves. $\endgroup$
    – SEJPM
    Jul 12 '15 at 16:20
  • 1
    $\begingroup$ The OP can define $*$ to mean whatever they want it to mean. They chose to define it as the solution of the CDH problem. $\endgroup$ Jul 12 '15 at 16:20
  • $\begingroup$ @CodesInChaos, so computing "$R=PQ=(pq)G$" would involve solving the EC-CDH / EC-DLP? That would imply that the operation may be infeasible... $\endgroup$
    – SEJPM
    Jul 12 '15 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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