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 just started studying Elliptic Curve Cryptography, and I have this doubt. In ECC the group operation is addition (and not multiplication). So, why is ECDLP stated as a variation of the discrete log problem? Wouldn't "discrete multiplier problem" or "discrete factor problem" be more apt?

share|improve this question
4  
Mathematicians don't care how you call the basic operation. We commonly call it addition, but calling it multiplication is just as valid. –  CodesInChaos Mar 18 at 9:48
    
@CodesInChaos: That sounds like a good answer to me - could you repost it as such so I can upvote as answer? –  figlesquidge Mar 18 at 11:07
    
@CodesInChaos - so it is a misnomer, but one which is accepted by the community. Please make this an answer so I can accept it. Thanks. –  P Godbole Mar 18 at 12:50

1 Answer 1

up vote 5 down vote accepted

CodesInChaos has it correct, however since you're just learning, I think I'll lay it out rather explicitly.

When we have an abstract group, there are two ways of expressing operations in the group.

One way is writing the operation as if it were the multiplication operation, for example, if we apply the operation to elements $A$ and $B$ and the result is the element $C$, we would write this as $AB = C$, or alternatively (if we want to emphasize the operation) $A \cdot B = C$. In addition, the act of performing the operation on $n$ copies of object $A$ is written as $$\underbrace{A \cdot A \cdot ... \cdot A}_\text{n copies} = A^n$$ When we write a group in this format, we call it a "multiplicative group".

The other way to write the operation would be to write it as if it were the addition operation. In our example where we apply the operation to elements $A$ and $B$ resulting in $C$, this gets expressed as $A+B=C$. The act of performing the operation on $n$ copies of the object $A$ is written as $$\underbrace{A + A + ... + A}_\text{n copies} = nA$$ When we write a group in this format, we call it an "additive group".

Now, the only difference between a multiplicative group and an additive group is how we choose to write it. For some groups, we traditionally write them in multiplicative form, for other groups, we generally write them in additive form.

One such group that always gets written in multiplicative form is that group $\mathbb{Z}_p^*$, which can be viewed as a set of integers between 1 and $p-1$ where the group operation is $(A \times B) \bmod p$. This is the first group where the problem "Given $G$ and $H$, it is difficult to find $n$ with $H = G^n$" was exploited cryptographically; because the analogous function in the Reals is called logarithm, as $n = \log_G H$, this problem was dubbed as the "discrete logarithm problem".

Now, we step to Elliptic Curve Groups; those groups are almost always written additively (I have seen it written multiplicatively, but it's rare). So, the analogous problem is "given points $G$ and $H$, find $n$ with $H = nG$". Now, if someone wanted to be completely consistent with the terminology, the obvious notational way to express this would be to write $n = H/G$ or this is a "point division problem". This would appear to make sense, however no one ever uses this terminology. Instead, everyone calls this the ECDLP problem, even though everything else done with elliptic cures is written additively. This is inconsistent, but language is like that; if you want other people to understand you, you use the terminology that everyone else does.

share|improve this answer
    
Thank you for the explanation. I thought mathematicians, of all people, to be the most precise in their language, but you have clarified the reason why they might not always be. –  P Godbole Mar 19 at 8:13
    
@PGodbole: actually, we are being precise; ECDLP means the problem "given the EC points $G$, and $nG$, find $n$", and nothing else. What it is not is consistent; we talk about the elliptic curve operation as analogous to "addition" everywhere except for ECDLP. –  poncho Mar 20 at 1:51
    
They are precise: what is meant by "multiplication" or "addition" is well-defined; that these words are interchangeable in the case of groups means that mathematicians are inefficient, not imprecise. ;) –  Andrew Poelstra Mar 21 at 16:30

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.