More efficient DDH pseudorandom generators (Q2380399)

Two pseudorandom generators are presented, both based on the decisional Diffie-Hellman (DDH) hardness. In~[\textit{R. R. Farashahi, B. Schoenmakers} and \textit{A. Sidorenko}, Lecture Notes in Computer Science 4450, 426--441 (2007; Zbl 1161.65305)], a DDH pseudorandom generator is presented. Let \(q\) be a Sophie Germain prime and let \(p=2q+1\), then \(p\) is prime as well. In the multiplicative group \(\mathbb{Z}_p^*\) let \(\mathbb{G}\) be its subgroup of order \(q\) and let \(\phi:\mathbb G\to\mathbb{Z}_q\) be an isomorphism. Let \(g_0,g_1\in\mathbb{G}\), and let \(s\in\mathbb{Z}_q\) be a secret seed. Let \(s_0=s\) and for any \(j>0\) let \(s_j=\phi(g_0^{s_{j-1}})\) and \(t_j=\phi(g_1^{s_{j-1}})\). The output pseudorandom sequence is \((t_j)_{j>0}\). The proof that this is pseudorandom is based on the hardness of the DDH: for a generator \(g\in\mathbb G\) and random selection of the exponents \(x,y,z\in\mathbb{Z}_q\) it is required to distinguish the Diffie-Hellman 4-tuple \((g,g^x,g^y,g^{xy})\) from the random 4-tuple \((g,g^x,g^y,g^z)\). By writing \(g_0=g\) and \(g_1=g^x\), then the Diffie-Hellman 4-tuple has the form \((g_0,g_1,g_0^y,g_1^y)\) and the random tuple \((g_0,g_1,g_0^{y_0},g_1^{y_1})\), with \(y_0=y\) and \(y_1=z(xy)^{-1}\). In the current paper a modified DDH is proposed: for \(m+1\) generators \(g_0,\dots,g_m\in\mathbb G\) and random selection of the exponents \(x,x_0,\dots,x_m\in\mathbb{Z}_q\) it is required to distinguish the Diffie-Hellman tuple \((g_i)_{i=0}^m*(g_i^x)_{i=0}^m\) from the random tuple \((g_i)_{i=0}^m*(g_i^{x_i})_{i=0}^m\) (here, \(*\) denotes concatenation). In Lemma 3, the authors prove that if the DDH is hard, then the modified DDH is hard as well (with a proper adjustment of the involved complexity parameters). The first proposed pseudorandom generator acts as follows: Let \(q\) be a Sophie Germain prime and let \(p=2q+1\). Let \(\mathbb{G}\) be the subgroup of order \(q\) in the multiplicative group \(\mathbb{Z}_p^*\) and let \(\phi:\mathbb G\to\mathbb{Z}_q\) be an isomorphism. Let \(g_0,\dots,g_m\in\mathbb G\) be \(m+1\) generators, and let \(s\in\mathbb{Z}_q\) be a secret seed. Let \(s_0=s\) and for any \(j>0\) let \(s_j=\phi(g_0^{s_{j-1}})\) and \(t_{ij}=\phi(g_i^{s_{j-1}})\), \(i=1,\dots,m\). The output pseudorandom sequence is \((t_{1j}*\cdots t_{mj})_{j>0}\). The robustness of the method follows from the hardness of the modified DDH and its efficiency is due to the fact that at each iteration, \(m\) values are output. The second method is performed in \(\mathbb{Z}_n^*\) where \(n=pq\) is the product of two primes \(p=2p_1+1\), \(q=2q_1+1\) and \(p_1,q_1\) are two Sophie Germain primes. Here, \(\mathbb{G}\) is the group of quadratic residues in \(\mathbb{Z}_n^*\) and the robustness of the method is based on the hardness of factoring. The authors provide a full analysis on the robustness. Finally, the authors provide illustrative statistics of the method performances.