All Papers By Category

Database contains 40 papers. Some papers are listed in multiple categories (and some listed in no category!).

Circuit constructions & optimizations (2 papers)»

Circuits of interest to secure computation. Combinatorial aspects of circuits in general that affect their suitability for secure computation.

[KS08b] Vladimir Kolesnikov, Thomas Schneider. A Practical Universal Circuit Construction and Secure Evaluation of Private Functions. FC 2008 [pdf] [bibtex]

Summary: Constructs a universal circuit that is asymptotically suboptimal (by a log factor) but whose concrete size is smaller than Valiant's (asymptotically optimal) construction for input circuits up to several thousand gates. »

[V76] Leslie Valiant. Universal Circuits. STOC 1976 [bibtex]

Summary: Construction of a "universal circuit" that takes an encoding of a circuit ⚠ {$C$} and value ⚠ {$x$} as input, and outputs ⚠ {$C(x)$} »

Cut-and-choose mechanisms (9 papers)»

The cut-and-choose mechanism and ways to deal with input consistency, output authenticity, selective failure, two-output functionalities, etc., against malicious adversaries.

[B13] Luís T. A. N. Brandão. Secure Two-Party Computation with Reusable Bit-Commitments, via a Cut-and-Choose with Forge-and-Lose Technique. Asiacrypt 2013 [pdf] [bibtex]

Summary: New cut-and-choose mechanism, achieving statistical security ⚠ {$2^{-s}$} only ⚠ {$\sim s$} garbled circuits. »

[FJNOO13] Tore Kasper Frederiksen, Thomas Pelle Jakobsen, Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi . MiniLEGO: Efficient Secure Two-Party Computation. EUROCRYPT 2013 [pdf] [bibtex]

Summary: Improves upon the NO09? LEGO protocol construction by relying on standard assumptions. »

[KS06] Mehmet Kiraz, Berry Schoenmakers. A Protocol Issue for the Malicious Case of Garbled Circuit Construction. Information Theory in the Benelux 2006 [pdf]

Summary: Identifies and fixes an issue related to selective failure attacks in cut-and-choose protocols. »

[L13] Yehuda Lindell. Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries. CRYPTO 2013 [pdf] [bibtex]

Summary: Presents a cut-and-choose mechanism requiring only ⚠ {$s$} garbled circuits for ⚠ {$2^{-s}$} security »

[LP07] Yehuda Lindell, Benny Pinkas. An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. EUROCRYPT 2007 [pdf] [bibtex]

Summary: The first cut-and-choose protocol with complete formal security proof »

[LP12] Yehuda Lindell, Benny Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. J Cryptology 2012 [pdf] [bibtex]

Summary: Efficiency improvements to the cut-and-choose method, using a new abstraction of cut-and-choose OT. »

[MR13] Payman Mohassel, Ben Riva. Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation. CRYPTO 2013 [pdf] [bibtex]

Summary: Several new techniques giving efficiency improvements to cut-and-choose mechanisms »

[SS11] abhi shelat, Chih-Hao Shen. Two-Output Secure Computation with Malicious Adversaries. EUROCRYPT 2011 [pdf] [bibtex]

Summary: Several new techniques for malicious security in the cut-and-choose paradigm »

[SS13] abhi shelat, Chih-Hao Shen. Fast two-party secure computation with minimal assumptions. ACM CCS 2013 [pdf] [bibtex]

Summary: Achieves malicious-secure 2PC with linear overhead in the security parameter, from general assumptions »

Garbling methods (10 papers)»

The garbling aspect of secure 2PC protocols.

[BHKR13] Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, Phillip Rogaway. Efficient Garbling from a Fixed-Key Blockcipher. SSP 2013 [pdf] [bibtex]

Summary: Achieves very fast circuit garbling by leveraging hardware AES instruction set »

[BHR12] Mihir Bellare, Viet Tung Hoang, Phillip Rogaway. Foundations of Garbled Circuits. ACM CCS 2012 [pdf] [bibtex]

Summary: The concept of a "garbling scheme" is abstracted as a fundamental cryptographic primitive. »

[CKKZ12] Seung Geol Choi, Jonathan Katz, Ranjit Kumaresan, Hong-Sheng Zhou. On the Security of the "Free-XOR" Technique. TCC 2012 [pdf] [bibtex]

Summary: Precisely identifies the security assumption needed for the free-XOR optimization »

[K05] Vladimir Kolesnikov. Gate Evaluation Secret Sharing And Secure One-Round Two-Party Computation. ASIACRYPT 2005 [pdf] [bibtex]

Summary: no summary yet »

[KMR14] Vladimir Kolesnikov, Payman Mohassel, Mike Rosulek. FleXOR: Flexible garbling for XOR gates that beats free-XOR. CRYPTO 2014 [pdf]

Summary: Introduces a garbling scheme FleXOR which offers some improvements over free-XOR »

[KS08] Vladimir Kolesnikov, Thomas Schneider. Improved garbled circuit: free XOR gates and applications. ICALP 2008 [pdf] [bibtex]

Summary: A method for garbling boolean circuits that allows XOR gates to be free (in garbling, communication, and evaluation costs) »

[LP09] Yehuda Lindell, Benny Pinkas. A proof of security of Yao's protocol for two-party computation. J Cryptology 2009 [pdf] [bibtex]

Summary: A formal description and security proof of Yao's 2PC protocol »

[MNPS04] Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella. Fairplay - Secure Two-Party Computation System. USENIX 2004 [pdf] [bibtex]

Summary: First implementation of 2PC. Introduces Point and Permute »

[PSSW09] Benny Pinkas, Thomas Schneider, Nigel P. Smart, Stephen C. Williams. Secure Two-Party Computation Is Practical. ASIACRYPT 2009 [pdf] [bibtex]

Summary: Describes several practical optimizations for MPC, including a new row-reduction technique »

[Y86] Andrew Yao. How to generate and exchange secrets. FOCS 1986 [pdf] [bibtex]

Summary: The paper credited with garbled circuits »

Implementations (2 papers)»

Implementation and analysis of secure computation protocols.

[KSS12] Benjamin Kreuter, abhi shelat, Chih-Hao Shen. Billion-Gate Secure Computation with Malicious Adversaries. USENIX 2012 [pdf]

Summary: no summary yet »

[LPS08] Yehuda Lindell, Benny Pinkas, Nigel Smart. Implementing Two-Party Computation Efficiently with Security Against Malicious Adversaries. SCN 2008 [pdf] [bibtex]

Summary: no summary yet »

Oblivious transfer extension (3 papers)»

Efficiently extending oblivious transfers.

[ALSZ13] Gilad Asharov, Yehuda Lindell, Thomas Schneider, Michael Zohner. More efficient oblivious transfer and extensions for faster secure computation. ACM CCS 2013 [pdf] [bibtex]

Summary: Practical optimizations for OT extension »

[IKNP03] Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank. Extending Oblivious Transfers Efficiently. CRYPTO 2003 [pdf] [bibtex]

Summary: OT extension provides a large number of OTs using a small number of "base" OTs plus cheap symmetric-key operations. »

[KK13] Vladimir Kolesnikov, Ranjit Kumaresan. Improved OT Extension for Transferring Short Secrets. CRYPTO 2013 [pdf] [bibtex]

Summary: no summary yet »

Protocol paradigms (4 papers)»

Basic paradigms for secure computation

[GKKKMRV12] S. Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, Yevgeniy Vahlis. Secure Computation with Sublinear Amortized Work. CCS 2012 [pdf] [bibtex]

Summary: Presents a semi-honest-secure 2PC protocol for securely evaluating an oblivious RAM program »

[KK12] Vladimir Kolesnikov, Ranjit Kumaresan. Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits. SCN 2012 [pdf] [bibtex]

Summary: A new paradigm for semi-honest and covert-secure 2PC using information-theoretic garbling. »

[MF06] Payman Mohassel, Matthew Franklin. Efficiency Tradeoffs for Malicious Two-Party Computation. PKC 2006 [pdf] [bibtex]

Summary: Introduces the dual-execution method for 2PC »

[Y86] Andrew Yao. How to generate and exchange secrets. FOCS 1986 [pdf] [bibtex]

Summary: The paper credited with garbled circuits »

Reference works (3 papers)»

Textbooks, lecture notes, survey papers.

[HL10] Carmit Hazay, Yehuda Lindell. Efficient Secure Two-Party Protocols. Monograph, Springer Information Security and Cryptography Series 2010 [bibtex]

Summary: Monograph covering definitions and constructions for efficient 2PC protocols. »

[LP08] Yehuda Lindell, Benny Pinkas. Secure Multiparty Computation for Privacy-Preserving Data Mining. eprint 2008 [pdf] [bibtex]

Summary: Tutorial on secure computation techniques »

[S12] Thomas Schneider. Engineering Secure Two-Party Computation Protocols. Monograph, Springer 2012 [bibtex]

Summary: no summary yet »

Security models (5 papers)»

Security models beyond the "standard" ones of semi-honest and malicious adversaries.

[AL10] Yonatan Aumann, Yehuda Lindell. Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries. J Cryptology 2010 [pdf] [bibtex]

Summary: Defines a new model of "covert security" in which honest parties are guaranteed to detect cheating parties with some specified probability. »

[AO12] Gilad Asharov, Claudio Orlandi. Calling Out Cheaters: Covert Security with Public Verifiability. ASIACRYPT 2012 [pdf] [bibtex]

Summary: Augments the covert model of security so that honest parties receive publicly verifiable proof of cheating. »

[HKE12] Yan Huang, Jonathan Katz, David Evans. Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution. S&P 2012 [pdf] [bibtex]

Summary: Provides a more detailed treatment of the dual-execution protocol of MF06 »

[MF06] Payman Mohassel, Matthew Franklin. Efficiency Tradeoffs for Malicious Two-Party Computation. PKC 2006 [pdf] [bibtex]

Summary: Introduces the dual-execution method for 2PC »

[MR13] Payman Mohassel, Ben Riva. Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation. CRYPTO 2013 [pdf] [bibtex]

Summary: Several new techniques giving efficiency improvements to cut-and-choose mechanisms »

Special-purpose protocols (1 papers)»

Practical protocols for specific functionalities or classes of functionalities.

[JKO13] Marek Jawurek and Florian Kerschbaum and Claudio Orlandi. Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently. ACM CCS 2013 [pdf] [bibtex]

Summary: Gives a practical protocol for ZK proofs, based on garbled circuits »