Rehovot, Israel, 1999

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.

- 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.

- 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.

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

Acknowledgments ..................................... iiiAbstract ............................................ v1. Introduction ..................................... 12. Preliminaries .................................... 193. A Study of Some Number-Theoretical Assumptions ... 254. Constructions of Pseudo-Random Functions ......... 395. Constructions of Pseudo-Random Permutations ...... 91