Flexible precomputation for verification checks

Multiscalar multiplications versus multiple scalar multiplications

Many elliptic curve protocols spend most of their time performing scalar multiplication operations: computing a*A for a curve point A and a scalar (integer modulo the curve order) a. In this post I’ll use capital letters A,B,P,Q,... for curve points and lower-case letters a,b,x,y,... for scalars, so it’s always possible to distinguish the type from the variable name.

a_1*A_1 + ... + a_n*A_n

Saving time with precomputation

Unfortunately, what these traits don’t allow is taking any advantage of precomputation. If the points are known up-front, it’s possible to trade memory for time by performing some precomputation on the points, then using it for each multiscalar multiplication.

Specifying the problem at a high level

As noted above, one of the core reasons that multiscalar multiplication can be faster than multiple scalar multiplications is that the entire problem is specified at once, and an implementation can share work between all the parts. We can write the general problem of multiscalar multiplication with precomputation in the form

a_1*A_1 + ... + a_n*A_n + b_1*B_1 + ... + b_m*B_m,

The VartimePrecomputedMultiscalarMul trait

This functionality is now provided in curve25519-dalek by the VartimePrecomputedMultiscalarMul trait, which takes the fixed points B_1,...,B_m in a constructor and returns a precomputation struct with three slightly different variants of the problem:

  • vartime_multiscalar_mul, which handles the special case where n=0 and there are no dynamic points;
  • vartime_mixed_multiscalar_mul, which takes the dynamic points as already-validated Points and is infallible;
  • optional_mixed_multiscalar_mul, which takes the dynamic points as Option<Point>s and returns an Option<Point>, so that a verification check on compressed point data can compose point decompression/validation into the input iterators.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Henry de Valence

Henry de Valence

interested in zero-knowledge, privacy, freedom, mathematics, & the number 24