Paper 2018/186

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-$$ forgers of the two schemes are algorithmically equivalent. But ECGDSA requires the signer to do one modular inversion, a small implementation security risk.