License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2020.2
URN: urn:nbn:de:0030-drops-121079
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12107/
Eriguchi, Reo ;
Kunihiro, Noboru
d-Multiplicative Secret Sharing for Multipartite Adversary Structures
Abstract
Secret sharing schemes are said to be d-multiplicative if the i-th shares of any d secrets s^(j), jā[d] can be converted into an additive share of the product ā_{jā[d]}s^(j). d-Multiplicative secret sharing is a central building block of multiparty computation protocols with minimum number of rounds which are unconditionally secure against possibly non-threshold adversaries. It is known that d-multiplicative secret sharing is possible if and only if no d forbidden subsets covers the set of all the n players or, equivalently, it is private with respect to an adversary structure of type Q_d. However, the only known method to achieve d-multiplicativity for any adversary structure of type Q_d is based on CNF secret sharing schemes, which are not efficient in general in that the information ratios are exponential in n.
In this paper, we explicitly construct a d-multiplicative secret sharing scheme for any ?-partite adversary structure of type Q_d whose information ratio is O(n^{?+1}). Our schemes are applicable to the class of all the ?-partite adversary structures, which is much wider than that of the threshold ones. Furthermore, our schemes achieve information ratios which are polynomial in n if ? is constant and hence are more efficient than CNF schemes. In addition, based on the standard embedding of ?-partite adversary structures into ā^?, we introduce a class of ?-partite adversary structures of type Q_d with good geometric properties and show that there exist more efficient d-multiplicative secret sharing schemes for adversary structures in that family than the above general construction. The family of adversary structures is a natural generalization of that of the threshold ones and includes some adversary structures which arise in real-world scenarios.
BibTeX - Entry
@InProceedings{eriguchi_et_al:LIPIcs:2020:12107,
author = {Reo Eriguchi and Noboru Kunihiro},
title = {{d-Multiplicative Secret Sharing for Multipartite Adversary Structures}},
booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)},
pages = {2:1--2:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-151-1},
ISSN = {1868-8969},
year = {2020},
volume = {163},
editor = {Yael Tauman Kalai and Adam D. Smith and Daniel Wichs},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12107},
URN = {urn:nbn:de:0030-drops-121079},
doi = {10.4230/LIPIcs.ITC.2020.2},
annote = {Keywords: Secret sharing scheme, multiplicative secret sharing scheme, multipartite adversary structure}
}
|
Keywords: |
|
Secret sharing scheme, multiplicative secret sharing scheme, multipartite adversary structure |
|
Collection: |
|
1st Conference on Information-Theoretic Cryptography (ITC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.06.2020 |
