Paper 2018/186

RKHD ElGamal signing and 1-way sums

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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
ElGamal signature
Contact author(s)
danibrown @ blackberry com
2018-02-20: received
Short URL
Creative Commons Attribution


      author = {Daniel R.  L.  Brown},
      title = {RKHD ElGamal signing and 1-way sums},
      howpublished = {Cryptology ePrint Archive, Paper 2018/186},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.