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).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Towards General-Purpose Program Obfuscation via Local Mixing

  • Ran Canetti,
  • Claudio Chamon,
  • Eduardo R. Mucciolo,
  • Andrei E. Ruckenstein

摘要

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).