Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/46655
22 Visitors
27 Hits
2 Downloads
- Title
- On secret reconstruction in secret sharing schemes
- Related
- IEEE transactions on information theory, Vol. 54, Issue 1, p.6-13
- DOI
- 10.1109/TIT.2007.911179
- Publisher
- IEEE
- Date
- 2008
- Author/Creator
- Wang, Huaxiong
- Author/Creator
- Wong, Duncan S
- Description
- 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.
- Description
- 8 page(s)
- Subject Keyword
- cover-free family
- Subject Keyword
- cryptography
- Subject Keyword
- information-theoretic security
- Subject Keyword
- multicast communication
- Subject Keyword
- secret sharing
- Resource Type
- journal article
- Organisation
- Macquarie University. Dept. of Computing
- Identifier
- http://hdl.handle.net/1959.14/46655
- Identifier
- ISSN:0018-9448
- Identifier
- mq-rm-2008003355
- Language
- eng
- Rights
- 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 pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.
- Full Text
- Reviewed
-
-
