More efficient DDH pseudorandom generators
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.
- A Pseudorandom Generator from any One-way Function
- A Simple Unpredictable Pseudo-Random Number Generator
- An improved pseudo-random generator based on the discrete logarithm problem
- Bit commitment using pseudorandomness
- Cryptography and Coding
- Efficient cryptographic schemes provably as secure as subset sum
- Efficient Pseudorandom Generators Based on the DDH Assumption
- How to Construct Pseudorandom Permutations from Pseudorandom Functions
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- How to turn loaded dice into fair coins
- scientific article; zbMATH DE number 1820017 (Why is no real title available?)
- scientific article; zbMATH DE number 5009203 (Why is no real title available?)
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- scientific article; zbMATH DE number 1186931 (Why is no real title available?)
- scientific article; zbMATH DE number 1302855 (Why is no real title available?)
- scientific article; zbMATH DE number 2081057 (Why is no real title available?)
- scientific article; zbMATH DE number 1406771 (Why is no real title available?)
- Multirecipient Encryption Schemes: How to Save on Bandwidth and Computation Without Sacrificing Security
- New directions in cryptography
- Oblivious Transfer Is Symmetric
- On the Provable Security of an Efficient RSA-Based Pseudorandom Generator
- On the security of modular exponentiation with application to the construction of pseudorandom generators
- Probabilistic encryption
- Public Key Cryptography – PKC 2004
- QUAD: A Practical Stream Cipher with Provable Security
- RSA and Rabin Functions: Certain Parts are as Hard as the Whole
- Selecting cryptographic key sizes
- Simultaneous Security of Bits in the Discrete Log
- Stronger security proofs for RSA and Rabin bits.
- Tiny families of functions with random properties: a quality-size trade-off for hashing (preliminary version)
This page was built for publication: More efficient DDH pseudorandom generators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380399)
