An embodiment of the present invention provides a method that minimizes the number of entries required in a garbled circuit associated with secure function evaluation of a given circuit. Exclusive OR (XOR) gates are evaluated in accordance with an embodiment of the present invention without the need of associated entries in the garbled table to yield minimal computational and communication effort. This improves the performance of SFE evaluation. Another embodiment of the present invention provides a method that replaces regular gates with more efficient constructions containing XOR gates in an implementation of a Universal Circuit, and circuits for integer addition and multiplication, thereby maximizing the performance improvement provided by the above.