The Garbled Circuit (GC) is now over thirty years old, and many optimization methodologies have been proposed, including point-and-permute, row-reduction, free-XOR, fixed-key blockcipher, half-and.

But, after Googling papers and forums, I can't find any concrete algorithmic descriptions which includes all of these optimizations. Does anyone know the exact descriptions of optimized GCs?

I ask because I need to implement the algorithm for personal use.


1 Answer 1


Not all optimizations of garbled circuits are compatible with each other. Are you interested in implementing all of the different combinations? If not, the Half Gates paper already gives a formal description of the scheme, which includes point-permute, fixed-key block cipher, free-XOR. This should represent the state-of-the-art combination of GC optimizations. There is a good implementation of half-gates in the Ivory project.

  • $\begingroup$ Thanks for your response. After looking at the paper talking about half-and, it is clear that it deploys almost all optimizations that can be integrated. Indeed, the final scheme of Half-And is really hard to understand for me. Do you have any good explanation on the constructions of its T_Gc and W_Gc as well as T_Ec and W_Ec? $\endgroup$
    – alexander
    Commented Aug 21, 2018 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.