[curves] Another try at point compression

[Robert Ransom]

On 12/20/14, Trevor Perrin <trevp at trevp.net> wrote:
> On Wed, Dec 17, 2014 at 8:12 AM, Robert Ransom <rransom.8774 at gmail.com>
> wrote:
>> On 12/14/14, Michael Hamburg <mike at shiftleft.org> wrote:
>>> * there is no fingerprinting or splitting attack based on how your
>>> signature
>>> scheme handles the cofactor;
>>
>> This is a major benefit -- major enough that I would seriously
>> consider using Curve1174 instead of Curve25519 in an anonymity system
>> or any privacy system that needs to permit alternative
>> implementations, despite the relative lack of implementation
>> experience.
>
> I believe your concern is this Ed25519 implementation choice, due to
> the cofactor:
>
> "The verifier is permitted to check this stronger equation [doesn't
> clear cofactor] However this is not required" (page 7):
> http://ed25519.cr.yp.to/ed25519-20110926.pdf

Yes.

> The "stronger" equation is used in "Fast single-signature
> verification", and clearing the cofactor is done in "Fast batch
> verification".  You've pointed out this choice would distinguish
> implementations in an anonymity context (e.g. over Tor).
>
> https://moderncrypto.org/mail-archive/curves/2014/000266.html
>
> This seems easy to avoid by recommending the stronger check in
> anonymity systems.  I assume most libraries implement fast
> single-signature verification, so already do this.
>
> That means avoiding batch verification in anonymity systems.  I don't
> think batch verification matters in practice - the only plausible use
> case I can think of is servers handling large volumes of signatures.
> However, 25519 is so fast (10K+ ops per second per core) that compute
> costs for large services are going to be relatively small, and not
> much is gained by a further 2x optimization (client-side optimization
> is more important).

I would prefer that single-signature verification be modified to only
check the equation 8R = 8hA + 8sB, so that it becomes
indistinguishable from batch verification -- at least that can be
enforced if some of the services which generate signatures add points
of small order to their R values.

But there's still a trade-off between making single-signature
verification as fast as possible and making batch verification as fast
as possible.  I would greatly prefer to eliminate that trade-off.


> Anyways, I still contend that the cofactor is a minor "security
> consideration".  Switching to a less-widely-used curve and more
> complex encoding to avoid it seems like adding more risk than you're
> eliminating.

No, this is the same sort of ‘hazard elimination’ that Dr. Bernstein
has been advocating (and implementing), e.g. with Curve25519 ECDH.

It's too bad that this point format will require cofactor 4 (although
there are good mathematical reasons for that) -- that either makes key
generation more complicated or decreases the secret key length by an
extra bit (regardless of the field).  Any implementation of signing
would already need to reduce scalars modulo the group order (in order
to compute s), so that bit of extra complexity won't hurt signature
software, but it sucks for ECDH.  Curve25519 remains better for ECDH.


Robert Ransom