14.4: Exercises
- Page ID
- 86470
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.
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:
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\)
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}\).
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\).
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:
(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}^{*}\).
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?
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}\).
Let \(\mathbb{G}\) be a cyclic group with \(n\) elements and generator \(g\). Consider the following algorithm:
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.