Patent ID: 8443205

Claim:
A computer implemented method for executing secure function evaluation defined by a garbled circuit with gates where inputs and outputs of the gates are related by entries in a garbled table, the method comprising the steps of: using a plurality of exclusive OR (XOR) gates each having first and second inputs, and an output in a circuit; generating a fixed global key R based on security parameter N; generating first garbled values w 0 assigned to the first inputs where the values w 0 are computed based on an actual value combined with a random number so that the values w 0 are random; generating non-random second garbled values w 1 in the garbled table assigned to the second inputs where the values w 1 are derived based on an actual value exclusive OR'ed with key R; generating, for other gates in the circuit that are not XOR gates, garbled values and corresponding garbled table entries, where entries in the garbled table are not required for inputs and outputs of the XOR; transmitting the garbled tables and garblings of active circuit input wires from one party to another party with whom the one party desires to exchange information via results produced by a universal circuit where the one party has private inputs P 1 and the another party has private inputs P 2 , where the private inputs are not known to the opposite party; calculating at least one resultant output from the circuit based on the inputs P 1 and P 2 , and the secure function evaluation as defined by the gates of the circuit.