Ristretto is a technique for constructing prime order elliptic curve groups
with non-malleable encodings. It extends Mike Hamburg's Decaf approach
to cofactor elimination to support cofactor-\(8\) curves such as Curve25519.
In particular, this allows an existing Curve25519 library to implement a
prime-order group with only a thin abstraction layer, and makes it possible
for systems using Ed25519 signatures to be safely extended with zero-knowledge
protocols, with no additional cryptographic assumptions and minimal code
changes.
Ristretto can be used in conjunction with Edwards curves with cofactor \(4\)
or \(8\), and provides the following specific parameter choices:
ristretto255, built on top of Curve25519.Many cryptographic protocols require an implementation of a group of prime
order \( \ell \), usually an elliptic curve group. However, modern elliptic curve
implementations with fast, simple formulas don't provide a prime-order group.
Instead, they provide a group of order \(h \cdot \ell \) for a small cofactor,
usually \( h = 4 \) or \( h = 8\).
In many existing protocols, the complexity of managing this abstraction is
pushed up the stack via ad-hoc protocol modifications. But these modifications
are a recurring source of vulnerabilities and subtle design complications, and
they usually prevent applying the security proofs of the abstract protocol.
On the other hand, prime-order curves provide the correct abstraction, but
their formulas are slower and more difficult to implement in constant time. A
clean solution to this dilemma is Mike Hamburg's Decaf proposal,
which shows how to use a cofactor-\(4\) curve to provide a prime-order group
– with no additional cost.
This provides the best of both choices: the correct abstraction required to
implement complex protocols, and the simplicity, efficiency, and speed of a
non-prime-order curve. However, many systems use Curve25519, which has
cofactor \(8\), not cofactor \(4\).
Ristretto is a variant of Decaf designed for compatibility with
cofactor-\(8\) curves, such as Curve25519. It is particularly well-suited
for extending systems using Ed25519 signatures with complex zero-knowledge
protocols.
Curve cofactors have caused several vulnerabilities in higher-layer protocol
implementations. The abstraction mismatch can also have subtle consequences for
programs using these cryptographic protocols, as design quirks in the protocol
bubble up—possibly even to the UX level.
The malleability in Ed25519 signatures caused a double-spend vulnerability—or, technically, octuple-spend as
\( h = 8\)—in the CryptoNote scheme used by the Monero cryptocurrency, where
the adversary could add a low-order point to an existing transaction, producing
a new, seemingly-valid transaction.
In Tor, Ed25519 public key malleability would mean that every v3 onion service
has eight different addresses, causing mismatches with user expectations and
potential gotchas for service operators. Fixing this required expensive runtime checks in the v3 onion services protocol,
requiring a full scalar multiplication, point compression, and equality check.
This check must be called in several places to validate
that the onion service's key does not contain a small torsion component.
In some protocols, designers can specify appropriate places to multiply by the
cofactor \(h\) to "fix" the abstraction mismatches; in others, it's unfeasible
or impossible. In any case, multiplying by the cofactor often means that
security proofs are not cleanly applicable.
As touched upon earlier, a curve point consists of an \( h \)-torsion
component and an \( \ell \)-torsion component. Multiplying by the cofactor is
frequently referred to as "clearing" the low-order component, however doing so
affects the \( \ell \)-torsion component, effectively mangling the point.
While this works for some cases, it is not a validation method.
To validate that a point is in the prime-order subgroup, one can alternately
multiply by \( \ell \) and check that the result is
the identity. But this is extremely expensive.
Another option is to mandate that all scalars have particular bit patterns, as
in X25519 and Ed25519. However, this means that scalars are no longer
well-defined \( \mathrm{mod} \ell \), which makes HKD schemes much more complicated. Yet another approach is to
choose a torsion-safe representative:
an integer which is \( 0 \mathrm{mod} h \) and with a particular value \(
\mathrm{mod} \ell \), so that scalar multiplications remove the low-order
component. But these representatives are a few bits too large to be used with
existing implementations, and in any case aren't a comprehensive
solution.
Rather than bit-twiddling, point mangling, or otherwise kludged-in ad-hoc
fixes, Ristretto is a thin layer that provides protocol
implementors with the correct abstraction: a prime-order group.
Ristretto is a construction of a prime-order group using a non-prime-order
Edwards curve.
The Decaf paper suggests using a non-prime-order curve \(\mathcal E\) to
implement a prime-order group by constructing a quotient group. Ristretto uses
the same idea, but with different formulas, in order to allow the use of
cofactor-\(8\) curves such as Curve25519.
Internally, a Ristretto point is represented by an Edwards point. Two Edwards
points \(P, Q\) may represent the same Ristretto point, in the same way that
different projective \( X, Y, Z \) coordinates may represent the same Edwards
point. Group operations on Ristretto points are carried out with no overhead
by performing the operations on the representative Edwards points.
To do this, Ristretto defines:
a new type for Ristretto points which contains the representative
Edwards point;
equality on Ristretto points so that all equivalent
representatives are considered equal;
an encoding function on Ristretto points so that all equivalent
representatives are encoded as identical bitstrings;
a decoding function on bitstrings with built-in validation, so that only the
canonical encodings of valid points are accepted;
a map from bitstrings to Ristretto points suitable for hash-to-point
operations.
In other words, an existing Edwards curve implementation can implement the
correct abstraction for complex protocols just by adding a new type and three
or four functions. Moreover, equality checking for the Ristretto group is
actually less expensive than equality checking for the underlying curve!
The Ristretto construction is described and justified in detail in the next
chapter, and explicit formulas aimed at implementors are
in the Explicit Formulas chapter.