Subject: Re: [Cfrg] ElGamal * Schnorr: quick idea?

From: Michael Hamburg <[email-masked]>
Date: Fri, 24 Jul 2015 10:22:13 -0700

> On Jul 24, 2015, at 10:09 AM, Dan Brown <[email-masked]> wrote:
> 
> Dear CFRG,
> 
> Kenny asked me off-list if my proposal (ECDSA_CFRG) could be amended to
> avoid inversion mod the group order.
> 
> I told him maybe.
> 
> Then I refreshed my history of signatures by looking into the Handbook of
> Applied Cryptography by Menezes, van Oorschot and Vanstone. 
> 
> Referring to Note 11.70 therein, Table 11.5, row 4 describes a variant of
> ElGamal which requires no inversion to compute s.  If one replaces the h(m)
> by h(m||r) for a wide-hash h, then one has something in the spirit of
> Kenny's request.
> 
> I'll transcribe and translate the relevant notation here, for completeness:
> 
> Signer secret a
> Signer public A = aB
> Signer nonce k
> Signature (R,s) = (kB, ah(m||R)+kf(R))
> Verification sB == h(m||R)Y + f(R)R
> 
> Where f(R) is a direct conversion of point R to an integer.
> 
> Of course, the integer operations are done mod ord(B).  (Please let's not
> use l ;-)
> 
> This is quite like Schnorr, with the additional feature that R (and k) get
> multiplied by f(R), because the hash is put in front of A (and a).
> Incidentally, HAC describes Schnorr using a suffix, not a prefix.

Why would we use this instead of Schnorr?  It’s ultimately equivalent to Schnorr (with h(m,R) = h(m||R)/f(R)), but with an extra f(R) thrown in for no reason.

> In HAC Note 11.71(ii) the intractability of inverting the function R ->
> f(R)R is mentioned as a requirement for that ElGamal variant in the table
> (which I've modified).  Side note: the one-up problem for ECDSA is a similar
> unusual problem involving f, and a requirement for ECDSA.  However, because
> of R in the hash, this problem no longer seems relevant.
> 
> What might be missing for this construction:
> - aegis security: have many people spent many years trying and failing to
> attack this construction?
> - arguable security: has anybody tried to argue its security, e.g. breaking
> this implies breaking that, perhaps assuming some of unicorn model.
> 
> Best regards,
> 
> Daniel Brown
> Certicom Research
> 
> 
> <winmail.dat>_______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Dan Brown <[email-masked]>
Date: Fri, 24 Jul 2015 17:52:49 +0000

> -----Original Message-----
> From: Michael Hamburg [mailto:[email-masked]]
> 
> Why would we use this instead of Schnorr?  It’s ultimately equivalent to
> Schnorr (with h(m,R) = h(m||R)/f(R)), 

[DB] Good point about the equivalence over adjusted hashes. 

> but with an extra f(R) thrown in for no
> reason.
> 
[DB] The reason is to have an inexpensive resilience to as many potential hash failures as possible.  For example, we like Schnorr because of its collision-resilience.  We can generalize this benefit.  Joux has shown that, for some hashes, multicollisions are not much harder to find than collisions.  My presentation mentioned hash deletion, which leads to Schnorr forgery in some case.  Hash deletion is one step worse than a multicollision, so perhaps also not much harder than collisions, for some hashes.  One can argue that this threat is unlikely (i.e. a huge step over multicollisions).  Or, one can use a better hash.  Or, one can modify the signature.   Or, all of the above: these back each other up, providing defense in depth.

Put another way: if we took Schnorr and left out the R from the hash, it would be very insecure.  So, Schnorr definitely relies on the hash doing a good job in its inclusion of R.  In your equivalence, the division by f(R) can be viewed as the signature helping out the hash at its job.  This _seems_ like a cheap way of reducing the trust of the hash.

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 24 Jul 2015 11:52:56 -0700

> On Jul 24, 2015, at 10:52 AM, Dan Brown <[email-masked]> wrote:
> 
> 

[MH] Cheap except that it turns the double-scalarmul into a triple-scalarmul.  I’m not convinced that “helping” the hash does anything in this case, especially since it seems to me that “deletions” are more likely to apply if R is hashed first rather than second.  (Though of course in that case you are vulnerable to collisions.)

— Mike

---

From: Dan Brown <[email-masked]>
Date: Fri, 24 Jul 2015 19:29:51 +0000

> Sent: Friday, July 24, 2015 2:53 PM
> 

[DB] Using this equivalence, one idea is take some form of Schnorr signatures, e.g. EdDSA, and amend the hash used by the vefier, defining it to be h(m,R) = h(m||R)*f(R) mod ord(B) -- where f is decodepoint in DJB's python script.  

The cost of this is an extra mod ord(B) multiplication, which is small.  The benefit is extra robustness (perhaps redundant) against hash failures.  As often the case, it's difficult to compare the small cost to the remote benefit.

Again, unlike my proposal, ECDSA_CFRG, I do not have argument that certain kinds of forgery of Schnorr signature with this modification imply forgery of a widely accepted signature scheme: I don't how to transform the message and signature from one scheme to the other scheme.

So, I leave it to the four other EC scheme proposal teams, whether they would like incorporate this Schnorr modification. 

> 
> [MH] Cheap except that it turns the double-scalarmul into a triple-scalarmul.
> I’m not convinced that “helping” the hash does anything in this case, especially
> since it seems to me that “deletions” are more likely to apply if R is hashed first
> rather than second.  

[DB] In the form I mentioned above the extra cost is not as much as you said, it is just one mod ord(B) multiplication.  

>(Though of course in that case you are vulnerable to
> collisions.)
[DB] Well, at least for wide-pipe hashes, you need an internal collision, not just a collision, the best known internal collision attack in a wide pipe are much harder to find than collisions.