Improving the Round Complexity of 'Round-Optimal' VSS
We revisit the following question: what is the optimal round complexity of verifiable secret sharing~(VSS)? We focus here on the case of perfectly-secure VSS where the number of corrupted parties $t$ satisfies $t < n/3$, with $n$ being the total number of parties. Work of Gennaro et al. (STOC~2001) and Fitzi et al. (TCC~2006) shows that, assuming a broadcast channel, 3~rounds are necessary and sufficient for efficient VSS. The efficient 3-round protocol of Fitzi et al., however, treats the broadcast channel as being available ``for free'' and does not attempt to minimize its usage. As argued previously by the authors, this approach leads to poor round complexity when protocols are compiled for a point-to-point network. We show here a VSS protocol that is simultaneously optimal in terms of both the number of rounds and the number of invocations of broadcast. Our protocol also has a certain ``2-level sharing'' property that makes it useful for constructing protocols for general secure computation.
On Expected Constant-Round Protocols for Byzantine Agreement
In a seminal paper, Feldman and Micali (STOC '88) show an $n$-party Byzantine agreement protocol tolerating $t < n/3$ malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the existence of a secure signature scheme and a public-key infrastructure (PKI). Combined with existing results, this gives the first expected constant-round protocol for secure computation with honest majority in a point-to-point network assuming only one-way functions and a PKI. Our key technical tool --- a new primitive we introduce called moderated VSS --- also yields a simpler proof of the Feldman-Micali result. We also show a simple technique for sequential composition of protocols without simultaneous termination (something that is inherent for Byzantine agreement protocols using $o(n)$ rounds) for the case of $t<n/2$.
On Constructing Universal One-Way Hash Functions from Arbitrary One-Way Functions
A fundamental result in cryptography is that a digital signature scheme can be constructed from an arbitrary one-way function. A proof of this somewhat surprising statement follows from two results: first, Naor and Yung defined the notion of universal one-way hash functions and showed that the existence of such hash functions implies the existence of secure digital signature schemes. Subsequently, Rompel showed that universal one-way hash functions could be constructed from arbitrary one-way functions. Unfortunately, despite the importance of the result, a complete proof of the latter claim has never been published. In fact, a careful reading of Rompel's original conference publication reveals a number of errors in many of his arguments which have (seemingly) never been addressed. We provide here what is --- as far as we know --- the first complete write-up of Rompel's proof that universal one-way hash functions can be constructed from arbitrary one-way functions.
Reducing Complexity Assumptions for Statistically-Hiding Commitment
Determining the minimal assumptions needed to construct various cryptographic building blocks has been a focal point of research in theoretical cryptography. For most --- but not all! --- cryptographic primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation. In this work, we show that regular one-way functions suffice. We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a ``stepping-stone'' for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem. Our results also improve the complexity assumptions needed for statistical zero-knowledge arguments.