6
$\begingroup$

Elliptic Curve Cryptosystem has various coordinate systems; like the Affine, Projective, and Jacobian coordinate systems.

We prefer not to use the Affine coordinate system during the calculations since the operations require inversion and that is much costlier than multiplication.

Katz and Lindell, in their book, wrote this sentence on page #332 of the 2nd ed. (bolds mine);

Specifically, a point expressed in projective coordinates may reveal some information about how that point was obtained, which may depend on some secret information. To address this — as well as for reasons of efficiency — affine coordinates should be used for transmitting and storing points, with projective coordinates used only as an intermediate representation during the course of a computation (with points converted to/from projective coordinates at the beginning/end of the computation).

  • So, what information is revealed? e.g. if we execute ECDH or ECDSA.
  • Is there a good example that shows how the information leaked?
Improve this question
$\endgroup$
0
4
$\begingroup$

The danger of revealing results in protective coordinates is pointed by David Naccache, Nigel P. Smart, and Jacques Stern's Projective Coordinates Leak, in proceedings of Eurocrypt 2004. As noted in comment, a concise re-exposition is in section 3 of Alejandro C. Aldaya, Cesar P. García and Billy B. Brumley's From A to Z: Projective coordinates leakage in the wild, in proceedings of CHES 2020 (which uses it in side-channel leakage attacks on implementations using projective coordinates internally, even when the result is output in affine coordinates).

In a nutshell: revealing $[k]\,G$ in projective coordinates can leak some information about $k$; that's problematic.

Slightly more detail: in affine coordinates, a point (other than the point at infinity) is expressed as $(x,y)$ satisfying the curve equation $y^2=x^3+a\,x+b$, where $x$ and $y$ are field elements. In standard projective coordinates, the same point is expressed as $(X,Y,Z)=(Z\,x,Z\,y,Z)$, where $Z$ is any non-zero field element. That becomes $(X,Y,Z)=(Z^2\,x,Z^3\,y,Z)$ in Jacobian projective coordinates.

Therefore giving a point in projective coordinate gives the point, and an extra information $Z$ that can be any non-zero field element. That $Z$ depends on how the point was obtained, and is a potential information leak.

More in detail: Assume that it is given $P=[k]\,G$ with unknown $k\in[1,n)$ as projective coordinates $(X_P,Y_P,Z_P)$, and that was computed starting from a known $G$ of projective coordinates $X_G,Y_G,Z_G=(x_g,y,g,1)$, and integer $k$, using standard formulas for point addition and point doubling, and the straightforward left-to-right exponent scanning algorithm:

  • $P\gets G$
  • for each bit $b$ of $k$ from second high-order to low-order
    • $P\gets P+P$ (point doubling)
    • if bit $b$ is set
      • $P\gets P+G$ (point addition)

It turns out that there is a relation between $k$ and the final $Z_P$, and that relation is exploitable to get some information on $k$.

[I started summarizing the first article, but did not finish, sorry. Feel free to expand!]

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Maybe you have already considered it, there is the CHES 2020 paper From A to Z: Projective coordinates leakage in the wild which applies the attack of Naccache-Smart-Stern you cited. There is a good explanation in section 3. $\endgroup$ – user69015 Aug 31 '20 at 13:05
  • $\begingroup$ @corpsfini could you add an answer if you have already read it? $\endgroup$ – kelalaka Aug 31 '20 at 14:26
  • $\begingroup$ I haven't read it, I only looked over the main ideas. Section 3 explains things clearly and answers the first question, while section 5 and 6 answer the second. $\endgroup$ – user69015 Aug 31 '20 at 15:51
  • $\begingroup$ Actually, projective coordinates are easily rerandomizable. For example, given a Jacobean projected ec point $(x, y, z)$, one can select a random value $r$ and compute $(r^2x, r^3y, rz)$. If $r$ is uniformly selected from $1$ to $n-1$, then this new representation is selected uniformly from all representations of that ec point, and thus the coordinates do not leak any information (other than what's inherent with the ec point) $\endgroup$ – poncho Sep 1 '20 at 19:05

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.