# 1.1: Syntax and Correctness for Encryption

The cryptographic approach to secure communication is a tool known as encryption. Before discussing the specifics of one-time pad, we will first define what pieces comprise an encryption scheme in general.

### Definition $$\PageIndex{1}$$ : Encryption Syntax

A symmetric-key encryption (SKE) scheme consists of the following algorithms:

• KeyGen: a randomized algorithm that outputs a key $$k\space\in$$ ?
• Enc: a (possibly randomized) algorithm that takes a key $$k\space\in$$ ? and plaintext $$m\space\in$$ ? as input, and outputs a ciphertext $$c\space\in$$?
• Dec: a deterministic algorithm that takes a key $$k\space\in$$ ? and ciphertext $$c\space\in$$? as input, and outputs a plaintext $$m\space\in$$ ?

We call ? the key space, ? the message space, and ? the ciphertext space of the scheme. When we use a single variable — say, $$\Sigma$$ — to refer to the scheme as a whole and distinguish one scheme from another, we write $$\Sigma$$.KeyGen, $$\Sigma$$, Enc, $$\Sigma$$.Dec, $$\Sigma$$.? , $$\Sigma$$, ?, and $$\Sigma$$.? to refer to its components.

The scheme satisfies correctness if for all $$k\space\in$$ ? and all $$m\space\in$$ ?,

$\text{Pr[Dec(}k,\text{Enc(}k,m)) = m] = 1,\nonumber$

where the probability is over the random choices (if any) made by Enc.

Encryption addresses the problem of secure communication in a very natural way:

• We imagine a sender and a receiver who wish to communicate. The sender encrypts the desired message/plaintext m using the encryption algorithm Enc and a key $$k$$ that was chosen according to a the key generation algorithm KeyGen. The result is a ciphertext $$c$$, which is sent to the receiver. The receiver can then use the decryption algorithm Dec with the same key $$k$$ to recover $$m$$.

• Because the same key is used for encryption and decryption, we refer to this style of encryption scheme as symmetric-key. It’s also sometimes referred to as secret-key or private-keyencryption; these terms are somewhat confusing because even other styles of encryption involve things that are called secret/private keys.
• The definition does not specify how the sender and receiver come to know a common key $$k$$. That problem is considered out of scope for encryption (it is known as key distribution). Rather, we are only concerned with what to do once the sender and receiver establish a shared key.
• The definition does not specify what it means to be secure. It is a syntax definition that specifies only what the honest parties (sender and receiver) are supposed to do, whereas security refers to a guarantee that holds in the presence of an adversary. We will actually spend a considerable amount of time in this course building up a good definition of encryption security, step by step.