Master Thesis
Linear Codes for Secret Sharing
A secret sharing scheme is a method where shares of a secret are distributed so that only specific parties of a set of participants can reconstruct the secret by pooling their shares. Such a set of specific parties is referred to as ‘qualified’ and all the qualified sets together build the access structure of a secret sharing scheme. Secret sharing schemes are widely used in cryptographic protocols such as key management, key distribution, and disributed cryptosystems. In this thesis, we are interested in a large family of such schemes, called Linear Secret Sharing Schemes (LSSS), which use tools from linear algebra. McEliece and Sarwate [1] were the first which observed a connection between secret-sharing and linear codes, where a linear code C is a k-dimensional linear subspace of the vector space F_q^n. Massey [2] introduced a construction of LSSS using a linear code C and showed that the access structure is given by the minimal codewords of the dual code of C. By the dual code of a linear code C, we mean the orthogonal complement of C in F_q^n. However, determining the minimal codewords is a hard problem for general linear codes and therefore also determining the access structure is hard. But for some linear codes, several authors have investigated their minimal codewords and characterized the access structure of LSSS based on their dual codes.
In a first step of this thesis, the goal is to understand the basic notions of algebraic coding theory and secret-sharing schemes, and to see how one can construct LSSS based on linear codes. In a second step, the goal is to study the connection between the access structure and the minimal codewords of the dual of the underlying code. Based on this, another goal is to understand the access structures of LSSS using specific types of codes.
References
[1] On Sharing Secrets and Reed-Solomon Codes
[2] Minimal Codewords and Secret Sharing
[3] Code Based Secret Sharing Schemes