Describing Discrete Logarithm Assumption

Question

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?

Answer 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$?

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?

$\in_R$ is somewhat common, as are $\gets_R$ and $\stackrel{\$}{\gets}$, ideally you will pick one notation and clarify its meaning in a dedicated "notation" section or you just embed the relevant clarification into the wording, e.g. "Select $a\in_R\mathbb Z_p$ uniformly at random".

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?

The definition from the Introduction to Modern Cryptography by Katz and Lindell uses a random group element here, but given that $g^x$ is a random group element for random choice of $x$ and that $g$ is a generator, so there exists exactly one $x$ for each group element, I'd say these definitions are identical.

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

As $\operatorname{negl}(n)$ is any function that grows slower than any polynomial it doesn't matter whether $=$ or $\leq$ is used. However $\leq$ would seem more natural, as you are essentially "bounding" the probability to be negligible and $\leq$ immediately conveys this bounding aspect to the reader instead of hiding it behind the definition of $\operatorname{negl}$.

---

Just for the fun of it, here's the definition from the aforementioned Introduction to modern Cryptography by Katz and Lindell (2nd edition):

$\newcommand{\opn}{\operatorname}\newcommand{\mc}{\mathcal}$

The discrete-logarithm experiment $\opn{DLog}_{\mc A,\mc G}(n)$:

1. Run $\mc G(1^n)$ to obtain $(\mathbb G,q,g)$, where $\mathbb G$ is a cyclic group of order $q$ (with $||q||=n$), and $g$ is a generator of $\mathbb G$.
2. Choose a uniform $h\in\mathbb G$.
3. $\mc A$ is given $\mathbb G,q,g,h$ and outputs $x\in\mathbb Z_q$.
4. The output of the experiment is defined to be $1$ if $g^x=h$, and $0$ otherwise.

Definition 8.62 We say that discrete-logarithm problem is hard relative to $\mc G$ if for all probabilistic polynomial-time algorithms $\mc A$ there exists a negligible function $\opn{negl}$ such that $\Pr[\opn{DLog}_{\mc A,\mc G}(n)=1]\leq\opn{negl}(n)$

_{The book priorly defines $\mathcal G$ to be a function generating a group and $||\cdot||$ to be the bit-length of a number.}