9
$\begingroup$

Edward curves were considered initially because they provide a unified formula for both doubling and addition, thus having inherent side-channel resistance. But a lot of work has been done recently involving construction of a different class of addition and doubling formula (e.g. differential addition formula, w-coordinate formula), particularly concerning efficiency of these formulas in terms of the number of field multiplications/squarings. Thus, the point of unification becomes invalid.

Please can anybody explain/cite some relevant papers which address this issue?

$\endgroup$
  • $\begingroup$ In some papers unification is preserved (e.g., "Twisted Edwards curves") while in others it is not (e.g., "Twisted Edwards curves revisited"). I think that in practice the order of the group is usually so large that the probability of accidentally having two times the same point in an addition is negligible. So this should not really be an issue. (Unless you know an attack that can exploit this?) $\endgroup$ – Chris Aug 10 '15 at 11:01
2
$\begingroup$

Edwards curves can be implemented using a unified formula for addition and doubling; i.e., one can implement addition such that $$\mathrm{dbl}(P)=\mathrm{add}(P,P).$$ Performance wise it is however more efficient to consider both functions separately, since the doubling can be implemented more efficiently than the addition.

Depending on the representation and the formulas, the unification property will be preserved or not. For instance, in "Twisted Edwards curves" by Berstein et al., there is a formula for $\mathrm{add}(P,Q)$ and a faster one for $\mathrm{dbl}(P)$, but the above property still holds. In "Twisted Edwards curves revisited" by Hisil et al., there are also two separate formulas, but the above property doesn't hold anymore.

I think the unification property looks great in a paper as it makes the description cleaner; however one does not necessarily need it in practice. Some examples:

  • Example 1: "Scalar multiplication (based on Exponentation by squaring)". When the factor is lower than the order of the group, you know that the next doubling is always higher than the accumulated value, so that an addition will always take place between two different points.

  • Example 2: "Addition of random points". The order of the group is in general so large, that the probabilty that two randomly chosen points are equal is negligible.

So in many situations the absence of the unification property does not seem to be an issue. It will of course depend on what precisely you are doing with the curve.

$\endgroup$
  • $\begingroup$ While performing the Scalar Multiplication operation, both doubling and addition operations are involved. An Edward curve implementation has the opportunity of using the unified formula for both doubling and addition, thus introducing inherent side-channel security. However recently separate formulas are being proposed for Edward curve also, which is not taking advantage of the unification property. My concern was why is that so ? $\endgroup$ – PD22 Sep 2 '15 at 12:38
  • $\begingroup$ @PD22: There are many ways to implement a scalar multiplication, e.g. there are techniques for fixed bases, for fixed exponents, techniques based on exponentiation by squaring, montgomery ladder, ... Using a unified formula does not automatically guarantee side-channel resistance. To obtain constant timing you must ensure that you have a fixed number of additions and doublings and that the whole computation is done without branchings. You can for instance use a Montgomery ladder for this. So you will have a fixed number of doublings, but its better to have fast ones than slow ones. :) $\endgroup$ – Chris Sep 2 '15 at 13:06
  • $\begingroup$ In case of Montgomary Ladder, due to the computation of fixed number of doubling and additions, there a number of dummy additions which are performed. So in that case although separate formulas are faster, there exists the overhead of dummy addition computations. While in case of unification doubling operation involves few extra field multiplications, however there will exist no extra addition operations when fixed base scalar multiplication is performed without use of Montgomary Ladder. The point is, unification may benefit instead of separate formulas also in some situations :) $\endgroup$ – PD22 Sep 3 '15 at 13:48
  • $\begingroup$ @PD22: Hmm... I'm sorry, but I think you might be mistaken. In any case you need a Montgomery ladder or something equivalent. It is not the case that unification protects you against timing attacks! To protect against timing attacks you must implement the complete scalar multiplication so that it executes in constant time $t$. In practice this typically means that you have a constant number of $x$ additions and a constant number of $y$ doublings. You then have $t=x\cdot \mbox{[time for 1 addition]} +y\cdot \mbox{[time for 1 doubling]}+c$. So you should normally benefit from faster doublings. $\endgroup$ – Chris Sep 3 '15 at 22:24
  • $\begingroup$ @PD22: There is a wikipedia page about timing attacks. I think it is the simplest side channel attack. $\endgroup$ – Chris Sep 4 '15 at 9:01
-1
$\begingroup$

Without knowing what recent work you refer to, I can state that one of the prime benefits of the Edwards curves is the unified adding / doubling, and their completeness -- i.e., no exceptional points. Hence no branching decisions to provide clues to side channel snooping. And also, fewer places to screw up the implementation.

$\endgroup$
  • $\begingroup$ The question is about why formulas that seem to undo this benefit have been developed/are interesting. $\endgroup$ – otus Aug 10 '15 at 8:17

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.