# 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?

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. • The question's statement should add that$p$has$n$bits when generating the group, right? – fgrieu May 16, 2018 at 20:03 • @fgrieu indeed, it would probably be better to put such a requirement in there, even though you could formulate it as a constraint on$\mathcal G$and "outsource" it, but then "'technically correct' - not the best kind of correct in cryptography"... May 16, 2018 at 20:06 • "$\mathbb Z_p$should be used" Why?$\mathbb Z_p$can be used;$\mathbb Z_p^*\$ can be used too. It makes a negligible difference. May 17, 2018 at 4:56