Skip to main content
Engineering LibreTexts

4.3: Indistinguishability

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

    So far we have been writing formal security definitions in terms of interchangeable libraries, which requires that two libraries have exactly the same effect on every calling program. Going forward, our security definitions will not be quite as demanding. First, we only consider polynomial-time calling programs; second, we don’t require the libraries to have exactly the same effect on the calling program, only that the effect is negligible.

    Definition \(\PageIndex{1}\)

    Letleft andright be two libraries with a common interface. We say thatleft andright are indistinguishable, and writeleft ≋ ℒright, if for all polynomial-time programs ? that output a single bit, Pr[? ◊ ℒleft ⇒ 1] ≈ Pr[? ◊ ℒright ⇒ 1].

    We call the quantity |Pr[? ◊ ℒleft ⇒ 1] − Pr[? ◊ ℒright ⇒ 1]| the advantage or bias of ? in distinguishingleft fromright. Two libraries are therefore indistinguishable if all polynomial-time calling programs have negligible advantage in distinguishing them.

    From the properties of the “≈” symbol, we can see that indistinguishability of libraries is also transitive, which allows us to carry out hybrid proofs of security in the same way as before.

    And similar to before, we also have a library composition lemma (you are asked to prove this as an exercise):

    Lemma 4.5: Composition:

    Ifleft ≋ ℒright then ℒsup>∗ ◊ ℒleft ≋ ℒ ◊ ℒrightfor any polynomial-time library.

    Bad-Event Lemma

    A common situation is when two libraries carry out exactly the same steps until some exceptional condition happens. In that case, we can bound an adversary’s distinguishing advantage by the probability of the exceptional condition.

    More formally, we can state a lemma of Bellare & Rogaway.6 We present it without proof, since it involves a syntactic requirement. Proving it formally would require a formal definition of the syntax/semantics of the pseudocode that we use for these libraries.

    Lemma 4.6: Bad Events

    Letleft andright be libraries that each define a variable bad that is initialized to 0. Ifleft and ℒright have identical code, except for code blocks reachable only when bad = 1(e.g., guarded by an “if bad = 1” statement), then


    6Mihir Bellare & Phillip Rogaway: “Code-Based Game-Playing Proofs and the Security of Triple Encryption,” in Eurocrypt 2006.

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