View source for Public Key Encryption (PKE)

<noinclude>
[[Category:Primitives]]
[[Category:Cryptomania]]

A [[Public Key Encryption (PKE)]] scheme is a [[primitive]] that allows someone to publish a public key that can be used to encrypt plaintext. Then, the generator of the key can use a secret key to decrypt the ciphertext. It is a critical notion for the modern public-key infrastructure and was famously made possible by [[ccref#rsa78|[RSA78]]] and [[ccref#elg85|[Elg85]]].

== Formal Definition ==

=== Syntax ===
A [[Public Key Encryption (PKE)]] scheme is a tuple of efficient functions <math>(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})</math>, with respect to a keyspace <math>\mathcal{K}=\mathcal{K}_{\text{pub}}\times \mathcal{K}_{\text{sec}}</math>, plaintext space <math>\mathcal{M}</math>, and ciphertext space <math>\mathcal{C}</math>, such that:
* <math>\mathsf{Gen}(1^{\lambda}) \to (pk,sk)</math>, is a randomized function that takes a security parameter, and outputs a public key <math>pk\in \mathcal{K}_{\text{pub}}</math> and secret key <math>sk\in \mathcal{K}_{\text{sec}}</math>
* <math>\mathsf{Enc}_{pk}(m) \to c</math>, is a randomized function that takes a public key <math>pk\in \mathcal{K}_{\text{pub}}</math> and plaintext message <math>m\in \mathcal{M}</math>, and outputs a ciphertext <math>c\in \mathcal{C}</math>,
* <math>\mathsf{Dec}_{sk}(c) \to m</math>, is a deterministic function that takes a secret key <math>sk\in \mathcal{K}_{\text{sec}}</math> and ciphertext <math>c\in \mathcal{C}</math>, and outputs a plaintext message <math>m\in \mathcal{M}</math>.

=== Chosen Plaintext Attack (CPA) Security ===
<span id="CPA-security"></span>
A PKE scheme is ''CPA-secure'' if for all efficient adversaries <math>A</math>, there exists a negligible function <math>\nu</math>, such that
<center><math>
\big| \Pr [A(pk, \mathsf{Enc}_{pk}(m_b)) = b : (m_0,m_1) \gets A(pk)] - 1/2\big| \le \nu(\lambda),
</math></center>
where <math>(pk,sk)\gets \mathsf{Gen}(1^{\lambda})</math> and <math>b</math> is a uniformly random bit.

=== Chosen Ciphertext Attack (CCA) Security ===
<span id="CCA-security"></span>
A SE scheme is ''CCA-secure'' if for all admissible efficient adversaries <math>A</math>, there exists a negligible function <math>\nu</math>, such that
<center><math>
\big| \Pr [A^{\mathsf{Dec}_{sk}}(pk, \mathsf{Enc}_{pk}(m_b)) = b : (m_0,m_1) \gets A^{\mathsf{Dec}_{sk}}(pk)] - 1/2\big| \le \nu(\lambda),
</math></center>
where <math>(pk,sk)\gets \mathsf{Gen}(1^{\lambda})</math> and <math>b</math> is a uniformly random bit.
Further, we say an adversary is admissible if it never queries <math>\mathsf{Dec}_{sk}</math> on the ciphertext given to <math>A</math> in the second phase of the game.

The difference in this definition is that we additionally give the adversary access to a decryption oracle. This is a strictly stronger definition than [[PKE#CPA-security]].

== Relationship to other primitives ==
* [[TDP]]s imply the existence of CPA-secure [[PKE]]s 

== Sufficient assumptions ==
See the sufficient assumptions for [[TDP]]s.

== Variations ==
* [[Symmetric Encryption (SE)]]
* [[Identity-Based Encryption (IBE)]]
* [[Registration-Based Encryption (IBE)]]

== Other Notes ==
* Other security definitions, named CCA1 and CCA2, exist and have historically been confused with the CCA notion outlined above