# Module curve25519_dalek::ristretto
[−]
[src]

An implementation of Ristretto, which provides a prime-order group.

# The Ristretto Group

Ristretto is a modification of Mike Hamburg's Decaf scheme to work
with Curve25519. The introduction of the Decaf paper, *Decaf:
Eliminating cofactors through point
compression*, notes that while
most cryptographic systems require a group of prime order, most
concrete implementations using elliptic curve groups fall short --
they either provide a group of prime order, but with incomplete or
variable-time addition formulae (for instance, most Weierstrass
models), or else they provide a fast and safe implementation of a
group whose order is not quite a prime \(q\), but \(hq\) for a
small cofactor \(h\) (for instance, Edwards curves, which have
cofactor at least \(4\)).

This abstraction mismatch requires ad-hoc protocol modifications to ensure security; these modifications require careful analysis and are a recurring source of vulnerabilities and design complications.

Instead, Ristretto uses a quotient group to implement a prime-order
group using a non-prime-order curve. More details are described in
the *Implementation* section below. Ristretto points are provided
in `curve25519-dalek`

by the `RistrettoPoint`

struct.

## Encoding and Decoding

Encoding is done by converting to and from a `CompressedRistretto`

struct, which is a typed wrapper around `[u8; 32]`

.

The encoding is not batchable, but it is possible to
double-and-encode in a batch using
`RistrettoPoint::double_and_compress_batch`

.

## Equality Testing

Testing equality of points on an Edwards curve in projective coordinates requires an expensive inversion. By contrast, equality checking in the Ristretto group can be done in projective coordinates without requiring an inversion, so it is much faster.

The `RistrettoPoint`

struct implements the `subtle::Equal`

trait for
constant-time equality checking, and the Rust `Eq`

trait for
variable-time equality checking.

## Scalars

Scalars are represented by the `Scalar`

struct. Each scalar has a
canonical representative mod the group order; see
`Scalar::from_canonical_bytes()`

and `Scalar::is_canonical()`

.

## Scalar Multiplication

Scalar multiplication on Ristretto points is provided by:

the

`*`

operator between a`Scalar`

and a`RistrettoPoint`

, which performs constant-time variable-base scalar multiplication;the

`*`

operator between a`Scalar`

and a`RistrettoBasepointTable`

, which performs constant-time fixed-base scalar multiplication;the

`ristretto::multiscalar_mult`

function, which performs constant-time variable-base multiscalar multiplication;the

`ristretto::vartime::multiscalar_mult`

function, which performs variable-time variable-base multiscalar multiplication.

## Random Points and Hashing to Ristretto

The Ristretto group comes equipped with an Elligator map. This is used to implement

`RistrettoPoint::random()`

, which generates random points from an RNG;`RistrettoPoint::from_hash()`

and`RistrettoPoint::hash_from_bytes()`

, which perform hashing to the group.

The Elligator map itself is not currently exposed.

## Implementation

The Decaf suggestion is to use a quotient group, such as \(\mathcal E / \mathcal E[4]\) or \(2 \mathcal E / \mathcal E[2] \), to implement a prime-order group using a non-prime-order curve.

This requires only changing

- the function for equality checking (so that two representatives of the same coset are considered equal);
- the function for encoding (so that two representatives of the same coset are encoded as identical bitstrings);
- the function for decoding (so that only the canonical encoding of a coset is accepted).

Internally, each coset is represented by a curve point; two points may represent the same coset in the same way that two points with different \(X,Y,Z\) coordinates may represent the same point. The group operations are carried out using the fast, safe Edwards formulas.

The Decaf paper suggests implementing the compression and
decompression routines using an isogeny from a Jacobi quartic; for
curves of cofactor \(4\), this eliminates the cofactor, and
explains the name: Decaf is named "after the procedure which divides
the effect of coffee by \(4\)". However, Curve25519 has a
cofactor of \(8\). To eliminate its cofactor, we tweak Decaf to
restrict further. This additional restriction
gives the *Ristretto* encoding.

Notes on the details of the encoding can be found in the
`ristretto::notes`

submodule of the internal `curve25519-dalek`

documentation.

## Modules

vartime |
Variable-time operations on ristretto points, useful for non-secret data. |

## Structs

CompressedRistretto |
A Ristretto point, in compressed wire format. |

RistrettoBasepointTable |
A precomputed table of multiples of a basepoint, used to accelerate scalar multiplication. |

RistrettoPoint |
A |

## Functions

multiscalar_mult |
Given an iterator of (possibly secret) scalars and an iterator of (possibly secret) points, compute $$ Q = c_1 P_1 + \cdots + c_n P_n. $$ |