Distributed Multi-User Secret Sharing and Results on Unique and List Decoding of Codes

Abstract

In this thesis, we consider three problems relating to coding theory. The first problem is the application of codes to cryptography, while the other two problems tackle the ongoing developments of coding theory. We consider the secret sharing problem in the context of distributed storage. In this setup, there is a dealer, n storage nodes, m secrets, and m t
users. The dealer wants to share with each user a t-subset of secrets via storage nodes while ensuring weak secrecy condition. The user downloads shares from the storage nodes based on the designed storage structure and reconstructs its secrets. We extend upon a recent framework [1] (considering t = 1) to the case where each user requests a subset of secrets. We identify a necessary condition on the storage structure to ensure weak secrecy. A distributed secret sharing protocol (DSSP) encodes secrets into shares and distributes them onto the storage node. The number of shares created per secret is defined as the storage overhead of the DSSP, which is at least one to ensure the correctness condition. The goal is to design a DSSP with optimal storage overhead. We relate the storage structure of a DSSP to t-disjunct matrices used in group testing. Using a storage structure obtained from disjunct matrices, we design a weakly secure DSSP that achieves optimal storage overhead. Using several constructions for t-disjunct matrices, we compare their performance in terms of the number of storage nodes and communication complexity (total number of shares needed to be downloaded from storage nodes). The rate of a secret is the size of the secret normalized by the size of a share, and the capacity region of the problem is the set of all achievable rate tuples. For a specified storage structure, we characterize the capacity region of the problem. Next, we consider the unique decoding algorithms for Reed-Muller (RM) codes. RM codes were shown to be capacity-achieving on the binary memoryless symmetric channels using bitwise maximuma-posteriori (bit MAP) decoding [2]. We propose an RXA-Syndrome decoding algorithm for RM(m, m− 4) code that exploits the large symmetry in the automorphism group of RM codes and the optimality of the maximum likelihood (ML) decoder. Codes that meet the Singleton bound with equality are called Maximum Distance Separable (MDS) codes. In a sense, MDS codes achieve the optimal trade-off between the size of the code and its minimum distance. However, unique decoding of MDS codes can correct errors only up to a certain limit which is related to the minimum distance of the code. In the third problem, we consider the construction of codes that can correct errors beyond this limit. To this end, list decoding was introduced recently, which returns a list of codewords containing the correct codeword. We derive necessary and sufficient conditions for a code to be (t, L)-list decodable. Recently, list decodable codes that meet generalized Singleton bound were considered as the higher-order generalization of MDS codes. It is important to understand the structural properties of these codes to develop explicit constructions and efficient decoding algorithms. Motivated by these developments, we present new results on the structure of higher order MDS codes. We identify conditions under which (n1, k1)-MDS(ℓ1) codes can be obtained from (n2, k2)-MDS(ℓ2) codes. We also simplify the conditions under which an (n, k)-MDS(k − 1) code is also an MDS(k) code.