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

[Andrew Poelstra]

HI Aurore,


Thanks for posting this! I am not aware of anybody answering my
question anywhere else. And thanks for spending the cycles to find
these curves.

As you point out, the order of E1 is p = 2^255 - 19, so you can do
Curve25519 arithmetic "in the group" of E1. (Not sure what the best
terminology here is; the point is that E1 is group-isomorphic to Z/pZ
which is also a field, so you can sorta pretend like the EC group is
itself a field and do field operations there.) But since Curve25519 has
non-prime order it can't form a cycle.

But...the crypto group, whose order is the full order of Curve25519
divided by 8, does have prime order. So you could imagine a chain
E1 -> Curve25519 -> E3 where E3's field has the same number of elements
as the divided-by-8 number. And maybe you can imagine extending the
chain to eventually cycle back to E1 .... but by the Hasse bound each
step can only bump the order by roughly sqrt(p) (roughly 2^128). So
you would need an EXTREMELY long chain to ever hope to compensate for
the loss of the factor 8 at step 1.

So I believe your result is the best possible for this type of question.



Best
Andrew


On Wed, Aug 21, 2024 at 06:00:46PM +0200, Aurore Guillevic wrote:
> 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
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-- 
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20240821/dcd939ba/attachment.sig>