PUMaC 2016 · 加试 · 第 4 题

Problem 4.5. (5 points) Characterize the one-time pad cipher using Definition 4.1.1. In particular, n if for a given security parameter n the plaintext space is { 0 , 1 } (the set of length- n bit strings), what are the key space K and ciphertext space C ? Briefly describe, in words, the key generation n n algorithm G , the encryption algorithm E , and the decryption algorithm D . In practice, Alice and Bob would exchange a very long key (of, say, a million bits). When Alice sends a message of length ` to Bob, she uses the first ` bits of the key that she had not previously used. Unlike the Caesar cipher, the one-time pad cipher is in fact perfectly secure. The issue with it is that the one-time pad cipher requires Alice and Bob to exchange a very long key: for every bit of communication between Alice and Bob, there must be a corresponding bit of the key that was exchanged between Alice and Bob originally. For this reason, the one-time pad is not used much in practice. 5 Security of Encryption Schemes 5.1 Indistinguishability of Encryptions We are now ready to define a notion of security for encryption schemes. There are many notions of encryption scheme security; this one is called statistical indistinguishability of encryptions . Note that for convenience, from now on we will only consider encryption schemes whose plaintext and ∗ ciphertext spaces are subsets of { 0 , 1 } , the set of all bit strings. Definition 5.1.1. An encryption scheme ( G, E, D ) satisfies computational indistinguishability of encryptions if there exists a negligible function neg( n ) such that for all n , for all messages m , m ∈ 0 1 P , for every PPT algorithm A , n | Pr [ A ( E ( m )) = 1] − Pr [ A ( E ( m )) = 1] | ≤ neg( n ) , k 0 k 1 n where the probability is over the randomness of G (1 ) (i.e. the randomness of they key), the randomness of E , and the randomness of A . 12 Let’s try to make sense of this definition. The algorithm A , often called an adversary (because it attempts to break the encryption), outputs 1 with a certain probability when given a ciphertext. (This probability might always be 0 or 1, but it doesn’t have to be, since A is not required to be deterministic.) The goal of A is to be able to distinguish between the encryptions of different messages: it wants to output 1 more often when given the encryption of one message than when given the encryption of another message. If A can do this successfully, then A can potentially give a hacker or spy useful information about the original message, and so the encryption scheme is insecure. If, on the other hand, for every pair of messages there is no adversary A that can distinguish effectively between their encryptions, then the encryption scheme satisfies computational indistinguishability of encryptions, one notion of security.