Byzantine agreement (BA), the task of $n$ parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in BA protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is $\tilde O(1)$ bits per party, but some parties must send $\Omega(n)$ bits.
In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $\tilde O(\sqrt{n})$.

In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party communicates only $\tilde O(1)$ bits? Our contributions in this line are as follows:

* We define a cryptographic primitive—succinctly reconstructed distributed signatures (SRDS)—that suffices for constructing $\tilde O(1)$ balanced BA. We provide two constructions of SRDS from different cryptographic and Public-Key Infrastructure (PKI) assumptions.

* The SRDS-based BA follows a paradigm of boosting from “almost-everywhere” agreement to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends $o(n)$ messages.

* We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product).

Our results provide new approaches forward, as well as limitations and barriers, towards minimizing per-party communication of BA. In particular, we construct the first two BA protocols with $\tilde O(1)$ balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).

§ INTRODUCTION

The problem of Byzantine agreement (BA) [Pease et al., 1980, Lamport et al., 1982] asks for a set of $n$ parties to agree on one of their input bits, even facing malicious corruptions. BA is a surprisingly powerful primitive that lies at the core of virtually every interactive protocol tolerating malicious adversaries, ranging from other types of consensus primitives such as broadcast [Pease et al., 1980, Lamport et al., 1982] and blockchain protocols ([Chen and Micali, 2019]), to secure multiparty computation (MPC) [Yao, 1982, Goldreich et al., 1987, Ben-Or et al., 1988, Chaum et al., 1988, Rabin and Ben-Or, 1989].
In this work, we study BA in a standard context, where a potentially large set of $n$ parties runs the protocol within a synchronous network, and security is guaranteed facing a constant fraction of statically corrupted parties.

Understanding the required communication complexity of BA as a function of $n$ is the subject of a rich line of research.
For the relaxed goal of almost-everywhere agreement [Dwork et al., 1988], agreement of all but $o(1)$ fraction of the parties, the full picture is essentially understood. The influential work of King et al., 2006 showed a solution roughly ideal in every dimension: in which each party speaks to $\tilde O(1)$ other parties (polylog degree of communication graph, a.k.a. communication locality [Boyle et al., 2013]), and communicates a total of $\tilde O(1)$ bits throughout the protocol, in $\tilde O(1)$ rounds;[We follow the standard practice in large-scale cryptographic protocols, where $\tilde{O}$ hides polynomial factors in $\log{n}$ and in the security parameter $\secParam$, see [Damgård and Ishai, 2006, Damgård et al., 2008].]
further, the solution does not require cryptographic and/or trusted setup assumptions and is given in the full-information model.
The main challenge in BA thus becomes extending almost-everywhere to full agreement.

In this regime, our current knowledge becomes surprisingly disconnected.
While it is known how to employ cryptography and setup assumptions to compute BA with $\tilde{O}(1)$ locality [Boyle et al., 2013, Chandran et al., 2015, Boyle et al., 2018], the number of bits that must be communicated by each party is large, $\Omega(n)$.[In fact, the constructions in [Boyle et al., 2013, Chandran et al., 2015, Boyle et al., 2018] are for MPC protocols that enable secure computation of any function with $\tilde{O}(1)$ locality; these protocols are defined over point-to-point networks, and so also provide a solution for the specific task of BA.]
BA with amortized $\tilde{O}(1)$ per-party communication (and computation) can be achieved [Braud-Santoni et al., 2013, Chen and Micali, 2019, Abraham et al., 2019]; however, the structure of these protocols is wildly unbalanced: with some parties who must each communicate with $\Theta(n)$ parties and send $\Omega(n)$ bits.
The existence of “central parties” who communicate a large amount facilitates fast convergence in these protocols.
When optimizing per-party communication, the best BA solutions degrade to $\tilde\Theta(\sqrt n)$ bits/party, with suboptimal $\tilde O(n^{3/2})$ overall communication [King and Saia, 2011, King et al., 2011].

This intriguing  gap leads us to the core question studied in this paper: Is such an imbalance inherent?
More specifically:

Is it possible to achieve Byzantine agreement with (balanced)
per-party communication of $\tilde{O}(1)$?

Before addressing our results, it is beneficial to consider the relevant lower bounds.
It is well known that any deterministic BA protocol requires $\Omega(n^2)$ communication [Dolev and Reischuk, 1985] (and furthermore, the connectivity of the underlying communication graph must be $\Omega(n)$ [Dolev, 1982, Fischer et al., 1986]).
This result extends to randomized BA protocols, in the special case of very strong adversarial (adaptive, strongly rushing[A strongly rushing adversary in [Abraham et al., 2019] can adaptively corrupt a party that has sent a message $m$ and replace the message with another $m'$, as long as no honest party received $m$.]) capabilities [Abraham et al., 2019].
Most closely related is the lower bound of Holtby et al., 2008, who showed that without trusted setup assumptions, at least one party must send $\Omega(\sqrt[3]{n})$ messages.[The lower bound in [Holtby et al., 2008] easily extends to a public setup such as a common reference string.] But, the bound in [Holtby et al., 2008] applies only to a restricted setting of protocols with static message filtering, where every party decides on the set of parties it will listen to before the beginning of each round (as a function of its internal view at the end of the previous round).
We note that while the almost-everywhere agreement protocol in [King et al., 2006] falls into the static-filtering model, all other scalable BA protocols mentioned above crucially rely on dynamic message filtering (which is based on incoming messages' content).
This leaves the feasibility question open.

§.§ Our Results

We perform an in-depth investigation of boosting from almost-everywhere to full agreement with $\tilde O(1)$ communication per party.
Motivated by the $\tilde O(1)$-locality protocol of <cit.>, we first achieve an intermediate step of certified almost-everywhere agreement, where almost all of the parties reach agreement, and, in addition, hold a certificate for the agreed value. Boyle et al., 2013 showed how to boost certified almost-everywhere agreement to full agreement in a single round, where every party communicates with $\tilde{O}(1)$ parties.

Our initial observation is that the protocol from [Boyle et al., 2013] achieves low communication aside from one expensive piece: the distributed generation of the certificate, which is of size $\Theta(n)$, and its dissemination.
We thus target this step and explore.

Our contributions can be summarized as follows.

* SRDS and balanced BA.
We define a minimal cryptographic primitive whose existence implies $\tilde O(1)$ balanced BA: succinctly reconstructed distributed signatures (SRDS).

We provide two constructions of SRDS, each based on a different flavor of a public-key infrastructure (PKI): (1) from one-way functions in a “trusted-PKI” model, and (2) from collision-resistant hash functions (CRH) and a strong form of succinct non-interactive arguments of knowledge (SNARKs)[A SNARK [Micali, 1994, Bitansky et al., 2017] is a proof system that enables a prover holding a witness $w$ to some public NP statement $x$ to convince a verifier that it indeed knows $w$ by sending a single message. The proof string is succinct in the sense that it is much shorter than the witness $w$, and knowledge is formalized via an efficient extractor that succeeds extracting $w$ from a malicious prover $P^*$ with roughly the same probability that $P^*$ convinces an honest verifier.] in a model with a “bare PKI” and a common random string (CRS). Roughly, trusted-PKI setup assumes that parties' keys are generated properly, whereas bare PKI further supports the case where corrupt parties may generate keys maliciously. We elaborate on the difference between the PKI models in <ref>.

* Necessity of setup for one-shot “boost.”
Our SRDS-based BA follows a paradigm of boosting from almost-everywhere to full agreement, and does so in a single communication round.
Complementarily, we prove two lower bounds for any such one-shot boost in which every party sends $o(n)$ messages. The first shows that some form of PKI (or stronger setup, such as correlated randomness[In the correlated-randomness model a trusted dealer samples $n$ secret strings from a joint distribution and delivers to each party its corresponding secret string, a setup for threshold signatures.]) is necessary for this task. The second shows that given only PKI setup (as opposed to stronger, correlated-randomness setup), then computational assumptions (namely, at least one-way functions) are additionally required.

In contrast to prior lower bounds ([Holtby et al., 2008, Abraham et al., 2019]), this holds even against a static adversary, and where parties can exercise dynamic filtering (without placing limitations on how parties can select to whom to listen).

* Connections to succinct arguments.
We further explore connections between a natural approach toward attaining SRDS in weaker PKI models and average-case succinct non-interactive argument (SNARG) systems[Similarly to a SNARK, a SNARG allows a prover holding a witness $w$ to some public NP statement $x$ to convince a verifier that $x$ belongs to the language; however, as opposed to a SNARK, here the prover does not prove that it knows $w$ (only that such a witness exists), hence there is no requirement to extract the witness from a cheating prover.] for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product). This can be interpreted as a barrier toward this approach for constructing SRDS without heavy “SNARG-like” tools.

Collectively, our results provide an initial mapping for the feasibility landscape of BA with $\tilde O(1)$ per-party communication, including new approaches forward, as well as limitations and barriers.
Our approach yields two BA protocols with $\tilde O(1)$ communication per party, offering a tradeoff between the setup assumptions and the cryptographic assumptions.
These results answer an open question presented by King and Saia, 2009, asking whether cryptography can be used to construct BA with $o(\sqrt{n})$ communication per party.
Our BA results are summarized in <ref> alongside other almost-everywhere to everywhere agreement protocols.

§.§ Technical Overview

We now proceed to present our results in greater detail.

Our first contribution is identifying and formalizing a cryptographic primitive that enables boosting from almost-everywhere agreement to full agreement on a value, with low per-party communication.

The primitive— (SRDS)—is a new type of a distributed signature scheme, with a natural motivation: allowing a set of parties to jointly produce a signature on some message $m$, which can serve as a succinct certificate for proving that a majority of the parties agree on $m$.
Interestingly, this task does not seem to be attained by existing distributed signature notions, such as multi-signatures [Itakura and Nakamura, 1983], aggregate signatures [Boneh et al., 2003], or threshold signatures [Desmedt and Frankel, 1989]. For example, while multi-signatures (and, similarly, aggregate signatures) can succinctly combine signatures of many parties, to verify the signature, the (length-$\Theta(n)$!) vector of contributing-parties identities must also be communicated.[Indeed, the verification algorithm of multi-signatures (and aggregate signatures) must receive the set of parties who signed the message. This is precisely the culprit for the large $\tilde \Theta(n)$ per-party communication within the low-locality protocol of [Boyle et al., 2013].]
As discussed in the related-work section (<ref>), threshold signatures are implied by SRDS but also do not suffice: while identities of the signers are no longer needed to verify a combined signature, this information is necessary to reconstruct the combined signature in the first place (even within specific existing schemes, [Gennaro et al., 2001, Boldyreva, 2003]).
We provide a more detailed comparison to different signature notions in <ref>.

An SRDS scheme is based on a PKI for signatures, where every party is set with a secret signing key and a public verification key.[As mentioned, we will distinguish between a bare PKI, where every party locally chooses its keys and corrupted parties can set their keys as a function of all verification keys (and any additional public information), and a trusted PKI, which is honestly generated (either locally or by a trusted party) and where corrupted parties cannot change their verification keys. See further discussion below.]
The parties may receive additional setup information that may contain, for example, public parameters for the signature scheme or a common random string (CRS), depending on the actual construction.
Given a message $m$, every party can locally generate a signature on $m$, and signatures on the same message can be succinctly aggregated into a new signature.
The new aspect is that given a combined signature and a message $m$, it is possible to verify whether is was aggregated from a “large” number of “base” signatures on $m$, and both aggregation and verification can be done succinctly.

Three properties are required from an SRDS scheme:
robustness means that an adversary cannot prevent the honest parties from generating an accepting signature on a message; unforgeability prevents an adversary controlling a minority from forging a signature; and succinctness requires that the “final” signature (including all information needed for verification) is short (of size $\tilde{O}(1)$) and can be incrementally reconstructed from “base” signatures in small batches of size $\polylog(n)$.[$\polylog(n)$ denotes $\log^c(n)$ for some constant $c>1$.]
An SRDS scheme is $t$-secure if it satisfies the above properties even facing $t$ colluding adversarial parties.

Balanced BA from SRDS.
We demonstrate how to attain $\tilde O(1)$-balanced BA against $\beta n$ corruptions (for $\beta<1/3$) given black-box access to any $\beta n$-secure SRDS scheme.
We begin by presenting a distilled version of the “certified almost-everywhere agreement” approach from [Boyle et al., 2013] that we tailor for Byzantine agreement, where only correctness matters and privacy is not required.[The focus of [Boyle et al., 2013] was on MPC and required stronger assumptions and additional rounds; in particular, a use of their MPC protocol cannot lead to communication-balanced BA as it requires all parties to send information to a designated $\polylog(n)$-size set, the so-called supreme committee.]

* The parties execute the almost-everywhere agreement protocol of King et al. [King et al., 2006]; this establishes a $\polylog(n)$-degree communication tree (which is essentially a sparse overlay network) in which each node is assigned with a committee of $\polylog(n)$ parties. The guarantees are that the $\polylog(n)$-size supreme committee (the committee assigned to the root) has a $2/3$ honest majority and almost all of the parties are connected to the supreme committee via the communication tree.

* The supreme committee executes a BA protocol on their inputs to agree on the output $y$, and, in addition, runs a coin-tossing protocol to agree on a random seed $s$. Next, the supreme committee propagates the pair $(y,s)$ to almost all of the parties.

* Once a party receives the pair $(y,s)$, the party signs it (in [Boyle et al., 2013], using a multi-signature scheme), and sends the signature back to the supreme committee that aggregates all the signatures. The aggregated signature attesting to $(y,s)$ is then distributed to almost all of the parties.

Once this form of certified almost-everywhere agreement on $(y,s)$ is reached, full agreement can be obtained in one round. Every party $\Party_i$ that receives the signed pair $(y,s)$, evaluates a pseudorandom function (PRF) on the seed $s$ and its identity $i$ to determine a set of (sufficiently random) $\polylog(n)$ parties, and sends the signed $(y,s)$ to every party in that set. A party that receives such a signed pair, can verify that a majority of the parties agree on $(y,s)$ (by the guarantees of multi-signatures) and that it was supposed to receive a message from the sender (by evaluating the PRF on $s$ and the sender's identity). In this case, it can output $y$ and halt.

The protocol from [Boyle et al., 2013] achieves $\tilde{O}(1)$ locality. However, recall that even though the size of a multi-signature might itself be “small,” the verification algorithm additionally requires a list of contributing parties, where the description size of this list will need to be proportional to $n$. Hence, the effective size of the aggregated signature, and thus per-party communication, is stuck at $\Theta(n)$.

At this point the new notion of SRDS comes into the picture.
We use the succinctness property of SRDS combined with the communication tree established by the protocol from [King et al., 2006] to bound the size of the aggregated signatures by $\tilde{O}(1)$.
In essence, the parties aggregate the signatures in a recursive manner up the communication tree such that in each step at most $\polylog(n)$ signatures are aggregated.

This technique introduces additional subtleties that must be addressed. For example, since the partially aggregated signature can no longer afford to describe the set of contributing parties, it is essential to make sure that the same “base” signature is not aggregated multiple times (this may allow the adversary to achieve more influence on the final aggregated signature than its proportional fraction of “base” signatures). To ensure that the  fraction of signatures that are generated by corrupted parties is equal to the corruption threshold, every party is assigned with $\polylog(n)$ (virtual) identities—one identity for each path from that party to the supreme committee in the communication tree.

Let $\beta<1/3$ be a constant. Assuming the existence of $\beta n$-secure SRDS, there exists an $n$-party, $\beta n$-resilient BA protocol that terminates after $\polylog(n)$ rounds, and where every party communicates $\polylog(n)\cdot\poly(\secParam)$ bits.

We note that our BA protocol is the first to establish a $\polylog(n)$-degree communication graph where every party has an “honest path” to a $2/3$-honest committee, such that the per-party communication required for establishing it is $\tilde{O}(1)$. Thus, we can obtain the following corollaries.

Let $\beta<1/3$ be a constant. Assuming the existence of $\beta n$-secure SRDS:

* Broadcast:
There exists a $\beta n$-resilient 1-bit broadcast protocol such that $\ell$ protocol executions (potentially with different senders) require $\ell\cdot\polylog(n)\cdot\poly(\secParam)$ bits of communication per party.

* MPC:
Assuming fully homomorphic encryption, a function $f:(\zo^\inputlen)^n\to\zo^\outputlen$ can be securely computed with guaranteed output delivery tolerating a static, malicious $\beta n$-adversary, such that the total communication complexity (of all parties) is $n\cdot\polylog(n)\cdot\poly(\secParam)\cdot(\inputlen+\outputlen)$ bits.

One remark regarding the corruption model is in place.
In this work we consider static adversaries that choose the set of corrupted parties before the beginning of the protocol. As mentioned above, our constructions are based on some form of trusted setup, which, as we prove below, is necessary. We emphasize that (as standard) we avoid trivialized settings, where the trusted setup determines a $\polylog(n)$-degree communication tree for achieving full agreement, by considering the adversarial model where the adversary can corrupt the parties adaptively during the setup phase given the setup information of the corrupted parties and any public setup information. During the online phase the adversary is static and cannot corrupt additional parties.

Constructing SRDS.
We present two constructions of SRDS, offering a tradeoff between setup assumptions and cryptographic assumptions.

Our first construction is influenced by the “sortition approach” of Algorand [Chen and Micali, 2019] and merely requires one-way functions (OWF); however, the public-key infrastructure (PKI) is assumed to be honestly generated (either by the parties themselves or by an external trusted third party), and corrupted parties cannot alter their keys. The construction is based on digital signatures augmented with an oblivious key-generation algorithm for sampling a verification key without knowing the corresponding signing key.[We note that standard signatures can be used if we strengthen the model assumptions, by assuming that a party can securely erase its signature key, or by considering a trusted party that only provides the verification keys to some parties. We opted not to rely on stronger model assumption since we can establish signatures with oblivious key generation from the minimal assumption of one-way functions.] Lamport's signatures [Lamport, 1979], which are based on OWF, can easily be adjusted to support this property.
To establish the PKI, every party decides whether to generate its public verification key obliviously or together with a signing key by tossing a biased coin, such that with overwhelming probability all but $\polylog(n)$ keys are generated obliviously.
Since those with the ability to sign are determined at random (as part of the trusted PKI), only parties who hold a signing key can sign messages. The
oblivious key-generation algorithm ensures that an adversary who
only sees a list of verification keys, cannot distinguish between the
keys that have a corresponding signing key and ones that do not.
As a result, even if the adversary chooses the set of corrupt parties
after the keys are sampled, with a high probability, the fraction
of honest parties will be preserved in the signing subset. SRDS
signature-aggregation is done by concatenation, and verification of
an SRDS signature requires counting how many valid signatures
were signed on the message.

It would be desirable to reduce the trust assumption in establishing the PKI, by using verifiable pseudorandom functions (VRF) [Micali et al., 1999] as done in [Chen and Micali, 2019].
However, this approach [Chen and Micali, 2019] is defined within a blockchain model where a fresh random string (the hash of the recent block) is assumed to be consistently available to all parties later in the protocol and serves as the seed for the sortition;
equivalently, that parties have access to a common random string (CRS) independent of corrupted parties' public keys.
Without this extra model assumption, their VRF approach does not apply.
We note that several recent consensus protocols [Abraham et al., 2019, Chan et al., 2019, Cohen et al., 2019, Chan et al., 2020, Cohen et al., 2020, Blum et al., 2020, Wan et al., 2020, Wan et al., 2020] also follow the sortition approach of [Chen and Micali, 2019]; however, similar to our first construction, their PKI is assumed to be honestly generated by a trusted third party.

Let $\beta<1/3$ and assume that OWF exist. Then, there exists a $\beta n$-secure SRDS in the trusted-PKI model.

Our second construction is based on a weaker bare-PKI setup, in which each party locally computes its signature keys, and the adversary can corrupt parties and change their keys as a function of honest parties' public keys.
To illustrate the underlying ideas, consider a simplified case where all of the nodes in the almost-everywhere communication tree are honest (each node will essentially be realized by some committee of parties). A construction would be to have all parties sign the message and send the signature to their respective leaf nodes. Every leaf node would then count the number of verified signatures received and send the message and the counter to its parent. In a recursive way, every node would simply add the counters received from its children and send it to its parent. At the end of this process, the root node would get a final count of the total number of verified signatures. This approach completely breaks down, however, if even one node is not honest as it can lie about its count. To enforce an honest behavior of the nodes, we need to make sure that the aggregation is done in a verifiable way, ensure that bad nodes send a valid count of the number of signatures aggregated so far.

Towards this, our first idea is to require each node to attach a “succinct proof” of honest behavior to their messages. In particular, in addition to the message $m$ and count $c$ that a leaf node sends to its parent, it must also send a proof to convince the parent that it knows $c$ distinct signatures on the message $m$. Similarly, every node must prove that they
received sufficiently many valid proofs backing up its count. To verify, it is sufficient to check at the root node, whether sufficiently many “base” signatures were aggregated. This approach requires proof systems that support recursive composition;
for this reason, we use proof-carrying data (PCD) systems [Chiesa and Tromer, 2010].

A PCD system extends the notion of SNARKs to the distributed setting by allowing recursive composition in a succinct way.
Informally, every party can generate a succinct proof on some statement, certifying that it satisfies a given local property with respect to its private input and previously received messages (statements and their proofs).
Bitansky et al., 2013 proved that PCD systems for logarithmic-depth DAGs exist assuming SNARKs with linear extraction, where the size of the extractor is linear in the size of the prover.[We note that although SNARKs with linear extraction are a stronger assumption than standard SNARKs (with polynomial extraction), standard SNARKs techniques do not separate the two notions.] Extractability assumptions of this kind have been previously considered in, [Valiant, 2008, Damgård et al., 2012, Gupta and Sahai, 2014, Boyle et al., 2018].
Since PCD systems allow for propagation of information up a communication tree in a succinct and publicly verifiable way, they seem to exactly capture our requirements for SRDS.

This simple idea, however, is vulnerable to an adversary that generates a valid-looking aggregate signature by using multiple copies of the same signature. Indeed, since the partially aggregated signature must be succinct, the parties cannot afford to keep track of which base signatures were already incorporated, leaving them vulnerable to a repeat occurrence.
We protect against such an attack by encoding additional information in the partially aggregated signatures using collision-resistant hash functions (CRH). We refer the reader to <ref> for the detailed solution.

Let $t<n/3$ and assume that CRH and SNARKs with linear extraction exist. Then, there exists a $t$-secure SRDS in the CRS and bare-PKI model.

Necessity of PKI for single-round boost of almost-everywhere agreement.
Our SRDS-based BA protocol (<ref>) shows how to boost almost-everywhere agreement to full agreement in a single round with small communication. Both our constructions crucially rely on a public-key infrastructure (PKI) that enables each party to publish its verification key on a bulletin board. We show that this setup assumption is necessary for this task. That is, given only public setup—the common reference string (CRS) model—this task is not possible.

We note that the lower bound of Holtby et al., 2008 does not translate to our setting, as it considers static message filtering, where every party chooses to whom to listen in a given round based on its view prior to that round. The lower bound in [Holtby et al., 2008] shows that dynamic filtering, where filtering can also be based on the content of received messages, is required (at least in the CRS model). We present the first such lower bound in the dynamic-filtering model.

There is no single-round protocol from almost-everywhere to everywhere agreement in the CRS model where every party sends sublinear ($o(n)$) many messages.

Recall that almost-everywhere agreement guarantees that all parties agree on the common output aside from a $o(n)$-size set of isolated parties, whose identities are unknown to the remaining honest parties.
In the setting of static filtering, one can prove continued isolation of these parties for any low-communication protocol in a relatively clean manner [Holtby et al., 2008]: The probability that an honest party $\Party_i$ will send messages to an honest isolated $\Party_j$ is independent of the event that $\Party_j$ will choose to process messages from $\Party_i$ in this round, thus placing a birthday-type bound on information successfully being conveyed.
With dynamic filtering, however, $\Party_j$ may process messages dependent on some property of this message, whether it contains particular authentication, which may only be contained in honest messages.[In general, message filtering should be via a simple and “light” test, counting how many messages arrived, or verifying a signature. We refer to [Boyle et al., 2018] for a discussion on message filtering in protocols over incomplete graphs.]
In such case, there is strong bias toward accepting honest messages, and one must work harder to ensure that isolated parties do not reach agreement.

At a high level, the idea of our lower bound is to make a linear set of corrupted parties emulate the role of isolated parties during the first part of the protocol (reaching almost-everywhere agreement). This way, the honest parties cannot distinguish between isolated honest parties and faking corrupted parties, and must attempt to communicate the output value to all such parties. However, if each honest party only sends a sublinear number of messages, then with a very high probability, most isolated honest parties (and faking corrupted parties) only receive messages from a sublinear number of non-isolated parties in the last round. The adversary can use this fact to keep an isolated honest party confused in the following sense. In the last round of an execution with preagreement on 0 (on 1), the adversary sends to this party messages corresponding to an execution with preagreement on 1 (on 0). Without private-coin setup such as PKI, an isolated party cannot distinguish between honest messages in the real execution and fake messages from the simulation.

To carry out this attack, we need to show that there exist parties who receive messages from a “small” set of neighbors in both scenarios: when all parties start with input $0$ and when all start with input $1$ (otherwise, the adversary may not have a sufficient corruption budget for the attack). Before the protocols begins, the adversary decides on the set of parties to corrupt by first emulating in its head two executions, one with preagreement on $0$ and the other with preagreement on $1$, where the same linear-size set of parties act as isolated parties. We use a counting argument to show that there exist isolated parties who receive messages from a sublinear set of neighbors in both executions. The adversary targets one of these parties to attack and corrupts all “simulated isolated parties” except for the targeted one, along with the pair of neighbor-sets who communicate with the targeted party in the simulation.
We refer the reader to Section <ref> for a formal description and analysis of the attack.

On the different PKI models.
As discussed above, SRDS implies a single-round boost of almost-everywhere to full agreement, which in turn (by <ref>) requires some form of private-coin setup. Given this, one of our goals is to minimize the trust assumptions in the setup phase. Our SNARK-based construction offers the minimal setup requirement—a bare PKI—where every party locally generates its own signature keys and publishes the verification key on a bulletin board. The adversary can adaptively corrupt parties and change their keys as a function of all the public setup information (including the honest parties' verification keys and the CRS, in case it exists). This is the prevalent PKI model that has appeared in, [Canetti, 2004, Katz and Koo, 2006, Kidron and Lindell, 2011, Canetti et al., 2016].

Our OWF-based construction, on the other hand, assumes an honestly generated PKI, where the adversary cannot alter the corrupted parties' keys. Such a setup assumption is normally captured by a trusted party who samples the keys for all the parties, and provides each party with its secret key as well as all public keys; see, [Lindell et al., 2006, Abraham et al., 2019, Chan et al., 2019, Cohen et al., 2019, Chan et al., 2020].
We note that our trusted-PKI setup is weaker than a full blown trusted party in two aspects: First, the distribution from which the trusted party samples the values is a product distribution, parties' keys are independent; this is weaker than a general correlated randomness setup (as used, in [Abraham et al., 2019] for threshold-signatures setup). Second, we consider public-coin sampling in the sense that the sampling coins are revealed to the corresponding party (intermediate key-generation values are not kept hidden). In fact, one can consider the model where every party honestly generates and publishes its public key, and corrupted parties can deviate from the protocol only in the online phase.

Necessity of OWF for single-round boost in PKI model.
<ref> states the necessity of private-coin setup for single-round protocols (from almost-everywhere agreement to full agreement) where every party sends $o(n)$ messages. In the PKI model, where the public/private keys of each party are independently generated, we further prove that cryptographic assumptions are necessary. Intuitively, if one-way functions (OWF) do not exist, an adversary can invert the PKI algorithm with noticeable probability to find a pre-image for each public key. In this case, the adversary can carry out the attack for the CRS model, discussed above.

If OWF do not exist, there is no single-round protocol from almost-everywhere to everywhere agreement in the trusted PKI model where every party sends sublinear many messages.

We note that this lower bound does not extend to more complex private-coin setups, where the parties receive correlated secret strings that are jointly sampled from some distribution, setup for information-theoretic signatures. Indeed, given such a setup it is possible to boost almost-everywhere to everywhere agreement in a single round with information-theoretic security and where every party sends $\polylog$ many messages (albeit, each of size $\Omega(n)$) [Boyle et al., 2018].
The reason that the proof approach of <ref> does not apply in this case is that when the private keys of two honest parties are  correlated, it is unclear how an (even computationally unbounded) adversary that only receives partial information about this correlation can consistently invert the setup information and impersonate honest parties. We leave the feasibility of single-round boost protocols from almost-everywhere to everywhere in the correlated-randomness model, in which every party sends sublinear many bits (as opposed to messages), as an interesting open question.

Connection to succinct arguments.
Our SRDS construction from CRH and SNARKs works with minimal setup requirements, but relies on relatively undesirable cryptographic assumptions (in particular, SNARKs are a non-falsifiable assumption [Gentry and Wichs, 2011]). On the other hand, our construction from one-way functions uses light computational assumptions, but (as with many other works in this area, [Abraham et al., 2019, Chan et al., 2019, Cohen et al., 2019, Chan et al., 2020]) requires a stronger assumption of trusted PKI. A clear goal is to obtain SRDS from better computational assumptions within a better setup model, ultimately reducing to bare PKI, or even more fine-grained intermediate models such as registered PKI[In the registered PKI, every party can arbitrarily choose its public key (just like in bare PKI), but in order to publish it, the party must prove knowledge of a corresponding secret key.] (see [Boldyreva, 2003, Lu et al., 2013] and a discussion in [Bellare and Neven, 2006]). A natural approach toward doing so is to build upon one of the closest existing relatives within this setting: multi-signatures.

Recall that multi-signatures almost provide the required properties of SRDS in this setting, in that they support succinct aggregation of signatures, with the sole issue that multi-signature verification requires knowledge of the set of parties who contributed to it—information that requires $\Theta(n)$ bits to describe. Multi-signatures have been constructed from (standard) falsifiable assumptions in the registered-PKI model, [Lu et al., 2013].
A natural approach toward constructing SRDS within this model is thus to simply augment a multi-signature scheme with some method of succinctly convincing the verifier that a given multi-signature is composed of signatures from sufficiently many parties. We demonstrate challenges toward such an approach, by showing that in some cases this necessitates a form of succinct non-interactive arguments.

More specifically, we observe that asserting approval of a multi-signature by sufficiently many parties is inherently equivalent to asserting existence of a large subset of parties $S\subseteq[n]$, such that their corresponding verification keys $\sset{\vk_i}_{i\in S}$ satisfy a given function-target relation $f_{\sigma,m}(\sset{\vk_i}_{i\in S})=1$. (Here $m$ is the message, $\sigma$ is the multi-signature and $f_{\sigma,m}$ is a function that is derived from the multi-signature verification function.) Such a task can be viewed as a class of “Subset-$f$” problems on the verification keys $\vk_1,\ldots,\vk_n$, capturing as special cases the standard Subset-Sum and Subset-Product problems with functions $f_{\Sigma}(\sset{x_i}_{i\in S})=\sum_{i\in S} x_i$ and $f_{\Pi}(\sset{x_i}_{i\in S})=\prod_{i\in S} x_i$, respectively.

Considering even a generous setup model of trusted PKI, where parties' verification keys $\vk_1,\ldots,\vk_n$ are generated independently and honestly, the Subset-$f$ problem begins taking the form of problems where we do not know (or even possibly believe) that the witness $S\subseteq[n]$ can be compressed to $o(n)$ bits. As we show, an SRDS of this form implies a type of average-case non-interactive argument for asserting membership in Subset-$f$, with succinct proof size: namely, a form of succinct non-interactive argument (SNARG) as in [Bitansky et al., 2013], with average-case soundness guarantees. Although this average-case notion does not directly fall within the negative results of Gentry and Wichs, 2011, it appears to be a powerful notion which may be interpreted as a barrier toward this approach to SRDS construction without SNARG-like tools.

Motivated by this, we explore hardness of the Subset-$f$ problem for more general classes of functions $f$. We show that over rings with appropriate structure (namely, Hadamard product), NP-hardness results for Subset-Sum and Subset-Product can be extended to include (worst-case) Subset-$\phi$ for all elementary symmetric polynomials $\phi$.

We make explicit the above connection for the multi-signature scheme of Lu et al., 2013 (LOSSW) in relation to (average-case) Subset-Product, and extend to multi-signature schemes of appropriate structure in relation to the Subset-$\phi$ problem for elementary symmetric polynomials $\phi$. The reduction leverages homomorphism, where a combined signature for a set of parties on message $m$ in the multi-signature scheme corresponds to a valid single-party signature with respect to a specific joint function of the parties' verification keys $\vk_i$; for LOSSW, their product $\vk^* = \prod_i \vk_i$.

Any SRDS based on the LOSSW [Lu et al., 2013] multi-signature scheme in a natural way (as we define) implies the existence of succinct non-interactive arguments for average-case Subset-Product.

This extends to a more general class of multi-signature schemes and Subset-$\phi$ for elementary symmetric polynomials.

At a high level, the reduction interprets a (random) Subset-Product instance with target $(x_1,\dots,x_n,t)$ as a set of uniform verification keys $(\vk_1,\dots,\vk_n,\vk_{n+1}=t^{-1})$ for the multi-signature scheme.
Given a satisfying witness $S \subseteq [n]$ with $\prod_{i \in S} x_i = t$ of appropriate size, this translates to knowing a large subset of verification keys for which generating an SRDS on their behalf can be achieved efficiently with respect to the degenerate verification key $\vk^* = \prod_{i \in S} \vk_i \cdot t^{-1} = 1$.
On the other hand, for uniformly sampled keys without such an embedded trapdoor subset, forging such an SRDS will be hard.

We refer the reader to <ref> for formal definitions of these notions (including SRDS “based on” a multi-signature scheme and average-case SNARGs), as well as further discussion and details of our claims and proofs.

§.§ Additional Related Work

Distributed signatures.
Distributed signatures come in many flavors. We compare SRDS to existing notions from the literature.

Threshold signatures [Desmedt and Frankel, 1989, Rabin, 1998, Gennaro et al., 2001, Shoup, 2000, Boldyreva, 2003, Harchol et al., 2018] can guarantee that a sufficiently large number of parties signed the message, while keeping the signature-length (including all information needed to verify) independent of $n$. However, threshold signatures require the keys to be generated by a trusted party in a correlated way (as a Shamir sharing of the signing key), and the signature-reconstruction protocol of existing schemes does not offer succinct aggregation in “small” batches. SRDS imply threshold signatures by having the setup algorithm produce the PKI for the parties, and using the aggregation algorithm to reconstruct a signature.

We note that Libert et al., 2016 constructed fully distributed threshold signatures that do not require any setup assumptions. However, this scheme is not applicable in our setting, since it requires an interactive key-generation protocol to generate the public and secret keys, and this protocol in turn uses a broadcast channel. In fact, as indicated by our lower bound, some form of private-coin setup is inherently needed for constructing SRDS.

Multi-signatures [Itakura and Nakamura, 1983, Micali et al., 2001, Boldyreva, 2003, Bellare and Neven, 2006, Lu et al., 2013, Boneh et al., 2018] guarantee that a subset of parties signed the message.
Unlike threshold signatures, correlated trusted setup is not needed and a bare PKI suffices; in addition, some of the constructions enable succinct aggregation in “small” batches.
Aggregate signatures [Boneh et al., 2003, Lysyanskaya et al., 2004, Boldyreva et al., 2007, Lu et al., 2013, Lee et al., 2013, Hohenberger and Waters, 2018] are a similar primitive that allows aggregating signatures on different messages. The main distinction of SRDS is succinctness that enables verification without knowing the signing parties. This property is crucial for our BA protocol construction.

Group signatures [Chaum and van Heyst, 1991] and ring signatures [Rivest et al., 2001] allow any individual party to sign a message on behalf of a set while hiding their identity.  This is different than our setting where we need to prove that a majority of the parties signed the message.

Large-scale MPC.
The focus of this work is communication complexity of Byzantine agreement protocols; however, <ref> demonstrates applications general secure multiparty computation (MPC).
Large-scale MPC was initially studied by Damgård and Ishai, 2006 and successors ([Damgård and Nielsen, 2007, Damgård et al., 2008, Damgård et al., 2010]), in the sense that the amortized per-party work grows only as $\tilde O(|C|/n + \poly(n))$, where $C$ is the circuit to be computed.
Dani et al., 2017 applied the almost-everywhere agreement protocol [King et al., 2006] to achieve MPC with amortized per-party communication of $\tilde{O}(\ssize{C}/n+\sqrt{n})$.
Using cryptographic assumptions (threshold FHE), Zamani et al., 2014 reduced the amortized cost to $\tilde{O}(\ssize{C}/n)$. Under comparable assumptions, our results achieve amortized cost of $\tilde{O}(\inputlen+\outputlen)$ (where $\inputlen$ and $\outputlen$ stand for the function's input/output length).

The bottleneck complexity of MPC was studied in [Boyle et al., 2018], as the maximum communication complexity required by any party within the protocol execution. It was shown that for some $n$-party functions $f: \zo^n \to \zo$, some parties must communicate $\Omega(n)$ bits to compute $f$, even if security is not required. This result rules out generic MPC with balanced, sublinear communication per party, and motivates our MPC results of amortized sublinear communication per party. Note that in [Boyle et al., 2015] load-balanced MPC was achieved, however, amortized over large programs (and in a model that allows each party to have a single use of a broadcast channel).

Communication-efficient BA.
Known protocols that break the $\Omega(n^2)$ communication barrier from [Dolev and Reischuk, 1985] (for deterministic protocols) follow one of two paradigms. The first is starting with the almost-everywhere agreement protocol of [King et al., 2006] and boost it to full agreement; this approach includes [King and Saia, 2009, King and Saia, 2011, King et al., 2011, Braud-Santoni et al., 2013, Boyle et al., 2013], as well as our results. The second is based on the sortition approach from Algorand [Chen and Micali, 2019], where only a “small” set of parties are allowed to talk in every round, and includes [Chen and Micali, 2019, Abraham et al., 2019]. The latter approach inherently leads to unbalanced protocols, since parties that are eligible to talk send messages to all other parties.

We note that while [King and Saia, 2009, King et al., 2011, Braud-Santoni et al., 2013, Boyle et al., 2013] and our results hold in the static-corruptions setting, some protocols are resilient to adaptive corruptions.
Assuming secure data erasures (where honest parties can erase some parts of their internal states) $\tilde{O}(\sqrt{n})$-balanced BA [King and Saia, 2011] and $\tilde{O}(1)$-amortized BA [Chen and Micali, 2019] can be achieved against adaptive corruptions. In the erasure-free setting, [Abraham et al., 2019] achieved $\tilde{O}(1)$-amortized BA against adaptive corruptions.
One of the interesting open questions we pose in <ref> is whether $\tilde{O}(1)$-balanced BA can be achieved in the adaptive setting.

§.§ Open Questions

Our results leave open several interesting questions for followup work.

Our constructions of SRDS offer a trade-off between cryptographic assumptions and setup assumptions (indeed, our lower bound indicates that some form of private-coin setup is needed). Is it possible to get the best of both, construct SRDS with bare PKI under standard, falsifiable assumptions? This in turn would imply $\tilde O(1)$-balanced BA from the corresponding computational assumption and setup. Alternatively, does SRDS in a weak setup model require strong computational assumptions: For example, do SRDS with bare PKI imply some kind of succinct non-interactive arguments (SNARGs)?

Taking a step back: Is it possible to achieve $\tilde O(1)$-balanced BA unconditionally? While our SRDS-based approach inherently makes use of computational assumptions (and our lower bound implies this necessity for a one-shot boost from almost-everywhere to everywhere agreement in the PKI model), this leaves open the possibility of removing cryptography via an alternative approach.

Can one further extend the lower bound in this work, identifying a minimal required round complexity for generically converting from almost-everywhere to everywhere agreement within various setup models?

In the $\tilde{O}(1)$-amortized BA setting, known constructions consider stronger security models. Namely, the protocol in Braud-Santoni et al., 2013 is secure against static corruptions (similarly to our protocols); however, no trusted setup assumptions are required. The protocol of Abraham et al., 2019 guarantees security against adaptive corruptions; however, it requires a trusted PKI assumption. In contrast, the protocol of King and Saia, 2011 does not require setup assumptions and is resilient to adaptive corruptions, but it provides suboptimal total communication $\tilde{O}(n\sqrt{n})$. It is very interesting to explore if $\tilde{O}(1)$-balanced BA can be achieved without setup or in the adaptive setting.

Regarding the communication model, the vast majority of sub-quadratic BA protocol are defined in the synchronous model. In the asynchronous setting unbalanced sub-quadratic BA in the trusted PKI model was recently proposed [Cohen et al., 2020, Blum et al., 2020]. We note that balanced sub-quadratic BA is not known even in the partially synchronous model. An interesting question is to expand our techniques beyond the synchronous realm.

Finally, all known BA protocols with $o(n^2)$ total communication follow either the approach of King et al., 2006 or of Chen and Micali, 2019, that are based on electing a polylog-size committee. As such, these protocols only support a non-optimal constant fraction of corruptions. Is it possible to achieve $o(n^2)$ total communication while tolerating the optimal number of corruptions $t<n/2$?

§.§ Paper Organization

In <ref>, we provide basic definitions. SRDS are defined in <ref>. Our BA protocol and the lower bounds appear in <ref>. <ref> presents two constructions of SRDS, and in <ref>, we explore the connection of SRDS based on multi-signatures to succinct non-interactive arguments.
Some of the definitions and proofs are deferred to the appendix.

§ PRELIMINARIES

In this section, we present the security model and the definition of Byzantine agreement. Additional definitions of proof-carrying data systems, of Merkle hash proof systems, and of multi-signatures, can be found in <ref>.

All protocols considered in this paper are PPT (probabilistic polynomial time): the running time of every party is polynomial in the (common) security parameter, given as a unary string. For simplicity, we consider Boolean-input Boolean-output protocols, where apart from the common security parameter, each party has a single input bit, and each of the honest parties outputs a single bit. We note that our protocols can be used for agreement on longer strings, with an additional dependency of the communication complexity on the input-string length.

We consider protocols in the PKI model, and we distinguish between two flavors of PKI: a trusted PKI and a bare PKI. In both settings, a trusted party samples a secret key $\sk_i$ and a public key $\vk_i$, for every $i\in[n]$, from some distribution. The adversary is allowed to corrupt parties adaptively based on $(\vk_1,\ldots,\vk_n)$ and learn the secret key associated with every corrupted party. In the bare-PKI model, the adversary can replace the public key of every corrupted party by an arbitrary string $\vk_i'$ of its choice.

The communication model is synchronous, meaning that protocols proceed in rounds. In each round every party can send a message to every other party over a private channel.[We note that using standard techniques, our constructions can be defined over authenticated channels (that do not provide privacy) by additionally assuming the existence of key-agreement protocols.] It is guaranteed that every message sent in a round will arrive at its destinations by the end of that round. The adversary is rushing in the sense that it can use the messages received by corrupted parties from honest parties in a given round to determine the corrupted parties' messages for that round.

Note that an adversary can always blow up the communication complexity of a protocol by flooding honest parties with many bogus messages. It is therefore standard to count only messages that are actually processed by honest parties. We follow the model of [Boyle et al., 2018], who formalized this intuition. Namely, message receival consists of two phases: a filtering phase, where incoming messages are inspected according to specific filtering rules defined by the protocol, and some messages may be discarded, followed by a processing phase, where the party computes its next-message function based on the remaining non-filtered messages. In practice, the filtering procedure should be “lightweight,” and consist of operations like counting messages or verifying validity of a signature.

In this section, we introduce a new notion of a distributed signature scheme for $n$ parties, which can be used to obtain low-communication BA. As discussed earlier, every party has signing/verification keys based on some form of PKI, and the parties may receive additional setup information consisting of public parameters for the underlying signature scheme and potentially a common random string (CRS).

We allow the adversary to adaptively corrupt a subset of the parties before the protocol begins, based on the setup information and all $n$ verification keys. We consider two PKI models; a bare PKI, where the adversary can choose the corrupted parties' keys, and a trusted PKI, where the keys are honestly generated and cannot be changed. We do not permit adaptive corruptions once the parties start signing messages.

Below, we define the new signature scheme and the security requirements.
Later, in <ref>, we present two constructions offering a tradeoff between cryptographic and setup assumptions: the first assuming one-way functions in the trusted-PKI model and the second assuming CRH and SNARKs with linear extraction in the CRS and bare-PKI model.
In <ref>, we show that a natural approach towards constructing SRDS in an untrusted-PKI model has strong connections to succinct average-case argument systems for certain NP-Complete problems.

§ BALANCED COMMUNICATION-EFFICIENT BYZANTINE AGREEMENT

In this section, we consider Byzantine agreement protocols with $\tilde{O}(1)$ communication per party.
In <ref>, we show how to use (SRDS) to boost almost-everywhere agreement to full agreement in a balanced way via a single communication round.
In <ref>, we show that a similar task cannot be achieved under weaker setup assumptions.

§.§ Balanced Byzantine Agreement from SRDS

We start by showing how to combine (SRDS) with the protocol of [Boyle et al., 2013] to obtain BA with balanced $\tilde{O}(1)$ communication. We prove the following theorem.

Let $\beta<1/3$ and assume existence of a $\beta n$-secure SRDS scheme in the bare-PKI model (trusted PKI model). Then, there exists a $\beta n$-resilient BA protocol (according to <ref>) in a hybrid model for generating the SRDS setup and the relevant PKI, such that:

* The round complexity and communication locality are $\polylog(n)$; every party communicates $\polylog(n)\cdot\poly(\secParam)$ bits.

* The adversary can adaptively corrupt the parties based on the public setup and the PKI before the onset of the protocol. For bare PKI, the adversary can additionally replace the corrupted parties' public keys.

By instantiating <ref> with our SRDS constructions from <ref>, we get the following corollaries.

Let $\beta<1/3$. Assuming OWF, there exists a $\beta n$-resilient BA protocol in the trusted-PKI model with balanced $\tilde{O}(1)$ communication per party.

Let $\beta<1/3$. Assuming CRH and SNARKs with linear extraction, there exists a $\beta n$-resilient BA protocol in the bare PKI and CRS model with balanced $\tilde{O}(1)$ communication per party.

High-level overview.
The protocol is defined in a hybrid model that abstracts the communication tree of [King et al., 2006]. The parties can communicate in a way that mimics almost-everywhere agreement, and the adversary is allowed to isolate a $o(1)$ fraction of the parties. Each party is assigned to $z=O(\log^4n)$ leaf nodes and $\zs=O(\log^5 n)$ parties are assigned to each leaf node in the communication tree. Since each party will send a signature to every leaf node he is assigned to, it is essential to ensure the same fraction of signatures is generated by corrupted parties as their fraction in the party-set.
For this reason, we allocate $z$ “virtual identities” to every party.
The SRDS is used for $n\cdot z$ virtual identities and each party samples separate SRDS keys for each of his virtual identities. These virtual IDs are assigned to the parties in such a way that the virtual IDs associated with the leaf node belong in the range $[(k-1)\cdot \zs+1,k\cdot \zs]$. This ensures that when the tree topology is expressed flat as a planar graph (no crossovers), then the virtual IDs of the leaf nodes are in increasing order. Looking ahead, this property is necessary for robustness, when using our SRDS construction from Section <ref>.

The protocol starts by invoking $\faecomm$ (defined below) to obtain an almost-everywhere-communication tree where each party is assigned to $z$ leaves. The supreme committee members (parties assigned to the root-node) run Byzantine agreement on their inputs to agree on the output $y$ and run a coin-tossing protocol to agree on a random seed $s$. The supreme committee then makes use of the communication-tree to distribute these values to all non-isolated parties. The parties then collectively generate an SRDS signature to certify the pair $(y,s)$.

To compute this signature, each party locally signs the received pair of values; this is done using a different virtual identity for every leaf node corresponding to the party. Each signature is sent to all parties assigned to the corresponding leaf node. For each node in the tree, the assigned parties aggregate the received signatures, while making sure that the maxima and minima of virtual IDs associated with the signatures that they aggregate indeed lie within the range associated with the leaf nodes that have a path to the current node, and propagate them to the node's parent in a recursive way until reaching the root, where the final aggregated signature is computed.

Next, the supreme-committee again uses the communication-tree to distribute this aggregated signature to all non-isolated parties. Each non-isolated party evaluates a PRF on the seed $s$ and its identity to determines a set of parties, to which he sends the pair $(y,s)$ along with the signature. Isolated parties can now verify the signature and be convinced about the correct output $y$.
Here correctness crucially relies on the fact that the adversary could not have forged an aggregated SRDS signature on any other value.

In <ref>, we define the ideal functionalities to be used in the BA protocol and in <ref> we describe the protocol and prove its security. Finally, in <ref>, we present applications of our protocol to broadcast and MPC.

§.§.§ Functionalities used in the Protocol

We start by describing the functionalities used in our construction.

Almost-everywhere communication.
The functionality $\faecomm$ is a reactive functionality that abstracts the properties obtained by the protocol from [King et al., 2006].
In the first invocation, the adversary specifies a special communication tree that allows all honest parties to communicate, except for a $o(1)$ fraction of isolated parties $\DS\subseteq[n]$. In all subsequent calls the “supreme committee,” the parties associated with the root of the tree, can send messages to all of the parties but $\DS$.
We use a slightly modified version of the $(n,\IS)$ defined in <ref>. Specifically, in <ref>, each party was assigned to a single leaf node of the tree. Here, each party in the BA protocol will be assigned to multiple leaf nodes (but will participate in the SRDS aggregation as multiple “virtual” parties, one for each appearance).

Let $\IS\subseteq[n]$ be a subset of size $\beta n$ for a constant $\beta<1/3$.
A directed rooted tree $\tree=(\vertex,\edge)$ is an $(n,\IS)$- if it satisfies the first four properties of an $(n,\IS)$- (<ref>) and additionally, the following properties are satisfied:

* Each leaf node of the tree is assigned a set of $\log^5 n$ parties.

* Each party is assigned to $O(\log^4 n)$ nodes at each level.

As observed in [Boyle et al., 2013], the fact that $1-o(1)$ fraction of the leaves are on good paths to the root implies that for a $1-o(1)$ fraction of the parties, a  majority of the leaf nodes that they are assigned to are good. The protocol of King et al., 2006 securely realizes $\faecomm$ in the authenticated-channels model tolerating a computationally unbounded, malicious adversary statically corrupting $\beta n$ parties, for a constant $\beta<1/3$.
Every invocation requires $\polylog(n)$ rounds, and every party sends and processes $\polylog(n)$ bits. Throughout all invocations, every party sends to, and processes messages received from $\polylog(n)$ other parties.

Byzantine agreement.
We consider the standard Byzantine agreement functionality $\fba$ as defined in <ref> (to be used within small committees in the larger protocol).
Every party sends its input to the trusted party who forwards the input value to the adversary. If more than $n-t$ inputs equal the same value $y\in\zo$, then deliver $y$ as the output for every party. Otherwise, let the adversary choose the value $y\in\zo$ to be delivered.

The $n$-party BA protocol of Garay and Moses, 1993 realizes $\fba$ over authenticated channels tolerating a computationally unbounded, malicious adversary statically corrupting $t<n/3$ parties using $t+1$ rounds and $\poly(n)$ communication complexity.
An immediate corollary is that for $n'=\polylog(n)$, the $n'$-party BA functionality $\fba$ can be instantiated using $\polylog(n)$ rounds and $\polylog(n)$ communication complexity.

Coin tossing.
The coin-tossing functionality $\fct$ samples a uniformly distributed $s\in\zo^\secParam$ and delivers $s$ to all the parties. The protocol of Chor et al., 1985 realizes $\fct$ over a broadcast channel assuming an honest majority (by having each party verifiably secret share (VSS) a random value, and later reconstruct all values and XOR them). By instantiating the broadcast channel using the protocol of [Garay and Moses, 1993], $n'=\polylog(n)$ parties can agree on a random $\secParam$-bit string in $\polylog(n)$ rounds and $\polylog(n)\cdot\poly(\secParam)$ communication.

Signature aggregation.
The signature-aggregation functionality $\faggrsig$ (formally described in <ref>) is an $n'$-party functionality, where every party $\Party_i$ provides a message $m_i$ and a set of signatures.
The functionality first determines the set of signatures received from a majority of the parties and aggregates only those signatures to obtain a new signature $\sigma$, which is delivered as the output for every party.

Note that the inputs to the aggregation procedure are not private, so if the aggregation algorithm $\TSAggr_2$ is deterministic (for example, in the OWF-based SRDS construction in <ref>) the parties simply need to agree on the common set of input signatures $S_\sig$ and locally run $\TSAggr_2$ to obtain the same aggregated signature. To agree on $S_\sig$, each party broadcasts its input signatures and filters-out invalid signatures by running the deterministic algorithm $\TSAggr_1$. However, if the algorithm $\TSAggr_2$ is randomized, it may be the case that security relies on keeping the random coins hidden from the parties. For this reason, after the parties agree on $S_\sig$, we use an MPC protocol to compute the aggregated signature and realize $\faggrsig$.

Assuming the existence of one-way functions, the protocol of Damgård and Ishai, 2005 can be used to realize the $n'$-party functionality $\faggrsig$, for $n'=\polylog(n)$, over secure channels, tolerating a malicious adversary corrupting a minority of the parties.
In addition, if the size of set $S_\sig$ is $\tilde{O}(1)$ the protocol requires $\polylog(n)\cdot\poly(\secParam)$ communication. In our construction, this functionality is used by the parties assigned to a node (in the almost-everywhere communication-tree obtained from $\faecomm$) for aggregating signatures received from parties assigned to their children. From <ref>, we know that each node only has $\log(n)$ child nodes and each node is assigned $\polylog(n)$ parties. Therefore, $\faggrsig$ is only used for aggregating at most $\polylog(n)$ signatures.  Note that in [Damgård and Ishai, 2005] a broadcast channel is also required and the resulting protocol is constant round. For $n'=\polylog(n)$ the broadcast can be realized by a deterministic protocol, from [Garay and Moses, 1993], and the resulting protocol has $\polylog(n)$ rounds and $\polylog(n)\cdot\poly(\secParam)$ communication.

§.§.§ The Byzantine Agreement Protocol

Having defined the ideal functionalities, we are now ready to present our BA protocol in <ref>.
To reduce the security of $\protba$ to that of the SRDS scheme, we will show that by robustness every honest party will receive an accepting signature on $(y,s)$, and by unforgeability, no party will receive an accepting signature on a different value. Before proceeding to the proof, we discuss a subtlety in the reduction.

Recall that robustness of an SRDS scheme ensures that an adversary who after the setup and corruption phase is allowed to choose a message $m$, and the order of aggregation (using a directed rooted tree $\tree$), cannot prevent the honest parties from successfully signing $m$.
Note that if in $\protba$, an adversary can prevent the honest parties from signing $(y,s)$, then we can derive the corresponding tree and partially aggregated signatures of the corrupted parties to break the robustness of the SRDS scheme. Note that here, in the robustness game, we will assume that the total number of parties are $n\cdot z$ (each virtual party in the Byzantine agreement protocol is a real party in the SRDS game) and  $(n,\IS)$- $\tree$ used in the Byzantine agreement protocol is transformed into an $(n\cdot z,\{(i,j)\}_{i\in\IS,j\in[z]})$- by augmenting it with a level 0 comprising of $n\cdot z$ nodes (representing the $n\cdot z$ parties in the SRDS game), and adding an edge between each of these nodes and the leaf node that it (the party that they represent) is assigned to.

Let $\beta<1/3$ and assume the existence of PRF and $\beta n$-secure SRDS in the bare-PKI model (trusted-PKI model). Then, protocol $\protba$ is a $\beta n$-resilient BA protocol in the $(\faecomm,\fba,\fct,\faggrsig)$-hybrid model such that:

* The round complexity and the locality of the protocol are $\polylog(n)$; the number of bits communicated by each party is $\polylog(n)\cdot\poly(\secParam)$.

* The adversary can adaptively corrupt the parties based on the public setup of the SRDS, $\pp$ and $\sset{\vk_{1,1},\ldots,\vk_{n,z}}$ before the onset of the protocol. For bare PKI, the adversary can additionally replace the corrupted parties' public keys.

The proof of <ref> can be found in <ref>.

§.§ Lower Bound on Balanced Byzantine Agreement

In the previous section, we showed how to extend almost-everywhere agreement to full agreement in one round. The minimal setup assumptions used were a bare PKI and CRS. In <ref>, we show the some form of private-coin setup is necessary for this task.[We note that, our lower bound easily extends to the random oracle model, for the sake of simplicity we prove it merely with a CRS setup.]
In <ref>, we show that in the PKI model, where the public/private keys of each party are independently sampled, cryptographic assumptions are further needed.

§.§.§ Lower Bound on Balanced Byzantine Agreement in CRS Model

We denote by $\faecomm^\ast$ a weakened version of the functionality $\faecomm$ (from <ref>) that enables communication between almost all of the parties, except for an isolated set $\DS$ that is randomly chosen by the functionality, rather than by the adversary. The purpose of this adjustment is to provide a stronger lower bound, as the adversary's capabilities are more restricted. In fact, we only require that with some inverse-polynomial probability, there exists a single isolated party that is chosen by the functionality.

Let $\pi$ be a $\beta n$-resilient Byzantine agreement protocol in the $(\fcrs,\faecomm^\ast)$-hybrid model, for $\beta<1$.
Assume that $\pi$ has two parts: the first consists of a polynomial number of rounds where communication is via $\faecomm^\ast$, and the second consists of a single round over channels.
Then, there exists a party that sends $\Theta(n)$ messages in the last round.

§.§.§ Lower Bound on Balanced Byzantine Agreement in PKI Model

We proceed to prove the second lower bound, showing that in the trusted PKI model, where each party receives an independently sampled pair of public/private keys, one-way functions are necessary for extending almost-everywhere agreement to full agreement in a single communication round. Note that a lower bound in the trusted PKI model readily implies a lower bound in weaker PKI models.

Let $\pi$ be a $\beta n$-resilient Byzantine agreement protocol in the trusted PKI and $\faecomm^\ast$-hybrid model, for $\beta<1$.
Assume that $\pi$ has two parts: the first consists of a polynomial number of rounds where communication is via $\faecomm^\ast$, and the second consists of a single round over channels.
Then, if one-way functions do not exist, there exists a party that sends $\Theta(n)$ messages in the last round.

§ CONSTRUCTIONS OF SRDS

In <ref>, we present an SRDS scheme with trusted PKI based on OWF, and in <ref>, an SRDS scheme with bare PKI based on proof-carrying data and CRH.

§ CONNECTION WITH SUCCINCT ARGUMENTS

In <ref>, we showed how to construct SRDS with a strong setup assumption (trusted PKI) from OWF, and with relatively weak setup assumptions (bare PKI) at the expense of strong, non-falsifiable, cryptographic assumptions (SNARKs with linear extractors).
A natural approach towards constructing SRDS that balances the cryptographic and setup assumptions, is to augment a multi-signature scheme with some method of convincing the verifier that sufficiently many parties contributed to the signing process. Indeed, multi-signatures are known to exist under standard falsifiable assumptions in the registered PKI model [Lu et al., 2013]. In this model each party locally generates its own keys (as with bare PKI) but to publish its verification key, the party must prove knowledge of the corresponding secret key, see [Boldyreva, 2003, Lu et al., 2013] and a discussion in [Bellare and Neven, 2006].

In this section, we discuss challenges toward such an approach, by showing that in some cases this necessitates some form of succinct non-interactive arguments.
We begin in <ref> by formalizing the notion of SNARGs for average-case instances of a language, and formalizing the notion of SRDS “based on” multi-signatures. Next, in <ref>, we show that any SRDS based on LOSSW multi-signatures imply SNARGs for average-case instances of the Subset-Product problem. Finally, in <ref>, we explore hardness of various Subset-$f$ problems and their connection to SRDS based on more general multi-signature schemes.

§.§ Average-Case SNARGs and SRDS based on Multi-signatures

Average-Case SNARGs.
We consider a notion of SNARGs for average-case instances of an NP language $\LS$. This constitutes a weaker primitive than standard SNARGs (as per [Bitansky et al., 2017]), which requires soundness against worst-case instances, and may be viewed as a variant of the notion for cryptographically hard languages considered in [Boneh et al., 2018]. An average-case SNARG for a language $\LS$ is parametrized by an efficiently sampleable distribution $\yesD$ over the instance-witness pairs in $\LS$, and an efficiently sampleable distribution $\noD$ over instances outside of $\LS$. In a similar way to regular SNARGs, average-case SNARGs consist of setup, prover, and verification algorithms. Intuitively, given any instance-witness pair $(x,w)$ in $\yesD$, the prover algorithm should output a verifying succinct proof with overwhelming probability. At the same time, it should be hard for an adversary to compute a verifying proof for a random instance $x$ from $\noD$.

Let $\LS$ be an NP language associated with a relation $R_{\LS}$, and let $\yesD$ and $\noD$ be efficiently sampleable distributions over $(x,w)\in R_{\LS}$ and $x\notin\LS$, respectively. A succinct non-interactive argument system $\Pi$ for average-case $\LS$, parametrized by the distributions $(\yesD,\noD)$, is defined by PPT algorithms $(\ProofSetup,\ProofProve,\ProofVerify)$ as follows:

* $\ProofSetup(1^\secParam, 1^n)\to\crs$. On input the security parameter $\secParam$ and the instance size $n$, the setup algorithm outputs a common reference string $\crs$.

* $\ProofProve(\crs, x,w)\to\pi$. On input the $\crs$ and an instance-witness pair $(x,w)\in R_{\LS}$, the prover algorithm outputs a proof $\pi$.

* $\ProofVerify(\crs, x,\pi)\to b$. On input the $\crs$, an instance $x$, and a proof $\pi$, the verification algorithm outputs a bit $b\in\zo$.

We require the argument system to satisfy the following properties:

* Succinctness: $|\pi| = \poly(\log n,\secParam)$ for all $(x,w)\gets\yesD(1^n)$.

* Completeness: For any instance-witness pair $(x,w)$ in the support of $\yesD$, it holds that

\begin{align*}
\pr{\ProofVerify(\crs,x,\pi)=1~\mid~ \crs\gets\ProofSetup(1^\secParam,1^n), \pi\gets\ProofProve(\crs,x,w)}\geq 1-\negl(n,\secParam).
\end{align*}

* Average-Case Soundness: For any non-uniform PPT prover $\PS^\ast$, it holds that

\begin{align*}
\pr{\ProofVerify(\crs,x,\pi)=1~\mid~ \crs\gets\ProofSetup(1^\secParam,1^n), x \gets\noD(1^n), \pi \gets \PS^*(\crs,x)}\leq\negl(n,\secParam).
\end{align*}

SRDS based on multi-signatures.
We consider implications of SRDS constructions based on an underlying multi-signature scheme (see <ref>) in the following sense. While rigorously specifying the notion is rather involved, at a high level, such a  scheme is one that satisfies three natural properties:

* Structure: The aggregate SRDS signature is a pair $(\sigmams,\pi)$, where $\sigmams$ is a multi-signature and $\pi$ is some (small) auxiliary information (of size $\tilde{O}(1)$).

* Completeness: Given a valid multi-signature $\sigmams$ on a message $m$ corresponding to a sufficiently large subset of keys $\sset{\vk_i}_{i\in S}$, together with knowledge of the subset $S$, it is easy to compute a valid SRDS signature certifying $m$.

* Soundness: Given a set of honestly generated verification keys, it is difficult to output a verifying SRDS signature $(\sigmams,\pi)$ on a message $m$ such that the multi-signature $\sigmams$ does not verify on $m$ against any sufficiently large subset of keys.

In order to prove that sufficiently many parties agree on a message $m$, it suffices to certify that there exists an $s$-size subset of parties (where $s$ is sufficiently large) who agree on the same message $m$. Therefore, moving forward for SRDS based on multi-signatures, we only focus on proving that exactly $s$ parties agree on a particular message.
We now formalize SRDS based on multi-signatures.

An SRDS scheme $\Pi=(\TSCR(1^\secParam,1^n),$ $\TSGen,$ $\TSSignShare,$ $\TSAggr,$ $\TSVerify)$ with bare PKI, is  $(\MSSetup,\MSGen,\MSSign,\MSVerify, \MSCombine,\MSMverify)$ if there exists $\subsetsize(n)\in\Theta(n)$, for which the following hold:

* Structure. The SRDS has the following structure:

* $\TSCR(1^\secParam,1^n)$: Outputs public parameters of the form $\ppsrds=(\ppms, \pp_2)$, where $\ppms\gets\MSSetup(1^\secParam)$ and $\pp_2$ are (potentially) additional public parameters.

* $\TSGen(\ppsrds)$: Parses $\ppsrds=(\ppms,\pp_2)$ and outputs $(\sk,\vk)\gets\MSGen(\ppms)$.

* $\TSAggr$: Any SRDS $\sigma$ output by $\TSAggr$ is of the form $(\sigmams,\pi)\in \XSms \times \zo^{\poly(\log n, \secParam)}$, where  $\sigmams\in\XSms$ is a multi-signature (in the support of $\MSCombine$).

* Completeness.
There exists a PPT algorithm $\progP$, such that with overwhelming probability (in $(n,\secParam)$) over honestly sampled $\ppsrds=(\ppms,\pp_2) \gets \TSCR(1^\secParam,1^n)$ and independently sampled verification keys $(\vk_i,\cdot)\gets\TSGen(\ppsrds)$ for $i\in[n]$, the following holds:

Let $m\in\MS$, let $S\subseteq[n]$ of size $\subsetsize(n)$, and let $\sigmams\in\XSms$ be a multi-signature satisfying $\MSMverify(\ppms,\vk_1,\ldots,\vk_n, S,m,\sigmams)=1$. Then, with overwhelming probability (in $(n,\secParam)$) over the auxiliary information $\pi\gets\progP(\ppsrds,\vk_1,\ldots,\vk_n,S,m,\sigmams)$, it holds that $\TSVerify(\ppsrds,\vk_1,\ldots,\vk_n,m,(\sigmams,\pi))=1$.

* Soundness.
Every non-uniform polynomial-time adversary $\Adv$ wins the following experiment with at most negligible probability (in $(n,\secParam)$):

* The challenger samples $\ppsrds=(\ppms,\pp_2) \gets  \TSCR(1^\secParam,1^n)$ and for every $i\in[n]$, sets $(\vk_i,\sk_i)\gets\TSGen(\ppsrds)$.

* The challenger gives the values $(\ppsrds,\vk_1,\ldots,\vk_n)$ and get back $(m, (\sigmams,\pi))$.

* The adversary wins the game if and only if $\TSVerify(\ppsrds,\vk_1,\ldots,\vk_n,m,(\sigmams,\pi))=1$ and, in addition, there does not exist a subset $S\subseteq[n]$ of size $\subsetsize(n)$, such that $\MSMverify(\ppms,\vk_1,\ldots,\vk_n, S,m,\sigmams)=1$.

(Observe that the output of this experiment is not necessarily efficiently computable.)

Note that for our purposes it will suffice to consider soundness against an adversary $\Adv$ who does not have access to a subset of keys $\sset{\sk_i}_{i\in S}$ or to a signing oracle. This is a weaker requirement than a comparable soundness guarantee when given corrupted secret keys, which means a barrier against such primitive is stronger.

§.§ Multi-signatures of Lg and Subset-Product

We proceed to show that any SRDS based on the multi-signature scheme of Lu et al., 2013 (“LOSSW”) as defined above implies SNARGs for a natural average-case version of Subset-Product. Intuitively, an LOSSW multi-signature $\sigma_{\ms}$ for a set of parties $S\subseteq[n]$ is equivalent to a single signature under the product of the verification keys $\prod_{i\in S}\vk_i$. In turn, existence of a large set of approving parties $S$ for $\sigma_{\ms}$ is equivalent to existence of a large set of verification keys $\{\vk_i\}_{i\in S}$ for which $\prod_{i\in S}\vk_i$ takes a particular desired value determined by $\sigma_{\ms}$.

The multi-signature scheme of Lu et al., 2013, is based on the Bilinear Computational Diffie-Hellman (BCDH) assumption, parametrized by a bilinear map $e:\GG\times\GG\to\GG_T$, where $\GG$ and $\GG_T$ are multiplicative cyclic groups of order $p$.
In <ref>, we formally describe the LOSSW multi-signature scheme; their scheme roughly works as follows:

[LOSSW Multi-signatures [Lu et al., 2013]]

* $\MSSetup(1^\secParam)$: The setup algorithm outputs public parameters $\ppms=(\GG, \GG_T, p, g, e)$.

* $\MSGen(1^\secParam)$: The key-generation algorithm outputs a signing key $\sk\in\ZZ_p$, and the corresponding verification key $\vk\in\GG_T$, computed as $e(g,g)^{\sk}$.

* $\MSSign(\ppms,\sk,m)$: There is a deterministic function $\fmsg$ that takes the public parameters $\ppms$ and the message $m\in\MS$ as input and outputs an element in $\GG$ (see <ref> for full specification). Given this $\fmsg$, a signature on $m$ with secret key $\sk$ is generated by sampling $r\gets\ZZ_p$ and computing $\sigma=(\sig_1,\sig_2)$ as follows:

\[
\sig_1=g^\sk\cdot \left(\fmsg(\ppms,m)\right)^r~\text{and}~\sig_2=g^r.
\]

* $\MSCombine(\ppms, \vk_1,\ldots,\vk_n,\sset{\sigma_i}_{i\in S},m)$: Given a set of individual signatures $\sset{\sigma_i}_{i\in S}$ on a message $m\in\MS$, the combine function parses each $\sigma_i$ as $(\sig_1^{(i)},\sig_2^{(i)})$ and computes:

\[
\sig_1=\prod_{i\in S} \sig_1^{(i)}\text{ and }\sig_2=\prod_{i\in S}\sig_2^{(i)}.
\]

The output is the combined multi-signature $\sigmams=(\sig_1,\sig_2)$.

Remark. Recall that $\sig_1^{(i)}$ and $\sig_2^{(i)}$ for each $i\in S$, is of the form
$$\sig_1^{(i)}=g^{\sk_i}\cdot \left(\fmsg(\ppms,m)\right)^{r_i}~\text{and}~\sig_2^{(i)}=g^{r_i}$$

for some $r_i\in\ZZ_p$. Therefore,

\[
\sig_1=g^{\sk^*}\cdot \left(\fmsg(\ppms,m)\right)^{r^*}\text{ and }\sig_2=g^{r^*},
\]

where $\sk^*=\sum_{i\in S}{\sk_i}$ and $r^*=\sum_{i\in S}r_i$. Note that the multi-signature $\sigmams=(\sig_1,\sig_2)$ can now be viewed as an individual signature on $m$ corresponding to secret key $\sk^*$ and randomness $r^*$.

* $\MSMverify(\ppms,\vk_1,\ldots,\vk_n,S,m,\sigmams)$: Given a message $m$, a multi-signature $\sigmams$ and the corresponding set $S$ of verification keys, the verification algorithm outputs 1 if and only if

\[
e(\sig_1,g)\cdot e(\sig_2,\fmsg(\ppms,m))^{-1}=\prod_{i\in S} \vk_{i}.
\]

Note that the same algorithm can be used to verify individual signatures (with $S=\sset{i}$).

Average-case subset-product problem.
We proceed to show a connection between any SRDS based on LOSSW multi-signatures, and the following average-case version of the Subset-Product problem.

Let $\subsetsize=\subsetsize(n)$ be an integer and let $\GG$ be a multiplicative group.
Given an instance $x=(a_1,\ldots,a_n,t)\in \GG^{n+1}$, the  is the problem of deciding if there exists a subset $S\subseteq[n]$ of size $\ssize{S}=\subsetsize$, such that $\prod_{i\in S}a_i=t$. All such instances are said to be in the $(s,\GG)$-Subset-Product language $\LS_{\times}$.

We consider the average-case version of this problem characterized by the following two distributions:

* $\yesD(1^n)\to(x,w)$:
For $i\in[n]$, sample $a_i\in \GG$ uniformly at random. Sample a set $S\subseteq[n]$ of size $\subsetsize$ uniformly at random. Set $t=\prod_{i\in S}a_i$. Output $x=(a_1,\ldots,a_n,t)$ and $w=S$.

* $\noD(1^n)\to x$:
For $i\in[n]$, sample $a_i\in \GG$ uniformly at random. Sample a target $t\in \GG$ uniformly at random. Output $x=(a_1,\ldots,a_n,t)$.

Note that for appropriate parameter regimes, $\noD$ yields instances $(x\notin\LS_{\times})$ with high probability.
For example, consider $s=n/2$ and $\GG=\ZZ_M^*$ for $M=2^{4n}$: the probability that there exists a subset $S$ such that $\prod_{i\in S} a_i$ is equal to a randomly chosen value $t$ is approximately $2^{-2n}$.

Subset-Product is a well-studied problem, with known NP-hardness results in the worst case, and conjectured hardness in the average-case version considered above.

* Hardness of Worst-Case Subset Product:
For $\GG=\ZZ^*_M$ and $s\in\Theta(n)$, the hardness of worst-case $(s,\GG)$-Subset-Product depends on the density $n/\log M$ of the instance. For $M=2^{\Theta(n)}$ ($n/\log M\in\Theta(1)$), there exists $s\in\Theta(n)$ for which the $(\subsetsize,\ZZ^*_M)$-Subset-product is NP-complete [Karp, 1972, Garey and Johnson, 1979, Impagliazzo and Naor, 1996, Lyubashevsky et al., 2010].[The Subset-Sum problem for arbitrary subset-sizes in this parameter regime was amongst the initial 21 problems that were shown to be NP-complete by Karp, 1972. There exists a generic reduction to reduce any instance of 3-SAT to an instance of the Subset-Sum problem for arbitrary subset-sizes. A slight modification to this reduction shows that there exists some $s\in\Theta(n)$ for which $(s,\ZZ_M)$-Subset-Sum problem is also NP-complete. There also exists a generic reduction from any instance of the $(s,\ZZ_M)$-Subset-Sum problem, where $\ZZ_M$ is an additive group of order $M$, to an instance of the $(s,\GG_M)$-Subset-Product problem, where $\GG_M$ is a cyclic multiplicative group of order $M$ (with efficient exponentiation).]

* Hardness of Average-Case Subset Product:
The average-case version of Subset-Product is thought to be computationally hard when $n/\log M$ is constant or even $O(1/\log n)$ [Impagliazzo and Naor, 1996], with the best known algorithms requiring at least $2^{\Omega(n)}$ time. Hardness of distinguishing between distributions $\yesD$ and $\noD$ as above is used (in an indirect way) as a computational hardness assumption in an assortment of cryptographic systems [Impagliazzo and Naor, 1996, Ajtai and Dwork, 1997, Regev, 2003, Regev, 2005, Peikert, 2009, Lyubashevsky et al., 2010].[This follows from the constructions in [Impagliazzo and Naor, 1996, Ajtai and Dwork, 1997, Regev, 2003, Regev, 2005, Peikert, 2009, Lyubashevsky et al., 2010] based on the Subset-Sum problem.]

LOSSW-based SRDS implies SNARGs for average-case Subset-Product.
We now show that an SRDS scheme based on the LOSSW multi-signature scheme implies the existence of SNARGs for average-case Subset-Product over the target group $\GG_T$ for the underlying bilinear map $e:\GG \times \GG \to\GG_T$. Intuitively, the construction takes the following form.

Given an instance $x=(a_1,\ldots,a_n,t)\in\GG_T^{n+1}$ (coming from either $\yesD$ or $\noD$), we will interpret $a_1,\ldots,a_n$ and $a_{n+1}=t^{-1}$ as $n+1$ verification keys $\sset{\vk_i}_{i\in[n+1]}$ for the SRDS scheme. The succinct proof certifying that $x$ is in the language will be an SRDS signature on a message $m\in\MS$ with respect to the set of parties $S\cup\sset{n+1}$ for which $\prod_{i\in S} a_i=t$. The scheme is succinct by construction; the required completeness and average-case soundness properties will hold as follows:

* Completeness: If $x$ was generated as $(x,w)\gets\yesD$ for $w=S\subseteq[n]$, then by definition $\prod_{i\in S}a_i=t$ and consequently $t^{-1}\cdot\prod_{i\in S}a_i=1$. Knowledge of the corresponding set of verification keys thus enables the prover to generate a valid LOSSW multi-signature under these keys, using the trivial $\sk^*=0$ for $\vk^*=\prod_{i\in S\cup\sset{n+1}}\vk_i=1$. By the completeness of the LOSSW-based SRDS (<ref>), the prover can then translate this multi-signature to a valid SRDS.

* Average-case Soundness: On the other hand, if $x$ was generated as $x\gets\noD$, then since $t$ and consequently $t^{-1}$ is uniform conditioned on $a_1,\ldots,a_n$, the resulting verification keys $\sset{\vk_i}_{i\in[n+1]}$ are jointly uniform. Thus (for appropriate parameters $n$ and $\ssize{\GG_T}$), soundness of the argument system holds from the soundness property of the LOSSW-based SRDS (see <ref>).

Assume there exists an SRDS scheme based on the LOSSW multi-signature scheme, where $\TSSetup(1^\secParam,1^n)$ generates $\ppms=(\GG, \GG_T, p, g,e)$, as per <ref>, with $n/\log|\GG_T|<1$. Let $0<\alpha<1$ be a constant and let $s(n)=\alpha \cdot n$.
Then, there exist SNARGs for average-case $(\subsetsize(n),\GG_T)$-Subset-Product (as defined in <ref>).

We construct average-case SNARGs for $(\subsetsize,\GG_T)$-Subset-Product using an SRDS scheme based on the LOSSW multi-signature scheme as per <ref>. Recall that the LOSSW multi-signature scheme is parametrized by a bilinear map $e:\GG\times\GG\to\GG_T$, where $\GG$ and $\GG_T$ are multiplicative cyclic groups of order $p$. Let $\MS$ be the message domain of the LOSSW multi-signature scheme.

* $\ProofSetup(1^\secParam,1^n):$ Run the setup of the SRDS scheme $\ppsrds=(\ppms,\pp_2)\gets\TSSetup(1^\secParam,1^n)$ and output $\crs=\ppsrds$.

* $\ProofProve(\crs,x,w):$
Given an average-case $\yes$ instance-witness pair, $(x,w)\gets\yesD(1^n)$ of the form $x=(a_1,\ldots,a_n,t)$ and $w=S$, proceed as follows:

* Parse $\crs=(\ppms,\pp_2)$ and interpret the set $\sset{a_1,\ldots,a_n,t^{-1}}$ as a set of $(n+1)$ verification keys $\sset{\vk_1,\ldots,\vk_{n+1}}$. Note that $\prod_{i\in S'}\vk_i=1$ for $S'=S\cup\sset{n+1}$.

* Since in the LOSSW multi-signature scheme, (aggregate) verification key $\vk^*=\prod_{i\in S'}\vk_i$ corresponds to a valid signing key $\sk^*=\sum_{i\in S'}\sk_i$, where $\vk^*=e(g,g)^{\sk^*}$, it holds that if $\vk^*=1$, then $\sk^*=0$. Choose an arbitrary $m\in\MS$ and sample $r\gets\ZZ_p$. Compute an LOSSW signature $\sigmams=(\sig_1,\sig_2)$ on $m$ with respect to $\vk^*=1$, where

\[
\sig_1=g^{0}\cdot\left(\fmsg\left(\ppms,m\right) \right)^r \quad \text{ and } \quad \sig_2=g^r.
\]

* Use the algorithm $\progP$ (that is guaranteed to exist by <ref>) to compute the auxiliary information $\pi\gets\progP(\ppsrds,\vk_1,\ldots,\vk_{n+1}, S', m,\sigmams)$ from the signature $\sigmams$ and the set $S'\subseteq[n+1]$.

* Finally output $(m,\sigmams,\pi)$.

* $\ProofVerify(\crs,x,(m,\sigmams,\pi)):$ Parse $x=(a_1,\ldots,a_n,t)$ and proceed as follows:

* Parse $\crs=(\ppms,\pp_2)$ and interpret the set $\sset{a_1,\ldots,a_n,t^{-1}}$ as a set of $(n+1)$ verification keys $\sset{\vk_1,\ldots,\vk_{n+1}}$.

* Run the verification algorithm of the LOSSW multi-signature scheme with respect to combined verification key $\vk^*=1$, parse $\sigmams=(\sig_1,\sig_2)$ and check if

\[
e(\sig_1,g)\cdot e(\sig_2,\fmsg(\ppms,m))^{-1}=1.
\]

In other words, compute

\[
b' = \Bigg\{\begin{array}{lr}
1, \text{ if } e(\sig_1,g)\cdot e(\sig_2,\fmsg(\ppms,m))^{-1}=1\\
0, \text{ otherwise } \\
\end{array}.
\]

* Run the verification algorithm of the SRDS scheme on $(\sigmams,\pi)$ with respect to $m$:

\[
\]

* Output $b\wedge b'$.

We now argue succinctness, completeness, and average-case soundness for this construction:

Succinctness follows from the succinctness of the SRDS scheme.

Given any average-case $\yes$ instance-witness pair $(x,w)\gets\yesD(1^n)$, with $x=(a_1,\ldots,a_n,t)$ and $w=S$, it holds that $\prod_{i\in S} a_{j} =t$ or equivalently $t^{-1}\cdot\prod_{i\in S} a_{j} =1$. Let $S'=S\cup\sset{n+1}$. Recall that in the LOSSW scheme

\[
\prod_{i\in S'} \vk_{i}
= \prod_{i\in S'} e(g,g)^{\sk_{i}}
= e(g,g)^{\sum_{i\in S'} \sk_{i}},
\]

where $\sk_i$ is the secret key associated with $\vk_i$. It follows that if $\prod_{i\in S'} \vk_{i} =1$ then $\sum_{i\in S'} \sk_{i} =0$.
Hence, $\sigmams=\left(\left(\fmsg\left(\ppms,m\right)\right)^r, g^r\right)$ is a valid multi-signature on $m$ with respect to $\sset{\sk_i}_{i\in S'}$.
Since the multi-signature verifies  $\MSMverify(\ppms,\vk_1,\ldots,\vk_{n+1}, S', m, \sigmams)=1$, completeness of SRDS based on a multi-signature scheme (see <ref>) implies that the output of $\progP$, given this signature and $S'$, will be a valid SRDS signature.

Average-Case Soundness.
Recall that each of the values $(a_1,\ldots,a_n,t)$ in $x\gets\noD(1^n)$ are sampled uniformly at random. Since  $t$ is a randomly sampled value, so is $t^{-1}$. Therefore, the verification keys $\sset{\vk_1,\ldots,\vk_n,\vk_{n+1}}$, where $\vk_i=a_i$ for $i\in[n]$ and $\vk_{n+1}=t^{-1}$, are uniformly distributed over $\GG_T^{n+1}$.
Since by assumption, $n/\log |\GG_T|<1$, it holds with overwhelming probability (bounded by ${2^{n+1}}/{|\GG_T|}$) that there does not exist a subset $S'\subseteq[n+1]$ of size $\subsetsize+1$, such that $\prod_{i\in S'}\vk_i=1$.

Given $(m,\sigmams,\pi)$, we check if: (1) $\sigmams$ is a valid multi-signature on $m$ with respect to $\vk^*=1$, and (2) if $(\sigmams,\pi)$ is a valid SRDS on $m$. Recall that given a multi-signature $\sigma_{\ms}=(\sig_1,\sig_2)$, a message $m$, the public parameters $\pp_{\ms}$, and a set of verification keys $\{\vk_i\}_{i\in S}$, the verification algorithm of the LOSSW multi-signature scheme checks if

\[
e(\sig_1,g)\cdot e(\sig_2,\fmsg(\ppms,m))^{-1}=\prod_{i\in S} \vk_{i}.
\]

In other words, given a valid multi-signature $\sigma_{\ms}$ on a message $m$, there exists a unique aggregate verification key $\prod_{i\in S} \vk_{i}$ for which $\sigma_{\ms}$ verifies. Therefore, if check (1) goes through, then $\vk^*=1$ is the only aggregate verification key for which $\sigma_{\ms}$ is a valid multi-signature on $m$. As argued earlier, with a high probability there does not exist a subset $S'\subseteq[n+1]$ such that $\Pi_{i\in S'}\vk_i=1$. Also, from the soundness of SRDS based on a multi-signature scheme (<ref>), we know that if there does not exist a subset $S'\subseteq[n+1]$ of size $s+1$, such that $\sigmams$ is a valid multi-signature on $m$ with respect to $\sset{\vk_i}_{i\in S'}$, then the probability of an adversary computing a valid SRDS $(\sigmams,\pi)$ on a message $m$ is negligible. Soundness now follows from the soundness of SRDS based on a multi-signature scheme.

§.§ General Multi-Signatures and the Subset-Lg Problem

Although the proof of <ref> depends on the specific LOSSW multi-signature scheme, the overall approach only depends on certain properties of that scheme; in particular, there is no inherent reliance on the structure of multiplication of keys and Subset-Product.
Motivated by this observation, in this section, we start by exploring hardness of Subset-$f$ problems for a more general class of functions $f$, focusing on the class of elementary symmetric polynomials $\phi_{\ell}$. We begin by demonstrating (worst-case) NP-hardness results for Subset-$\phi_{\ell}$. We then abstract out the properties used in <ref> (deemed “SNARG-compliance”), and show that existence of SRDS based on a SNARG-compliant multi-signature scheme implies existence of SNARGs for corresponding Subset-$\phi_{\ell}$ problems.

The Subset-$f$ problem.
We first define the following analogous variant of average-case Subset-Product problem for more general functions $f$. We restrict our attention to the natural setting of symmetric functions $f$; one can extend to arbitrary $f$, given a canonical ordering of inputs.

Let $\subsetsize=\subsetsize(n)$ be an integer, let $R$ be a ring, and let $f:R^\subsetsize\to R$ an efficiently computable symmetric function.
Given an instance $x=(a_1,\ldots,a_n,t)\in R^{n+1}$, the  is the problem of deciding if there exists a subset $S\subseteq[n]$ of size $\ssize{S}=\subsetsize$, such that $f((a_i)_{i\in S})=t$.
Such instances are said to be in the $(s,R)$-Subset-$f$ language $\LS_f$.

We consider the average-case version of this problem characterized by the following two distributions:

* $\yesD(1^n)\to(x,w)$: For each $i\in[n]$, sample $a_i\in R$ uniformly at random. Sample a set $S\subseteq[n]$ of size $\subsetsize$ uniformly at random. Set $t=f((a_i)_{i\in S})$.  Output $x=(a_1,\ldots,a_n,t)$, $w=S$.

* $\noD(1^n)\to x$:  For each $i\in[n]$, sample $a_i\in R$ uniformly at random. Sample a target $t\in R$ uniformly at random. Output $x=(a_1,\ldots,a_n,t)$.

We also consider a variant of the $(s,R)$-Subset-$f$ problem,  where the instance does not include the size of the subset, given an instance $x=(a_1,\ldots,a_n,t)\in R^{n+1}$, the $R$-Subset-$f$ problem is the problem of deciding if there exists a subset $S\subseteq[n]$ of any size such that $f((a_i)_{i\in S})=t$.

Note that Subset-$f$ is within NP for any function $f$ describable by a polynomial-size circuit. For appropriate parameter regimes, the hardness of Subset-$f$ problems depends on the function $f$. In <ref> below, we show that for rings (of appropriate size) with Hadamard product, Subset-$f$ for all elementary symmetric polynomials $f$ is NP-complete.

NP-hardness of Subset-$\phi_{\ell}$. Recall that Hadamard product (also known as entry-wise product) takes two vectors of the same dimension and produces another vector of matching dimension where the element of the resulting vector is a product of the elements of the two input vectors.

Let $\field$ be a field and let $\vec{a}=(a_1\ldots,a_n),\vec{b}=(b_1\ldots,b_n)\in \field^n$ be vectors of length $n$. The  of $\vec{a}$ and $\vec{b}$ is the vector $\vec{a}\odot \vec{b}=(a_1 b_1,\ldots, a_n b_n)\in \field^n$.

We now define elementary symmetric polynomials.

Let $n\in\NN$ and $\ell\in[n]$.
The elementary symmetric polynomial $\phi_\ell(x_1,\ldots,x_n)$ is defined as:

\[
\phi_\ell(x_1,\ldots,x_n)=\sum_{1\leq j_1<\ldots< j_\ell\leq n} x_{j_1}\cdot\ldots\cdot x_{j_\ell}.
\]

In the following theorem, we show that for certain rings $R$ that admit Hadamard product, and any elementary symmetric polynomial $\phi_\ell$, the $(\subsetsize,R)$-Subset-$\phi_\ell$ problem is NP-complete. In particular, we show this for suitably sized rings of the form $R=\field^n$, where for $\ell=2$, the characteristic of the field must be at least 63 and for $\ell>2$, the characteristic of the field must be at least $\ell+2$.

There exists $\subsetsize(n)\in\Theta(n)$ such that, for any field $\field$ with $\characteristic(\field)\geq \indexMax(\ell+2,63)$, any ring $R=\field^n$ of size $\ssize{R}=2^{\Theta(n)}$ with Hadamard product, and any elementary symmetric polynomial $\phi_\ell$, the $(\subsetsize,R)$-Subset-$\phi_\ell$ problem is NP-complete.

We next present a high-level overview of the proof; the full proof can be found in <ref>. We start with a recap of the proof for NP-completeness of subset sum by Karp, 1972.

NP-completeness of Subset Sum.
The  proof for NP-completeness of $\ZZ_M$-Subset-Sum [Karp, 1972][Recall that this is a variation of the $(s,\ZZ_M)$-Subset-sum problem, where the instance does not include the size of the subset, as defined in <ref>.] shows a polynomial-time reduction from 3-SAT. At a high level, the reduction proceeds as follows: Given a 3-SAT instance with $N$ variables $\sset{x_i}_{i\in[N]}$ and $m$ clauses $\sset{C_j}_{j\in[m]}$, define a $\ZZ_M$-Subset-Sum instance with the following $2(N+m)$ numbers, each with $N+m$ digits, for $M\geq 10^{N+m}$:

* For each input $i\in[N]$, define two numbers $v_i$ and $v_i'$. The least significant digit of both these numbers is set to 1.  If $x_i\in C_j$, then the (N+j) least significant digit of $v_i$ is set to 1, else if $\neg x_i\in C_j$, then the (N+j) least significant digit of $v'_i$ is set to 1. The remaining digits in both these numbers are set to 0.

* For each clause $j\in[m]$, define two numbers $c_j^1$ and $c^2_j$. The (N+j) least significant digit of both these numbers is set to 1 and all the remaining digits are set to 0.

* The target number $t$ is also an $(N+m)$-digit number in which the first $N$ digits are set to 1, while the remaining digits are set to 3.

Intuitively, given a satisfying assignment for the 3-SAT instance, the corresponding witness for the $\ZZ_M$-Subset-sum instance includes the following: For each $i\in[N]$, it includes $v_i$ if $x_i=1$, and $v_i'$ if $x_i=0$. For each $j\in[m]$, it includes any one of $c^1_j$ or $c_j^2$ if there are two literals with value 1 in the clause, and both $c^1_j$ or $c_j^2$ if there is only one literal with a value of 1 in the clause.

We extend this reduction to show that $R$-Subset-$\phi_\ell$ for $\ell>1$ is also NP-complete, where $R$ is a ring of appropriate size with Hadamard product.
Each of the $a_i$ (for $i\in[n]$) elements and the target value $t$ in an instance of $R$-Subset-$\phi_{\ell}$ is an element in $R$ and thereby a vector of elements in $\field$. Unlike simple addition, since $\phi_{\ell}$ is a sum of products, if (any) entry in the target value is a non-zero element in $\field$, the solution to a  $\yes$ instance of $R$-Subset-$\phi_{\ell}$ must consist of at least $\ell$ elements with  non-zero entries.
Therefore, depending on $\ell$, we need to define additional elements in the reduction.
We give an overview of our reduction from any 3-SAT instance to $R$-Subset-$\phi_\ell$ for $\ell\geq 3$; the special case of $\ell=2$ requires a slight modification that is addressed in <ref>. In a similar way to Subset-Sum, this reduction can also be adjusted to show that there exists $s\in\Theta(n)$, for which $(s,R)$-Subset-$\phi_\ell$ problem is also NP-complete, which is sketched in <ref>.

Given a 3-SAT instance with $N$ variables $\sset{x_i}_{i\in[N]}$ and $m$ clauses $\sset{C_j}_{j\in[m]}$, define a $R$-Subset-$\phi_{\ell}$ instance with $\ell+2N+(\ell-1) m$ elements, where $R=\field^{1+N+m}$. As shown in <ref>, each of these elements is a vector of $1+N+m$ elements in the field $\field$ and are defined as follows:

* An element $\alpha_0\in R$, whose first entry is 1. All the remaining entries in $\alpha_0$ correspond to 0.

* For each $k\in[\ell-1]$, define $\alpha_k\in R$, whose first $N+1$ entries correspond to 1, and the remaining entries correspond to 0.

* For each $i\in[N]$, define two elements $v_i\in R$ and $v_i'\in R$. The (1+i) entry of both these numbers is set to 1. If $x_i\in C_j$, then the (1+N+j) entry of $v_i$ is set to 1, else if $\neg x_i\in C_j$, then the (1+N+j) entry of $v'_i$ is set to 1. All the remaining entries correspond to 0.

* For each $j\in[m]$ and $k\in[\ell-1]$, define element $c_j^k\in R$. The (1+N+j) entry in $c_j^k$ corresponds to 1 and the remaining entries correspond to 0.

* The target element $t$ is also a vector of $1+N+m$ elements in $\field$, with all its entries set to 1.

Now, given a satisfying assignment for the 3-SAT instance, the corresponding witness for the $R$-Subset-$\phi_\ell$ instance includes the following: It includes $\alpha_0$ and each $\alpha_k$ for $k\in[\ell-1]$. For each $i\in[N]$, it includes $v_i$ if $x_i=1$, and $v_i'$ if $x_i=0$. For each $j\in[m]$, it includes any $\ell-3$ of the elements $c_j$ if all three literals in the clause have value 1, else if any two literals have value 1 then it includes any $\ell-2$ of the elements $c_j$ and if only one of the literals has value 1 then all the $\ell-1$ elements $c_j$ are included in the witness. This guarantees that the value 1 appears precisely $\ell$ times in the column of each satisfied clause, so that $\phi_{\ell}$ will evaluate to the target value 1 in these positions.

Similarly for soundness, a valid witness $S$ for the $R$-Subset-$\phi_\ell$ instance must include $a_0,\ldots,a_{\ell-1}$ in order to get $\ell$ times the value 1 in the first column. Apart from $a_1,\ldots,a_{\ell-1}$, the only other elements that have the value 1 in the next $N$ columns are $v_i$ and $v'_i$. For each $i\in[N]$, if both $v_i$ and $v'_i$ are included in the set $S$, a total of $\ell+1$ elements in $S$ will have value 1 in the (i+1) column. The (i+1) entry in the result obtained by applying $\phi_{\ell}$ over such a set is $\ell+1$. Since the characteristic of the field $\field$ is at least $\ell+2$, we know that $\ell+1\neq 1$.
Therefore, $S$ can either contain $v_i$ (implying $x_i=1$) or $v'_i$ (implying $\neg x_i=1$) for each $i\in[N]$, but not both.  For each of the last $m$ columns, $S$ can contain some or all of the elements $c_j$ (for each $j\in[m]$). But since this set of $c_j$ elements can only contribute at most $\ell-1$ times the value 1 in the (1+N+j) column,
we need at least one of the $v$ or $v'$ elements to contribute a 1 value to that column, in order to get a non-zero (1+N+j) entry in the result of $\phi_{\ell}$.
This guarantees at least one variable with a value of 1 in each clause. We give a full proof of completeness and soundness for this reduction <ref>.

SNARG-compliant multi-signatures and Subset-$\phi_\ell$.  We now identify the properties of the LOSSW multi-signature scheme used in <ref> to provide the connection with average-case SNARGs. Roughly, these properties are:

* Verification keys are sampled independently and uniformly from the key-space of the multi-signature scheme. This property is important for arguing soundness in <ref>.

* The verification algorithm with keys $\sset{\vk_i}_{i\in S}$, is equivalent to the verification algorithm with a single aggregate key $\vkagg=\prod_{i\in S}\vk_i$. In other words, there exists a key-aggregation function $\fagg$ ($\fagg=\prod$ in the LOSSW multi-signature scheme), such that the verification algorithm can be decomposed into first applying $\fagg$ over the set of keys to obtain an aggregate key $\vkagg$ and then running some residual function $\MSVerifyAgg$ to perform the remaining verification with respect to $\vkagg$.

* Given a valid multi-signature $\sigma_{\ms}$ on a message $m$, there exists a unique and well-defined aggregate key $\vk$ for which the residual function $\MSVerifyAgg$ (as defined in the previous bullet) outputs 1. Moreover, this aggregate key is easy to compute. For example, for LOSSW, this property is crucially used for arguing soundness in <ref>.

* And finally, there exist degenerate keys $\skdeg$ and $\vkdeg$ ($\skdeg=0\in\GG$ and $\vkdeg=1\in\GG_T$ in the LOSSW multi-signature scheme) that allow forging a multi-signature on any message. This property is used in the completeness argument in <ref>.

We call multi-signature schemes that satisfy these properties as SNARG-compliant multi-signature schemes. We formally define this notion in <ref> in <ref>.
Finally, by using the properties of a SNARG-compliant multi-signature scheme, we are able to prove a generalized version of <ref>. Namely, we show in <ref> that an SRDS scheme based on a SNARG-compliant multi-signature scheme with key-aggregation function $\fagg=\phi_{\ell}$, implies SNARGs for average-case Subset-$\phi_{\ell}$.

E. Boyle’s research is supported in part by ISF grant 1861/16 and AFOSR Award FA9550-17-1-0069 and ERC project HSS (852952).
R. Cohen’s research is supported in part by NSF grant 1646671.
A. Goel’s work was done in part while visiting the FACT Center at IDC Herzliya, Israel. Her research is supported in part by an NSF CNS grant 1814919, NSF CAREER award 1942789 and Johns Hopkins University Catalyst award.

[Abraham et al., 2019]
I. Abraham, T. H. Chan, D. Dolev, K. Nayak, R. Pass, L. Ren, and E. Shi.
Communication complexity of Byzantine agreement, revisited.
In Proceedings of the 38th Annual ACM Symposium on Principles
of Distributed Computing (PODC), pages 317–326, 2019a.

[Abraham et al., 2019]
I. Abraham, S. Devadas, D. Dolev, K. Nayak, and L. Ren.
Synchronous Byzantine agreement with expected O(1) rounds,
expected o(n\({}^{\mbox{2)}}\) communication, and optimal resilience.
In Financial Cryptography and Data Security, pages 320–334,

[Ajtai and Dwork, 1997]
M. Ajtai and C. Dwork.
A public-key cryptosystem with worst-case/average-case equivalence.
In Proceedings of the 29th Annual ACM Symposium on Theory of
Computing (STOC), pages 284–293, 1997.

[Asharov et al., 2012]
G. Asharov, A. Jain, A. López-Alt, E. Tromer, V. Vaikuntanathan, and
D. Wichs.
Multiparty computation with low communication, computation and
interaction via threshold FHE.
In 31st Annual International Conference on the Theory and
Applications of Cryptographic Techniques (EUROCRYPT), pages 483–501, 2012.

[Barak and Goldreich, 2008]
B. Barak and O. Goldreich.
Universal arguments and their applications.
SIAM Journal on Computing, 380 (5):0
1661–1694, 2008.

[Bellare and Neven, 2006]
M. Bellare and G. Neven.
Multi-signatures in the plain public-key model and a general forking
In Proceedings of the 13th ACM Conference on Computer and
Communications Security (CCS), pages 390–399, 2006.

[Ben-Or et al., 1988]
M. Ben-Or, S. Goldwasser, and A. Wigderson.
Completeness theorems for non-cryptographic fault-tolerant
distributed computation (extended abstract).
In Proceedings of the 20th Annual ACM Symposium on Theory of
Computing (STOC), pages 1–10, 1988.

[Ben-Sasson et al., 2014]
E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza.
Scalable zero knowledge via cycles of elliptic curves.
In 33rd Annual International Cryptology Conference (CRYPTO),
part II, pages 276–294, 2014.

[Bitansky et al., 2013]
N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer.
Recursive composition and bootstrapping for SNARKs and
proof-carrying data.
In Proceedings of the 45th Annual ACM Symposium on Theory of
Computing (STOC), pages 111–120, 2013.

[Bitansky et al., 2017]
N. Bitansky, R. Canetti, A. Chiesa, S. Goldwasser, H. Lin, A. Rubinstein, and
E. Tromer.
The hunting of the SNARK.
Journal of Cryptology, 300 (4):0 989–1066,

[Blum et al., 2020]
E. Blum, J. Katz, C. Liu-Zhang, and J. Loss.
Asynchronous Byzantine agreement with subquadratic communication.
In Proceedings of the 18th Theory of Cryptography Conference
(TCC), part I, pages 353–380, 2020.

[Boldyreva, 2003]
A. Boldyreva.
Threshold signatures, multisignatures and blind signatures based on
the gap-Diffie-Hellman-group signature scheme.
In Proceedings of the 6th International Conference on the
Theory and Practice of Public-Key Cryptography (PKC), pages 31–46, 2003.

[Boldyreva et al., 2007]
A. Boldyreva, C. Gentry, A. O'Neill, and D. H. Yum.
Ordered multisignatures and identity-based sequential aggregate
signatures, with applications to secure routing.
In Proceedings of the 14th ACM Conference on Computer and
Communications Security (CCS), pages 276–285, 2007.

[Boneh et al., 2003]
D. Boneh, C. Gentry, B. Lynn, and H. Shacham.
Aggregate and verifiably encrypted signatures from bilinear maps.
In 22nd International Conference on the Theory and Applications
of Cryptographic Techniques (EUROCRYPT), pages 416–432, 2003.

[Boneh et al., 2018]
D. Boneh, M. Drijvers, and G. Neven.
Compact multi-signatures for smaller blockchains.
In 24th International Conference on the Theory and Application
of Cryptology and Information Security (ASIACRYPT), part II, pages
435–464, 2018a.

[Boneh et al., 2018]
D. Boneh, Y. Ishai, A. Sahai, and D. J. Wu.
Quasi-optimal SNARGs via linear multi-prover interactive proofs.
In 37th Annual International Conference on the Theory and
Applications of Cryptographic Techniques (EUROCRYPT), part III, pages
222–255, 2018b.

[Boyle et al., 2013]
E. Boyle, S. Goldwasser, and S. Tessaro.
Communication locality in secure multi-party computation - how to run
sublinear algorithms in a distributed setting.
In Proceedings of the 10th Theory of Cryptography Conference
(TCC), pages 356–376, 2013.

[Boyle et al., 2015]
E. Boyle, K. Chung, and R. Pass.
Large-scale secure computation: Multi-party computation for
(parallel) RAM programs.
In 34th Annual International Cryptology Conference (CRYPTO),
part II, pages 742–762, 2015.

[Boyle et al., 2018]
E. Boyle, R. Cohen, D. Data, and P. Hubáček.
Must the communication graph of MPC protocols be an expander?
In 38th Annual International Cryptology Conference (CRYPTO),
part III, pages 243–272, 2018a.

[Boyle et al., 2018]
E. Boyle, A. Jain, M. Prabhakaran, and C. Yu.
The bottleneck complexity of secure multiparty computation.
In Proceedings of the 45th International Colloquium on
Automata, Languages, and Programming (ICALP), pages 24:1–24:16,

[Braud-Santoni et al., 2013]
N. Braud-Santoni, R. Guerraoui, and F. Huc.
Fast Byzantine agreement.
In Proceedings of the 32th Annual ACM Symposium on Principles
of Distributed Computing (PODC), pages 57–64, 2013.

[Canetti, 2000]
R. Canetti.
Security and composition of multiparty cryptographic protocols.
Journal of Cryptology, 130 (1):0 143–202,

[Canetti, 2001]
R. Canetti.
Universally Composable Security: A New Paradigm for Cryptographic
In Proceedings of the 42nd Annual Symposium on Foundations of
Computer Science (FOCS), pages 136–145, 2001.

[Canetti, 2004]
R. Canetti.
Universally composable signature, certification, and authentication.
In 17th IEEE Computer Security Foundations Workshop,
(CSFW), page 219, 2004.

[Canetti et al., 2016]
R. Canetti, D. Shahaf, and M. Vald.
Universally composable authentication and key-exchange with global
In Proceedings of the 19th International Conference on the
Theory and Practice of Public-Key Cryptography (PKC), part II, pages
265–296, 2016.

[Chan et al., 2019]
T. H. Chan, R. Pass, and E. Shi.
Consensus through herding.
In 38th Annual International Conference on the Theory and
Applications of Cryptographic Techniques (EUROCRYPT), part I, pages
720–749, 2019.

[Chan et al., 2020]
T. H. Chan, R. Pass, and E. Shi.
Sublinear-round Byzantine agreement under corrupt majority.
In Proceedings of the 23rd International Conference on the
Theory and Practice of Public-Key Cryptography (PKC), part II, pages
246–265, 2020.

[Chandran et al., 2015]
N. Chandran, W. Chongchitmate, J. A. Garay, S. Goldwasser, R. Ostrovsky, and
V. Zikas.
The hidden graph model: Communication locality and optimal resiliency
with adaptive faults.
In Proceedings of the 6th Annual Innovations in Theoretical
Computer Science (ITCS) conference, pages 153–162, 2015.

[Chaum and van Heyst, 1991]
D. Chaum and E. van Heyst.
Group signatures.
In 10th Workshop on the Theory and Applications of
Cryptographic Techniques (EUROCRYPT), pages 257–265, 1991.

[Chaum et al., 1988]
D. Chaum, C. Crépeau, and I. Damgård.
Multiparty unconditionally secure protocols (extended abstract).
In Proceedings of the 20th Annual ACM Symposium on Theory of
Computing (STOC), pages 11–19, 1988.

[Chen and Micali, 2019]
J. Chen and S. Micali.
Algorand: A secure and efficient distributed ledger.
Theoretical Computer Science, 777:0 155–183, 2019.

[Chiesa and Tromer, 2010]
A. Chiesa and E. Tromer.
Proof-carrying data and hearsay arguments from signature cards.
In Innovations in Computer Science - ICS, pages 310–331,

[Chor et al., 1985]
B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch.
Verifiable secret sharing and achieving simultaneity in the presence
of faults (extended abstract).
In Proceedings of the 17th Annual ACM Symposium on Theory of
Computing (STOC), pages 383–395, 1985.

[Cohen, 2016]
R. Cohen.
Asynchronous secure multiparty computation in constant time.
In Proceedings of the 19th International Conference on the
Theory and Practice of Public-Key Cryptography (PKC), part II, pages
183–207, 2016.

[Cohen et al., 2019]
R. Cohen, S. Coretti, J. A. Garay, and V. Zikas.
Probabilistic termination and composability of cryptographic
Journal of Cryptology, 320 (3):0 690–741,

[Cohen et al., 2019]
R. Cohen, I. Haitner, N. Makriyannis, M. Orland, and A. Samorodnitsky.
On the round complexity of randomized Byzantine agreement.
In Proceedings of the 33rd International Symposium on
Distributed Computing (DISC), pages 12:1–12:17, 2019b.

[Cohen et al., 2021]
R. Cohen, S. Coretti, J. A. Garay, and V. Zikas.
Round-preserving parallel composition of probabilistic-termination
cryptographic protocols.
Journal of Cryptology, 340 (2):0 12, 2021.

[Cohen et al., 2020]
S. Cohen, I. Keidar, and A. Spiegelman.
Not a COINcidence: Sub-quadratic asynchronous Byzantine agreement
In Proceedings of the 34th International Symposium on
Distributed Computing (DISC), pages 25:1–25:17, 2020.

[Coretti et al., 2016]
S. Coretti, J. A. Garay, M. Hirt, and V. Zikas.
Constant-round asynchronous multi-party computation based on one-way
In 22nd International Conference on the Theory and Application
of Cryptology and Information Security (ASIACRYPT), part II, volume 10032,
pages 998–1021, 2016.

[Damgård and Ishai, 2005]
I. Damgård and Y. Ishai.
Constant-round multiparty computation using a black-box pseudorandom
In 24th Annual International Cryptology Conference (CRYPTO),
pages 378–394, 2005.

[Damgård and Ishai, 2006]
I. Damgård and Y. Ishai.
Scalable secure multiparty computation.
In 25th Annual International Cryptology Conference (CRYPTO),
pages 501–520, 2006.

[Damgård and Nielsen, 2007]
I. Damgård and J. B. Nielsen.
Scalable and unconditionally secure multiparty computation.
In 26th Annual International Cryptology Conference (CRYPTO),
pages 572–590, 2007.

[Damgård et al., 2008]
I. Damgård, Y. Ishai, M. Krøigaard, J. B. Nielsen, and A. D. Smith.
Scalable multiparty computation with nearly optimal work and
In 27th Annual International Cryptology Conference (CRYPTO),
pages 241–261, 2008.

[Damgård et al., 2010]
I. Damgård, Y. Ishai, and M. Krøigaard.
Perfectly secure multiparty computation and the computational
overhead of cryptography.
In 29th Annual International Conference on the Theory and
Applications of Cryptographic Techniques (EUROCRYPT), pages 445–465, 2010.

[Damgård et al., 2012]
I. Damgård, S. Faust, and C. Hazay.
Secure two-party computation with low communication.
In Proceedings of the 9th Theory of Cryptography Conference
(TCC), pages 54–74, 2012.

[Dani et al., 2017]
V. Dani, V. King, M. Movahedi, J. Saia, and M. Zamani.
Secure multi-party computation in large networks.
Distributed Computing, 300 (3):0 193–229,

[Desmedt and Frankel, 1989]
Y. Desmedt and Y. Frankel.
Threshold cryptosystems.
In 8th Annual International Cryptology Conference (CRYPTO),
pages 307–315, 1989.

[Dolev, 1982]
D. Dolev.
The Byzantine generals strike again.
J. Algorithms, 30 (1):0 14–30, 1982.

[Dolev and Reischuk, 1985]
D. Dolev and R. Reischuk.
Bounds on information exchange for Byzantine agreement.
Journal of the ACM, 320 (1):0 191–204, 1985.

[Dwork et al., 1988]
C. Dwork, D. Peleg, N. Pippenger, and E. Upfal.
Fault tolerance in networks of bounded degree.
SIAM Journal on Computing, 170 (5):0
975–988, 1988.

[Fischer et al., 1986]
M. J. Fischer, N. A. Lynch, and M. Merritt.
Easy impossibility proofs for distributed consensus problems.
Distributed Computing, 10 (1):0 26–39, 1986.

[Garay and Moses, 1993]
J. A. Garay and Y. Moses.
Fully polynomial Byzantine agreement in t+1 rounds.
In Proceedings of the 25th Annual ACM Symposium on Theory of
Computing (STOC), pages 31–41, 1993.

[Garey and Johnson, 1979]
M. R. Garey and D. S. Johnson.
Computers and Intractability: A Guide to the Theory of
W. H. Freeman & Co., New York, NY, USA, 1979.
ISBN 0716710447.

[Gennaro et al., 2001]
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin.
Robust threshold DSS signatures.
Information and Computation, 1640 (1):0
54–84, 2001.

[Gentry and Wichs, 2011]
C. Gentry and D. Wichs.
Separating succinct non-interactive arguments from all falsifiable
In Proceedings of the 43rd Annual ACM Symposium on Theory of
Computing (STOC), pages 99–108, 2011.

[Goldreich, 2004]
O. Goldreich.
Foundations of Cryptography – VOLUME 2: Basic Applications.
Cambridge University Press, 2004.

[Goldreich et al., 1987]
O. Goldreich, S. Micali, and A. Wigderson.
How to play any mental game or a completeness theorem for protocols
with honest majority.
In Proceedings of the 19th Annual ACM Symposium on Theory of
Computing (STOC), pages 218–229, 1987.

[Gupta and Sahai, 2014]
D. Gupta and A. Sahai.
On constant-round concurrent zero-knowledge from a knowledge
In INDOCRYPT, pages 71–88, 2014.

[Harchol et al., 2018]
Y. Harchol, I. Abraham, and B. Pinkas.
Distributed SSH key management with proactive RSA threshold
In Proceedings of the 16th International Conference on Applied
Cryptography and Network Security (ACNS), pages 22–43, 2018.

[Hohenberger and Waters, 2018]
S. Hohenberger and B. Waters.
Synchronized aggregate signatures from the RSA assumption.
In 37th Annual International Conference on the Theory and
Applications of Cryptographic Techniques (EUROCRYPT), part II, pages
197–229, 2018.

[Holtby et al., 2008]
D. Holtby, B. M. Kapron, and V. King.
Lower bound for scalable Byzantine agreement.
Distributed Computing, 210 (4):0 239–248,

[Impagliazzo and Luby, 1989]
R. Impagliazzo and M. Luby.
One-way functions are essential for complexity based cryptography
(extended abstract).
In Proceedings of the 30th Annual Symposium on Foundations of
Computer Science (FOCS), pages 230–235, 1989.

[Impagliazzo and Naor, 1996]
R. Impagliazzo and M. Naor.
Efficient cryptographic schemes provably as secure as subset sum.
Journal of Cryptology, 90 (4):0 199–216,

[Itakura and Nakamura, 1983]
K. Itakura and K. Nakamura.
A public-key cryptosystem suitable for digital multisignatures.
NEC Research & Development, 71:0 1–8, 1983.

[Karp, 1972]
R. M. Karp.
Reducibility among combinatorial problems.
In Proceedings of a symposium on the Complexity of Computer
Computations, pages 85–103, 1972.

[Katz and Koo, 2006]
J. Katz and C. Koo.
On expected constant-round protocols for Byzantine agreement.
In 25th Annual International Cryptology Conference (CRYPTO),
pages 445–462, 2006.

[Kidron and Lindell, 2011]
D. Kidron and Y. Lindell.
Impossibility results for universal composability in public-key
models and with fixed inputs.
Journal of Cryptology, 240 (3):0 517–544,

[King and Saia, 2009]
V. King and J. Saia.
From almost everywhere to everywhere: Byzantine agreement with
$\tilde{O}(n^{3/2})$ bits.
In Proceedings of the 23th International Symposium on
Distributed Computing (DISC), pages 464–478, 2009.

[King and Saia, 2011]
V. King and J. Saia.
Breaking the $O(n^2)$ bit barrier: scalable Byzantine agreement
with an adaptive adversary.
Journal of the ACM, 580 (4):0 18:1–18:24,

[King et al., 2006]
V. King, J. Saia, V. Sanwalani, and E. Vee.
Scalable leader election.
In Proceedings of the 17th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 990–999, 2006.

[King et al., 2011]
V. King, S. Lonargan, J. Saia, and A. Trehan.
Load balanced scalable Byzantine agreement through quorum building,
with full information.
In Proceedings of the 12th International Conference on
Distributed Computing and Networking (ICDCN), pages 203–214, 2011.

[Lamport, 1979]
L. Lamport.
Constructing digital signatures from a one way function.
Technical Report CSL-98, SRI International, 1979.

[Lamport et al., 1982]
L. Lamport, R. E. Shostak, and M. C. Pease.
The Byzantine generals problem.
ACM Transactions on Programming Languages and Systems,
40 (3):0 382–401, 1982.

[Lee et al., 2013]
K. Lee, D. H. Lee, and M. Yung.
Sequential aggregate signatures made shorter.
In Proceedings of the 11th International Conference on Applied
Cryptography and Network Security (ACNS), pages 202–217, 2013.

[Libert et al., 2016]
B. Libert, M. Joye, and M. Yung.
Born and raised distributively: Fully distributed non-interactive
adaptively-secure threshold signatures with short shares.
Theoretical Computer Science, 645:0 1–24, 2016.

[Lindell et al., 2006]
Y. Lindell, A. Lysyanskaya, and T. Rabin.
On the composition of authenticated Byzantine agreement.
Journal of the ACM, 530 (6):0 881–917, 2006.

[Lu et al., 2013]
S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters.
Sequential aggregate signatures, multisignatures, and verifiably
encrypted signatures without random oracles.
Journal of Cryptology, 260 (2):0 340–373,

[Lysyanskaya et al., 2004]
A. Lysyanskaya, S. Micali, L. Reyzin, and H. Shacham.
Sequential aggregate signatures from trapdoor permutations.
In 23rd International Conference on the Theory and Applications
of Cryptographic Techniques (EUROCRYPT), pages 74–90, 2004.

[Lyubashevsky et al., 2010]
V. Lyubashevsky, A. Palacio, and G. Segev.
Public-key cryptographic primitives provably as secure as subset sum.
In Proceedings of the 7th Theory of Cryptography Conference
(TCC), pages 382–400, 2010.

[Merkle, 1989]
R. C. Merkle.
A certified digital signature.
In 8th Annual International Cryptology Conference (CRYPTO),
pages 218–238, 1989.

[Micali, 1994]
S. Micali.
CS proofs (extended abstracts).
In Proceedings of the 35th Annual Symposium on Foundations of
Computer Science (FOCS), pages 436–453, 1994.

[Micali et al., 1999]
S. Micali, M. O. Rabin, and S. P. Vadhan.
Verifiable random functions.
In Proceedings of the 40th Annual Symposium on Foundations of
Computer Science (FOCS), pages 120–130, 1999.

[Micali et al., 2001]
S. Micali, K. Ohta, and L. Reyzin.
Accountable-subgroup multisignatures: extended abstract.
In Proceedings of the 8th ACM Conference on Computer and
Communications Security (CCS), pages 245–254, 2001.

[Nielsen, 2002]
J. B. Nielsen.
A threshold pseudorandom function construction and its applications.
In 21st Annual International Cryptology Conference (CRYPTO),
pages 401–416, 2002.

[Pease et al., 1980]
M. C. Pease, R. E. Shostak, and L. Lamport.
Reaching agreement in the presence of faults.
Journal of the ACM, 270 (2):0 228–234, 1980.

[Peikert, 2009]
C. Peikert.
Public-key cryptosystems from the worst-case shortest vector problem:
extended abstract.
In Proceedings of the 41st Annual ACM Symposium on Theory of
Computing (STOC), pages 333–342, 2009.

[Rabin, 1998]
T. Rabin.
A simplified approach to threshold and proactive RSA.
In 17th Annual International Cryptology Conference (CRYPTO),
pages 89–104, 1998.

[Rabin and Ben-Or, 1989]
T. Rabin and M. Ben-Or.
Verifiable secret sharing and multiparty protocols with honest
majority (extended abstract).
In Proceedings of the 30th Annual Symposium on Foundations of
Computer Science (FOCS), pages 73–85, 1989.

[Regev, 2003]
O. Regev.
New lattice based cryptographic constructions.
In Proceedings of the 35th Annual ACM Symposium on Theory of
Computing (STOC), pages 407–416, 2003.

[Regev, 2005]
O. Regev.
On lattices, learning with errors, random linear codes, and
In Proceedings of the 37th Annual ACM Symposium on Theory of
Computing (STOC), pages 84–93, 2005.

[Rivest et al., 2001]
R. L. Rivest, A. Shamir, and Y. Tauman.
How to leak a secret.
In 7th International Conference on the Theory and Application
of Cryptology and Information Security (ASIACRYPT), pages 552–565, 2001.

[Shoup, 2000]
V. Shoup.
Practical threshold signatures.
In 19th International Conference on the Theory and Applications
of Cryptographic Techniques (EUROCRYPT), pages 207–220, 2000.

[Valiant, 2008]
P. Valiant.
Incrementally verifiable computation or proofs of knowledge imply
time/space efficiency.
In Proceedings of the 5th Theory of Cryptography Conference
(TCC), pages 1–18, 2008.

[Wan et al., 2020]
J. Wan, H. Xiao, S. Devadas, and E. Shi.
Round-efficient Byzantine broadcast under strongly adaptive and
majority corruptions.
In Proceedings of the 18th Theory of Cryptography Conference
(TCC), part I, pages 412–456, 2020a.

[Wan et al., 2020]
J. Wan, H. Xiao, E. Shi, and S. Devadas.
Expected constant round Byzantine broadcast under dishonest
In Proceedings of the 18th Theory of Cryptography Conference
(TCC), part I, pages 381–411, 2020b.

[Yao, 1982]
A. C. Yao.
Protocols for secure computations (extended abstract).
In Proceedings of the 23rd Annual Symposium on Foundations of
Computer Science (FOCS), pages 160–164, 1982.

[Zamani et al., 2014]
M. Zamani, M. Movahedi, and J. Saia.
Millions of millionaires: Multiparty computation in large networks.
IACR Cryptology ePrint Archive, 2014:0 149, 2014.

[Abraham et al., 2019]
I. Abraham, T. H. Chan, D. Dolev, K. Nayak, R. Pass, L. Ren, and E. Shi.
Communication complexity of Byzantine agreement, revisited.
In Proceedings of the 38th Annual ACM Symposium on Principles
of Distributed Computing (PODC), pages 317–326, 2019a.

[Abraham et al., 2019]
I. Abraham, S. Devadas, D. Dolev, K. Nayak, and L. Ren.
Synchronous Byzantine agreement with expected O(1) rounds,
expected o(n\({}^{\mbox{2)}}\) communication, and optimal resilience.
In Financial Cryptography and Data Security, pages 320–334,

[Ajtai and Dwork, 1997]
M. Ajtai and C. Dwork.
A public-key cryptosystem with worst-case/average-case equivalence.
In Proceedings of the 29th Annual ACM Symposium on Theory of
Computing (STOC), pages 284–293, 1997.

[Asharov et al., 2012]
G. Asharov, A. Jain, A. López-Alt, E. Tromer, V. Vaikuntanathan, and
D. Wichs.
Multiparty computation with low communication, computation and
interaction via threshold FHE.