#ITEM 2 - Ristretto Implementation over Sean's Doppio Curve

[CPerezz]

Since the curve that Sean provided in:

Here's an "embedded" curve over ristretto255's scalar field

-x^2 + y^2 = 1 - (86649/86650)x^2y^2

which is Ristretto-ready and birationally equivalent to

y^2 = x^3 + 346598x^2 + x (and it's twist secure)

Any other suggestions?

— Sean Bowe (@ebfull) January 22, 2019

Provides values for the Twisted Edwards form that aren't suitable for a Ristretto protocol implementation we have two options:

• Find an isomorphic twist that allows us to mantain the same orders for the Finite Field and also the Sub group, and at the same time, gives a & d values that are suitable for a Ristretto implementation.

• Choice a diferent curve. This will force us to:

  • Find the new order of the Sub group and refactor the Scalar implementation to work over the new order and implement Decaf or Ristretto depending on the co-factor that the new curve provides.

It seems that @Bounce23 found an isomorphic twist that can do the job. We will update here the discussions.

[CPerezz]

@Bounce23 provided the values: a = -1, d = -86649 related to the isomorphic twist solution.

[CPerezz]

As far as we've seen, with the implementation of sqrt_ratio_i and the refactor of inv_sqrt functions done on 9c00824 and 73ee720 and the refactor done then of compression/decompression functions done in 2f395a7, allowed us to pass:

• bad_encoding_test, see: https://ristretto.group/test_vectors/ristretto255.html
• identity_point_encoding/decoding.

We are still unable to pass the good_encoding_tests since the RISTRETTO_BASEPOINT_COMPRESSED variable cannot be decompressed (which might mean that we need to find our own Basepoint).

[CPerezz]

@Bounce23 found the following parameters for an isomorphic twist that should work:

sage: d = 86649

sage: a = -1

sage: b = d/a

sage: b = 4*b

sage: c = 2-b

sage: c

346598

This ones, will provide the same Sub-group order, and also satisfy:

• Twisted Edwards Curve with Co-factor 8.
• Satisfy the isogeny proof b between the 3 curve types (Tw Edwards, Montgomery, Jacobian).

[LukePearson1]

We are still able to use a basepoint encoding for our curve, to fit with the ristretto scalar field. This is the one shown here:

sage: def findBasepoint(prime, A):
....:        F = GF(prime)
....:        E = EllipticCurve(F, [0, A, 0, 1, 0])
....: 
....:        for uInt in range(1, 1e3):
....:          u = F(uInt)
....:          v2 = u^3 + A*u^2 + u
....:          if not v2.is_square():
....:            continue
....:          v = v2.sqrt()
....:          point = E(u, v)
....:          pointOrder = point.order()
....:          if pointOrder > 8 and pointOrder.is_prime():
....:             Q=u^3 + A*u^2 + u
....:             return u, Q, sqrt(Q), point
....:
sage: res = findBasepoint(x, 346598)
sage: res
(17,
 100171752,
 1014685013428497365422144808165958100622560545891891747637198454693655077041,
 (17 : 1014685013428497365422144808165958100622560545891891747637198454693655077041 : 1))

The difference is that we make use of an Edwards Y, without the need to specify the 'unique' basepoint stemming from (u-1)/(u+1), as this is for thee 25519 Montgomery fast scalar multiplication. Whereas ours is Edwards points encoded as field elements.
The chosen Y value for a base point passes all the tests.

[LukePearson1]

Furthering the above comment: the base point for twisted Edwards, Y = 100171752, is not chosen arbitrarily; and is in line with the safe curves criteria as shown here, which is found in the code at line 422 here. This is set such that the curve maintains rigidity and to allow y(P) as a ladder coordinate.

[CPerezz]

This is closed since we take part of this on #82