Trait curve25519_dalek_ng::traits::VartimeMultiscalarMul

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

A trait for variable-time multiscalar multiplication without precomputation.

Associated Types

type Point

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

Loading content...

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.

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

Loading content...

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.

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

Loading content...

Implementors

impl VartimeMultiscalarMul for EdwardsPoint

type Point = EdwardsPoint

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

impl VartimeMultiscalarMul for RistrettoPoint

type Point = RistrettoPoint

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

Loading content...