Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima

In this work, we consider generic Garbled Circuit (GC)-based techniques for Secure Function Evaluation (SFE) in the semi- honest model. We propose new GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using the above building blocks. Our techniques rely on recently proposed "free XOR" GC technique. As an additional contribution, we present concrete and detailed improved GC constructions for the problem of secure integer comparison, and related problems of auctions, minimum selection, and minimal distance. Performance improvement comes both from building on our new basic blocks and several problem-specic GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.