Struct curve25519_dalek::backend::serial::scalar_mul::straus::Straus

pub struct Straus {}

Perform multiscalar multiplication by the interleaved window method, also known as Straus' method (since it was apparently first published by Straus in 1964, as a solution to a problem posted in the American Mathematical Monthly in 1963).

It is easy enough to reinvent, and has been repeatedly. The basic idea is that when computing \[ Q = s_1 P_1 + \cdots + s_n P_n \] by means of additions and doublings, the doublings can be shared across the \( P_i \).

We implement two versions, a constant-time algorithm using fixed windows and a variable-time algorithm using sliding windows. They are slight variations on the same idea, and are described in more detail in the respective implementations.

Trait Implementations

impl MultiscalarMul for Straus

type Point = EdwardsPoint

The type of point being multiplied, e.g., RistrettoPoint.

fn multiscalar_mul<I, J>(scalars: I, points: J) -> EdwardsPoint where
    I: IntoIterator,
    I::Item: Borrow<Scalar>,
    J: IntoIterator,
    J::Item: Borrow<EdwardsPoint>, 

Constant-time Straus using a fixed window of size \(4\).

Our goal is to compute \[ Q = s_1 P_1 + \cdots + s_n P_n. \]

For each point \( P_i \), precompute a lookup table of \[ P_i, 2P_i, 3P_i, 4P_i, 5P_i, 6P_i, 7P_i, 8P_i. \]

For each scalar \( s_i \), compute its radix-\(2^4\) signed digits \( s_{i,j} \), i.e., \[ s_i = s_{i,0} + s_{i,1} 16^1 + ... + s_{i,63} 16^{63}, \] with \( -8 \leq s_{i,j} < 8 \). Since \( 0 \leq |s_{i,j}| \leq 8 \), we can retrieve \( s_{i,j} P_i \) from the lookup table with a conditional negation: using signed digits halves the required table size.

Then as in the single-base fixed window case, we have \[ \begin{aligned} s_i P_i &= P_i (s_{i,0} + s_{i,1} 16^1 + \cdots + s_{i,63} 16^{63}) \\ s_i P_i &= P_i s_{i,0} + P_i s_{i,1} 16^1 + \cdots + P_i s_{i,63} 16^{63} \\ s_i P_i &= P_i s_{i,0} + 16(P_i s_{i,1} + 16( \cdots +16P_i s_{i,63})\cdots ) \end{aligned} \] so each \( s_i P_i \) can be computed by alternately adding a precomputed multiple \( P_i s_{i,j} \) of \( P_i \) and repeatedly doubling.

Now consider the two-dimensional sum \[ \begin{aligned} s_1 P_1 &=& P_1 s_{1,0} &+& 16 (P_1 s_{1,1} &+& 16 ( \cdots &+& 16 P_1 s_{1,63}&) \cdots ) \\ + & & + & & + & & & & + & \\ s_2 P_2 &=& P_2 s_{2,0} &+& 16 (P_2 s_{2,1} &+& 16 ( \cdots &+& 16 P_2 s_{2,63}&) \cdots ) \\ + & & + & & + & & & & + & \\ \vdots & & \vdots & & \vdots & & & & \vdots & \\ + & & + & & + & & & & + & \\ s_n P_n &=& P_n s_{n,0} &+& 16 (P_n s_{n,1} &+& 16 ( \cdots &+& 16 P_n s_{n,63}&) \cdots ) \end{aligned} \] The sum of the left-hand column is the result \( Q \); by computing the two-dimensional sum on the right column-wise, top-to-bottom, then right-to-left, we need to multiply by \( 16\) only once per column, sharing the doublings across all of the input points.

impl VartimeMultiscalarMul for Straus

type Point = EdwardsPoint

The type of point being multiplied, e.g., RistrettoPoint.

fn optional_multiscalar_mul<I, J>(scalars: I, points: J) -> Option<EdwardsPoint> where
    I: IntoIterator,
    I::Item: Borrow<Scalar>,
    J: IntoIterator<Item = Option<EdwardsPoint>>, 

Variable-time Straus using a non-adjacent form of width \(5\).

This is completely similar to the constant-time code, but we use a non-adjacent form for the scalar, and do not do table lookups in constant time.

The non-adjacent form has signed, odd digits. Using only odd digits halves the table size (since we only need odd multiples), or gives fewer additions for the same table size.

fn vartime_multiscalar_mul<I, J>(scalars: I, points: J) -> Self::Point where
    I: IntoIterator,
    I::Item: Borrow<Scalar>,
    J: IntoIterator,
    J::Item: Borrow<Self::Point>,
    Self::Point: Clone, 

Given an iterator of public scalars and an iterator of public points, compute $$ Q = c_1 P_1 + \cdots + c_n P_n, $$ using variable-time operations.