We propose a new protocol for two-party computation, secure against malicious adversaries, that is significantly faster than prior work in the single-execution (i.e., non-amortized) setting. In particular, our protocol requires only O(ρ) public key operations and ρ garbled circuits, where ρ is the statistical security parameter, whereas previous work with the same number of garbled circuits required either O(ρn)

public-key operations (where n is the input/output length) or another execution of a separate malicious two-party protocol.

We implement our protocol to evaluate its performance. Our prototype is able to securely compute AES in only 65ms

over a local-area network using a single thread without any pre-computation, only 3× slower than a semi-honest execution of the same functionality, and 22× faster than the best prior work in the single-execution setting. On a local-area network, our protocol requires around 20μs to process each input/output bit and around 4μs to process each AND gate, along with a fixed cost of around 23ms to compute the base oblivious transfers.