Skip to main content
Engineering LibreTexts

2.2: Formalisms for Security Definitions

  • 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}}\)

    We now have all the technical tools needed to revisit the security of one-time pad. First, we can restate Claim 1.3.1 in terms of libraries:

    Claim \(\PageIndex{1}\): OTP Rule

    The following two libraries are interchangeable (i.e., \(\mathscr{L}_{otp-real}\equiv\mathscr{L}_{otp-rand}\)):

    \[\mathscr{L}_{otp-real} \space\space\space\space\space\space\space\space\space\space \mathscr{L}_{otp-rand}\\ \underline{QUERY(m\space\in\{0,1\}^{\lambda}):}\space\space\space\space\space\space\space\space\space\space \underline{QUERY(m\space\in\{0,1\}^{\lambda}):}\\k\space\leftarrow \{0,1\}^{\lambda} \space\space\space\space\space\space\space\space\space\space c\space\leftarrow\space\{0,1\}^{\lambda}\\\text{return}\space k\oplus m\space\space\space\space\space\space\space\space\space\space\text{return}\space c\nonumber\]

    Note that the two libraries \(\mathscr{l}_{otp-^{\ast}}\) indeed have the same interface. Claim \(\PageIndex{1}\) is that the two libraries are have the same input-output behavior.

    Claim \(\PageIndex{1}\) is specific to one-time pad, and in the previous chapter we have argued why it has some relevance to security. However, it’s important to also have a standard definition of security that can apply to any encryption scheme. With such a general-purpose security definition, we can design a system in a modular way, saying “my system is secure as long as the encryption scheme being used has such-and-such property.” If concerns arise about a particular choice of encryption scheme, then we can easily swap it out for a different one, thanks to the clear abstraction boundary.

    In this section, we develop such a general-purpose security definition for encryption. That means it’s time to face the question,

    what does it mean for an encryption scheme to be “secure?”

    To answer that question, let’s first consider a very simplistic scenario in which an eavesdropper sees the encryption of some plaintext (using some unspecified encryption scheme \(\Sigma\)). We will start with the following informal idea:

    seeing a ciphertext should leak no information about the choice of plaintext.

    Our goal is to somehow formalize this property as a statement about interchangeable libraries. Working backwards from The Central Principle of Security DefinitionsTM, suppose we had two libraries whose interface allowed the calling program to learn a ciphertext, and whose only internal difference was in the choice of plaintext that was encrypted. If those two libraries were interchangeable, then their common interface (seeing a ciphertext) would leak no information about the internal differences (the choice of plaintext).

    Hence, we should consider two libraries that look something like:

    \[\underline{QUERY(??):}\space\space\space\space\space\space\space\space\space\space\underline{QUERY(??):}\\k\space\leftarrow\space \Sigma .\text{KeyGen} \space\space\space\space\space\space\space\space\space\space k\space\Sigma . \text{KeyGen}\\c\space\leftarrow\space\text{Enc(}j,m_L)\space\space\space and\space\space\space\space\space\space c\space\leftarrow\space\Sigma .\text{Enc(}k,m_R)\\\text{return}\space c \space\space\space\space\space\space\space\space\space\space\text{return}\space c\nonumber\]

    Indeed, the common interface of these libraries allows the calling program to learn a ciphertext, and the libraries differ only in the choice of plaintext mL vs. mR (highlighted). We are getting very close! However, the libraries are not quite well-defined — it’s not clear where these plaintexts mL and mR come from. Should they be fixed, hard-coded constants? Should they be chosen randomly?

    A good approach here is actually to let the calling program itselfchoose mL and mR. Think of this as giving the calling program control over precisely what the difference is between the two libraries. If the libraries are still interchangeable, then seeing a ciphertext leaks no information about the choice of plaintext, even if you already knew some partial information about the choice of plaintext — in particular, even if you knew that it was one of only two options, and even if you got to choose those two options.

    Putting these ideas together, we obtain the following definition:

    Definition \(\PageIndex{1}\): One-Time Secrecy

    Let \(\Sigma\) be an encryption scheme. We say that \(Sigma\) is (perfectly) one-time secret if \(\mathscr{L}^{\Sigma}_{ots-L}\equiv\mathscr{L}^{\Sigma}_{ots-R}\), where:

    \[\mathscr{L}^{\Sigma}_{ots-L}\space\space\space\space\space\space\space\space\space\space \mathscr{L}^{\Sigma}_{ots-R}\\\underline{QUERY(m_L,m_R\space\in\Sigma.M):}\space\space\space\space\space\space\space\space\space\space\underline{QUERY(m_L, m_R\space\in\Sigma. M):}\\k\space\leftarrow\space \Sigma .\text{KeyGen} \space\space\space\space\space\space\space\space\space\space k\space\Sigma . \text{KeyGen}\\c\space\leftarrow\space\text{Enc(}j,m_L)\space\space\space\space\space\space\space\space\space c\space\leftarrow\space\Sigma .\text{Enc(}k,m_R)\\\text{return}\space c\space\space\space\space\space\space\space\space\space\space\text{return}\space c\nonumber\]

    This security notion is often called perfect secrecy in other sources.\(^{[1]}\)The definition is deceptively simple, and we will explore some of its subtleties through some more examples.

    [1]Personally, I think that using the term “perfect” leads to an impression that one-time pad should always be favored over any other kind of encryption scheme (presumably with only “imperfect” security). But if you want encryption, then you should almost never favor plain old one-time pad.

    This page titled 2.2: Formalisms for Security Definitions is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .

    • Was this article helpful?