Andrew Poelstra

2018-03-21 12:30:50 UTC

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

--

Andrew Poelstra

Mathematics Department, Blockstream

Email: apoelstra at wpsoftware.net

Web: https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese

who can never find their peace,

whether north or south or west or east"

--Joanna Newsom

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

--

Andrew Poelstra

Mathematics Department, Blockstream

Email: apoelstra at wpsoftware.net

Web: https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese

who can never find their peace,

whether north or south or west or east"

--Joanna Newsom