<p>Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing. </p>

<p>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 &amp; Rogaway's lecture notes, or is easy to derive yourself via a hybrid argument.</p>

<p>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. </p>

CC BY-SA 3.0
2015-02-10T00:33:06.190Z
Thanks!  Do you happen to know what crypto assumptions give semantic security?
Lev Reyzin
CC BY-SA 3.0
2015-02-10T00:35:34.903Z
@LevReyzin, [semantic security](https://en.wikipedia.org/wiki/Semantic_security) is the standard (minimal) notion of security for an encryption scheme -- it's the bare-minimum to have an encryption scheme that is considered at all reasonable.  Semantic security should be covered in any good textbook on crypto -- see, e.g., Katz & Lindell, or Bellare & Rogaway's lecture notes.  I recommend studying standard resources/textbooks to help familiarize yourself with these concepts.
D.W.
CC BY-SA 3.0
2015-02-10T02:10:35.170Z
One-way functions are necessary and sufficient for semantically secure encryption (the Katz-Lindell textbook has parts of the proof).
Adam Smith
CC BY-SA 3.0
2015-02-10T00:13:10.727Z
2015-02-10T00:13:10.727Z
D.W.
<p>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.</p>

<p>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)?</p>

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

<cr.crypto-security><cryptographic-attack><linear-equations>
Cryptographic systems that don't leak linear combinations of encrypted bits
Lev Reyzin
# Cryptographic systems that don't leak linear combinations of encrypted bits

(Asked by: username_0 on 2015-02-09)

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.

**Tags:** cr.crypto-security, cryptographic-attack, linear-equations

---

## 1 answers

### Answer by username_1 on 2015-02-10. Score: 6 | Accepted answer

Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing.

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.

> **Comments:**
> **username_0**: Thanks!  Do you happen to know what crypto assumptions give semantic security?  
> **username_1**: @LevReyzin, [semantic security](https://en.wikipedia.org/wiki/Semantic_security) is the standard (minimal) notion of security for an encryption scheme -- it's the bare-minimum to have an encryption scheme that is considered at all reasonable.  Semantic security should be covered in any good textbook on crypto -- see, e.g., Katz & Lindell, or Bellare & Rogaway's lecture notes.  I recommend studying standard resources/textbooks to help familiarize yourself with these concepts.  
> **username_2**: One-way functions are necessary and sufficient for semantically secure encryption (the Katz-Lindell textbook has parts of the proof).  

---

