tailieunhanh - Information Theory and Security

Up to this point we have seen: Classical Crypto Symmetric Crypto Asymmetric Crypto These systems have focused on issues of confidentiality: Ensuring that an adversary cannot infer the original plaintext message, or cannot learn any information about the original plaintext from the ciphertext. In today’s lecture we will put a more formal framework around the notion of what information is, and use this to provide a definition of security from an information-theoretic point of view. | Information Theory and Security Lecture Motivation Up to this point we have seen: Classical Crypto Symmetric Crypto Asymmetric Crypto These systems have focused on issues of confidentiality: Ensuring that an adversary cannot infer the original plaintext message, or cannot learn any information about the original plaintext from the ciphertext. In today’s lecture we will put a more formal framework around the notion of what information is, and use this to provide a definition of security from an information-theoretic point of view. Lecture Outline Probability Review: Conditional Probability and Bayes Entropy: Desired properties and definition Chain Rule and conditioning Coding and Information Theory Huffman codes General source coding results Secrecy and Information Theory Probabilistic definitions of a cryptosystem Perfect Secrecy The Basic Idea Suppose we roll a 6-sided dice. Let A be the event that the number of dots is odd. Let B be the event that the number of dots is at least 3. A | Information Theory and Security Lecture Motivation Up to this point we have seen: Classical Crypto Symmetric Crypto Asymmetric Crypto These systems have focused on issues of confidentiality: Ensuring that an adversary cannot infer the original plaintext message, or cannot learn any information about the original plaintext from the ciphertext. In today’s lecture we will put a more formal framework around the notion of what information is, and use this to provide a definition of security from an information-theoretic point of view. Lecture Outline Probability Review: Conditional Probability and Bayes Entropy: Desired properties and definition Chain Rule and conditioning Coding and Information Theory Huffman codes General source coding results Secrecy and Information Theory Probabilistic definitions of a cryptosystem Perfect Secrecy The Basic Idea Suppose we roll a 6-sided dice. Let A be the event that the number of dots is odd. Let B be the event that the number of dots is at least 3. A = {1, 3, 5} B = {3, 4, 5, 6} I tell you: the roll belongs to both A and B then you know there are only two possibilities: {3, 5} In this sense tells you more than just A or just B. That is, there is less uncertainty in than in A or B. Information is closely linked with this idea of uncertainty: Information increases when uncertainty decreases. Probability Review, pg. 1 A random variable (event) is an experiment whose outcomes are mapped to real numbers. For our discussion we will deal with discrete-valued random variables. Probability: We denote pX(x) = Pr(X = x). For a subset A, Joint Probability: Sometimes we want to consider more than two events at the same time, in which we case we lump them together into a joint random variable, . Z = (X,Y). Independence: We say that two events are independent if Probability Review, pg. 2 Conditional Probability: We will often ask questions about the probability of events Y given that we have observed X=x. In particular, we define the .