[rhyzomatic]

Super fun paper.

It seems like their modification to Aaronson's algorithm would also work for Yao's garbled circuits, i.e.

1. Alice generates a long random bitstring s, and publishes hash(s)

2. Alice crafts a garbled circuit with just one AND gate, where the false output is 0+s, and the true output is 1. Alice sends the circuit and her input to Bob.

3. Bob gets his input from Alice using oblivious transfer. He evaluates the circuit, publishing the result.

4. If the result starts with 0, Bob verifies that hash of the rest of the string matches the hash published by Alice. Alice also checks to make sure the rest of the string matches her original s.