On Secret Reconstruction in Secret Sharing Schemes

• Published in: IEEE transactions on information theory 2008-01, Vol.54 (1), p.473-480
• Main Authors: Huaxiong Wang, Wong, D.S.
• Format: Article
• Language: English
• Subjects: Applied sciences; Australia Council; Broadcasting; Channels; Combinatorial analysis; Communication channels; Complexity theory; Computer science; Costs; Cover-free family; Cryptography; Equivalence; Exact sciences and technology; Information security; Information sharing; Information theory; Information, signal and communications theory; information-theoretic security; Lower bounds; Mathematical problems; Multicast communication; Optimization; Phases; Physics computing; Reconstruction; Secret; secret sharing; Signal and communications theory; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Transmission and modulation (techniques and equipments)
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2007.911179

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 is the number of participants in a secret sharing scheme. We also study the communication rates of partial broadcast channels for the secret reconstruction.