You are looking at a specific version 20150728:111400 of this paper. See the latest version.

Paper 2009/411

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

Vladimir Kolesnikov and Ahmad-Reza Sadeghi and Thomas Schneider

Abstract

We consider generic Garbled Circuit (GC)-based techniques for Secure Function Evaluation (SFE) in the semi-honest model. 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.

Note: Fixed errors in subtraction and comparison circuit.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Full version of the CANS 2009 paper.
Keywords
Secure ComputationGarbled CircuitMillionaires ProblemAuctionsMinimum Distance
Contact author(s)
thomas schneider @ trust rub de
History
2017-12-08: last of 7 revisions
2009-09-01: received
See all versions
Short URL
https://ia.cr/2009/411
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.