logo

Trait curve25519_dalek::traits::VartimeMultiscalarMul

source · [−]
pub trait VartimeMultiscalarMul {
    type Point;
    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>>;

    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,
    { ... }
}
Expand description

A trait for variable-time multiscalar multiplication without precomputation.

Associated Types

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

Required methods

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.

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

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.

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());

Implementors