Public Key Cryptography with a Group of Unknown Order
197. R. P. Brent,
Public Key Cryptography with a Group of Unknown Order,
Report PRG-TR-02-00, Oxford University Computing Laboratory,
5 June 2000, 11 pp.
Report:
dvi (20K),
pdf (165K),
ps (85K).
Abstract
We present algorithms for digital signature generation and verification
using public key cryptography over an arbitrary group G.
The algorithms are similar to those of ElGamal,
but do not require a knowledge of the group order.
Forging signatures or determining the secret key
requires the solution of a discrete logarithm problem over G,
or the solution of other problems which appear at least as difficult.
The algorithms can be modified to work over arbitrary semigroups.
Comments
The result
that point counting can be avoided at the cost of a protocol slowdown
was obtained independently by
J. S. Coron et al
[ECC: Do we need to count ?,
Proc. Asiacrypt 99, LNCS 1716, 122-134].
I thank John Pollard
for drawing Coron's paper to my attention.
Go to next publication
Return to Richard Brent's index page