Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

[Nico Williams <[e-mail]>]

On Thu, May 21, 2015 at 06:49:32PM -0400, Watson Ladd wrote:
> On the contrary, 3 would hurt unless properly designed. The danger is
> that the same key could produce a valid signature under two different
> algorithms, thus leading to potential exploitation. We would need to
> ensure there are no collisions in what is fed into the signing
> algorithm.

On the counter-contrary :) if we don't do #3 and only provide an
off-line signature scheme, then some users will *sometimes* sign a hash
of long messages, leaving us with the problem you point out.  But worse:
then we really can't address this in the signature scheme.

Or we could provide an online signature scheme only, and decidedly give
up collision resistance.

By providing both functions we can ensure that one private key for both
begets distinct sub-keys for each -- more hygienic key usage.

Mind you, the key hygiene argument seems unlikely here: the attacker
still has to produce a collision for a hash input they do not entirely
control (particularly the prefix).

> It seems as though determinism, one pass schemes, and avoiding
> collision resistance are at odds, unfortunately, unless someone comes
> up with a good idea.

Agreed.

My ranking from most desirable to easiest to give up is: determinism,
online, collision resistance.  But I admit uneasiness in giving up
collision resistance, but with #3 we can get the right mix of features
on an app-by-app basis.

#3 does mean making the user choose -- a higher cognitive load than we
would prefer to place on them.

Nico
--