# Describing Discrete Logarithm Assumption

I'd like to work out how exactly we should describe the discrete logarithm assumption (say, if we are writing a paper).

Consider this:

Let Gen be a group-generation algorithm on input $1^n$, which outputs a group description $(G, g, p)$ where $G$ is a group, $g$ is a generator of $G$, and $p$ is the order of the group.

Let $(G, g, p)$ be outputted by $Gen(1^n)$. Select $a \in_R \mathbb{Z}^*_p$. We say the discrete logarithm problem is hard with respect to $Gen$ if for every probabilistic polynomial time algorithm, $A$, there exists a negligible function $negl$ such that $Pr[A(g, g^a)= a] = negl(n)$.

My main confusion is about $a \in_R \mathbb{Z}^*_p$.

1. Should $a$ be chosen from $\mathbb{Z}_p$ not $\mathbb{Z}^*_p$ ? After all, $p$ is the order of $G$, so we should be able to pick any element from $G$?

2. Is $\in_R$ a common notation? I've also seen $\leftarrow_R$. Does it make sense as something that says we are picking $a$ uniformly at random?

3. Instead of $a$, should I say that we choose $h \in_R G$? That is, choose a random group element rather than a random exponent?

4. Should the probability be equal to $negl(n)$ or $\leq negl(n)$? Does it matter, and why?

## 1 Answer

Should $a$ be chosen from $\mathbb{Z}_p$ not $\mathbb{Z}^*_p$ ? After all, $p$ is the order of $G$, so we should be able to pick any element from $G$?

Yes, $\mathbb Z_p$ should be used as there is not reason to require that the $a$-th root needs to exist for arbitrary elements.

Is $\in_R$ a common notation? I've also seen $\leftarrow_R$. Does it make sense as something that says we are picking $a$ uniformly at random?
