International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Communication Efficient Perfectly Secure VSS and MPC in Asynchronous Networks with Optimal Resilience

Authors:
Arpita Patra
Ashish Choudhary
C. Pandu Rangan
Download:
URL: http://eprint.iacr.org/2010/007
Search ePrint
Search Google
Abstract: Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among n parties, where t out of n parties can be under the influence of a Byzantine (active) adversary, having unbounded computing power. It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff n \geq 4t+1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with n=4t+1 as optimally resilient VSS (MPC) protocol. A secret is d-shared among the parties if there exists a random degree-d polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-d polynomial. Typically VSS is used as a primary tool to generate t-sharing of secret(s). In this paper, we present an optimally resilient, perfectly secure Asynchronous VSS (AVSS) protocol that can generate d-sharing of secret for any d, where t \leq d \leq 2t. This is the first optimally resilient, perfectly secure AVSS of its kind in the literature. Specifically, our AVSS can generate d-sharing of \ell \geq 1 secrets from F concurrently, with a communication cost of O(\ell n^2 \log{|F|}) bits, where F is a finite field. Communication complexity wise, the best known optimally resilient, perfectly secure AVSS is reported in [BH07]. The protocol of [BH07] can generate t-sharing of \ell secrets concurrently, with the same communication complexity as our AVSS. However, the AVSS of [BH07] and [BCG93] (the only known optimally resilient perfectly secure AVSS, other than [BH07]) does not generate d-sharing, for any d > t. Interpreting in a different way, we may also say that our AVSS shares \ell(d+1 -t) secrets simultaneously with a communication cost of O(\ell n^2 \log{|F|}) bits. Putting d=2t (the maximum value of d), we notice that the amortized cost of sharing a single secret using our AVSS is only O(n \log{|F|}) bits. This is a clear improvement over the AVSS of [BH07] whose amortized cost of sharing a single secret is O(n^2 \log{|F|}) bits. As an interesting application of our AVSS, we propose a new optimally resilient, perfectly secure Asynchronous Multiparty Computation (AMPC) protocol that communicates O(n^2 \log|F|) bits per multiplication gate. The best known optimally resilient perfectly secure AMPC is due to [BH07], which communicates O(n^3 \log|F|) bits per multiplication gate. Thus our AMPC improves the communication complexity of the best known AMPC of [BH07] by a factor of \Omega(n).
BibTeX
@misc{eprint-2010-22908,
  title={Communication Efficient Perfectly Secure VSS and MPC in Asynchronous Networks with Optimal Resilience},
  booktitle={IACR Eprint archive},
  keywords={foundations /},
  url={http://eprint.iacr.org/2010/007},
  note={ arpitapatra_10@yahoo.co.in 14617 received 8 Jan 2010},
  author={Arpita Patra and Ashish Choudhary and C. Pandu Rangan},
  year=2010
}