Abstract
Consider the communication efficient secret sharing problem. A dealer wants to share a secret with n parties such that any k ≤ n parties can reconstruct the secret and any z < k parties eavesdropping on their shares obtain no information about the secret. In addition, a legitimate user contacting any d, k ≤d ≤n, parties to decode the secret can do so by reading and downloading the minimum amount of information needed. We are interested in communication efficient secret sharing schemes that tolerate the presence of malicious parties actively corrupting their shares and the data delivered to the users. The knowledge of the malicious parties about the secret is restricted to the shares they obtain. We characterize the capacity, i.e., maximum size of the secret that can be shared. We derive the minimum amount of information needed to to be read and communicated to a legitimate user to decode the secret from d parties, k ≤d≤ n. We construct codes that achieve capacity. In addition, the constructed codes achieve minimum read and communication costs for all possible values of d. Our codes are based on Staircase codes, previously introduced for communication efficient secret sharing, and on the use of a pairwise hashing scheme used in distributed data storage and network coding settings to detect the presence of a limited knowledge adversary.
Original language | English |
---|---|
Title of host publication | 2020 IEEE International Symposium on Information Theory (ISIT) |
Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
Pages | 548-553 |
Number of pages | 6 |
ISBN (Electronic) | 9781728164328, 9781728164311 |
ISBN (Print) | 9781728164335 |
DOIs | |
Publication status | Published - 24 Aug 2020 |
Event | 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Los Angeles, United States Duration: 21 Jul 2020 → 26 Jul 2020 |
Publication series
Name | IEEE International Symposium on Information Theory |
---|---|
Publisher | IEEE |
ISSN (Print) | 2157-8095 |
ISSN (Electronic) | 2157-8117 |
Conference
Conference | 2020 IEEE International Symposium on Information Theory, ISIT 2020 |
---|---|
Country/Territory | United States |
City | Los Angeles |
Period | 21/07/20 → 26/07/20 |
Bibliographical note
Publisher Copyright:© 2020 IEEE.
Keywords
- cs.IT
- math.IT