Secret Sharing Schemes Based on Error-Correcting Codes

DSpace Repository


Dokumentart: Dissertation
Date: 2016
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Informatik
Advisor: Hauck, Peter (Prof. Dr.)
Day of Oral Examination: 2016-06-03
DDC Classifikation: 004 - Data processing and computer science
Keywords: Kryptologie
Other Keywords: Reed-Muller Codes erster Ordnung
fehlerkorrigierende Codes
Secret Sharing Schemes
Beliebige Zugriffsstrukturen
first order Reed-Muller codes
error-correcting codes
secret sharing schemes
general access structures
License: Publishing license including print on demand
Order a printed copy: Print-on-Demand
Show full item record


In this thesis we present a new secret sharing scheme based on binary error-correcting codes, which can realize arbitrary (monotone or non-monotone) access structures. In this secret sharing scheme the secret is a codeword in a binary error-correcting code and the shares are binary words of the same length. When a group of participants wants to reconstruct the secret, the participants calculate the sum of their shares and apply Hamming decoding to that sum. The shares have the property that, when the group is authorized, the secret is the codeword which is closest to the sum of the shares. Otherwise, the sum differs strongly enough from the secret such that Hamming decoding yields another codeword. The shares can be described by the solutions of a system of linear equations which is closely related to first order Reed-Muller codes. We consider the case that there are only two different Hamming distances from the sums of the shares to the secret: one small distance k for the authorized sets and one large distance g for unauthorized sets. For this case a method of how to find suitable shares for arbitrary access structures is presented. In the resulting secret sharing scheme large code lengths are needed and the security distance g is rather small. In order to find classes of access structures which have more efficient and secure realizations, we classify the access structures such that all access structures of one class allow the same parameters g and k. Furthermore we study several changes in the access structure and their impact on the possible realizations. This gives rise to special classes of access structures defined by veto sets and necessary sets, which are particularly suitable for our approach.

This item appears in the following Collection(s)