Attack on a Feistel Cipher given the key and half of the ciphertext Consider a classical Feistel Cipher, with the round functions given and the keys used in the ciphering process. 

Is it possible to reconstruct the original data if half of the ciphered text is given? Furthermore, is it possible to reconstruct the original data if less than half of the ciphered text is given?

What would be the complexity of these tasks?

Example:
Suppose that we have a text that "makes sense" (e.g. it belongs to a dictionary or some set $S$). Let's say that "Salsifis" is ciphered into "abcdefgh". Suppose that "efgh" is revealed as well as the keys. Can "Salsifis" be reconstructed other than using an exhaustive search?
In a block cipher (SPN of Feistel), we want each of the plaintext bits affects the ciphertext bits. In other terms, if you write down the boolean function of the ciphertext bits $c_i$, we expect that the function contains all of the plaintext bits and the key bits;

$$C_i:\{p_0,\ldots,p_l\} \times \{k_0,\ldots,k_n\} \mapsto \{0,1\}$$ $$c_i=C_i(p_0,\ldots,p_l,k_0,\ldots,k_n)$$with $l$-bit block cipher, $n$-bit key size, and $C_i$ is a boolean funtion and $c_i$ is the i-th bit of the ciphertext.

Similarly, one can write boolean functions for the plaintext bits;

$$P_i:\{c_0,\ldots,c_l\} \times \{k_0,\ldots,k_n\} \mapsto \{0,1\}$$ $$p_i=P_i(c_0,\ldots,c_l,k_0,\ldots,k_n)$$

One-bit missing case

In this case, each of the boolean functions $P_i$ will have a free variable, the missing bit. By avalanche property, we expect that being 1 or zero will affect the half of the bits randomly. So you will have an almost completely different plaintext if you set this variable 1 or 0. If you have a pre-knowledge about the plaintext, like the language or structure, you may able to decide which one is correct.

More than one bit is missing

In this case, the missing variables will behave much more complicated. One, however,  can still try guessing the bits and check the plaintext properties to verify.

The complexity

As one can see, all is nothing but brute-force. So the complexities are $2^m$ where the $m$ is the number of missing bits. And remember, brute-force can only be successful if you have some information about the plaintext, as in RSA challenge. 

** update: a simple test case for one-bit change in DES.**

key        : $\texttt{0e1f35bbaf37a86b}$

Ciphertext : $\texttt{0123456789ABCDEF}$

Plaintext  : $\texttt{0d738d5e43fbd5fe}$

Ciphertext : $\texttt{1123456789ABCDEF}$

Plaintext  : $\texttt{bd85b2e02bb056df}$

The difference between two plaintexts with one-bit change; 

$\texttt{b0f63fbe684b8321}$, and in binary;

1011000011110110001111111011111001101000010010111000001100100001

which has 33 1's