Adversarial Indistinguishability I am trying to devise an encryption scheme such that an adversary can win the following game with probability at most $1/2 + \epsilon$.


Adversary gives challenger two plaintext messages $m_1$ and $m_0$
Challenger chooses one the two at random and encrypts it and gives adversary the cipher
Adversary determines which of the two messages was chosen.


The key space has to be smaller than the message space. 

Any ideas?
An adversary can easily win this game with $\epsilon = 0.5$ when the scheme under examination is any block cipher in ECB mode.

Simply set $m_0$ and $m_1$ to the same block value, $q$. This guarantees that you'll get the encryption of $q$ back, which we'll call $r$.

Then you can distinguish between $q$ and some other block value with probability $1$ on subsequent trial by checking whether $r$ is returned or not.