**RKHD ElGamal signing and 1-way sums**

*Daniel R. L. Brown*

**Abstract: **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.

**Category / Keywords: **public-key cryptography / ElGamal signature

**Date: **received 14 Feb 2018

**Contact author: **danibrown at blackberry com

**Available format(s): **PDF | BibTeX Citation

**Version: **20180220:014402 (All versions of this report)

**Short URL: **ia.cr/2018/186

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]