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.