Public Key Encryption (PKE)

From Cryptology City
Revision as of 14:35, 4 July 2024 by Axhoover (talk | contribs)
Jump to navigation Jump to search


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 [RSA78] and [Elg85].

Formal Definition

Syntax

A Public Key Encryption (PKE) scheme is a tuple of efficient functions , with respect to a keyspace , plaintext space , and ciphertext space , such that:

  • , is a randomized function that takes a security parameter, and outputs a public key and secret key
  • , is a randomized function that takes a public key and plaintext message , and outputs a ciphertext ,
  • , is a deterministic function that takes a secret key and ciphertext , and outputs a plaintext message .

Chosen Plaintext Attack (CPA) Security

A PKE scheme is CPA-secure if for all efficient adversaries , there exists a negligible function , such that

where and is a uniformly random bit.

Chosen Ciphertext Attack (CCA) Security

A SE scheme is CCA-secure if for all admissible efficient adversaries , there exists a negligible function , such that

where and is a uniformly random bit. Further, we say an adversary is admissible if it never queries on the ciphertext given to 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

  • TDPs imply the existence of CPA-secure PKEs

Sufficient assumptions

See the sufficient assumptions for TDPs.

Variations

Other Notes

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