# Cryptographic systems that don't leak linear combinations of encrypted bits

Various encryption schemes would be considered broken if an adversary could have a non-negligible edge in predicting the first (or any) bit of an encrypted message. I am looking for a slightly stronger guarantee.

In particular, does any cryptographic system or crypto assumption (that relies on keys, not a one time pad) guarantee that any linear combination of the encrypted bits cannot be predicted after an adversary sees only a polynomial number of messages (possibly of his choosing)?

Note -- I am not at all an expert in cryptography, and this may be considered trivial.

The easiest way to see this is to note that IND-CPA (left-or-right indistinguishability) implies real-or-random indistinguishability under chosen-plaintext attack: an attacker cannot distinguish the encryption of messages $M_1,\dots,M_n$ (chosen by the attacker) from the encryption of random strings $R_1,\dots,R_n$ (chosen randomly and not revealed to the attacker). This fact is proven in Bellare & Rogaway's lecture notes, or is easy to derive yourself via a hybrid argument.
Now your result follows. Let $\ell$ be any linear function of the message. Then it follows that no attacker can predict $\ell(M_i)$ better than random guessing. Why? $\ell(R_i)$ is a random bit. So, if knowledge of $E_k(M_i)$ lets you distinguish $\ell(M_i)$ from random (i.e., distinguish $\ell(M_i)$ from $\ell(R_i)$), then it would also let you distinguish $E_k(M_i)$ from $E_k(R_i)$, which would violate semantic security.