Crate babygiant_alt_bn128

This crate is accompanying the Noir library noir-elgamal.

do_compute_dlog is supposed to be called as a last step during decryption, taking as input the value returned by the exp_elgamal_decrypt Noir function.

This code is heavily inspired by zkay.

Two main differences with respect to zkay :

1/ We replaced scalar multiplication inside the baby steps loop by point addition, this lead to a 7x speedup on average, as well as multithreading for another 2.5x improvement allowing to decrypt u40 instead of just u32 in less than 6 seconds (on a Mac M1 chip), this is why we replaced the max_bitwidth argument from 32 to 40 in the baby_giant call.

Even in the browser (see the accompanying npm package), it is now practical to decrypt a u40 in less than 9s in the worst case (WASM overhead) when using a num_threads between 5 and 8.

2/ Another big difference is that the imported arkworks library uses the Edwards form instead of the Twisted Edwards form which is used in Noir for the Baby Jubjub curve, so we did a coordinate transform to encode points in the Twisted Edwards form instead of the Edwards form, for using the same format as the Noir implementation.

Functions

• do_compute_dlog
  This function will compute the Discrete Logarithm of a point on the Baby Jubjub curve, in Twisted Edwards form.