Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications

Nicolas Alhaddad; Mayank Varia; Ziling Yang

doi:10.62056/a0qj5w7sf

Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications

Authors

Nicolas Alhaddad, Mayank Varia, Ziling Yang

Nicolas Alhaddad

Boston University, United States
nhaddad at bu dot edu

Mayank Varia

Boston University, United States
varia at bu dot edu

Ziling Yang

University of Illinois Urbana-Champaign, United States
zilingy2 at illinois dot edu

Abstract

Asynchronous complete secret sharing (ACSS) is a foundational primitive in the design of distributed algorithms and cryptosystems that require confidentiality. ACSS permits a dealer to distribute a secret to a collection of N servers so that everyone holds shares of a polynomial containing the dealer's secret.

This work contributes a new ACSS protocol, called Haven++, that uses packing and batching to make asymptotic and concrete advances in the design and application of ACSS for large secrets. Haven++ allows the dealer to pack multiple secrets in a single sharing phase, and to reconstruct either one or all of them later. For even larger secrets, we contribute a batching technique to amortize the cost of proof generation and verification across multiple invocations of our protocol.

The result is an asymptotic improvement in the worst-case amortized communication and computation complexity, both for ACSS itself and for its application to asynchronous distributed key generation. Our ADKG based on Haven++ achieves, for the first time, an optimal worst case amortized communication complexity of κN without a trusted setup. To show the practicality of Haven++, we implement it and find that it outperforms the work of Yurek et al. (NDSS 2022) by more than an order of magnitude when there are malicious, faulty parties.

References

[AAPP24]

Ittai Abraham, Gilad Asharov, Shravani Patil, and Arpita Patra. Perfect Asynchronous MPC with Linear Communication Overhead. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, pages 280–309, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-58740-5_10

Google Scholar ePrint

[ADD⁺22a]

Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 399–417, New York, NY, USA. 2022. Association for Computing Machinery. DOI: 10.1145/3519270.3538475

Google Scholar ePrint

[ADD⁺22b]

Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. Brief Announcement: Asynchronous Verifiable Information Dispersal with Near-Optimal Communication. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 418–420, New York, NY, USA. 2022. Association for Computing Machinery. DOI: 10.1145/3519270.3538476

Google Scholar ePrint

[ADVZ21]

Nicolas Alhaddad, Sisi Duan, Mayank Varia, and Haibin Zhang. Succinct Erasure Coding Proof Systems. https://eprint.iacr.org/2021/1500. Cryptology ePrint Archive, Paper 2021/1500. 2021.

Google Scholar ePrint

[AJM⁺23a]

Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, and Gilad Stern. Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing and Distributed Key Generation. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, pages 39–70, Cham. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-38557-5

Google Scholar ePrint

[AJM⁺23b]

Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu. Reaching consensus for asynchronous distributed key generation. Distributed Computing, 36(3):219-252, September 2023. DOI: 10.1007/s00446-022-00436-8

Google Scholar ePrint

[AMS19]

Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically Optimal Validated Asynchronous Byzantine Agreement. In Peter Robinson and Faith Ellen, editors, 38th ACM PODC, pages 337–346. 2019. ACM. DOI: 10.1145/3293611.3331612

Google Scholar ePrint

[AVZ21]

Nicolas Alhaddad, Mayank Varia, and Haibin Zhang. High-Threshold AVSS with Optimal Communication Complexity. In Nikita Borisov and Claudia Díaz, editors, FC 2021, Part II, volume 12675 of LNCS, pages 479–498. March 2021. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-64331-0_25

Google Scholar ePrint

[BBB⁺18]

Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. In 2018 IEEE Symposium on Security and Privacy, pages 315–334. May 2018. IEEE Computer Society Press. DOI: 10.1109/SP.2018.00020

Google Scholar ePrint

[BCC⁺16]

Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 327–357. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49896-5_12

Google Scholar ePrint

[BCG93]

Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In 25th ACM STOC, pages 52–61. May 1993. ACM Press. DOI: 10.1145/167088.167109

Google Scholar ePrint

[BDK13]

Michael Backes, Amit Datta, and Aniket Kate. Asynchronous Computational VSS with Reduced Communication Complexity. In Ed Dawson, editor, CT-RSA 2013, volume 7779 of LNCS, pages 259–276. 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-36095-4_17

Google Scholar ePrint

[Bea91]

Donald Beaver. Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, 4:75–122, 1991. DOI: https://doi.org/10.1007/BF00196771

Google Scholar ePrint

[BFS20]

Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK Compilers. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 677–706. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45721-1_24

Google Scholar ePrint

[BG18]

Jonathan Bootle and Jens Groth. Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part II, volume 10770 of LNCS, pages 561–588. March 2018. Springer, Cham. DOI: 10.1007/978-3-319-76581-5_19

Google Scholar ePrint

[BGdMM05]

Lucas Ballard, Matthew Green, Breno de Medeiros, and Fabian Monrose. Correlation-Resistant Storage via Keyword-Searchable Encryption. https://eprint.iacr.org/2005/417. Cryptology ePrint Archive, Paper 2005/417. 2005.

Google Scholar ePrint

[Bol03]

Alexandra Boldyreva. Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme. In Yvo Desmedt, editor, PKC 2003, volume 2567 of LNCS, pages 31–46. January 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-36288-6_3

Google Scholar ePrint

[Bra87]

Gabriel Bracha. Asynchronous Byzantine Agreement Protocols. Inf. Comput., 75(2):130–143, 1987. DOI: https://doi.org/10.1016/0890-5401(87)90054-X

Google Scholar ePrint

[BTH07]

Zuzana Beerliová-Trubíniová and Martin Hirt. Simple and Efficient Perfectly-Secure Asynchronous MPC. In Kaoru Kurosawa, editor, Advances in Cryptology – ASIACRYPT 2007, pages 376–392, Berlin, Heidelberg. 2007. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-76900-2_23

Google Scholar ePrint

[Can96]

Ran Canetti. Studies in secure multiparty computation and applications. PhD thesis, Citeseer, 1996.

Google Scholar ePrint

[CF13]

Dario Catalano and Dario Fiore. Vector Commitments and Their Applications. In Kaoru Kurosawa and Goichiro Hanaoka, editors, PKC 2013, volume 7778 of LNCS, pages 55–72. 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-36362-7_5

Google Scholar ePrint

[CFS17]

Alessandro Chiesa, Michael A. Forbes, and Nicholas Spooner. A Zero Knowledge Sumcheck and its Applications. Electron. Colloquium Comput. Complex., 24:57, 2017.

Google Scholar ePrint

[CKLS02]

Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, and Reto Strobl. Asynchronous Verifiable Secret Sharing and Proactive Cryptosystems. In Vijayalakshmi Atluri, editor, ACM CCS 2002, pages 88–97. November 2002. ACM Press. DOI: 10.1145/586110.586124

Google Scholar ePrint

[CKPS01]

Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and Efficient Asynchronous Broadcast Protocols. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 524–541. August 2001. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-44647-8_31

Google Scholar ePrint

[CKS05]

Christian Cachin, Klaus Kursawe, and Victor Shoup. Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography. Journal of Cryptology, 18(3):219–246, July 2005. DOI: 10.1007/s00145-005-0318-0

Google Scholar ePrint

[CR93a]

Ran Canetti and Tal Rabin. Fast asynchronous Byzantine agreement with optimal resilience. In 25th ACM STOC, pages 42–51. May 1993. ACM Press. DOI: 10.1145/167088.167105

Google Scholar ePrint

[CR93b]

Ran Canetti and Tal Rabin. Fast asynchronous Byzantine agreement with optimal resilience. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 42–51, New York, NY, USA. 1993. Association for Computing Machinery. DOI: 10.1145/167088.167105

Google Scholar ePrint

[CT05]

Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. In SRDS, pages 191–201. 2005. IEEE. DOI: 10.1109/RELDIS.2005.9

Google Scholar ePrint

[DN07]

Ivan Damgård and Jesper Buus Nielsen. Scalable and Unconditionally Secure Multiparty Computation. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 572–590. August 2007. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-74143-5_32

Google Scholar ePrint

[DWZ23]

Sisi Duan, Xin Wang, and Haibin Zhang. FIN: Practical Signature-Free Asynchronous Common Subset in Constant Time. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 815–829, New York, NY, USA. 2023. Association for Computing Machinery. DOI: 10.1145/3576915.3616633

Google Scholar ePrint

[DXKKR23]

Sourav Das, Zhuolun Xiang, Lefteris Kokoris-Kogias, and Ling Ren. Practical Asynchronous High-threshold Distributed Key Generation and Distributed Polynomial Sampling. In Joseph A. Calandrino and Carmela Troncoso, editors, USENIX Security 2023, pages 5359–5376. August 2023. USENIX Association.

Google Scholar ePrint

[DXR21]

Sourav Das, Zhuolun Xiang, and Ling Ren. Asynchronous Data Dissemination and its Applications. In Giovanni Vigna and Elaine Shi, editors, ACM CCS 2021, pages 2705–2721. November 2021. ACM Press. DOI: 10.1145/3460120.3484808

Google Scholar ePrint

[GJKR07]

Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. Journal of Cryptology, 20(1):51–83, January 2007. DOI: 10.1007/s00145-006-0347-3

Google Scholar ePrint

[GS24]

Jens Groth and Victor Shoup. Fast Batched Asynchronous Distributed Key Generation. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, pages 370–400, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-58740-5_13

Google Scholar ePrint

[HMW18]

Timo Hanke, Mahnush Movahedi, and Dominic Williams. DFINITY Technology Overview Series, Consensus System. CoRR, abs/1805.04548, 2018.

Google Scholar ePrint

[JLS24]

Xiaoyu Ji, Junru Li, and Yifan Song. Linear-Communication Asynchronous Complete Secret Sharing with Optimal Resilience. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, pages 418–453, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-68397-8_13

Google Scholar ePrint

[KHG12]

Aniket Kate, Yizhou Huang, and Ian Goldberg. Distributed Key Generation in the Wild. Cryptology ePrint Archive, Report 2012/377. 2012.

Google Scholar ePrint

[KMS20]

Eleftherios Kokoris-Kogias, Dahlia Malkhi, and Alexander Spiegelman. Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020, pages 1751–1767. November 2020. ACM Press. DOI: 10.1145/3372297.3423364

Google Scholar ePrint

[KZG10]

Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 177–194. December 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-17373-8_11

Google Scholar ePrint

[LY10]

Benoît Libert and Moti Yung. Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs. In Daniele Micciancio, editor, TCC 2010, volume 5978 of LNCS, pages 499–517. February 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-11799-2_30

Google Scholar ePrint

[MS77]

Florence Jessie MacWilliams and Neil James Alexander Sloane. The theory of error-correcting codes, volume 16. Elsevier 1977.

Google Scholar ePrint

[SS24]

Victor Shoup and Nigel P. Smart. Lightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience. Journal of Cryptology, 37(3):27, 2024. DOI: 10.1007/s00145-024-09505-6

Google Scholar ePrint

[TCZ⁺20]

Alin Tomescu, Robert Chen, Yiming Zheng, Ittai Abraham, Benny Pinkas, Guy Golan Gueta, and Srinivas Devadas. Towards Scalable Threshold Cryptosystems. In 2020 IEEE Symposium on Security and Privacy (SP), pages 877-893. 2020. DOI: 10.1109/SP40000.2020.00059

Google Scholar ePrint

[YLF⁺22]

Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, and Andrew Miller. hbACSS: How to Robustly Share Many Secrets. In NDSS 2022, San Diego, CA, USA. April 24–28 2022. The Internet Society. DOI: 10.14722/ndss.2022.23120

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a0qj5w7sf

History

Submitted: 2024-07-09
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Nicolas Alhaddad, Mayank Varia, and Ziling Yang, Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a0qj5w7sf.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-4-3,
    author = "Alhaddad, Nicolas and Varia, Mayank and Yang, Ziling",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/a0qj5w7sf"
}

TY - JOUR
AU - Alhaddad, Nicolas
AU - Varia, Mayank
AU - Yang, Ziling
PY  - 2025
TI  - Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 4
DO  - 10.62056/a0qj5w7sf
UR  - https://doi.org/10.62056/a0qj5w7sf
AB  - <p>Asynchronous complete secret sharing (ACSS) is a foundational primitive in the design of distributed algorithms and cryptosystems that require confidentiality. ACSS permits a dealer to distribute a secret to a collection of N servers so that everyone holds shares of a polynomial containing the dealer's secret.</p><p>This work contributes a new ACSS protocol, called Haven++, that uses packing and batching to make asymptotic and concrete advances in the design and application of ACSS for large secrets. Haven++ allows the dealer to pack multiple secrets in a single sharing phase, and to reconstruct either one or all of them later. For even larger secrets, we contribute a batching technique to amortize the cost of proof generation and verification across multiple invocations of our protocol.</p><p>The result is an asymptotic improvement in the worst-case amortized communication and computation complexity, both for ACSS itself and for its application to asynchronous distributed key generation. Our ADKG based on Haven++ achieves, for the first time, an optimal worst case amortized communication complexity of κN without a trusted setup. To show the practicality of Haven++, we implement it and find that it outperforms the work of Yurek et al. (NDSS 2022) by more than an order of magnitude when there are malicious, faulty parties. </p>
ER  -

Nicolas Alhaddad, Mayank Varia, and Ziling Yang, Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a0qj5w7sf.