Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style


Reingold, Omer

The Weizmann Institute of Science
Rehovot, Israel, 1999

Pseudo-Random Synthesizers, Functions and Permutations



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

ISSN 1433-8092 | Imprint