TY - JOUR
T1 - On secret reconstruction in secret sharing schemes
AU - Wang, Huaxiong
AU - Wong, Duncan S.
N1 - Copyright 2008 IEEE. Reprinted from IEEE transactions on information theory. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Macquarie University’s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to [email protected]. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.
PY - 2008/1
Y1 - 2008/1
N2 - A secret sharing scheme typically requires secure communications in each of two distribution phases: 1) a dealer distributes shares to participants (share distribution phase); and later 2) the participants in some authorised subset send their share information to a combiner (secret reconstruction phase). While problems on storage required for participants, for example, the size of shares, have been well studied, problems regarding the communication complexity of the two distribution phases seem to have been mostly neglected in the literature so far. In this correspondence, we deal with several communication related problems in the secret reconstruction phase. Firstly, we show that there is a tradeoff between the communication costs and the number of participants involved in the secret reconstruction. We introduce the communication rate as the ratio of the secret size and the total number of communication bits transmitted from the participants to the combiner in the secret reconstruction phase. We derive a lower bound on the communication rate and give constructions that meet the bound. Secondly, we show that the point-to-point secure communication channels for participants to send share information to the combiner can be replaced with partial broadcast channels. We formulate partial broadcast channels as set systems and show that they are equivalent to the well-known combinatorial objects of cover-free family. Surprisingly, we find that the number of partial broadcast channels can be significantly reduced from the number of point-to-point secure channels. Precisely, in its optimal form, the number of channels can be reduced from n to Ο(log n), where n is the number of participants in a secret sharing scheme. We also study the communication rates of partial broadcast channels for the secret reconstruction.
AB - A secret sharing scheme typically requires secure communications in each of two distribution phases: 1) a dealer distributes shares to participants (share distribution phase); and later 2) the participants in some authorised subset send their share information to a combiner (secret reconstruction phase). While problems on storage required for participants, for example, the size of shares, have been well studied, problems regarding the communication complexity of the two distribution phases seem to have been mostly neglected in the literature so far. In this correspondence, we deal with several communication related problems in the secret reconstruction phase. Firstly, we show that there is a tradeoff between the communication costs and the number of participants involved in the secret reconstruction. We introduce the communication rate as the ratio of the secret size and the total number of communication bits transmitted from the participants to the combiner in the secret reconstruction phase. We derive a lower bound on the communication rate and give constructions that meet the bound. Secondly, we show that the point-to-point secure communication channels for participants to send share information to the combiner can be replaced with partial broadcast channels. We formulate partial broadcast channels as set systems and show that they are equivalent to the well-known combinatorial objects of cover-free family. Surprisingly, we find that the number of partial broadcast channels can be significantly reduced from the number of point-to-point secure channels. Precisely, in its optimal form, the number of channels can be reduced from n to Ο(log n), where n is the number of participants in a secret sharing scheme. We also study the communication rates of partial broadcast channels for the secret reconstruction.
UR - http://www.scopus.com/inward/record.url?scp=38349104231&partnerID=8YFLogxK
U2 - 10.1109/TIT.2007.911179
DO - 10.1109/TIT.2007.911179
M3 - Article
AN - SCOPUS:38349104231
SN - 0018-9448
VL - 54
SP - 473
EP - 480
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 1
ER -