Subject: [Cfrg] Impact of point compression on security, round 2

From: Watson Ladd <[email-masked]>
Date: Tue, 21 Oct 2014 07:55:03 -0700

Dear all,

What is the result of accepting damaged points? For ECDH a
catastrophe. But for signatures? The answer is it depends on the
details of the signature mechanism. In particular, if signatures
themselves do not contain points, than bad points can only be public
keys, which ends up not violating the standard assumption on
signatures (EUF-CMA). (The reason is only properly formed keys matter)

Unfortunately, batchable signatures contain points, so there is the
possibility of forgery when bad points are accepted. Ultimately, we
need benchmarks of signature verification to see what the impact is.
Note that verification uses only public data, and so can be as
non-constant time for speed as desired. In particular, double-base
mult doesn't usually need side channel protection.

On the gripping hand, some protocols like MQV do need protected
double-scalar addition, and need an honest group to work with. So
compressed point formats do add security to some applications, enable
more performant signatures,  and at a fairly reasonable cost of 10% on
receiving.

I didn't realize this before, which is why I'm thinking about it now.
I think this still supports compression as mandatory, but it's not
nearly as strong a case as it used to be, and in particular for PKIX
uses, probably not necessary.

(We also have to decide: what are we doing about signatures? The best
option in my mind is batchable Schnorr variants, but others might
disagree)

Sincerely,
Watson Ladd