# Concurrent Asynchronous Byzantine Agreement
in Expected-Constant Rounds, Revisited††thanks: This is the full version of a
paper that appeared at _TCC 2023_. The proceedings version is available at
https://doi.org/10.1007/978-3-031-48624-1_16.

Ran Cohen Efi Arazi School of Computer Science, Reichman University. E-mail:
<EMAIL_ADDRESS>Pouyan Forghani Department of Computer Science and
Engineering, Texas A&M University. E-mail:
<EMAIL_ADDRESS>Juan Garay‡ Rutvik Patel‡ Vassilis
Zikas Department of Computer Science, Purdue University. E-mail:
<EMAIL_ADDRESS>
###### Abstract

It is well known that without randomization, Byzantine agreement (BA) requires
a linear number of rounds in the synchronous setting, while it is flat out
impossible in the asynchronous setting. The primitive which allows to bypass
the above limitation is known as _oblivious common coin_ (OCC). It allows
parties to agree with constant probability on a random coin, where agreement
is oblivious, i.e., players are not aware whether or not agreement has been
achieved.

The starting point of our work is the observation that no known protocol
exists for information-theoretic multi-valued OCC—i.e., OCC where the coin
might take a value from a domain of cardinality larger than 2—with optimal
resiliency in the asynchronous setting (with eventual message delivery). This
apparent hole in the literature is particularly problematic, as multi-valued
OCC is implicitly or explicitly used in several constructions. (In fact, it is
often falsely attributed to the asynchronous BA result by Canetti and Rabin
[STOC ’93], which, however, only achieves binary OCC and does not translate to
a multi-valued OCC protocol.)

In this paper, we present the first information-theoretic multi-valued OCC
protocol in the asynchronous setting with optimal resiliency, i.e., tolerating
$t<n/3$ corruptions, thereby filling this important gap. Further, our protocol
efficiently implements OCC with an exponential-size domain, a property which
is not even achieved by known constructions in the simpler, synchronous
setting.

We then turn to the problem of round-preserving parallel composition of
asynchronous BA. A protocol for this task was proposed by Ben-Or and El-Yaniv
[Distributed Computing ’03]. Their construction, however, is flawed in several
ways: For starters, it relies on multi-valued OCC instantiated by Canetti and
Rabin’s result (which, as mentioned above, only provides binary OCC). This
shortcoming can be repaired by plugging in our above multi-valued OCC
construction. However, as we show, even with this fix it remains unclear
whether the protocol of Ben-Or and El-Yaniv achieves its goal of expected-
constant-round parallel asynchronous BA, as the proof is incorrect. Thus, as a
second contribution, we provide a simpler, more modular protocol for the above
task. Finally, and as a contribution of independent interest, we provide
proofs in Canetti’s Universal Composability framework; this makes our work the
first one offering composability guarantees, which are important as BA is a
core building block of secure multi-party computation protocols.

###### Contents

  1. 1 Introduction
    1. 1.1 Concurrent A-BA in Expected-Constant Rounds: Cracks in the Concrete
    2. 1.2 Overview of Our Results
    3. 1.3 Additional Related Work
    4. 1.4 Organization of the Paper
  2. 2 Model and Preliminaries
    1. 2.1 UC Basics
    2. 2.2 Modeling Eventual Message Delivery in UC
  3. 3 Ideal Functionalities for a Few Standard Primitives
    1. 3.1 Modeling Delayed Participation
    2. 3.2 Ideal Functionalities for a Few Standard Primitives
  4. 4 Asynchronous Oblivious Common Coin
    1. 4.1 A-OCC Ideal Functionality
    2. 4.2 The A-OCC Protocol
    3. 4.3 Security Proof
  5. 5 Concurrent A-BA in Expected-Constant Rounds
    1. 5.1 Concurrent A-BA Ideal Functionality
    2. 5.2 The Simplified Concurrent A-BA Protocol
    3. 5.3 Security Proof
  6. A Attack on Ben-Or and El-Yaniv’s Select Protocol
    1. A.1 Static Attack
    2. A.2 Adaptive Attack
  7. B The Asynchronous Turpin-Coan Extension

##  1 Introduction

_Byzantine agreement_ (BA) [74, 67] enables $n$ parties to reach agreement on
one of their inputs in an adversarial setting, facing up to $t$ colluding and
cheating parties. The core properties require all honest parties to eventually
terminate with the same output (_agreement_), which equals their input value
in case they all begin with the same common input (_validity_). BA and its
closely related single-sender variant, _broadcast_ , are fundamental building
blocks in the construction of cryptographic protocols, in particular for
_secure multi-party computation_ (MPC) [81, 56, 12, 22], in which parties wish
to privately compute a joint function over their inputs.

We consider a complete network of authenticated and private point-to-point
(P2P) channels, which enables every pair of parties to communicate directly.
The central settings in which BA has been studied are:

The _synchronous_ setting.

Here the protocol proceeds in a round-by-round fashion, and messages sent in a
given round are guaranteed to be delivered by the start of the next round. The
round structure can be achieved given synchronized clocks and a known bound on
message delivery, and enables the use of _timeouts_. This clean abstraction
allows for simpler analyses of protocols, but comes at the cost that parties
must wait for the worst-case delay in each round before they can proceed.

The _asynchronous_ setting.

Here no assumptions are made on the clocks or on the bound of message delivery
(other than that each message will be eventually delivered), and messages may
be adversarially delayed by an arbitrary (yet finite) amount of time. The main
challenge is that timeouts cannot be used, implying the inability to
distinguish a slow honest party from a silent, noncooperative corrupted party.
On the positive side, asynchronous protocols can advance as fast as the
network allows, irrespectively of the worst-case delay, and each party can
proceed to the next step as soon as it gets sufficiently many messages.

The _feasibility_ of BA is inherently related to the synchrony assumptions of
the system. Synchronous BA with _perfect_ security is achievable with
deterministic protocols for $t<n/3$ [74, 11, 55]; this bound is tight in the
plain model111That is, without setup assumptions and without imposing resource
restrictions on the adversary. even when considering weaker, computational
security [74, 46, 15], but can be overcome with setup assumptions, yielding
computationally secure BA [37], and even information-theoretically secure BA
[75], for $t<n/2$.222The bound $t<n/2$ is tight for BA [44]; however, under
the same setup assumptions, broadcast can be solved for any number of
corruptions. On the other hand, deterministic asynchronous BA (A-BA) is
impossible even facing a single crash failure [47], and randomized solutions
are a necessity. Following Ben-Or [10] and Rabin [76], information-theoretic
randomized A-BA has been achieved with $t<n/3$ corruptions [16, 34, 3], which,
as opposed to the synchronous case, is a tight bound even given setup and
cryptographic assumptions [36, 18].

#### Round complexity of BA.

In the synchronous setting, it is known that _deterministic_ BA requires $t+1$
rounds [45, 37], a bound that is matched by early feasibility results [74, 37,
55]. It is also known that $t$-secure randomized BA for $t\in\Theta(n)$ cannot
terminate in a _strict_ constant number of rounds [30, 62, 32]; yet,
_expected_ constant-round protocols have been constructed both for $t<n/3$ in
the plain model [50] and for $t<n/2$ in the PKI model [42, 60].333Fitzi and
Garay [42] devised expected-constant-round BA for $t<n/2$ in the PKI model
under number-theoretic assumptions. Katz and Koo [60] established a similar
result from the minimal assumption of digital signatures, which yields an
information-theoretic variant using pseudo-signatures [75]. The latter
protocols follow the approach of Rabin [76] and rely on an _oblivious common
coin_ (OCC), that is, a distributed coin-tossing protocol over a domain $V$
such that the output of every honest party is a common random value $v\in V$
with constant probability $p$, but with probability $1-p$ is independently and
adversarially chosen; the coin toss is “oblivious” since the parties cannot
distinguish between a successful coin toss and an adversarial one.444This
primitive is sometimes known as a “weak” common coin in the literature.

Loosely speaking, round complexity in the asynchronous setting can be defined
based on the expected number of times an honest party has to alternate between
sending and receiving messages that are “causally related” [25]. In an
unpublished manuscript, Feldman [41] generalized the expected-constant-round
synchronous protocol of [48] to asynchronous networks with $t<n/4$; at the
core of the construction lies a binary (asynchronous) OCC protocol which
actually has resiliency $\min(t^{\prime},\lceil n/3\rceil-1)$, where
$t^{\prime}$ is the corruption threshold of an _asynchronous verifiable secret
sharing_ (A-VSS) scheme.555Feldman’s A-VSS suffers from a negligible error
probability. An _errorless_ A-VSS scheme for $t<n/4$ is given in [7] and used
to construct a _perfectly_ secure asynchronous MPC protocol with resiliency
$t<n/4$. Canetti and Rabin [34] constructed A-VSS for $t<n/3$, thereby
obtaining A-BA in expected-constant rounds for the optimal threshold $t<n/3$.

#### Concurrent BA.

All of the above constructions are for solving a _single_ instance of BA.
However, most applications, particularly MPC protocols, require composing
multiple instances of BA: sequentially, in parallel, or concurrently. While
the composition of synchronous, deterministic protocols is relatively simple
(although care must be taken in the cryptographic setting [65]), composing
expected-constant-round protocols with probabilistic termination is a much
more challenging task.

Indeed, Ben-Or and El-Yaniv [8, 9] observed that running $m$ instances of a
probabilistic-termination protocol in parallel may incur a blow-up in the
expected number of rounds until they all terminate. The technical reason is
that the expectation of the maximum of $m$ independent, identically
distributed random variables does not necessarily equal the maximum of their
expectations. In particular, for expected-constant-round BA with a geometric
termination probability (which is the case in all known protocols), the
parallel composition of $m$ instances terminates after expected $\Theta(\log
m)$ rounds [23]. Further, even when all parties start the protocol together,
simultaneous termination is not guaranteed as the adversary can force some
honest parties to terminate after the others; although this gap can be reduced
to a single round, inaccurate sequential re-synchronization of $\ell$
instances of BA may lead to an exponential blow up in $\ell$ if not done with
care [64]. Following [9, 64, 65, 60], recent works have shown how to compose
synchronous BA in a round-preserving way with simulation-based security in
Canetti’s framework for universal composability (UC) [21], with optimal
resiliency and _perfect_ security in the plain model for $t<n/3$ [23], and
with cryptographic security in the PKI model for $t<n/2$ [24].

In the asynchronous setting, the parties are not assumed to begin the protocol
at the same time, so intuitively, sequential composition is not problematic.
However, running $m$ instances of expected-constant-round A-BA concurrently
would yield a $\Theta(\log m)$ blowup as in the synchronous case. Ben-Or and
El-Yaniv [9] further showed how to execute $m$ instances of A-BA in expected-
constant rounds and with optimal resiliency $t<n/3$; however, their solution
is more complicated than the synchronous one. In addition, they only prove a
property-based security definition of A-BA that does not necessarily address
modern security requirements such as security under composition, or facing
adaptive adversaries.

###  1.1 Concurrent A-BA in Expected-Constant Rounds: Cracks in the Concrete

The underlying idea behind the synchronous protocol of Ben-Or and El-Yaniv [9]
for parallel BA is to execute each BA instance multiple times over the same
inputs, but only for a constant number of rounds. For a suitable choice of
parameters, this ensures that with high probability each party will have
obtained at least one output value in each such batch. To coordinate these
outputs, the parties then run an _oblivious leader election_ (OLE) protocol,
which guarantees that with constant probability, a random leader is elected.
In the event that the leader is honest and the parties obtained an output in
each batch (which, again, occurs with constant probability) the parties will
terminate; otherwise they repeat the process.

The same general technique underlies Ben-Or and El-Yaniv’s asynchronous
protocol, but great care is needed to deal with the low message dispersion
inherent in asynchronous networks while maintaining optimal resiliency
$t<n/3$. A closer look at their security proof indeed raises a number of
subtle issues. First, they point to Canetti and Rabin [34] for instantiating
the (asynchronous) OLE primitive used in their construction (called _A-
Election()_). (Recall that Canetti and Rabin construct an OCC to obtain A-BA
in expected-constant rounds; an $n$-valued OCC would indeed imply OLE.) As it
turns out, the OCC construction in [34, Sec. 8] (as well as the more detailed
versions in [20, Sec. 5.7] and [35, Sec. 8]) is only _binary_ (i.e., it only
works for $V=\\{0,1\\}$), and it does not seem straightforward to generalize
to larger (non-constant-sized) domains.

Further, running $\log n$ executions of a binary OCC, with agreement
probability $p$, in parallel to make it multi-valued yields only $p^{\log
n}\in 1/\mathsf{poly}(n)$ probability of agreement, and as long as the coin is
not _perfectly_ fair (i.e., guaranteeing that all honest parties output $0$
with probability $1/2$, and $1$ with probability $1/2$, which is impossible in
the asynchronous setting [38]), that would not imply OLE with constant success
probability. We can also consider a different type of “strong” common coin:
one which achieves arbitrarily small bias, possibly with guaranteed agreement.
Such an $\epsilon$-biased binary coin would in fact achieve arbitrarily small
bias even when run in parallel, and there are even known protocols for this
task that simultaneously enjoy almost-sure termination and optimal resiliency
($t<n/3$) [4], but these coins do not have constant round complexity, since at
the very least there will be a dependence on $\epsilon$.666The protocol in [4]
actually incurs an additional overhead of several factors of $n$, due to its
use of ACS and almost-surely terminating A-BA.

We note that Patra et al. [73] claim to construct a $(t+1)$-bit asynchronous
OCC, but their main focus is on communication complexity, and the agreement
probability of their protocol is no better than would be obtained by running
$t+1$ executions of a binary OCC protocol (i.e., exponentially small).
Techniques used to get OLE in the synchronous setting [48, 60] do not seem to
extend in asynchrony for $t<n/3$ (we elaborate on this in Section 1.2). Thus,
to the best of our knowledge, no existing OCC construction is _simultaneously_
optimally resilient, multi-valued, and asynchronous, without relying on
computational assumptions (in Section 1.3 we discuss solutions in the
cryptographic setting).

Second, there is a subtle issue in the logic of one of the proofs in [9]. This
issue raises concerns about the validity of the proof claiming an expected-
constant round complexity of one of the main subroutines—namely, the
$\Pi_{\mathsf{select}}$ subroutine, which handles the shortcomings of their
message-distribution mechanism. Specifically, in the analysis of
$\Pi_{\mathsf{select}}$ it is claimed that if the leader is chosen from a
certain set, the protocol will terminate. However, further examination reveals
that there are scenarios in which the protocol may not terminate for certain
leaders from that set. As a result, this issue casts doubt on the promised
expected-constant round complexity of their concurrent A-BA protocol. (Refer
to Appendix A for more details on this issue.)

Finally, the concurrent asynchronous (resp., synchronous) BA protocol in [9]
relies on _multi-valued_ asynchronous (resp., synchronous) BA in expected-
constant rounds.777This is true even if one is interested only in _binary_
concurrent BA (i.e., when the input vectors consist of bits). Multi-valued BA
is needed to agree on the leader’s output vector. Recall that running the
binary protocols in [50] or [34] $\omega(1)$ times in parallel would terminate
in expected $\omega(1)$ rounds, so they cannot be naïvely used for this task.
In the synchronous setting, Turpin and Coan [78] extended binary BA to multi-
valued BA for $t<n/3$ with an overhead of just two rounds. Ben-Or and El-Yaniv
claim that this technique can be adapted for asynchronous networks by using
Bracha’s “A-Cast” primitive [16] for message distribution. However, a closer
look reveals that although the Turpin-Coan extension works (with appropriate
modifications) in the asynchronous setting for $t<n/5$, it provably does not
work when $t\geq n/5$, regardless of the specific choice of the underlying
binary A-BA protocol and even when the adversary is limited to static
corruptions (see Appendix B).

More recently, an optimally resilient multi-valued A-BA protocol with
expected-constant round complexity was proposed by Patra [72], but it relies
on the _Agreement on a Common Subset_ (ACS) protocol in [14]; however, as we
explain below, this ACS protocol does not achieve expected-constant round
complexity without some modifications, which require either expected-constant-
round concurrent A-BA (this would be circular), or information-theoretic
asynchronous OLE with optimal resiliency. Fortunately, Mostéfaoui and Raynal
[70] recently gave a black-box, constant-round reduction from multi-valued to
binary A-BA for $t<n/3$,888They are also concerned with obtaining $O(n^{2})$
message complexity. The novelty of their result, even without this more
stringent requirement, does not seem to be acknowledged in the paper. using
just one invocation of the underlying binary protocol as in [78].

We emphasize that the asynchronous protocol of Ben-Or and El-Yaniv [8, 9]
lies, either explicitly or implicitly, at the core of virtually every round-
efficient asynchronous MPC construction [7, 14, 57, 13, 58, 31, 25, 19, 63].
The concerns raised above regarding the result of [9] render this extensive
follow-up work unsound. In this paper, we revisit this seminal result and
rectify these issues.

###  1.2 Overview of Our Results

We now present an overview of our results, which are three-fold, including a
detailed exposition of our techniques.

#### Multi-valued and asynchronous oblivious common coin.

As a starting point, we look at the _binary_ asynchronous OCC protocol of
Canetti and Rabin [34]. The idea (following the approach of [50] in the
synchronous setting and [41] in the asynchronous setting) is that each party
secret-shares a random vote for each party, using an optimally resilient A-VSS
scheme. Each party accepts $t+1$ of the votes cast for him (at least one of
which must have come from an honest party), and once it is determined that
enough secrets have been fixed (based on several rounds of message exchange,
using Bracha’s A-Cast primitive [16] for message distribution), the parties
begin reconstructing the accepted votes. The sum or “tally” of these votes
becomes the value associated with the corresponding party. After computing the
values associated with an appropriate set of at least $n-t$ parties, an honest
party outputs $0$ if at least one of those tallies is $0$, and outputs $1$
otherwise. Note that each tally must be uniformly random, and the properties
of A-Cast guarantee that no two honest parties can disagree on the value of
any given tally (although up to $t$ tallies may be “missing” in an honest
party’s local view); moreover, Canetti and Rabin show using a counting
argument that at least $n-2t>n/3$ of the tallies are known to all honest
parties (i.e., common to their local views).999An enhanced version of this
counting argument, using the “Gather” protocol of Abraham et al. [5], can be
used to increase the size of this intersection to $n-t>2n/3$. This can be used
to show that with probability at least $1/4$ all honest parties output $0$,
and similarly for $1$.

In the conference version of Feldman and Micali’s paper [48], there is a brief
remark suggesting that the synchronous version of the above protocol can be
modified to obtain (oblivious) leader election.101010This claim no longer
appears in the ICALP [49] or journal [50] versions of the paper, or in
Feldman’s thesis [40]. Rather than outputting a bit, parties output the index
of the party whose tally is minimum; when the domain of secrets is large
enough, with constant probability the same _honest_ party is chosen. This
approach was fully materialized by Katz and Koo [60] for $t<n/3$ in the
information-theoretic setting and $t<n/2$ in the computational setting. We
note that what is obtained is not exactly OLE as we have defined it, as the
adversary can of course bias the index of the elected party, but nevertheless,
this is sufficient for the concurrent BA protocols of Ben-Or and El-Yaniv [9].

Unfortunately, the approach effective in the synchronous setting cannot be
directly applied in the asynchronous setting while maintaining optimal
resiliency. The challenge arises from the fact that the adversary can
selectively remove $t$ coordinates from the honest parties’ local views of the
tallies, ensuring that the leader is not chosen from the parties corresponding
to those missing coordinates. This poses a significant obstacle as the
original concurrent A-BA protocol by Ben-Or and El-Yaniv [9] terminates
successfully when the leader is honest and selected from an adversarially
chosen subset of $n-2t$ parties. Consequently, when $t<n/3$, the size of this
subset is only $t+1$, allowing the adversary to reduce the probability of
choosing an appropriate leader to as low as $\frac{1}{n-t}$. The same issue
arises in our simplified concurrent A-BA protocol, where we also require the
leader to be selected from an adversarially chosen subset of parties with size
$n-2t$. Again, when $t<n/3$, this subset can be of size $t+1$, leading to the
same challenge. However, when $t<n/4$, the set of potential appropriate
leaders becomes larger in both concurrent A-BA protocols, enabling us to
circumvent this issue. Therefore, in addition to the inherent value in
obtaining a true OCC (where a successful coin toss produces a uniform value),
we specifically need such a primitive to obtain optimal resiliency for
concurrent A-BA.

In summary, no OLE construction—and therefore no concurrent A-BA protocol in
expected-constant rounds—exists with optimal resiliency $t<n/3$ in
asynchronous networks. We now describe our solution to this problem, which is
based on the following simple combinatorial observation. If we work over a
field of size $N\in\Theta(n^{2})$, then with _constant_ probability, at least
one value will be repeated in the global view of tallies, and, moreover, all
repeats will occur within the subset of indices known to all honest parties.
The intuition for this fact is that when $N\in O(n^{2})$ there is, due to the
birthday paradox, at least one repeat in any constant fraction of the indices
with constant probability, and when $N\in\Omega(n^{2})$, there are no repeats
at all with constant probability. There is a “sweet spot” between these
extremes that can be leveraged to extract shared randomness: Honest parties
output the value that is repeated in their local views of the tallies and has
the minimum index in the vector of tallies. With this modification of Canetti
and Rabin’s protocol [34], we obtain the first $n^{2}$-valued asynchronous OCC
for $t<n/3$ in the information-theoretic setting. We remark that the above
combinatorial observation at the heart of our construction may be of
independent interest.

It is straightforward to extend our OCC protocol to accommodate arbitrary
domains $V$. One approach is to work over a prime field of size at least
$\mathrm{lcm}(n^{2},|V|)$. In this setting, we can still identify “repeats” by
considering the tallies modulo $n^{2}$. Once the repeat with minimum index is
determined, we can generate a common random output by reducing the
corresponding (original) field element modulo $|V|$. In particular, when
$|V|=n$, we get asynchronous OLE with optimal resiliency.

Proving the security of our multi-valued OCC protocol in a _simulation-based_
manner is not without its own challenges. The issue is that the simulator must
expose a view of the vector of tallies that both adheres to the distribution
in the real world and is consistent with the random value chosen by the OCC
functionality (in the case of a successful coin toss) in the ideal world.
While the simulator can easily determine the exact set of indices known to all
honest parties from its internal execution with the real-world adversary,
properly sampling the “repeat pattern” according to these constraints is a
delicate task; furthermore, since the functionality is only parameterized by a
(constant) lower bound on the probability of a successful coin toss, the
simulator must handle the complementary case carefully in order to avoid
skewing the distribution. It is not immediately clear how to perform this
inverse sampling efficiently.

A heavy-handed solution is to simply have the functionality sample the tallies
itself, and then determine the output based on the location of repeats
relative to the subset of indices (supplied by the simulator) that are known
to all honest parties. This protocol-like functionality would certainly allow
for simulation—and would in fact be sufficient for our purposes—but its
guarantees are more difficult to reason about and, more importantly, it cannot
be realized by other protocols! Instead, we construct a simulator that, given
the exact probabilities of certain events in the protocol, can also
efficiently sample from those events, potentially conditioned on the output of
a successful coin toss. By selecting the appropriate sampling procedure, the
simulator can derive a vector of tallies that preserves the (perfect)
indistinguishability of the real and ideal worlds. Equipped with the means to
carry out the inverse sampling, we can now realize a more abstract (and
natural) OCC functionality, which is ready to be plugged into higher-level
protocols.

#### Simplified concurrent A-BA.

Ben-Or and El-Yaniv [9] devised an expected-constant-round concurrent A-BA
protocol. However, in addition to relying on unspecified building blocks, as
mentioned above, it suffers from logical issues in its proof. Although our new
OCC protocol can instantiate the missing primitive, doubts remain about the
expected-constant round complexity due to a lingering issue in the proof. This
issue stems from the steps taken to address low message dispersion, and the
possibility of resolving it without changing the protocol is unclear. To
tackle this, we redesign the message-distribution phase, avoiding the problem
in the proof and obtaining stronger guarantees. These guarantees simplify the
protocol structure, achieving a level of simplicity comparable to the
synchronous solution.

In more detail, we build on Ben-Or and El-Yaniv’s work, where parties initiate
multiple executions for each A-BA instance that are “truncated” after a fixed
number of iterations. However, we adopt a different approach to message
distribution, allowing us to establish the rest of the protocol based on the
simpler structure of their synchronous solution. Similarly to [9], we set
parameters to ensure that each party receives at least one output from each
batch of truncated A-BA executions (for each instance) with constant
probability. Based on their local results from those truncated A-BAs, parties
create suggestions for the final output. Subsequently, the message-
distribution phase begins with parties running a binary A-BA to verify a
precondition, ensuring the ability to validate each other’s suggestions. If
they choose to proceed, they A-Cast their suggestions and only accept those
they can validate using their local results from the truncated A-BAs. This
validation relies on the property that honest parties terminate within two
consecutive iterations in each A-BA execution, ensuring the validity of
suggestions even when provided by corrupted parties. Once parties receive
$n-t$ suggestions, they proceed by A-Casting the set of the first $n-t$
suggestions they receive, along with the identities of their providers. The
checked precondition guarantees that everyone can move on to the next step.

Parties then wait until they receive enough suggestions and enough sets,
ensuring that at least $n-t$ sets are completely contained within the set of
suggestions they received. By employing a counting argument similar to [41,
34], we can ensure the delivery of suggestions from at least $n-2t>n/3$
parties to all honest participants. Moreover, the validation process applied
to the suggestions guarantees that each honest party only accepts valid
suggestions, even if they originate from corrupted sources. These robust
guarantees in the distribution of suggested outputs establish that the $n-2t$
suggestions commonly received by honest parties are legitimate outputs. This
enables us to directly utilize the synchronous protocol in the asynchronous
setting.

We employ our new asynchronous OCC protocol to elect a leader for party
coordination. Every party adopts the leader’s suggestion and runs a multi-
valued A-BA to handle the obliviousness of the leader-election mechanism. If
the parties successfully agree on a random leader who happens to be chosen
from the $n-2t>n/3$ parties whose suggestions are commonly received, which
occurs with constant probability, all honest parties initiate the A-BA
protocol with the leader’s suggestion and output the same value. If the leader
is not among those parties (or there is disagreement on the leader),
precautions are taken to ensure no malicious value is output. For this
purpose, we utilize an “intrusion-tolerant” A-BA protocol that guarantees the
output to be either a default value $\bot$ or one of the honest parties’
inputs.111111Ben-Or and El-Yaniv [9] introduced and used a strengthened
property for (A-)BA without naming it, which was later called “non-intrusion”
validity in [70]. Non-intrusion validity lies between standard validity and
“strong” validity [42], as it requires that a value decided by an honest party
is either an honest party’s input or a special symbol $\bot$ (i.e., the
adversary cannot intrude malicious values into the output). Thus, in case the
output is not $\bot$ the parties can safely output it, and otherwise they can
simply start over. Unlike the synchronous solution in [9], which includes a
validation step in between the agreement on the leader’s suggestion and a
final agreement on termination, our concurrent A-BA protocol involves
validation in the message-distribution phase, and so consensus on a non-
default value can directly be used to agree on termination.

By following the above approach, we sidestep the issues in Ben-Or and El-
Yaniv’s proof and achieve a significantly simpler protocol structure for the
asynchronous setting compared to the one presented in [9]. Somewhat
surprisingly, the resulting protocol is conceptually as simple as its
synchronous counterpart.

We now elucidate exactly how our findings enable round-efficient asynchronous
MPC, in both the computational and information-theoretic settings, while
maintaining optimal resiliency. Asynchronous MPC crucially relies on ACS for
determining the set of input providers [7]; this task commonly boils down to
concurrently executing $n$ instances of A-BA. Our expected-constant-round
concurrent A-BA protocol can be directly plugged into the asynchronous MPC
protocols in [7, 57, 13, 58, 31, 63], preserving their (expected) round
complexity. However, despite folklore belief, concurrent A-BA cannot be used
in a black-box way in the BKR protocol [14] to achieve asynchronous MPC with
round complexity linear in the depth of the circuit. The issue (as pointed out
in [82, 1]) is that the ACS protocol outlined in [14] assigns input values for
certain A-BA instances based on the outputs of other instances. This problem
also affects other works like [25, 19] that rely on [14].

Fortunately, this issue can be readily addressed by modifying the ACS protocol
from [7] (which is secure for $t<n/3$). Recall that this protocol involves a
preprocessing step for distributing input shares before initiating concurrent
A-BA, which necessitates $O(\log n)$ rounds. Replacing the $O(\log n)$-round
preprocessing step with the constant-round “Gather” protocol described in
[5]—an enhanced version of Canetti and Rabin’s counting argument [34]—results
in an ACS protocol with constant round complexity. This modified ACS protocol
can be seamlessly integrated into both [7] and [14], effectively rendering
their round complexity independent of the number of parties. Alternatively,
one can leverage the expected-constant-round ACS protocol recently proposed by
Abraham et al. [1], or the one by Duan et al. [39] (instantiating all building
blocks with information-theoretic realizations; in particular, the assumption
of a “Rabin dealer” [76], used for leader election, can be replaced by our
multi-valued OCC).

#### Composable treatment of expected-constant-round concurrent A-BA.

We choose to work in Canetti’s Universal Composability (UC) framework [21],
and as such, we prove the security of our protocols in a _simulation-based_
manner. (See Section 2.1 for a high-level overview.) The UC framework provides
strong composability guarantees when secure protocols are run as a subroutine
in higher-level protocols (this is absolutely critical in our context given
that expected-constant-round concurrent A-BA is a key building block in many
round-efficient cryptographic protocols, as mentioned above), and even in _a
priori_ unknown or highly adversarial environments (such as asynchronous
networks). Moreover, it enables us to provide a modular, bottom-up security
analysis. However, obtaining a composable and round-preserving treatment of
“probabilistic-termination” BA is non-trivial, as pointed out by Cohen et al.
[23, 24] in the synchronous setting. In the following, we discuss some unique
issues in asynchrony and how we address them.

To model eventual message delivery, we follow [61, 25, 31] and require parties
to repeatedly attempt fetching messages from the network. The first $D$ such
requests are ignored by the functionality, where $D$ is a value provided by
the adversary in unary so that it remains bounded by the adversary’s running
time (i.e., so that messages cannot be delayed _indefinitely_). It is
straightforward then to derive a formal notion of asynchronous rounds in UC,
based on this mechanism. We remark that unlike in the synchronous setting
[61], (asynchronous) rounds cannot be used by the environment to distinguish
the real and ideal worlds in the asynchronous setting. Thus, as opposed to
[23, 24], our functionalities are round-unaware. Similarly, we do not need to
deal with standard issues in sequential composition, namely, non-simultaneous
start/termination (“slack”), since asynchronous protocols are already robust
to slack. Indeed, it is entirely possible that some parties receive output
from a (secure) asynchronous protocol before other parties have even started
the protocol!

On the other hand, the issue of _input incompleteness_ is trickier to address.
This refers to the problem that in the asynchronous setting, the inputs of up
to $t$ honest parties may not be considered in the result of the computation;
the remaining $n-t$ parties form a “core set” of input providers. Note that in
the worst case, the core set is adversarially chosen and includes all
corrupted parties. Prior work [25, 31] allowed the adversary to send an
explicit core set to the functionality; however, this approach does not always
accurately model what happens in the real world, and can cause difficulties in
the simulation. Instead, our solution is to allow the adversary to define the
core set _implicitly_ , by delaying the submission of inputs to the
functionality in the same way that it delays the release of outputs from the
functionality. Using this novel modeling approach, we obtain updated
functionalities for some standard asynchronous primitives that more accurately
capture realizable security guarantees.

###  1.3 Additional Related Work

As mentioned earlier, the $t+1$ lower bounds for deterministic BA [45, 37]
were extended to rule out _strict-_ constant-round $t$-secure randomized BA
for $t=\Theta(n)$ [30, 62, 32]; these bounds show that any such $r$-round BA
must fail with probability at least $(c\cdot r)^{-r}$ for a constant $c$, a
result that is matched by the protocol of [52]. Cohen et al. [27] showed that
for $t>n/3$, two-round BA is unlikely to reach agreement with constant
probability, implying that the _expected_ round complexity must be larger;
this essentially matches Micali’s BA [68] that terminates in three rounds with
probability $1/3$. Attiya and Censor-Hillel [2] extended the results on worst-
case round complexity for $t=\Theta(n)$ from [30, 62] to the asynchronous
setting, showing that any $r$-round A-BA must fail with probability $1/c^{r}$
for some constant $c$.

In the dishonest-majority setting, expected-constant-round broadcast protocols
were initially studied by Garay et al. [53], who established feasibility for
$t=n/2+O(1)$ as well as a negative result. A line of work [51, 33, 79, 80, 77]
established expected-constant-round broadcast for any constant fraction of
corruptions under cryptographic assumptions.

Synchronous and (binary) asynchronous OCC protocols in the information-
theoretic setting were discussed earlier. Using the synchronous protocol in
[9], Micali and Rabin [69] showed how to realize a _perfectly unbiased_ common
coin in expected-constant rounds for $t<n/3$ over secure channels (recall that
this task is impossible in asynchronous networks [38]). In the cryptographic
setting, both synchronous and asynchronous OCC protocols with optimal
resiliency are known, relying on various computational assumptions; we mention
a few here. Beaver and So [17] gave two protocols tolerating $t<n/2$
corruptions in synchronous networks, which are secure under the quadratic
residuosity assumption and the hardness of factoring, respectively. Cachin et
al. [29] presented two protocols for $t<n/3$ and asynchronous networks, which
are secure in the random oracle model based on the RSA and Diffie-Hellman
assumptions, respectively. Nielsen [71] showed how to eliminate the random
oracle and construct an asynchronous OCC protocol relying on standard
assumptions alone (RSA and DDH). Although these constructions are for
asynchronous networks, they can be readily extended to work in synchronous
networks for $t<n/2$ (e.g., so that they can be used in the computationally
secure BA protocol from [42]). We also note that while the resiliency bounds
for asynchronous OCC protocols coincide in the information-theoretic and
computational settings, working in the latter typically yields expected-
constant-round A-BA protocols that are much more efficient in terms of
communication complexity (i.e., _interaction_) than the unconditionally secure
protocol of Canetti and Rabin [34].

Lastly, we discuss solutions to multi-valued A-BA in the computational
setting. Cachin et al. [28] studied a more general version of this problem, in
which the validity property is replaced with “external” validity, where the
output domain can be arbitrarily large but the agreed-upon value must only
satisfy an application-specific predicate. They gave a construction for multi-
valued “validated” A-BA that runs in expected-constant rounds for $t<n/3$,
assuming a PKI and a number of threshold cryptographic primitives (including
an asynchronous OCC), and used it to obtain an efficient protocol for
asynchronous _atomic_ broadcast. Recently, Abraham et al. [6] (and follow-ups,
e.g., [66, 5, 54]) have improved the communication complexity. The work of
Fitzi and Garay [42] also considered _strong_ (A-)BA. Here we require “strong”
validity: the common output must have been one of the honest parties’ inputs
(note that this is equivalent to standard validity in the binary case). When
the size of the input domain is $m>2$, neither a Turpin-Coan-style reduction
[78] nor the obvious approach of running $\log m$ parallel executions of a
binary protocol would suffice to realize this stronger notion of agreement;
indeed, Fitzi and Garay showed that strong A-BA is possible if and only if
$t<n/(m+1)$. This bound holds in both the information-theoretic and
computational settings. Their unconditionally secure asynchronous protocol
actually involves oblivious coin flipping on the domain, but $m>2$ forces
$t<n/4$ and the binary asynchronous OCC protocols in [41, 34] can be extended
to multi-valued in this regime, as discussed in Section 1.2.

###  1.4 Organization of the Paper

The rest of the paper is organized as follows. We start in Section 2 with some
preliminaries, including a brief overview of the UC framework. In Section 3,
we discuss our model in greater depth, formally specifying the asynchronous
primitives we use as building blocks and motivating our novel modeling choices
along the way. Section 4 contains our multi-valued asynchronous OCC
construction with optimal resiliency $t<n/3$, and its security proof. Finally,
in Section 5 we present the impactful result that our OCC construction
enables: a simplified and sound protocol for concurrent A-BA in expected-
constant rounds. Appendix A contains our attack on the asynchronous
construction in [9] (along with the required background material), and
Appendix B demonstrates that an asynchronous version of the binary to multi-
valued BA extension in [78] works if and only if $t<n/5$.

##  2 Model and Preliminaries

For $m\in\mathbb{N}$, we use $[m]$ to denote the set $\\{1,\ldots,m\\}$. Our
protocols often use dynamically growing sets $S$; when $|S|\geq k$, we denote
by $S^{(k)}\subseteq S$ the set containing the first $k$ elements that were
added to $S$. We also denote by $\mathbb{F}$ the field from which the
protocols’ messages come. Our statements (in particular, the ones about
statistical security) assume an (often implicit) security parameter $\kappa$
which is assumed to be linear in $\max\\{\log|\mathbb{F}|,n\\}$.

We write our protocols using a series of numbered steps. The interpretation is
that a party repeatedly goes through them in sequential order, attempting each
instruction. Of course, in the asynchronous setting, the necessary
precondition for carrying out an instruction might only be met much later in
the protocol, and furthermore messages may be delayed. We discuss the latter
below, in Section 2.2. Regarding the former, we frequently use statements of
the form “Wait until [condition]. Then, [instruction],” which is to be
executed at most once, or “If [condition], then [instruction],” which can be
executed multiple times.

###  2.1 UC Basics

We prove our constructions secure in the UC framework [21] and we briefly
summarize it here. Protocol machines, ideal functionalities, the adversary,
and the environment are all modeled as interactive Turing machine (ITM)
instances, or ITIs. An execution of protocol $\Pi$ consists of a series of
activations of ITIs, starting with the environment $\mathcal{Z}$ who provides
inputs to and collects outputs from the parties and the adversary
$\mathcal{A}$; parties can also give input to and collect output from sub-
parties (e.g., hybrid functionalities), and $\mathcal{A}$ can communicate with
parties via “backdoor” messages. Although parties can send messages to one
another, $\mathcal{A}$ is responsible for delivering them, making this model
_completely_ asynchronous (see Section 2.2 for the way we capture eventual-
delivery channels). Protocol instances are delineated using a unique session
identifier (SID).

Corruption of parties is modeled by a special corrupt message sent from
$\mathcal{A}$ to the party; upon receipt of this message, the party sends its
entire local state to $\mathcal{A}$, and in all future activations follows the
instructions of $\mathcal{A}$. We emphasize that corruptions can occur at any
point during the protocol (i.e., $\mathcal{A}$ is assumed to be adaptive).
Denote by $\textsc{exec}_{\Pi,\mathcal{A},\mathcal{Z}}$ the probability
distribution ensemble corresponding to the (binary) output of $\mathcal{Z}$ at
the end of an execution of $\Pi$ with adversary $\mathcal{A}$.

The ideal-world process for functionality $\mathcal{F}_{\mathsf{}}$ is simply
defined as an execution of the ideal protocol
$\textsc{ideal}_{\mathcal{F}_{\mathsf{}}}$, in which the so-called “dummy”
parties just forward inputs from $\mathcal{Z}$ to $\mathcal{F}_{\mathsf{}}$
and forward outputs from $\mathcal{F}_{\mathsf{}}$ to $\mathcal{Z}$ (in
particular, the dummy parties do not communicate with the adversary, but
rather the adversary is expected to send backdoor messages directly to
$\mathcal{F}_{\mathsf{}}$, including corruption requests). Our functionalities
implicitly respond to corruption requests in the standard way (e.g., all
previous inputs of the newly corrupted party are leaked, and the adversary has
the option to replace its output); we refer to [21] for further details. The
adversary in the ideal world is also called the _simulator_ and denoted
$\mathcal{S}$; the corresponding ensemble is denoted by
$\textsc{ideal}_{\mathcal{F}_{\mathsf{}},\mathcal{S},\mathcal{Z}}$.

We are interested in unconditional (aka information-theoretic) security. Thus,
we say that a protocol $\Pi$ (statistically) UC-realizes an ideal
functionality $\mathcal{F}_{\mathsf{}}$ if for any computationally unbounded
adversary $\mathcal{A}$, there exists a simulator $\mathcal{S}$ (which is
polynomial in the complexity of $\mathcal{A}$), such that for any
computationally unbounded environment $\mathcal{Z}$, we have
$\textsc{exec}_{\Pi,\mathcal{A},\mathcal{Z}}\approx\textsc{ideal}_{\mathcal{F}_{\mathsf{}},\mathcal{S},\mathcal{Z}}$.
In case the distribution ensembles are perfectly indistinguishable we say that
$\Pi$ UC-realizes $\mathcal{F}_{\mathsf{}}$ with _perfect_ security.

When $\Pi$ is a $(\mathcal{G}_{1},\ldots,\mathcal{G}_{n})$-hybrid protocol
(i.e., making subroutine calls to
$\textsc{ideal}_{\mathcal{G}_{1}},\ldots,\textsc{ideal}_{\mathcal{G}_{n}}$),
we say that $\Pi$ UC-realizes $\mathcal{F}_{\mathsf{}}$ in the
$(\mathcal{G}_{1},\ldots,\mathcal{G}_{n})$-hybrid model.

###  2.2 Modeling Eventual Message Delivery in UC

As mentioned above, the base communication model in UC is completely
unprotected. To capture asynchronous networks with eventual message delivery,
we work in a hybrid model with access to the multi-use _asynchronous secure
message transmission_ functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax
smt}}$, shown in Figure 1, which was introduced in [25] and is itself based on
the (single-use) _eventual-delivery secure channel_ functionality
$\mathcal{F}_{\mathsf{ed\mathchar 45\relax sec}}$ from [61].

Functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax smt}}$ The
functionality proceeds as follows. At the first activation, verify that
$\mathsf{sid}=(P_{s},P_{r},\mathsf{sid}^{\prime})$, where $P_{s}$ and $P_{r}$
are player identities. Initialize the current delay
$D\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$ and the message
buffer
$M\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\texttt{eom})$,
where eom is a special “end-of-messages” symbol. Upon receiving
$(\texttt{send},\mathsf{sid},m)$ from $P_{s}$, update
$M\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(m,\mathsf{mid})\parallel
M$ (i.e., insert $(m,\mathsf{mid})$ at the beginning of $M$), where
$\mathsf{mid}$ is a unique message ID, and send
$(\texttt{leakage},\mathsf{sid},\mathsf{mid})$ to the adversary. Upon
receiving $(\texttt{delay},\mathsf{sid},T)$ from the adversary for
$T\in\mathbb{Z}$ represented in unary notation, update
$D\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(1,D+T)$ and
send $(\texttt{delay-set},\mathsf{sid})$ to the adversary (thereby returning
the activation to the adversary). Upon receiving
$(\texttt{fetch},\mathsf{sid})$ from $P_{r}$, do: 1. Update
$D\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(0,D-1)$ and
send $(\texttt{fetched},\mathsf{sid})$ to the adversary. 2. If $D=0$ and
$M=((m_{1},\mathsf{mid}_{1}),\ldots,(m_{l},\mathsf{mid}_{l}),\texttt{eom})$,
then update
$M\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=((m_{2},\mathsf{mid}_{2}),\ldots,(m_{l},\mathsf{mid}_{l}),\texttt{eom})$
and send $(\texttt{output},\mathsf{sid},m_{1})$ to $P_{r}$. Upon receiving
$(\texttt{permute},\mathsf{sid},\pi)$ from the adversary, if
$M=((m_{1},\mathsf{mid}_{1}),\ldots,(m_{l},\mathsf{mid}_{l}),\texttt{eom})$
and $\pi$ is a permutation over $[l]$, then update
$M\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=((m_{\pi(1)},\mathsf{mid}_{\pi(1)}),\ldots,(m_{\pi(l)},\mathsf{mid}_{\pi(l)}),\texttt{eom})$.
(Adaptive Message Replacement) Upon receiving
$(\texttt{replace},\mathsf{sid},((m_{1},\mathsf{mid}_{1}),\ldots,(m_{l^{\prime}},\mathsf{mid}_{l^{\prime}})),T^{\prime})$
from the adversary: If $P_{s}$ is corrupted, $D>0$, and $T^{\prime}$ is a
valid delay, then update
$M\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=((m_{1},\mathsf{mid}_{1}),\ldots,(m_{l^{\prime}},\mathsf{mid}_{l^{\prime}}),\texttt{eom})$
and
$D\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(1,T^{\prime})$.

Figure 1: The asynchronous secure message transmission functionality.

The functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax smt}}$ models a
_secure_ eventual-delivery channel between a sender $P_{s}$ and receiver
$P_{r}$.121212Recall that while (concurrent) A-BA is not a private task,
secure channels are needed to construct an OCC. To reflect the adversary’s
ability to delay the message by an arbitrary finite duration (even when
$P_{s}$ and $P_{r}$ are not corrupted), the functionality operates in a “pull”
mode, managing a message buffer $M$ and a counter $D$ that represents the
current message delay. This counter is decremented every time $P_{r}$ tries to
fetch a message, which is ultimately sent once the counter hits $0$. The
adversary can at any time provide an additional integer delay $T$, and if it
wishes to immediately release the messages, it needs only to submit a large
negative value. It is important to note that $T$ must be encoded in unary;
this ensures that the delay, while arbitrary, remains bounded by the
adversary’s computational resources or running time.131313We refer to [21] for
a formal definition of running time in the UC framework. Also, note that
$\mathcal{F}_{\mathsf{a\mathchar 45\relax smt}}$ guarantees eventual message
delivery assuming that the environment gives sufficient resources to the
protocol, i.e., activates $P_{r}$ sufficiently many times. We additionally
allow the adversary to permute the messages in the buffer; see [25] for a
discussion.

Since $\mathcal{F}_{\mathsf{a\mathchar 45\relax smt}}$ (and our other
asynchronous functionalities) may not provide output immediately, we must
clarify what we mean when instructing a party to fetch the output from
multiple instances of a hybrid (e.g., one per party), as repeatedly attempting
to fetch from the first instance before continuing to the second instance
might not make any progress. Accordingly, we require that parties fetch the
output in a “round-robin fashion” across activations (i.e., after attempting
to fetch from each instance, the party moves on to try the remaining steps in
the protocol). It is implicit that the party stops making fetch requests to
any given instance after it receives an output from that instance (of course,
this behavior can be easily implemented using flags).

Finally, we note that while the UC framework has no notion of time, and we are
in the asynchronous setting (with eventual message delivery) where parties may
proceed at different rates, one can still formally define a notion of
asynchronous rounds along the lines of [25], which will be referred to in our
statements. Informally, rounds are delimited by alternations between sending
messages to and reading messages from the network. More precisely, each party
maintains a local round counter, which is incremented every time the party
sends an input to a hybrid after fetching a (causally related) output from a
hybrid. For example—and this accounts for virtually all of the times that a
round advances during an execution of our protocols—a successful fetch request
may directly trigger a send in the next activation, in which case the party
increments its round counter. Note that we allow for multiple sends to be
“batched” within the same round (i.e., only the first send will trigger a
round advancement). We refrain from putting forth a formal treatment of
causality; notwithstanding, causal relationships between messages will be
immediately apparent from our protocol descriptions.

Denote by $R_{\mathcal{A},\mathcal{Z},z}$ the random variable (defined over
the random choices of all relevant machines) representing the maximum number
of rounds that an honest party takes in an execution with a _fixed_ adversary
$\mathcal{A}$, environment $\mathcal{Z}$, and input $z$ to $\mathcal{Z}$. We
now define the (expected) round complexity of the protocol by considering the
maximum expected value of this random variable, over all admissible
adversaries, environments, and inputs:
$\max_{\mathcal{A},\mathcal{Z},z}\\{\mathbb{E}[R_{\mathcal{A},\mathcal{Z},z}]\\}$.

##  3 Ideal Functionalities for a Few Standard Primitives

In this section, we present ideal functionalities for asynchronous primitives
used in our constructions. This seemingly simple task requires careful
consideration of certain aspects, as the adversary’s ability to delay messages
in the network has an upstream impact on the achievable security guarantees of
distributed tasks. In particular, the adversary can obstruct the output
release procedure and impede honest parties’ participation. To model _delayed
output release_ , we extend the mechanism discussed in Section 2.2 (using per-
party delay counters). However, to model _delayed participation_ , we
introduce a novel and more natural approach that addresses limitations of
prior work and more closely captures the effects of asynchrony. We start by
discussing in Section 3.1 our design choices for the latter, and proceed to
describe a few ideal functionalities in Section 3.2.

###  3.1 Modeling Delayed Participation

In the asynchronous setting, honest parties cannot distinguish whether
uncooperative parties are corrupted and intentionally withholding messages, or
if they are honest parties whose messages have been delayed. Consequently,
when the number of corruptions is upper-bounded by $t$, waiting for the
participation of the last $t$ parties can result in an indefinite wait. In
ideal functionalities, this translates to expecting participation and/or input
only from a subset of adversarially chosen parties, known as the “core set,”
with a size of $n-t$. Observe that the value of $t$ is closely related to the
behavior of the functionality. In this work, we specifically consider optimal
resiliency, where $t=\lceil\frac{n}{3}\rceil-1$. However, our functionalities
can be easily adapted to accommodate other resiliency bounds.

In our modeling approach, the adversary implicitly determines the core set by
strategically delaying participation (or input submission) to the
functionality. If we instruct the ideal functionality to proceed once $n-t$
parties have participated, the adversary can precisely determine the core set
by manipulating the order of participation (or input submissions). To
accommodate arbitrary but finite delays for input submissions, we employ a
technique similar to the one we use for the output-release mechanism. That is,
in addition to a per-party _output delay counter_ , there is an _input delay
counter_ (updatable by the adversary) which is decremented every time the
party pings the functionality; once the counter reaches zero, the party is
allowed to participate.

This approach contrasts with the work of Cohen [31] and Coretti et al. [25],
wherein the adversary (simulator) explicitly sends a core set to the
functionality. Obtaining the core set from the adversary all at once does not
accurately mimic real-world executions and requires careful consideration to
ensure the implementation works in all scenarios. For instance, a challenging
case to model is when the simulator sets the core set, but the environment
never activates some parties in that core set. If not handled properly, this
situation can lead to either the ideal functionality stalling indefinitely
while the real-world execution proceeds, or allowing for core sets of smaller
sizes, neither of which is acceptable.

There are other aspects of modeling the core set that can potentially cause
issues. If the simulator is required to set the core set early on, it may
encounter issues during the simulation because in some real-world protocols,
such as the asynchronous MPC protocol of Ben-Or et al. [14], the core set is
not fixed in the early stages of the execution. Similarly, if the
functionality allows late submission of the core set, then when using the
functionality as a hybrid, the adversary can potentially stall the
functionality unless appropriate preventive mechanisms are in place. In
contrast, implicitly defining the core set by delaying parties’ participation
aligns more closely with real-world executions, reducing the probability of
errors. Additionally, it can potentially simplify the simulation process, as
the simulator can gradually define the core set as the protocol progresses.

###  3.2 Ideal Functionalities for a Few Standard Primitives

We now cast a few standard asynchronous primitives as UC functionalities,
following our novel modeling approach. We also present security statements
showing how classical protocols can be used to realize these primitives.

#### Asynchronous Broadcast (A-Cast).

The first essential primitive used in both our OCC and concurrent A-BA
protocols, which also finds numerous applications in other asynchronous
protocols, is Bracha’s Asynchronous Broadcast (A-Cast) [16]. A-Cast enables a
distinguished sender to distribute its input, such that if an honest party
outputs a value, then all honest parties must (eventually) output the same
value. Moreover, if the sender is honest, then all honest parties must
(eventually) output the sender’s input. While these are essentially the
agreement and validity properties required from regular (synchronous)
broadcast, we stress that honest parties may not terminate when the sender is
corrupted. We formulate A-Cast as the ideal functionality
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$, shown in Figure 2.

Functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ The
functionality proceeds as follows. Start a session once a message of the form
$(\texttt{send},\mathsf{sid},\cdot)$ with
$\mathsf{sid}=(\mathcal{P},P_{s},\mathsf{sid}^{\prime})$ is received from (the
sender) $P_{s}\in\mathcal{P}$, where $\mathcal{P}$ is a player set of size
$n$. For each $P_{i}\in\mathcal{P}$, initialize
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$
and delay values
$D^{\mathrm{input}}_{i}=D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Also initialize $y$ to a default value $\bot$ and
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lceil\frac{n}{3}\rceil-1$.
Upon receiving $(\texttt{delay},\mathsf{sid},P_{i},\mathsf{type},D)$ from the
adversary for $P_{i}\in\mathcal{P}$,
$\mathsf{type}\in\\{\mathrm{input},\mathrm{output}\\}$, and $D\in\mathbb{Z}$
represented in unary notation, update
$D^{\mathsf{type}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(1,D^{\mathsf{type}}_{i}+D)$
and send $(\texttt{delay-set},\mathsf{sid})$ to the adversary. Upon receiving
$(\texttt{send},\mathsf{sid},v)$ from $P_{i}=P_{s}$ (or the adversary on
behalf of corrupted $P_{s}$), run the Input Submission Procedure, record
$y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$, and send
$(\texttt{leakage},\mathsf{sid},v)$ to the adversary. Upon receiving
$(\texttt{replace},\mathsf{sid},v)$ from the adversary ($v$ can be $\bot)$, if
$P_{s}$ is corrupted and no party has received their output yet, then update
$y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$. Upon receiving
$(\texttt{fetch},\mathsf{sid})$ from $P_{i}\in\mathcal{P}$ (or the adversary
on behalf of corrupted $P_{i}$), run the Input Submission and Output Release
Procedures, and send $(\texttt{fetched},\mathsf{sid},P_{i})$ to the adversary
and any messages set by the Output Release Procedure to $P_{i}$. Input
Submission Procedure: If $\mathsf{participated}_{i}=0$ then do: 1. Update
$D^{\mathrm{input}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{input}}_{i}-1$.
2. If $D^{\mathrm{input}}_{i}=0$ then set
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Output Release Procedure: If $\sum_{j=1}^{n}\mathsf{participated}_{j}\geq n-t$
and $y\neq\bot$, then do: 1. Update
$D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{output}}_{i}-1$.
2. If $D^{\mathrm{output}}_{i}=0$ then set $(\texttt{output},\mathsf{sid},y)$
to be sent to $P_{i}$.

Figure 2: The A-Cast functionality.

Note that although A-Cast is a single-sender primitive, assuming it can
proceed to the output generation phase without sufficient participation from
other parties is too idealized. A realizable functionality should only proceed
to the output generation phase when $n-t$ parties (which may include the
sender) have participated. Non-sender parties demonstrate their participation
by issuing fetch requests to the functionality. An important technicality here
is that the participation of parties before the sender initiates the session
should not contribute to the count. Therefore,
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ starts a session only once
the input from the sender is received. Consequently, any efforts for
participation before that point will not be taken into account. An implication
of this design choice when using $\mathcal{F}_{\mathsf{a\mathchar 45\relax
cast}}$ as a hybrid is that parties other than the sender will not know when
the session has started.

Bracha’s asynchronous broadcast protocol [16] can be used to UC-realize
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with perfect security. We
formally state this result in the following proposition, whose proof is
straightforward.

######  Proposition 1.

$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ can be UC-realized with
perfect security in the $\mathcal{F}_{\mathsf{a\mathchar 45\relax
smt}}$-hybrid model, in constant rounds and against an adaptive and malicious
$t$-adversary, provided $t<\frac{n}{3}$.

#### Asynchronous Verifiable Secret Sharing (A-VSS).

Another crucial primitive we require, mainly for our OCC protocol, is
_Asynchronous Verifiable Secret Sharing_ (A-VSS). A-VSS allows a dealer to
secret-share a value among all parties, ensuring that no unauthorized subset
of colluding parties can learn any information about the secret. However, any
authorized subset of parties should be able to efficiently reconstruct the
secret using their shares. The term “verifiable” reflects that the dealer
cannot cheat, for example by causing the reconstruction to fail or by inducing
inconsistent output values from honest parties. In particular, whenever the
sharing phase succeeds, any authorized subset of parties should be able to
efficiently complete the reconstruction phase, and all honest parties doing so
must recover the same secret. Moreover, if the dealer is honest, the sharing
phase must always succeed, and everyone should recover the value originally
shared by the dealer. In our context, we consider only the threshold access
structure, where a subset of parties can recover the secret if and only if it
contains at least $n-t$ of the parties. However, we leak the secret to the
adversary as soon as $t+1$ parties have participated (at least one of whom
must be honest). The formulation of A-VSS as an ideal functionality,
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$, is shown in Figure 3. We
denote this as the “plain” A-VSS functionality, as it does not allow
homomorphic computation over shares; nonetheless, this basic functionality
suffices for obtaining a multi-valued asynchronous OCC.

Functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{V}$ The
functionality is parameterized by a set $V$ of possible secrets and proceeds
as follows. Start a session once a message of the form
$(\texttt{share},\mathsf{sid},v)$ with
$\mathsf{sid}=(\mathcal{P},P_{d},\mathsf{sid}^{\prime})$ and $v\in V$ is
received from (the dealer) $P_{d}\in\mathcal{P}$, where $\mathcal{P}$ is a
player set of size $n$. For each $P_{i}\in\mathcal{P}$, initialize
$\mathsf{phase}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\mathrm{share}$,
$\mathsf{participated}_{i,\mathrm{share}}=\mathsf{participated}_{i,\mathrm{rec}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$,
and current delay values
$D^{\mathrm{share},\mathrm{input}}_{i}=D^{\mathrm{share},\mathrm{output}}_{i}=D^{\mathrm{rec},\mathrm{input}}_{i}=D^{\mathrm{rec},\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Also initialize $\mathsf{secret}$ to a default value $\bot$ and
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lceil\frac{n}{3}\rceil-1$.
Upon receiving
$(\texttt{delay},\mathsf{sid},P_{i},\mathsf{phase},\mathsf{type},D)$ from the
adversary for $P_{i}\in\mathcal{P}$,
$\mathsf{phase}\in\\{\mathrm{share},\mathrm{rec}\\}$,
$\mathsf{type}\in\\{\mathrm{input},\mathrm{output}\\}$, and $D\in\mathbb{Z}$
represented in unary notation, update
$D^{\mathsf{phase},\mathsf{type}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(1,D^{\mathsf{phase},\mathsf{type}}_{i}+D)$
and send $(\texttt{delay-set},\mathsf{sid})$ to the adversary. Upon receiving
$(\texttt{share},\mathsf{sid},v)$ from $P_{i}=P_{d}$ (or the adversary on
behalf of corrupted $P_{d}$) for $v\in V$, run the Input Submission Procedure,
record
$\mathsf{secret}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$,
and send $(\texttt{leakage},\mathsf{sid},|\mathsf{secret}|)$ to the adversary.
Upon receiving $(\texttt{replace},\mathsf{sid},v)$ from the adversary, if
$P_{d}$ is corrupted, $v\in V\cup\\{\bot\\}$, and no honest party has received
$(\texttt{shared},\mathsf{sid})$ yet, then update
$\mathsf{secret}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$.
Upon receiving $(\texttt{rec},\mathsf{sid})$ from $P_{i}\in\mathcal{P}$ (or
the adversary on behalf of corrupted $P_{i}$), run the Input Submission
Procedure, and if $\sum_{j=1}^{n}\mathsf{participated}_{j,\mathrm{rec}}\geq
t+1$ then send $(\texttt{leakage},\mathsf{sid},P_{i},\mathsf{secret})$ to the
adversary; else send $(\texttt{fetched},\mathsf{sid},P_{i})$ to the adversary.
Upon receiving $(\texttt{fetch},\mathsf{sid})$ from $P_{i}\in\mathcal{P}$ (or
the adversary on behalf of corrupted $P_{i}$), run the Input Submission and
Output Release Procedures, and send $(\texttt{fetched},\mathsf{sid},P_{i})$ to
the adversary and any messages set by the Output Release Procedure to $P_{i}$.
Input Submission Procedure: If
$\mathsf{participated}_{i,\mathsf{phase}_{i}}=0$, and either
$\mathsf{phase}_{i}=\mathrm{share}$ or $\mathsf{phase}_{i}=\mathrm{rec}$ and
$(\texttt{rec},\mathsf{sid})$ was previously received from $P_{i}$, then do:
1. Update
$D^{\mathsf{phase}_{i},\mathrm{input}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathsf{phase}_{i},\mathrm{input}}_{i}-1$.
2. If $D^{\mathsf{phase}_{i},\mathrm{input}}_{i}=0$ then set
$\mathsf{participated}_{i,\mathsf{phase}_{i}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Output Release Procedure: If
$\sum_{j=1}^{n}\mathsf{participated}_{j,\mathsf{phase}_{i}}\geq
n-t\land(\mathsf{phase}_{i}=\mathrm{share}\lor\mathsf{secret}\neq\bot)$ then
do: 1. Update
$D^{\mathsf{phase}_{i},\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathsf{phase}_{i},\mathrm{output}}_{i}-1$.
2. If $D^{\mathsf{phase}_{i},\mathrm{output}}_{i}=0$, then do the following.
If $\mathsf{phase}_{i}=\mathrm{share}$, set $(\texttt{shared},\mathsf{sid})$
to be sent to $P_{i}$ and update
$\mathsf{phase}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\mathrm{rec}$;
otherwise, set $(\texttt{opened},\mathsf{sid},\mathsf{secret})$ to be sent to
$P_{i}$.

Figure 3: The plain A-VSS functionality.

A-VSS, being a single-sender primitive, also requires the participation of at
least $n-t$ parties to be realizable. We adopt a similar approach to
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ in modeling this
requirement. Parties other than the dealer demonstrate their participation in
the sharing phase by issuing fetch requests, while participation in the
reconstruction phase additionally requires sending a (dummy) input message.
This ensures that the minimum participation threshold is met for the A-VSS
protocol to proceed with each phase. Also, it is important to note that
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$ only initiates a session once
it receives the first input (share) from the dealer. Any participation efforts
made before that point are not taken into account.

The A-VSS protocol given by Canetti and Rabin in [34] can be used to UC-
realize $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$ with statistical
security for $t<n/3$. This result is formally stated in the following
proposition. It is worth noting that perfectly secure A-VSS is impossible for
$t\geq n/4$ [14, 4].

######  Proposition 2.

For any finite field $\mathbb{F}$ (with $|\mathbb{F}|>n$),
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$ can be UC-
realized with statistical security in the $\mathcal{F}_{\mathsf{a\mathchar
45\relax smt}}$-hybrid model, in constant rounds and against an adaptive and
malicious $t$-adversary, provided $t<\frac{n}{3}$.

#### Asynchronous Byzantine Agreement (A-BA).

We use A-BA for both binary and multi-valued domains $V$ in our revised
concurrent A-BA protocol. In this primitive, each party $P_{i}$ has an input
$v_{i}\in V$. The goal is for all honest parties to output the same value,
such that if $n-2t$ input values are the same, that value (which for well-
definedness we require is unique) is chosen as the output; otherwise, the
adversary determines the output. We initially consider corruption-unfair A-BA,
where the adversary learns the input of each party the moment it is provided.
Corruption fairness, as introduced in [59] and later coined in [26],
essentially ensures that the (adaptive) adversary cannot corrupt a party and
subsequently influence the input value of that party based on its original
input. It is worth noting that corruption-fair A-BA can easily be defined by
avoiding leaking honest parties’ inputs before the output is generated. We
formulate A-BA as the ideal functionality $\mathcal{F}_{\mathsf{a\mathchar
45\relax ba}}$, shown in Figure 4.

Functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax ba}}^{V}$ The
functionality is parameterized by a set $V$ of values and proceeds as follows.
At the first activation, verify that
$\mathsf{sid}=(\mathcal{P},\mathsf{sid}^{\prime})$, where $\mathcal{P}$ is a
player set of size $n$. For each $P_{i}\in\mathcal{P}$, initialize $v_{i}$ to
a default value $\bot$,
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$,
and delay values
$D^{\mathrm{input}}_{i}=D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Also initialize
$y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot^{\prime}$,
$a\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$, and
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lceil\frac{n}{3}\rceil-1$.
Upon receiving $(\texttt{delay},\mathsf{sid},P_{i},\mathsf{type},D)$ from the
adversary for $P_{i}\in\mathcal{P}$,
$\mathsf{type}\in\\{\mathrm{input},\mathrm{output}\\}$, and $D\in\mathbb{Z}$
represented in unary notation, update
$D^{\mathsf{type}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(1,D^{\mathsf{type}}_{i}+D)$
and send $(\texttt{delay-set},\mathsf{sid})$ to the adversary. Upon receiving
$(\texttt{input},\mathsf{sid},v)$ from $P_{i}\in\mathcal{P}$ (or the adversary
on behalf of corrupted $P_{i}$), run the Input Submission Procedure and send
$(\texttt{leakage},\mathsf{sid},P_{i},v)$ to the adversary. Upon receiving
$(\texttt{replace},\mathsf{sid},v)$ from the adversary, record
$a\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$. Upon receiving
$(\texttt{fetch},\mathsf{sid})$ from $P_{i}\in\mathcal{P}$ (or the adversary
on behalf of corrupted $P_{i}$), run the Input Submission and Output Release
Procedures, and send $(\texttt{fetched},\mathsf{sid},P_{i})$ to the adversary
and any messages set by the Output Release Procedure to $P_{i}$. Input
Submission Procedure: If $\mathsf{participated}_{i}=0$ and
$(\texttt{input},\mathsf{sid},v)$ was previously received from $P_{i}$, then
do: 1. Update
$D^{\mathrm{input}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{input}}_{i}-1$.
2. If $D^{\mathrm{input}}_{i}=0$, then set
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$
and record $v_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$.
Output Release Procedure: If $\sum_{j=1}^{n}\mathsf{participated}_{j}\geq n-t$
then do: 1. Update
$D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{output}}_{i}-1$.
2. If $D^{\mathrm{output}}_{i}=0$, then do the following. If
$y=\bot^{\prime}$, then set
$y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=x$ if there exists a
unique value $x\in V$ such that $x=v_{k}$ for at least $n-2t$ inputs $v_{k}$;
else if $a=\bot$ or $a\in V$ was provided by at least one honest party, then
set $y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=a$; else set
$y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$. Additionally,
set $(\texttt{output},\mathsf{sid},y)$ to be sent to $P_{i}$.

Figure 4: The (intrusion-tolerant) A-BA functionality.

The functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax ba}}$ encompasses
an additional property known as “non-intrusion” validity (see Section 1.2). In
a nutshell, this property guarantees that no malicious value can be present in
the output. In other words, the output must be either an honest party’s input
or a default value $\bot$. This stronger notion of A-BA is vital for the
security of our concurrent A-BA protocol.

Note that when the input domain $V$ already contains a “null” value,
$\mathcal{F}_{\mathsf{a\mathchar 45\relax ba}}$ can simply output it as the
default value. Slightly abusing notation, we can therefore run multi-valued
A-BA on some domain $V^{\prime}\cup\\{\bot\\}$, with the assurance that a non-
default (i.e., _meaningful_) output value must have originated with an honest
party. (We stress that, on the other hand, an output of $\bot$ would guarantee
nothing in that scenario, even though $\bot$ is a possible input value.)
Looking ahead, our concurrent A-BA protocol will make use of this behavior, by
setting $V^{\prime}$ to be the set of all output vectors and allowing an
honest party who did not receive a vector to input $\bot$.

The expected-constant-round binary A-BA protocol of Canetti and Rabin [34] can
be used to UC-realize $\mathcal{F}_{\mathsf{a\mathchar 45\relax ba}}^{V}$ with
statistical security for binary domains ($|V|=2$) and $t<n/3$. However, our
concurrent A-BA protocol (and the one in [9]) require multi-valued A-BA, where
$|V|$ is not constant (in fact, exponential), in expected-constant rounds.
Ben-Or and El-Yaniv [9] claim that the constant-round reduction of multi-
valued to binary BA proposed by Turpin and Coan [78], which works in the
synchronous setting for $t<n/3$, can be extended to work in the asynchronous
setting by using A-Cast for message distribution. However, we demonstrate that
the asynchronous version of this reduction works if and only if $t<n/6$, even
when using A-Cast and considering a static adversary. (See Appendix B for
details.) Some additional modifications can improve this bound to $t<n/5$, but
achieving optimal resiliency is not straightforward.

More recently, Mostéfaoui and Raynal [70] presented a constant-round
transformation from binary to multi-valued A-BA that works for $t<n/3$.
Furthermore, the resulting protocol satisfies the non-intrusion validity
property mentioned above. By applying this transformation to the binary A-BA
protocol of Canetti and Rabin [34], we can UC-realize
$\mathcal{F}_{\mathsf{a\mathchar 45\relax ba}}^{V}$ for arbitrary $V$ with
statistical security:

######  Proposition 3.

For any domain $V$, $\mathcal{F}_{\mathsf{a\mathchar 45\relax ba}}^{V}$ can be
UC-realized with statistical security in the $\mathcal{F}_{\mathsf{a\mathchar
45\relax smt}}$-hybrid model, in expected-constant rounds and against an
adaptive and malicious $t$-adversary, provided $t<\frac{n}{3}$.

##  4 Asynchronous Oblivious Common Coin

The oblivious common coin (OCC) is a crucial primitive, particularly in the
asynchronous setting. As discussed in the Introduction, achieving even binary
A-BA against a single fail-stop corruption becomes impossible without the use
of randomization [47], emphasizing the importance of randomization in the
asynchronous setting. The OCC primitive allows parties to collectively agree
on a random value with a constant probability. This property opens up
possibilities for various higher-level asynchronous protocols, as an OCC can
potentially serve as the building block that provides the necessary
randomization. To illustrate its significance, in the case of binary values,
OCC enables binary A-BA in expected-constant rounds [76], and when extended to
domains with size equal to the number of participants, it can be used for
oblivious leader election (OLE) and sets the stage for expected-constant-round
concurrent BA in both synchronous and asynchronous networks [9]. Refer to
Section 5.2 for a formal definition of asynchronous OLE (A-OLE) and its
application toward expected-constant-round concurrent A-BA.

As highlighted in the Introduction, none of the existing OCC proposals is
simultaneously information-theoretic, asynchronous, multi-valued, and
optimally resilient. Furthermore, no straightforward adaptation of the
existing schemes yields an OCC with all of these properties. In Section 4.1,
we first formulate (multi-valued) OCC as an ideal functionality in the
asynchronous setting with eventual delivery. Subsequently, in Section 4.2, we
propose our own OCC protocol that aims to satisfy all of these properties. In
Section 4.3, we prove that our protocol runs in constant time and UC-realizes
the (multi-valued) OCC functionality with perfect security in the asynchronous
setting, even against an adaptive and malicious adversary who corrupts fewer
than $1/3$ of the parties.

At a high level, our protocol is based on the binary OCC of Feldman [41] and
Canetti and Rabin [34], and incorporates a novel combinatorial technique
derived from our observation stated in Lemma 4 below. By leveraging this
lemma, we unveil interesting and powerful properties of the local views formed
during the protocol’s execution, leading to enhanced extraction capabilities.
In fact, instead of extracting a single bit, by choosing appropriate
parameters we can extract random values from any arbitrary domain still with a
constant probability.

###  4.1 A-OCC Ideal Functionality

An OCC is parameterized by a set $V$ and some constant probability $p>0$. Each
party starts with an empty input $\lambda$ and outputs a value from $V$, where
with probability at least $p$ all parties output the same uniformly random
value $x\in V$ and with probability $1-p$ the adversary chooses each party’s
output.141414It is important to note that the term “oblivious” in this context
refers to the fact that parties do not learn whether an agreement on a random
coin value has been achieved or not, while the adversary does.

The above goal can be translated to a UC functionality as follows: Initially,
the ideal functionality samples a “fairness bit”
$b\leftarrow\mathrm{Bernoulli}(p)$ and a random value
$y\xleftarrow{\mathrm{R}}V$. Then, if $b=1$ or no meaningful input is received
from the adversary, it outputs $y$ to every party. However, if $b=0$ and
meaningful input is received from the adversary, it assigns each party the
value provided by the adversary; note that in this case, we allow the
adversary to assign outputs gradually. The functionality also informs the
adversary about the fairness bit and the random value once at least $t+1$
parties have participated (at least one of whom must be honest). Asynchronous
aspects, including delayed output release and participation, are handled as in
Section 3. The resulting functionality is shown in Figure 5.

Functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}^{V,p}$ The
functionality is parameterized by a set $V$ of possible outcomes and a
fairness probability $p$, and it proceeds as follows. At the first activation,
verify that $\mathsf{sid}=(\mathcal{P},\mathsf{sid}^{\prime})$, where
$\mathcal{P}$ is a player set of size $n$. For each $P_{i}\in\mathcal{P}$,
initialize $y_{i}$ to a default value $\bot$,
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$,
and delay values
$D^{\mathrm{input}}_{i}=D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
Also initialize $a$, $y$, and $b$ to $\bot$, and
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lceil\frac{n}{3}\rceil-1$.
Upon receiving $(\texttt{delay},\mathsf{sid},P_{i},\mathsf{type},D)$ from the
adversary for $P_{i}\in\mathcal{P}$,
$\mathsf{type}\in\\{\mathrm{input},\mathrm{output}\\}$, and $D\in\mathbb{Z}$
represented in unary notation, update
$D^{\mathsf{type}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max(1,D^{\mathsf{type}}_{i}+D)$
and send $(\texttt{delay-set},\mathsf{sid})$ to the adversary. Upon receiving
$(\texttt{input},\mathsf{sid})$ from $P_{i}\in\mathcal{P}$ (or the adversary
on behalf of corrupted $P_{i}$), run the Input Submission Procedure, and send
$(\texttt{leakage},\mathsf{sid},P_{i})$ to the adversary. Moreover, if
$\sum_{j=1}^{n}\mathsf{participated}_{j}\geq t+1$, then additionally send
$(\texttt{reveal},\mathsf{sid},b,y)$ to the adversary. Upon receiving
$(\texttt{replace},\mathsf{sid},v)$ from the adversary, record
$a\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v$. Upon receiving
$(\texttt{fetch},\mathsf{sid})$ from $P_{i}\in\mathcal{P}$ (or the adversary
on behalf of corrupted $P_{i}$), run the Input Submission and Output Release
Procedures, and send $(\texttt{fetched},\mathsf{sid},P_{i})$ to the adversary
and any messages set by the Output Release Procedure to $P_{i}$. Input
Submission Procedure: If $\mathsf{participated}_{i}=0$ and
$(\texttt{input},\mathsf{sid})$ was previously received from $P_{i}$, then do:
1. Update
$D^{\mathrm{input}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{input}}_{i}-1$.
2. If $D^{\mathrm{input}}_{i}=0$ then set
$\mathsf{participated}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$.
3. If $b=\bot$ then sample a “fairness bit” $b\leftarrow\mathrm{Bernoulli}(p)$
and a random value $y\xleftarrow{\mathrm{R}}V$. Output Release Procedure: If
$\sum_{j=1}^{n}\mathsf{participated}_{j}\geq n-t$ then do: 1. Update
$D^{\mathrm{output}}_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D^{\mathrm{output}}_{i}-1$.
2. If $D^{\mathrm{output}}_{i}=0$, then do the following. If $y_{i}=\bot$,
then if $b=1$ or $a$ cannot be parsed as $(a_{1},\ldots,a_{n})\in V^{n}$, set
$y_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=y$; otherwise,
set $y_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=a_{i}$.
Additionally, set $(\texttt{output},\mathsf{sid},y_{i})$ to be sent to
$P_{i}$.

Figure 5: The asynchronous OCC functionality.

###  4.2 The A-OCC Protocol

We proceed to present our asynchronous and multi-valued OCC protocol. We begin
by discussing all the essential building blocks employed in our protocol.
Subsequently, we provide a high-level overview of the protocol, highlighting
its key ideas. This is followed by a detailed description.

#### Building blocks.

The basic building blocks of our A-OCC protocol are A-VSS and A-Cast. A-VSS
enables parties to contribute by privately providing their local randomness
and only revealing this randomness when the contributions to the output are
determined. Thus, A-VSS ensures the secrecy and verifiability of the shared
secrets in an asynchronous setting. The A-VSS primitive is formally modeled as
the ideal functionality $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$,
described in Section 3.2. On the other hand, A-Cast facilitates communication
among parties by providing stronger guarantees than simple message
distribution. This is especially crucial in asynchronous settings where
challenges such as low message dispersion can occur. A-Cast helps in
overcoming these challenges and ensures reliable message dissemination among
the parties. We use the ideal functionality $\mathcal{F}_{\mathsf{a\mathchar
45\relax cast}}$, described in Section 3.2, to model this primitive.

#### The protocol.

As previously mentioned, our multi-valued protocol is built upon existing
binary A-OCC constructions [41, 34] and introduces a novel combinatorial
technique for extracting values from arbitrary domains. In both the binary
protocol and our proposed protocol, each party secret-shares $n$ random
elements from a field. It can be observed that at some point during the
protocol execution, a vector of length $n$ consisting of random elements from
the same field is established (with up to $t$ missing values due to
asynchrony). For each coordinate of this vector, random elements shared by
$t+1$ parties are utilized to prevent the adversary, controlling up to $t$
parties, from biasing any specific coordinate. Subsequently, each party starts
reconstructing secrets shared by other parties to form the same vector
locally. In the asynchronous setting, due to the low dispersion of messages,
not all coordinates can be reconstructed by honest parties. This can result in
different parties reconstructing different subsets of coordinates. However, by
using mechanisms to improve message dispersion, as originally demonstrated by
Feldman [41], it has been proven that when $t<n/3$, while the local vectors of
honest parties may have up to $t$ missing coordinates, they have an overlap of
size at least $n-2t>n/3$.151515Feldman calculated the size of the overlap,
denoted as $x$, based on the number of participants $n$ and the maximum number
of corruptions $t$. The general relation is $x\geq n-t-\frac{t^{2}}{n-2t}$,
which yields $x>n/3$ and $x>5n/8$ when $t<n/3$ and $t<n/4$, respectively. This
argument was later used in [34] to achieve optimal resiliency. This is
significant because without such mechanisms, and allowing for $t$ missing
components when $n=3t+1$, the overlap in the local vectors of just four
parties could be empty.

In fact, by incorporating the “Gather” protocol in [5], we can achieve an
overlap of size at least $n-t>2n/3$, at the cost of an extra round of message
exchange. While this stronger guarantee is not crucial to our feasibility
result, we use it to improve the agreement probability of our OCC, and
consequently the concrete round efficiency of our concurrent A-BA protocol.

Traditionally, existing protocols extract a single bit from the local views of
the random vector by instructing parties to take all existing coordinates
modulo $n$, outputting $0$ if any coordinate is $0$ and outputting $1$
otherwise. In contrast, our protocol represents a significant improvement by
going beyond the extraction of a single bit from the local views of the random
vector. This enhanced randomness extraction is through a combinatorial
observation regarding vectors of random values, as formulated in Lemma 4. This
observation allows the parties to agree non-interactively on certain
coordinates of the random vector with a constant probability, while also
ensuring that these agreed-upon coordinates lie within their overlap section.
The minimum such coordinate is then used to select a common output value from
the vector.

Another important observation regarding existing binary A-OCC protocols is the
lack of a proper termination mechanism. This poses significant challenges as
network delays can cause parties to operate out of sync. In such cases, some
parties may receive the output before completing their role in the execution,
and if they stop, others may not be able to generate the output at all. This
directly affects the simulator’s ability to accurately simulate the protocol,
especially in managing input and output delays in the ideal functionality.
This is mainly because, unlike the protocol, the ideal functionality ensures
that once a party receives the output, sufficient participation has occurred,
and any other party, regardless of others’ participation, can fetch the output
if activated sufficiently many times. One potential solution could be invoking
A-BA on the output at the end; however, this would create a circular
dependency since A-OCC itself is used to achieve A-BA. Instead, we choose to
adopt a simpler approach inspired by Bracha’s termination mechanism. This
approach resolves the participation issue without causing deadlocks and
ensures agreement if all parties initiate the procedure with the same value.
The formal description of our multi-valued asynchronous OCC protocol
$\Pi_{\mathsf{a\mathchar 45\relax occ}}$ appears in Figure 6.

Protocol $\Pi_{\mathsf{a\mathchar 45\relax occ}}^{V}$ The protocol is
parameterized by a set $V$ of possible outcomes. At the first activation,
verify that $\mathsf{sid}=(\mathcal{P},\mathsf{sid}^{\prime})$ for a player
set $\mathcal{P}$ of size $n$. Let
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lceil\frac{n}{3}\rceil-1$
and
$m\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\mathrm{lcm}(n^{2},|V|)$,
and let $\mathbb{F}$ be the smallest prime field with size at least $m$. Party
$P_{i}\in\mathcal{P}$ proceeds as follows. Initialize sets $C_{i}$, $G_{i}$,
$R_{i}$, and $S_{i}$ to $\emptyset$, flag $\mathsf{finished}$ to $0$, and
variables $Z_{i}$ and $y_{i}$ to $\bot$. Also initialize
$C_{j}^{\prime}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$,
$b_{j,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$,
$r_{k,j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$,
$v_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$, and
$z^{\prime}_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bot$
for all $j,k\in[n]$. Upon receiving input $(\texttt{input},\mathsf{sid})$ from
the environment, do the following. For each $j\in[n]$, choose
$x_{i,j}\xleftarrow{\mathrm{R}}[m]$ and send
$(\texttt{share},\mathsf{sid}_{i}^{\mathrm{share},j},x_{i,j})$ to an instance
of $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$ with SID
$\mathsf{sid}_{i}^{\mathrm{share},j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathcal{P},P_{i},\mathsf{sid}^{\prime},\texttt{share},j)$.
Upon receiving input $(\texttt{fetch},\mathsf{sid})$ from the environment, if
$\mathsf{finished}=1$ then output $(\texttt{output},\mathsf{sid},y_{i})$ to
the environment; else do: 1. For each $j,k\in[n]$, fetch the share from the
instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$ with
SID $\mathsf{sid}_{j}^{\mathrm{share},k}$. Upon receiving back
$(\texttt{shared},\mathsf{sid}_{j}^{\mathrm{share},k})$ set
$b_{j,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$, and if
$b_{j,l}=1$ for all $l\in[n]$ then update
$C_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=C_{i}\cup\\{P_{j}\\}$.
2. Wait until $|C_{i}|\geq t+1$. Then, send
$(\texttt{send},\mathsf{sid}_{i}^{\mathrm{attach}},C_{i}^{(t+1)})$ to an
instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{i}^{\mathrm{attach}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathcal{P},P_{i},\mathsf{sid}^{\prime},\texttt{attach})$.
3. For each $j\in[n]$, fetch the output from the instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{j}^{\mathrm{attach}}$. Upon receiving back
$(\texttt{output},\mathsf{sid}_{j}^{\mathrm{attach}},Y)$ where $|Y|=t+1$,
record
$C_{j}^{\prime}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=Y$ and
wait until $C_{j}^{\prime}\subseteq C_{i}$; then update
$G_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=G_{i}\cup\\{P_{j}\\}$.
4. Wait until $|G_{i}|\geq n-t$. Then, send
$(\texttt{send},\mathsf{sid}_{i}^{\mathrm{set}},G_{i}^{(n-t)})$ to an instance
of $\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{i}^{\mathrm{set}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathcal{P},P_{i},\mathsf{sid}^{\prime},\texttt{set})$.
5. For each $j\in[n]$, fetch the output from the instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{j}^{\mathrm{set}}$. Upon receiving back
$(\texttt{output},\mathsf{sid}_{j}^{\mathrm{set}},G_{j}^{\prime})$ where
$|G_{j}^{\prime}|=n-t$, wait until $G_{j}^{\prime}\subseteq G_{i}$; then
update
$R_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=R_{i}\cup\\{P_{j}\\}$.
6. Wait until $|R_{i}|\geq n-t$. Then, send
$(\texttt{send},\mathsf{sid}_{i}^{\mathrm{ready}},R_{i}^{(n-t)})$ to an
instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{i}^{\mathrm{ready}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathcal{P},P_{i},\mathsf{sid}^{\prime},\texttt{ready})$.
7. For each $j\in[n]$, fetch the output from the instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{j}^{\mathrm{ready}}$. Upon receiving back
$(\texttt{output},\mathsf{sid}_{j}^{\mathrm{ready}},R_{j}^{\prime})$ where
$|R_{j}^{\prime}|=n-t$, wait until $R_{j}^{\prime}\subseteq R_{i}$; then
update
$S_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=S_{i}\cup\\{P_{j}\\}$.
8. Wait until $|S_{i}|\geq n-t$. Then, record
$Z_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=G_{i}$. 9. If
$|S_{i}|\geq n-t$, then for each $P_{k}\in C_{j}^{\prime}$ such that $P_{j}\in
G_{i}$, send $(\texttt{rec},\mathsf{sid}_{k}^{\mathrm{share},j})$ to the
instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$ with
SID $\mathsf{sid}_{k}^{\mathrm{share},j}$.161616Note that reconstruction
inputs can be sent outside of the initial batch, if a party gets added to
$G_{i}$ later, but only one reconstruction input is ever sent per instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$. 10. For each
$P_{k}\in C_{j}^{\prime}$ such that $P_{j}\in G_{i}$, fetch the secret from
the instance of $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$
with SID $\mathsf{sid}_{k}^{\mathrm{share},j}$. Upon receiving back
$(\texttt{opened},\mathsf{sid}_{k}^{\mathrm{share},j},s)$ record
$r_{k,j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=s$, and if
$r_{l,j}\not=\bot$ for all $P_{l}\in C_{j}^{\prime}$ then set
$v_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{P_{l}\in
C_{j}^{\prime}}r_{l,j}\bmod m$. 11. Wait until $Z_{i}\not=\bot$ and
$v_{j}\not=\bot$ for all $P_{j}\in Z_{i}$. Then, let
$S\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{j\in[n]\mid
v_{j}\equiv v_{k}\mod{n^{2}}\text{ for some }k\not=j\\}$ and do the following.
Let
$z_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=v_{\min\\{S\\}}\bmod{|V|}$
(if $S=\emptyset$ then let $z_{i}$ be an arbitrary value from $V$) and send
$(\texttt{send},\mathsf{sid}_{i}^{\mathrm{term}},z_{i})$ to an instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{i}^{\mathrm{term}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\mathcal{P},P_{i},\mathsf{sid}^{\prime},\texttt{term})$.
12. For each $j\in[n]$, fetch the output from the instance of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$ with SID
$\mathsf{sid}_{j}^{\mathrm{term}}$. Upon receiving back
$(\texttt{output},\mathsf{sid}_{j}^{\mathrm{term}},x)$, record
$z^{\prime}_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=x$. 13.
Wait until $z^{\prime}_{j}\not=\bot$ for at least $n-t$ indices $j\in[n]$.
Then, set
$\mathsf{finished}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1$
and $y_{i}$ to the mode (most repeated value) among all
$z^{\prime}_{j}\not=\bot$.

Figure 6: The multi-valued asynchronous OCC protocol.

###  4.3 Security Proof

Having described our A-OCC protocol, we proceed to present and prove the
formal security statement that demonstrates how the protocol UC-realizes
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$. However, we first prove a
combinatorial observation regarding vectors of random values that facilitates
the security proof. We formulate this observation separately in the following
lemma, as it may be of independent interest.

######  Lemma 4.

Let $V$ be a vector of $n$ values chosen independently and uniformly at random
from a set $S$ of size $N\in\Theta(n^{2})$, and let $\alpha$ be a constant
satisfying $0<\alpha\leq 1$. Then for any subset of indices $I\subseteq[n]$
such that $|I|\geq\alpha n$, with constant probability $p$ there is at least
one repeated value in $V$; moreover, all of the repeated values are
constrained to the indices in $I$.

###### Proof.

It suffices to consider the case $|I|=\lceil\alpha n\rceil$. We first define
the following events. Denote by $V_{J}$ the restriction of $V$ to the indices
in $J\subseteq[n]$.

$\displaystyle E_{V}\colon$ At least two components of $V$ have the same value
$\displaystyle E_{V_{I}}\colon$ At least two components of $V_{I}$ have the
same value $\displaystyle E_{V_{I^{\mathrm{c}}}}\colon$ At least two
components of $V_{I^{\mathrm{c}}}$ have the same value $\displaystyle
E_{(V_{I},V_{I^{\mathrm{c}}})}\colon$ At least one component of $V_{I}$ has
the same value as a component of $V_{I^{\mathrm{c}}}$

We now compute

$\displaystyle p$ $\displaystyle={\mathrm{Pr}}[E_{V_{I}}\cap
E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}\cap
E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}]$
$\displaystyle={\mathrm{Pr}}[E_{V_{I}}\mathbin{|}E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}\cap
E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}]{\mathrm{Pr}}[E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}\cap
E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}]$
$\displaystyle\geq{\mathrm{Pr}}[E_{V_{I}}\mathbin{|}E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}\cap
E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}]{\mathrm{Pr}}[E^{\mathrm{c}}_{V}]$
$\displaystyle\left(E^{\mathrm{c}}_{V}\subseteq
E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}\cap
E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}\right)$
$\displaystyle=\left(1-{\mathrm{Pr}}[E^{\mathrm{c}}_{V_{I}}\mathbin{|}E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}\cap
E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}]\right){\mathrm{Pr}}[E^{\mathrm{c}}_{V}]$
$\displaystyle=\left(1-\frac{{\mathrm{Pr}}[E^{\mathrm{c}}_{V_{I}}\mathbin{\cap}E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}\cap
E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}]}{{\mathrm{Pr}}[E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}\mathbin{|}E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}]{\mathrm{Pr}}[E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}]}\right){\mathrm{Pr}}[E^{\mathrm{c}}_{V}]$
$\displaystyle=\left(1-\frac{{\mathrm{Pr}}[E^{\mathrm{c}}_{V}]}{{\mathrm{Pr}}[E^{\mathrm{c}}_{(V_{I},V_{I^{\mathrm{c}}})}\mathbin{|}E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}]{\mathrm{Pr}}[E^{\mathrm{c}}_{V_{I^{\mathrm{c}}}}]}\right){\mathrm{Pr}}[E^{\mathrm{c}}_{V}]$
$\displaystyle=\left(1-\frac{\prod_{i=0}^{n-1}\left(1-\frac{i}{N}\right)}{\left(1-\frac{n-\lceil\alpha
n\rceil}{N}\right)^{\lceil\alpha n\rceil}\prod_{i=0}^{n-\lceil\alpha
n\rceil-1}\left(1-\frac{i}{N}\right)}\right)\prod_{i=0}^{n-1}\left(1-\frac{i}{N}\right)$
$\displaystyle\approx\left(1-\frac{\prod_{i=0}^{n-1}\left(e^{-\frac{i}{N}}\right)}{\left(e^{-\frac{n-\lceil\alpha
n\rceil}{N}}\right)^{\lceil\alpha n\rceil}\prod_{i=0}^{n-\lceil\alpha
n\rceil-1}\left(e^{-\frac{i}{N}}\right)}\right)\prod_{i=0}^{n-1}\left(e^{-\frac{i}{N}}\right)$
$\displaystyle\left(\text{since }\frac{n}{N}\ll 1\right)$
$\displaystyle=\left(1-\frac{e^{-\frac{1}{N}\sum_{i=0}^{n-1}i}}{e^{-\frac{n\lceil\alpha
n\rceil-\lceil\alpha
n\rceil^{2}}{N}}\left(e^{-\frac{1}{N}\sum_{i=0}^{n-\lceil\alpha
n\rceil-1}i}\right)}\right)e^{-\frac{1}{N}\sum_{i=0}^{n-1}i}$
$\displaystyle=\left(1-\frac{e^{-\frac{n^{2}-n}{2N}}}{e^{-\frac{n\lceil\alpha
n\rceil-\lceil\alpha n\rceil^{2}}{N}}\left(e^{-\frac{n^{2}+\lceil\alpha
n\rceil^{2}-2n\lceil\alpha n\rceil-n+\lceil\alpha
n\rceil}{2N}}\right)}\right)e^{-\frac{n^{2}-n}{2N}}$
$\displaystyle=\left(1-e^{-\frac{\lceil\alpha n\rceil^{2}-\lceil\alpha
n\rceil}{2N}}\right)e^{-\frac{n^{2}-n}{2N}}$ $\displaystyle\in\Theta(1).$
$\displaystyle\left(\textrm{since}~{}N\in\Theta(n^{2})\right)\qed$

With the groundwork laid out, we now prove the security of protocol
$\Pi_{\mathsf{a\mathchar 45\relax occ}}$:

######  Theorem 1.

There exists a probability $p\in\Theta(1)$ such that for any integer domain
$V$, protocol $\Pi_{\mathsf{a\mathchar 45\relax occ}}^{V}$ UC-realizes
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}^{V,p}$ with perfect security
in the $(\mathcal{F}_{\mathsf{a\mathchar 45\relax
cast}},\allowbreak\mathcal{F}_{\mathsf{a\mathchar 45\relax
vss}}^{\mathbb{F}})$-hybrid model where $\mathbb{F}$ is the smallest prime
field of size at least $\mathrm{lcm}(|V|,\allowbreak n^{2})$, in constant
rounds and in the presence of an adaptive and malicious t-adversary, provided
$t<\frac{n}{3}$.

###### Proof.

Let $\mathcal{A}$ be an adversary in the real world. We construct a simulator
$\mathcal{S}$ in the ideal world, such that no environment $\mathcal{Z}$ can
distinguish whether it is interacting with $\Pi_{\mathsf{a\mathchar 45\relax
occ}}^{V}$ and $\mathcal{A}$, or with $\mathcal{F}_{\mathsf{a\mathchar
45\relax occ}}^{V,p}$ and $\mathcal{S}$, where $p$ is to be determined later.

The simulator internally runs a copy of $\mathcal{A}$, and plays the roles of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$,
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$, and the parties
in a simulated execution of the protocol. All inputs from $\mathcal{Z}$ are
forwarded to $\mathcal{A}$, and all outputs from $\mathcal{A}$ are forwarded
to $\mathcal{Z}$. Moreover, whenever $\mathcal{A}$ corrupts a party in the
simulation, $\mathcal{S}$ corrupts the same party in the ideal world by
interacting with $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}^{V,p}$, and
if the corruption was direct (i.e., not via either of the aiding
functionalities), then $\mathcal{S}$ sends $\mathcal{A}$ the party’s state and
thereafter follows $\mathcal{A}$’s instructions for that party. Moreover,
$\mathcal{S}$ manages delays in the ideal functionality based on the delays
that $\mathcal{A}$ sets on the hybrids.

The simulated execution commences when $\mathcal{S}$ receives the messages
$(\texttt{leakage},\mathsf{sid},P_{i})$ and
$(\texttt{reveal},\mathsf{sid},b,y)$ from $\mathcal{F}_{\mathsf{a\mathchar
45\relax occ}}$. During the internal execution, $\mathcal{S}$ faithfully
simulates the behavior of $\mathcal{F}_{\mathsf{a\mathchar 45\relax cast}}$.
As for $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$,
$\mathcal{S}$ can simulate the sharing phase without explicitly assigning any
random secrets to honest parties. However, the actual value of each secret
must be determined by $\mathcal{S}$ before $n-t$ parties participate in the
reconstruction phase of the corresponding $\mathcal{F}_{\mathsf{a\mathchar
45\relax vss}}^{\mathbb{F}}$ instance. It is crucial for $\mathcal{S}$ to
select these secrets in such a way that the output matches that of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$, while ensuring
indistinguishability between the real- and ideal-world views.

We first argue that every tally $v_{j}$ computed by an honest party $P_{i}$ is
uniformly distributed in $[m]$, and moreover that another honest party $P_{h}$
cannot compute a _different_ tally $v_{j}^{\prime}$ for party $P_{j}$
(although up to $t$ tallies may be “missing” from $P_{h}$’s view). Recall that
$P_{i}$ computes $v_{j}$ by summing the reconstructed secrets “attached” to
$P_{j}$ (i.e., the votes cast by the parties in $C_{j}^{\prime}$ for $P_{j}$).
An honest party $P_{k}\in C_{j}^{\prime}$ will have cast a uniform vote
$x_{k,j}\in[m]$, but even for a corrupted party a well-defined field element
will be reconstructed as its vote, since $P_{i}$ validated that
$C_{j}^{\prime}\subseteq C_{i}$ and $C_{i}$ contains parties whose secrets
were successfully shared to $P_{i}$. Moreover, the votes of corrupted parties
in $C_{j}^{\prime}$ are independent of those cast by honest parties in
$C_{j}^{\prime}$, because the secrets attached to $P_{j}$ are fixed by the
time the first honest party $P_{h}$ “accepts” $P_{j}$ (i.e., adds $P_{j}$ to
$G_{h}$)—due to the guarantees of $\mathcal{F}_{\mathsf{a\mathchar 45\relax
vss}}^{\mathbb{F}}$—while no honest party starts reconstructing them until it
considers $P_{j}$ as accepted. Since $|C_{j}^{\prime}|=t+1$, it must contain
at least one honest party, and therefore $P_{i}$ will compute a uniform tally
$v_{j}\in[m]$. Furthermore, since $P_{j}$ A-Casts the set $C_{j}^{\prime}$,
all honest parties will agree on the parties contributing to $P_{j}$’s tally,
and since any honest party $P_{h}$ computing $v_{j}$ has
$C_{j}^{\prime}\subseteq C_{h}$, by the guarantees of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}^{\mathbb{F}}$ they will all
reconstruct the secrets attached to $P_{j}$ to the same values. Therefore, we
can indeed speak of a _fixed_ vector of uniform tallies, where each honest
party eventually holds a local view of at least $n-t$ coordinates.

By employing an enhanced version of the counting argument in [41, 34] in the
same way as [5], we can demonstrate that once the first honest party $P_{i}$
reaches the stage where $|S_{i}|\geq n-t$, a subset $A$ of parties, with size
$n-t>2n/3$, becomes fixed such that each honest party $P_{h}$ will
(eventually) have $A\subseteq Z_{h}$. That is, over $2/3$ of the tallies will
be visible to all honest parties by the time they are able to generate output.
In more detail, assume that the honest party $P_{i}$ reaches the stage where
$s\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=|S_{i}|\geq n-t$. We
can construct an $s\times n$ table $T$, where $T_{j,k}=1$ if and only if
$P_{j}\in S_{i}$ and $P_{k}\in R_{j}^{\prime}$ (where $R_{j}^{\prime}$ was
received from $P_{j}$’s A-Cast).171717Technically the table has $n$ rows, each
corresponding to an A-Casted $R$-set, and $P_{i}$ has a local view of $s$ rows
that it has validated against $R_{i}$. Each row of the table contains
(exactly) $n-t$ entries equal to one, indicating that there are a total of
$s(n-t)$ one-entries in $T$. We claim that at least one column must contain at
least $t+1$ one-entries. Indeed, suppose to the contrary that each column
contains at most $t$ one-entries. Since $n-t\leq s$ and $t<n/3$, we have

$\frac{4}{9}n^{2}<(n-t)^{2}\leq s(n-t)\leq nt<\frac{1}{3}n^{2},$

which is a contradiction.

Therefore, we can conclude that some column $k$ in ($P_{i}$’s view of) the
table contains at least $t+1$ one-entries. Now consider another honest party
$P_{h}$ who reaches the stage $|S_{h}|\geq n-t$ and thereby records $Z_{h}$.
Since $(n-t)+(t+1)>n$, the $k$th column in $P_{h}$’s view of the table must
necessarily contain a one-entry. From the specification of the protocol, we
can deduce that $P_{k}\in R_{h}$, and hence $G_{k}^{\prime}\subseteq Z_{h}$
(where $G_{k}^{\prime}$ was received from $P_{k}$’s A-Cast). In other words,
there is a set
$A\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=G_{k}^{\prime}$ of
size $n-t$ such that every honest party $P_{h}$ will eventually have
$A\subseteq Z_{h}$.

Once the first honest party $P_{i}$ reaches the condition $|S_{i}|\geq n-t$,
the simulator $\mathcal{S}$, being aware of message delivery, can easily
determine the set $A$. Basically, $\mathcal{S}$ can form the table $T$ as
described above, find a column $k$ with at least $t+1$ ones, and then set
$A\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=G_{k}^{\prime}$ (or
rather the indices of the parties in $G_{k}^{\prime}$). Utilizing the set $A$,
and the values $b$ and $y$ received from $\mathcal{F}_{\mathsf{a\mathchar
45\relax occ}}$, the simulator is able to sample a vector of tallies that
follows the same distribution as in the real-world execution and results in
the same output as $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$ when
$b=1$. Let us now outline the process for this inverse sampling. We first
define the following events, given the set $A$ and a random vector
$(w_{1},\ldots,w_{n})$ where each element $w_{i}\xleftarrow{\mathrm{R}}[m]$.

  * •

$E_{1}$: There is at least one repeat in the vector
$(w^{\prime}_{1},\ldots,w^{\prime}_{n})$, where
$w^{\prime}_{i}=w_{i}\bmod{n^{2}}$ for all $i\in[n]$, and all the repeats lie
inside $A$.

  * •

$E_{1,y}$ for $y\in V$: The vector $(w_{1},\ldots,w_{n})$ is in $E_{1}$, and
the smallest index $j$ of the repeated elements in
$(w^{\prime}_{1},\ldots,w^{\prime}_{n})$, where
$w^{\prime}_{i}=w_{i}\bmod{n^{2}}$ for all $i\in[n]$, contains an element
$w_{j}$ congruent to $y$ modulo $|V|$.

  * •

$E_{2}$: There are no repeats at all in the vector
$(w^{\prime}_{1},\ldots,w^{\prime}_{n})$, where
$w^{\prime}_{i}=w_{i}\bmod{n^{2}}$ for all $i\in[n]$.

  * •

$E_{3}$: There is at least one repeat in the vector
$(w^{\prime}_{1},\ldots,w^{\prime}_{n})$, where
$w^{\prime}_{i}=w_{i}\bmod{n^{2}}$ for all $i\in[n]$, which is not fully
contained inside $A$.

The simulator $\mathcal{S}$ initially computes the precise probabilities of
the events $E_{1}$, $E_{2}$, and $E_{3}$.181818These probabilities only need
to be computable by the simulator to give a constructive description of
$\mathcal{S}$. Note that an existential argument, which is sufficient to
complete the emulation, would not require $\mathcal{S}$ to calculate those
probabilities at all. Nonetheless, we opt for a constructive approach to
better illustrate the concept. Given that $m=\mathrm{lcm}(n^{2},|V|)$,
sampling vectors uniformly from $[m]^{n}$ and taking each coordinate modulo
$n^{2}$ is equivalent to uniform sampling from $[n^{2}]^{n}$. Therefore, we
can compute the aforementioned probabilities by considering vectors
exclusively from $[n^{2}]^{n}$. Let $l=|A|$. For $1\leq k\leq l$, denote by
$N_{k}$ the number of ways to choose the elements inside $A$ from any fixed
subset of $k$ residues modulo $n^{2}$ such that _exactly_ $k$ distinct
residues are chosen (equivalently, the number of strings of length $l$ over an
alphabet of size $k$ that use each character at least once). We have the
following recursive expression for $N_{k}$.

$N_{k}=k^{l}-\sum_{i=1}^{k-1}\binom{k}{i}N_{i}$

Note that $N_{1},\ldots,N_{l}$ are efficiently computable. Moreover, for any
$1\leq k\leq l$, the number of ways to choose the elements in
$(w^{\prime}_{1},\ldots,w^{\prime}_{n})$ from $[n^{2}]$ such that $A$ contains
exactly $k$ distinct elements and all repeats (if any) lie inside $A$ is

$\binom{n^{2}}{k}N_{k}\prod_{j=0}^{n-l-1}(n^{2}-k-j).$

Noting that $k=l$ exactly corresponds to the case that there are no repeats at
all, we now compute
$p_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}={\mathrm{Pr}}[E_{i}]$
for $i\in[3]$:

$\displaystyle p_{1}$
$\displaystyle=\frac{1}{(n^{2})^{n}}\sum_{k=1}^{l-1}\left(\binom{n^{2}}{k}N_{k}\prod_{j=0}^{n-l-1}(n^{2}-k-j)\right)$
$\displaystyle p_{2}$
$\displaystyle=\frac{1}{(n^{2})^{n}}\prod_{j=0}^{n-1}(n^{2}-j)$ $\displaystyle
p_{3}$ $\displaystyle=1-p_{1}-p_{2}$

Now we present a sampling strategy utilized by $\mathcal{S}$ to ensure that
the vector of tallies is sampled in a manner that maintains both the observed
distribution in the real-world execution and the consistency of outputs with
the ideal functionality. This strategy is effective under the condition that
the probability of outputting a random common coin in the ideal functionality,
denoted as $p$, does not exceed the probability defined above as $p_{1}$,
which is the probability with which the protocol guarantees a random common
coin. Looking ahead, $\mathcal{S}$ is required to perform a task with a
probability denoted as $q_{1}$, which becomes negative if $p>p_{1}$, thereby
rendering the entire process unsound. For any $p\leq p_{1}$, the simulator
does the following:

  * •

If $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$ outputs $b=1$, uniformly
sample from $E_{1,y}$ where $y$ is the value received from
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$.

  * •

If $b=0$ is received from $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$:

    * –

With probability $q_{1}=\frac{p_{1}-p}{1-p}$, uniformly sample from $E_{1}$.

    * –

With probability $q_{2}=\frac{p_{2}}{1-p}$, uniformly sample from $E_{2}$.

    * –

With probability $q_{3}=\frac{p_{3}}{1-p}$, uniformly sample from $E_{3}$.

Before delving into the details of the sampling procedures, it is important to
understand why this inverse sampling approach effectively eliminates any
distinguishability. The simulator samples from $E_{1,y}\subseteq E_{1}$ when
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$ outputs $b=1$, and from
$E_{1}$ with probability $q_{1}$ when $\mathcal{F}_{\mathsf{a\mathchar
45\relax occ}}$ outputs $b=0$. Since $\mathcal{F}_{\mathsf{a\mathchar 45\relax
occ}}$ samples $b\leftarrow\mathrm{Bernoulli}(p)$, the simulator samples a
vector from $E_{1}$ with probability $p+(1-p)q_{1}=p_{1}$, which exactly
matches the probability in the real-world execution. Moreover, when $b=1$, the
simulator ensures that the element in the sample at the smallest index of a
repeated residue is congruent modulo $|V|$ to the value $y$ received from
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$, which guarantees that the
simulated view is consistent with the output of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$. It is important to note that
enforcing this constraint does not skew the probability since
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$ samples $y$ uniformly at
random from $V$ and $m$ is a multiple of $|V|$. In cases when $b=0$, the
simulator influences $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$ to
output values that match those in the simulated execution. Additionally,
$\mathcal{S}$ samples from $E_{2}$ and $E_{3}$ with probabilities $q_{2}$ and
$q_{3}$, respectively. Since $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$
outputs $b=0$ with probability $1-p$, the simulator samples from $E_{2}$ and
$E_{3}$ with respective probabilities $(1-p)q_{2}=p_{2}$ and
$(1-p)q_{3}=p_{3}$, which exactly match the corresponding real-world
probabilities. Therefore, this inverse sampling strategy ensures that there
are no distinguishability opportunities for $\mathcal{Z}$.

Now we explain how each sampling procedure works. The general approach is to
first determine the “repeat pattern,” which is encoded as a vector
$(r_{1},\ldots,r_{n})\in[n^{2}]^{n}$ of residues modulo $n^{2}$, consistently
with the event being sampled from, and then fill in each coordinate of the
vector $(w_{1},\ldots,w_{n})\in[m]^{n}$ by sampling from the corresponding
congruence class (with one caveat, discussed below). This is of course
equivalent to sampling the elements in $(w_{1},\ldots,w_{n})$ such that their
residues modulo $n^{2}$ have the appropriate repeat pattern, but it greatly
simplifies the presentation and also enables us to cast the procedure for
sampling from $E_{1,y}$ as a variation on the procedure for sampling from
$E_{1}$.

  * •

Procedure 1 (sampling from $E_{1}$ or $E_{1,y}$):

    1. 1.

Initialize $(w_{1},\ldots,w_{n})$ and $(r_{1},\ldots,r_{n})$ to
$(\bot,\ldots,\bot)$.

    2. 2.

Randomly choose two distinct indices $g$ and $h$ from $A$.191919Note that this
is well-defined since $|A|=n-t>2$ when $1\leq t<n/3$. Sample
$r_{g}=r_{h}\xleftarrow{\mathrm{R}}[n^{2}]$.

    3. 3.

For each $i\in A\setminus\\{g,h\\}$, sample
$r_{i}\xleftarrow{\mathrm{R}}[n^{2}]$.

    4. 4.

Fill in the remaining coordinates of $(r_{1},\ldots,r_{n})$ with random
_distinct_ residues that have not yet been chosen. That is, for each
$j\in[n]\setminus A$, sample
$r_{j}\xleftarrow{\mathrm{R}}[n^{2}]\setminus\cup_{k=1}^{n}\\{r_{k}\\}$.

    5. 4.5.

(Only if sampling from $E_{1,y}$) Let
$S\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{j\in[n]\mid
r_{j}=r_{k}\text{ for some }k\not=j\\}$, and sample
$x\xleftarrow{\mathrm{R}}\\{v\in[m]\mid v\equiv y\mod{|V|}\\}$. Set
$w_{\min\\{S\\}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=x$.
Then, randomly choose a permutation $\pi$ over $[n^{2}]$ such that
$\pi(r_{\min\\{S\\}})=x\bmod{n^{2}}$, and update
$r_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\pi(r_{i})$ for
each $i\in[n]$.

    6. 5.

For each $i\in[n]$ such that $w_{i}=\bot$, sample
$w_{i}\xleftarrow{\mathrm{R}}\\{v\in[m]\mid v\equiv r_{i}\mod{n^{2}}\\}$.

  * •

Procedure 2 (sampling from $E_{2}$):

    1. 1.

Initialize $(w_{1},\ldots,w_{n})$ to $(\bot,\ldots,\bot)$.

    2. 2.

Randomly choose $n$ distinct residues $r_{1},\ldots,r_{n}$ from $[n^{2}]$.

    3. 3.

For each $i\in[n]$, sample $w_{i}\xleftarrow{\mathrm{R}}\\{v\in[m]\mid v\equiv
r_{i}\mod{n^{2}}\\}$.

  * •

Procedure 3 (sampling from $E_{3}$):

    1. 1.

Initialize $(w_{1},\ldots,w_{n})$ and $(r_{1},\ldots,r_{n})$ to
$(\bot,\ldots,\bot)$.

    2. 2.

Randomly choose an index $g$ from $[n]\setminus A$ and an index $h$ from
$[n]\setminus\\{g\\}$. Sample $r_{g}=r_{h}\xleftarrow{\mathrm{R}}[n^{2}]$.

    3. 3.

For each $i\in[n]\setminus\\{g,h\\}$, sample
$r_{i}\xleftarrow{\mathrm{R}}[n^{2}]$.

    4. 4.

For each $i\in[n]$, sample $w_{i}\xleftarrow{\mathrm{R}}\\{v\in[m]\mid v\equiv
r_{i}\mod{n^{2}}\\}$.

The simulator uses Procedure 1 to sample from either $E_{1}$ or $E_{1,y}$. In
the former case, there is no need to ensure that the sample is consistent with
any particular output value. Thus, $\mathcal{S}$ can randomly “plant” a repeat
inside $A$, sample the rest of the residues appearing within $A$ totally at
random, and lastly round out the repeat pattern by selecting unused residues
for the indices outside of $A$. This process guarantees that we sample from
$E_{1}$ with the uniform distribution.

The latter case, in which $\mathcal{S}$ must sample from $E_{1}$ while
ensuring that the element at the smallest index of a repeated residue is
congruent to $y$ modulo $|V|$, requires a more complex approach. It is not
enough to simply follow Procedure 1 and then readjust the repeated residue
with minimum index (as well as the elements in the vector
$(w_{1},\ldots,w_{n})$ from the corresponding congruence class) at the end.
The reason is that adjusting values after sampling can potentially skew the
distribution of the repeat pattern. If we adjust only the values of existing
repeats, there is a chance that the adjusted value may match another repeated
value, altering the distribution by decreasing the number of distinct repeated
values and increasing the number of times a value is repeated. It is even
possible that the adjusted value will collide with a value outside of the
designated set $A$! On the other hand, introducing new repeats would increase
the number of distinct repeated values and once again deviate from the desired
distribution. Addressing these challenges requires careful consideration and
decision-making on the part of $\mathcal{S}$, as determining when to add new
repeats and when to readjust existing ones is a delicate task.

Fortunately, it is possible for $\mathcal{S}$ to carefully re-sample the
repeat pattern, preserving the overall _structure_ but ensuring consistency
with $y$. Since taking the repeated value with minimum index is a global
criterion, this two-pass strategy is essentially the best we can hope for. In
more detail, $\mathcal{S}$ starts by determining the (preliminary) repeat
pattern as if it were sampling from $E_{1}$; in this way, $\mathcal{S}$
obtains a correct distribution of repeats naturally induced by random values.
However, $\mathcal{S}$ now samples a random element $x\in[m]$ that is
congruent to $y$ modulo $|V|$, which is used to reassign the congruence class
(modulo $n^{2}$) associated with the smallest index of a repeated value in the
old repeat pattern (note that this new congruence class is not uniquely
determined by $y$). The set of distinct residues appearing in the repeat
pattern is then re-sampled around this constraint; in other words, we apply a
random permutation over residues with the property that the appropriate
residue is mapped to $x\bmod{n^{2}}$. The simulator now uses the modified
repeat pattern to sample the elements in $(w_{1},\ldots,w_{n})$, except that
the element at the smallest index of a repeated residue should be fixed to
$x$. By following this procedure, $\mathcal{S}$ is guaranteed to sample
uniformly from $E_{1,y}$, for any $y\in V$.

Procedure 2 is straightforward: $\mathcal{S}$ forms the repeat pattern by
choosing random residues, ensuring that no value is used more than once. This
simple strategy guarantees that the sample is drawn from $E_{2}$ and maintains
a uniform distribution.

Finally, in Procedure 3, the simulator first randomly plants a repeat
involving an index outside of $A$ (it does not matter whether the second index
is inside $A$ or not). Then, the remaining residues can be chosen randomly
without any restrictions. This process guarantees a uniform sample from
$E_{3}$.

That completes the inverse sampling process. With the knowledge of $A$, $b$,
and $y$, the simulator is able to sample a vector $(w_{1},\ldots,w_{n})$ that
is indistinguishable from the observations in the real-world execution.
Furthermore, the sampled vector is consistent with the output $y$ of the ideal
functionality when the fairness bit $b=1$.

After sampling the vector of tallies $(w_{1},\ldots,w_{n})$, the simulator
retains the flexibility to determine the secrets shared by honest parties.
This is possible because none of the honest parties engage in the
reconstruction phase of any $\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$
instance until the first honest party $P_{i}$ satisfies the condition
$|S_{i}|\geq n-t$. Consequently, $\mathcal{S}$ has sufficient time to make
decisions regarding the shared secrets without the need to leak them to the
adversary. At this point, $\mathcal{S}$ can initiate the opening of secrets
through the reconstruction phase of $\mathcal{F}_{\mathsf{a\mathchar 45\relax
vss}}$ in such a way that if an honest party recovers the $j$th tally $v_{j}$,
it will correspond to $v_{j}=w_{j}$. This can be accomplished by leveraging
the fact that each tally consists of secrets from $t+1$ parties, which must
include at least some honest parties. By appropriately adjusting the secrets
of the honest parties, $\mathcal{S}$ can ensure that the tally sums up to the
desired value. It is crucial to note that, according to the inverse sampling
process described above, the vector $(w_{1},\ldots,w_{n})$ maintains the same
distribution as in the real-world execution. Therefore, sampling random
secrets while conditioning them on the desired tallies does not introduce any
distinguishability in the views.

#### Correctness.

The above approach allows for generating an output in the simulated execution
matched with the output of the ideal functionality and results in a view
indistinguishable from the real-world execution if the inverse sampling
process works correctly. This is the case because when
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$ samples $b=1$ and $y$, the
simulator samples the vector of tallies from $E_{1,y}$ which guarantees the
same output $y$ for all the honest parties. On the other hand, when $b=0$ is
sampled by $\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$, $\mathcal{S}$ is
allowed to influence the output of $\mathcal{F}_{\mathsf{a\mathchar 45\relax
occ}}$. The simulator, who observes the simulated execution, can seize this
opportunity and exert influence to ensure that the output of
$\mathcal{F}_{\mathsf{a\mathchar 45\relax occ}}$ matches the output of the
simulated execution. As mentioned above, the inverse sampling process relies
on the fact that $p\leq p_{1}$. By a direct utilization of Lemma 4, we can
show that there is a constant lower bound for $p_{1}$ for any set $A$ with
size $|A|\geq\frac{2}{3}n$. Therefore, there exists some constant $p$ such
that $p\leq p_{1}$, which makes the simulation go through correctly.

#### Termination.

To ensure the termination of the protocol and maintain the
indistinguishability of the real and ideal worlds, we need to demonstrate that
the protocol will eventually terminate.

For each honest party $P_{j}$, the secret-sharing of all of its votes
$x_{j,1},\ldots,x_{j,n}$ will eventually succeed for any honest party $P_{i}$.
It is certainly the case then that every honest party $P_{i}$ will eventually
pass the threshold $|C_{i}|\geq t+1$ and A-Cast $C_{i}^{(t+1)}$.

Whenever an honest party $P_{h}$ adds $P_{j}$ to $C_{j}$, any other honest
party $P_{i}$ will eventually add $P_{j}$ to $C_{i}$. This is because
$\mathcal{F}_{\mathsf{a\mathchar 45\relax vss}}$ guarantees that if the
sharing of a secret succeeds for one honest party, then it will eventually
succeed for all honest parties. Since every honest party $P_{h}$ eventually
A-Casts $C_{h}^{(t+1)}$, every honest party $P_{i}$ will eventually receive at
least $n-t$ A-Casts $C_{j}^{\prime}$ satisfying $|C_{j}^{\prime}|=t+1$ and
$C_{j}^{\prime}\subseteq C_{i}$. Thus, every honest party $P_{i}$ will
eventually pass the threshold $|G_{i}|\geq n-t$ and A-Cast $G_{i}^{(n-t)}$.

Whenever an honest party $P_{h}$ adds $P_{j}$ to $G_{h}$, any other honest
party $P_{i}$ will eventually add $P_{j}$ to $G_{i}$. This is because $P_{h}$
received some $C_{j}^{\prime}$ from $P_{j}$’s A-Cast, where
$|C_{j}^{\prime}|=t+1$ and $C_{j}^{\prime}\subseteq C_{h}$, so eventually
$P_{i}$ will receive the same $C_{j}^{\prime}$, and following the analysis
above it will eventually hold that $C_{j}^{\prime}\subseteq C_{i}$ as well.
Since every honest party $P_{h}$ eventually A-Casts $G_{h}^{(n-t)}$, every
honest party $P_{i}$ will eventually receive at least $n-t$ A-Casts
$G_{j}^{\prime}$ satisfying $|G_{j}^{\prime}|=n-t$ and
$G_{j}^{\prime}\subseteq G_{i}$. Thus, every honest party $P_{i}$ will