[Cfrg] Specifying Decaf

[Mike Hamburg <[e-mail]>]

Hello CFRG,

I’ve had a few requests over the past several months to write a formal specification of Decaf for Ed448, as a complement to Ristretto.

Here is a first take on this specification.  Let me know if you see any mistakes or concerns, or if the spec is too broad/narrow, and I’ll start an RFC.  The specification is based on the SAGE script at:

https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/_aux/ristretto/ristretto.sage <https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/_aux/ristretto/ristretto.sage>

which also includes Ristretto.



The goal of Decaf is to serialize points on an Edwards elliptic curve E.  The Decaf paper (https://eprin <https://eprin/>t.iacr.org/2015/673.pdf <http://t.iacr.org/2015/673.pdf>) specifies several approaches to encode points on an elliptic curve while eliminating the cofactor.  Some of the methods work only for Edwards curves, and only for h=4, whereas others work for h=8, twisted Edwards curves, Montgomery curves, etc.  The main design works by choosing a Jacobi quartic J which is 2-isogenous to the curve in question, and performing the encoding on J.

The Ed448Goldilocks curve is not isomorphic to Curve448, but 4-isogenous to each other.  The 4-isogeny filters through a 2-isogenous Jacobi quartic curve J, so that J is the canonical choice to use for the Decaf encoding on either Curve448 or Ed448.

Ed25519 is isomorphic to Curve25519.  Therefore there are two possible curves J: one that is 2-isogenous to Curve25519 using the isogeny in the Decaf paper, and one that is 2-isogenous to Ed25519 using the isogeny in the Decaf paper.  These curves are isomorphic to each other, but result in different encodings.

There were two initial implementations of Decaf: one by me covering both Ed25519 and Ed448, and one by Henry de Valence with input from Isis Lovecruft and Tony Arcieri.  My implementation used the curve adjacent to Curve25519, since it has a small d-coefficient (for NUMS purposes).  Henry et al used the curve adjacent to Ed25519.  So our implementations were mutually incompatible.  We met together and hashed out a compromise implementation called Ristretto.  I also changed my Decaf implementation on Ed448 to be more similar to Ristretto, so that their code would mostly match.

The Ristretto spec is published, but it is designed for Ed25519 explicitly.  It uses the fact that sqrt(-1) is in the field, and that the cofactor h=8.  It could be adapted to curves with h=4 such as Ed448 as well, but I would prefer using something closer to the original Decaf proposal, since that is already implemented, and since in fact Ristretto is already a compromise between that and an earlier curve25519 implementation.

Here is the specification of the Decaf encoding.





Let p be a prime, and GF(p) be the finite field of order p.  An element x of GF(p) has a canonical representation canon(x), which is the least non-negative integer which is congruent to x mod p.  An element x of GF(p) is “negative” if its canonical representation is odd, and “non-negative” otherwise.  Let abs(x) denote x or -x, whichever is non-negative.  Let sqrt(x) denote the non-negative square root of x, if it exists.

To serialize a field element to bytes, use the little-endian encoding of canon(x) using ceil(log(p,256)) bytes.  When deserializing a point, the representation must be of an even integer in the range [0, p-1].

Let a = 1 or -1.  Let E(p,a,d) be the Edwards curve y^2 + a*x^2 = 1 + d*x^2*y^2 over GF(p), and suppose that E has order h*q with q an odd prime.  The value h is called the “cofactor”.  We will assume that either h=4, or h=8 and a=1.  Call a point P on E “even” if P=2*Q for some point Q on E.

For compatibility with Ristretto’s encodings, we need a “magic” value in the encode function: magic = {
  sqrt(-d) if a = 1 and h=4
  sqrt(-1-d) if a = -1 and h=4
  -sqrt(d-1) if a = 1 and h = 8
}

These square roots will exist if h=4.  The h=8 case is tuned to match Ristretto on Ed25519.

To encode an even point P = (x,y) on E using Decaf, calculate as follows:

if x==0 or y==0: return 0
if h==8 and is_negative(x*y*magic): (x,y) = (-y,x)
u = sqrt(1-a*x^2) # This always exists if P is even
altx = x*y*magic / u
if negative(altx): u = -u
return abs((1-u)/x)



To decode an encoded point s:

if is_negative(s): fail()
if s==0: return (0,1)
t = sqrt(s^4 + 2*(a-2*d)*s^2 + 1) # if sqrt doesn’t exist, then fail()
altx = 2*s*magic / t
if is_negative(altx): t = -t
x = 2*s / (1+a*s^2)
y = (1-a*s^2) / t
if h==8 and (y==0 or is_negative(x*y*magic)): fail()
return (x,y)



It is also possible to use Elligator 2 with Decaf curves.  This function requires a quadratic nonresidue qnr in GF(p).  It takes an input r0 in GF(p), and calculates a point (x,y) on E as follows:
r = qnr * r0^2
den = (d*r-(d-a))*((d-a)*r-d)
if den == 0: return (0,1)
n1 = (r+1)*(a-2*d)/den
n2 = r*n1
if is_square(n1): s,t = sqrt(n1),  -(r-1)*(a-2*d)^2 / den - 1
else: s,t = -sqrt(n2), r*(r-1)*(a-2*d)^2 / den - 1
x = 2*s / (1+a*s^2)
y = (1-a*s^2) / t
return (x,y)

The resulting point will always be on E, and will always be even.  If elligator is to be applied to a string str of bytes, it should be interpreted as little_endian_decode(str) mod p.  The restrictions that it must be even and in [0,p-1] apply to decoding a point, but not to Elligator.



The recommended curves for use with Decaf are:

Ed448Goldilocks:
    p = 2^448 - 2^224 - 1
    d = -39081
    a = 1
    h = 4
    qnr = -1
    base point: 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33

TwistedEd448Goldilocks:
    p = 2^448 - 2^224 - 1
    d = -39082
    a = -1
    h = 4
    qnr = -1
    base point: 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33

These two curves are compatible, meaning that if one starts and ends with serialized points only, and performs only serialize, deserialize, Elligator2 and group operations (add, sub, scalarmul, etc), then the result will be the same with either curve.  Note that the usual addition law on TwistedEd448Goldilocks is not complete, and cannot be complete, because a=-1 isn’t square.  But the addition law is complete for even points, so as long as this curve is used with Decaf, it is a safe optimization over Ed448Goldilocks.



IsoEd25519:
    p = 2^255-19
    a = 1
    d = -121665
    h = 8
    qnr = sqrt(-1)
    base point: e2 f2 ae 0a 6a bc 4e 71 a8 84 a9 61 c5 00 51 5f 58 e3 0b 6a a5 82 dd 8d b6 a6 59 45 e0 8d 2d 76

The IsoEd25519 curve is compatible with Ristretto.  It has a potential performance advantage in that d is small.  However, it also has a=1, whereas a=-1 would be faster.  For maximum performance, implementers can use the curve:

ImaginaryIsoEd25519:
    p = 2^255-19
    a = -1
    d = 121665
    h = 8

This curve is isomorphic to IsoEd25519 by the map (x,y) -> (i*x, y) where i = sqrt(-1).  It can be encoded by undoing the isomorphism and then  using IsoEd25519’s encoder, and it can be decoded by applying IsoEd25519’s decoder and then using the isomorphism.

There is another obvious curve which we could use, but this is dangerous:

TwistedIsoEd25519: # don’t use
    p = 2^255-19
    a = -1
    d = -121666
    h = 8

However, this curve has 2x4 torsion instead of 8x1, which results in several problems.  The above formulas need further adaptation to work on it, and the addition is not complete.  So if you’re chasing the best possible performance for Decaf/Ristretto on Ed25519, it is better to use ImaginaryIsoEd25519 instead of TwistedIsoEd25519.


Questions / comments / typo corrections / thoughts?

Regards,
— Mike Hamburg