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.

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??

share|improve this question
    
$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) –  CodesInChaos Aug 5 '13 at 7:18
    
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. –  HareshKannan Aug 5 '13 at 10:54
    
@HareshKannan This kind of verification is only possible when you choose a curve with an efficiently computable pairing. –  minar Aug 5 '13 at 13:11
    
@minar Problem is that am trying to bring out without using pairing. –  HareshKannan Aug 6 '13 at 3:01
add comment

2 Answers

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.

share|improve this answer
add comment

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.

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.