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

Network and Distributed System Security Symposium

Constant Round Maliciously Secure 2PC with Function-independent Preprocessing using LEGO

Jesper Buus Nielsen, Thomas H. Schneider, Roberto Trifiletti

Published Jan 1, 2017• 50 citations
Publisher

Abstract

Author(s): Jesper Buus Nielsen, Thomas Schneider, Roberto Trifiletti Download: Paper (PDF) Date: 27 Feb 2017 Document Type: Reports Additional Documents: Slides Video Associated Event: NDSS Symposium 2017 Abstract: Asymptotically more efficient than on the circuit level. Since then the LEGO approach has been improved upon in several theoretical works, but never implemented. In this paper we describe further … Continued

DOI
10.14722/ndss.2017.23075

Related papers

Constant Round Maliciously Secure 2PC with Function-independent Preprocessing using LEGO.

Jesper Buus Nielsen, Thomas H. Schneider, Roberto Trifiletti

•Jan 1, 2016•1 citation

Pushing the Communication Barrier in Secure Computation using Lookup Tables

Ghada Dessouky, Farinaz Koushanfar, Ahmad‐Reza Sadeghi +3 more

Author(s): Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, Shaza Zeitouni, Michael Zohner Download: Paper (PDF) Date: 27 Feb 2017 Document Type: Reports Additional Documents: Slides Video Associated Event: NDSS Symposium 2017 Abstract: Secure two-party computation (S2PC) allows two parties to compute a function on their joint inputs while leaking only the output of the function. At … Continued

Network and Distributed System Security Symposium•Jan 1, 2017•66 citations

Revisiting LEGOs: Optimizations, Analysis, and their Limit.

Yan Huang, Ruiyu Zhu

Abstract. The Cut-and-choose paradigm gives by far the most popular and efficient secure two-party computation protocols in the standard malicious model, able to offer s bits of security with only s copies of garbled circuits in the one-time execution scenario [33]. Nielsen, Orlandi et al. [48,13] have even proposed the seminal idea of LEGO-style cut-and-choose to further reduce the number of circuit copies to less than s while still keep constant round complexity. However, a substantial gap still exists between the theoretical idea of LEGO cut-and-choose and a practical implementation, e.g., [48] is not compatible with free-XOR and uses expensive asymmetric key operations for soldering, while [13] leaves the important building-block of soldering unspecified. In this work, we introduce XOR-Homomorphic Interactive Hash and propose an efficient implemen-tation of this primitive by combining Reed-Solomon encoding and k-out-of-n oblivious transfers. We show how to apply this primitive to solve the performance-critical wire-soldering problem and propose a new LEGO-style cut-and-choose protocol. Comparing to previous LEGO-style protocols, ours only requires a single (as opposed to “a majority of”) correctly garbled gate in each bucket to guarantee security against malicious adversaries. Plus, through integrating Half-Gates garbling, we double the chance a “bad ” gate being detected in the check stage (compared to MiniLEGO [13]). Our construction

•Jan 1, 2015•2 citations

Engineering secure two-party computation protocols: design, optimization, and applications of efficient secure function evaluation / Thomas Schneider

Thomas H. Schneider

•Jan 1, 2012•0 citations

Black-Box Constant-Round Secure 2PC with Succinct Communication

Michele Ciampi, Ankit Kumar Misra, Rafail Ostrovsky +1 more

Lecture notes in computer science•Jan 1, 2025•5 citations

ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation

Daniel Demmler, Thomas H. Schneider, Michael Zohner

Author(s): Daniel Demmler, Thomas Schneider, Michael Zohner Download: Paper (PDF) Date: 7 Feb 2015 Document Type: Briefing Papers Additional Documents: Slides Associated Event: NDSS Symposium 2015 Abstract: Secure computation enables multiple mutually distrusting parties to jointly evaluate functions on their private inputs without revealing anything but the result. Generic secure computation protocols in the semi-honest … Continued

Network and Distributed System Security Symposium•Jan 1, 2015•858 citations
Author(s): Jesper Buus Nielsen, Thomas Schneider, Roberto Trifiletti Download: Paper (PDF) Date: 27 Feb 2017 Document Type: Reports Additional Documents: Slides Video Associated Event: NDSS Symposium 2017 Abstract: Asymptotically more efficient than on the circuit level. Since then the LEGO approach has been improved upon in several theoretical works, but never implemented. In this paper we describe further … Continued
Abstract. The Cut-and-choose paradigm gives by far the most popular and efficient secure two-party computation protocols in the standard malicious model, able to offer s bits of security with only s copies of garbled circuits in the one-time execution scenario [33]. Nielsen, Orlandi et al. [48,13] have even proposed the seminal idea of LEGO-style cut-and-choose to further reduce the number of circuit copies to less than s while still keep constant round complexity. However, a substantial gap still exists between the theoretical idea of LEGO cut-and-choose and a practical implementation, e.g., [48] is not compatible with free-XOR and uses expensive asymmetric key operations for soldering, while [13] leaves the important building-block of soldering unspecified. In this work, we introduce XOR-Homomorphic Interactive Hash and propose an efficient implemen-tation of this primitive by combining Reed-Solomon encoding and k-out-of-n oblivious transfers. We show how to apply this primitive to solve the performance-critical wire-soldering problem and propose a new LEGO-style cut-and-choose protocol. Comparing to previous LEGO-style protocols, ours only requires a single (as opposed to “a majority of”) correctly garbled gate in each bucket to guarantee security against malicious adversaries. Plus, through integrating Half-Gates garbling, we double the chance a “bad ” gate being detected in the check stage (compared to MiniLEGO [13]). Our construction