Discrete logarithm assumption

From CRYPTUTOR

Jump to: navigation, search

The discrete logarithm (DL) assumption is a computational hardness assumption based on cyclic groups.

[edit]

Definition

Let G be a cyclic group of order n with generator g. We will write the group operation as multiplication. The discrete logarithm (DL) problem in G is:

Given h \in G\,, compute r \in \mathbb{Z}_n such that h = g^r\,.

r is called the discrete logarithm of h with respect to base g, and written as \log_g h\,.

The discrete logarithm assumption holds for G if for all non-uniform PPT algorithms A,

\Pr_{h \gets G}[ A(h) = \log_g h ] is negligible.

More precisely, this is a statement about a sequence of groups indexed by security parameter \lceil\log n\rceil, the number of bits needed to represent elements of the group. The running time of A is polynomial in the security parameter, and its probability of correctly computing the discrete logarithm is negligible in the security parameter.

[edit]

The hardness of the DL assumption

The discrete logarithm assumption is a weaker assumption than the decisional Diffie-Hellman assumption. For instance, the DL assumption is assumed to hold for the multiplicative group of integers modulo a large prime, but the DDH assumption is known not to hold.

However, as it is a computational assumption as opposed to an indistinguishability assumption, the DL assumption is less applicable in cryptographic security reductions.

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Discrete_logarithm_assumption"