How to Privatize Random Bits
Marius Zimand · 1996
The paper investigates the extent to which a public source of random bits can be used to obtain private random bits that can be safely used in cryptographic protocols. We consider two cases: (a) the case in which the part privatizing random bits is computationally more powerful than the adversary, and (b) the case in which the part privatizing random bits has a small number of private random bits. The first case corresponds to randomized hard functions and the second variant corresponds to randomized pseudo-random generators. We show the existence of strong randomized hard functions and pseudo-random generators. As a side effect, it is shown that relative to a random oracle P=poly is not measurable in EXP in the resource-bounded theoretical sense and a very strong separation between sublinear time and AC 0 is obtained. Keywords: one-way function, pseudo-random generator, hard function. Supported in part by grant NSF-CCR-8957604, NSF-INT-9116781/JSPS-ENG-207 and NSF-CCR9322513. 1 Int...