From aurore.guillevic at inria.fr Wed Aug 21 09:00:46 2024 From: aurore.guillevic at inria.fr (Aurore Guillevic) Date: Wed, 21 Aug 2024 18:00:46 +0200 Subject: [curves] Curve with group order 2^255-19 In-Reply-To: <20180321123050.GG9082@boulet.lan> References: <20180321123050.GG9082@boulet.lan> Message-ID: <51a4397f-718f-4f8e-9de4-a114f580b797@inria.fr> 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 From apoelstra at wpsoftware.net Wed Aug 21 14:27:46 2024 From: apoelstra at wpsoftware.net (Andrew Poelstra) Date: Wed, 21 Aug 2024 21:27:46 +0000 Subject: [curves] Curve with group order 2^255-19 In-Reply-To: <51a4397f-718f-4f8e-9de4-a114f580b797@inria.fr> References: <20180321123050.GG9082@boulet.lan> <51a4397f-718f-4f8e-9de4-a114f580b797@inria.fr> Message-ID: 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: