Key Highlights
- Vitalik Buterin released the third and final post in his series on indistinguishability obfuscation (iO), focusing on the emerging local-mixing approach.
- Unlike mainstream and diamond iO methods, local mixing draws on principles from symmetric cryptography rather than elliptic curves, factoring, or lattice-based assumptions.
- The technique transforms circuits into reversible circuits and replaces functional sections with randomly selected equivalent circuits to obscure their internal structure.
Ethereum co-founder Vitalik Buterin has released the third and final post in his series on cryptographic obfuscation, known as indistinguishability obfuscation, or iO. The post examines local mixing, a distinct approach to constructing obfuscation protocols.
In the previous two parts of the series, Buterin covered the mainstream line of iO protocols that rely on assumptions closer to standard cryptography but involve high computational overhead and diamond iO, which incorporates novel lattice-based assumptions to reduce overhead while remaining impractical for general use.
The latest post focuses on local mixing as the third major family under development.
Distinct approach to cryptography
The post explores local mixing, which he mentions differs from the other approaches. It does not rely on elliptic curves, prime factorization, or lattices. Instead, it draws from principles in symmetric cryptography, such as the design of encryption schemes and hash functions.
Symmetric cryptography has developed through iterative processes of proposing functions intended to be pseudorandom, analyzing them for weaknesses and refining designs. Examples of resulting standards include SHA and BLAKE.
Local mixing applies similar methods to circuits composed of logic gates such as XOR, AND, and NOT. The objective is to transform a circuit so that its functionality remains intact while internal logic becomes obscured.
Circuit transformation pipeline
The process begins by converting the original circuit into a reversible circuit that can execute both forward and backward. Reversible circuits facilitate mixing because a single reversible gate can be substituted with multiple alternative reversible gates that perform the same function. Irreversible gates, by contrast, collapse entropy, which can reduce the number of possible outputs in longer circuits.
An example used is a two-bit adder. After conversion, the circuit incorporates multiple copies of an “r57” gate with three inputs and three outputs. Additional junk inputs are included, some set to fixed values of 0 or 1, to support intermediate computations and output storage.
A subsequent hardening step, referred to in some work as sandwiching, transforms the reversible circuit so that it can only execute the original function on given inputs without alternative manipulations. Sandwiching is described as a form of hardened Toffoli construction suited to cases without a prior reversibilization step, particularly for obfuscating random permutations.
Generation mixing process
Another section includes Generation mixing, which involves creating a table of all small circuits that share identical functionality. Sets of gates that are contiguous or non-interfering are selected from the circuit. These are replaced with randomly chosen equivalent small circuits from the same class in the table.
The new sub-circuit is then repositioned within a range of legal locations that preserve overall functionality. The procedure includes optimization steps such as canonicalization to identify equivalent circuits, conversion to polynomial form, and a rainbow-table mechanism for efficient storage and querying.
Multiple rounds and phases of mixing are applied, with some phases expanding the circuit size and others maintaining or slightly reducing it. The aim is to cover each gate repeatedly.
Gadgetization introduces additional structures to achieve nonlinearity and minimum-correlation-weight properties for individual gates. It does not provide security against pattern-matching attacks on its own and requires subsequent mixing. Mixing addresses structural leakage, while gadgetization targets certain algebraic properties. The relative contribution of each component remains an area of ongoing examination.
Security objectives and current scope
The target properties include the absence of detectable relationships between executions of the obfuscated circuit and the original circuit. Current efforts prioritize obfuscation of random circuits.
Successful obfuscation of random circuits would enable constructions such as public-key encryption and, with additional overhead, general-purpose obfuscation. The local mixing pipeline is under active development, with authors planning further publications.
Public endpoints and technical details of the approach are available through the associated research repository and Buterin’s post.
Also Read: Ethereum Price Eyes $3,000 After ETH Rally Nears $2,450
