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
[ Cryptology ePrint archive ]