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.