Indistinguishable obfuscation and its applications

lynndell 03 Jun 2025

Indistinguishable obfuscation

1. Introduction

Program Obfuscation refers to the process of transforming a polynomial-time algorithm into a functionally equivalent one that does not reveal any internal state. This concept was first proposed by Hada [1] and Barak et al. [2], but was shown to be impossible to achieve in general. Barak et al. [2] introduced the notion of Virtual Black-Box (VBB) security, which allows a program to be executed securely as if inside a virtual black box—producing the same output for a given input without leaking any additional information. However, further research demonstrated that VBB is also unachievable for general functionalities. As a result, later studies focused on achieving obfuscation for specific classes of functions.

A significant breakthrough came from Garg et al. [3], who proposed a candidate construction for Indistinguishability Obfuscation (iO) based on Multilinear Maps [4]. They also demonstrated the powerful applications of iO in areas such as functional encryption. Indistinguishability obfuscation requires that if two algorithms produce the same output for every input, then their obfuscations must be computationally indistinguishable. A large body of research (e.g., [5, 6, 7]) has since shown that most cryptographic applications can be realized using iO (along with one-way functions), and some even regard iO as cryptographically complete.

The first class of obfuscation techniques typically relies on multilinear maps [3, 8, 9], as these structures support both homomorphic multiplication and addition. However, all existing multilinear map constructions are not based on standard cryptographic hardness assumptions and are vulnerable to various attacks [10, 11]. In addition, several iO constructions based on multilinear maps have been subject to concrete attacks [12].

A second line of work explores constructions of iO that either do not rely on multilinear maps or significantly reduce their use. Bitansky and Vaikuntanathan [13] showed how to realize iO using only functional encryption. Lin [14] and Lin–Vaikuntanathan [15] proposed iO constructions based on constant-degree multilinear maps, with the eventual goal of basing iO entirely on standard bilinear map assumptions, which are currently believed to be secure.

Later efforts aimed to construct iO from smaller-degree or constant-degree multilinear maps [16]. Lin and Tessaro [17] proposed an iO candidate using multilinear maps of degree $L\ge 2$, together with pseudorandom generators (PRGs) possessing special locality properties. However, it was shown that the PRGs required for the $L=2$ case are insecure and, in fact, impossible to construct [18]. At present, the only known iO constructions rely on trilinear maps [19].

Finally, other works such as [20, 21] introduced new techniques to address these security challenges and develop iO constructions based on bilinear maps. Nonetheless, these constructions remain candidate schemes, as they also depend on novel pseudorandom objects with unstandardized security properties.

2. Basic Concepts

Source Code: For example, C language, which is clear in expression and easy to understand.

Code Obfuscation: Replaces C program keywords globally, unrolls for loops, compiles into machine code, and applies numerous optimizations and redundant insertions during compilation. As a result, after obfuscation, the machine code is difficult to comprehend, achieving an obfuscation effect. Two pieces of code may serve the same function, i.e., given an input $x$, both return the function value $f(x)$.

Limitations of Code Obfuscation: While humans may not understand the machine code, a machine can decompile it back into C code, making it easier to analyze. From a cryptographic perspective, code obfuscation leaks information and is thus insecure.

Cryptographic Requirement of Indistinguishability Obfuscation (iO): The obfuscated code should be secure - no polynomial-time adversary should be able to extract meaningful information. Virtual Black Box: A hypothetical ideal black box in which a program is placed. The user may input values and receive corresponding outputs, but no polynomial-time adversary can extract program internals or related information.

Indistinguishability Obfuscation: Requires both functionality and security to be equivalent to the virtual black box.

Only Difference: The virtual black box is typically realized in hardware (e.g., trusted execution environments) or is idealized (and thus non-existent), whereas indistinguishability obfuscation is achieved via algorithmic (software-based) methods.

Program Requirements: The program must not be of a type where outputs reveal internal structure, such as the Fibonacci sequence, geometric/arithmetic progressions, etc. It should instead be a program such as digital signature generation with a private key (input data $\rightarrow$ output signature) or symmetric encryption with a private key (input data $\rightarrow$ ciphertext), which does not leak private keys or intermediate states.

In essence, the virtual black box is conceptually equivalent to indistinguishability obfuscation.

3. Indistinguishability Obfuscation

Concept: Given two programs with identical functionality, if no polynomial-time adversary can distinguish between their obfuscated versions, this property is called indistinguishability obfuscation (iO).

Definition: A polynomial-time machine $i\mathcal{O}$ is said to be an indistinguishability obfuscator for a class of circuits ${\mathcal{C}_\lambda}$ if it satisfies the following:

Functionality Preserving: The obfuscated program $i\mathcal{O}(C)$ has the same functionality as the original program $C$. That is, for any input $x$, the output values are identical, i.e., $C(x)=i\mathcal{O}(C)(x).$
Indistinguishability: If two programs $C_1$ and $C_2$ are functionally equivalent, i.e., produce the same output $C_1(x)=C_2(x)$ for all inputs $x$, then no polynomial-time adversary can distinguish their obfuscated versions $i\mathcal{O}(C_1)$ and $i\mathcal{O}(C_2)$, i.e., $\Pr[\mathcal{A}(i\mathcal{O}(C_1)) = 1] \approx \Pr[\mathcal{A}(i\mathcal{O}(C_2)) = 1]$
Efficiency: The obfuscated program $i\mathcal{O}(C)$ must be at most a polynomial factor larger than the original program $C$, i.e., $|i\mathcal{O}(C)| \le ploy(|C|)$

It cannot grow exponentially. If the size increase is exponential, the obfuscation becomes impractical. For example, if a program’s input is ${0,1}^n$ and output is ${0,1}^m$, one could construct an exponential-size lookup table ${0,1}^{(n+m)}$ to directly map inputs to outputs. Although this satisfies both functionality preservation and indistinguishability, it is not practically feasible. know if you need sections 3 and 4 translated as well.

4. Scheme Instance

A typical indistinguishability obfuscation (iO) scheme consists of the following six steps:

Algorithm Representation: Any algorithm is expressed as a logic circuit.
Data Abstraction as Matrices: Data is abstracted into Matrix Branching Program $\mathbf{M}_1,\mathbf{M}_2$. Matrix multiplication is equivalent to logic circuit operations (similar to the R1CS in Groth16 corresponds to matrix operations and is also equivalent to polynomial computations).
Matrix Randomization: To defend against three types of attacks - matrix permutation attacks, partial product attacks, and out-of-order input attacks - the following three randomization techniques are applied:
- Multiplying with random matrices $\mathbf{R}$ (matrix $\mathbf{M}_1,\mathbf{M}_2$ are randomized as $\mathbf{M}_1\mathbf{R},\mathbf{M}_2\mathbf{R}^{-1}$),
- Expanding matrix dimensions by adding redundant random terms,
- Inserting auxiliary random matrices.
Encryption: The randomized data is then encoded/encrypted, typically via discrete logarithms $\mathbf{g}^{\mathbf{M}_1\mathbf{R}},\mathbf{g}^{\mathbf{M}_2\mathbf{R}^{-1}}$. The ciphertext serves as the input to the black box.
Black-Box Computation: Homomorphic multiplication is realized through multilinear/bilinear maps $e(g^a,g^b)=e(g,g)^{ab}$; Homomorphic addition is achieved through group multiplication $g^a*g^b=g^{a+b}$. These operations correspond to plaintext multiplication $ab$ and addition $a+b$.

During computation: Random matrices $\mathbf{R}$ cancel out; Bookend vectors $\mathbf{\vec {s}},\mathbf {\vec {t}}$ reduce matrix dimensions; Auxiliary random matrices are negated. The black box outputs ciphertext. Alternative: Fully homomorphic encryption (FHE) may be used for similar privacy-preserving computation.
Zero Testing: Each ciphertext is checked to see whether it is equal to the identity element $g^{s_i}\mathop = \limits^?g$. If equal, the $s_i=0$; otherwise, $s_i=1$. The final computation result is retrieved. Note: Intermediate ciphertexts cannot be tested due to the presence of randomization; only the final result can be tested.

Complexity Analysis: Step 1 (logic circuit representation of arbitrary algorithms) requires a large number of logic gates and has high complexity. Step 3’s randomization techniques lead to severe data expansion. In Step 5, adversaries are allowed access to the black box’s inputs and outputs but not any internal information. This step uses bilinear pairings or FHE, which are computationally intensive.

5. Applications

5.1 Digital Signatures

Key Generation: Alice embeds a symmetric key key and symmetric encryption algorithm $\mathbf{SEnc}$ into an iO instance, i.e., $i\mathcal{O}(\mathbf{SEnc}, \text{key})$, and publishes it as her public key. The actual key key is not leaked.
Signing: Alice encrypts a message $m$ using $\mathbf{SEnc}$ with key key, resulting in ciphertext $c$, which serves as the signature.
Verification: Any verifier uses $i\mathcal{O}(\mathbf{SEnc}, \text{key})$ to encrypt $m$ and checks if the resulting ciphertext matches the signature $c$.

5.2 Public-Key Encryption

Key Generation: Alice embeds $\mathbf{SEnc}$ and key key into an iO instance, i.e., $i\mathcal{O}(\mathbf{SEnc}, \text{key})$, and publishes it as her public key.
Encryption: Any sender uses $i\mathcal{O}(\mathbf{SEnc}, \text{key})$ to encrypt message $m$, generating ciphertext $c$ and sends it to Alice.
Decryption: Alice uses $\mathbf{SEnc}$ with key to decrypt $c$ and recover $m$.

5.3 Diffie–Hellman Key Exchange

Original Diffie–Hellman Key Exchange Protocol:

Both parties exchange public keys $X = x \cdot G, Y = y \cdot G$, then both compute $x \cdot Y = xy \cdot G$ and $y \cdot X = xy \cdot G$. Both arrive at the same shared key.

New Diffie–Hellman Key Exchange Protocol with iO:

Alice embeds $\mathbf{SEnc}$ and key into $i\mathcal{O}(\mathbf{SEnc}, \text{key})$ and broadcasts it to Bob.
Bob uses $i\mathcal{O}(\mathbf{SEnc}, \text{key})$ to encrypt message $m_1$ and sends the ciphertext to Alice.
Alice decrypts it using $\mathbf{SEnc}$ with key to recover $m_1$.
(Roles reversed) Alice encrypts message $m_2$ similarly and sends it to Bob, who decrypts it.
Both compute the session key as $\mathbf{Hash}(m_1, m_2)$.

Security Analysis: The original digital signature, public-key encryption, and DH key exchange rely on the hardness of the discrete logarithm problem, which is vulnerable to quantum attacks. The new methods assume the security of $\mathbf{SEnc}$ and $i\mathcal{O}$: (i) $\mathbf{SEnc}$ is invoked as a black box and can be upgraded to post-quantum-secure symmetric encryption. (ii) $i\mathcal{O}$ can be based on fully homomorphic encryption, also potentially post-quantum secure. Therefore, these protocols are post-quantum secure.

5.4 Blockchain/Bitcoin Scalability

Initialization: Combine $zk.verifier$, the verification key $VK$, the Schnorr signature algorithm $schnorr.sig$, and private key $sk$ into a single algorithm, and obfuscate it: $i\mathcal{O}(zk.verifier,VK, schnorr.sig,sk)$.
L2 Execution and Proof Generation: After Layer 2 execution, the Prover generates a zk-proof for the L2 state.
iO Execution: The Operator invokes $i\mathcal{O}(zk.verifier,VK, schnorr.sig,sk)$ with the zk-proof as input. If the proof is invalid, output is false. If valid, output is a Schnorr signature.
On-chain Transaction: Layer 1 (L1) accepts the Schnorr signature and processes the transaction.
- Analysis: Only correct L2 execution can produce a valid zk-proof, which then results in a valid signature, allowing the L1 transaction to succeed.
- Advantage: Not only is zk-proof generation moved off-chain (to L2), but even verification is done off-chain via iO. Layer 1 only handles transactions, enhancing scalability.