A remark to Luby-Rackoff and Ueli M. Maurer pseudorandom generators

Rok, strany: 2000, 119 - 126

There are two excellent papers among many others: while Luby and Rackoff's paper [M. Luby, C. Rackoff: How to construct pseudorandom permutations from pseudorandom functions SIAM J. Comput. 17 (1988), 373–386] treats pseudorandom permutation generators focusing on complexity theory, Maurer's paper [U. M. Maurer: A simplified and generalized treatment of Luby–Rackoff, Pseudorandom Permutation Generators, Lecture Notes in Comput. Sci., Vol. 658, Springer-Verlag, Berlin, 1993, pp. 239–255] is based on the relation between probability and complexity theory. One of the Maurer's result is that the famous Luby–Rackoff lemma can be assumed as a purely probabilistic result. In this paper we compare and generalize both approaches. We show that for arbitrary $n$, and given a general oracle circuit $C_2n$ it is not possible to find Boolean function $g:({0,1}²ⁿ)^k ightarrow{0,1}$ and $x=(x₁,…,x_k)$, $x_iin{0,1}²ⁿ$ such that for all Boolean functions $f:{0,1}²ⁿ ightarrow{0,1}²ⁿ$ the relation $C_2n(f)= g(f(x₁),…, f(x_k))$ is valid.

ISO 690:

Grošek, O., Nemoga, K., Satko, L. 2000. A remark to Luby-Rackoff and Ueli M. Maurer pseudorandom generators. In Tatra Mountains Mathematical Publications, vol. 20, no.3, pp. 119-126. 1210-3195.

APA:

Grošek, O., Nemoga, K., Satko, L. (2000). A remark to Luby-Rackoff and Ueli M. Maurer pseudorandom generators. Tatra Mountains Mathematical Publications, 20(3), 119-126. 1210-3195.