Garbled circuit generation in a leakage-resilient manner
View Patent ↗Methods and apparatus are provided for generating a garbled circuit for a client in a leakage-resilient manner, for use in secure function evaluation between the client and a server. The garbled circuit is generated by obtaining a token from the server, wherein said token comprises a leakage-protected area; querying the token gate-by-gate, wherein for each gate of said garbled circuit, the token interacts with the leakage-protected area to generate a garbled table for the gate; and receiving the garbled circuit from the token. The client can interact with the server to obtain garbled inputs; and then evaluate the garbled circuit on the garbled inputs to obtain a garbled output. A final output can be obtained by matching the garbled output with an output table in the garbled circuit.
1. A method, comprising:
generating a garbled circuit for Secure Function Evaluation (SFE) by querying a hardware token gate-by-gate, said hardware token comprising a leakage-protected area, wherein for each gate g of the garbled circuit with input wires and output wires, the hardware token interacts with the leakage-protected area of the token to generate a garbled table for the gate g, and wherein the generating is based on a random correspondence between wire values and their garblings that is unknown to the hardware token; and
receiving the garbled circuit from the hardware token.
2. The method of claim 1 , further comprising the step of obtaining a garbled output from the garbled inputs using the garbled circuit.
3. The method of claim 2 , further comprising the step of obtaining a final output by matching the garbled output with an output table in the garbled circuit.
4. The method of claim 1 , wherein the leakage-protected area comprises a circuit embedded inside the hardware token.
5. The method of claim 1 , wherein the hardware token interacts with the leakage-protected area to generate the garbled table in a leakage-resilient manner for the gate g by generating and storing a triple (k i 0 ,k i 1 ,k i ) for every wire w i connected to the gate g for which the wire garblings have not yet been generated, where k i 0 ,k i 1 ,εK are selected pseudo-randomly from the key space of double encryption (DE), and k i ←Encode(b i ) is an encoding of a pseudo-random bit b i .
6. The method of claim 5 , wherein a correspondence of the wire keys k i 0 ,k i 1 to wire bit values is determined by the bit b i .
7. The method of claim 5 , wherein a wire key k i v corresponds to a wire value b i ⊕v, where v is a plain text value of wire w i and b i is a random bit value of said wire w i .
8. The method of claim 5 , wherein the leakage-protected area encodes output wire keys in an order, and the hardware token constructs the garbled table based on the order without knowledge of a correspondence of the wire keys to corresponding bit values.
9. The method of claim 1 , wherein the garbled circuit comprises garbled tables for all gates in a Boolean circuit, and decryption tables for output wires.
10. The method of claim 9 , wherein the decryption tables comprise an association of output wire keys with their values.
11. The method of claim 2 , further comprising obtaining the garbled inputs from a server.
12. An apparatus comprising:
a memory; and
at least one hardware device, coupled to the memory, operative to:
communicate with a hardware token, wherein said hardware token comprises a leakage-protected area;
query the hardware token gate-by-gate, wherein for each gate g of a garbled circuit with input wires and output wires and used for Secure Function Evaluation (SFE), the hardware token interacts with the leakage-protected area to generate a garbled table for the gate g, wherein the garbled circuit is generated based on a random correspondence between wire values and their garblings that is unknown to the hardware token; and
receive the garbled circuit from the hardware token.
13. The apparatus of claim 12 , wherein said at least one hardware device is further configured to obtain a garbled output from the garbled inputs using the garbled circuit.
14. The apparatus of claim 13 , wherein said at least one hardware device is further configured to obtain a final output by matching the garbled output with an output table in the garbled circuit.
15. The apparatus of claim 13 , wherein said at least one hardware device is further configured to obtain the garbled inputs from a server.
16. The apparatus of claim 12 , wherein the leakage-protected area comprises a circuit embedded inside the hardware token.
17. The apparatus of claim 12 , wherein the garbled circuit comprises garbled tables for all gates in a Boolean circuit, and decryption tables for output wires.
18. The apparatus of claim 17 , wherein the decryption tables comprise an association of output wire keys with their values.
19. An apparatus, comprising:
an integrated circuit; and
a leakage-protected subset of the integrated circuit,
wherein the integrated circuit is configured to receive a query, and in response to said query, to interact with the leakage-protected subset of the integrated circuit to generate a garbled table for a gate g of a garbled circuit with input wires and output wires and used for Secure Function Evaluation (SFE), wherein the garbled circuit is generated based on a random correspondence between wire values and their garblings that is unknown to the apparatus.
20. The apparatus of claim 19 , wherein the leakage-protected subset comprises a circuit embedded inside the integrated circuit.
21. The apparatus of claim 19 , wherein the garbled circuit comprises garbled tables for all gates in a Boolean circuit, and decryption tables for output wires.
22. The apparatus of claim 21 , wherein the decryption tables comprise an association of output wire keys with their values.