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).


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.


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