On the Rate Region of Symmetric Multilevel Imperfect Secret Sharing

In this paper, we introduce an n-channel multilevel imperfect secret sharing problem, which can be regarded as a generalization of secret sharing and a variation of multilevel diversity coding. In this model, a discrete memoryless source (DMS) is encoded into n encoded messages. To measure the secrecy of the system, we introduce a security level for each subset of encoded messages. In the paper, we focus on the n-channel symmetric multilevel imperfect secret sharing (SMISS) problem, i.e., the security levels of all the subsets with the same cardinality are identical. First, we explicitly characterize the coding rate regions for 2-channel and 3-channel SMISS problems. However, it is difficult to characterize the explicit rate region for a general n, since the complexity of designing optimal coding schemes can grow with n exponentially. Nevertheless, we put forward an inner bound and an outer bound on the rate region of the general n-channel SMISS problem. Moreover, we consider two special cases, i.e., the Two-SMISS problem and the linear SMISS problem, and prove that the inner and outer bounds are tight for these two problems, respectively.

Automated summary

This paper introduces an n-channel multilevel imperfect secret sharing problem, encoding a DMS into n messages and introducing security levels to measure secrecy. The paper focuses on the symmetric multilevel imperfect secret sharing (SMISS) problem and provides inner and outer bounds on the rate region for a general n. Additionally, special cases like Two-SMISS and linear SMISS problems are considered, with tight inner and outer bounds proven for these cases.