Graph-based Asynchrony with Quasilinear Complexity for Any Linear Verifiable Secret Sharing Scheme

Read full text Summarise with VIRAT
Authors: Hugo Delavenne, Lola-Baie Mallordy
Cited by: 0
References: 24

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Verifiable Secret Sharing (VSS) schemes usually consider synchronous communication, which cannot always be the case on real networks where packets can be lost or parties arbitrarily delayed. Allowing asynchrony adds a large overhead complexity cost: the dealer and communication complexity is in O(n²log(n)) in state of the art n-parties Asynchronous VSS (AVSS) schemes [ABD+25], whereas there are synchronous schemes with only linear communications. To ensure that all honest parties agree on the same secret and are ready for reconstruction, AVSS schemes essentially perform a protocol similar to Bracha’s broadcast [Bra87]. While this immediately bounds the overall communication complexity of the protocol to be at least in O(n²), this method enables to reach the maximum threshold of malicious parties of t=n/3. However, a smaller threshold t may be sufficient for some use cases, and one may want to take advantage of this. We consider a statistical scheme, meaning that the correctness and termination properties are only guaranteed with good probability. We propose a new method to transform any linear VSS scheme into a statistical AVSS. We build a statistical AVSS protocol Bonneval-on-Arc where each party only communicates with d neighbours, a situation that we model by a d-regular graph. We obtain quasilinear communication complexity for the dealer, and sublinear complexity for each party, and a corruption threshold t < n/(d + 2) as a tradeoff.

Fields of Study & Subjects

Cryptography and Data Security Coding theory and cryptography Advanced Authentication Protocols Security

Publication details

Journal / source
HAL
Publication date
13 March 2026
Language
EN
Document type
Preprint