Obfuscators - 暗号理論教室

---

Def (Obfuscator)

F : a family of functions
a PPT O is an obfuscator of F if

• 【(Statsitical) Approximate Functionality】
  • ∀F ∈ F, Pr_{coins of O}[ ∃x, O(F)(x) ≠ F(x) ] ≦ ε(n). （普通のO(F)はパーフェクト）
• 【Polynomial Slowdown】
  • ∃p: poly, ∀F ∈ F, O(F) runs in time ≦ p(time(F)).
• 【Virtual Black-box property】
  • ∀A : nonuniform PPT, ∀p: poly, ∃S: nonuniform PPT, ∀F ∈ F,
  • | Pr[ b ← A(O(F)) : b = 1 ] - Pr[b ← S^F : b = 1] | ≦ 1/p(n). （n >> 0）

Theorem (Obfuscator)

Obfuscators do not exist.

Proof Idea

Suppose ∃ O : obfuscator.

Take ∀α, β ∈ {0,1}^k.

• C_{α, β}(x) := return β if x = α, or 0^k otherwise.
• D_{α, β}(C) := return 1 if C(α) = β, or 0 otherwise.

Consider an adversary A doing

• A(C, D) := return D(C).

Then

• Pr[ A(O(C_{α, β}), O(D_{α, β})) = 1 ] = 1.

So, especially when α ← {0,1}^k, β≠0^k,

• 1 ≒ Pr[ S^{C_{α, β}, D_{α, β}} = 1 ]
• ≒ Pr[ S^{Z_k, D_{α, β}} = 1 ]
  • Z_k : a TM that always output 0^k
• ≒ Pr[ A(O(Z_k), O(D_{α, β})) = 1 ] ≒ 0.

Contradiction!

Construction in the random oracle model

F_x denotes a point function that outputs 1 for x.
F_{x, y} denotes a point function that outputs y for x.
Let R be a random oracle.

O(F_x) :

• z = R(x)
• return "on input y, return 1 if R(y) = z, or 0 otherwise".

O(F_{x, y}) :

• r ← {0,1}ⁿ
• z₁ = R₁(x,r)
• z₂ = R₂(x,r) + y
• return "on input a, return z₂ + R₂(a, r) if R₁(a, r) = z₁."

Def (Computational approximate functionality)

F : a family of functions
a PPT O is an obfuscator of F with computational approximate functionality if (Polynomial Slowdown), (Vritual Black-box property) and

• ∀F ∈ F, ∀A : a nonuniform PPT, Pr[ x ← A(O(F)) : O(F)(x) ≠ F(x) ] ≦ ε(n).

Def (Statistical Perfect One-Way Function)

A probabilistic function family H = {H_k}_k is a statistically perfect one-way (POW) function if

• 【Efficient Verification】
  • ∃V_H: PT, ∀k ∈ K_n, ∀x ∈ {0,1}ⁿ, ∀r ∈ {0,1}ⁿ, V_H(x, H_k(x, r)) = 1. （それら以外では0）
• 【Collision Resistance】
  • ∀A: nonuniform PPT,
  • Pr[ k ← K_n, (x₁, x₂, y) ← A(k) : x₁ ≠ x₁, V_H(x₁, y) = V_H(x₂, y) = 1 ] ≦ ε(n).
• 【Statistical 2-indistinguishability】
  • ∀X = {X_n}: well-spread, ∀k ∈ K_n,
  • Δ( (H_k(X_n, R_n¹), H_k(X_n, R_n²)), (H_k(U_n¹, R_n¹), H_k(U_n², R_n²)) ) ≦ ε(n).

Theorem (Obfuscator with computational approximate functionality)

Obfuscators with computational approximate functionality exist for point functions.

Construction

Let H be a POW function.

O(F_x) :

• z = H(x)
• return "on input y, return 1 if V_H(y, z) = 1, or 0 otherwise".

O(F_{x, y}) : // t = |y|

• r₁, ... , r_t+1 ← {0,1}ⁿ
• u₁ = O(F_x; r₁)
• i ∈ [1..t]:
  • z_i+1 = x if y_i = 1, or uniform if y_i = 0
  • u_i+1 = O(F_zi+1; r_i+1)
• return "on input a,
  • u₁(a) =^? 0: return 0
  • else i ∈ [2..(t+1)]: y_i-1 = u_i(a)
  • return y = y₁...y_t."

上へ

---