pyecsca.ec.mult.msm.pippenger module

Provides the Pippenger (bucket) multi-scalar multiplier.

class PippengerMultiplier(add, dbl, width, scl=None, accumulation_order=AccumulationOrder.PeqPR, complete=True, skip_zero=True, short_circuit=True)

Bases: MultiScalarMultiplier

Pippenger (bucket method) multi-scalar multiplier.

Computes the sum of the products of the points with their scalars using b-bit windows and 2**b buckets per window, see [Pip76]. The scalar windows are gathered into buckets and the buckets are accumulated in a single pass, which makes the per-window cost independent of the number of points.

Note

The bucket accumulation feeds special point pairs to the addition formula: the running sum may add a point to itself (when a bucket is empty, the result equals the running sum and R = R + C becomes C + C) and it may cancel a point with its negation (P + (-P)). The provided addition and doubling formulas therefore must be complete, i.e. they must handle these cases without a special-case branch.

Parameters:

• width (int) – The window width (number of bits per window).

• complete (bool) – Whether it processes the full order-bit-length of the scalars.

• accumulation_order (AccumulationOrder) – The order of accumulation of points.

• short_circuit (bool) – Whether the use of formulas will be guarded by short-circuit on inputs of the point at infinity.

requires: ClassVar[Set[Type]] = {<class 'pyecsca.ec.formula.base.AdditionFormula'>, <class 'pyecsca.ec.formula.base.DoublingFormula'>}

The set of formula types that the multiplier requires.

optionals: ClassVar[Set[Type]] = {<class 'pyecsca.ec.formula.base.ScalingFormula'>}

The optional set of formula types that the multiplier can use.

width: int

The window width (number of bits per window).

accumulation_order: AccumulationOrder

The order of accumulation of points.

complete: bool

Whether it processes the full order-bit-length of the scalars.

short_circuit: bool

Whether the formulas will short-circuit upon input of the point at infinity.

formulas: Mapping[str, Formula]

All formulas the multiplier was initialized with.

skip_zero: bool

Whether it skips zero-value windows and assigns the first point to the bucket (w/o addition).

init(params, points, bits=None)

Initialize the multi-scalar multiplier with params and a list of points.

Warning

The points are not verified to be on the curve represented in the domain parameters.

Parameters:

• params (DomainParameters) – The domain parameters to initialize the multiplier with.

• points (List[Point]) – The points to initialize the multiplier with.

• bits (Optional[int]) – The number of bits to use in the multi-scalar multiplication (i.e. no scalar will be larger than 2^bits). The default is the bit length of the full order of the curve (including cofactor).

multiply(scalars)

Compute the multi-scalar product of the points the multiplier was initialized with.

Note

The multiplier needs to be initialized by a call to the init() method.

Parameters:

scalars (List[int]) – The scalars to use, one per point the multiplier was initialized with.

Return type:

Point

Returns:

The resulting linear combination.