Advanced Program Obfuscation Techniques and Analysis

Towards general Towards general- -purpose program obfuscation via local mixing purpose program obfuscation via local mixing Ran Canetti Claudio Chamon Eduardo Mucciolo Andrei Ruckenstein BU CS BU Physics UCF Physics BU Physics TCC 24 presentation

Indistinguishability Obfuscation is an intriguing beast [Barak-Goldreich- Impagliazzo-Rudich- Sahai-Vadhan-Yang01] Carries no intrinsic computational hardness : exists even if P=NP Yet it enables molding and amplifying raw hardness in many ways: (P<NP) & IO => OWFs, ..PRFs, NIZK, PKE, OT, FE, Den-Enc, Trapdoor Perms, Multi-linear maps, [Sahai-Waters14,Komargodski-Naor-Pass-Rosen-Yogev14, Paneth-Sahai14, Bitansky-Paneth-Wichs16, ] ( lossy f s) & sexpIO => CRH, FHE, [Canetti-Lin-Tessaro-Vaikuntanathan15, ] IO + minimal raw hardness all of crypto ?

Constructing IO Known constructions are amazing feats [Garg-Gentry-Halevi-Raykova-Sahai-Waters13, ,Jain-Lin-Sahai20,21, ,Ragavan-Vafa-Vaikutanathan24] But: use highly structured primitives (Multi-linear maps, Evasive LWE, LPN, ) have high overhead are complex ( roundabout ?)

Can IO be constructed from first principles? This work: an attempt at a first principles approach.

The basic idea: iteratively rerandomize small program segments. For circuits: ? ?(?) -Pick a circuit segment with O(1) gates -Replace by a sufficiently random functionally equivalent circuit -Repeat

Towards analysis Functionality is preserved throughout. What about security? Intuition/hope: the local perturbations would create a global effect First (na ve) idea: Show that the process converges to some stationary distribution that depends only on the truth table ?(?) ? But this would imply NP=coNP [Goldwasswer-Rothblum 08] (In fact, the mere existence of a polysize locally verifiable path between any ? ? suffices) More randomization woes: To provide meaningful randomization , new sub-circuit may need to be larger than original Overall circuit size grows No hope of reaching stationary distribution Injected randomness is clustered in small sub-circuits, may be detectable (and reversed) Some more structure seems to be needed

Reversible circuits to the rescue! ?1 ?2 . . . . . . ? ?7 ?2 ?1 ?? ?1: ?7 ?7 ?1?1,?2 ?1: 0,12 {0,1} Set of gates is ? = { ?,?,?,? ?: 0,12 0,1 , ?,?,? 1 ? }. (? = ? = ?(?3) ) Each gate ??= (??,??,??,??) computes a permutation ??_? ?2?: ???(?1 ??) = ( ?1 ??? 1,??? ?????,???,??? 1 ??) If ? = ?1 ?? ? ?? ??= ??? ??1. For each gate ?, ?? ??. (and so for each circuit C, ?|? = ?1 ???? ?1 ??.) Can embed standard circuits within reversible ones, so it suffices to consider IO for reversible circuits.

Why reversible circuits? - The reversible model gives less protections than the standard circuit model: - Information is never lost or duplicated (no fanout ) - All internal states are computable from the output - Random reversible circuits have some appealing properties!

Property 1: Property 1: Random reversible circuits are almost k Random reversible circuits are almost k- -wise independent wise independent ??,? = {? wire, ?-gate circuits} ( |??,?| = ??, ? = ? ?3 ) Theorem[Gowers 96, Hoory-Magen-Myers-Rackoff04, Brodsky-Hoory05, Odonnel-He24,Gretta-He- Pelecanos24]: For any ?,? < 2? 1 and ? ?(?,?,log 1/?), ??,? is an adaptive ?-almost ? wise independent hash family. (Proof: The reduced Cayley graph ? = { ?1 ???? 0,1?,?? ??,? = well.) ?, ? ? ? ?.?.??= ?? ?}mixes Conjecture[Gowers96, Barak18] : ? ???? ? s.t. {??,? }? ? is a (strong) pseudorandom permutation family (PRP). ( The quintessential block cipher )

Property 2 Property 2: : white box pseudorandomness of reversible circuits ? ??,? C $ ?? 1?,(? 1)? C $ ??,?? ? ??,? ? Split Circuit Pseudorandomness (SCP) assumption (simplified)

Property 3: Property 3: Potential rerandomizability of RRC s ?1 ?2 . . . . . . ? ?7 ?2 ?1 ?? 1. Each segment potentially randomizes the entire state 2. Reversibility guarantees that information about the circuit can be effectively erased 3. Random walks on the Cayley graph of ?2?are studied objects with significant structure 4. The growth of ??,?= {? ??,?|? ?} as a function of ? is relatively well understood After initial growth, can keep the circuit size fixed and eventually reach stationarity.

The candidate construction: Outline 1. Define and construct Random Circuit Obfuscators (RCOs) for random reversible circuits. 2. Use RCOs for random ?-gate circuits to construct IO for all circuits.

From RCO for short circuits to IO for all circuits Construction in three steps: (given an RCO ?:??,? ??,? ) 1. Build a random identity-circuit generator: Choose ? $??,? , compute ?1,?2 $? ? , output ?1|?2 2: For each gate (base permutation) ?, Build a random ?-circuit generator: . Reject-sample ? $ ??(??) until ? = g|? . Output ? .

From RCO for short circuits to IO for all circuits 3. Given a circuit ? = ?1 ??: (a) Sample a random ?? -circuit for each ?: ?1 ?2 ?? (b) Solder each two adjacent blocks: ?? ??+1 ??? - Secure under the SCP assumption.

A candidate RC obfuscator (for bounded ?) Fix ? = O 1 . 1. Repeat ?? times: Choose random ?-gate slice, replace by a random functionally equivalent ?2-gate slice ( inject fat ) 2. Repeat ?? times: Choose random ?10-gate slice, replace by a random functionally equivalent ?10-gate slice ( knead fat ) Questions: How fast does this process reach a stationary distribution? Is the stationary distribution the same for most circuits? (it cannot be so for all ) Is it statistically close to random? (might be, if ?is small enough ) Is it pseudorandom?

Additional open questions / future directions - Can we use presentation theory to analyze local mixing? - The word problem: How to generate /enumerate/ sample Identity circuits - Sampling identity circuits seems closely related to randomizing a circuit - Better understand the black+white box pseudorandomness of RRC s - Connection between SCP and K-complexity? MCSP? - Can we show that RRC s are universal PRPs ? - How about other animals in the crypto zoo? - OWFs from RRC s? CRHs from RRC s? PKE? FHE? (Chamon-Mucciolo-Ruckenstein23 propose FHE candidates) - How about Quantum mixing of classical circuits? - How about mixing of quantum circuits?