A Study on (t, n) Threshold Secret Sharing Schemes Based on the Generalized Vector Space Construction
Todorka Alexandrova · Institutional Repositories DataBase (IRDB) · 2008
A secret sharing scheme is a technique of sharing a secret s into n pieces, calledshares, and distributing them to a set of users P , fP1, .., Png in such a way thatonly certain qualified subsets of users can recover the secret by combining theirshares. As a special class of secret sharing schemes, threshold secret sharing schemeswere introduced. A secret sharing scheme is called a (t, n) threshold secret sharingscheme if knowledge of any t or more shares makes the secret s computable and theknowledge of any t 1 or fewer shares leaves s completely undetermined (in thesense that all its possible values are equally likely).Threshold secret sharing schemes are an important tool in the information security.In many of the real applications of the threshold secret sharing schemes itis important to be able to share the secret among a large number of users. In thisthesis we consider the scenario that the secret information is assumed to be very importantbut can be represented as a symbol and there are needs to be shared amonga really large number of users. Therefore we focus on (t, n) threshold secret sharingschemes such that the number of users n is to be increased as much as possible underthe condition that a a secret s is chosen from a finite field with q elements, whereq is a prime power. In fact, a secret of one bit would be very important in manyapplications in the real file where the secret might be the ”yes” or ”no” answer to areally important question (e. g. stock market, a company keeps excellent conditionor not, and so on).The efficiency of a given secret sharing scheme is measured by its informationrate ρ, which is the ratio between the size of the secret and the size of the shares.It has been proven that for perfect secret sharing schemes 0 ρ 1. Dependingon their information rate, secret sharing schemes can be divided into two classes ofideal and non-ideal secret sharing schemes. A secret sharing scheme is called ideal ifit is perfect and has information rate ρ = 1 and non-ideal if it has information rate0 ρ 3.The power k is a function of the size of the shares for each user and if an appropriatevalue of k has been chosen then (2, n) and (3, n) threshold secret sharing schemesfor any arbitrary n can be constructed.Thus, it is possible to increase the number of the users in the schemes for a fixedalphabet size q by increasing the number of the columns in the matrices correspondingto each user in the generalized vector space construction.Moreover, we present a recursive algorithm for constructing general (t, n) thresholdsecret sharing schemes for t ， 4 and any arbitrary n. The algorithm is basedon a combination between the proposed (2, n) threshold secret sharing schemes and(t 1, t 1) threshold secret sharing schemes.Using the proposed algorithms, a (t, n) threshold secret sharing scheme can beconstructed for any arbitrary number of users n and any threshold value t.