[Resource Topic] 2018/186: RKHD ElGamal signing and 1-way sums

Welcome to the resource topic for 2018/186

RKHD ElGamal signing and 1-way sums

Authors: Daniel R. L. Brown


An ECDSA modification with signing equation s=rk+hd has the properties that the signer avoids modular inversion and that passive universal forgery is equivalent to inverting a sum of two functions with freely independent inputs. Let \sigma:s\mapsto sG and \rho:R\mapsto -rR where r is an integer representation of the point R. The free sum of \rho and \sigma is \nu: (R,s) \mapsto \rho(R)+\sigma(s). A RKHD signature (R,s) verifies if and only if \nu(R,s) = hQ, where h is the hash of the message and Q is the public key. So RKHD security relies upon, among other things, the assumption that free sum \nu is 1-way (or unforgoable, to be precise). Other free sums are 1-way under plausible assumptions: elliptic curve discrete logs, integer factoring, and secure small-key Wegman–Carter–Shoup authentication. Yet other free sums of 1-way functions (integer-factoring based) fail to be 1-way. The ease with which these free sums arise hints at the ease determining RKHD security. RKHD signatures are very similar to ECGDSA (an elliptic curve version Agnew–Mullin–Vanstone signatures): variable-G forgers of the two schemes are algorithmically equivalent. But ECGDSA requires the signer to do one modular inversion, a small implementation security risk.

ePrint: https://eprint.iacr.org/2018/186

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .