In a Feistel cipher (as shown below), it seems that the security of the cipher would be entirely dependent upon the function $F$. What requirements on $F$ are necessary for a secure Feistel cipher? Is there any relationship between the function $F$ and the number of rounds necessary to have a secure cipher?
Luby and Rackoff published a famous article on that subject (SIAM Journal on Computing, 1988, Vol. 17, No. 2 : pp. 373-386 ). Namely, they showed that if the $F$ functions are pseudorandom, then four rounds are sufficient to achieve security.
There are subtle details, though:
Each round has its own $F$ function. We usually say that there is a single $F$ function indexed by the subkey for that round. In the Luby-Rackoff construction, the function for each round must be indistinguishable from a function taken at random, uniformly, among the set of possible functions which take an input as large as $R_i$ and produce an output as large as $L_i$; and that "random selection" must also hold between rounds (the round function for round 2 must be selected independently of the round function for round 1).
The security proof holds for balanced Feistel schemes ($L_i$ and $R_i$ have the same size).
If the block size is $n$ bits, then the security proof is valid up to $2^{n/2}$ elementary operations. So, if you want "proven" 128-bit security, the block cipher must use 256-bit blocks (or larger).
There is also the (technically unpublished) construction by Matt Blaze called Turtle: it is a four-round Feistel scheme for which each round function is itself a four-round Feistel scheme, recursively. Blaze links the security to an NP-complete problem, which is nifty, although it does not tell much about the security of the construction in practice (NP-completeness is about asymptotic behaviour; whether it applies on a given finite computational budget is a matter of guess and faith). Since Turtle was not formally published, it is a bit unclear whether the lack of cryptanalytic result is due to its inherent security, or lack of academic visibility.
A much more recent article from Morris, Rogaway and Stegers explores the security of unbalanced Feistel schemes where the "left part" ($L_i$) is a single bit. They show that, given enough rounds, one can get almost ultimate security, i.e. resilient against chosen ciphertext attacks up to $2^{n(1-1/r)}$ oracle requests, where $r$ is the number of rounds. This work is mostly useful in situation where we want small blocks. There again, the proof holds as long as the round functions are pseudorandom.
An empirical rule about Feistel ciphers is that, most of the time, complexity of attacks raises somewhat exponentially with the number of rounds. This holds as long as successive rounds are sufficiently dissimilar from each other; otherwise, you can have weaknesses due to slide attacks. For instance, one can say that if the best differential for the first half of the cipher has probability $P_1$, and the best differential for the second half has probability $P_2$, then the best differential for the whole cipher has probability at most $P_1 P_2$ -- but only if the two halves are independent of each other (i.e. use independent subkeys), which is an ideal but hard-to-get property.
