14.4: Exercises

Exercise $14.1$

Let $p$ be an odd prime, as usual. Recall that $\mathbb{Q R}_{p}^{*}$ is the set of quadratic residues mod $p$ - that is, $\mathbb{Q R}_{p}^{*}=\left\{x \in \mathbb{Z}_{p}^{*} \mid \exists y: x \equiv{ }_{p} y^{2}\right\}$. Show that if $g$ is a primitive root of $\mathbb{Z}_{p}^{*}$ then $\left\langle g^{2}\right\rangle=\mathbb{Q} \mathbb{R}_{p}^{*}$

Note: This means that $g^{a} \in \mathbb{Q R}_{p}^{*}$ if and only if $a$ is even $-$ and in particular, the choice of generator $g$ doesn’t matter.

Exercise $14.2$

Suppose $N=p q$ where $p$ and $q$ are distinct primes. Show that $\left|\mathbb{Q} \mathbb{R}_{N}^{*}\right|=\left|\mathbb{Q} \mathbb{R}_{p}^{*}\right| \cdot\left|\mathbb{Q} \mathbb{R}_{q}^{*}\right|$.

Hint:

Exercise $14.3$

Suppose you are given $X \in\langle g\rangle$. You are allowed to choose any $X^{\prime} \neq X$ and learn the discrete log of $X^{\prime}$ (with respect to base $g$ ). Show that you can use this ability to learn the discrete $\log$ of $X$

Exercise $14.4$

Let $\langle g\rangle$ be a cyclic group with $n$ elements and generator $g$. Show that for all integers $a$, it is true that $g^{a}=g^{a \% n}$.

Note: As a result, $\langle g\rangle$ is isomorphic to the additive group $\mathbb{Z}_{n}$.

Exercise $14.5$

Let $g$ be a primitive root of $\mathbb{Z}_{n}^{*}$. Recall that $\mathbb{Z}_{n}^{*}$ has $\phi(n)$ elements. Show that $g^{a}$ is a primitive root of $\mathbb{Z}_{n}^{*}$ if and only if $\operatorname{gcd}(a, \phi(n))=1$

Note: It follows that, for every $n$, there are either 0 or $\phi(\phi(n))$ primitive roots mod $n$.

Exercise $14.6$

Let $\langle g\rangle$ be a cyclic group with $n$ elements. Show that for all $x, y \in\langle g\rangle$, it is true that $x^{n}=y^{n} .$

$\dot{\varepsilon}_{u}\left(v_{v} b\right)$ SI ๆеч $M \cdot v \mathrm{~}$

Hint:

Exercise $14.7$

(a) Prove the following variant of Lemma 4.10: Suppose you fix a value $x \in \mathbb{Z}_{N}$. Then when sampling $q=\sqrt{2 N}$ values $r_{1}, \ldots, r_{q}$ uniformly from $\mathbb{Z}_{N}$, with probability at least $0.6$ there exist $i \neq j$ with $r_{i} \equiv_{N} r_{j}+x$.

(b) Let $g$ be a primitive root of $\mathbb{Z}_{p}^{*}$ (for some prime $p$ ). Consider the problem of computing the discrete $\log$ of $X \in \mathbb{Z}_{p}^{*}$ with respect to $g-$ that is, finding $x$ such that $X \equiv_{p} g^{x}$. Argue that if one can find integers $r$ and $s$ such that $g^{r} \equiv_{p} X \cdot g^{s}$ then one can compute the discrete $\log$ of $X$.

(c) Combine the above two observations to describe a $O(\sqrt{p})$-time algorithm for the discrete logarithm problem in $\mathbb{Z}_{p}^{*}$.

Exercise $14.8$

In an execution of DHKA, the eavesdropper observes the following values:

$$\begin{array}{ll} p=461733370363 & A=114088419126 \\ g=2 & B=276312808197 \end{array}$$

What will be Alice & Bob’s shared key?

Exercise $14.9$

Explain what is wrong in the following argument:

In Diffie-Hellman key agreement, Alice sends $A=g^{a}$ and Bob sends $B=g^{b}$. Their shared key is $g^{a b}$. To break the scheme, the eavesdropper can simply compute $A \cdot B=\left(g^{a}\right)\left(g^{b}\right)=g^{a b}$.

Exercise $14.10$

Let $\mathbb{G}$ be a cyclic group with $n$ elements and generator $g$. Consider the following algorithm:

Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)

Let $D H=\left\{\left(g^{a}, g^{b}, g^{a b}\right) \in \mathbb{G}^{3} \mid a, b, \in \mathbb{Z}_{n}\right\}$

(a) Suppose $(A, B, C) \in D H$. Show that the output distribution of $\operatorname{RAND}(A, B, C)$ is the uniform distribution over $D H$

(b) Suppose $(A, B, C) \notin D H$. Show that the output distribution of $\operatorname{RAND}(A, B, C)$ is the uniform distribution over $\mathbb{G}^{3}$.

$\star$ (c) Consider the problem of determining whether a given triple $(A, B, C)$ is in the set $D H$. Suppose you have an algorithm $\mathcal{A}$ that solves this problem on average slightly better than chance. That is: $$\begin{aligned} &\operatorname{Pr}[\mathcal{A}(A, B, C)=1]>0.51 \text { when }(A, B, C) \text { chosen uniformly in } D H \\ &\operatorname{Pr}[\mathcal{A}(A, B, C)=0]>0.51 \text { when }(A, B, C) \text { chosen uniformly in } \mathbb{G}^{3} \end{aligned}$$ The algorithm $\mathcal{A}$ does not seem very useful if you have a particular triple $(A, B, C)$ and you really want to know whether it is in $D H$. You might have one of the triples for which $\mathcal{A}$ gives the wrong answer, and there’s no real way to know.

Show how to construct a randomized algorithm $\mathcal{A}^{\prime}$ such that: for every $(A, B, C) \in \mathbb{G}^{3}$ : $$\operatorname{Pr}\left[\mathcal{A}^{\prime}(A, B, C)=[(A, B, C) \stackrel{?}{\in} D H]\right]>0.99$$ Here the input $A, B, C$ is fixed and the probability is over the internal randomness in $\mathcal{A}^{\prime}$. So on every possible input, $\mathcal{A}^{\prime}$ gives a very reliable answer.