Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
The Round Complexity of Verifiable Secret Sharing: The Statistical Case
verfasst von : Ranjit Kumaresan, Arpita Patra, C. Pandu Rangan
Erschienen in: Advances in Cryptology - ASIACRYPT 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the round complexity of a basic cryptographic task:
verifiable secret sharing
(VSS). This well-studied primitive provides a good “test case” for our understanding of round complexity in general; moreover, VSS is important in its own right as a central building block for, e.g., Byzantine agreement and secure multi-party computation.
The round complexity of
perfect
VSS was settled by Gennaro et al. (STOC 2001) and Fitzi et al. (TCC 2006). In a surprising result, Patra et al. (Crypto 2009) recently showed that if a negligible probability of error is allowed, the previous bounds no longer apply. We settle the key questions left open by their work, and in particular determine the
exact
round complexity of statistical VSS with optimal threshold. Let
n
denote the number of parties, at most
t
of whom are malicious. Their work showed that 2-round statistical VSS is impossible for
t
≥
n
/3. We show that 3-round statistical VSS is possible iff
t
<
n
/2. We also give an
efficient
4-round protocol for
t
<
n
/2.