Paper 2012/121

An Efficient Multistage Secret Sharing Scheme Using Linear One-way Functions and Bilinear Maps

Mitra Fatemi, Taraneh Eghlidos, and Mohammadreza Aref

Abstract

In a Multistage Secret Sharing (MSSS) scheme, the authorized subsets of participants could reconstruct a number of secrets in consecutive stages. A One-Stage Multisecret Sharing (OSMSS) scheme is a special case of MSSS schemes that all secrets are recovered simultaneously. In these schemes, in addition to the individual shares, the dealer should provide the participants with a number of public values related to the secrets. The less the number of public values, the more efficient the scheme. It is desired that MSSS and OSMSS schemes provide the computational security; however, we show in this paper that OSMSS schemes do not fulfill the promise. Furthermore, by introducing a new multi-use MSSS scheme based on linear one-way functions, we show that the previous schemes can be improved in the number of public values. Compared to the previous MSSS schemes, the proposed scheme has less complexity in the process of share distribution. Finally, using bilinear maps, the participants are provided with the ability of verifying the released shares from other participants. To the best of our knowledge, this is the first verifiable MSSS scheme in which the number of public values linearly depends on the number of the participants and the secrets and which does not require secure communication channels.