Reingold, Omer
The Weizmann Institute of Science
Rehovot, Israel, 1999
Pseudo-Random Synthesizers, Functions and Permutations
Abstract
The research reflected in this dissertation is a study of
(computational) pseudo-randomness. More specifically, the main
objective of this research is the efficient and simple construction of
pseudo-random functions and permutations [GGM,LR],
where efficiency refers both to the sequential and parallel time
complexity of the computation. Pseudo-random functions and
permutations are fundamental cryptographic primitives with many
applications in cryptography and more generally in computational
complexity.
Constructions of Pseudo-Random Functions
For our constructions of pseudo-random functions, we introduce and
study a new cryptographic primitive which we call a pseudo-random
synthesizer and a generalization of this primitive which we call a
k-dimensional pseudo-random synthesizer. These primitives are
of independent interest as well. In addition, we consider various
applications of our constructions and study some of the underlying
cryptographic assumptions used in these constructions. The main
results obtained by this research are:
- Introducing new cryptographic primitives called pseudo-random synthesizer and k-dimensional pseudo-random synthesizer.
- Using pseudo-random synthesizers for a parallel construction of a pseudo-random function (the depth of the functions is larger by a logarithmic factor than the depth of the synthesizers).
- Showing several NC^1 implementations of synthesizers based on concrete intractability assumptions such as factoring and the computational Diffie-Hellman assumption.
- Showing a very simple, parallel construction of synthesizers based on what we call weak pseudo-random functions which implies simple constructions of synthesizers based on trapdoor one-way permutations and based on any hard-to-learn problem (under the definition of [BFKL]).
These results yield the first parallel pseudo-random functions (based
on computational intractability assumptions) and the first alternative
to the original construction of Goldreich, Goldwasser and Micali
[GGM]. In addition, we show two new constructions of
pseudo-random functions (that are related to the construction based on
synthesizers). The pseudo-randomness of one construction is proven
under the assumption that factoring is hard while the other
construction is pseudo-random if the decisional version of the
Diffie-Hellman assumption holds. These functions have the following
properties:
- They are much more efficient than previous proposals: Computing the value of our functions at any given point involves two subset products.
- They are in TC^0 (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications.
- They have a simple algebraic structure that implies additional features. In particular, we show a zero-knowledge proof for statements of the form ``y=f_s(x)'' and ``y not equal f_s(x)'' given a commitment to a key s of a pseudo-random function f_s.
We discuss some applications of our constructions in cryptography
(including applications in public-key cryptography) as well as their
consequences in computational complexity and in computational
learning-theory.
Constructions of Pseudo-Random Permutations
Luby and Rackoff [LR] showed a method for constructing a
pseudo-random permutation from a pseudo-random function. The method is
based on composing four (or three for weakened security) so called
Feistel permutations, each of which requires the evaluation of a
pseudo-random function. We reduce somewhat the complexity of the
construction and simplify its proof of security by showing that two
Feistel permutations are sufficient together with initial and final
pair-wise independent permutations. The revised construction and
proof provide a framework in which similar constructions may be
designed and their security can be easily proved. We demonstrate this
by presenting some additional adjustments of the construction that
achieve the following:
- Reduce the success probability of the adversary.
- Provide a construction of pseudo-random permutations with large input-length using pseudo-random functions with small input length.
A Study of Some Number-Theoretical Assumptions
Our research includes a study of two number-theoretical assumptions
that are related to the Diffie-Hellman key-exchange protocol and that
are used in our constructions of pseudo-random functions. The first
is the decisional version of the Diffie-Hellman assumption
(DDH-Assumption). This assumption is relatively new, or more
accurately, was explicitly considered only recently. We
therefore survey some of the different applications of the assumption
and the current knowledge on its security. Furthermore, we show a
randomized reduction of the worst-case DDH-Assumption to its average
case (based on the random-self-reducibility of the DDH-Problem that
was previously used by Stadler [Stad]). We consider our research
of the DDH-Assumption to be of independent importance given that the
assumption was recently used in quite a few interesting applications
(e.g., [CS]).
The second assumption we study is the generalized Diffie-Hellman
assumption (GDH-Assumption). This assumption was originally considered
in the context of a generalization of the Diffie-Hellman key-exchange
protocol to k>2 parties. We prove that breaking this assumption
modulo a so called Blum-integer would imply an efficient algorithm for
factoring Blum-integers. Therefore, both the generalized key-exchange
protocol and our pseudo-random function (that is based on the
GDH-Assumption) are secure as long as factoring Blum-integers is hard.
Our reduction strengthens a previo
Table of Contents
Acknowledgments ..................................... iii
Abstract ............................................ v
1. Introduction ..................................... 1
2. Preliminaries .................................... 19
3. A Study of Some Number-Theoretical Assumptions ... 25
4. Constructions of Pseudo-Random Functions ......... 39
5. Constructions of Pseudo-Random Permutations ...... 91
