Paper 2008/172
The Round Complexity of Verifiable Secret Sharing Revisited
Arpita Patra, Ashish Choudhary, Tal Rabin, and C. Pandu Rangan
Abstract
The round complexity of interactive protocols is one of their most
important complexity measures. In this work we prove that existing lower bounds for the round complexity of VSS can be circumvented by introducing a negligible probability of error in the reconstruction phase. Previous results show matching lower and upper bounds of {\em three} rounds for VSS, with
Note: This paper is the combined version of our two papers titled "Probabilistic Verifiable Secret Sharing Tolerating Adaptive Adversary" and "Efficient Protocol for Generating IC Signature and its Application to Unconditional Verifiable Secret Sharing", which appeared earlier as ePrint Archive report no 2008/101 and 2008/172 respectively. The article 2008/172 was based on the improvement of the results of article 2008/101. However, there was a minor common bug in both the papers, which could be easily rectified. So instead of rectifying the bug separately in each paper, we corrected it and combined both the papers. We also changed the title of the combined paper as we found the new title to be more appropriate.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. This is a full version of thepaper that is accepted in CRYPTO 2009
- Keywords
- FoundationsVSSInformation Theoretic Security
- Contact author(s)
-
arpitapatra_10 @ yahoo co in
talr @ us ibm com - History
- 2009-06-05: last of 3 revisions
- 2008-04-21: received
- See all versions
- Short URL
- https://ia.cr/2008/172
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/172, author = {Arpita Patra and Ashish Choudhary and Tal Rabin and C. Pandu Rangan}, title = {The Round Complexity of Verifiable Secret Sharing Revisited}, howpublished = {Cryptology {ePrint} Archive, Paper 2008/172}, year = {2008}, url = {https://eprint.iacr.org/2008/172} }