<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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
