Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

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

Vladimir Kolesnikov, Ahmad‐Reza Sadeghi, Thomas H. Schneider

Published Jan 1, 2009• 264 citations
Publisher
DOI
10.1007/978-3-642-10433-6_1

Related papers

Improved Garbled Circuit: Free XOR Gates and Applications

Vladimir Kolesnikov, Thomas H. Schneider

Lecture notes in computer science•Aug 12, 2008•769 citations

Improvements for Gate-Hiding Garbled Circuits

Mike Rosulek

Lecture notes in computer science•Jan 1, 2017•11 citations

Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits

Vladimir Kolesnikov, Ranjit Kumaresan

Lecture notes in computer science•Jan 1, 2012•14 citations

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

Vladimir Kolesnikov, Ahmad‐Reza Sadeghi, Thomas H. 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 problemspecific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.

•Jan 1, 2009•0 citations

Fast Garbling of Circuits Under Standard Assumptions

Shay Gueron, Yehuda Lindell, Ariel Nof +1 more

Journal of Cryptology•Dec 11, 2017•21 citations

How to Combine Homomorphic Encryption and Garbled Circuits - Improved Circuits and Computing the Minimum Distance Efficiently

Vladimir Kolesnikov, Ahmad‐Reza Sadeghi, Thomas H. Schneider

Abstract. We show how two existing paradigms for two-party secure function evaluation (SFE) in the semi-honest model can be combined securely and efficiently – those based on additively homomorphic encryption (HE) with those based on garbled circuits (GC) and vice versa. Additionally, 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 (including the protocols for combining HE and GC). Based on these results, we present efficient constant-round protocols for secure integer comparison, and the related problems of minimum selection and minimum distance, which are crucial building blocks of many cryptographic schemes such as privacy preserving biometric authentication (e.g., face recognition, fingerprint matching, etc).

•Sep 1, 2009•12 citations
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 problemspecific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.
Abstract. We show how two existing paradigms for two-party secure function evaluation (SFE) in the semi-honest model can be combined securely and efficiently – those based on additively homomorphic encryption (HE) with those based on garbled circuits (GC) and vice versa. Additionally, 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 (including the protocols for combining HE and GC). Based on these results, we present efficient constant-round protocols for secure integer comparison, and the related problems of minimum selection and minimum distance, which are crucial building blocks of many cryptographic schemes such as privacy preserving biometric authentication (e.g., face recognition, fingerprint matching, etc).