Securely executing on a public computer code represented by non-linear gates which operates on encrypted data

A non-transitory computer-readable medium carrying one or more sequences of instructions, wherein execution of the one or more sequences of instructions by a first set of one or more processors causes the first set of one or more processors to:

• a. configure a permutation encryption module for n-bit words comprising only a first stage that can be decomposed into k-bit gates including at least one non-linear 3-bit gate, wherein k is not less than 3;
• b. receive first data that indicates a first function to be implemented as a first obfuscated module operating on and producing only encrypted data formed according to the permutation encryption module;
• c. configure the first obfuscated module by
• determining a first plurality of 3-bit gates that implement the first function,
• straddling each gate in the first plurality with the first stage in reverse order and the first stage to form an expanded set of gates,
• replacing the expanded set of gates using a finite set of substitution rules to form an ordered set of daughter gates,
• concatenating the ordered set of daughter gates produced for each gate in the first plurality,
• for each output bit of each ordered set of daughter gates, forming a binary decision diagram (BDD) that indicates a value based on 3 or more input bits of the non-linear expanded set of gates for each daughter gate,
• generating a module chip by combining all BDDs, and
• configuring the first obfuscated module by including the module chip;
• and
• d. send to an unsecured device the first obfuscated module for execution by the unsecured device

A system comprising:

• a first set of at least one processor;
• and
• at least one memory including one or more sequences of instructions,
• the at least one memory and the one or more sequences of instructions configured to, with the at least one processor, cause an apparatus to
• a. configure a permutation encryption module for n-bit words comprising only a first stage that can be decomposed into k-bit gates including at least one non-linear k-bit gate wherein k is not less than 3;
• b. receive first data that indicates a first function to be implemented as a first obfuscated module operating on and producing only encrypted data formed according to the permutation encryption module;
• c. configure the first obfuscated module by
• determining a first plurality of 3-bit gates that implement the first function,
• straddling each gate in the first plurality with the first stage in reverse order and the first stage to form an expanded set of gates,
• replacing the expanded set of gates using a finite set of substitution rules to form an ordered set of daughter gates,
• concatenating the ordered set of daughter gates produced for each gate in the first plurality,
• for each output bit of each ordered set of daughter gates, forming a binary decision diagram (BDD) that indicates a value based on 3 or more input bits of each ordered set of daughter gates,
• generating a module chip by combining all BDDs, and
• configuring the first obfuscated module by including the module chip;
• and
• d. send to an unsecured device the first obfuscated module for execution by the unsecured device.

A method operating on a first processor comprising:

• a. configuring a permutation encryption module for n-bit words comprising only a first stage that can be decomposed into only linear 3-bit gates and a second stage that can be decomposed into k-bit gates including at least one non-linear k-bit gate, wherein k is not less than 3;
• b. receiving first data that indicates a first function to be implemented as a first obfuscated module operating on and producing only encrypted data formed according to the permutation encryption module;
• c. configuring the first obfuscated module by
• determining a first plurality of 3-bit gates that implement the first function,
• straddling each gate in the first plurality with the first stage in reverse order and the first stage to form a linear expanded set of gates,
• replacing the linear expanded set of gates using a finite set of substitution rules to form an ordered set of daughter gates,
• concatenating the ordered set of daughter gates produced for each gate in the first plurality,
• straddling each gate in the concatenated ordered set of daughter gates with the second stage in reverse order and the second stage to form a non-linear expanded set of gates for each daughter gate,
• for each output bit of the non-linear expanded set of gates for each daughter gate, forming a binary decision diagram (BDD) or equivalent that indicates a value based on 3 or more input bits of the non-linear expanded set of gates for each daughter gate,
• generating a module chip by combining all BDDs or equivalents, and
• configuring the first obfuscated module by including the module chip;
• and
• d. sending to an unsecured device the first obfuscated module for execution by the unsecured device.

A non-transitory computer-readable medium carrying one or more sequences of instructions, wherein execution of the one or more sequences of instructions by a first set of one or more processors causes the first set of one or more processors to:

• a. configure a permutation encryption module for n-bit words comprising only a first stage that can be decomposed into only linear 3-bit gates and a second stage that can be decomposed into k-bit gates including at least one non-linear 3-bit gate, wherein k is not less than 3;
• b. receive first data that indicates a first function to be implemented as a first obfuscated module operating on and producing only encrypted data formed according to the permutation encryption module;
• c. configure the first obfuscated module by
• determining a first plurality of 3-bit gates that implement the first function,
• straddling each gate in the first plurality with the first stage in reverse order and the first stage to form a linear expanded set of gates,
• replacing the linear expanded set of gates using a finite set of substitution rules to form an ordered set of daughter gates,
• concatenating the ordered set of daughter gates produced for each gate in the first plurality,
• straddling each gate in the concatenated ordered set of daughter gates with the second stage in reverse order and the second stage to form a non-linear expanded set of gates for each daughter gate,
• for each output bit of the non-linear expanded set of gates for each daughter gate, forming a binary decision diagram (BDD) or equivalent that indicates a value based on 3 or more input bits of the non-linear expanded set of gates for each daughter gate,
• generating a module chip by combining all BDDs or equivalents, and
• configuring the first obfuscated module by including the module chip;
• and
• d. send to an unsecured device the first obfuscated module for execution by the unsecured device.

A system comprising:

• a first set of at least one processor;
• and
• at least one memory including one or more sequences of instructions,
• the at least one memory and the one or more sequences of instructions configured to, with the at least one processor, cause an apparatus to
• a. configure a permutation encryption module for n-bit words comprising only a first stage that can be decomposed into only linear 3-bit gates and a second stage that can be decomposed into k-bit gates including at least one non-linear k-bit gate wherein k is not less than 3;
• b. receive first data that indicates a first function to be implemented as a first obfuscated module operating on and producing only encrypted data formed according to the permutation encryption module;
• c. configure the first obfuscated module by
• determining a first plurality of 3-bit gates that implement the first function,
• straddling each gate in the first plurality with the first stage in reverse order and the first stage to form a linear expanded set of gates,
• replacing the linear expanded set of gates using a finite set of substitution rules to form an ordered set of daughter gates,
• concatenating the ordered set of daughter gates produced for each gate in the first plurality,
• straddling each gate in the concatenated ordered set of daughter gates with the second stage in reverse order and the second stage to form a non-linear expanded set of gates for each daughter gate,
• for each output bit of non-linear expanded set of gates for each daughter gate, forming a binary decision diagram (BDD) or equivalent that indicates a value based on 3 or more input bits of the non-linear expanded set of gates for each daughter gate,
• generating a module chip by combining all BDDs or equivalents, and
• configuring the first obfuscated module by including the module chip;
• and
• d. send to an unsecured device the first obfuscated module for execution by the unsecured device.