§13 One-way Functions, Cyclic Groups, Discrete Log and Diffie-Hellman Problems

One-Way Functions

One-Way Functions: Definition

• Definition. The inverting experiment $\operatorname{Invert}_{\mathscr{A}, f}(n)$:
  1. Choose uniform $x \in \{0,1\}^n$, and compute $y := f(x)$.
  2. Adversary $\mathscr{A}$ is given $1^n$ and $y$ as inputs. $\mathscr A$ outputs $x'$.
  3. $\mathscr A$ succeeds and the experiment evaluates to $1$ if and only if $f(x') = y$.
• Definition. A function $f : \{0,1\}^* \rightarrow \{0,1\}^*$ is one-way if the following two conditions hold:

  1. (Easy to compute): There is a polynomial-time algorithm that on input $x$ outputs $f(x)$.

  2. (Hard to invert): For all PPT algorithms $\mathscr A$ there is a negligible function $\epsilon(n)$ such that:

     $$\Pr [\operatorname{Invert}_{\mathscr{A}, f}(n) = 1] \le \epsilon(n)$$

A One-Way Function based on the Factoring Assumption

• Given $1^n$ and $GenModulus$, define the (deterministic) function $f_{Gen}$ as follows:
  • Input: String $x$ of length $n$.
  • Output: Integer $N$.
  • compute $(N, p, q) := GenModulus(1^n; x)$, i.e., run $Gen(1^n)$ using random tape $x$.
  • return $N$.
• Theorem. If the Factoring problem is hard relative to $GenModulus$, then $f_{Gen}$ is a one-way function.

Cyclic Groups

Order of a Group Element

• Definition. Let $\mathbb{G}$ be a finite group of order $m$. Let $g \in \mathbb{G}$ be an arbitrary element. The order of $g$ is the smallest positive integer $i$ such that $g^i = 1$.
  • Let $\mathbb{G}$ be a finite group of order $m$. Let $g \in \mathbb{G}$ be an arbitrary element.
  • Consider the set $\langle g \rangle := \{g_0, g_1, \ldots \}$. By Fermat’s Little Theorem, we know that $g^m = 1$.
  • Let $i \le m$ be the smallest positive integer for which $g^i = 1 ( = g^0)$. $\langle g \rangle = \{g^0, \ldots, g^{i-1}\}$.
  • $\langle g \rangle$ contains exactly $i$ elements. Furthermore, $\langle g \rangle$ is a subgroup of $\mathbb{G}$ for any $g$.

Cyclic Groups

• Definition. If an element $g \in \mathbb{G}$ has order $| \mathbb{G} | = m$, then $\langle g \rangle = \mathbb{G}$.

  In this case, we call $\mathbb{G}$ a Cyclic Group and say that $g$ is a Generator of $\mathbb{G}$.

Cyclic Groups: Groups of Prime Order

• Theorem: If $\mathbb{G}$ is a group of prime order $p$, then $\mathbb{G}$ is cyclic.

  Furthermore, all elements of $\mathbb{G}$ except the identity element are generators of $\mathbb{G}$.

Cyclic Groups: $\mathbb{Z}^*_p$

• Theorem: If $p$ is prime, then $\mathbb{Z}^*_p$ is cyclic (of order $p - 1$).

Discrete Log and Diffie-Hellman Problems

Discrete-Logarithm problem

• Fix a cyclic group $\mathbb{G}$ of order $q$, and generator $g \in \mathbb{G}$.

  We know that: $\{g_0, g_1, \ldots, g_{q-1}\} = \mathbb{G}$.

  Equivalently, for every $h \in \mathbb{G}$, there is a unique $x \in \mathbb{Z}_q$, such that $g^x = h$.

• Define $\log_g h$ to be this $x$. This is the discrete logarithm of $h$ with respect to $g$ (in the group $\mathbb{G}$).

  Discrete Logarithm problem in $\mathbb{G}$: Given $g \in \mathbb{G}$, and uniform $h \in \mathbb{G}$, compute $\log_g h$.

• Discrete Logarithms obey same rules as standard logs:

  $log_g 1 = 0$

  $log_g h^r = [r \cdot log_g h \bmod q]$

  $log_g (h_1 h_2) = [(\log_g h_1 + \log_g h_2) \bmod q]$

Discrete-Logarithm Experiment $\operatorname{DLog}_{\mathscr{A},\mathscr{G}}(n)$

• For a group generation algorithm $\mathscr{G}$, algorithm $\mathscr{A}$, and parameter $n$, define the experiment $\operatorname{DLog}_{\mathscr{A},\mathscr{G}}(n)$:
  1. Run $\mathscr{G}(1^n)$ to obtain $(\mathbb{G}, q, g)$, i.e., $(\mathbb{G}, q, g) \leftarrow \mathscr{G}(1^n)$.
  2. Choose uniform $h \in \mathbb{G}$.
  3. $\mathscr A$ is given $(\mathbb{G}, q, g, h)$, and outputs $x \in \mathbb{Z}_q$.
  4. $\mathscr{A}$ succeeds and the experiment evaluates to $1$ if and only if $g^x = h$, and $0$ otherwise.

Discrete-Logarithm problem: Security

• Definition. The Discrete Logarithm problem is hard relative to $\mathscr{G}$ if for all probabilistic polynomial time algorithms $\mathscr{A}$, there exists a negligible function $\epsilon(n)$ such that:

  $$\Pr [\operatorname{DLog}_{\mathscr{A},\mathscr{G}}(n) = 1] \le \epsilon(n)$$

Diffie-Hellman Problems: Computational Diffie-Hellman (CDH)

• Fix cyclic group $\mathbb{G}$ of order $q$, and generator $g \in \mathbb{G}$.

  Given elements $h_1, h_2 \in \mathbb{G}$, define $\operatorname{DH}_g (h_1, h_2) := g^{\log_g h_1 \cdot \log_g h_2}$.

  That is, if $h_1 = g^{x_1}$, $h_2 = g^{x_2}$, then $\operatorname{DH}_g (h_1, h_2) = g^{x_1 \cdot x_2} = h^{x_2}_1 = h^{x_1}_2$.

• CDH problem in $\mathbb{G}$ (Informal): Given $g \in \mathbb{G}$, and uniform $h_1, h_2 \in \mathbb{G}$, compute $\operatorname{DH}_g (h_1, h_2)$.

Diffie-Hellman Problems: Decisional Diffie-Hellman (DDH)

• Fix cyclic group $\mathbb{G}$ of order $q$, and generator $g \in \mathbb{G}$.

  Given elements $h_1, h_2 \in \mathbb{G}$, define $\operatorname{DH}_g (h_1, h_2) := g^{\log_g h_1 \cdot \log_g h_2}$.

  That is, if $h_1 = g^{x_1}$, $h_2 = g^{x_2}$, then $\operatorname{DH}_g (h_1, h_2) = g^{x_1 \cdot x_2} = h^{x_2}_1 = h^{x_1}_2$.

• DDH problem in $\mathbb{G}$ (Informal): Given $g \in \mathbb{G}$, and uniform $h_1, h_2 \in \mathbb{G}$, distinguish $\operatorname{DH}_g (h_1, h_2)$ from a uniform group element in $\mathbb{G}$.

DDH problem (Formal)

• Let $\mathscr{G}$ be a group-generation algorithm. On input $1^n$, $\mathscr{G}$ outputs a cyclic group $\mathbb{G}$, its order $q$, (with bit length $\|q\| = n$), and a generator $g$.

• Definition. The DDH problem is hard relative to $\mathscr G$ if for all PPT algorithms $\mathscr{A}$, there is a negligible function $\epsilon(n)$ such that:

  $$\left|\operatorname{Pr}\left[\mathscr{A}\left(\mathbb{G}, q, g, g^{x}, g^{y}, g^{z}\right)=1\right]-\operatorname{Pr}\left[\mathscr{A}\left(\mathbb{G}, q, g, g^{x}, g^{y}, g^{x \cdot y}\right)=1\right]\right| \leq \epsilon(n)$$

  where the probabilities are taken over the experiment in which $\mathscr{G}(1^n)$ outputs $(\mathbb{G}, q, g)$ and then uniform $x, y, z \in \mathbb{Z}_q$ are chosen.

— Mar 21, 2023

§13 One-way Functions, Cyclic Groups, Discrete Log and Diffie-Hellman Problems by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.