[−][src]Trait curve25519_dalek::traits::MultiscalarMul

pub trait MultiscalarMul {
    type Point;
    fn multiscalar_mul<I, J>(scalars: I, points: J) -> Self::Point
    where
        I: IntoIterator,
        I::Item: Borrow<Scalar>,
        J: IntoIterator,
        J::Item: Borrow<Self::Point>;
}

A trait for constant-time multiscalar multiplication without precomputation.

Associated Types

type Point

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

Loading content...

Required methods

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

Given an iterator of (possibly secret) scalars and an iterator of public points, compute $$ Q = c_1 P_1 + \cdots + c_n P_n. $$

It is an error to call this function with two iterators of different lengths.

Examples

The trait bound aims for maximum flexibility: the inputs must be convertable to iterators (I: IntoIter), and the iterator's items must be Borrow<Scalar> (or Borrow<Point>), to allow iterators returning either Scalars or &Scalars.

use curve25519_dalek::constants;
use curve25519_dalek::traits::MultiscalarMul;
use curve25519_dalek::ristretto::RistrettoPoint;
use curve25519_dalek::scalar::Scalar;

// Some scalars
let a = Scalar::from(87329482u64);
let b = Scalar::from(37264829u64);
let c = Scalar::from(98098098u64);

// Some points
let P = constants::RISTRETTO_BASEPOINT_POINT;
let Q = P + P;
let R = P + Q;

// A1 = a*P + b*Q + c*R
let abc = [a,b,c];
let A1 = RistrettoPoint::multiscalar_mul(&abc, &[P,Q,R]);
// Note: (&abc).into_iter(): Iterator<Item=&Scalar>

// A2 = (-a)*P + (-b)*Q + (-c)*R
let minus_abc = abc.iter().map(|x| -x);
let A2 = RistrettoPoint::multiscalar_mul(minus_abc, &[P,Q,R]);
// Note: minus_abc.into_iter(): Iterator<Item=Scalar>

assert_eq!(A1.compress(), (-A2).compress());
Loading content...

Implementors

impl MultiscalarMul for Straus[src]

type Point = EdwardsPoint

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

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 MultiscalarMul for EdwardsPoint[src]

type Point = EdwardsPoint

impl MultiscalarMul for RistrettoPoint[src]

type Point = RistrettoPoint

Loading content...