Methods and apparatus are provided for generating a garbled circuit for a client in a leakage-resilient manner, for use in secure function evaluation between the client and a server. The garbled circuit is generated by obtaining a token from the server, wherein said token comprises a leakage-protected area; querying the token gate-by-gate, wherein for each gate of said garbled circuit, the token interacts with the leakage-protected area to generate a garbled table for the gate; and receiving the garbled circuit from the token. The client can interact with the server to obtain garbled inputs; and then evaluate the garbled circuit on the garbled inputs to obtain a garbled output. A final output can be obtained by matching the garbled output with an output table in the garbled circuit.