I have an elliptic curve defined over finite field where $S_1=aP$ . Is it valid to say that $S_1P$ can also be computed. $P$ is the generator of the group. What my real question is that. Should '$a$' be always an integer or can it be a group element itself??

  • $\begingroup$ $a$ needs to be an integer (which can be reduced modulo the curve order). There is no operation that multiplies two curve points, and dividing two curve points is prohibitively expensive (requires computing the discrete logarithm) $\endgroup$ – CodesInChaos Aug 5 '13 at 7:18
  • $\begingroup$ I am working with discrete logarithm problem. Currently am constructing a signature scheme where one of my signature component is in terms of like $S_1=aP$ and the verification algorithm so far which I have come out with has $S_1P=$some value. Is that possible(Since $S_1$ will be a group element) or in case if you have faced any such moments, do you have any idea about it's alternative solution. $\endgroup$ – HareshKannan Aug 5 '13 at 10:54
  • $\begingroup$ @HareshKannan This kind of verification is only possible when you choose a curve with an efficiently computable pairing. $\endgroup$ – minar Aug 5 '13 at 13:11
  • $\begingroup$ @minar Problem is that am trying to bring out without using pairing. $\endgroup$ – HareshKannan Aug 6 '13 at 3:01

Should '$a$' be always an integer or can it be a group element itself??

Well, $aP$ is defined to be:

$aP \equiv \underbrace{P + P + \ldots + P}_\text{a times}$

From that definition, we see that this makes sense only if $a$ is an integer; it needs to be a count of the number of $P$'s to add together.

| improve this answer | |

In ECC you have two distinct types, group elements and scalars.

With group elements you can:

  • Add two points $A+B$
  • Negate a point $-A$ (together with addition this allows subtraction $A+(-B)=A-B$
  • Multiply a point with a scalar $a B$
  • Theoretically you can divide to points to obtain a scalar $s = A/B$. But on secure curves this is too expensive, since computing $s$ is equivalent to solving the discrete logarithm problem on the curve.

But multiplying two group elements is not possible. This isn't merely expensive, there isn't even a definition that says what the result should be. If it were defined, it'd be a completely separate operation.

One interesting operation is the decisional Diffie-Hellman problem, where you're given $A, B, S$ and generator $G$ with $A=aG$ and $B=bG$ it is possible to check if $S$ is equal to $abG$. This operation is usually difficult, but there are some curves where a pairing allows efficient checking of this condition. On these curves you can use the BLS signature scheme.

With scalars you can use all operations possible in modular arithmetic modulo the order, including addition, subtraction, multiplication, division,... With non-prime multiplication is lossy and thus not invertible and division doesn't have a unique result but is still cheap to compute.

| improve this answer | |

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.