Discrete Logarithm Problem

DLP

Computational Diffie–Hellman Problem; Elliptic Curve Discrete Logarithm Problem; Function Field Sieve; Generic Attacks Against DLP; Number Field Sieve for the DLP

Let G be a cyclic group of order n, and g be a generator for G. Given an element \(y \in G\), the discrete logarithm problem is to find an integer x such that

The discrete logarithm problem has been of particular interest since Diffie and Hellman (Diffie-Hellman Key Agreement) invented a cryptographic system based on the difficulty of finding discrete logarithms (a similar system was created around the same time by Malcolm Williamson at the Government Communications Headquarters (GCHQ) in the UK, but not revealed until years later).

Any finite group may be used for a Diffie-Hellman system, but some are more secure than others. The main groups used are:

• The multiplicative subgroup of a finite field GF(q), with q a prime or a power of 2

• The points on an...

Authors and Affiliations

1. IDA Center for Communications Research, 4320 Westerra Court, 92121, San Diego, CA, USA

   Dan Gordon Dr.

Editors and Affiliations

1. Department of Mathematics and Computing Science, Eindhoven University of Technology, 5600 MB, Eindhoven, The Netherlands

   Henk C. A. van Tilborg

2. Center for Secure Information Systems, George Mason University, Fairfax, VA, 22030-4422, USA

   Sushil Jajodia

Reprints and permissions

© 2011 Springer Science+Business Media, LLC

Policies and ethics