# 1.1: Syntax and Correctness for Encryption

- Page ID
- 7313

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*\(k\space\in\) ?**key**

- Enc:
*a (possibly randomized) algorithm that takes a key*\(k\space\in\)*? and*\(m\space\in\) ?**plaintext***as input, and outputs a*\(c\space\in\)?**ciphertext**

- 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-key*encryption; 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.