Improved garbled circuit building blocks and applications to auctions and computing minima. (English) Zbl 1287.94078

Garay, Juan A. (ed.) et al., Cryptology and network security. 8th international conference, CANS 2009, Kanazawa, Japan, December 12–14, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10432-9/pbk). Lecture Notes in Computer Science 5888, 1-20 (2009).
Summary: 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.
For the entire collection see [Zbl 1176.94003].


94A60 Cryptography
68P25 Data encryption (aspects in computer science)
Full Text: DOI Link