This document provides a rough outline of the security reduction from the
construction implemented in main.py
to the security of the underlying
stream cipher.
This construction produces a 32-bit block cipher using four 16-bit pseudorandom functions in a Feistel network. These four functions are chosen randomly and uniformly from the set of all 16-bit pseudorandom functions as the output of a stream cipher.
In [1], Luby and Rackoff proved that four-round Feistel networks are indistinguishable from randomly-chosen permutations by a chosen-plaintext adversary, provided that the F-functions are pseudorandom functions.
This section establishes a security reduction between the generated pseudorandom functions and the underlying stream cipher.
A pseudorandom function is defined by the fact that its outputs, for any set of inputs, must be indistinguishable from random noise (barring the fact that identical inputs will produce identical outputs). In our construction, a set of inputs may be viewed as a set of indices into the output of the stream cipher. If the output of our pseudorandom function for this set of inputs could be distinguished from random noise, then an adversary could use this as a distinguishing attack against the underlying stream cipher, by looking at the same indices and in the same order, and performing the same attack thet used against the pseudorandom function.
- "How to Construct Pseudorandom Permutations from Pseudorandom Functions". Luby and Rackoff, 1988, SIAM Journal on Computing.