sipa/bips

bip-schnorr: Inaccurate proof of quadratic residuosity

hebasto opened this issue · 2 comments

hebasto commented

From footnote 9:

Given a candidate x, the valid Y coordinates are the square roots of c = x3 + 7 mod p and they can be computed as y = ±c(p+1)/4 mod p (see Quadratic residue) if they exist, which can be checked by squaring and comparing with c. Due to Euler's criterion it then holds that c(p-1)/2 = 1 mod p. The same criterion applied to y results in y(p-1)/2 mod p = ±c((p+1)/4)((p-1)/2) mod p = ±1 mod p. Therefore y = +c(p+1)/4 mod p is a quadratic residue and -y mod p is not.

This part of equation y(p-1)/2 mod p = ±c((p+1)/4)((p-1)/2) mod p is not correct for the minus sign.

For the strict proof:

  1. y(p-1)/2 mod p = (c(p+1)/4)(p-1)/2 mod p = (c(p-1)/2)(p+1)/4 mod p = 1 mod p; therefore, every y = +c(p+1)/4 mod p is a quadratic residue
  2. there are (p-1)/2 residues and (p−1)/2 nonresidues; therefore, every -y = -c(p+1)/4 mod p is not a quadratic residue

My higher education was not in English, so I kindly ask anyone with good academic English to make a PR.

jonasnick commented

I fail to see why the existing proof is incorrect but I totally agree that this section needs to be reworked. For one, it needs to be stated what exactly is proven.

To prove: c mod p is a QR => y = b*c(p+1)/4 mod p is a QR for b = 1 and a non-QR for b = -1

It holds that (-1)(p-1)/2 = -1 because p = 3 mod 4 which implies (p - 1)/2 = 1 mod 2.

For b in {-1, 1} we have

y(p-1)/2 mod p
= (b*c(p+1)/4)(p-1)/2 mod p
= b(p-1)/2 * (c(p-1)/2)(p+1)/4 mod p
= b * 1(p+1)/4 mod p
= b mod p

If that convinces you, I can open a PR to improve the section.

  • 👍1
hebasto commented

@jonasnick

I fail to see why the existing proof is incorrect...

I didn't mean "incorrect", rather "inaccurate" or "loose" ;)

It holds that (-1)(p-1)/2 = -1 because p = 3 mod 4 which implies (p - 1)/2 = 1 mod 2.

Correct. But I'd prefer do not use modular operations with an exponent:

[1] for secp256k1 it holds that p = 3 mod 4 or p = 4k+3
[2] (-1)(p-1)/2 mod p = (p-1)(2k+1) mod p =
=(p2-2p+1)k * (p-1) mod p = 1k * (p-1) mod p = -1 mod p

... I can open a PR to improve the section.

It will be very kind of you.