publications | Gilad Stern

2026

Nearly Quadratic Asynchronous Distributed Key Generation from Recursive Consensus

Ittai Abraham, Renas Bacho, Julian Loss, and Gilad Stern

In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2026, Egham, United Kingdom, July 6-10, 2026, 2026

DOI ePrint Bib

@inproceedings{AbrahamBLS26,
  author = {Abraham, Ittai and Bacho, Renas and Loss, Julian and Stern, Gilad},
  editor = {Olivetti, Dennis and Ruppert, Eric and Ovens, Sean},
  title = {Nearly Quadratic Asynchronous Distributed Key Generation from Recursive
                    Consensus},
  booktitle = {Proceedings of the {ACM} Symposium on Principles of Distributed Computing,
                    {PODC} 2026, Egham, United Kingdom, July 6-10, 2026},
  pages = {247--258},
  publisher = {{ACM}},
  year = {2026},
  url = {https://doi.org/10.1145/3796701.3815942},
  doi = {10.1145/3796701.3815942},
  timestamp = {Tue, 21 Jul 2026 17:07:25 +0200},
  biburl = {https://dblp.org/rec/conf/podc/AbrahamBLS26.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

Fast and Efficient Perfectly Secure Network-Agnostic Secure Computation

Gilad Asharov, Fatima Elsheimy, and Gilad Stern

In Advances in Cryptology - EUROCRYPT 2026 - 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10-14, 2026, Proceedings, Part III, 2026

DOI ePrint Bib

@inproceedings{AsharovES26,
  author = {Asharov, Gilad and Elsheimy, Fatima and Stern, Gilad},
  editor = {Daemen, Joan and Thom{\'{e}}, Emmanuel},
  title = {Fast and Efficient Perfectly Secure Network-Agnostic Secure Computation},
  booktitle = {Advances in Cryptology - {EUROCRYPT} 2026 - 45th Annual International
                    Conference on the Theory and Applications of Cryptographic Techniques,
                    Rome, Italy, May 10-14, 2026, Proceedings, Part {III}},
  series = {Lecture Notes in Computer Science},
  volume = {16543},
  pages = {185--213},
  publisher = {Springer},
  year = {2026},
  url = {https://doi.org/10.1007/978-3-032-25324-8\_7},
  doi = {10.1007/978-3-032-25324-8\_7},
  timestamp = {Fri, 10 Jul 2026 14:28:23 +0200},
  biburl = {https://dblp.org/rec/conf/eurocrypt/AsharovES26.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

Quadratic Asynchronous DKG from Plain Setup

Ittai Abraham, Renas Bacho, and Gilad Stern
To be published in DISC 2026.
2026

ePrint

2025

Asynchronous Algorand: Reaching Agreement with Near Linear Communication and Constant Expected Time

Ittai Abraham, Eli Chouatt, Yossi Gilad, Gilad Stern, and Sophia Yakoubov

In Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

DOI ePrint Bib

The celebrated Algorand protocol solves validated byzantine agreement in a scalable manner in the synchronous setting. In this paper, we study the feasibility of similar solutions in the asynchronous setting. Our main result is an asynchronous validated byzantine agreement protocol that we call Asynchronous Algorand. As with Algorand, it terminates in an expected constant number of rounds, and honest parties send an expected O(n polylog n) bits, where n is the number of parties. The protocol is resilient to a fully-asynchronous weak-adaptive adversary that can corrupt a near-optimal number of parties (< (1/3 - ϵ)n) and requires just a verifiable random function (VRF) setup and secure erasures.A key innovation in Asynchronous Algorand is a rather simple but surprisingly effective method to do committee-based role assignment for asynchronous verifiable secret sharing in the You Only Speak Once (YOSO) model. This method achieves near-optimal resilience and near-linear communication complexity while relying solely on a VRF setup and secure erasures.
@inproceedings{10.1145/3732772.3733533, author = {Abraham, Ittai and Chouatt, Eli and Gilad, Yossi and Stern, Gilad and Yakoubov, Sophia}, title = {Asynchronous Algorand: Reaching Agreement with Near Linear Communication and Constant Expected Time}, year = {2025}, isbn = {9798400718854}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3732772.3733533}, doi = {10.1145/3732772.3733533}, booktitle = {Proceedings of the ACM Symposium on Principles of Distributed Computing}, pages = {28–38}, numpages = {11}, keywords = {consensus, asynchrony, cryptographic protocols, committee sampling}, location = {Hotel Las Brisas Huatulco, Huatulco, Mexico}, series = {PODC '25}, }
Nested YOSO MPC: Near Optimal Resilience Without an MPC Setup

Ittai Abraham, Eli Chouatt, Ivan Damgård, Yossi Gilad, Gilad Stern, and Sophia Yakoubov
To be published in TCC 2026.
2025

ePrint

2024

Asynchronous Agreement on a Core Set in Constant Expected Time and More Efficient Asynchronous VSS and MPC

Ittai Abraham, Gilad Asharov, Arpita Patra, and Gilad Stern

In Theory of Cryptography - 22nd International Conference, TCC 2024, Milan, Italy, December 2-6, 2024, Proceedings, Part IV, 2024

DOI ePrint Bib

@inproceedings{DBLP:conf/tcc/AbrahamAPS24,
  author = {Abraham, Ittai and Asharov, Gilad and Patra, Arpita and Stern, Gilad},
  editor = {Boyle, Elette and Mahmoody, Mohammad},
  title = {Asynchronous Agreement on a Core Set in Constant Expected Time and
                    More Efficient Asynchronous {VSS} and {MPC}},
  booktitle = {Theory of Cryptography - 22nd International Conference, {TCC} 2024,
                    Milan, Italy, December 2-6, 2024, Proceedings, Part {IV}},
  series = {Lecture Notes in Computer Science},
  volume = {15367},
  pages = {451--482},
  publisher = {Springer},
  year = {2024},
  url = {https://doi.org/10.1007/978-3-031-78023-3\_15},
  doi = {10.1007/978-3-031-78023-3\_15},
  timestamp = {Sun, 22 Dec 2024 15:48:25 +0100},
  biburl = {https://dblp.org/rec/conf/tcc/AbrahamAPS24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

On the Round Complexity of Asynchronous Crusader Agreement

Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri

In 27th International Conference on Principles of Distributed Systems (OPODIS 2023), 2024

DOI ePrint Bib

@inproceedings{abraham_et_al:LIPIcs.OPODIS.2023.29,
  author = {Abraham, Ittai and Ben-David, Naama and Stern, Gilad and Yandamuri, Sravya},
  title = {{On the Round Complexity of Asynchronous Crusader Agreement}},
  booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages = {29:1--29:21},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-308-9},
  issn = {1868-8969},
  year = {2024},
  volume = {286},
  editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.29},
  urn = {urn:nbn:de:0030-drops-195195},
  doi = {10.4230/LIPIcs.OPODIS.2023.29},
  annote = {Keywords: lower bounds, asynchronous protocols, round complexity},
}

HARTS: High-Threshold, Adaptively Secure, and Robust Threshold Schnorr Signatures

Renas Bacho, Julian Loss, Gilad Stern, and Benedikt Wagner

In Advances in Cryptology - ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9-13, 2024, Proceedings, Part III, 2024

DOI ePrint Bib

@inproceedings{DBLP:conf/asiacrypt/BachoLSW24,
  author = {Bacho, Renas and Loss, Julian and Stern, Gilad and Wagner, Benedikt},
  editor = {Chung, Kai{-}Min and Sasaki, Yu},
  title = {{HARTS:} High-Threshold, Adaptively Secure, and Robust Threshold Schnorr
                    Signatures},
  booktitle = {Advances in Cryptology - {ASIACRYPT} 2024 - 30th International Conference
                    on the Theory and Application of Cryptology and Information Security,
                    Kolkata, India, December 9-13, 2024, Proceedings, Part {III}},
  series = {Lecture Notes in Computer Science},
  volume = {15486},
  pages = {104--140},
  publisher = {Springer},
  year = {2024},
  url = {https://doi.org/10.1007/978-981-96-0891-1\_4},
  doi = {10.1007/978-981-96-0891-1\_4},
  timestamp = {Wed, 08 Jan 2025 21:12:46 +0100},
  biburl = {https://dblp.org/rec/conf/asiacrypt/BachoLSW24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

Consensus in the Presence of Overlapping Faults and Total Omission

Julian Loss, Kecheng Shi, and Gilad Stern

In Theory of Cryptography - 22nd International Conference, TCC 2024, Milan, Italy, December 2-6, 2024, Proceedings, Part I, 2024

DOI ePrint Bib

@inproceedings{DBLP:conf/tcc/LossSS24,
  author = {Loss, Julian and Shi, Kecheng and Stern, Gilad},
  editor = {Boyle, Elette and Mahmoody, Mohammad},
  title = {Consensus in the Presence of Overlapping Faults and Total Omission},
  booktitle = {Theory of Cryptography - 22nd International Conference, {TCC} 2024,
                    Milan, Italy, December 2-6, 2024, Proceedings, Part {I}},
  series = {Lecture Notes in Computer Science},
  volume = {15364},
  pages = {353--382},
  publisher = {Springer},
  year = {2024},
  url = {https://doi.org/10.1007/978-3-031-78011-0\_12},
  doi = {10.1007/978-3-031-78011-0\_12},
  timestamp = {Sun, 22 Dec 2024 15:48:25 +0100},
  biburl = {https://dblp.org/rec/conf/tcc/LossSS24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

2023

Uncle Maker: (Time)Stamping Out The Competition in Ethereum

Aviv Yaish, Gilad Stern, and Aviv Zohar

In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023, 2023

Received the Disinguished Paper Award.

DOI ePrint Bib

Disinguished Paper Award

@inproceedings{DBLP:conf/ccs/YaishSZ23,
  author = {Yaish, Aviv and Stern, Gilad and Zohar, Aviv},
  editor = {Meng, Weizhi and Jensen, Christian Damsgaard and Cremers, Cas and Kirda, Engin},
  title = {Uncle Maker: (Time)Stamping Out The Competition in Ethereum},
  booktitle = {Proceedings of the 2023 {ACM} {SIGSAC} Conference on Computer and
                    Communications Security, {CCS} 2023, Copenhagen, Denmark, November
                    26-30, 2023},
  pages = {135--149},
  publisher = {{ACM}},
  year = {2023},
  url = {https://doi.org/10.1145/3576915.3616674},
  doi = {10.1145/3576915.3616674},
  timestamp = {Sun, 19 Jan 2025 13:26:42 +0100},
  biburl = {https://dblp.org/rec/conf/ccs/YaishSZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks

Ittai Abraham and Gilad Stern

In 26th International Conference on Principles of Distributed Systems (OPODIS 2022), 2023

Received the Best Student Paper Award.

DOI ePrint Bib

Best Student Paper Award

@inproceedings{abraham2022newDR,
  author = {Abraham, Ittai and Stern, Gilad},
  title = {{New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks}},
  booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages = {16:1--16:18},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-265-5},
  issn = {1868-8969},
  year = {2023},
  volume = {253},
  editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/opus/volltexte/2023/17636},
  urn = {urn:nbn:de:0030-drops-176368},
  doi = {10.4230/LIPIcs.OPODIS.2022.16},
  annote = {Keywords: consensus, crusader broadcast, Byzantine fault tolerance, blockchain, synchrony, lower bounds},
}

Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing and Distributed Key Generation

Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, and Gilad Stern

In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part I, 2023

DOI ePrint Bib

@inproceedings{DBLP:conf/crypto/AbrahamJMMS23,
  author = {Abraham, Ittai and Jovanovic, Philipp and Maller, Mary and Meiklejohn, Sarah and Stern, Gilad},
  editor = {Handschuh, Helena and Lysyanskaya, Anna},
  title = {Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing and
                    Distributed Key Generation},
  booktitle = {Advances in Cryptology - {CRYPTO} 2023 - 43rd Annual International
                    Cryptology Conference, {CRYPTO} 2023, Santa Barbara, CA, USA, August
                    20-24, 2023, Proceedings, Part {I}},
  series = {Lecture Notes in Computer Science},
  volume = {14081},
  pages = {39--70},
  publisher = {Springer},
  year = {2023},
  url = {https://doi.org/10.1007/978-3-031-38557-5\_2},
  doi = {10.1007/978-3-031-38557-5\_2},
  timestamp = {Mon, 14 Aug 2023 16:16:25 +0200},
  biburl = {https://dblp.org/rec/conf/crypto/AbrahamJMMS23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

Zombies and Ghosts: Optimal Byzantine Agreement in the Presence of Omission Faults

Julian Loss and Gilad Stern

In Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part IV, 2023

DOI ePrint Bib

@inproceedings{loss2023zombies,
  author = {Loss, Julian and Stern, Gilad},
  editor = {Rothblum, Guy N. and Wee, Hoeteck},
  title = {Zombies and Ghosts: Optimal Byzantine Agreement in the Presence of Omission Faults},
  booktitle = {Theory of Cryptography - 21st International Conference, {TCC} 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part {IV}},
  series = {Lecture Notes in Computer Science},
  volume = {14372},
  pages = {395--421},
  publisher = {Springer},
  year = {2023},
  url = {https://doi.org/10.1007/978-3-031-48624-1\_15},
  doi = {10.1007/978-3-031-48624-1\_15},
  timestamp = {Wed, 06 Dec 2023 13:56:15 +0100},
  biburl = {https://dblp.org/rec/conf/tcc/LossS23.bib},
}

2022

Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults

Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern

In 36th International Symposium on Distributed Computing (DISC 2022), 2022

DOI ePrint Bib

@inproceedings{abraham2022authenticated,
  author = {Abraham, Ittai and Dolev, Danny and Kagan, Alon and Stern, Gilad},
  title = {{Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults}},
  booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
  pages = {38:1--38:3},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-255-6},
  issn = {1868-8969},
  year = {2022},
  volume = {246},
  editor = {Scheideler, Christian},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/opus/volltexte/2022/17229},
  urn = {urn:nbn:de:0030-drops-172292},
  doi = {10.4230/LIPIcs.DISC.2022.38},
  annote = {Keywords: consensus, state machine replication, mixed faults, synchrony, lower bounds},
}

Validated Byzantine Asynchronous Multidimensional Approximate Agreement

Maya Dotan, Gilad Stern, and Aviv Zohar

ArXiv, 2022

arXiv Bib

@article{Dotan2022ValidatedBA,
  title = {Validated Byzantine Asynchronous Multidimensional Approximate Agreement},
  author = {Dotan, Maya and Stern, Gilad and Zohar, Aviv},
  journal = {ArXiv},
  year = {2022},
  url = {https://arxiv.org/abs/2211.02126},
}

2021

Reaching Consensus for Asynchronous Distributed Key Generation

Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu

In PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, 2021

DOI Journal arXiv Bib

@inproceedings{DBLP:conf/podc/AbrahamJMMST21,
  author = {Abraham, Ittai and Jovanovic, Philipp and Maller, Mary and Meiklejohn, Sarah and Stern, Gilad and Tomescu, Alin},
  editor = {Miller, Avery and Censor{-}Hillel, Keren and Korhonen, Janne H.},
  title = {Reaching Consensus for Asynchronous Distributed Key Generation},
  booktitle = {{PODC} '21: {ACM} Symposium on Principles of Distributed Computing,
                    Virtual Event, Italy, July 26-30, 2021},
  pages = {363--373},
  publisher = {{ACM}},
  year = {2021},
  url = {https://doi.org/10.1145/3465084.3467914},
  doi = {10.1145/3465084.3467914},
  timestamp = {Sun, 19 Jan 2025 13:32:11 +0100},
  biburl = {https://dblp.org/rec/conf/podc/AbrahamJMMST21.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

Aggregatable Distributed Key Generation

Kobi Gurkan, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu

In Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, 2021

DOI ePrint Bib

@inproceedings{DBLP:conf/eurocrypt/GurkanJMMST21,
  author = {Gurkan, Kobi and Jovanovic, Philipp and Maller, Mary and Meiklejohn, Sarah and Stern, Gilad and Tomescu, Alin},
  editor = {Canteaut, Anne and Standaert, Fran{\c{c}}ois{-}Xavier},
  title = {Aggregatable Distributed Key Generation},
  booktitle = {Advances in Cryptology - {EUROCRYPT} 2021 - 40th Annual International
                    Conference on the Theory and Applications of Cryptographic Techniques,
                    Zagreb, Croatia, October 17-21, 2021, Proceedings, Part {I}},
  series = {Lecture Notes in Computer Science},
  volume = {12696},
  pages = {147--176},
  publisher = {Springer},
  year = {2021},
  url = {https://doi.org/10.1007/978-3-030-77870-5\_6},
  doi = {10.1007/978-3-030-77870-5\_6},
  timestamp = {Wed, 16 Jun 2021 11:54:07 +0200},
  biburl = {https://dblp.org/rec/conf/eurocrypt/GurkanJMMST21.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

Information Theoretic HotStuff

Ittai Abraham and Gilad Stern

In 24th International Conference on Principles of Distributed Systems (OPODIS 2020), 2021

DOI arXiv Bib

@inproceedings{abraham_et_al:LIPIcs.OPODIS.2020.11,
  author = {Abraham, Ittai and Stern, Gilad},
  title = {{Information Theoretic HotStuff}},
  booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages = {11:1--11:16},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-176-4},
  issn = {1868-8969},
  year = {2021},
  volume = {184},
  editor = {Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.11},
  urn = {urn:nbn:de:0030-drops-134969},
  doi = {10.4230/LIPIcs.OPODIS.2020.11},
  annote = {Keywords: byzantine agreement, partial synchrony, bounded space},
}

2020

Revisiting Asynchronous Fault Tolerant Computation with Optimal Resilience

Ittai Abraham, Danny Dolev, and Gilad Stern

In PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, 2020

DOI Journal arXiv Bib

@inproceedings{DBLP:conf/podc/AbrahamDS20,
  author = {Abraham, Ittai and Dolev, Danny and Stern, Gilad},
  editor = {Emek, Yuval and Cachin, Christian},
  title = {Revisiting Asynchronous Fault Tolerant Computation with Optimal Resilience},
  booktitle = {{PODC} '20: {ACM} Symposium on Principles of Distributed Computing,
                    Virtual Event, Italy, August 3-7, 2020},
  pages = {139--148},
  publisher = {{ACM}},
  year = {2020},
  url = {https://doi.org/10.1145/3382734.3405722},
  doi = {10.1145/3382734.3405722},
  timestamp = {Tue, 04 Aug 2020 16:14:27 +0200},
  biburl = {https://dblp.org/rec/conf/podc/AbrahamDS20.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}