[messaging] XEdDSA specification

[Trevor Perrin]

On Thu, Oct 20, 2016 at 7:44 PM, Martin Thomson
<martin.thomson at gmail.com> wrote:
> On 21 October 2016 at 10:37, Trevor Perrin <trevp at trevp.net> wrote:
>> I'm happy to announce that a spec for the "XEd25519" signature
>> algorithm used in Signal is available at [1].
>
>
> One comment: the document doesn't really explain why you might want to
> use X- or VX-prefixed variants over the deterministic base algorithms
> (the benefits of which have many words spilled over).


There's some rationales sprinkled throughout, though I guess it's
light on that.  We'll probably discuss design and rationales more on
curves list.

As far as deterministic vs randomized algorithms, that's discussed in Section 8.

Determinism is somewhat of a red herring.  To protect the private key
it's important that different hash "challenges" (h) get different
nonces (r).  Hashing the message into the computation of h and r helps
with this.

However, it's not important that the same h gets the same r.  Adding
randomization on top of hashing adds some resilience against glitching
and side-channel attacks.

If it's important that the same (message, public key) can only give
one output, then you want a VRF.

Trevor