## Goal of the bounty

To win the bounty you must find a reversible circuit with < 1014 gates which is funtionally equivalent to the obfuscted circuit we've provided.

We've provided an obfuscated circuit of a randomly sampled reversible circuit which is also an strong pseudo random permutation (SPRP). SPRP implies that the output permutation on any input bitstring is indistinguishable from a truly random permutation. The original reversible circuit has n=64 wires and 1014 gates. The task is to find the original "reversible circuit" only given the obfuscated circuit. The obfuscated circuit has n=64 wires and 12111 gates. If you're able to find another circuit with <= 1014 gates that is not the orignal circuit you still win the bounty because doing so breaks the assumption that original circuit is an SPRP.

*Note: Generating input to output map of the permutation that obfuscted circuit computes is not "finding the original circuit". Hence, is not a valid submission.*

### Submission

To submit send the [circuit JSON file]() of the circuit to [e-mail]. To pay out the bounty it suffices to verify that your circuit is funtionally equivalent to our original/obfuscated circuit.

#### Circuit JSON file

Following a example circuit JSON file for reversible circuit n=4 and 1 gate:

{
    "wire_count": 4,
    "gate_count": 1,
    "gates": [
        [
            0, 
            3, 
            2, 
            1
        ]
    ]
}

"wire_count" and "gate_count" are self explanatory. "gates" is array of base gates. Each gate is represented via an array of 4 elements. The first element is control wire 0, second element is control wire 1, third is the target wire, and the fourth element is the control function. There are 16 different control functions and their index can be found here.

If circuit binary file already exists then its circuit JSON file can be generated using the following command:

cargo run --release -- 3 [circuit_bin_path] [circuit_json_path]

where
- circuit_bin_path: path to circuit's binary
- circuit_json_path: location to store input circuit's JSON file.

### Where to start

If you're new to program obfuscation via local mixing and reversible circuits [this hackmd doc](https://hackmd.io/Vg3LlttcSH-oXZDFSHUDlw) is a good place to start. Here after for the rest of the section we'll assume knowledge of program obfuscation via local mixing and reversible circuits.

#### How does bounty relate to breaking "Program obfuscation via local mixing"?

We're interested in better understanding the security of local-mixing approach to program obfuscation. Random identity generator (RIG) obfuscated circuits is the core construction required to obfuscate any arbitrary reversible circuit, hence any arbitrary boolean function. RIG requires an obfuscator function, O_1, that satifies property 1 of RIO and the bounty tests the security of this function.

Algorithm to construct RIG samples a random SPRP reversible circuit C and outputs $O_1(C) | O_1^{\dagger}(C)$ where \dagger is inverse. For security, O_1 must be output reversible circuits that are indistinguishable from random reversible circuits that compute same permutation as the orignal circuit C.

We implemented local mixing approach to O_1, sampled random SPRP reversible circuit C based on 3-stage block cipher decribed in [Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers
](https://arxiv.org/abs/2011.06546) (check [this](https://hackmd.io/Vg3LlttcSH-oXZDFSHUDlw#Quantum-statistical-mechanics-of-encryption-reaching-the-speed-limit-of-classical-block-ciphers-httpsarxivorgabs201106546) section of the [hackmd](https://hackmd.io/Vg3LlttcSH-oXZDFSHUDlw)) and ran O_1 with strategy 1 for 230K iterations. Successful recover of C or another funtionally equivalent circuit with equivalent no. of gates in C will imply local mixing approach to O_1 is not secure.

#### How was obfuscated circuit generated?

We implemented obfuscator function based on local mixing approach that satisfies property 1 of RIO (ie function O_1) available [here](https://github.com/gausslabs/obfustopia).

We obfuscated a random reversible SPRP circuit C with strategy 1 using the following command:

cargo run --release -- 1 logs.log out.bin original.bin 1

where `out.bin` is obfuscation job's binary and `orignal.bin` is original circuit C's binary.

Before running the command we modified default parameters for strategy 1 (`fn default_strategy1()`) to use n=64 and total_steps=250,000.

The command sampled a random SPRP reversible circuit with n=64 (ie no. of wires) by calling `Circuit::sample_multi_stage_cipher(n=64, rng)`. The sampled circuit is the original circuit C. Multi-stage cipher is based on [Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers
](https://arxiv.org/abs/2011.06546) (check [this](https://hackmd.io/Vg3LlttcSH-oXZDFSHUDlw#Quantum-statistical-mechanics-of-encryption-reaching-the-speed-limit-of-classical-block-ciphers-httpsarxivorgabs201106546) section of the [hackmd](https://hackmd.io/Vg3LlttcSH-oXZDFSHUDlw)) and is conjectured to be an SPRP.

After sampling C the command ran local mixing step with strategy 1 for total_steps=250,000 times. Once obfuscation job finished, we converted both the original circuit and the obfuscated circuit to circuit JSON file with following commands.

Convert original circuit C's binary to circuit JSON

cargo run --release -- 3 original.bin orignal.json

Isolate obfuscated circuit in obfuscation job's binary and convert to circuit JSON

cargo run --release -- 4 out.bin obfuscated.json

We've provided `obfuscated.json` file here.

<!-- #### Brute force attack

A naive attempt to find the orignal circuit is to find a reversible circuit that is funtionally equivalent to the original circuit with 1000 gates with brute force. However, we suspect that doing so is not practical.

Here's our reasoning: The original circuit has 1000 gates with n=64. For each gate there are 16(n)(n-1)(n-2) possibilities (recall wires that a gate touces need to be mutually exclusive). Hence, for a circuit with n=64 and 1000 gates, there are $(16 \times 64 \times 63 \times 62)^{1000}$ possible circuits.

#### A much smarter attack

Recall that we obfuscate with strategy 1 and run local mixing steps 250K times. In each iteration, we randomly sample $\ell^{out}$ in range $[2, 4]$ and $\ell^{in}$ is set to 4.

Let's take a single local mixing iteration with $\ell^{out} = 2$. The step finds a random convex subgraph, C^out, in the skeleton graph with 2 gates and replaces it with another funtionally equivalent circuit C^in with $\ell^{in} = 4$ gates. Hence, intuitivelly it should easy to find $C^{out}$ given $C^{in}$. This forms the basis of the smarter attack.

To attack find an open thread to start pulling from. In other words, find a subgraph $C^{in'}$ with $\ell^{in}=4$ gates for which it is easy to find a functionally equivalent circuit $C^{out'}$ with $\ell^{out}$ gates (ie circuit with $\ell^{in}$ has computational complexity $\leq \ell^{out}$). Then replace $C^{in'}$ with $C^{out'}$. Repeat the procedure until the size of circuit is reduced to the original circuit.
-->
<!--
### FAQ

**How to get started?**

Download the obfuscated circuit via this url.

**How would you know whether the the circuit you've found is same as the original circuit?**

THe obfuscated circuit takes 64-bit inputs. So brute forcing through all of them will be take days if not months. The best approach we've is to probabilitically check whether your circuit computes the same function as obfuscated circuit.

You can also independently verify the orignal circuit by its hash - TODO

**What if the orignal circuit I've recovered has functionally equivalent but not same to the orignal circuit?**

The bounty still applies. If you've come up with a different circuit that is functionally equivalent to orignal circuit but not exactly same then you've proven that orignal circuit is not a strong pseudo-random permutation. THis is because with only access to oracle, the so-called obfuscated circuit, you've recovered a function that computes the SPRP.

###

### Where to start atacking?

We've provided a obfuscated circuit of a random reversible circuit with the following properties.

Blah blah

-->