4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks! Do you happen to know what crypto assumptions give semantic security? $\endgroup$
    – Lev Reyzin ♦
    Feb 10, 2015 at 0:33
  • 1
    $\begingroup$ @LevReyzin, 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. $\endgroup$
    – D.W.
    Feb 10, 2015 at 0:35
  • 4
    $\begingroup$ One-way functions are necessary and sufficient for semantically secure encryption (the Katz-Lindell textbook has parts of the proof). $\endgroup$
    – Adam Smith
    Feb 10, 2015 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.