Uniformly robust threshold secret sharing scheme with maximum threshold and reduced complexity of share computation and secret reconstruction

Abstract

A secret sharing scheme is a cryptographic protocol that enables a secret to be distributed among a prescribed set of participants in such a way that only certain (authorized) coalitions of participants are able to reconstruct the value of the secret by combining their components (shares of the secret). The collection of all authorized coalitions of participants is referred to as the access structure of the given secret sharing scheme. A scheme is called threshold if its access structure consists of all coalitions whose cardinality is bounded below by a fixed number, called the threshold.

This paper is devoted to the construction of a uniformly robust perfect threshold secret sharing scheme with the maximum threshold (equal to the number of participants), which is characterized by lower time complexity of share computation and secret reconstruction compared to a previously known analogous scheme. The robustness of a scheme means its unconditional security against attacks by dishonest participants who may substitute their own shares in order to distort the value of the secret during reconstruction. A secret sharing scheme is called uniformly robust if it remains secure against this attack regardless of the method used to select the set of secret keys from the collection of all elements that can potentially be distributed.

Interest in such secret sharing schemes is primarily motivated by the possibility of constructing perfect schemes for arbitrary access structures on their basis, which is acceptable for practical applications provided that each participant belongs to a not excessively large number of minimal authorized coalitions.

It is shown that the proposed secret sharing scheme is not inferior to the previously known one with respect to any efficiency metric, while significantly outperforming it in terms of the complexity of the secret sharing and reconstruction procedures. The proposed scheme is constructed on the basis of a random maximum-distance separable (MDS) code, which differs from the Reed–Solomon code underlying the construction of the previously known scheme. This feature makes it possible to reduce the computational complexity without increasing either the amount of data stored by the participants or the probability of successful share substitution by dishonest participants.