Computation of garbled tables in garbled circuit
View Patent ↗An efficient encryption system for improving the computation speed of a garbled circuit is set forth. The garbled circuit includes a number of garbled Boolean gates having first and second garbled Boolean gate input wires. The system includes a first key ki on a first garbled gate input wire. A second key kj is also provided on a second garbled gate input wire. A programmable function is provided for combining the first key ki and the second key kj to obtain an encrypted output key. A method for expediting encryption and decryption of a garbled circuit having a number of encryptions for a garbled table of a garbled gate is also set forth. The method includes the steps of: forming the garbled table with a number of secret keys by applying a function to the secret keys to produce less than twice the number of secret keys as the number of encryptions for the garbled table, and evaluating the garbled table to decrypt an output key of the garbled table.
1. An apparatus, comprising:
a first pair of input keys on a first garbled gate input wire;
a second pair of input keys on a second garbled gate input wire; and
a computer readable non-transitory medium having instructions located thereon which when executed by a processor:
receive a Pseudo-Random Function Generator (PRFG) circuit from a secure token configured to generate the PRFG circuit and to transmit the PRFG circuit from a first network device to a second network device, the PRFG circuit including a number of gate tables and wire encryptions, each gate for the number of garbled gates including a first key ki and a second key kj; and
implement the PRFG circuit, the PRFG circuit being configured to generate a random permutation of four garbled table entries, each garbled table entry being formed by a single encryption operation applied to a corresponding output key, each single encryption operation including encrypting each corresponding output key with a key formed from an exclusive OR function (XOR) of one of the four possible combinations of one key of the first pair of input keys and one key of the second pair of input keys,
wherein the encrypted output key for each garbled gate is selected from the domain of the PRFG circuit.
2. The apparatus according to claim 1 , wherein the first and second keys are each 127 bits long, and wherein the programmable function adds the first and second keys.
3. The apparatus according to claim 1 , wherein the PRFG is further defined by Advanced Encryption Standard (AES).
4. The apparatus according to claim 1 , wherein the PRFG is further defined by Secure Hash Algorithm-256 (sha256).
5. An apparatus comprising:
a computer readable non-transitory memory;
a first input wire having a first pair of input keys;
a second input wire having a second pair of input keys; and
a garbled gate forming algorithm stored in the memory, wherein when executed by a processor the garbled gate forming algorithm receives a Pseudo-Random Function Generator (PRFG) circuit from a secure token, and generates from the PRFG circuit a random permutation of four garbled table entries, each garbled table entry being formed by a single encryption operation applied to a corresponding output key, each single encryption operation including encrypting each corresponding output key with a key formed from an exclusive OR function (XOR) of one of the four possible combinations of one key of the first pair of input keys and one key of the second pair of input keys,
wherein the secure token is configured to generate the PRFG circuit and to transmit the PRFG circuit from a first network device to a second network device, the PRFG circuit including a number of gate tables and wire encryptions, each gate for the number of garbled gates including a first key ki and a second key kj configured to generate the random permutation of four garbled table entries, each garbled table entry being formed by a single encryption operation applied to a corresponding output key, each single encryption operation including encrypting each corresponding output key with a key formed from an exclusive OR function (XOR) of one of the four possible combinations of one key of the first pair of input keys and one key of the second pair of input keys,
wherein the encrypted output key for each garbled gate is selected from the domain of the PRFG circuit.
6. The apparatus according to claim 5 , wherein the gate forming algorithm further comprises Advanced Encryption Standard (AES).
7. The apparatus according to claim 5 , wherein the PRFG circuit is transmitted via a secure token.
8. A method comprising the steps of:
providing a gate having first and second input wires, wherein the first wire has a first pair of input keys and wherein the second wire has a second pair of input keys;
generating a gate table using a secure token with a Pseudo-Random Function Generator (PRFG) circuit configured to generate a random permutation of four garbled table entries, each garbled table entry being formed by a single encryption operation applied to a corresponding output key, wherein the gate table includes four encryption operations, each single encryption operation including encrypting each corresponding output key with a key formed from an exclusive OR (XOR) function of one of the four possible combinations of one key of the first pair of input keys and one key of the second pair of input keys;
transmitting the PRFG circuit from a first network device to a second network device by the secure token, the PRFG circuit including a number of gate tables and wire encryptions, each gate for the number of garbled gates including a first key ki and a second key kj; and
selecting the encrypted output key for each garbled gate from the domain of the PRFG circuit.
9. The method according to claim 8 , wherein the step of generating the gate table with a PRFG algorithm is further defined by generating the gate table using Advanced Encryption Standard (AES).
10. The method according to claim 8 , wherein the step of generating the gate table with a PRFG algorithm is further defined by generating the gate table using Secure Hash Algorithm-256 (sha256).
11. An apparatus, comprising:
a network server adapted to receive communications from a first communication device and to send the communications to a second communication device comprising an encryption system for a garbled circuit, the garbled circuit including a number of garbled Boolean gates having first and second garbled Boolean gate input wires, comprising:
a first pair of input keys on a first garbled gate input wire;
a second pair of input keys on a second garbled gate input wire; and
a computer readable non-transitory medium having instructions located thereon which when executed by a processor implement:
a Pseudo-Random Function Generator (PRFG) circuit configured to generate a random permutation of four single encryption operations applied to a corresponding output key, each single encryption operation including encrypting each corresponding output key with a key formed from an exclusive OR function (XOR) of one of the four possible combinations of one key of the first pair of input keys and one key of the second pair of input keys,
wherein the garbled circuit is transmitted by a secure token, the garbled circuit including a number of gate tables and wire encryptions, each gate for the number of garbled gates including a first key ki and a second key kj,
wherein the token generates and transmits the circuit from a first network device to a second network device, and
wherein the encrypted output key for each garbled gate is selected from the domain of the garbled circuit.
12. The network server according to claim 11 , further comprising a second network server adapted to receive the communications for the second communication device and transmit the communications to the second communications device.
13. The network server according to claim 11 , further comprising:
a third key kk on a third garbled gate input wire,
wherein the programmable function configured to combine the first key ki and the second key kj further combines the third key kk with ki and kj to obtain an encrypted output key.
14. The network server according to claim 11 , further comprising:
an nth key kn on an nth garbled gate input wire,
wherein the programmable function configured to combine the first key ki and the second key kj further combines the nth key kn with ki and kj to obtain an encrypted output key.