publications

2025

2025

1. Nearly Quadratic Asynchronous Distributed Key Generation

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

   2025

   ePrint Bib

   @misc{cryptoeprint:2025/006,
     author = {Abraham, Ittai and Bacho, Renas and Loss, Julian and Stern, Gilad},
     title = {Nearly Quadratic Asynchronous Distributed Key Generation},
     howpublished = {Cryptology {ePrint} Archive, Paper 2025/006},
     year = {2025},
   }

2. 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, Hotel Las Brisas Huatulco, Huatulco, Mexico, 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},
   }

2024

2024

1. 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},
   }

2. 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},
   }

3. 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},
   }

4. 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

2023

1. 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},
   }

2. 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},
   }

3. 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},
   }

4. 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

2022

1. 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},
   }

2. 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

2021

1. 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},
   }

2. 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},
   }

3. 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

2020

1. 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},
   }