Cryptology ePrint Archive: Report 2021/118

High-Threshold AVSS with Optimal Communication Complexity

Nicolas Alhaddad and Mayank Varia and Haibin Zhang

Abstract: Asynchronous verifiable secret sharing (AVSS) protocols protect a secret that is distributed among N parties. Dual-threshold AVSS protocols guarantee consensus in the presence of T Byzantine failures and privacy if fewer than P parties attempt to reconstruct the secret. In this work, we construct a dual-threshold AVSS protocol that is optimal along several dimensions. First, it is a high-threshold AVSS scheme, meaning that it is a dual-threshold AVSS with optimal parameters T < N/3 and P < N - T. Second, it has O(N^2) message complexity, and for large secrets it achieves the optimal O(N) communication overhead, without the need for a public key infrastructure or trusted setup. While these properties have been achieved individually before, to our knowledge this is the first protocol that is achieves all of the above simultaneously. The core component of our construction is a high-threshold AVSS scheme for small secrets based on polynomial commitments that achieves O(N^2 log(N)) communication overhead, as compared to prior schemes that require O(N^3) overhead with T<N/4 Byzantine failures or O(N^4) overhead for the recent high-threshold protocol of Kokoris-Kogias et al (CCS 2020). Using standard amortization techniques based on erasure coding, we can reduce the communication complexity to O(N*|F|) for a large secret F.

Category / Keywords: cryptographic protocols / secret sharing, threshold cryptography, distributed cryptography, broadcast

Original Publication (in the same form): Financial Cryptography and Data Security 2021

Date: received 1 Feb 2021, last revised 9 Feb 2021

Contact author: nhaddad at bu edu

Available format(s): PDF | BibTeX Citation

Version: 20210209:153939 (All versions of this report)

Short URL: ia.cr/2021/118