Paper 2020/448
Partial Secret Sharing Schemes
Amir Jafari and Shahram Khazaei
Abstract
The information ratio of an access structure is an important parameter for quantifying the efficiency of the best secret sharing scheme (SSS) realizing it. The most common security notion is perfect security. The following relaxations, in increasing level of security, have been presented in the literature: quasi-perfect, almost-perfect and statistical. Understanding the power of relaxing the correctness and privacy requirements in the efficiency of SSSs is a long-standing open problem. In this article, we introduce and study an extremely relaxed security notion, called partial security, for which it is only required that any qualified set gains strictly more information about the secret than any unqualified one. To compensate the extreme imperfection, we quantify the efficiency of such schemes using a parameter called partial information ratio. Despite our compensation, partial security turns out weaker than the weakest mentioned non-perfect security notion, i.e., quasi-perfect security. We present three main results in this paper. First, we prove that partial and perfect information ratios coincide for the class of linear SSSs. Consequently, for this class, information ratio is invariant with respect to all security notions. Second, by viewing a partial SSS as a wiretap channel, we prove that for the general (i.e., non-linear) class of SSSs, partial and statistical information ratios are equal. Consequently, for this class, information ratio is invariant with respect to all non-perfect security notions. Third, we show that partial and almost-perfect information ratios do not coincide for the class of mixed-linear schemes (i.e., schemes constructed by combining linear schemes with different underlying finite fields). Our first result strengthens the previous decomposition theorems for constructing perfect linear schemes. Our second result leads to a very strong decomposition theorem for constructing general (i.e., non-linear) statistical schemes. Our third result provides a rare example of the effect of imperfection on the efficiency of SSSs for a certain class of schemes.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Information theoretic cryptographySecret sharingPerfect and non-perfect securityWiretap channelDecomposition methods
- Contact author(s)
- shahram khazaei @ gmail com
- History
- 2022-07-24: revised
- 2020-04-20: received
- See all versions
- Short URL
- https://ia.cr/2020/448
- License
-
CC BY