Subject: [Cfrg] ECDSA_CFRG tweak: projective s

From: Dan Brown <[email-masked]>
Date: Tue, 4 Aug 2015 16:15:05 +0000

This is a _contingency_ proposal, in case CFRG wants to avoid _requiring_
signer inverting mod the group order, yet still wants some of the benefits
of ECDSA_CFRG.

At a high level: in the tweaked proposal, (R; t:u) is valid if and only if
(R, t/u) is valid in the original ECDSA_CFRG proposal.

Reminder: (R,s) is a valid ECDSA_CFRG signature if and only if sR = h(R,M)G
+ f(R)A, where A is the signer's public key.

Reminder: I prefer h(R,M) for the reasons DJB has mentioned (internal
collision resilience). If the CFRG chairs rules that the h(R,M) option (of
three other proposals) is consistent with IUF requirements, then my tweak
would adopt h(R,M) instead of h(M,R).  So, for the time being I'll write
h(R,M) instead.

Downsides: the t:u part of the tweak results in:
- larger signature (we might allow compression for t=1 and u=1 special
cases),
- possible complexity, i.e. more chances for the signer to mess up (see next
point),
- larger subliminal/kleptographic channel,
- possible additional IPR.

Reminder of how t:u avoids inversions:

At a high level, it is projective coordinates, which should be familiar to
ECC implementers.

For the signer:
The signer computes ephemeral secret nonce r, as per usual.
The signer computes some _secret_ multiplier m, at least pseudorandomly,
perhaps non-deterministically.
The signer computes t=(h(R,M)+f(R)a)m and u=rm, all mod group order.

Note: I think that this m corresponds to multiplicative mask that I used in
the pseudocode for ECDSA_CFRG signature generation.  In other words,
ECDSA_CFRG has one more step, which is to compute s = t/u.  The inversion of
u is the masked inversion of r.

For the verifier:
Actually, ECDSA_CFRG verification already _avoids_ inversion, since the
ECDSA_CRFG verification equation has no inversion.  

That said, to speed things up, a verifier can invert one of the
coefficients, to replace a triple-scalar multiply (2 variable base, one
fixed base) by a double-scalar-multiply (one variable, one fixed).  A faster
verifier might also re-scale to provide half-length multipliers for the
variable bases (R and A), which helps when a heavily optimized fixed-base
multiply implementation is available --- though this verifier should seek a
license from Certicom/BlackBerry.  In the t:u setting, the signer can help
the verifier with this inversion - see further below.

In some exceptional cases, the signer can try to compress t:u
- by setting u=1, essentially reverting to the ECDSA_CFRG proposal.
- by setting t=1, or
- by setting t and u smaller in size by using some variant of the extended
Euclidean algorithm.
These exceptional cases have a greater risk of a side channel, so need some
protections.  The first two can be protected using multiplicative masking
and Fermat's little theorem.  I think the third case can be protected by
multiplicative masking, but I have not checked.  Strictly, these exceptions
might be viewed as violating the CFRG ballot, so the CFRG may want to rule
that these are illegal practices, or to allow them as options at the
implementer's risk.

The signer, again at the cost of the signer evaluating an inverse mod group
order, could also form t:u in a form that speeds up the verifier's task,
pre-computing one of the verifier's speed-ups.  One such trick has t=1.
Another has t and f(R)u (mod group order) as half-length ints (with possible
IPR, as mentioned above).

Best regards,

Daniel Brown
Certicom Research / BlackBerry Standards