scipr-lab
Allow curve parameters to bound Fp/Fp2 sqrt
The Tonelli-Shanks Algorithm used in Fp/Fp2 is currently unbounded, so an attack vector exists if someone provides you with a compressed curve point, and you attempt to decompress it, and the sqrt does not terminate. There are provable bounds on the cost for this algorithm that the curve parameters should be able to configure to prevent this kind of attack.
See http://stanford.edu/~jbooher/expos/sqr_qnr.pdf and https://eprint.iacr.org/2012/685.pdf.
See https://github.com/zcash/zcash/issues/1073 as well.
Instead we've decided to enable the "DEBUG" lines which check if it's a square using euler's criterion. (We throw an exception instead of asserting.) This is fine for performance because we don't need to sqrt that often. (We don't perform point compression on the proving/verifying keys.)
New location of the Booher square roots paper https://www.math.arizona.edu/~jeremybooher/expos/sqr_qnr.pdf
