[SCHNORR BREAK] Use quadratic-residue-y as symmetry breaker #359

pull sipa wants to merge 5 commits into bitcoin-core:master from sipa:legendreschnorr changing 14 files +832 −251

sipa commented at 6:00 PM on November 25, 2015: contributor

(Builds on top of #322)

This changes the implied y coordinate in Schnorr signatures to be the one which is a quadratic residue (the older logic required it to be even). This should be faster, as it doesn't need a modular inverse.
sipa force-pushed on Nov 25, 2015
sipa force-pushed on Nov 25, 2015
sipa force-pushed on Nov 25, 2015
sipa force-pushed on Nov 25, 2015
peterdettman commented at 4:01 AM on November 26, 2015: contributor

I guess it's worth reminding that our sqrt returns the particular root (if any exist) that is a quadratic residue already, which seems relevant to "Verification (method 2)".
sipa commented at 10:00 AM on November 26, 2015: contributor

@peterdettman Yes, I implemented it that way. It could use some explanation indeed.
sipa commented at 11:49 AM on November 26, 2015: contributor

@peterdettman By the way, do you have any intuition for a fast (and hopefully not too complex) algorithm for computing a Jacobi symbol (a|p) (where p is the size of our field)?
[Schnorr API change] Schnorr multisigning API overhaul 2f8a7c5ae1
Move schnorr documentation to markdown document f2514204a8

Add Jacobi symbol test via GMP

Also add native Jacobi symbol test (Andrew)

Rebased-by: Andrew Poelstra
Rebased-by: Pieter Wuille

7e5332e95b

Add function for testing quadratic residue field/group elements. d2dd320f9a
[SCHNORR BREAK] Use y being a quadratic residue as symmetry breaker 5ce3353ef2
sipa force-pushed on Dec 14, 2015
sipa commented at 1:56 PM on June 29, 2016: contributor

Going to do this differently.
sipa closed this on Jun 29, 2016

Contributors