# 15: Public-Key Encryption


# Public-Key Encryption

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 $$(p k, s k)$$ where $$p k$$ is a public key and $$s k$$ is a private/secret key.

Enc: Takes the public key $$p k$$ and a plaintext $$m$$ as input, and outputs a ciphertext $$c$$.

Dec: Takes the secret key $$s k$$ 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 \in \mathcal{M}$$ and all $$(p k, s k) \leftarrow \operatorname{KeyGen}$$, we have $$\operatorname{Dec}(s k, \operatorname{Enc}(p k, m))=m$$ (with probability 1 over the randomness of Enc).

15: Public-Key Encryption is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.