I like that Açık Per, Ara 2, 2021 00:02, coderman <[email protected]> yazdı:
> https://ristretto.group/ > > Ristretto is a technique for constructing prime order elliptic curve groups > with non-malleable encodings. It extends Mike Hamburg's > [Decaf](https://www.shiftleft.org/papers/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. > > Background > > 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](https://eprint.iacr.org/2015/673.pdf), 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. > > Pitfalls of a cofactor > > 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](https://moderncrypto.org/mail-archive/curves/2017/000898.html)—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](https://trac.torproject.org/projects/tor/ticket/22006#comment:13) in > the v3 onion services protocol, requiring a full scalar multiplication, point > compression, and equality check. This check [must be called in several > places](https://github.com/torproject/tor/search?q=hs_address_is_valid&unscoped_q=hs_address_is_valid) > to validate that the onion service's key does not contain a small torsion > component. > > Why can't we just multiply by the cofactor? > > 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](https://moderncrypto.org/mail-archive/curves/2017/000858.html). > Yet another approach is to choose a [torsion-safe > representative](https://moderncrypto.org/mail-archive/curves/2017/000866.html): > 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. > > 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. > > What is Ristretto? > > 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](https://ristretto.group/details/index.html), and explicit formulas > aimed at implementors are in the [Explicit > Formulas](https://ristretto.group/formulas/index.html) chapter. > > ...
