On Sun, Nov 07, 2021 at 09:44:43AM -0800, Benjamin Kaduk wrote: > Hi Rene, > > While you may be an experienced enough cryptographer to be comfortable > asserting that there is "no new crypto" in these procedures, I contend that > being able to make that assessment does actually require some > cryptographic knowledge. In particular, the question is not just that > (r,s) and (r,-s) are either both valid solutions to the ECDSA signing > equation or both not solutions; rather, it is whether making use of this > property has any interaction with the ECDSA assumptions that must be taken > into account for use in a protocol scenario. While the fact that it is a > transform solely on public data suggests that there should not be any risk, > I, for one, am not willing to risk the reputation of the IETF on just my > own personal analysis of this case.
What I think are more relevant properties: While this does not prove that batch verification is safe (e.g., it relies on random numbers and if those are predictable, it is not safe). However, since everything is easily computable and all parameters are considered public (e.g, the private key appears nowhere), these two theorems establish that ECDSA and ECDSA* are of strictly equal security in single verification. Theorem 1: If (r,s) is valid ECDSA signature for message m with key Q, then ((H(m)/s)*G+(r/s)*Q),s) is valid ECDSA* signature for message m with key Q. Proof: Since (r,s) is valid ECDSA signature for message m with key Q, by assumption it holds that: r = x((H(m)/s)*G+(r/s)*Q) Now, let R = (H(m)/s)*G+(r/s)*Q) Substituting latter to former gives r = x(R). Therefore: R = (H(m)/s)*G+(x(R)/s)*Q) Which is impiles that (R,s) = ((H(m)/s)*G+(r/s)*Q),s) is a valid ECDSA* signature. Q.E.D. Theorem 2: If (R,s) is valid ECDSA* signature for message m with key Q, then (x(R),s) is valid ECDSA signature for message m with key Q. Proof: Since (R,s) is valid ECDSA* signature for message m with key Q, by assumption it holds that: R = (H(m)/s)*G+(x(R)/s)*Q) Now, let r = x(R). Substituting latter to former gives: R = (H(m)/s)*G+(r/s)*Q Taking x() of both sides gives: x(R) = x(H(m)/s)*G+(r/s)*Q) Which by definition equals: r = x(H(m)/s)*G+(r/s)*Q) Which impiles that (x(R),s) is a valid ECDSA signature. Q.E.D. -Ilari _______________________________________________ COSE mailing list [email protected] https://www.ietf.org/mailman/listinfo/cose
