Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Inject uniformly distributed randomness into Scalar::random #129

Closed
moCello opened this issue Nov 16, 2023 · 1 comment
Closed

Inject uniformly distributed randomness into Scalar::random #129

moCello opened this issue Nov 16, 2023 · 1 comment

Comments

@moCello
Copy link
Member

moCello commented Nov 16, 2023

Summary

The current random method for the bls scalar,implemented as part of the Field trait, is not uniformly distributed: because we 'wrap' the scalar at the modulus some scalars in the field are hit more often than others.

We want to implement uniformly distributed randomness (by discarding invalid scalars) but face some complications.

  1. The code in the files that are pulled from upstream (this includes scalar.rs which implements Scalar::random() as part of the Field trait) may not be changed so we don't break backwards compatibility (we removed code that we don't need but left everything else like it is in the upstream crate)
  2. We don't want to have two different implementations of the random scalar generation: the randomness should only change when the underlying random number generator changes. This means we will remove uni_random()

Possible solution design or implementation

  1. Add an instance of a random number generator that wraps a generic rng and overrides fill_bytes so that only canonical scalars are generated.
  2. Remove the Field trait implementation from 'src/scalar.rs' and implement the trait in 'src/scalar/dusk/rs'. That way we can change the implementation of random() as we see fit

Additional context

The same needs to be done for jubjub scalars

moCello added a commit that referenced this issue Nov 16, 2023
moCello added a commit that referenced this issue Nov 17, 2023
moCello added a commit that referenced this issue Nov 17, 2023
moCello added a commit that referenced this issue Nov 17, 2023
moCello added a commit that referenced this issue Nov 21, 2023
moCello added a commit that referenced this issue Nov 22, 2023
moCello added a commit that referenced this issue Nov 22, 2023
moCello added a commit that referenced this issue Nov 22, 2023
moCello added a commit that referenced this issue Nov 22, 2023
Resolves: #129

Co-authored-by: Victor Lopez <vhrlopes@gmail.com>
@moCello
Copy link
Member Author

moCello commented Nov 29, 2023

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

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 BlsScalar to generate a valid scalar.

For BlsScalar we have:

p := 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
p = 52435875175126190479447740508185965837690552500527637822603658699938581184513

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 := 255699135089535202043525422716183576215815630510683217819334674386498370757523

and

m := s - p * r
m = 3294906474794265442129797520630710739278575682199800681788903916070560242797

Now we can check whether:

r > 2^64 * root(m/p)
r > 2^64 * root(0.06283687387289490447)
r > 18446744073709551616 * 0.25067284231223554

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 (which is an array of 64 bytes) and take it modulo p.

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant