A New Approach to Weighted Multi-Secret Sharing

Secret sharing is important in information and network security and has broad applications in the real world. Since an elegant secret sharing mechanism was first proposed by Shamir in 1979, many schemes have appeared in literature. These schemes deal with either single or multiple secrets and their shares have either the same weight or different weights. Weighted shares mean that different shares have different capabilities in recovering the secret(s) - a more (less) weighted share needs fewer (more) other shares to recover the secret(s). In this paper, we identify a direct relation between the length (i.e., the number of bits) and the weight of shares and, based on this relation, present a new Chinese Remainder Theorem (CRT) based weighted multiple secret sharing scheme. This scheme can also be naturally applied to other cases such as sharing a single secret with same-weight shares and is remarkably simple and easy to implement. Compared to both Shamir's scheme and Mignotte's scheme the representative of existing CRT based secret sharing schemes, the new scheme is more efficient than both schemes in share computation and more efficient than Shamir's scheme (and as efficient as Mignotte's scheme) in secret recovery. One prominent advantage of the new scheme is that the sizes of shares can vary distantly to fit different requirements and constraints of various devices such as sensors, PDAs, cell phones, iPads, hence, the new scheme is able to apply to broader applications involving wireless/sensor networks and pervasive computing.