International Association
for Cryptologic Research

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. Specifically: * We formulate a new (and relatively weak) obfuscation task regarding the ability to obfuscate random circuits of bounded length. We call such obfuscators random input & output (RIO) obfuscators. * We construct indistinguishability obfuscators for all (unbounded length) circuits given only an RIO obfuscator. We prove security of this construction under a new assumption regarding the pseudorandomness of sufficiently-long random reversible circuits with known functionality. This assumption builds on a conjecture made by Gowers (Comb. Prob. Comp. '96) regarding the pseudorandomness of bounded-size random reversible circuits and appears to be of independent interest. * We give candidate constructions of RIO obfuscators using only local, functionality preserving perturbations of the circuit structure. Our approach is rooted in statistical mechanics and can be thought of as locally ``thermalizing'' a circuit while preserving its functionality. We also provide arguments for security of the constructions and point to connections with the geometry of non-Abelian infinite groups. Given the power of program obfuscation, viability of the proposed approach would provide an alternative route to realizing almost all cryptographic tasks using the computational hardness of problems that are very different from standard ones. Furthermore, our specific candidate obfuscators are very simple and relatively efficient: the obfuscated version of an n-wire, m-gate (reversible) circuit with security parameter k has n wires and poly(n,k)*m gates. We hope that our initial exploration will motivate further study of this alternative path to program obfuscation.