Vitalik lands on local mixing as obfuscation series reaches third stage

Ethereum co-founder Vitalik Buterin has published the third installment of his cryptographic obfuscation series on Friday. 

He examined a method called “local mixing” that throws out lattices and elliptic curves in favor of ideas lifted from hash function design.

Buterin had published Part I on June 29, and the second one, which is the diamond iO writeup, was published on July 28. 

In those publications, he touched on lattice-heavy constructions. With local mixing, Buterin said that it is “a totally different way of doing cryptography.” In his post, he wrote that local mixing has no elliptic curves, no prime factorization, and no lattices anywhere in the design.

According to Buterin, the closest relative to local mixing is symmetric cryptography, which is the discipline behind everyday encryption and hashing.

Junk gates and a circuit run in reverse

The local mixing process starts with a circuit made of logic gates such as XOR, AND, and NOT, that goes through a pipeline that keeps the output identical while it scrubs away any trace of the internal logic.

Buterin wrote that local mixing goes through the following original circuit, adding reversibility, hardening, gadgetization, mixing, and finally obfuscation.

During mixing, junk gates are scattered through the circuit. The arrangement is then shuffled, and it swaps out small blocks for different gates that compute the same thing.

However, it is not enough on its own, and that is why the other steps are important, as they do most of the work.

Reversibility comes first because it makes the rest possible. Buterin explains that a reversible gate can be rewritten as an arbitrary pile of other reversible gates with matching behavior. This is harder to do with an AND or an OR. 

A bet built on past failures

Buterin still called local mixing a “wild and risky bet,” writing that it sits on “a graveyard of failed attempts at white-box cryptography.” 

However, he pointed out that the authors of local mixing say that more efforts, along with a willingness to accept higher overhead, could make the idea hold.

One proposed shortcut is artificial intelligence, as it could compress the three decades of hash functions needed to mature into a span of a few years. However, it moves away from the lattice-based routes, where the trade-off was security assumptions.

Buterin called obfuscation the “final boss of cryptography” in his June publication, and he called it “the final frontier of cryptography” in this latest publication. 

He said the most rigorous constructions carry “literally galactic” runtimes, longer than the lifetime of the universe. 

Why is obfuscation worth the trouble?

A program can be turned into an encrypted version that still runs on ordinary inputs using obfuscation. Here, ordinary outputs are returned while hiding their code.

When obfuscation is paired with a blockchain, it gets close to a “trustless trusted third party” that enables things like private, collusion-resistant voting with no M-of-N committee to trust.

If you're reading this, you’re already ahead. Stay there with our newsletter.