Trait VartimeMultiscalarMul

pub trait VartimeMultiscalarMul {
    type Point;

    // Required method
    fn optional_multiscalar_mul<I, J>(
        scalars: I,
        points: J,
    ) -> Option<Self::Point>
       where I: IntoIterator,
             I::Item: Borrow<Scalar>,
             J: IntoIterator<Item = Option<Self::Point>>;

    // Provided method
    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 { ... }
}

A trait for variable-time multiscalar multiplication without precomputation.

Required Associated Types

type Point

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

Required Methods

fn optional_multiscalar_mul<I, J>(scalars: I, points: J) -> Option<Self::Point>

where I: IntoIterator, I::Item: Borrow<Scalar>, J: IntoIterator<Item = Option<Self::Point>>,

Given an iterator of public scalars and an iterator of Options of points, compute either Some(Q), where $$ Q = c_1 P_1 + \cdots + c_n P_n, $$ if all points were Some(P_i), or else return None.

This function is particularly useful when verifying statements involving compressed points. Accepting Option<Point> allows inlining point decompression into the multiscalar call, avoiding the need for temporary buffers.

#[cfg(feature = "alloc")]
use curve25519_dalek::constants;
use curve25519_dalek::traits::VartimeMultiscalarMul;
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);
let abc = [a,b,c];

// Some points
let P = constants::RISTRETTO_BASEPOINT_POINT;
let Q = P + P;
let R = P + Q;
let PQR = [P, Q, R];

let compressed = [P.compress(), Q.compress(), R.compress()];

// Now we can compute A1 = a*P + b*Q + c*R using P, Q, R:
let A1 = RistrettoPoint::vartime_multiscalar_mul(&abc, &PQR);

// Or using the compressed points:
let A2 = RistrettoPoint::optional_multiscalar_mul(
    &abc,
    compressed.iter().map(|pt| pt.decompress()),
);

assert_eq!(A2, Some(A1));

// It's also possible to mix compressed and uncompressed points:
let A3 = RistrettoPoint::optional_multiscalar_mul(
    abc.iter()
        .chain(abc.iter()),
    compressed.iter().map(|pt| pt.decompress())
        .chain(PQR.iter().map(|&pt| Some(pt))),
);

assert_eq!(A3, Some(A1+A1));

Provided Methods

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.

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.

#[cfg(feature = "alloc")]
use curve25519_dalek::constants;
use curve25519_dalek::traits::VartimeMultiscalarMul;
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::vartime_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::vartime_multiscalar_mul(minus_abc, &[P,Q,R]);
// Note: minus_abc.into_iter(): Iterator<Item=Scalar>

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

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl VartimeMultiscalarMul for EdwardsPoint

type Point = EdwardsPoint

impl VartimeMultiscalarMul for RistrettoPoint

type Point = RistrettoPoint