# 4.3: Indistinguishability

- Page ID
- 7336

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

*Let* ℒ_{left} *and* ℒ_{right} *be two libraries with a common interface. We say that* ℒ_{left} *and* ℒ_{right }*are indistinguishable, and write* ℒ_{left} ≋ ℒ_{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 distinguishing*ℒ

_{left}

*from*ℒ

_{right}.

*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:**

*If* ℒ_{left} ≋ ℒ_{right} *then* ℒsup>∗ ◊ ℒ_{left} ≋ ℒ^{∗} ◊ ℒ_{right}*for 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**

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

^{6}Mihir Bellare & Phillip Rogaway: “Code-Based Game-Playing Proofs and the Security of Triple Encryption,” in Eurocrypt 2006. __ia.cr/2004/331__