Skip to main content
Engineering LibreTexts

1.1: Syntax and Correctness for Encryption

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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\).

    Screen Shot 2019-02-11 at 10.19.08 AM.png

    • 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.

    1.1: Syntax and Correctness for Encryption is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.

    • Was this article helpful?