Higher Order MDS Codes for Combinatorial List Decoding and Distributed Multi-User Secret Sharing

Abstract

In this thesis two problems have been considered. The first one is related to the structure of higher order MDS codes which are a generalization of traditional MDS codes and the second one is related to distributed multi-user secret sharing. When data is transmitted over noisy channels, errors can occur, corrupting the received information. Traditional error-correcting codes like Reed-Solomon or Hamming codes are designed to correct a specific number of errors. However, they have a limitation that they can only correct up to a certain number of errors beyond which they fail to recover the original message. In many scenarios, such as wireless communication or storage systems, the number of errors can be quite high, and standard error-correction techniques might not be sufficient. This is where list decoding, proposed independently by Elias and Wozencraft, comes into play. Instead of trying to pinpoint the exact original message, list decoding provides a list of possible messages that could have been transmitted. By doing so, it offers a more flexible and robust approach to error correction, allowing for a higher number of correctable errors. The decoding radius is the maximum number of errors that can be corrected by the code. By increasing the decoding radius and allowing for a list of possible codewords, list decodable codes can handle a higher number of errors and provide a more robust approach to error correction. In a recent work by Shangguan and Tamo, an upper bound on the size of a list deocodable codes, called the Generalized Singleton bound, is derived for a given list size and decoding radius. The codes which meet this bound with equality are optimally list decodable codes. In our first problem, we study a recently introduced class of higher order MDS codes which are closely related to the optimally list decodable codes. For certain parameter regimes, we identify conditions under which performing expurgation and shortening (see Section 2.2) like operations on the higher order MDS codes based on Reed-Solomon codes obtained using Vandermonde matrix results in new higher order MDS codes with a related set of parameters. More specifically, we identify the conditions under which (n1, k1)-MDS(ℓ1) codes can be obtained from (n2, k2)-MDS(ℓ2) codes via various techniques where (n, k)-MDS(ℓ) codes denote higher order MDS codes of length n, dimension k and order ℓ ≥ 1. We also obtain a new field size upper bound for the existence of such codes which arguably improves over the best known existing bound in some parameter regimes. We believe that these results will aid in efficient constructions of higher order MDS codes. In the second problem, we focus on a Distributed Multi-User Secret Sharing (DMUSS) problem. Distributed Multi-User Secret Sharing is motivated by the need for secure and efficient ways to share sensitive information among multiple users in a decentralized manner. The traditional secret sharing scheme involves a single dealer dividing a secret into shares and distributing them among a group of users. However, this centralized approach has limitations, especially when dealing with large-scale systems or scenarios with multiple secrets and a large number of users. In DMUSS, each user can request access to a specific subset of secrets. This access control mechanism ensures that users only gain access to the secrets they are authorized to see. In this thesis we consider a DMUSS setting involving a dealer, n storage nodes and m secrets. Each user requests a subset of t out of the m secrets. Previous work in this setting addressed the case of t = 1 which we extend to handle general values of t. The users download shares from storage nodes based on the access structure and reconstruct their secrets. We establish a necessary condition on the access structure to ensure certain privacy conditions. Additionally, we establish a connection between access structures and disjunct matrices which are majorly used in the Group testing. In the Distributed Secret Sharing Protocol proposed for our setting, we utilize various disjunct matrix constructions and compare their performance in terms of the number of storage nodes and communication complexity. Moreover, we derive bounds on the optimal communication complexity of a distributed secret sharing protocol.