Paper 2005/337
Statistical Multiparty Computation Based on Random Walks on Graphs
Liangliang Xiao, Mulan Liu, and Zhifang Zhang
Abstract
With respect to a special class of access structures based on connectivity of graphs, we start from a linear secret sharing scheme and turn it into a secret sharing scheme with perfect security and exponentially small error probability by randomizing the reconstruction algorithm through random walks on graphs. It reduces the polynomial work space to logarithmic. Then we build the corresponding statistical multiparty computation protocol by using the secret sharing scheme. The results of this paper also imply the inherent connections and influences among secret sharing, randomized algorithms, and secure multi-party computation.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- secret sharingdistributed cryptography
- Contact author(s)
-
mlliu @ amss ac cn
zfz @ amss ac cn - History
- 2005-09-27: received
- Short URL
- https://ia.cr/2005/337
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/337,
author = {Liangliang Xiao and Mulan Liu and Zhifang Zhang},
title = {Statistical Multiparty Computation Based on Random Walks on Graphs},
howpublished = {Cryptology ePrint Archive, Paper 2005/337},
year = {2005},
note = {\url{https://eprint.iacr.org/2005/337}},
url = {https://eprint.iacr.org/2005/337}
}
