The Quest for Practical iO with Machina iO

Anna Rose and Tarun engage with Sora and Enrico from Makina IO to discuss their work on Indistinguishability Obfuscation (IO), a form of program obfuscation that makes two equivalent programs indistinguishable once obfuscated. Although IO is largely theoretical, Makina is pursuing early implementations to address its impracticality and explore its potential. Sora shares his journey into IO, highlighting a paper that discusses IO construction from standard waveform assumptions. He raises concerns about the security of smart contracts using Multi-Party Computation (MPC) or Fully Homomorphic Encryption (FHE), suggesting that IO could enable smart contracts to handle secrets without human oversight, offering advantages over ZK and FHE.

Enrico emphasizes the necessity of privacy for businesses submitting invoices and initially explored FHE but found it inadequate due to trust distribution issues, leading him to investigate IO as a more reliable solution. The conversation touches on IO's experimental status within Ethereum's roadmap, aligning with the foundation's privacy goals. Protecting privacy in applications requires more than just Zero-Knowledge Proofs (ZKP), as decentralized exchanges and cross-chain bridges necessitate additional technologies. IO is positioned to secure data management, particularly for private keys, and could simplify processes in cross-chain bridges without exposing sensitive information.

Makina IO aims to replace existing systems based on MPC and threshold cryptography. IO is also seen as a means to enhance FHE applications by embedding decryption logic within an obfuscated program, thus removing reliance on a trusted committee. The discussion includes technical details about IO's construction, involving the separation of circuits into public and private bits and the challenges of computation space, indicating a shift towards linear algebra in Learning With Errors (LWE) for practical implementation.

The conversation examines assumptions in LWE and Ring LWE, emphasizing the significance of understanding these assumptions, particularly the reliance on lattice assumptions. The all product LWE assumption posits that variations of LWE instances remain secure despite revealing input patterns, while evasive LWE has faced counterexamples that apply only to specific cases, leaving its overall security uncertain. The relationship between LWE and IO is discussed, noting that while stock LWE suffices for FHE, it is inadequate for IO due to information leakage about the circuit.

Recent papers inform the core construction of IO, including a new algebraic approach to functional encryption and the diamond IO paper, which incorporates the product LWE assumption. The speaker notes a security gap between FHE and IO, raising questions about the equivalence of assumptions and the complexity of implementations. Larger input sizes lead to increased matrix requirements and accumulated error, making current implementations impractical, as demonstrated by lengthy obfuscation times and large program sizes.

Optimization potential is discussed, drawing parallels to FHE techniques like bootstrapping to enhance IO practicality. The construction employs selection matrices for encoding evaluator input bits, ensuring obfuscation without revealing internal workings. Security proofs focus on maintaining independence and security across different input paths, with the all product assumption being critical. The complexity of Input/Output (I/O) in relation to Boolean functions and circuit sampling is highlighted, stressing the need for appropriate benchmarks targeting larger input sizes.

The podcast discusses the benchmarking of IO and its applications, emphasizing its potential as a universal tool for constructing various cryptographic primitives. One speaker suggests that reductions using IO for simpler tasks may be more beneficial than using raw IO directly. Current limitations in separating input bits are noted, along with unit tests for IO applications focusing on basic operations. The transition from functional encryption to IO is described as not significant, as many concepts overlap.

Gentry's 2012 paper is referenced in the context of zero-knowledge proofs, clarifying his influence on both fully homomorphic encryption and zk proofs. The speakers acknowledge significant contributions from Pia Park and others, emphasizing the project's openness to new contributors and the need for better documentation. The podcast addresses the post-quantum security of IO, noting that it can be considered quantum safe under certain security assumptions. The current state of IO constructions is discussed, with a focus on standard assumption constructions and the potential for post-quantum IO if new lattice assumptions are secure against both classical and quantum adversaries.