Discrete Logarithm Problem (DLP)

Multiplicative Notation

• $g^x=r(modp)$
• $g:generator$
• $r:1<r<p$
• $g^x$ will give a result that is uniformly distributed between 1 and (p - 1), inclusive
• Given g, r and p, it is hard to deduce x
• If p is small, it is easy to find x
• If p is very large, it is hard to find x

Additive Notation

• Given $E$ is a standard elliptic curve and arbitrary nonzero $g,g^{\prime }\in E$
• $n\cdot g=g^{\prime }$
• where $n\in F_q$ and $n\in (N)$ (e.g. $n$ is 254-bit if $E$ is BN254 )
• $n$ is hard to find
• However, given $g$ and $n$, one can compute $n\cdot g$ in $O(logn)$

General

• An instance of the Hidden Subgroup Problem (HSP)