[curves] Finalizing XEdDSA
Ron Garret
ron at flownet.com
Tue Nov 1 09:04:15 PDT 2016
On Nov 1, 2016, at 7:14 AM, Peter Schwabe <peter at cryptojedi.org> wrote:
> 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?
Possibly naive question: What is “this stronger equation” that the paper refers to? Because the immediately preceding equation is:
SB = rB + H(\encode{R},\encode{A},M)aB = R + H(\encode{R},\encode{A},M)A
which is actually two equations. The first:
SB = rB + H(\encode{R},\encode{A},M)aB
relies on the secret key a, so that does not seem particularly useful. But the second equation:
SB = R + H(\encode{R},\encode{A},M)A
Is (AFAICT) identical to the earlier “weaker” equation:
8SB = 8R+8H(\encode{R},\encode{A},M)A
except for factoring out the 8’s. (Where did those 8’s come from anyway? They seem completely unmotivated.)
What am I missing?
rg
More information about the Curves
mailing list