We describe efficient GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits for subtraction and comparison 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 our efficient building blocks. The techniques rely on recently proposed ``free XOR'' GC technique.
Further, we present concrete and detailed improved GC protocols 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 efficient basic blocks and several problem-specific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.
Category / Keywords: cryptographic protocols / Secure Computation, Garbled Circuit, Millionaires Problem, Auctions, Minimum Distance Publication Info: Full version of the CANS 2009 paper. Date: received 24 Aug 2009, last revised 28 Jul 2015 Contact author: thomas schneider at trust rub de Available format(s): PDF | BibTeX Citation Note: Fixed errors in subtraction and comparison circuit. Version: 20150728:111400 (All versions of this report) Short URL: ia.cr/2009/411 Discussion forum: Show discussion | Start new discussion