e>the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
Ecient Pseudorandom Generators Based on the DDH Assumption
Ecient Pseudorandom Generators Based on the DDH
Assumption
Reza Rezaeian Farashahi, Berry Schoenmakers, and Andrey Sidorenko
Eindhoven University of Technology,
P.O. Box 513, 5600MB Eindhoven, The Netherlands
r.rezaeian@tue.nl, berry@win.tue.nl, a.sidorenko@tue.nl
Abstract. A family of pseudorandom generators based on the decisional Die-
Hellman assumption is proposed. The new construction is a modied and generalized
version of the Dual Elliptic Curve generator proposed by Barker and Kelsey. Although
the original Dual Elliptic Curve generator is shown to be insecure, the modied ver-
sion is provably secure and very ecient in comparison with the other pseudorandom
generators based on discrete log assumptions.
Our generator can be based on any group of prime order provided that an additional
requirement is met (i.e., there exists an eciently computable function that in some
sense enumerates the elements of the group). Two specic instances are presented. The
techniques used to design the instances, for example, the new probabilistic randomness
extractor are of independent interest for other applications.
1
Introduction
A pseudorandom generator is a deterministic algorithm that converts a short sequence of
uniformly distributed random bits into a longer sequence of bits that cannot be distinguished
from uniformly random by a computationally bounded algorithm. It is known that a pseudo-
random generator can be constructed from any one-way function [27]. Thus, intractability
of the discrete logarithm problem suces to construct a pseudorandom generator. Such a
construction was rst proposed by Blum and Micali [2]. However, the Blum-Micali pseudo-
random generator and similar ones are inecient in the sense that only a single bit is output
per modular exponentiation. In this paper, we show that the stronger assumption that the
decisional Die-Hellman problem is hard to solve (DDH assumption) gives rise to much
more ecient pseudorandom generators.
Using strong assumptions in order to improve performance of cryptographic schemes is a
common practice nowadays. In particular, several pseudorandom generators based on strong
number theoretic assumptions have been proposed during the last decade. For instance, Patel
and Sundaram [22], Gennaro [8] show that ecient pseudorandom generators can be built
if one assumes that computing discrete logarithms with short exponents is a hard problem.
Steinfeld et al. [28] propose an improved version of the well-known RSA generator assuming
the intractability of a strong variant of the RSA problem.
In comparison with many other assumptions, the DDH assumption is thoroughly studied
(for more details about the security of the DDH problem, refer e.g. to [21]) and has become
a basis for a wide variety of cryptographic schemes. To the best of our knowledge, the
construction proposed in this paper is the rst pseudorandom generator based on the DDH
assumption. Security of the new construction is tightly related to the intractability of the
DDH problem.
1.1
Related Work
Our work is inspired by the publication of Barker and Kelsey [1], in which the so-called
Dual Elliptic Curve generator is proposed. Let P and Q be points on a prime order elliptic 2
curve over a prime eld F
p
such that p is close to 2
256
. Let q denote the order of the
curve. On input s
0
chosen uniformly at random from Z
q
the Dual Elliptic Curve generator
produces two sequences of points s
i
P and s
i
Q such that s
i
is set to be the x-coordinate of
s
i1
P , i = 1, 2, . . . , k. The generator outputs k binary strings each string consisting of the
240 least signicant bits of the x-coordinate of s
i
Q. The sequence of points s
i
Q is shown
to be indistinguishable from the sequence of uniformly random points of the elliptic curve
under the assumption that the DDH problem and the non-standard x-logarithm problem
are intractable in E(F
p
) [3]. However, the binary sequence produced by the generator turns
out to be distinguishable from uniform. The reason is that points of the elliptic curve are
transformed into random bits in an improper way [10, 24].
Some ideas of the Dual Elliptic Curve generator are present in the earlier work by Naor
and Reingold [21]. Let p be a prime and let g be a generator of a subgroup of Z p
of prime
order q. Let a Z
q
be a xed number. Naor and Reingold [21] propose a simple function G
that on input b Z
q
outputs (g
b
, g
ab
). If b is chosen uniformly at random, the output of the
function is computationally indistinguishable from uniform under the DDH assumption in
the subgroup. Note, however, that function G produces random elements of the subgroup
rather than random bits and therefore it is not a pseudorandom generator in the sense of
Denition 1 (converting random elements of the subgroup into random bits is a nontrivial
problem). Moreover, although function G doubles the input it cannot be iterated to produce
as much pseudorandomness as required by the application. Namely, it is not clear how to
produce a new value of b given two group elements g
b
and g
ab
. Accordingly, the goal of
Naor and Reingold [21] is to construct not a pseudorandom generator but a pseudorandom
function, for which function G turns out to be a suitable building block.
1.2
Our Contributions
We modify and generalize the Dual Elliptic Curve generator such that the modied version
is provably secure under the DDH assumption. In comparison with the original Dual Elliptic
Curve generator, our generator can be based on any group of prime order meeting an addi-
tional requirement (i.e., there exists an eciently computable function that in some sense
enumerates the elements of the group). The new generator is more ecient than all known
pseudorandom generators based on discrete log assumptions.
We present two specic instances of the new pseudorandom generator.
The rst instance is based on the group of quadratic residues modulo a safe prime
p = 2q + 1. This instance uses an elegant idea of Cramer and Shoup [5] who show that there
exists a simple bijective function that maps quadratic residues modulo p to Z
q
.
The second instance is based on an arbitrary prime order subgroup of Z p
, where p is
prime but not necessarily a safe prime. To construct this instance, we rst propose a surpris-
ingly simple probabilistic randomness extractor that provided with some extra randomness
converts a uniformly random element of the subgroup of order q into a uniformly random
number in Z
q
, which in turn can be easily converted into a string of uniformly random bits
using, for instance, algorithm Q
2
from [12] (for an overview of probabilistic randomness
extractors, refer to [25]). Note that all (probabilistic and deterministic) extractors known so
far can only convert random elements of the subgroup into bits that are statistically close to
uniform.
We derive the security parameters of the new pseudorandom generators from the cor-
responding security reductions. For this purpose, we make practical assumptions about in-
tractability of the discrete logarithm problem in the corresponding groups.
2
Preliminaries
In this section, we introduce some conventions and recall basic denitions. 3
2.1
Notation
Let x and y be random variables taking on values in a nite set S. The statistical distance
between x and y is dened as
(x, y) = 12
S
| Pr[x = ] Pr[y = ]|.
We say that algorithm D distinguishes x and y with advantage
if and only if
| Pr[D(x) = 1] Pr[D(y) = 1] | .
If the statistical distance between x and y is less than
then no algorithm distinguishes x
and y with advantage
(see, e.g., Exercise 22 of [17]).
Let U
m
denote a random variable uniformly distributed on Z
m
. We say that an algorithm
is T -time if it halts in time at most T .
2.2
Pseudorandom Generators
Consider a deterministic algorithm PRG : {0, 1}
n
{0, 1}
M
, where M > n. Loosely speak-
ing, PRG is called a pseudorandom generator if it maps uniformly distributed input into
an output which is computationally indistinguishable from uniform. The input is called the
seed and the output is called the pseudorandom sequence. The precise denition is given
below.
A T -time algorithm D : {0, 1}
M
{0, 1} is said to be a (T, )-distinguisher for PRG if
| Pr[D(PRG(U
2
n
)) = 1] Pr[D(U
2
M
) = 1] | .
(1)
Denition 1 (Pseudorandom generator). Algorithm PRG is called a (T, )-secure pseu-
dorandom generator if no (T, )-distinguisher exists for PRG.
An important question is what level of security (T, ) suces for practical applications
of pseudorandom generators. Unfortunately, the level of security is often chosen arbitrarily.
Knuth ([14], p. 176) sets
= 0.01 and consider several values for T up to 53.5 � 10
12
Mips-
Years
1
. In [6], the security level is set to T = 1 Mips-Year and = 0.01. In [8], T = 3.5 � 10
10
Mips-Years, = 0.01.
The fact that a pseudorandom generator is (T, )-secure does not automatically mean
that the generator is (T , )-secure for all T and
such that T / T / . For instance, if a
pseudorandom generator is (T, 0.01)-secure it does not necessarily mean that the generator
is (T , 0.009)-secure even if T
T . The reason is that a (T , 0.009)-distinguisher cannot
always be trans