ETH Zürich » Computer Science » Theory » Cryptography

Secure Distributed Computation

Research Highlights

  • Separation of secure multi-party computation (MPC) and secure function evaluation (SFE). In secure computation, which come in two flavors, MPC and SFE, one considers an adversary with a certain capability of corrupting the parties in various ways. In [BFHMZ08] and [HMZ08] we have characterized exactly for which adversary capabilities on can securely perform MPC and SFE and have illustrated that the conditions for MPC and SFE separate, contrary to the fact that previous protocols applied to both MPC and SFE.
  • Efficient asynchronous multi-party computation. It was shown in [HNP05] and [HNP08] that MPC protocols for asynchronous networks (like the Internet) can be made almost as efficient as their synchronous counterparts.
  • Multi-party computation with linear communication. The communication overhead of multi-party computation could be reduced to be constant per participant and per multiplication, first with cryptographic security [HN05, HN06], then even with perfect security [BH08].
  • Detectable Byzantine agreement and multi-party computation. In [FGHHS02], it was shown that Byzantine agreement is possible with a higher corruption threshold, if the protocol may fail in the presence of cheating. This result was extended and generalized to multi-party computation in [FHHW03].
  • Resilience for free in secure multi-party computation. It was demonstrated in [HM01] that there exists a secure multi-party computation protocol resilient against cheating but equally efficient as protocols that are only secure if the players are guaranteed to follow the protocol correctly. The complexity of the basic operation in the best protocol was reduced from O(n^6) to O(n^2), where n is the number of players.
  • Generalized Byzantine agreement. Various new results on Byzantine agreement were published, introducing new models. For instance, it was shown in [FM00] that one can tolerate up to one half cheaters if broadcast from any sender to two other receivers is assumed to be available as a primitive.
  • Secure MPC from any linear secret sharing scheme. In [CDM00] it was shown that a secure MPC protocol can be constructed from any linear secret-sharing scheme, a primitive that was previously believed to be much weaker than MPC.
  • General adversary structures. In [HM97] (see also [HM00]) a new adversary model in multi-party cryptography was introduced. Instead of simply counting the number of players corruptible by an adversary (and hence assuming that all players are equally hard to corrupt and independent), all subsets of potentially corruptible players can be specified. Depending on the scenario, secure MPC is possible if and only if no two (three) of these sets cover the full player set. This allows to tolerate strictly more cheating than in a threshold setting.
  • Efficient voting protocol. In [CGS97] the most efficient known voting protocol was proposed.

Publications Concerning This Topic

Yuval Ishai, Rafail Ostrovsky, and Vassilis Zikas
Secure Multi-Party Computation with Identifiable Abort
Advances in Cryptology — CRYPTO 2014, Lecture Notes in Computer Science, Springer-Verlag, vol. 8617, pp. 369-386, Aug 2014.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Seung Geol Choi, Jonathan Katz, Alex J. Malozemoff, and Vassilis Zikas
Efficient Three-Party Computation from Cut-and-Choose
Advances in Cryptology — CRYPTO 2014, Lecture Notes in Computer Science, Springer-Verlag, vol. 8617, pp. 513-530, Aug 2014.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Jonathan Katz, Aggelos Kiayias, Hong-Sheng Zhou, and Vassilis Zikas
Distributing the Setup in Universally Composable Multi-Party Computation
ACM Symposium on Principles of Distributed Computing – PODC 2014, Jul 2014, (to appear).
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt, Ueli Maurer, and Pavel Raykov
Broadcast Amplification
Theory of Cryptography Conference — TCC 2014, Lecture Notes in Computer Science, Springer, vol. 8349, pp. 419–439, 2014.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Juan Garay, Clint Givens, Rafail Ostrovsky, and Pavel Raykov
Fast and Unconditionally Secure Anonymous Channel
Proc. 33rd ACM Symposium on Principles of Distributed Computing — PODC 2014, ACM, pp. 313–321, 2014.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt and Pavel Raykov
Multi-Valued Byzantine Broadcast: the $t < n$ Case
To appear in Advances in Cryptology — ASIACRYPT 2014, 2014.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt and Daniel Tschudi
Efficient General-Adversary Multi-Party Computation
Advances in Cryptology—ASIACRYPT 2013, Lecture Notes in Computer Science, Springer-Verlag, vol. 8270, pp. 181-200, Dec 2013.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Juan Garay, Clint Givens, Rafail Ostrovsky, and Pavel Raykov
Broadcast (and Round) Efficient Verifiable Secret Sharing
The 7th International Conference on Information Theoretic Security — ICITS 2013, Lecture Notes in Computer Science, Springer, vol. 8317, pp. 200–219, Nov 2013.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt, Christoph Lucas, and Ueli Maurer
A Dynamic Tradeoff Between Active and Passive Corruptions in Secure Multi-Party Computation
Advances in Cryptology — CRYPTO 2013, Lecture Notes in Computer Science, Springer-Verlag, vol. 8043, pp. 203–219, Aug 2013.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt and Pavel Raykov
On the Complexity of Broadcast Setup
Automata, Languages, and Programming — 40th International Colloquium, ICALP (1), Lecture Notes in Computer Science, Springer, vol. 7965, pp. 552–563, Jul 2013.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas
Universally Composable Synchronous Computation
Theory of Cryptography — TCC 2013, Lecture Notes in Computer Science, Springer, vol. 7785, pp. 477-498, Mar 2013.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Jan Camenisch, Robert R. Enderlein, and Victor Shoup
Practical and Employable Protocols for UC-Secure Circuit Evaluation over Zn
Computer Security - ESORICS 2013 - 18th European Symposium on Research in Computer Security, Lecture Notes in Computer Science, Springer, vol. 8134, pp. 19–37, 2013.
Available files: [ Abstract ] [ BibTeX ]
Joel Alwen, Jonathan Katz, Ueli Maurer, and Vassilis Zikas
Collusion-Preserving Computation
Advances in Cryptology — CRYPTO 2012, Lecture Notes in Computer Science, Springer-Verlag, vol. 7417, pp. 124-143, Aug 2012.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt, Christoph Lucas, Ueli Maurer, and Dominik Raub
Passive Corruption in Statistical Multi-Party Computation
The 6th International Conference on Information Theoretic Security - ICITS 2012, Lecture Notes in Computer Science, Springer-Verlag, 2012, Full Version available from http://eprint.iacr.org/2012/272.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Jan Camenisch, Maria Dubovitskaya, Robert R. Enderlein, and Gregory Neven
Oblivious Transfer with Hidden Access Control from Attribute-Based Encryption
Security and Cryptography for Networks - 8th International Conference, Lecture Notes in Computer Science, Springer, vol. 7485, pp. 559–579, 2012.
Available files: [ Abstract ] [ BibTeX ]
Martin Hirt and Vassilis Zikas
Player-Centric Byzantine Agreement
Automata, Languages and Programming — 38th International Colloquium, ICALP 2011, Lecture Notes in Computer Science, Springer-Verlag, vol. 6755, pp. 281–292, Jul 2011.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer and Renato Renner
Abstract Cryptography
The Second Symposium on Innovations in Computer Science, ICS 2011, Tsinghua University Press, pp. 1–21, Jan 2011.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt, Christoph Lucas, Ueli Maurer, and Dominik Raub
Graceful Degradation in Multi-Party Computation
The 5th International Conference on Information Theoretic Security - ICITS 2011, Lecture Notes in Computer Science, Springer-Verlag, vol. 6673, pp. 163–180, 2011, Full Version available from http://eprint.iacr.org/2011/094.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Arpita Patra
Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication Complexity
OPODIS, Lecture Notes in Computer Science, Springer, vol. 7109, pp. 34-49, 2011.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Arpita Patra and C. Pandu Rangan
Communication Optimal Multi-valued Asynchronous Byzantine Agreement with Optimal Resilience
ICITS, Lecture Notes in Computer Science, Springer, vol. 6673, pp. 206-226, 2011.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Ashish Choudhury, Kaoru Kurosawa, Arpita Patra
The Round Complexity of Perfectly Secure General VSS
ICITS, Lecture Notes in Computer Science, Springer, vol. 6673, pp. 143-162, 2011.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Zuzana {Beerliova-Trubiniova}, Martin Hirt, and Jesper Buus Nielsen
On the Theoretical Gap Between Synchronous and Asynchronous MPC Protocols
Proc. of the 2010 ACM Symposium on Principles of Distributed Computing — PODC '10, pp. 211–218, Jul 2010.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Christoph Lucas, Dominik Raub, and Ueli Maurer
Hybrid-Secure MPC: Trading Information-Theoretic Robustness for Computational Privacy
Proc. of the 2010 ACM Symposium on Principles of Distributed Computing — PODC '10, pp. 219–228, Jul 2010, Full Version available from http://eprint.iacr.org/2009/009.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt and Vassilis Zikas
Adaptively Secure Broadcast
Advances in Cryptology — EUROCRYPT 2010, Lecture Notes in Computer Science, Springer-Verlag, vol. 6110, pp. 466–485, May 2010.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Joel Alwen, Jonathan Katz, Yehuda Lindell, Giuseppe Persiano, Abhi Shelat, and Ivan Visconti
Collusion-Free Multiparty Computation in the Mediated Model
Advances in Cryptology — CRYPTO 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5677, pp. 524-540, Aug 2009.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Vassilis Zikas, Sarah Hauser, and Ueli Maurer
Realistic Failures in Secure Multi-party Computation
Theory of Cryptography Conference — TCC 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5444, pp. 274-293, Mar 2009.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Robin Künzler, Jörn Müller-Quade, and Dominik Raub
Secure Computability of Functions in the IT setting with Dishonest Majority and Applications to Long-Term Security
Theory of Cryptography — TCC 2009, Lecture Notes in Computer Science, Springer-Verlag, Mar 2009.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt, Ueli Maurer, and Vassilis Zikas
{MPC} vs. {SFE}: Unconditional and Computational Security
Advances in Cryptology — ASIACRYPT 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 5350, pp. 1–18, Dec 2008.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Joel Alwen, Abhi Shelat, and Ivan Visconti
Collusion-Free Protocols in the Mediated Model
Advances in Cryptology — CRYPTO 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 5157, pp. 497-514, Aug 2008.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek
Asynchronous Multi-Party Computation With Quadratic Communication
Automata, Languages and Programming — ICALP 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 5126, pp. 473–485, Jul 2008.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
Rethinking Digital Signatures
Proc. of SECRYPT 2008, INSTICC, pp. IS-31–IS-33, Jul 2008.
Available files: [ Abstract ] [ BibTeX ]
Zuzana {Beerliova-Trubiniova}, Matthias Fitzi, Martin Hirt, Ueli Maurer, and Vassilis Zikas
{MPC} vs. {SFE}: Perfect Security in a Unified Corruption Model
Theory of Cryptography Conference — TCC 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 4948, pp. 231–250, Mar 2008.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Zuzana {Beerliova-Trubiniova} and Martin Hirt
Perfectly-Secure {MPC} with Linear Communication Complexity
Theory of Cryptography Conference — TCC 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 4948, pp. 213–230, Mar 2008.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Zuzana {Beerliova-Trubiniova}, Martin Hirt, and Micha Riser
Efficient {B}yzantine Agreement with Faulty Minority
Advances in Cryptology — ASIACRYPT 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4833, pp. 393 - 409, Dec 2007.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Zuzana {Beerliova-Trubiniova} and Martin Hirt
Simple and Efficient Perfectly-Secure Asynchronous {MPC}
Advances in Cryptology — ASIACRYPT 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4833, pp. 376–392, Dec 2007.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Bartosz Przydatek
Approaches to Efficient and Robust Cryptographic Protocols
PhD Thesis, {ETH Zurich}, 2007, Diss. ETH No. 17102, ISBN 978-3-86628-153-0.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Remo Meier, Bartosz Przydatek, and J{ü}rg Wullschleger
Robuster Combiners for Oblivious Transfer
Theory of Cryptography Conference — TCC 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4392, pp. 404–418, Feb 2007.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Haowen Chan, Adrian Perrig, Bartosz Przydatek, and Dawn Song
{SIA}: Secure Information Aggregation in Sensor Networks
Journal of Computer Security, vol. 15, no. 1, pp. 69–102, Jan 2007, Special Issue on Security of Ad-Hoc and Sensor Networks. Preliminary version: [PSP03].
Available files: [ Abstract ] [ BibTeX ]
Remo Meier and Bartosz Przydatek
On Robust Combiners for Private Information Retrieval and Other Primitives
Advances in Cryptology — CRYPTO 2006, Lecture Notes in Computer Science, Springer-Verlag, vol. 4117, pp. 555–569, Aug 2006.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt and Jesper Buus Nielsen
Robust Multiparty Computation with Linear Communication Complexity
Advances in Cryptology — CRYPTO 2006, Lecture Notes in Computer Science, Springer-Verlag, vol. 4117, pp. 463–482, Aug 2006.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Matthias Fitzi and Martin Hirt
Optimally Efficient Multi-Valued {B}yzantine Agreement
Proc. 25th {ACM} Symposium on Principles of Distributed Computing — PODC 2006, ACM, Jul 2006.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Christian Cachin and Stefano Tessaro
Optimal Resilience for Erasure-Coded Byzantine Distributed Storage
Proc. Intl. Conference on Dependable Systems and Networks — DSN 2006, pp. 115–124, Jun 2006.
Available files: [ Abstract ] [ BibTeX ]
Zuzana {Beerliova-Trubiniova} and Martin Hirt
Efficient Multi-Party Computation with Dispute Control
Theory of Cryptography Conference — TCC 2006, Lecture Notes in Computer Science, Springer-Verlag, vol. 3876, pp. 305–328, Mar 2006.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
Secure Multi-party Computation made Simple
Discrete Applied Mathematics, vol. 154, pp. 370–381, 2006.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Christian Cachin and Stefano Tessaro
Asynchronous Verifiable Information Dispersal
Proceedings of the 24th Symposium on Reliable Distributed Systems — SRDS 2005, pp. 191–202, Oct 2005.
Available files: [ Abstract ] [ BibTeX ]
Jeffrey Considine, Matthias Fitzi, Matthew Franklin, Leonid A. Levin, Ueli Maurer, and David Metcalf
{B}yzantine Agreement Given Partial Broadcast
Journal of Cryptology, vol. 18, no. 3, pp. 191–217, Jul 2005.
Available files: [ Abstract ] [ BibTeX ]
Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek
Cryptographic Asynchronous Multi-Party Computation with Optimal Resilience
Advances in Cryptology — EUROCRYPT 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3494, pp. 322–340, May 2005, Full version available as Report 2004/368 at Cryptology ePrint Archive, http://eprint.iacr.org/2004/368.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Bartosz Przydatek and Reto Strobl
Asynchronous Proactive Cryptosystems Without Agreement (extended abstract)
Advances in Cryptology — ASIACRYPT 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 3329, pp. 152–169, Dec 2004.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
Towards a Theory of Consistency Primitives
International Symposium on Distributed Computing — DISC 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 3274, pp. 379–389, Oct 2004.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Bartosz Przydatek, Dawn Song, and Adrian Perrig
{SIA}: Secure Information Aggregation in Sensor Networks
Proc. {ACM} Conference on Embedded Networked Sensor Systems — SENSYS 2003, ACM, pp. 255–265, Nov 2003, Journal version: [CPPS07].
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Matthias Fitzi, Martin Hirt, Thomas Holenstein, and J{ü}rg Wullschleger
Two-Threshold Broadcast and Detectable Multi-Party Computation
Advances in Cryptology — EUROCRYPT 2003, Lecture Notes in Computer Science, Springer-Verlag, vol. 2656, pp. 51–67, May 2003.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Matthias Fitzi
Generalized Communication and Security Models in {B}yzantine Agreement
PhD Thesis, {ETH Zurich}, 2003, Reprint as vol. 4 of ETH Series in Information Security and Cryptography}, {ISBN} 3-89649-853-3, {H}artung-{G}orre {V}erlag, {K}onstanz, 2003.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt and Ueli Maurer
Robustness for Free in Unconditional Multi-Party Computation
Advances in Cryptology — CRYPTO 2001, Lecture Notes in Computer Science, Springer-Verlag, vol. 2139, pp. 101–118, Aug 2001.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Martin Hirt, Ueli Maurer, and Bartosz Przydatek
Efficient Secure Multi-Party Computation
Advances in Cryptology — ASIACRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, vol. 1976, pp. 143–161, Dec 2000.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Matthias Fitzi and Ueli Maurer
Global Broadcast by Broadcasts Among Subsets of Players
IEEE International Symposium on Information Theory — ISIT 2000, IEEE, pp. 267, Jun 2000.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Matthias Fitzi and Ueli Maurer
From Partial Consistency to Global Broadcast
Proc. 32nd ACM Symposium on Theory of Computing — STOC 2000, ACM, pp. 494–503, May 2000.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Matthias Fitzi, Martin Hirt, and Ueli Maurer
General Adversaries in Unconditional Multi-Party Computation
Advances in Cryptology — ASIACRYPT '99, Lecture Notes in Computer Science, Springer-Verlag, vol. 1716, pp. 232–246, Nov 1999.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Bernd Altmann, Matthias Fitzi, and Ueli Maurer
{B}yzantine Agreement Secure Against General Adversaries in the Dual Failure Model
International Symposium on Distributed Computing — DISC '99, Lecture Notes in Computer Science, Springer-Verlag, vol. 1693, pp. 123–137, Sep 1999.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ronald Cramer, Ivan Damg{å}rd, Stefan Dziembowski, Martin Hirt, and Tal Rabin
Efficient Multiparty Computations Secure Against an Adaptive Adversary
Advances in Cryptology — EUROCRYPT '99, Lecture Notes in Computer Science, Springer-Verlag, vol. 1592, pp. 311–326, May 1999.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Serge Fehr
Efficient Construction of the Dual Span Program
Manuscript, May 1999.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Matthias Fitzi and Ueli Maurer
Efficient Byzantine Agreement Secure Against General Adversaries
International Symposium on Distributed Computing — DISC '98, Lecture Notes in Computer Science, Springer-Verlag, vol. 1499, pp. 134–148, Sep 1998.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Matthias Fitzi, Martin Hirt, and Ueli Maurer
Trading Correctness for Privacy in Unconditional Multi-Party Computation
Advances in Cryptology — CRYPTO '98, Lecture Notes in Computer Science, Springer-Verlag, vol. 1462, pp. 121–136, Aug 1998, Corrected proceedings version.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers
A Secure and Optimally Efficient Multi-Authority Election Scheme
Advances in Cryptology — EUROCRYPT '97, Lecture Notes in Computer Science, Springer-Verlag, vol. 1233, pp. 103–118, May 1997, Final version: [CGS97].
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]

© IACR | Springer | ACM | IEEE


Main Research Page