Campus Event Calendar
Event Entry
New for: D2, D3
What and Who
Statistical Asynchronous Weak Commitment Scheme: A NewPrimitive to Design Statistical Asynchronous Verifiable SecretSharing Scheme
Ashish Choudhury
Indian Statistical Institute, Kolkata
SWS Colloquium
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 18 April 2011
15:00
60 Minutes
E 1 7
323
Saarbrücken
Abstract
Asynchronous Weak Secret Sharing (AWSS) is a well known
primitive for the design of statistical Asynchronous
Verifiable Secret Sharing (AVSS) schemes involving n parties. The
existing efficient AWSS schemes are based on the idea of sharing a
secret using bivariate polynomial and invokes n^2 instances of
another well known asynchronous primitive, namely Asynchronous
Information Checking Protocol (AICP). In this paper, we propose a
substitute for AWSS called asynchronous weak commitment
scheme (AWCS) that has weaker requirements in comparison to AWSS.
Due to its weaker requirements, AWCS is conceptually much simpler to
construct compared to AWSS. In fact, we can design AWCS using simple
Shamir secret sharing scheme (based on
univariate polynomial), instead of using bivariate polynomials.
Moreover, our AWCS invokes only n instances of AICP. Therefore, the
existing best known AVSS schemes call for only n^2 instances of AICP
when they incorporate our AWCS, as compared to n^3 instances
required earlier. This matches the number of instances of ICP
(synchronous version of AICP) invoked in the best known statistical
VSS schemes in the synchronous settings. We observe that we gain a
factor of \Theta(n) in the communication complexity when our AWCS is
used in the existing AVSS schemes in place of AWSS. This further
saves a factor of \Theta(n) in the communication complexity of the
best known existing asynchronous Byzantine agreement (ABA) and
asynchronous multiparty computation (AMPC) protocols where AVSS is
used as an important stepping stone.
primitive for the design of statistical Asynchronous
Verifiable Secret Sharing (AVSS) schemes involving n parties. The
existing efficient AWSS schemes are based on the idea of sharing a
secret using bivariate polynomial and invokes n^2 instances of
another well known asynchronous primitive, namely Asynchronous
Information Checking Protocol (AICP). In this paper, we propose a
substitute for AWSS called asynchronous weak commitment
scheme (AWCS) that has weaker requirements in comparison to AWSS.
Due to its weaker requirements, AWCS is conceptually much simpler to
construct compared to AWSS. In fact, we can design AWCS using simple
Shamir secret sharing scheme (based on
univariate polynomial), instead of using bivariate polynomials.
Moreover, our AWCS invokes only n instances of AICP. Therefore, the
existing best known AVSS schemes call for only n^2 instances of AICP
when they incorporate our AWCS, as compared to n^3 instances
required earlier. This matches the number of instances of ICP
(synchronous version of AICP) invoked in the best known statistical
VSS schemes in the synchronous settings. We observe that we gain a
factor of \Theta(n) in the communication complexity when our AWCS is
used in the existing AVSS schemes in place of AWSS. This further
saves a factor of \Theta(n) in the communication complexity of the
best known existing asynchronous Byzantine agreement (ABA) and
asynchronous multiparty computation (AMPC) protocols where AVSS is
used as an important stepping stone.
Contact
Brigitta Hansen
0681 - 93039102
--email hidden
passcode not visible
logged in users only
Brigitta Hansen, 04/15/2011 09:10
Brigitta Hansen, 04/13/2011 10:40
Brigitta Hansen, 04/13/2011 10:37 -- Created document.
Brigitta Hansen, 04/13/2011 10:40
Brigitta Hansen, 04/13/2011 10:37 -- Created document.