Secure function evaluation for a covert client and a semi-honest server using string selection oblivious transfer

摘要

Methods and apparatus are provided for secure function evaluation for a covert client and a semi-honest server using string selection oblivious transfer. An information-theoretic version of a garbled circuit C is sliced into a sequence of shallow circuits C1, . . . Cn, that are evaluated. Consider any wire wj of C that is an output wire of Ci, and is an input wire of Ci+1. When a slice Ci is evaluated, Ci's 1-bit wire key for wj is computed by the evaluator, and then used, via string selection oblivious transfer (SOT), to obtain the wire key for the corresponding input wire of Ci+1. This process repeats until C's output wire keys are computed by the evaluator. The 1-bit wire keys of the output wires of the slice are randomly assigned to wire values.

主权项

1. A method for secure function evaluation between a client and a server, comprising:
obtaining a circuit, C, representing a function, ƒ; preparing slices of said circuit, C, into a sequence of sub-circuits C1, . . . Cl, wherein each of said sub-circuits C1, . . . Cl comprises a fan-out-one circuit; executing an oblivious transfer of keys for said sub-circuits C1, . . . Cl, to said client for evaluation, wherein input keys of one or more of said sub-circuits C1, . . . Cl, are based on output keys of a prior one of said sub-circuits C1, . . . Cl, wherein a secret associated with said oblivious transfer is only sent to said client if one of a plurality of allowed selection strings is provided by said client to said server, wherein said allowed selection strings comprise a plurality of bits; and sending one or more output translation tables to said client.