Brief Note: Asynchronous Verifiable Secret Sharing with Optimal Resilience and Linear Amortized Overhead

In this work we present hbAVSS, the Honey Badger of Asynchronous Verifiable Secret Sharing (AVSS) protocols - an AVSS protocol that guarantees linear amortized communication overhead even in the worst case. The best prior work can achieve linear overhead only at a suboptimal resilience level (t<n/4) or by relying on optimism (falling back to quadratic overhead in case of network asynchrony or Byzantine faults). Our protocol therefore closes this gap, showing that linear communication overhead is possible without these compromises. The main idea behind our protocol is what we call the encrypt-and-disperse paradigm: by first applying ordinary public key encryption to the secret shares, we can make use of highly efficient (but not confidentiality preserving) information dispersal primitives. We prove our protocol is secure under a static computationally bounded Byzantine adversary model.


I. INTRODUCTION
In a verifiable secret sharing (VSS) protocol, a dealer shares a secret among a set of n parties, such that t + 1 honest parties can reconstruct the secret. VSS forms the basis for fault tolerant file storage [5], [9], shared databases [2], and many other applications. It is also an essential component of secure multiparty computation (MPC) protocols, used both for generating random preprocessing elements and for accepting secret-shared inputs from untrusted clients.
The verifiability property means that if any party gets their shares, then every correct party also receives a valid share. This is essential when VSS is used as input to MPC, since parties need to assume the shares will be available in order to make irrevocable actions (such as revealing intermediate outputs of a computation). The challenge is that a faulty dealer may provide invalid data to some but not all of the parties. The main idea behind nearly all VSS protocols, starting from Feldman et al., [8], is to broadcast a polynomial commitment, enabling parties to individually validate their shares.
In the case of synchronous VSS, we can simply wait to hear a confirmation from all n parties, or else abort. The asynchronous VSS case is more difficult since we must proceed after hearing from only n − f of the parties, where f is the number of parties that undergo a Byzantine fault. Since crashed nodes are indistinguishable from slow nodes, it could be that f of the ones we waited for are corrupted, hence only n − 2 f correct parties received valid shares.
In order to cope with asynchrony, AVSS protocols typically distribute shares with additional redundancy, such that parties  [2] t < n/3 O(N) O(N 2 ) eAVSS [1] t < n/3 O(N 2 ) AVSS [4] t < n/3 O(N 3 ) Sh [6] t < n /4 O(N) who received invalid shares can recover their shares through interaction with the others. This recovery process either results in extra communication overhead [4], or else relies on loosened resilience guarantees [6].
Improvements to AVSS have made use of concise polynomial commitments based on pairing cryptography [1]. Most notably, in recent work, Basu et al. [2] present an optimistic AVSS protocol that achieves linear communication overhead in the typical case, but in the presence of Byzantine faults or network asynchrony may fall back to quadratic overhead. The goal of this paper is to present a protocol that provides linear guarantees even in the worst case.
Overview of our solution. The main idea behind our approach is a technique we call encrypt-then-disperse, inspired by a related application in HoneyBadgerBFT [12]. The secret share encoding and polynomial commitments are as usual. However, before transmitting, the secret shares are first encrypted using public key encryption. Next the encrypted payload is dispersed using an information dispersal routine, which can guarantee robustness and efficiency since it does not have to provide secrecy.
The use of information dispersal guarantees that every honest node receives some data, even in the asynchronous setting. If it turns out to be invalid, then it can be used as evidence to implicate the leader. Once the dealer is determined to be faulty, we enter a share recovery phase, which ensures every correct party receives their share. The share recovery phase can be very efficient too, since it does not need to ensure confidentiality at all, since it can only be initiated once the dealer is determined to be faulty. A summary comparison of our results to related work is given in Table I.

II. PRELIMINARIES A. Asynchronous Network Model
Throughout this paper we assume the standard asynchronous network model. We assume a fixed set of n communicating parties P 1 , ..., P n , as well as a dealer D. We consider a static Byzantine corruption model. The dealer and up to f < n/3 of the parties may be corrupted, in which case they are controlled entirely by the adversary. The parties are connected by pairwise authenticated channels. Messages between uncorrupted parties are guaranteed eventually to be delivered, although the order and timing of delivery of messages is determined by the adversary. We assume a computationally bounded adversary that is unable to break cryptographic primitives.

B. Asynchronous Verifiable Secret Sharing
Here we give the security definition for our construction: In an AVSS protocol, the dealer D receives input s ∈ F p , and each party P i receives an output share φ (i) for some degree-t polynomial φ : The protocol must satisfy the following properties: • Correctness: If the dealer D is correct, then all correct parties eventually output a share φ (i) where φ is a random polynomial with φ (0) = s. • Secrecy: If the dealer D is correct, then the adversary learns no information about φ except for the shares of corrupted parties. • Agreement: If any correct party receives output, then there exists a unique degree-t polynomial φ such that each correct party P i eventually outputs φ (i).
For simplicity, this definition is written to be specific to Shamir sharing, though a more generic definition would be possible [1]. Our agreement property is written to incorporate the strong commitment property from Backes et al. [1], in which the secret-shared value must be determined by the time that the first correct party outputs a share (and cannot be influenced thereafter by the adversary).

C. Polynomial Commitments
Polynomial commitments are an interface by which a committer can create a commitment to a polynomial as well as witnesses to its evaluation at different points, so to prove that evaluations are correct without revealing the full polynomial. Polynomial commitments have been implicit in all cryptographic VSS protocols since Feldman [8], but were first formalized by Kate et al. [11] We use the scheme from Kate et al. because it gives commitments that are additively homomorphic and constant-sized. Definition 2. (PolyCommit (c.f. [11]) Let (F p ) κ be a family of finite fields indexed by a security parameter κ (we'll typically omit κ and just write F p ). A PolyCommit scheme for F p consists of the following algorithms: Setup(1 κ ,t) generates system parameters SP to commit to a polynomial over F p of degree bound t. Setup is run by a trusted or distributed authority. SP can also be standardized for repeated use. PolyCommit(SP, φ (·)) outputs a commitment C to a polynomial φ (·) for the system parameters SP, and some associated decommitment information aux.
If so, the algorithm outputs accept, otherwise it outputs reject.
A PolyCommit scheme must satisfy the following properties: , then except with negligible probability, an adversary can not create then except with negligible probability, an adversary can not create an evaluation φ ( j), witness w j , and decommitment information aux j such that VerifyEval(SP,C, i, φ ( j), w j , aux j ) = 1 if i = j. • Hiding: Given C and w i for any i, an adversary either -Can only determine φ (·) or φ (i) with negligible probability given bounded computation (Computational Hiding) -Can not determine any information about φ (·) or φ (i), even given unbounded computation (Unconditional Hiding) We additionally require that the commitments and witnesses be additively homomorphic. This allows us to create new commitments and witnesses through interpolation, a property we rely on in our AVSS construction.
• Additive Homomorphism: Given commitments C a and C b to polynomials φ a (·) and φ b (·) respectively, there should be an efficient operation to compute C a+b , the commitment to φ a (·) + φ b (·). Additionally, given w i,a and w i,b , the witnesses for the evaluations of φ a (·) and φ b (·) at i respectively, it should be similarly efficient to compute w i,a+b . Lastly, it should also be efficient to compute w i+ j,a from w i,a and w j,a .
In this work we use PolyCommitPed from Kate et al. [11], which provides a constant-sized commitment that achieves unconditional hiding as well as our desired homomorphic properties. We also note that PolyCommitPed achieves unconditional hiding through the use of a hiding polynomial, which we notate as aux in this work. As aux is instantiated as a polynomial over a finite field, it too realizes our desired property of additive homomorphism.

D. Asynchronous Verifiable Information Dispersal
Our protocol relies on an information dispersal protocol as defined below. Our definition is for a batch, such that M messages v 1 , ..., v M are dispersed at once and can be individually retrieved. Hendricks et al. [10] present AVID − FP, an AVID protocol whose total communication complexity is only O(|v|) in disperse phase for a sufficiently large batch v >> n, i.e. it achieves only constant communication overhead.

E. Reliable Broadcast
Reliable broadcast [3] is a primitive that enables a dealer D to broadcast a message v to every party. Regardless of if the dealer is correct, if any party receives some output v then every party eventually receives v . Reliable broadcast is a special case of information dispersal, where each party simply begins Retrieve immediately after Disperse completes. In fact, all efficient protocols we know of, such as Cachin and Tessaro [5] or Duan et al., [7], are built from an AVID protocol. We therefore skip the definition but use the ReliableBroadcast syntax in our protocol description as short hand for Disperse followed by all parties immediately beginning Retrieve.

F. Public Key Encryption
We make use of a semantically secure public key encryption scheme, (Enc, Dec), such that Enc PK (m) produces a ciphertext encrypted under public key PK, while Dec SK (c) decrypts the message using secret key SK. We assume a PKI, such that each party P i already knows SK i . We also assume that each public key is a function of the secret key, written PK = g SK , which we make use of by revealing secret key during the dealer implication phase.
We note that while in our presentation we only consider a single session with a single dealer, for a practical deployment, we would want to derive per-session keys from a single longterm keypair and allow a recipient to present the session key along with a proof of its correctness, rather than reveal her secret key (and consequently need to update her key in the PKI).  Fig. 1. Illustration of hbAVSS. A batch of secrets s 1 , ..., s N are encoded as a degree-(t,t) bivariate polynomial φ (·, ·). Each party P i 's shares φ (i, ·) are encrypted, then dispersed. Polynomial commitments to the sharings are broadcast, enabling parties to validate their shares. If a party P i detects an invalid share, they publish their decryption key, enabling the other parties to confirm the dealer is faulty. Invalid shares are then recovered in two steps: (R1) each party P j receives valid shares to interpolate one column φ (·, j), then (R2) each party P i reconstructs their shares φ (i, ·).

III. THE hbAVSS PROTOCOL A. Protocol description
At a high level, the hbAVSS protocol consists of the following steps: 1) Dealer's phase: the dealer creates Shamir sharings for t + 1 secrets and broadcasts t +1 commitments to the polynomials that encode them. The dealer then encrypts each party's shares using their public encryption keys, and disperses the encrypted payloads. 2) Share validation: each party retrieves their encrypted payload, and then attempts to decrypt and validate their shares against the polynomial commitments. If sufficiently many parties successfully receive valid shares, then the shares are output. 3) Implicating a faulty dealer: if any party finds that the shares they receive are invalid or fail to decrypt, they reveal their secret key, enabling the other parties to confirm that the dealer was faulty. 4) Share recovery: once the dealer is implicated as faulty, the parties who did receive valid shares distribute them to enable the remaining parties also to reconstruct their shares. We now explain these steps in more detail. The protocol pseudocode is given in Algorithm 1, and the narration below refers to the schematic illustration in Figure III-A. 1) Sharing and committing: : The protocol shares a batch of t + 1 inputs at a time, {s 1 , ..., s t+1 }. The dealer creates a degree-t Shamir sharing φ (·, k) for each input such that φ (0, k) = s k , and each party P i 's share of s k is φ (i, k). We visualize this as a matrix, with each party's shares forming a row as illustrated in Figure III-A. Later, if share recovery is needed, we make use of φ (·, ·) as a degree-(t,t) bivariate polynomial.

512:
output shares {φ (i, k)} k∈[t+1] * Note: To avoid clutter, the protocol is written to share a batch of exactly t + 1 secret values. To achieve linear communication overhead, the ReliableBroadcast and Disperse instances should be shared among a batch of several simultaneously executing instances, as explained in Section III-C.
The dealer then uses PolyCommit to create a commitment C k to each sharing φ (·, k). The commitments are then broadcast, ensuring all the parties can validate their shares consistently.
Next, for each share k and party P i , the dealer creates an encrypted payload z i,k , consisting of the shares φ (i, k) and the polynomial evaluation witness w i,k , encrypted under P i 's public key PK i . The dealer then Disperses these encrypted payloads. With the broadcast and dispersal complete, the dealer's role in the protocol is concluded -in fact since information dispersal itself requires only one message from the dealer, the dealer's entire role is just to send messages in the first round.
2) Share Verification: : Each party P i waits for ReliableBroadcast and Disperse to complete, and then retrieves just their payload {z i,k } k∈[t+1] . The party then attempts to decrypt and validate its shares. If decryption is successful and all the shares are valid, then P i signals this by sending an OK message to the other recipients. The goal of the OK and READY messages (lines 302-307) is to ensure that if any party outputs a share, then enough correct parties have shares for share recovery to succeed if necessary.
3) Implicating a faulty dealer: : If any honest party P i receives a share that either fails to decrypt or fails verification, they reveal their secret key by sending (IMPLICATE, SK i , k), which other parties can use to repeat the decryption and confirm that the dealer dispersed invalid data. 4) Share Recovery: After a dealer is implicated as faulty, the protocol enters a two-step share recovery process, following the approach of Choudhury et al. [6]. In the first step, parties wait for t + 1 R1 messages from parties that received valid shares originally. The R1 can be checked individually by making use of the homomorphic property of polynomial commitments and witnesses (Section II-C). Every correct party P j participates in the second phase of share recovery, by reconstructing one column of the bivariate polynomial φ (·, j).
The second step is the transpose, where each party reconstructs the row polynomial corresponding to its shares. Since all correct parties send an R2 message, even if they did not originally receive valid shares, we can interpolate through ordinary robust decoding rather than using the polynomial commits.
Batching: For simplicity, we have described the protocol as sharing a batch of exactly t +1 values. However, to reach our desired amortized complexity goals, we need to run multiple instances in parallel in order to offset the overhead of Disperse and ReliableBroadcast. The idea is to run several instances of hbAVSS such that the Disperse and ReliableBroadcast protocols are in lockstep, sharing their control messages (i.e., the payloads are concatenated across the several instances).
B. Security Analysis of hbAVSS Theorem 1. The hbAVSS protocol (Algorithm 1) satifies the requirements of an AVSS protocol (with high probability) when instantiated with an additively homomorphic polynomial commitment scheme (Setup, Commit), an AVID protocol (Disperse, Retrieve), a reliable broadcast protocol ReliableBroadcast, and a semantically secure public key encryption scheme (Enc, Dec) with a pre-established PKI such that each party P i knows their secret key SK i and the public keys {PK i = g SK i } i∈ [N] are well known.
Proof. Correctness. The correctness property follows easily: If the dealer D is correct, then ReliableBroadcast and Disperse complete, so each honest party receives their valid shares and outputs them through the ordinary case (line 307). Secrecy. Secrecy also follows easily. The hiding property of the broadcasted polynomial commitments ensures that they reveal nothing about the shares. Each party's shares are encrypted prior to dispersal, so the computationally-bounded adversary only obtains the shares that can be decrypted using corrupt parties' secret keys. Share recovery reveals more information, but if the dealer is correct, then any attempts by the adversary to initiate share recovery will be rejected (line 405). Agreement. It is easy to check that parties only output shares that are consistent with the broadcasted polynomial commitments. The challenge is in showing that if any correct party outputs a share, then all of them do. In the following, assume a correct party has output a share, either through the typical path (line 307) or through share recovery (line 512). In either case, the broadcast and dispersal must have completed and the party must have received 2t + 1 READY messages (line 305).
First, notice the READY-amplification in line 304 plays the same role as in Bracha broadcast: Claim 1. If any correct party outputs a share, then all correct parties eventually receive 2t + 1 READY messages (line 305).
If any correct party receives 2t + 1 READY messages, then at least t + 1 correct parties must have sent READY messages, which causes all correct parties to send READY messages.
Next, the following claim ensures that share recovery can proceed if necessary: Claim 2. If any correct party outputs a share, then at least t + 1 correct parties receive valid shares.
For READY-amplification to begin, some correct party must have initially sent READY after receiving 2t + 1 OK messages (line 302), thus t + 1 correct parties must have successfully received valid shares (line 208).
Because of the availability and agreement properties of dispersal, every correct party either receives valid shares (and by then Claim 1 outputs ordinarily) or else receives an invalid share and initiates share recovery, which by Claim 2 is able to proceed.

C. Performance Analysis of hbAVSS
We now analyze the performance of hbAVSS, focusing primarily on communication complexity. Recall that our goal is to achieve linear amortized communication overhead. Since one run of this protocol results in t + 1 secret shared values, we have a budget of O(n 2 ) communication complexity to keep in mind.
We encounter a challenge: the up-front overhead (independent of payload size) of the Broadcast and Disperse primitives is either O(n 2 log n) if Merkle tree checksums are used (as in Cachin and Tessaro [5]) or O(n 3 ) if full cross checksums are used (as in Hendricks et al. [10]). Hence to obtain linear overhead, we consider amortizing these costs across at least n multiple runs executing in parallel, sharing the upkeep.
The broadcast payload consists of t + 1 commitments, but each one is constant size. Since the overhead of broadcast is O(n), the total communication cost is O(n 2 ). The total size of the Disperse payload is n(t + 1) elements, but the overhead of dispersal is constant, so the total cost is O(n 2 ). Each party Retrieves only a block of t + 1 elements, thus all n of them. The Bracha-like OK and READY messages clearly contribute O(n 2 ).
The share recovery process clearly involves O(n 2 ) total communication, but only occurs at most once, since it enables all correct parties to reconstructing their shares at once.
The final challenge is dealing with spurious implications. In the worst case, each honest party may need to validate up to t false implications, each of which requires retrieving a block from the dispersal protocol, thus O(n 3 ) worst case cost in total. Fortunately, we amortize this in the same way, by running at least n concurrent instances of the protocol. We only need to process at most one implication per party across all the instances. If spurious, further implications are ignored; if confirmed, initiate share recovery in all instances.