Leakage resilient garbled circuit generation using reduced memory hardware token
View Patent ↗A garbled circuit is generated for a client in a leakage-resilient manner with a reduced memory requirement. The garbled circuit is used for secure function evaluation between the client and a server. The garbled circuit is generated with a reduced storage requirement by obtaining a token from the server; querying the token gate-by-gate, wherein for each gate of the garbled circuit, the token generates new wire garblings and stores them with the client using a Stream Cipher and interacts with the leakage-protected area to generate a garbled table for the gate; and receiving the garbled circuit from the token. The token comprises a leakage-protected area. The Stream Cipher is leakage-resilient and can be a symmetric-key cryptographic primitive that has a secret key as an input and generates an unbounded stream of pseudorandom bits as an output. The number of evaluations of the Stream Cipher is kept to a substantial minimum. For example, the Stream Cipher can execute with a same key only twice, such as only once for an encryption and only once for a decryption.
1. A method, comprising:
querying, by a client, a hardware token gate-by-gate, said hardware token comprising a leakage-protected area, wherein for each gate of a garbled circuit, the hardware token generates new wire garblings and stores said new wire garblings in an encrypted manner with the client using a Stream Cipher and interacts with the leakage-protected area to generate a garbled table for the gate, wherein the garbled circuit is generated based on a random correspondence between wire values and the corresponding garblings that is unknown to the hardware token, wherein the hardware token is obtained from a server; and
receiving, by the client, the garbled circuit from the hardware token.
2. The method of claim 1 , wherein said Stream Cipher is a symmetric-key cryptographic primitive that has a secret key as an input and generates an unbounded stream of pseudorandom bits as an output.
3. The method of claim 1 , further comprising the step of performing a number of evaluations of said Stream Cipher, wherein said number satisfies a predefined criteria.
4. The method of claim 3 , wherein said Stream Cipher executes with a same key only once for an encryption and only once for a decryption.
5. The method of claim 1 , further comprising the steps of:
interacting with said server to obtain garbled inputs;
evaluating the garbled circuit on the garbled inputs to obtain a garbled output; and
obtaining a final output by matching the garbled output with an output table in the garbled circuit.
6. The method of claim 1 , wherein the leakage-protected area comprises a circuit embedded inside the hardware token.
7. 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.
8. The method of claim 1 , wherein said Stream Cipher is leakage-resilient.
9. The method of claim 1 , wherein said Stream Cipher executes with a same key only twice.
10. An apparatus for generating a garbled circuit in a leakage-resilient manner, used in secure function evaluation between the client and a server, comprising:
a memory; and
at least one hardware device, coupled to the memory, configured to perform the following steps:
querying, by a client, a hardware token gate-by-gate, said hardware token comprising a leakage-protected area, wherein for each gate of a garbled circuit, the hardware token generates new wire garblings and stores said new wire garblings in an encrypted manner with the client using a Stream Cipher and interacts with the leakage-protected area to generate a garbled table for the gate, wherein the garbled circuit is generated based on a random correspondence between wire values and the corresponding garblings that is unknown to the hardware token, wherein the hardware token is obtained from said server; and
receiving, by the client, the garbled circuit from the token.
11. The apparatus of claim 10 , wherein said Stream Cipher is a symmetric-key cryptographic primitive that has a secret key as an input and generates an unbounded stream of pseudorandom bits as an output.
12. The apparatus of claim 10 , wherein said at least one hardware device is further configured to perform a number of evaluations of said Stream Cipher, wherein said number satisfies a predefined criteria.
13. The apparatus of claim 10 , wherein said Stream Cipher executes with a same key only twice.
14. The apparatus of claim 13 , wherein said Stream Cipher executes with a same key only once for an encryption and only once for a decryption.
15. The apparatus of claim 10 , wherein said at least one hardware device is further configured to:
interact with said server to obtain garbled inputs;
evaluate the garbled circuit on the garbled inputs to obtain a garbled output; and
obtain a final output by matching the garbled output with an output table in the garbled circuit.
16. The apparatus of claim 10 , wherein the leakage-protected area comprises a circuit embedded inside the hardware token.
17. The apparatus of claim 10 , wherein said Stream Cipher is leakage-resilient.
18. 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 from a client, and in response to said query, generate Previously Presented wire garblings, store said Previously Presented wire garblings in an encrypted manner with the client using a Stream Cipher and interact with the leakage-protected subset of the integrated circuit to generate a garbled table for a gate of a garbled circuit, wherein the garbled circuit is generated based on a random correspondence between wire values and the corresponding garblings that is unknown to the hardware token.
19. The apparatus of claim 18 , wherein the leakage-protected subset comprises a circuit embedded inside the integrated circuit.
20. The apparatus of claim 18 , wherein the garbled circuit comprises garbled tables for all gates in a Boolean circuit, and decryption tables for output wires.
21. The apparatus of claim 20 , wherein the decryption tables comprise an association of output wire keys with their values.