[curves] Curve with group order 2^255-19

[Aurore Guillevic]

Hi all,

It seems the email below from Andrew Poelstra is the usual reference 
about the plain cycle of elliptic curves secp256k1 and secq256k1.

I don't know if the question of Andrew Poelstra with 2^255-19 was 
answered somewhere else?
Here is an example in SageMath of a plain elliptic curve E1 of prime 
order 2^255-19, so that its scalar field is the base field of Curve25519.
Because E1 has prime order, it can form a cycle, and E2 given below is 
the cycle curve.

As Curve25519 is not of prime order but has a cofactor 8, it cannot form 
a cycle, it only forms a 2-chain with E1: Curve25519 is the embedded 
curve of E1.

p = 2^255-19
q = 
57896044618658097711785492504343953926364671633031636665140593451561373407839
E1 = EllipticCurve(GF(q), [-3, 
13234454322292634933698063389512331917842329599874076633128963737335133558588])
assert E1.order() == p
E2 = EllipticCurve(GF(p), [-3, 
32261232353061579396593790943068895026169339441948595271130540869330756371269])
assert E2.order() == q

It took me about two days of computation on a single core on a laptop to 
generate the example, with a non-optimized code in SageMath and GP.
The curves E1 and E2 have discriminant D = -65012179.

With best regards,

Aurore.

Aurore Guillevic
Équipe CAPSULE, Centre Inria de l'Université de Rennes, IRISA,
Campus de Beaulieu, 263 Avenue Général Leclerc, 35042 Rennes Cedex
https://members.loria.fr/AGuillevic/


On 3/21/18 13:30, Andrew Poelstra wrote:
> Hi all,
>
>
> A spooky seeming-fact about j-invariant 0 prime-order curves over prime fields
> is that you can "just swap the field and group order" to obtain a new prime
> order curve of j-invariant [0].
>
> This is very convenient, because many popular ZK systems work, or can be made
> to work, over arithmetic circuits over a given field [1,2,3,4]. For EC-based
> ZKPs this field typically has as many elements as the order of the curve
> you're producing the ZKPs on.
>
>
> This means that, e.g., you can prove in zero knowledge operations on secp256k1
>
>     y^2 = x^3 + 7   mod 2^256 - 2^32 - 977
>
> by producing a ZKP on the curve "secq256k1" whose equation [5] is
>
>     y^2 = x^3 + 7   mod (group order of secp256k1)
>
> which is a pretty nifty trick.
>
>
> Doing ZKPs of EC operations on a target group is a generally very useful tool
> because it lets you do ZKPs on deployed cryptosystems, which lets you "bolt on"
> compression, audit trails, avoidance of semi-honest assumptions, etc., and
> potentially layer new applications onto seemingly limited protocols [6].
>
>
> Unfortunately, my trick of swapping the field and curve orders seems to only
> work on j-invariant 0 prime-order fields, and ed25519 is neither. So my question
> is: is there a standard (or at least well-known) (or at least easily findable)
> DL-hard curve whose group of rational points has order 2^255 - 19?
>
>
> Cheers
> Andrew
>
>
>
>
> [0] A j-invariant 0 curve has equation y^2 = x^3 + b and the various values
>      of b give you at most six different isomorphism classes. Not all have
>      prime order, you may have to try a few. But this seems to work very
>      reliably. See
>      https://mathoverflow.net/questions/249982/elliptic-curve-related-equivalence-between-fields-of-different-characteristic
>
> [1] https://eprint.iacr.org/2013/507
> [2] http://engineering.nyu.edu/events/2017/10/27/ligero-lightweight-sublinear-zero-knowledge-arguments
> [3] https://eprint.iacr.org/2017/1066
> [4] https://eprint.iacr.org/2018/046
>
> [5] The fact that both equations have exactly the same coefficients is a
>      coincidence. In particular the two 7s, being in different ground fields,
>      are actually completely unrelated objects even though we use the same
>      symbol for them.
>
> [7] https://www.nasdaq.com/article/scriptless-scripts-how-bitcoin-can-support-smart-contracts-without-smart-contracts-cm882818
>
>
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves