Given a $N$-bit AES or similar block cipher with his $N$-bit key $k$.
We can encrypt a $N$-bit message $m$ to a $N$-bit cipher $c$ and decrypt it again.
$$E(m,k) = c$$
$$D(c,k) = m$$
An adversary does know $n_m$ bits of the message, $n_c$ bits of the cipher and different to most applications also the full key $k$.
He want to find pairs $(m\leftrightarrow c)$ which match the $n_m$ and $n_c$ bits on their related side.
Q: Can he find them significant faster than with brute force?
Further nodes:
The AES/block cipher is in ECB-mode - it does always use the same known key $k$.
It's length-perceiving encryption - $m,c,k$ all have bit length $N$
The bit location of the known bits is also know (e.g. could be the first $n_m$ bits of the message and last $n_c$ bits of the cipher)
Brute-force:
The number of different messages with those $n_m$ target bit is $2^{\displaystyle N-n_m}$. At the cipher side it's $2^{\displaystyle N-n_c}$.
The brute force method would start at the side with less values and encrypt (or decrypt) all possible values and check if the result matches the target bits.
Assuming uniform distribution the mean number of matches will only be $2^{\displaystyle N -n_m -n_c}$ pairs.
Can the adversary make use of this and test significant less values than with the described brute force method?
Bonus question:
In case the adversary can make use of this would it be more secure it the leaked information is distributed among all bits of $m$ or $c$?
E.g. instead of the $n_m$ bits only a module residue $r_m \equiv m \bmod 2^{\displaystyle n_m}$ is known to the adversary. Or can he also make use of that?
