Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Information Theoretic Security

    Uploaded by

    Asbah Rehman

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Information Theoretic Security

    Uploaded by

    Asbah Rehman
    15 views2 pages

    Original Title

    information theoretic security

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    15 views2 pages

    Information Theoretic Security

    Uploaded by

    Asbah Rehman

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Notes on Information Theoretic Security

    Ninghui Li

    1 Information theoretic security


    A cryptosystem is information-theoretically secure if its security derives purely from information theory.
    That is, it is secure even when the adversary has unbounded computing power. No brute-force attack, in
    fact, no attack except for stealing the key, can break the security.
    For ciphers, where one cares about confidentiality, being information-theoretically secure is also known
    as having perfect secrecy: an encryption algorithm has perfect secrecy if a ciphertext produced using it
    provides no information about the plaintext without knowledge of the key.
    Information-theoretic security can be applied in contexts other than encryption, to properties other than
    confidentiality. For example, one can define information-theoretically secure authenticity (in message au-
    thentication code schemes), information-theoretically binding (in cryptographic commitment schemes), and
    so on. Here we are only concerned with perfect secrecy.
    A cipher provides perfect secrecy if and only if for any probability distribution from which the plaintext
    is drawn, and for any plaintext-ciphertext pair (M0 , C0 ), we have

    Pr[PT = M0 | CT = C0 ] = Pr[PT = M0 ].

    That is, after observing the ciphertext is C0 , the posterior probability that the plaintext is M0 remains the
    same as the prior probability that the plaintext is M0 .
    An example of an information-theoretically secure cryptosystem is the one-time pad.

    2 One-Time Pad
    The One-Time Pad encryption

    • M = C = K = {0, 1}n , where M is the plaintext (message) space, C is the ciphertext space, K is the
    key space, they are all n-bit binary strings.

    • K = K ←− K (meaning that K is drawn uniformly random from K, in other words, each key in K is
    drawn with equal probability).

    • EK [M ] = E[K, M ] = K ⊕ M .

    • DK [C] = D[K, C] = K ⊕ C.

    1
    One-Time Pad has Perfect Secrecy
    Proof. For any probability distribution from which the plaintext is drawn, for any plaintext-ciphertext
    pair (M0 , C0 ), we need to show that Pr[PT = M0 | CT = C0 ] = Pr[PT = M0 ].

    Pr[PT = M0 , CT = C0 ] Pr[PT = M0 ] Pr[CT = C0 | PT = M0 ]


    Pr[PT = M0 | CT = C0 ] = =∑
    Pr[CT = C0 ] M ∈M (Pr[PT = M ] Pr[CT = C0 | PT = M ])

    Since that the encryption key is drawn uniformly random from the key space, and there is only one key
    that encrypts any given plaintext into any given cipher text (the key is given by the XOR of the plaintext and
    the ciphertext),
    # of keys in K that encrypts M0 into C0 1
    Pr[CT = C0 | PT = M0 ] = = n
    # of total keys in K 2

    Similarly, for every M ∈ M, Pr[CT = C0 | PT = M ] = 1


    2n .
    Therefore, continuing the first equation, we have

    Pr[PT = M0 ] 21n Pr[PT = M0 ] Pr[PT = M0 ]


    Pr[PT = M0 | CT = C0 ] = ∑ 1 =∑ =
    M ∈M (Pr[PT = M ] 2n ) M ∈M (Pr[PT = M ]) 1

    3 A Crypto System that does not have perfect secrecy


    Consider a crypto system in which M = {a, b, c}, K = {K1 , K2 , K3 } and C = {1, 2, 3, 4}. The keys are
    chosen uniformly randomly; in other words, Pr[Key = K1 ] = Pr[Key = K2 ] = Pr[Key = K3 ] = 1/3,
    and the encryption matrix is as follows:

    a b c
    K1 1 2 3
    K2 2 3 4
    K3 3 4 1
    This does not have perfect secrecy because observing that the ciphertext is 1, one knows that the plaintext
    cannot be b.
    That is, for any distribution of plaintext in which Pr[PT = b] ̸= 0, we have Pr[PT = b | CT = 1] = 0,
    and thus Pr[PT = b | CT = 1] ̸= Pr[PT = b].

    You might also like