Paper 2021/118

High-Threshold AVSS with Optimal Communication Complexity

Nicolas Alhaddad, Mayank Varia, and Haibin Zhang


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Financial Cryptography and Data Security 2021
secret sharingthreshold cryptographydistributed cryptographybroadcast
Contact author(s)
nhaddad @ bu edu
2021-02-09: last of 2 revisions
2021-02-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Alhaddad and Mayank Varia and Haibin Zhang},
      title = {High-Threshold AVSS with Optimal Communication Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2021/118},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.