MachinaIO: Project Proposal to Build Practical Indistinguishability/Ideal Obfuscation and its Applications

# MachinaIO: Project Proposal to Build Practical Indistinguishability/Ideal Obfuscation and its Applications Authors: Sora, Enrico  ## Introduction This document proposes the establishment of a new research team within PSE to develop the first practical implementation of an indistinguishability/ideal obfuscation (iO) scheme that is built based on popular cryptographic assumptions. Many applications leveraging advanced cryptography, specifically multi party computation (MPC) and (multi-key) fully homomorphic encryption (FHE), rely on a committee where a majority exceeding a certain threshold of its members must remain honest and stay online even beyond the setup phase. This requirement introduces a trade-off between the security and scalability of such applications. Improving scalability by increasing the hardware requirements for committee parties raises the cost of participation, which reduces the number of committee members and their decentralization, thereby increasing the risk of adversarial collusion. We address this issue by developing a practical implementation of indistinguishability/ideal obfuscation (iO). In essence, iO transforms any program into a black-box representation that hides its inner workings without altering its functionality. While users can locally execute obfuscated programs on arbitrary inputs, they gain no additional information beyond the input-output relation of the program. These features of iO eliminate the need for a committee in applications based on MPC and FHE. As a result, iO provides these applications with unlimited scalability while preserving their security. Furthermore, we believe Ethereum can play a complementary role in the context of iO. For example, while iO obfuscates stateless programs, Ethereum provides a platform for preserving private states, accessible and modifiable only by the obfuscated program. On the other side, developments in iO will unlock a new range of on-chain applications based on encrypted smart contracts. This synergy indicates that some demand for iO could translate into demand for Ethereum. ## Risk of the project ### Technical evidences supporting the feasibility of practical iO Although many people, including cryptography researchers, have considered iO to be merely a theoretical concept, the following technical evidences show that our attempt to build practical iO is promising. First, assuming FHE and SNARK, the only operations that need to be obfuscated are FHE decryption and SNARK verification [GGH+13, BIS+17]. Specifically, FHE handles main computation of the circuit being obfuscated, which is proved with SNARK. On the other hand, a circuit obfuscated by (minimum) iO simply decrypts the given FHE encryption of the circuit output with the hardcoded FHE secret key, if and only if the given proof of the correct homomorphic evaluation is valid. This suggests that 1) the effifiency of iO can be optimized for the simple and specific functionality and 2) the rapid improvements in the efficiency of FHE and ZKPs in recent years will similarly improve the efficiency of iO. Second, in October 2024, [AKY24a] and [BDJ+24] proposed new obfuscation schemes based on LWE and evaisve LWE assumptions. Notably, [AKY24b], a companion paper to [AKY24a], presented a remarkably simple construction of functional encryption (FE), which is a main building block of iO, in just two pages. Therefore, we expect we can easily implement it within three months. Additionally, its efficiency can be improved by replacing the LWE-based construction with one based on ring-LWE (RLWE). In fact, benchmarks in [DDP+17] demonstrate that the homomorphic evaluation algorithm of the BGG+ encoding, which could be a major bottleneck in this FE scheme, performed a binary NAND tree circuit with 128 encoded bits at depth 7 in 643 ms, and another circuit with 1024 encoded bits at depth 10 in 9,411 ms. Third, most of the iO building blocks described above rely on FFT, which can be easily parallelized using GPUs. Notably, if FFT is the main bottleneck in these building blocks, a larger number of GPUs might allow evaluating obfuscated circuits with a greater number of gates without substantially increasing the execution time. ### Side-quest deliverables Although achieving a secure and practical iO in a short period is challenging, we can implement the following useful iO building blocks as side-quest deliverables with a high probability. **(Updated in June, 2025) Functional Encryption (FE):** Functional encryption (FE) is another building block that can be useful for Ethereum, enabling non-interactive private delegation of computation. For example, consider a scenario where Alice wants to make an on-chain transaction if her intent satisfies a certain algorithm $f$. With FE, she can non-interactively delegate this process to an untrusted party without revealing her intent and private key, and without running the entire algorithm $f$ herself. Notably, FE is stronger than FHE because FE decryption directly provides the plaintext result of the function output, removing the need for interaction with the encryptor. These advantages are significant especially when 1) $f$ is complex such as a deep-learning algorithm, or 2) the encryptor goes offline quickly, for example, due to a weak Internet environment. Specifically, we can implement the FE scheme proposed in [AKY24b]. Moreover, if it is acceptable for the user’s ciphertext to be usable with only a single algorithm, the FE scheme can be simplified to laconic function evaluation, eliminating the need for lattice preimages—the most expensive component of the [AKY24] construction.   ### Remaining bottlenecks There are still three challenges to be addressed in building a practical iO. 1. Efficient bootsrapping from FE to iO. 2. SNARK scheme easily verifiable inside iO. 3. Sub-exponential security loss. The first challenge is the largest bottleneck because existing bootsrapping techniques in [BV15, AJ15] requires running FE encryption recursively. We already have a concrete idea of a more straightforward bootstrapping techniques that is based on the FE scheme in [AKY24b]. **Updated in June, 2025:** We have proposed a new iO construction called [Diamond iO](https://eprint.iacr.org/2025/236.pdf) that solves the first challenge. This replaces the recursive FE encryption with simple matrix operations. The second challenge is also important. Since recent lattice-based SNARK schemes were not designed with iO usage in mind, there may be an opportunity to optimize them for iO. For example, we are considering to optimize the latest designated-verifier SNARK proposed in [SSE+22]. **Updated in June, 2025:** We identified that the biggest bottleneck to support SNARK verification within iO is the input size of the obfuscated circuit. While lattice-based SNARK schemes require more than 10KB proof size, [our current implementation can support only a few input bits](https://machina-io.com/posts/hello_world_first.html). Therefore, the second challenge requires increasing the input size. The third challenge implies that, to make the implementation consistent with the theoretical security proof, some parameter sizes must be increased on the order of $2^L$, where $L$ is the bit size of the input. Although larger parameters reduce efficiency, having parameter sizes smaller than those required by the security proof does not immediately mean that the iO scheme is vulnerable to concrete attacks. Therefore, we plan to overlook this issue until the development of a production-level application, and we will focus on quickly creating a proof-of-concept (PoC) implementation and demonstration applications. More detailed steps to resolve each challenge is described below. ## Milestones We set the following milestones for the period from January to November 2025. - [x] end of Feb 2025 - Invent a new iO scheme that is more straight-forward to understand and implement. It is assumed to solves the **challenge #1**. However, the scheme is still "leveled" because parameters depends on the total input size. - Estimate its performance, such as circuit size and error growth. - Publish a paper describing our solution -> Published at https://eprint.iacr.org/2025/236. - [x] end of March 2025 - Construct an E2E toy implementation of `Obfuscate` and `Evaluate` algorithms of Diamond iO in its RLWE version. - Publish an article (either blogpost or paper) describing our solutions + the implementaton.   - [ ] end of August, 2025 - Construct an efficient lookup table evaluation on BGG+ encodings of public data, i.e., public lookup evaluation. Note that they will be useful not only for iO but also for many cryptographic primitives, such as attribute-based encryption, laconic function evaluation, and functional encryption. - Publish the implementation. - Publish a paper about this technique and its applications in September. - [ ] end of October 2025 - Implement FHE evaluation on BGG+ encodings and leverage it to homomorphically evaluate PRF on the encodings. - Publish the implementation. - [ ] by Devconnect - Construct an "input-scalable" iO scheme (no longer levelled) such that the parameters are independent of the total input size. To achieve this, we will develop a noise refershing technique for the Diamond iO. - Publish article (either blogpost or paper) describing our solutions + the implementaton.  - [ ] after Devconnect - Construct an obfuscated program performing ZKP verification, implying that we will solve the **challenge #2** at this stage. ~~This would require extensive research over lattice-based ZKP schemes to choose or invent the best candidate. Note that by accomplishing this task we would be able to achieve iO construction for **all** circuits leveraging the bootstrapping techniques from [GGH+13].~~ (**Updated in July 15th**) we focus on implementing the ZKP verification first. This allows building a practical witness encryption, which is already useful for many trustless applications such as [trustless bitcoin bridge](https://ethresear.ch/t/trustless-bitcoin-bridge-creation-with-witness-encryption/11953/28). - Publish an article (either blogpost or paper) describing our solutions + the implementaton. - [ ] after Devconnect - Deliver an interesting iO-based application. It should be simple to implement while able to communicate the core value proposition of iO. ~~Specifically, we plan to build a demo of untraceable mixing protocol using iO.~~ - Publish an article (either blogpost or paper) describing the application + the demo implementaton.    **⚠️ Warning**: the above milestones are set based on our current knowledge. Depending on the outcomes of the research, some of these milestones may be delayed or modified in the future. In such scenarios, we could consider exploring approaches other than the current lattice-based iO. Nevertheless, we commit to try our best to deliver a demo application to present the power of iO at Devconnect 2025.   ## Team members We are a team of 2 FTE as follows: - 1 FTE for Sora: He leads the team - 1 FTE for Enrico: Researcher We actively look for adding more cryptography enginners/researchers. ## Team Strategy We will actively collaborate with academic researchers to ensure security while trying to optimize concrete efficiencies. After we complete at least the first implementation of iO, we plan to apply grants from ESP to secure funds for additional team members and hardwares to run our implementations. ## References - [JLS22] https://eprint.iacr.org/2021/1334.pdf - [AKY24a] https://eprint.iacr.org/2024/1720.pdf - [BDJ+24] https://eprint.iacr.org/2024/1742.pdf - [AKY24b] https://eprint.iacr.org/2024/1719.pdf - [CCM+24] https://eprint.iacr.org/2024/006.pdf - [Wee22] https://eprint.iacr.org/2023/906.pdf - [VWW22] https://eprint.iacr.org/2022/1140.pdf - [HLL23] https://eprint.iacr.org/2023/1716.pdf - [BGG+14] https://eprint.iacr.org/2014/356.pdf - [GGH+13] https://eprint.iacr.org/2013/451.pdf - [JLS20] https://eprint.iacr.org/2020/1003.pdf - [BOK+15] https://mediatum.ub.tum.de/doc/1246288/1246288.pdf - [SAS24] https://eprint.iacr.org/2024/762.pdf - [BIS+17] https://eprint.iacr.org/2017/240.pdf - [DDP+17] https://eprint.iacr.org/2017/601.pdf#page=16.76 - [ISW21] https://eprint.iacr.org/2021/977.pdf - [SSE+22] https://eprint.iacr.org/2022/1690.pdf - [Gro16] https://eprint.iacr.org/2016/260.pdf - [OB22] https://eprint.iacr.org/2021/1530.pdf - [AJ15] https://eprint.iacr.org/2015/173.pdf - [BV15] https://eprint.iacr.org/2015/163.pdf