Paper 2018/186
RKHD ElGamal signing and 1way 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 1way (or unforgoable, to be precise). Other free sums are 1way under plausible assumptions: elliptic curve discrete logs, integer factoring, and secure smallkey WegmanCarterShoup authentication. Yet other free sums of 1way functions (integerfactoring based) fail to be 1way. 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 AgnewMullinVanstone 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 ElGamal signature
 Contact author(s)
 danibrown @ blackberry com
 History
 20180220: received
 Short URL
 https://ia.cr/2018/186
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/186, author = {Daniel R. L. Brown}, title = {RKHD ElGamal signing and 1way sums}, howpublished = {Cryptology ePrint Archive, Paper 2018/186}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/186}}, url = {https://eprint.iacr.org/2018/186} }