Subject: [Cfrg] Why hash verifier's key?

From: Dan Brown <[email-masked]>
Date: Thu, 23 Jul 2015 16:44:39 +0000

Dear EC signature proposers,

Three of the five submissions hash the verifier's public key, as done in
EdDSA.

The original EdDSA article justifies this step: "the use of A is an
inexpensive way to alleviate the concerns that several public keys could be
attacked simultaneously".

Could one the EdDSA proposers more formally expand on what these "concerns"
might be?  

In case it helps, I will expand on one theoretical concern.  In slide 8 of
my IETF 93 presentation on ECDSA_CFRG, I refer to a hypothetical hash
deletion.  A hash deletion would indeed mean that "several public keys could
be attacked simultaneously".  

In the notation I used on that slide, my Q is EdDSA's A, and if Q had to be
hashed too, then M' would have to begin with Q.  This would force a
hypothetical attacker to find one M' for each target public key Q, which
might well be more difficult.

Of course, that's just one peculiar possibility: perhaps the concerns
alluded to in the EdDSA paper address something more worrisome.

Does inclusion of the verifier's public key in the hash precludes derivation
of the verifier's public key from the signature?

If so, then that might be viewed as a weak form of anonymity, and thus a
slight security bonus.  On the other hand, being able to recover the public
key from a signature might have some other advantages.  For example, one
could compress certificate chain by omitting the issuer's public keys.

Finally, when was inclusion of the verifier's public key in the signature
hash first proposed?

Best regards,

Daniel Brown

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 23 Jul 2015 11:08:40 -0700

Hm.  Public key recovery is incompatible with short Schnorr, but it could
be done with EdDSA-style Schnorr if you dropped the verifier’s key hash.

You could even explicitly design for recovery by making the response
challenge*ephemeral + secret instead of challenge*secret + ephemeral.
That would allow recovery without implementing inversion. But for ordinary
verifications that would require decompressing the ephemeral and so
increase the attack surface if your library has bugs.  It would also make
precomputation on the public key less effective.  Overall, I think this is
probably going too far unless you’re in an embedded environment and
need the space savings, but it’s a thought.

Cheers,
— Mike

> On Jul 23, 2015, at 9:44 AM, Dan Brown <[email-masked]> wrote:
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg