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.
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 ≋ ℒ∗ ◊ ℒrightfor any polynomial-time library ℒ∗.
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
6Mihir Bellare & Phillip Rogaway: “Code-Based Game-Playing Proofs and the Security of Triple Encryption,” in Eurocrypt 2006. ia.cr/2004/331