UNI-MB - logo
UMNIK - logo
 
E-resources
Peer reviewed Open access
  • Staircase Codes for Secret ...
    Bitar, Rawad; Rouayheb, Salim El

    IEEE transactions on information theory, 02/2018, Volume: 64, Issue: 2
    Journal Article

    We study the communication efficient secret sharing (CESS) problem. A classical threshold secret sharing scheme encodes a secret into <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> shares given to <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> parties, such that any set of at least <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">t<n </tex-math></inline-formula>, parties can reconstruct the secret, and any set of at most <inline-formula> <tex-math notation="LaTeX">z </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">z<t<n </tex-math></inline-formula>, colluding parties cannot obtain any information about the secret. A CESS scheme satisfies the previous properties of threshold secret sharing. Moreover, it allows to reconstruct the secret from any set of <inline-formula> <tex-math notation="LaTeX">d\geq t </tex-math></inline-formula>, parties by reading and communicating the minimum amount of information. In this paper, we introduce three explicit constructions of CESS codes called Staircase codes . The first construction achieves optimal communication and read costs for a given <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula>. The second construction achieves optimal costs universally for all possible values of <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula> between <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula>. The third construction, which is the most general, achieves optimal costs universally for all values of <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula> in any given set <inline-formula> <tex-math notation="LaTeX">\Delta \subseteq \{t, {\dots },n\} </tex-math></inline-formula>. The introduced Staircase codes can store a secret of maximal size, i.e., equal to <inline-formula> <tex-math notation="LaTeX">t-z </tex-math></inline-formula> shares, and they are all designed over a small finite field <inline-formula> <tex-math notation="LaTeX">GF(q) </tex-math></inline-formula>, for any prime power <inline-formula> <tex-math notation="LaTeX">q> n </tex-math></inline-formula>. However, Staircase codes may require dividing the secret and the shares into many symbols. We also describe how Staircase codes can be used to construct threshold changeable secret sharing with minimum storage cost, i.e., minimum share size.