Construction and Analysis of Nonlinear Secret Sharing Schemes

Abstract

A secret sharing scheme is a method by which a set of shares are generated from secret data. These shares are then distributed among a set of participants. The secret can then be recovered from the shares of legitimate subsets of participants. The set of these subsets is called the access structure of the scheme. If the functions that recover the secret from the shares are all linear, then the scheme is called a linear secret sharing scheme. The inherent linearity of these secret recovery functions enable participants to cheat by wrongly declaring their shares during secret recovery. An example of such an attack is the `Tompa-Woll' attack. In these attacks, the wrongly declared share leads to a wrongly recovered secret. However, the cheating participants can use the linearity of the recovery function to calculate the correct secret from the wrongly recovered one. Various verification techniques have been devised to detect this kind of cheating. An alternate method of resisting such attacks is by designing schemes with nonlinear secret recovery functions. These functions must be such that the cheating participants gain no information about the actual secret from the wrongly recovered one. This motivates the study of nonlinear secret sharing schemes.