On the development of block-ciphers and pseudo-random function generators using the composition and XOR operators

Abstract

We attempt to provide evidence for the security of block-ciphers which are constructed by taking the composition and exclusive or of non-secure function generators. We provide this evidence by showing that such construction can be used to combine partially secure pseudo-random, function generators into generators with stronger security properties than any of their constituents. We extend results of Luby and Rackoff, and show that there are constructions based on the composition and □ operators which can be used to combine 1 − δ secure pseudo-random permutation and function generators, where 0 < δ < 1, to achieve a $1-1log$

c

n </math> secure generator, for any c > 0. We then give the first proof that there is a natural construction which combines together 1 > δ secure function generators to form a pseudo-random function generator.