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-$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
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- ElGamal signature
- Contact author(s)
- danibrown @ blackberry com
- History
- 2018-02-20: 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 1-way sums}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/186}, year = {2018}, url = {https://eprint.iacr.org/2018/186} }