[curves] Finalizing XEdDSA

[Peter Schwabe]

Trevor Perrin <trevp at trevp.net> wrote:

Dear Trevor,

> One last tweak to consider is clearing the cofactor in verification.
> Currently XEdDSA does "cofactorless verification", i.e. it takes a
> signature (R, s) and checks R == sB - hA.  We could change it to cR ==
> c(sB - hA).  VXEdDSA would be unchanged.
> 
> This has no effect on valid signatures, but adding the cofactor
> multiplication means signers could create signatures with a few
> different values of R for the same s (which has no security relevance,
> I think, and does not cause "malleability" because the signer's choice
> of R is included in the hash).
> 
> Advantages to current "cofactorless" approach:
>  - matches existing code like (ref10, libsodium)
>  - less code, doesn't need a "point comparison" function (can encode,
> then compare)
>  - less computation (by tiny amount, 1% or something)
> 
> Advantages to changing to "cofactor" approach:
>  - Allows batch verification of signatures (I'm told), that can give ~2x speedup
>  - Preferred approach in Ed25519 paper, "EdDSA for more curves" paper,
> and CFRG draft

The Ed25519 paper says 

  "The verifier is /permitted/ to check this stronger equation and
  to reject alleged signatures where the stronger equation does not
  hold. However, this is not /required/; checking that
  8SB=8R+8H(\encode{R},\encode{A},M)A is enough for security."


You could decide to do the same; allowing both for verification in the
specification and leaving the choice to the implementation. If I
understand correctly, this gives you the advantages of both approaches,
right?


Best regards,

Peter
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 811 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161101/64688e68/attachment.sig>