PUMaC 2016 · 加试 · 第 3 题

Problem 3.5. (7 points) Prove Chebyshev’s inequality. Problem 3.6. (5 points) 1000 fair coins are flipped. Give an upper bound on the probability that 600 or more coins land heads-up: (a) (2 points) Use Markov’s inequality. (b) (3 points) Use Chebyshev’s inequality. 4 Introduction to Cryptography 4.1 Definition of an Encryption Scheme Suppose that Alice has a message that she wants to deliver to Bob, so that Bob can read it but no one else can. Alice can send her message by mail to Bob, but this has an obvious problem: Eve, a worker at the post office, could open the letter and read it. So Alice decides to put her message in a locked box and send it to Bob. But this is also problematic: how can Bob open the box? Well, if Alice and Bob meet in advance of the message being sent, Alice can give Bob a key with which to open the box. Essentially, Alice and Bob share a private key with which they can communicate: Alice can put a message in a box, lock it with the key, and send it to Bob, who can then open the box with the key. 8 While this is a secure system , it is cumbersome: every message has to be sent inside a box. It would be nice if Alice could send her message in an envelope, so that even if Eve opens the envelope, she can’t understand what Alice wrote. This idea is the basis of encryption, and just as a physical key was crucial to Alice and Bob’s plan in the previous paragraph, Alice can now use a figurative key to keep the message secret from Eve. Essentially, a (secret key) encryption scheme is an algorithm 8 We’re using “secure” in an informal way until we define it in the next section. If we call a system secure, it means that it’s either impossible or really hard for Eve to decipher the message. PUMaC 2016 Power Round Page 10 that encrypts a message using a key, together with an algorithm that can decipher the message using the key. Thus, Alice can share a key with Bob when they meet, and then send an encrypted message to Bob that Bob can decipher using the key. If the encryption scheme is secure (which will be defined rigorously later), Eve won’t be able to decipher the message. Definition 4.1.1. An encryption scheme is an ordered triple of algorithms ( G, E, D ), where G and E are PPT algorithms and D is a (deterministic) polynomial-time algorithm, such that for every positive integer n ( n is called the security parameter ): n • G , the key generation algorithm , takes as input 1 , the string of n ones (for some n ), and uses 9 randomness to choose a key k from a set of possible keys K , called the key space . n • E , the encryption algorithm , takes as input a message m ∈ P ( P is called the plaintext space n n for the security parameter n ), and, using k , outputs an encrypted message c ∈ C ( C is called n n the ciphertext space for the security parameter n ). E might also use randomness (in the sense that E ( m ) may not always output the same ciphertext c ). If E uses the key k to encrypt the k message m and outputs c , we write E ( m ) = c . k • D , the decryption algorithm , takes as input an encrypted message and uses k to decipher it. D is deterministic (does not use randomness). Thus, D , the decryption algorithm given the k key k , is a function from the ciphertext space to the plaintext space. This means that for all 10 m ∈ P , we have D ( E ( m )) = m . k k This definition has a lot packed into it. The next definition should help you gain some intuition for it. 4.2 Examples of Encryption Schemes The following examples are intended to help you gain intuition for Definition 4.1.1. 4.2.1 Caesar Cipher The Caesar cipher takes a message written using the English alphabet (which has 26 letters) and performs a cyclic shift of a randomly chosen, pre-determined amount on all of the letters. So if Alice and Bob want to communicate using the Caesar cipher, Alice and Bob meet and agree on a shift (let’s say they agree on 5). Later, if Alice wants to send Bob the word “YOGURT”, she will replace each letter with the letter that is 5 after it, looping around the alphabet if necessary. Thus, Alice sends Bob “DTLZWY”. Then Bob can decipher the message by “subtracting 5” from every letter. (Note that, as in this example, when we specify a shift it is always in the forward direction.)