  We propose a new approach to practical two-party computation secure against
an active adversary. All prior practical protocols were based on Yao's garbled
circuits. We use an OT-based approach and get efficiency via OT extension in
the random oracle model. To get a practical protocol we introduce a number of
novel techniques for relating the outputs and inputs of OTs in a larger
construction.
  We also report on an implementation of this approach, that shows that our
protocol is more efficient than any previous one: For big enough circuits, we
can evaluate more than 20000 Boolean gates per second. As an example,
evaluating one oblivious AES encryption (~34000 gates) takes 64 seconds, but
when repeating the task 27 times it only takes less than 3 seconds per
instance.
