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 dada@gmail.com. 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 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
(check this section of the hackmd) 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.

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
(check this section of the hackmd) 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.