Summary
Today we begin to talk about publickey cryptography, starting from publickey encryption.
We define the publickey analog of the weakest form of security we studied in the privatekey setting: messageindistinguishability for one encryption. Because of the publickey setting, in which everybody, including the adversary, has the ability to encrypt messages, this is already equivalent to CPA security.
We then describe the El Gamal cryptosystem, which is messageindistinguishable (and hence CPAsecure) under the plausible Decision DiffieHellman assumption.
1. PublicKey Cryptography
So far, we have studied the setting in which two parties, Alice and Bob, share a secret key and use it to communicate securely over an unreliable channel. In many cases, it is not difficult for the two parties to create and share the secret key; for example, when we connect a laptop to a wireless router, we can enter the same password both into the router and into the laptop, and, before we begin to do online banking, our bank can send us a password in the physical mail, and so on.
In many other situations, however, the insecure channel is the only communication device available to the parties, so it is not possible to share a secret key in advance. A general problem of privatekey cryptography is also that, in a large network, the number of required secret keys grows with the square of the size of the network.
In publickey cryptography, every party generates two keys: a secret key and a public key . The secret key is known only to the party who generated it, while the public key is known to everybody.
(For publickey cryptosystems to work, it is important that everybody is aware of, or has secure access to, everybody else’s public key. A mechanism for the secure exchange of public keys is called a Public Key Infrastructure (PKI). In a network model in which adversaries are passive, meaning that they only eavesdrop on communication, the parties can just send each other’s public keys over the network. In a network that has active adversaries, who can inject their own packets and drop other users’ packets, creating a publickey infrastructure is a very difficult problem, to which we may return when we talk about network protocols. For now we assume that either the adversary is passive or that a PKI is in place.)
As in the privatekey setting, we will be concerned with two problems: privacy, that is the communication of data so that an eavesdropper can gain no information about it, and authentication, which guarantees to the recipient the identity of the sender. The first task is solved by publickey encryption and the second task is solved by signature schemes.
2. Public Key Encryption
A publickey encryption scheme is defined by three efficient algorithms such that
 takes no input and outputs a pair of keys
 , on input a public key and a plaintext message outputs a ciphertext .
(Typically, is a probabilistic procedure.)
 , on input a secret key and ciphertext , decodes . We require that for every message
A basic definition of security is messageindistinguishability for one encryption.
Definition 1 We say that a publickey encryption scheme is messageindistinguishable if for every algorithm of complexity and for every two messages ,
(From now on, we will not explicitly state the dependance of probabilities on the internal coin tosses of , although it should always be assumed.)
Exercise 1 Formalize the notion of CPAsecurity for publickey encryption. Show that if is message indistinguishable, and is computable in time , then is also CPAsecure.
3. The Decision DiffieHellman Assumption
Definition 2 (Decision DiffieHellman Assumption) A distribution over triples , where is a cyclic group of elements and is a generator, satisfies the Decision DiffieHellman Assumption if for every algorithm of complexity we have
Note that the El Gamal assumption may be plausibly satisfied even by a fixed group and a fixed generator .
4. El Gamal Encryption
The El Gamal encryption scheme works as follows. Let be a distribution over that satisfies the Decision DiffieHellman assumption:
 samples , and picks a random number .
 :
 pick at random
 output

 Compute
 Find the multiplicative inverse of
 output
Theorem 3 Suppose is a distribution that satisfies the Decision DiffieHellman assumption and that it is possible to perform multiplication in time in the groups occurring in .
Then the El Gamal cryptosystem is messageindistinguishable.
Once your class is done with, can you compile the lectures and make them a downloadable PDF?