[−][src]Trait curve25519_dalek::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 Pippenger[src]

type Point = EdwardsPoint

impl VartimeMultiscalarMul for Straus[src]

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>>, [src]

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.

impl VartimeMultiscalarMul for EdwardsPoint[src]

type Point = EdwardsPoint

impl VartimeMultiscalarMul for RistrettoPoint[src]

type Point = RistrettoPoint

Loading content...