2023 Edsger W. Dijkstra Prize in Distributed Computing

The Edsger W. Dijkstra Prize in Distributed Computing is awarded for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributed computing have been evident for at least a decade. It is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). The prize is presented annually, with the presentation taking place alternately at PODC and DISC.

The 2023 Edsger W. Dijkstra Prize in Distributed Computing has been awarded to the papers

  • Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation, by Michael Ben-Or, Shafi Goldwasser and Avi Wigderson – STOC 1988, 1-10.
  • Multiparty Unconditionally Secure Protocols, by David Chaum, Claude Crépeau and Ivan Damgård – STOC 1988, 11-19.
  • Verifiable Secret Sharing and Multiparty Protocols with Honest Majority, by Tal Rabin and Michael Ben-Or – STOC 1989, 73-85.

for introducing Information-Theoretic Secure Multiparty Computations and showing how to achieve
maximal resilience to malicious adversaries while providing unconditional security.

The area of Secure Multiparty Computation (MPC) answers the following fundamental question about
distributed computations: How can a group of parties compute a function of their inputs while ensuring both the correctness of the output and the secrecy of each party’s input? Furthermore, this goal should be achieved in the case where some of the parties are malicious and try to foil the computation. Consequently, Secure MPC is at the heart of many large-scale distributed applications, including cloud services, blockchains and privacy-preserving distributed machine learning.

The awarded papers opened the vibrant area of MPC in the information theoretic setting, in which
thousands of works have been published, and that is still going strong. Protocols in the information theoretic model often are more efficient than their computational counterparts, in some cases by orders of magnitude, and thus have led to the most efficient state-of-the-art designs of MPC implementations. These protocols are an indispensable tool in the increasing demands for security and privacy in our modern digital society.

MPC and the techniques from the nominated papers have had tremendous impact on the broader area
of cryptography with such results relating to zero-knowledge proofs and coding theory. They also have had far reaching impact on the broader area of theoretical computer science by providing a technical basis and inspiration for such results as locally random reductions, private information retrieval, and locally decodable codes.

The 2023 Edsger W. Dijkstra Prize in Distributed Computing Award Committee:

  • Yehuda Afek, Tel-Aviv University
  •  Magnús M. Halldórsson (chair), Reykjavik University
  •  Idit Keidar, Technion
  •  Rotem Oshman, Tel-Aviv University
  •  Ulrich Schmid, TU Wien
  •  Gadi Taubenfeld, Reichman University