CEU Electronic Theses and Dissertations, 2011
| Author | Gergely, Peter Miklos |
|---|---|
| Title | From database theory to secret sharing |
| Summary | A database can be considered as a matrix where a sufficiently large set of columns (a key) will uniquely determine the rows. Given the number of columns and the family of minimal keys an interesting task is to find the minimal number of rows with which a matrix can be constructed that fulfills these requirements. Secret sharing is based on a similar situation. There is a treasure box with many keyholes with each participant holding a key. The box can only be opened if at least a given number of key holders pool their resources together. This can also be formulated by a matrix where the participants are represented by the columns and the treasures are the indices of the rows. Here one can also ask what the minimum number of rows is with which this situation can be reached. In both problems insufficient resources should not determine the row/secret. However, in real life applications we need stronger security. We cannot allow the possibilities to be narrowed down to the point where brute force is enough to find the correct one. Also we may require that the keys of the participants must be changed from time to time, in other words there must be many sets of partial secrets which properly function. The main task of the present thesis is to investigate mathematical problems lying in-between. There is a very wide class of problems which are special cases of the general problem obtained as a common generalization of problems in database theory and secret sharing. |
| Supervisor | Katona, Gyula O. H. |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2011/tphgep01.pdf |
Visit the CEU Library.
© 2007-2021, Central European University