Ristretto

[zeynepaydogan]

Sent from ProtonMail for iOS

Açık Sal, Ara 21, 2021 00:41, zeynepaydogan <zeynepaydogan at protonmail.com> yazdı:

> I like that
>
> Açık Per, Ara 2, 2021 00:02, coderman <coderman at protonmail.com> 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.
>>
>> ...
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/html
Size: 9024 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20211220/3e492138/attachment.txt>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2623C301-571A-4D0A-82B4-94BEA41BED3D.jpg
Type: image/jpeg
Size: 140518 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20211220/3e492138/attachment-0001.jpg>