Staircase Codes for Secret Sharing With Optimal Communication and Read Overheads

DOI10.1109/TIT.2017.2723019MaRDI QIDQ4566677zbMATH OpenFDO

Authors Rawad Bitar, Salim El Rouayheb

Publication date 27 June 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.02990

Mathematics Subject Classification ID

Authentication, digital signatures and secret sharing (94A62)

Abstract: We study the communication efficient secret sharing (CESS) problem introduced by Huang, Langberg, Kliewer and Bruck. A classical threshold secret sharing scheme randomly encodes a secret into $n$ shares given to $n$ parties, such that any set of at least $t$, $t<n$, parties can reconstruct the secret, and any set of at most $z$, $z<t$, parties cannot obtain any information about the secret. Recently, Huang et al. characterized the achievable minimum communication overhead (CO) necessary for a legitimate user to decode the secret when contacting $dgeqt$ parties and presented explicit code constructions achieving minimum CO for $d=n$. The intuition behind the possible savings on CO is that the user is only interested in decoding the secret and does not have to decode the random keys involved in the encoding process. In this paper, we introduce a new class of linear CESS codes called Staircase Codes over any field $GF(q)$, for any prime power $q>n$. We describe two explicit constructions of Staircase codes that achieve minimum communication and read overheads respectively for a fixed $d$, and universally for all possible values of $d,tleqdleqn$.

Recommendations

• Code based secret sharing schemes. Applied combinatorial coding theory
• A note on ramp secret sharing schemes from error-correcting codes
• Multisecret-sharing schemes and bounded distance decoding of linear codes
• Near-optimal secret sharing and error correcting codes in \(\mathsf{AC}^0\)
• On the composition of secret sharing schemes related to codes
• Secret-sharing with a class of ternary codes
• Improved decoding and error floor analysis of staircase codes
• Optimal codes from Fibonacci polynomials and secret sharing schemes
• Characterization of some minimal codes for secret sharing
• Coding theorem for secret sharing communication systems with two noisy channels

Cited in

(5)

• Universal secure rank-metric coding schemes with optimal communication overheads
• Multi-party quantum secret sharing protocol based on GHZ states entanglement swapping
• Threshold changeable ramp secret sharing
• A practical and efficient quantum threshold secret sharing scheme
• A communication-efficient quantum threshold secret sharing scheme

This page was built for publication: Staircase Codes for Secret Sharing With Optimal Communication and Read Overheads

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566677)