2
$\begingroup$

A lot of papers use these terms but I do not find a proper explanation of them. Can somebody tell the meaning / difference / intuition / application and if possible with an example.

$\endgroup$
3
$\begingroup$

Unified addition means that the formula you use for adding two points doesn't depend on whether they are equal. Simplifying point addition in the Weierstrass form somewhat $s=(y_A-y_b)/(x_A-x_b)$ when $A\neq B$ - this is "Adding". Otherwise $s=(3x_A^2-p)/{2y_A}$ when doubling a point.

The implementation of these steps would normally involve different code paths and this can lead to problems as information about the private key is leaked if you can monitor the power consumption or timing to work out which path was taken even if you can't see the numbers involved. See section one of Barbosa & Page. Also, Bernstein ,on page 3 talks about a stronger but related property called "completeness".

Page 15 of the same Bernstein paper explains "differential additions". Another Bernstein quote is

Differential addition chains (also known as strong addition chains, Lucas chains, and Chebyshev chains) are addition chains in which every sum is already accompanied by a difference.

They are used to support fast addition on elliptic curves in the Edwards form.

$\endgroup$
0
$\begingroup$

Beware: This is the way I understand it from x25519 code, I have very little background in formal math, so apologies if I speak like a caveman.

The way i understood it is:

  • You know x coordinate of point P
  • You know x coordinate of point Q
  • You know x coordinate of point P-Q (which you obtained somehow, ie previous ladder step)
  • And only all of the above gives you answer to P+Q (which is the whole point)

Looking at x25519 montgomery ladder code, P and Q start as same point initially, but soon may differ depending on the further bits of the scalar. This works, because you know P-Q from previous rung (apparently), but you can't use this for explicit point addition alone, as you don't know P-Q in that case.

Note that all of this works X/Z -> x projection, but we can basically just think of z as "extended" part of the X input.

$\endgroup$

Your Answer

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