Encryption scheme

From CRYPTUTOR

An encryption scheme is a protocol for two parties to securely send "secret messages" over an insecure channel, so that an eavesdropper who sees the messages from the channel does not learn anything about the "secret messages". Depending on whether the two parties need to share a common secret, we call the encryption scheme private-key or public-key.

We can formally define the security in different ways, depending on our model of the eavesdropper's capabilities.

[edit]

Private-key encryption scheme

A private-key encryption scheme consists of the following 3 algorithms:

Key generation (KeyGen): A probabilistic algorithm which takes the implicit security parameter as input, and outputs a key. We view KeyGen as a distribution over keys, and use the notation $k \gets \mathsf{KeyGen}$ to denote that $k$ is chosen according to that distribution.
Encryption (Enc): An algorithm (possibly probabilistic) which takes a key and a message as input, and outputs a ciphertext. We often abbreviate $\mathsf{Enc}(k,m)$ as $\mathsf{Enc}_k(m)$ .
Decryption (Dec): An algorithm which takes a key and a ciphertext as input, and outputs a message. We often abbreviate $\mathsf{Dec}(k,c)$ as $\mathsf{Dec}_k(c)$ .

These algorithms must satisfy the following properties:

Efficiency: All three algorithms run in polynomial time in the security parameter.
Correctness: For all keys $k$ and messages $m$ , we have $\mathsf{Dec}_k( \mathsf{Enc}_k( m) ) = m$ .
Security: A security definition such as perfect secrecy, IND-CPA, SIM-CPA, IND-CCA, or SIM-CCA.

We call the space of keys, messages, and ciphertexts the key space ( $\mathcal{K}$ ), message space ( $\mathcal{M}$ ), and ciphertext space ( $\mathcal{C}$ ), respectively.

[edit]

Public-key encryption scheme

A public-key encryption scheme consists of the same three algorithms, with the following modifications:

The key generation algorithm now outputs a pair $(P K, S K)$ consisting of a private key and public key.
The encryption algorithm encrypts using only the public key (written $\mathsf{Enc}_{PK}$ ), while the decryption algorithm decrypts using only the private key (written $\mathsf{Dec}_{SK}$ ).