dusk-network / jubjub

Implementation of the Jubjub elliptic curve group
Other
4 stars 12 forks source link

Add `UniScalarRng` #123

Closed moCello closed 11 months ago

moCello commented 11 months ago

Resolves: #121

moCello commented 11 months ago

After extensive discussions we decided to not change the random scalar generation because it was deemed secure enough for our purpose:

We will use this paper to determine whether the current implementation of the random scalar implementation as done in the Field trait implmentation is cryptographically safe.

In the current implementation of random, we sample a random element with 512 bits, and reduce it by the modulo of the field of JubJubScalar to generate a valid scalar.

For JubJubScalar we have:

p := 0x0e7db4ea6533afa906673b0101343b00a6682093ccc81082d0970e5ed6f72cb7
p = 6554484396890773809930967563523245729705921265872317281365359162392183254199

and

s := 2^512
s = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

To check whether the above approach is secure, we do the following:

For p < s calculate r and m so that

s = rp + m

This leads to:

r := 2045593080716281616348203381729468609728209645786990242449482205581148743408809

and

m := s - p * r
m = 2244478849891746936202736009816130624903096691796347063256129649283183245105

Now we can check whether:

r > 2^64 * root(m/p)
r > 2^64 * root(0.34243408237518300501)
r > 18446744073709551616 * 0.58517867559847308999

This clearly holds true, which means that we fall in the first conversion of the paper above, and can safely sample an element from the field over 2^512 and take it modulo p.

This concludes that we don't need to make any adjustments to the current implementation of random scalar generation.