【文件属性】：
文件名称：On Secret Reconstruction in Secret Sharing Schemes
文件大小：312KB
文件格式：PDF
更新时间：2012-05-28 01:08:00
Secret Sharing Schemes
Abstract—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 O(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.