Towards General-Purpose Program Obfuscation via Local Mixing

Towards General-Purpose Program Obfuscation via Local Mixing

연구 분야: Analysis

학회: Theory of Cryptography Conference

We explore the possibility of obtaining general-purpose obfuscation for all circuits by way of making only simple, local, functionality preserving random perturbations in the circuit structure. Towards this goal, we use the additional structure provided by reversible circuits, but no additional algebraic structure. Our approach is rooted in statistical mechanics and can be thought of as locally “thermalizing” a circuit while preserving its functionality. We analyze the security of this approach in two steps. First, we provide arguments towards its security for a relatively simple task: obfuscating random circuits of bounded length. Next we show how to construct indistinguishability obfuscators for all (unbounded length) circuits given an obfuscator for random reversible circuits of bounded length. Here security is proven under a new assumption regarding the pseudorandomness of sufficiently-long random reversible circuits. Our specific candidate obfuscators are very simple and relatively efficient: the obfuscated version of an n-wire, m-gate (reversible) circuit with security parameter \(\kappa \) has n wires and \(O(\kappa m)\) gates. We hope that our initial exploration will motivate further study of this alternative path to program obfuscation (and, consequently, to cryptography in general).