PaperlayerView exact revision on arXiv

Source-linked AI summary

Asynchronous Verifiable and Complete Secret Sharing: From Design Patterns to System-Level Trade-offs

Joachim Bruneau-Queyreix, Martin Zivojinovic, Leo Mendiboure, Tom Claudel, Laurent Réveillère

arXiv:2610.37234v1cs.CR

TL;DR

Practical costs of modern asynchronous verifiable and complete secret sharing remain difficult to compare across protocols and workloads. The paper analyzes seven representative designs in a common framework, finding that architectural choices shape performance trade-offs and no protocol dominates across workloads.

  • Problem

    Modern one-shot AVSS and ACSS protocols have strong theoretical guarantees, but their concrete costs depend on interacting mechanisms and are poorly understood, leaving practitioners without a principled basis for selection under system constraints.

    Source: §I · p. 1

  • Method

    The paper presents a design-space analysis of modern one-shot AVSS/ACSS and evaluates representative protocols in a common codebase under optimistic and faulty-dealer stress conditions.

    Source: §I · p. 1

  • Results

    No single protocol dominates across workloads; measured trade-offs reflect communication, verification, recovery, batching or packing, and optimistic versus robust-first execution choices.

    Source: §VIII · p. 15

  • Takeaways & Limitations

    The findings offer practical guidance for choosing among designs according to their workload and security trade-offs.

    Source: §VIII · p. 15

    The faulty-dealer tests are controlled stress scenarios, and Grid’5000 does not reproduce geo-distributed WAN or heterogeneous deployments; results are comparative under the stated workloads and placement policy.

    Source: A. Threats to Validity · p. 13

Abstract

from arXiv · show

Modern secret sharing protocols promise robust secret sharing in fully asynchronous Byzantine systems, but their practical costs remain difficult to compare across papers, assumptions, and workloads. The difficulty is not merely experimental: protocols with similar asymptotic guarantees often place very different work on the critical path through their choices of dissemination, verification, batching, and recovery. This paper turns that fragmented research landscape into a corpus-backed designspace analysis and systems evaluation of asynchronous verifiable and complete secret sharing. We derive a design sieve, select seven representative protocols, and implement them in a common Rust framework. In our experiments on the Grid'5000 platform, we evaluate honest-dealer and faulty-dealer stress executions using latency, throughput, message count, bandwidth, and aggregate CPU-time. The results show that message complexity alone poorly predicts latency, that optimistic paths can be dominated by recovery cost, and that batching or packing helps only when verification stays off the critical path. These findings turn protocol-by-protocol comparisons into design-to-cost guidance for choosing, implementing, and extending asynchronous verifiable and complete sharing protocols.

I. INTRODUCTION

Asynchronous verifiable and complete secret sharing supports higher-level distributed applications, but the practical costs of modern protocols remain difficult to compare under concrete system constraints. This paper analyzes seven representative designs in a common framework and connects their architectural choices to measured performance and cost trade-offs.

I. INTRODUCTION

  • VSS supports higher-level protocols such as secure multiparty computation, distributed key generation, and randomness beacons, where performance and scalability matter because sharing lies on the application critical path.VSS adds verification data so parties can check that shares are consistent with one underlying secret and detect dealer misbehavior.Source: §I · p. 1
  • Modern asynchronous verifiable and complete secret sharing protocols have strong theoretical guarantees, but their concrete costs depend on interacting design choices and remain poorly understood.Practitioners lack a principled basis for choosing protocols under latency, throughput, bandwidth, CPU, setup, and fault-assumption constraints.Source: §I · p. 1
  • The paper decomposes protocols into design dimensions—including dissemination, verification, fault handling, and batching—to explain how similar asymptotic guarantees can yield different measured costs.The dimensions affect latency, throughput, CPU, bandwidth, message count, and scalability.Source: §I · p. 1
  • The authors analyze seven representative protocols in a common Rust framework under honest-dealer and faulty-dealer stress, measuring latency, throughput, messages, bandwidth, and aggregate CPU-time.The framework supports controlled comparisons of recurring patterns rather than implementation artifacts.Source: §I · pp. 1–2
  • Optimistic protocols perform well without faults but can degrade sharply under faulty-dealer stress; batch-oriented protocols scale efficiently but add latency for small workloads.High-resilience designs provide stronger security guarantees at substantial communication and cryptographic cost.Source: §I · p. 2
  • The paper builds a curated corpus and design dimensions for understanding asynchronous secret-sharing costs, then maps seven representative protocols across assumptions, guarantees, adversaries, completion mechanisms, and asymptotic costs.The corpus-backed analysis also identifies directions for research on recovery, batching, dissemination, verification, and hardware-assisted sharing.Source: §I · p. 2

II. BACKGROUND AND RELATED WORK

The paper fixes a common model and vocabulary for comparing one-shot sharing protocols, then positions its study against prior evaluations and taxonomies. It focuses on asynchronous sharing with Byzantine faults and sharing completion, a gap not addressed by existing normalized evaluations.

A. System model and notation

  • The model considers one-shot sharing among parties and a dealer over authenticated channels in a fully asynchronous network, with Byzantine parties able to collude, equivocate, omit messages, or act as dealer.The benchmark isolates the sharing phase and invokes reconstruction only when needed to explain validity or recovery.Source: A. System model and notation · p. 2
  • The paper distinguishes correctness, agreement, privacy, termination, and sharing completion, defining completion as propagation of an accepted usable output to all honest parties for the same sharing object.Sharing completion is weaker than a uniform ACSS functionality but stronger than ordinary VSS verifiability.Source: A. System model and notation · p. 2

B. Related work

  • Prior AVSS/ACSS evaluations use protocol-specific codebases, platforms, parameters, and metrics, while existing systems benchmarks and surveys do not connect modern sharing mechanisms to common faulty-dealer measurements.The specific gap is attributing AVSS/ACSS costs to design choices under normalized implementation and workload conditions.Source: B. Related work · pp. 2–3

III. ONE-SHOT AVSS/ACSS DESIGN SPACE AND PROTOCOL SELECTION

  • The study defines its scope, constructs a design-space sieve for recent one-shot asynchronous sharing protocols, and selects representative protocols for theoretical analysis and empirical measurement.The sieve organizes mechanisms such as communication, verification, recovery, and amortization.Source: §III · p. 3

A. Scope and terminology

The study compares one-shot sharing protocols that provide verifiable, mutually consistent outputs and completion, while retaining the terminology used by each original paper. It filters a growing literature into a representative set and uses a five-part sieve to organize the mechanisms shaping performance.

A. Scope and terminology

  • The study compares one-shot sharing in which a dealer distributes one or more secrets and honest parties obtain verifiable, mutually consistent shares, invoking recovery only to complete that execution.ACSS names the guarantee that once one honest party outputs, all honest parties eventually obtain compatible shares; some papers provide it while retaining the AVSS name.Source: A. Scope and terminology · p. 3

B. Research landscape and filtering

  • The literature search produced a corpus of 193 VSS-related papers, of which 35 address or contain an in-scope AVSS/ACSS interface; nearly three quarters of those appeared since 2022.The authors use recurring design dimensions to select representative protocols rather than implement the entire corpus.Source: B. Research landscape and filtering · p. 3

C. A design-space sieve

  • The sieve records each protocol’s security envelope and examines how its communication model affects evidence availability, message volume, synchronization, and scalability.Communication ranges from direct secure distribution and reliable-broadcast transcripts to AVID dispersal and peer exchange over algebraic sharing objects.Source: C. A design-space sieve · pp. 3–4
  • Verification choices—including hashes, commitments, encryption, and zero-knowledge proofs—also encode setup assumptions and can shift costs toward networking, CPU, or proof generation and verification.The security envelope includes the corruption model and privacy threshold.Source: C. A design-space sieve · p. 4
  • Recovery strategies range from complaint-driven repair and transcript broadcast to AVID disclosure, peer-data interpolation, and abort-and-retry, determining whether faulty-dealer executions complete or merely detect invalid sharing.Recovery is identified as the main explanation for the gap between honest-dealer and faulty-dealer stress executions.Source: C. A design-space sieve · p. 4
  • Protocols batch independent secrets, pack several secrets into one algebraic object, or use information dispersal; these choices determine when throughput improves and when batching adds latency.The sieve distinguishes cryptographic batch amortization, packing, vectorized independent polynomials, and single-secret designs.Source: C. A design-space sieve · p. 4
  • Optimistic protocols defer expensive robustness work to complaints or recovery, while robust-first designs pay more in every execution; intermediate designs include propagation evidence or recovery metadata upfront.This execution-model distinction matches the paper’s honest and faulty-dealer stress experiments.Source: C. A design-space sieve · p. 4

D. Selection criteria

The authors select protocols for asynchronous one-shot semantics, recency, implementability, and design diversity, then treat them as design points rather than an exhaustive survey. Their analysis and evaluation questions focus on how these choices affect costs and fault handling.

D. Selection criteria

  • Benchmark inclusion requires one-shot asynchronous AVSS/ACSS semantics under Byzantine faults, a modern construction, sufficient specification for faithful implementation, and design diversity rather than exhaustive coverage.For broader services, only the qualifying one-shot sharing component is evaluated.Source: D. Selection criteria · p. 4

E. Representative design points

  • The seven selected protocols—HAVEN, HBACSS, SIMPLAVSS, BINGO, GOSSAMER, LIGHTAVSS, and HONEYB—are representative design points, not an exhaustive survey of the corpus.They span hash-based optimistic AVSS, batch-oriented AVID-based ACSS, transcript-based public verifiability, adaptive packed sharing, lightweight batched ACSS, and high-threshold designs.Source: E. Representative design points · p. 4
  • The evaluation asks how fault stress changes performance, which communication models scale with party count, when verification bottlenecks arise, when batching or packing amortizes costs, and which recovery strategies preserve progress.The questions connect the design-space analysis to the empirical evaluation.Source: E. Representative design points · p. 5

IV. SELECTED ONE-SHOT SHARING PROTOCOLS

  • The protocol analysis separates each design’s research contribution, pattern, operational sharing sketch, and performance implication, using the sieve to compare security envelopes and asymptotic costs.The authors position unimplemented related constructions as refinements of already covered design points or as differing in assumptions.Source: §IV · p. 5, E. Representative design points · p. 5

A. HAVEN - High-Threshold AVSS

HAVEN combines high-threshold privacy, optimal asynchronous Byzantine resilience, and no trusted setup, while HBACSS uses batching and AVID-style dissemination to make completion under faults predictable. Their costs reflect different priorities: HAVEN pays for robustness upfront, while HBACSS amortizes fixed overhead over large batches.

A. HAVEN - High-Threshold AVSS

  • HAVEN combines high-threshold privacy, optimal asynchronous Byzantine resilience, and no trusted setup with lower communication than earlier high-threshold AVSS designs.Its dual-threshold structure uses two-layer polynomial sharing, commitments, and reliable broadcast; large secrets can use symmetric encryption and information dispersal to reduce payload overhead.Source: A. HAVEN - High-Threshold AVSS · p. 5
  • HAVEN’s broadcast-heavy dissemination and verification of many related polynomial commitments produce high baseline cost but stable behavior across honest-dealer and faulty-dealer stress scenarios.The design pays for robustness upfront, with limited scalability compared with protocols that defer recovery work.Source: A. HAVEN - High-Threshold AVSS · p. 6

B. HBACSS - Batch-Oriented ACSS

  • HBACSS combines AVID-style dissemination with batch polynomial commitments to make ACSS completion under faults predictable rather than exceptional.In the implemented hbACSS0-style recovery path, recipients disclose disputed decryption keys and missing recipients retrieve, verify, and interpolate at least t + 1 valid payloads.Source: B. HBACSS - Batch-Oriented ACSS · p. 6
  • HBACSS’s fixed cryptographic and dispersal overhead is expensive for one secret but amortizes over large batches, with a small faulty-dealer gap in large-batch throughput.Fault stress triggers disclosure and interpolation instead of aborting, yielding higher single-secret latency.Source: B. HBACSS - Batch-Oriented ACSS · p. 6

C. BINGO - Adaptively Secure Packed AVSS

BINGO packs secrets in an adaptively secure bivariate sharing structure, HONEYB provides encrypted high-threshold complete sharing, and LIGHTAVSS keeps its honest-dealer path lightweight. Their performance implications differ: packing and batching can amortize costs, while recovery or proof work can remain expensive.

C. BINGO - Adaptively Secure Packed AVSS

  • BINGO supports adaptive security for packed AVSS/ACSS by amortizing several secrets within one bivariate sharing instance.It encodes t + 1 secrets and embeds recovery in its row/column structure rather than a separate complaint protocol.Source: C. BINGO - Adaptively Secure Packed AVSS · pp. 6–7
  • BINGO’s packing reduces communication per secret, but heavier cryptographic and peer-exchange costs leave proof verification and peer exchange as throughput limits under high concurrency.The design favors workloads matching its packing granularity and faults occurring.Source: C. BINGO - Adaptively Secure Packed AVSS · p. 7

D. HONEYB - Encrypted High-Threshold Complete Sharing

  • HONEYB provides an encrypted high-threshold complete-sharing layer with publicly checkable consistency evidence.Its one-shot path pays for high-threshold privacy and public verifiability through public-key operations, zero-knowledge proofs, and reliable broadcast.Source: D. HONEYB - Encrypted High-Threshold… · p. 7

E. LIGHTAVSS - Optimistic Hash-Based AVSS

  • LIGHTAVSS uses hash and symmetric primitives for lightweight batched sharing while isolating the cost of faults.Its basic beacon-based construction keeps the honest-dealer path lightweight and moves expensive work to complaints and recovery.Source: E. LIGHTAVSS - Optimistic Hash-Based… · p. 7
  • LIGHTAVSS has a pronounced gap between honest-dealer and faulty-dealer stress executions when recovery communication and synchronization are triggered.The happy path offers excellent latency and throughput, followed by a marked slowdown under faulty-dealer stress.Source: E. LIGHTAVSS - Optimistic Hash-Based… · p. 7

F. SIMPLAVSS - Transcript-Based Public Verifiability

SIMPLAVSS centers completion on a public transcript, while GOSSAMER uses original-evaluation propagation and bivariate degree checking to avoid homomorphic commitments. The evaluation’s faulty-dealer stress scenario deliberately exercises fault handling but is not a protocol-level worst case.

F. SIMPLAVSS - Transcript-Based Public Verifiability

  • SIMPLAVSS simplifies AVSS around publicly checkable transcripts and acknowledgment evidence, reducing interactive complaint complexity and making completion evidence externally auditable.The transcript carries commitments, acknowledgments, and batched openings for missing signers; multi-secret evaluation uses grouped independent polynomials, not packing or cryptographic batch amortization.Source: F. SIMPLAVSS - Transcript-Based Public… · p. 7
  • SIMPLAVSS’s transcript replaces interactive complaints with public evidence, while grouped messages amortize scheduling and transport overhead but leave transcript work and commitment verification per secret.The protocol favors simple, robust single-secret execution.Source: F. SIMPLAVSS - Transcript-Based Public… · p. 8

G. GOSSAMER - Lightweight Linear-Communication ACSS

  • GOSSAMER removes homomorphic commitments from linear-communication ACSS, using original-evaluation propagation and bivariate degree checking to preserve amortized linear communication for sufficiently large batches.Its higher fixed batch cost must be repaid for the O(κn) per-secret cost to appear once b ≥ O(n^2 log n).Source: G. GOSSAMER - Lightweight… · p. 8

V. EXPERIMENTAL ENVIRONMENT

  • The faulty-dealer stress scenario drives protocols away from complaint-free execution but does not exhaust Byzantine schedules, equivocation patterns, or adaptive corruptions.The test uses a Byzantine dealer that sends incorrect or missing shares to up to t −1 parties while additional faulty parties remain silent.Source: §V · p. 8

A. Implementation and framework

The shared Rust framework standardizes protocol interfaces, infrastructure, and measurements across physical machines. Experiments vary system size and batch size, and the reported comparisons show that faulty-dealer recovery costs can sharply widen execution gaps.

A. Implementation and framework

  • The approximately 13,700-line Rust framework implements protocols as independent modules over shared interfaces and infrastructure for controlled comparison.It uses shared network, serialization, placement, logging, and permitted common subprotocol implementations, and runs on multiple physical machines over real TCP connections.Source: A. Implementation and framework · p. 8

B. Experimental Setup

  • Experiments vary the number of parties from 10 to 100 and batch size from 1 to 50, with HAVEN and HONEYB evaluated only at batch size 1 because they lack native batching.SIMPLAVSS uses grouped independent polynomials rather than cryptographic amortization; the HBACSS and LIGHTAVSS implementations use specified variants of their recovery and beacon-based paths.Source: B. Experimental Setup · p. 9

VI. EVALUATIONS AND RESULTS

  • The evaluation compares optimistic and faulty-dealer stress executions using latency, throughput, messages, bandwidth, and aggregate CPU-time.For single-secret latency, 100 sequential sharing instances are averaged; peak throughput is the last stable point before saturation, or a measured maximum-throughput lower bound when no knee appears.Source: §VI · p. 9, B. Experimental Setup · p. 9, A. RQ1: Gap between optimistic and… · p. 9

A. RQ1: Gap between optimistic and faulty-dealer executions

  • At n = 100, LIGHTAVSS latency rises from 170 ms to 2.64 s under faulty-dealer stress, while SIMPLAVSS remains around 145 ms and 134 ms in the same scenarios.For B = 50 at n = 100, LIGHTAVSS rises from 1.65 s to 4.51 s, while GOSSAMER rises from 204 ms to 468 ms.Source: A. RQ1: Gap between optimistic and… · p. 9

B. RQ2: Dominating communications models for scalability

Across communication, verification, and batching, performance depends on work placed on the asynchronous critical path, not message counts alone. Batching and packing trade communication against latency and CPU cost, with outcomes shaped by verification and recovery.

B. RQ2: Dominating communications models for scalability

  • At n = 100, LIGHTAVSS, HBACSS, and GOSSAMER send about 57 k–58 k messages, yet LIGHTAVSS and GOSSAMER remain latency-competitive while HAVEN is slowest.In faulty-dealer stress, GOSSAMER sends about 37 MB and 70.5 k messages but stays below 0.5 s latency; vectorized SIMPLAVSS’s message savings do not fully carry over to multi-secret workloads.Source: B. RQ2: Dominating communications… · pp. 10–11

C. RQ3: Dominating cryptographic verification bottlenecks

  • Public-key-heavy, polynomial-commitment, and adaptive packed verification drive CPU costs, while hash-based verification and original-evaluation propagation are cheaper in the evaluated workloads.BINGO’s lower communication comes with high CPU-time; GOSSAMER keeps batched CPU-time low, while SIMPLAVSS’s grows as public transcript processing scales with independently shared secrets.Source: C. RQ3: Dominating cryptographic… · p. 11

D. RQ4: Batching and packing

  • At n = 60 and B = 50, GOSSAMER completes in about 95 ms with about 5.7 s aggregate CPU-time, while LIGHTAVSS, HBACSS, and vectorized SIMPLAVSS take about 0.93–1.22 s and 34–57 s.GOSSAMER minimizes critical-path computation and latency when bandwidth is sufficient, although it does not minimize bytes or messages.Source: D. RQ4: Batching and packing · p. 11
  • At n = 100 under faulty-dealer stress, BINGO uses about 14.4 MB and 43 k messages, while GOSSAMER uses about 37.2 MB and 70.5 k messages.GOSSAMER remains below 0.5 s latency and about 26.5 s CPU-time, versus BINGO near 1.95 s and 149 s.Source: D. RQ4: Batching and packing · p. 11
  • Transcript-based completion limits SIMPLAVSS’s single-secret fault penalty, whereas LIGHTAVSS’s optimistic path incurs the largest recovery penalty, especially for batches.GOSSAMER propagates original authenticated evaluations instead of using commitment-heavy repair; BINGO avoids LIGHTAVSS’s collapse but remains CPU-bound relative to GOSSAMER and SIMPLAVSS.Source: D. RQ4: Batching and packing · pp. 11–12

F. Peak-throughput saturation

At saturation, throughput depends more on critical-path work than raw message count. GOSSAMER sustains high batched output rates by keeping CPU-time low, while communication savings or good isolated-execution performance do not guarantee a higher throughput knee.

F. Peak-throughput saturation

  • For B = 50, GOSSAMER sustains around one thousand secrets per second with sub-200 ms average latency at the knee in both honest-dealer and faulty-dealer peak experiments.Its batched path keeps CPU-time low and avoids commitment-heavy recovery, at a communication cost that is especially visible under faulty-dealer stress.Source: Figure 9 · p. 12, Figure 10 · p. 12, F. Peak-throughput saturation · p. 13
  • For B = 1, SIMPLAVSS, LIGHTAVSS, and GOSSAMER sustain similar honest-dealer output rates, while LIGHTAVSS loses most single-secret throughput under faulty-dealer stress.SIMPLAVSS remains stable and GOSSAMER keeps comparable throughput while spending more messages and bytes; LIGHTAVSS’s complaint and recovery work moves onto the critical path.Source: F. Peak-throughput saturation · p. 12, Figure 9 · p. 12, Figure 10 · p. 12
  • In the B = t + 1 packed setting, BINGO reduces network cost relative to all-to-all batched designs, but its packed and adaptive-verification machinery limits peak throughput.GOSSAMER sustains a higher knee by keeping CPU-time low while paying more messages and bytes.Source: Figure 11 · p. 12, F. Peak-throughput saturation · p. 13

G. Synthesis

The evaluation links protocol design choices to cost trade-offs rather than a universal ranking. Its implications are bounded by implementation and workload scope, and practitioners are advised to filter by required security assumptions before choosing for a deployment bottleneck.

G. Synthesis

  • Optimistic execution, transcript completion, batch recovery, original-evaluation propagation, and packed bivariate sharing explain distinct performance trade-offs across the evaluated protocols.Protocol choice is multi-objective, depending on latency, CPU-time, bandwidth, fault recovery, or adaptive-security requirements.Source: G. Synthesis · p. 13

A. Threats to Validity

  • The common framework controls several implementation factors but cannot eliminate bias; selected protocols are representative design points, not an exhaustive corpus implementation.Conclusions apply primarily to the evaluated mechanisms and one-shot sharing interfaces.Source: A. Threats to Validity · p. 13
  • Faulty-dealer stress is controlled rather than exhaustive, and Grid’5000’s homogeneous, low-latency environment does not reproduce WAN or heterogeneous deployments.The reported averages and peak-throughput knees are comparative measurements under stated workloads and placement, not universal deployment predictions.Source: A. Threats to Validity · p. 13

B. Implications for Practitioners

  • Practitioners should first filter protocols by adversary, privacy, setup, and trust assumptions, then select according to the deployment bottleneck.The guidance distinguishes fault-free from fault-prone execution, isolated secrets from bursts, and required high-threshold privacy, public verifiability, or adaptive security.Source: B. Implications for Practitioners · pp. 13–14

C. Future Research Directions

The paper identifies research directions around critical-path recovery, adaptive batching, scalable dissemination, verification primitives, and hardware assistance. Its conclusion ties these directions to the observed trade-offs among communication, verification, recovery, and execution paths.

C. Future Research Directions

  • Recovery research should expose cheap, locally checkable evidence on the critical path and defer heavier repair or audit work where possible.The open question is the minimum evidence needed for completion, agreement, and later reconstructability under asynchrony.Source: C. Future Research Directions · p. 14
  • Future protocols should treat batch size as a systems parameter and explore adaptive batching, lightweight verification for packed encodings, and interfaces spanning single secrets and batches.The passage identifies bursty MPC, DKG, and randomness-generation workloads as settings where these designs could be useful.Source: C. Future Research Directions · p. 14
  • Scalable dissemination must reduce all-to-all pressure while preserving asynchronous completion, verifiability, recovery semantics, and the corruption threshold.The paper cautions that existing communication techniques are not a mechanical substitute for reliable broadcast or secure message distribution.Source: C. Future Research Directions · p. 14
  • AVSS- and ACSS-oriented commitment interfaces should support many evaluations, batched recipient checks, recovery openings, and cheap aggregation across concurrent instances.The interface should make explicit which operations lie on dealer, recipient-verification, and recovery paths.Source: C. Future Research Directions · pp. 14–15
  • Hybrid sharing could use hardware assistance on the common path while retaining a cryptographic recovery path for compromise, side channels, rollback, or attestation failure.The passage stresses that TEEs change the threat model rather than merely improving performance.Source: C. Future Research Directions · p. 15

VIII. CONCLUSION

  • Across seven representative designs, performance and cost trade-offs track architectural choices, and no single protocol dominates across workloads.Batching or packing improves scalability only when verification and recovery work amortize cleanly.Source: §VIII · p. 15

Related papers

Loading 2610.37234v1…