So far, the encryption schemes that we’ve seen are symmetric-key schemes. The same key is used to encrypt and decrypt. In this chapter we introduce public-key (sometimes called asymmetric) encryption schemes, which use different keys for encryption and decryption. The idea is that the encryption key can be made public, so that anyone can send an encryption to the owner of that key, even if the two users have never spoken before and have no shared secrets. The decryption key is private, so that only the designated owner can decrypt.
We modify the syntax of an encryption scheme in the following way. A public-key encryption scheme consists of the following three algorithms:
KeyGen: Outputs a pair (pk,sk) where pk is a public key and sk is a private/secret key
Enc: Takes the public key pk and a plaintext m as input, and outputs a ciphertext c.
Dec: Takes the secret key sk and a ciphertext c as input, and outputs a plaintext m.
We modify the correctness condition similarly. A public-key encryption scheme satisfies correctness if, for all m ∈ ? and all (pk,sk) ← KeyGen, we have Dec(sk,Enc(pk,m)) = m (with probability 1 over the randomness of Enc).