[curves] Input validation for genus 2 scalar multiplication

[Robert Ransom]

<http://cr.yp.to/papers.html#kummer> provides most of the information
needed to implement scalar multiplication efficiently on the
Gaudry-Schost genus-2 Kummer surface modulo 2^127 - 1, but (as of the
2014-02-18 version) omits any mention of input validation:

* The paper does not mention that software must verify that input
  points alleged to be on a Kummer surface satisfy the equation of the
  Kummer surface.

* The paper does not mention any techniques to check that input points
  satisfy the equation of the Kummer surface efficiently.

* The paper does not even mention the equation which input points must
  satisfy.

* The paper also does not give any evidence that input validation is
  unnecessary for Kummer-surface cryptographic software.

(The paper does mention that the Gaudry-Schost surface is
‘twist-secure’, but this only matters once a point is verified to be
on that surface.)

This leads me to expect that the software described in that paper does
not perform input validation, and thus the performance figures do not
include the cost of any required input validation.


I wrote a quick-and-dirty test program to apply scalar multiplication
routines using the formulas in figure 2.4 to both the standard
basepoint specified in the paper and several random inputs.  It
reported that the scalar multiplication routine was ‘non-commutative’
(i.e. a*(b*P) did not equal b*(a*P)) at every invalid input point, for
both the 2.4(a) and the 2.4(b) formulas.  Thus, any attack enabled by
lack of input validation will require ad-hoc methods, rather than
being a generalization of the ‘invalid-curve attack’.


Background:

Curve-based cryptography uses the ‘Jacobian’ group associated with an
algebraic curve as an analogue of the original setting for
discrete-logarithm-based cryptography, the multiplicative group modulo
a prime.

*Over an algebraically closed field*, a Kummer variety of a Jacobian
is an algebraic variety (which may be a curve, a surface, or some
higher-dimensional object), specified along with a map k from the
Jacobian to the Kummer variety such that k(P) = k(-P) for each element
P of the Jacobian group, k(P) is not equal to k(Q) unless Q = P or Q =
-P, and every element of the Kummer variety is of the form k(P).

The Jacobian of a genus-1 (elliptic) curve is naturally represented as
the set of points on the curve.  (Thus, introductions to
elliptic-curve cryptography frequently omit the term “Jacobian”
entirely.)  The Kummer varieties used for genus-1 (elliptic) curves
all consist of the whole projective line P^1.

For a genus-2 curve, each element of the Jacobian group is represented
by an unordered pair of points on the curve, and the usual Kummer
variety maps each such pair to a single point on a two-dimensional
surface in P^3.  Since the Kummer variety is of dimension 2, but
embedded in a space of dimension 3, not every point in P^3 represents
a point on the Kummer variety.


In practice, cryptography must be performed in fields that are not
algebraically closed.  A curve's Kummer variety then contains many
points that do not correspond to elements of the curve's Jacobian over
the same base field; these points instead represent elements of the
Jacobian of the curve's quadratic twist.  ‘Twist security’ means that
both the curve and its quadratic twist have group structures suitable
for cryptographic use, so that software can safely use a point on the
Kummer variety without performing a relatively expensive computation
to check which curve it belongs to.

In genus 1, twist security can allow Kummer-variety scalar
multiplication software to skip all input validation.  In genus 2,
twist security is not sufficient; software must verify that an input
point is on the Kummer variety, rather than merely in the space in
which the Kummer variety is embedded, before operating on that input.
Fortunately, this consists of merely checking that the input satisfies
an algebraic equation, rather than performing a square-root
computation or Legendre symbol test.


Robert Ransom