Re: Convenient x-coordinate-only EC signing

On 2006-09-14, xmath <xmath.news@xxxxxxxxx> wrote:
This equation also holds if you use -R instead of R, so it doesn't
matter which one you recover.

You can just as easily pin down one to recover: R S(R), which is the
same as -R S(-R). There's no reason for S to be hard to evaluate: for
example, protocols often take the square root below p/2.

Here's how I'd describe the design elements of your system, starting
from Schnorr's system. Let's say

* the standard base point is B,
* the hash function (such as SHA-256) is H,
* the signer's public key is the x-coordinate X(P) of a point P,
* the signer's secret key is the discrete logarithm of P base B, and
* the signer's random number for this message is z.

Schnorr finds a solution s to the equation sB = zB + H(zB,m) P and
transmits (H(zB,m),s) as a signature; the verifier, given (r,s), checks
that H(sB-rP,m) = r. Here are the design changes:

* Transmit zB (in compressed form) rather than its hash H(zB,m). The
verifier, given (Q,s), checks that sB = Q + H(Q,m) P.

This doesn't affect security. A valid (Q,s) can be converted into a
valid (r,s), namely (H(Q,m),s), and a valid (r,s) can be converted
into a valid (Q,s), namely (sB-rP,s).

Transmitting a hash was one of Schnorr's changes to the ElGamal
system. Transmitting zB is a return to ElGamal style. The only
reason for the change was to save space; that isn't an issue for
compressed elliptic-curve points.

* Replace H by its reciprocal. This doesn't produce an equivalent
system (except in the generic model) but it also doesn't change our
confidence: both H and its reciprocal are hash functions with no
apparent structure.

The verifier, given (Q,s), now checks that sB = Q + H(Q,m)^(-1) P,
i.e., that s H(Q,m) B = H(Q,m) Q + P.

* Transmit t = s H(Q,m) rather than s. This doesn't change security.
The verifier, given (Q,t), now checks that tB = H(Q,m) Q + P, i.e.,
that tB - H(Q,m) Q = P.

At first glance I prefer the sB = Q + H(Q,m) P form. Either way the
verifier has to recover one y-coordinate; the virtue of having this
be the y-coordinate of P is that it can be reused for other
signatures under the same public key. Is there an advantage the
other way?

* Make the signing deterministic. Specifically, replace z with a
secret function of the message, as suggested by Barwood and Wigley
(independently) in 1997.

The secret key used for this function should be separated from the
secret discrete logarithm of P. Both secrets can be derived from a
single key, for example as two separate stream-cipher outputs.

The function itself should be unpredictable, i.e.,
indistinguishable from uniform. Every recent nonceless MAC is
explicitly aiming at this property, not merely unforgeability, so
there are many reasonable choices of function.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago
.

Relevant Pages

  • Re: The New York Times at War With America
    ... Seems to me that should have been a closely held secret within ... Raising the power of the ... Often, it seems, Congress lets them get by with this. ... "It is useless to attempt to reason a man out of what he was never reasoned into." ...
    (soc.retirement)
  • Re: The New York Times at War With America
    ... Seems to me that should have been a closely held secret within ... Raising the power of the ... Often, it seems, Congress lets them get by with this. ... "It is useless to attempt to reason a man out of what he was never reasoned into." ...
    (soc.retirement)
  • Re: September 11, 2006
    ... neighbouring country. ... For the same reason they don't suggest a manned mission to Mars. ... But not because they clearly stated Hussein had no WMD. ... So all those secret prisons that were.... ...
    (misc.transport.trucking)
  • Re: Killing threads
    ... >>>the proces of serving a client for any reason, ... The server thread actually forks new ... > recover a thread that is taking too long for whatever reason. ...
    (comp.programming.threads)
  • Re: safe computer disposal
    ... determined invader can sometimes recover it.For that reason, ... destroy really sensitive data, but physically melts the drive in a furnace. ... people a zero-fill utility is more than sufficient. ...
    (microsoft.public.windowsxp.general)