THE DISTINGUISHER'S TABLETABLE I/IVROUND 1ε = 0.25ALLOWANCE 500
A game of one reduction
The Distinguisher's Table
◆
Proving that PRG security implies EAV security — by playing the reduction, one round at a time.
▸ Press start ◂
Music begins when you start · ♪ in the top bar mutes it
Briefing
You are the distinguisher
◆
The challenger deals you a string w from one of two sources, and will not say which. Either w = G(k) for a hidden seed, or w is uniformly random. Tell them apart and you have broken G — which nobody has ever done.
You cannot read w. It is noise either way. What you can do is hire Ā, an eavesdropper who breaks Enc(k,m) = G(k) ⊕ m with advantage ε — and turn Ā's talent into an answer about w.
Assembly · Part I of IV
What the challenger hands you
Rejected
Table I
The Braggart
◆
D · you
Ā · under contract
the challenger
the challenger waits
BREAK
◂ uniformevidencepseudorandom ▸
hands dealt 0 · matched 0 · rate —odds 1 : 1
Round 1
BP
Observed rate · the two hypotheses
The call
Which source is dealing?
◆
Result
◆
Hover the plot to read a point.
◆ The theorem ◆
An adversary you cannot use is an adversary that cannot hurt you.
◆
Field Manual
The scheme Ā attacks
G : {0,1}ⁿ → {0,1}^ℓ(n), ℓ(n) > n
Gen(1ⁿ) : k ← {0,1}ⁿ
Enc(k, m) : G(k) ⊕ m for m ∈ {0,1}^ℓ(n)
Dec(k, c) : G(k) ⊕ c
The game you are playing
G is a PRG if ℓ(n) > n and for every probabilistic
polynomial-time D there is a negligible negl with
| Pr[ D(G(k)) = 1 ] − Pr[ D(w) = 1 ] | ≤ negl(n)
for uniform k ← {0,1}ⁿ and uniform w ← {0,1}^ℓ(n).
You are D. The two probabilities are the two lines on
the strip. Your job is to pull them apart.
The game Ā wins
PrivK^eav_{A,Π}(n):
1. A(1ⁿ) outputs m₀, m₁ with |m₀| = |m₁|
2. k ← Gen(1ⁿ); b ← {0,1}; c ← Enc(k, m_b)
3. A(c) outputs b′
4. the experiment outputs 1 iff b′ = b
Ā's contract says Pr[b′ = b] = 1/2 + ε.
Rounds, BP and Break
Each round you deal hands and gain 1 BP (max 5).
Boost spends BP to deal many hands at once.
Every hand tilts the evidence meter. When it reaches
either BREAK line the odds are 20:1 and you may call.
Allowance is your polynomial budget of hands. It is
finite, on purpose.
Negligible
f is negligible if for every polynomial p there is N
with f(n) < 1/p(n) for all n > N.
Table IV uses ε = 2⁻⁶⁴. That is what negligible feels
like from your side of the table.
The machine you assembled
Ā never learns it is inside anything: every ciphertext it sees has the shape it was promised. The one thing you add is the coin b, kept outside Ā's view — which is why you can grade Ā's answer and Ā cannot.
Standard construction and proof: J. Katz & Y. Lindell, Introduction to Modern Cryptography, Theorem 3.18 (§3.3.3).