Header menu link for other important links
X
Efficient statistical asynchronous verifiable secret sharing with optimal resilience
Ashish Choudhary,
Published in
2010
Volume: 5973 LNCS
   
Pages: 74 - 92
Abstract
We present a new statistical asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience; i.e. with n = 3t + 1, where n is the total number of participating parties and t is the maximum number of parties that can be under the control of a computationally unbounded active adversary A t. Our protocol privately communicates O((ℓn3 + n 4k)k) bits and A-casts O(n3 log(n)) bits to simultaneously share ℓ ≥ 1 elements from a finite field double-struck F, where k is the error parameter. There are only two known statistical AVSS protocols with n = 3t + 1, reported in [11] and [26]. The AVSS protocol of [11] requires a private communication of O(n9 k4) bits and A-cast of O(n 9 k2 log(n)) bits to share a single element from double-struck F. Thus our AVSS protocol shows a significant improvement in communication complexity over the AVSS of [11]. The AVSS protocol of [26] requires a private communication of O((ℓn3 + n4)k) bits and A-cast of O((ℓn3 + n4)k) bits to share ℓ ≥ 1 elements. However, the shared element(s) may be NULL ∉ double-struck F. Thus our AVSS is better than the AVSS of [26] due to two reasons: (a) The A-cast communication of our AVSS is independent of the number of secrets i.e. ℓ; (b) Our AVSS makes sure that the shared value(s) always belong to double-struck F. Using our AVSS, we design a new primitive called Asynchronous Complete Secret Sharing (ACSS) which is an essential building block of asynchronous multiparty computation (AMPC). Using our ACSS scheme, we can design a statistical AMPC with optimal resilience; i.e., with n = 3t + 1, that privately communicates O(n5 k) bits per multiplication gate. This will significantly improve the only known statistical AMPC of [8] with n = 3t + 1, which privately communicates Ω(n11 k4) bits and A-cast Ω(n11 k2 log(n)) bits per multiplication gate. © 2010 Springer-Verlag.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN03029743
Open AccessNo
Concepts (19)
  •  related image
    ACTIVE ADVERSARY
  •  related image
    BELONG TO
  •  related image
    Building blockes
  •  related image
    CAN DESIGN
  •  related image
    Communication complexity
  •  related image
    ERROR PARAMETERS
  •  related image
    Finite fields
  •  related image
    MULTIPARTY COMPUTATION
  •  related image
    OPTIMAL RESILIENCE
  •  related image
    PRIVATE COMMUNICATION
  •  related image
    Secret sharing
  •  related image
    SHARED VALUES
  •  related image
    SINGLE ELEMENT
  •  related image
    VERIFIABLE SECRET SHARING
  •  related image
    Communication
  •  related image
    Information theory
  •  related image
    Optimization
  •  related image
    Security of data
  •  related image
    Statistics