  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 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 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. 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.
