elliptic curves

Work in Progress

Summary

The points on a nonsingular elliptic curve, together with the point at infinity, form an abelian group. Scalar multiplication is efficient while elliptic-curve DLOG is believed hard.

Concept

Elliptic curves

  • set of points that satisfy an equation + point at infinity
  • this simplified weierstrass form requires characteristic != 2

the full weierstrass form is but not covered in co485

Geometric interpretation

  • over the real numbers
x2Ry2Ry2=x3¡2x+1overR
  • over a finite field
y2Z89x2Z89²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²y2=x3¡2x+1overZ89

Group operation

  • on points on the eliptic curve
  • line connecting two points -> 3rd intersection -> flip y

Geometric interpretation

  • point addition/chord rule
PQR
  • identity/neutral element
O
  • inverse, flip y
P¡P
  • tangent rule, “exponentiation” for elliptic curve groups
P2P

Algebraic interpretation

Short weierstrass form

  • all elliptic curves have a weierstrass form if the characteristic != 2 or 3

all elliptic curves in fields where can be expressed in weierstrass form

Common shapes

a=¡2a=¡1a=0a=1b=¡1b=0b=1b=2y2=x3+ax+b

Group operation for short weierstrass

Computing efficiently

Runtime of group operation

Double-and-add

  • calculate “exponentiation” in the elliptic curve group,
  • same principle as square-and-multiply,

Sources