Struct curve25519_dalek::backend::serial::scalar_mul::straus::Straus

source ·
pub struct Straus {}
Available on crate feature alloc only.
Expand description

Perform multiscalar multiplication by the interleaved window method, also known as Straus’ method (since it was apparently first published by Straus in 1964, as a solution to a problem posted in the American Mathematical Monthly in 1963).

It is easy enough to reinvent, and has been repeatedly. The basic idea is that when computing \[ Q = s_1 P_1 + \cdots + s_n P_n \] by means of additions and doublings, the doublings can be shared across the \( P_i \).

We implement two versions, a constant-time algorithm using fixed windows and a variable-time algorithm using sliding windows. They are slight variations on the same idea, and are described in more detail in the respective implementations.

Trait Implementations§

source§

impl MultiscalarMul for Straus

source§

fn multiscalar_mul<I, J>(scalars: I, points: J) -> EdwardsPoint

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.

§

type Point = EdwardsPoint

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

impl VartimeMultiscalarMul for Straus

source§

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

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.

§

type Point = EdwardsPoint

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

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. Read more

Auto Trait Implementations§

§

impl Freeze for Straus

§

impl RefUnwindSafe for Straus

§

impl Send for Straus

§

impl Sync for Straus

§

impl Unpin for Straus

§

impl UnwindSafe for Straus

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> Conv for T

source§

fn conv<T>(self) -> T
where Self: Into<T>,

Converts self into T using Into<T>. Read more
source§

impl<T> FmtForward for T

source§

fn fmt_binary(self) -> FmtBinary<Self>
where Self: Binary,

Causes self to use its Binary implementation when Debug-formatted.
source§

fn fmt_display(self) -> FmtDisplay<Self>
where Self: Display,

Causes self to use its Display implementation when Debug-formatted.
source§

fn fmt_lower_exp(self) -> FmtLowerExp<Self>
where Self: LowerExp,

Causes self to use its LowerExp implementation when Debug-formatted.
source§

fn fmt_lower_hex(self) -> FmtLowerHex<Self>
where Self: LowerHex,

Causes self to use its LowerHex implementation when Debug-formatted.
source§

fn fmt_octal(self) -> FmtOctal<Self>
where Self: Octal,

Causes self to use its Octal implementation when Debug-formatted.
source§

fn fmt_pointer(self) -> FmtPointer<Self>
where Self: Pointer,

Causes self to use its Pointer implementation when Debug-formatted.
source§

fn fmt_upper_exp(self) -> FmtUpperExp<Self>
where Self: UpperExp,

Causes self to use its UpperExp implementation when Debug-formatted.
source§

fn fmt_upper_hex(self) -> FmtUpperHex<Self>
where Self: UpperHex,

Causes self to use its UpperHex implementation when Debug-formatted.
source§

fn fmt_list(self) -> FmtList<Self>
where &'a Self: for<'a> IntoIterator,

Formats each item in a sequence. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> Pipe for T
where T: ?Sized,

source§

fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> R
where Self: Sized,

Pipes by value. This is generally the method you want to use. Read more
source§

fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> R
where R: 'a,

Borrows self and passes that borrow into the pipe function. Read more
source§

fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> R
where R: 'a,

Mutably borrows self and passes that borrow into the pipe function. Read more
source§

fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
where Self: Borrow<B>, B: 'a + ?Sized, R: 'a,

Borrows self, then passes self.borrow() into the pipe function. Read more
source§

fn pipe_borrow_mut<'a, B, R>( &'a mut self, func: impl FnOnce(&'a mut B) -> R, ) -> R
where Self: BorrowMut<B>, B: 'a + ?Sized, R: 'a,

Mutably borrows self, then passes self.borrow_mut() into the pipe function. Read more
source§

fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
where Self: AsRef<U>, U: 'a + ?Sized, R: 'a,

Borrows self, then passes self.as_ref() into the pipe function.
source§

fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
where Self: AsMut<U>, U: 'a + ?Sized, R: 'a,

Mutably borrows self, then passes self.as_mut() into the pipe function.
source§

fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
where Self: Deref<Target = T>, T: 'a + ?Sized, R: 'a,

Borrows self, then passes self.deref() into the pipe function.
source§

fn pipe_deref_mut<'a, T, R>( &'a mut self, func: impl FnOnce(&'a mut T) -> R, ) -> R
where Self: DerefMut<Target = T> + Deref, T: 'a + ?Sized, R: 'a,

Mutably borrows self, then passes self.deref_mut() into the pipe function.
source§

impl<T> Same for T

§

type Output = T

Should always be Self
source§

impl<T> Tap for T

source§

fn tap(self, func: impl FnOnce(&Self)) -> Self

Immutable access to a value. Read more
source§

fn tap_mut(self, func: impl FnOnce(&mut Self)) -> Self

Mutable access to a value. Read more
source§

fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
where Self: Borrow<B>, B: ?Sized,

Immutable access to the Borrow<B> of a value. Read more
source§

fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
where Self: BorrowMut<B>, B: ?Sized,

Mutable access to the BorrowMut<B> of a value. Read more
source§

fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
where Self: AsRef<R>, R: ?Sized,

Immutable access to the AsRef<R> view of a value. Read more
source§

fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
where Self: AsMut<R>, R: ?Sized,

Mutable access to the AsMut<R> view of a value. Read more
source§

fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
where Self: Deref<Target = T>, T: ?Sized,

Immutable access to the Deref::Target of a value. Read more
source§

fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
where Self: DerefMut<Target = T> + Deref, T: ?Sized,

Mutable access to the Deref::Target of a value. Read more
source§

fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self

Calls .tap() only in debug builds, and is erased in release builds.
source§

fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self

Calls .tap_mut() only in debug builds, and is erased in release builds.
source§

fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
where Self: Borrow<B>, B: ?Sized,

Calls .tap_borrow() only in debug builds, and is erased in release builds.
source§

fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
where Self: BorrowMut<B>, B: ?Sized,

Calls .tap_borrow_mut() only in debug builds, and is erased in release builds.
source§

fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
where Self: AsRef<R>, R: ?Sized,

Calls .tap_ref() only in debug builds, and is erased in release builds.
source§

fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
where Self: AsMut<R>, R: ?Sized,

Calls .tap_ref_mut() only in debug builds, and is erased in release builds.
source§

fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
where Self: Deref<Target = T>, T: ?Sized,

Calls .tap_deref() only in debug builds, and is erased in release builds.
source§

fn tap_deref_mut_dbg<T>(self, func: impl FnOnce(&mut T)) -> Self
where Self: DerefMut<Target = T> + Deref, T: ?Sized,

Calls .tap_deref_mut() only in debug builds, and is erased in release builds.
source§

impl<T> TryConv for T

source§

fn try_conv<T>(self) -> Result<T, Self::Error>
where Self: TryInto<T>,

Attempts to convert self into T using TryInto<T>. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.