Definitions of semantic security

  1. One-time semantic security.
  2. The simplest definition of semantic security is one-time semantic security which naturally applies to stream ciphers:

    An adversary sends two plaintext messages of equal length to the challenger and receives one encrypted message; semantic security means an adversary can’t distinguish which plaintext message was encrypted.

    The above is more an intuition than a definition; the strict formal definition involves details not suitable here.

    In practice a semantically secure stream cipher is as good as perfect one-time pad.

    The block cipher’s electronic codebook (ECB) mode of operation is not one-time semantically secure; the reason is ECB mode always maps identical plaintexts to identical ciphertexts. To win the game an adversary creates two messages of two blocks length; the first message consists of two identical blocks and the second consists of two different blocks; after receiving the ciphertext an adversary checks whether the ciphertext blocks are identical or not and decides which plaintext was encrypted. On the other hand the cipher block chaining (CBC) mode is one-time semantically secure.

  3. Semantic security under the chosen plaintext attack (CPA).
  4. One-time semantic security is not good for block ciphers because the block ciphers usually use many-time keys, so we need many-time security definition:

    An adversary sends q pairs of plaintext messages to the challenger; the challenger encrypts either the first messages or the second messages and sends them to an adversary; semantic security means an adversary can’t distinguish which messages (first or second) were encrypted.

    The above semantic security under CPA definition gives more power to an adversary. The CBC mode is semantically secure under CPA only if an initialization vector (IV) is unpredictable (random). If an adversary can predict the next IV used by the challenger he can create a one-block message which he can encrypt himself and use this message to win the CPA game.

    The semantic security under CPA implies that an adversary can force the challenger to encrypt the messages of his choice; all an adversary has to do is to send a pair of identical messages to the challenger and receive the ciphertext.

    So in the CPA game an adversary can get q-1 encrypted messages of his choice, then send the last q-th pair of different messages, receive the ciphertext and his goal now is to decide which message was encrypted.

  5. Semantic security under the chosen ciphertext attack (CCA).
  6. CCA game gives even more power to an adversary. Now an adversary can send queries of two types to the challenger – first type are the same pairs of plaintext messages as in the CPA game and the second type queries are ciphertexts which the challenger decrypts and sends the decrypted plaintexts back to an adversary. The adversary goal is to decide which plaintext messages, first or second, were encrypted in the queries of the first type.
    The only limitation is that an adversary can’t send ciphertexts which he receives from the challenger in the first type queries because otherwise the game is senseless.

    In the CCA game an adversary can force the challenger both to encrypt the plaintexts of his choice and decrypt ciphertexts of his choice; his goal again is to distinguish between the plaintext messages and decide which messages were encrypted.

    The CCA security is required against an active adversary, who can not only eavesdrop but also tamper, for example by blocking or injecting network packets. The CBC mode with random IV is not semantically secure under CCA. To be secure under CCA a system should provide CPA secure encryption with message authentication; the examples are SSL and IPSec protocols.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s