search

hyperledger / anoncreds-clsignatures-rs

Apache License 2.0
7 stars 12 forks source link

Add checks to quadratic residue sampling #30

Closed doowt closed 1 year ago

doowt commented 1 year ago

To sample a quadratic residue mod n uniformly at random, one technique is to sample an integer between 1 and n-1, check that it is invertible, and square it, e.g. see here.

The added code ensures the randomly-sampled element that gets squared is invertible (which also implies it is non-zero, so no need to check it is non-zero separately).

In normal usage of this function for AnonCreds, n = p * q where p and q are large primes, so the probability that an element is not invertible is only 1 - (p-1)*(q-1) / (p*q) = 1/p + 1/q - 1/(p*q), which means the expectation on the number of iterations of the while loop is very close to 1.

swcurran commented 1 year ago

Thanks for the contribution. Your commit needs to have DCO sign off (DCO - Developer Certificate of Origin - https://github.com/apps/dco). Could you please update your commit to include that signoff? Details are on the “Details” link of the failed “DCO” check. Thanks!