algebra icon indicating copy to clipboard operation
algebra copied to clipboard

Add tom-256 curve

Open ineiti opened this issue 1 year ago • 1 comments

For our experiments we would like to add the tom-256 curve. It is described in the following paper:

https://eprint.iacr.org/2021/1183

And the parameters can be found here:

https://neuromancer.sk/std/other/Tom-256

I started a first implementation here, but it's my first time adding something to arkworks-rs/algebra, and the test fail. The base-point is not on the curve !

https://github.com/c4dt/algebra/pull/1

ineiti avatar Jan 24 '25 16:01 ineiti

Fq and Fr should be set as

// fq.rs
#[derive(MontConfig)]
#[modulus = "115792089210356248762697446949407573530594504085698471288169790229257723883799"]
#[generator = "6"]
...

// fr.rs
#[derive(MontConfig)]
#[modulus = "115792089210356248762697446949407573530086143415290314195533631308867097853951"]
#[generator = "6"]
....

I got the generators using Sage and ensured that both are quadratic non-residues (as per the docs of MontConfig macro) so the generators should likely be fine. And both of them being 6 is just incidental.

Sage code

// Fq's generator
tom256_q = GF(115792089210356248762697446949407573530594504085698471288169790229257723883799)
gen_q = tom256_q.multiplicative_generator() // gen_q is 6
assert tom256_q(6).is_square() == False       // 6 is quadratic non-residue

// Fr's generator 
tom256_r = GF(115792089210356248762697446949407573530086143415290314195533631308867097853951)
gen_r = tom256_r.multiplicative_generator() // gen_r is 6
assert tom256_r(6).is_square() == False       // 6 is quadratic non-residue

But I am not sure if I should set small_subgroup_base and small_subgroup_power.

Config::mul_by_a should not be overridden for Tom-256 as a is non-zero.

lovesh avatar Jan 26 '25 16:01 lovesh