Paper 2024/006

Towards general-purpose program obfuscation via local mixing

Ran Canetti, Boston University
Claudio Chamon, Boston University
Eduardo Mucciolo, University of Central Florida
Andrei Ruckenstein, Boston University

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. We start by formulating 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 then show how to construct indistinguishability obfuscators for all (unbounded length) circuits given only an RIO obfuscator --- under a new assumption regarding the pseudorandomness of sufficiently long random reversible circuits with known functionality, which in turn builds on a conjecture made by Gowers (Comb. Prob. Comp. '96) regarding the pseudorandomness of bounded-size random reversible circuits. Furthermore, the constructed obfuscators satisfy a new measure of security - called random output indistinguishability (ROI) obfuscation - which is significantly stronger than IO and may be of independent interest. We then investigate the possibility of constructing RIO obfuscators using local, functionality preserving perturbations. Our approach is rooted in statistical mechanics and can be thought of as locally ``thermalizing'' a circuit while preserving its functionality. We provide candidate constructions along with a pathway for analyzing the security of such strategies. Given the power of program obfuscation, viability of the proposed approach would provide an alternative route to realizing almost all cryptographic tasks under hardness assumptions that are very different from standard ones. Furthermore, our specific candidate obfuscators are 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 cryptography.

Available format(s)
Publication info
program obfuscationreversible circuitsthermodynamicspseudorandomnessKolmogorov complexity
Contact author(s)
canetti @ bu edu
chamon @ bu edu
mucciolo @ physics ucf edu
andreir @ bu edu
2024-01-27: last of 2 revisions
2024-01-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Claudio Chamon and Eduardo  Mucciolo and Andrei  Ruckenstein},
      title = {Towards general-purpose program obfuscation via local mixing},
      howpublished = {Cryptology ePrint Archive, Paper 2024/006},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.