Multiple Threshold Schemes Under The Weak Secure Condition

Jiahong Wu, Nan Liu, Wei Kang J. Wu and N. Liu are with the National Mobile Communications Research Laboratory, Southeast University, Nanjing, China (email: {jiahongwu,nanliu}@seu.edu.cn). W. Kang is with the School of Information Science and Engineering, Southeast University, Nanjing, China (email: [email protected]). This work was partially supported by the National Natural Science Foundation of China under Grants

61971135

, the Research Fund of National Mobile Communications Research Laboratory, Southeast University (No. 2020A03) and Six talent peaks project in Jiangsu Province.

Abstract

In this paper, we consider the case that sharing many secrets among a set of participants using the threshold schemes. All secrets are assumed to be statistically independent and the weak secure condition is focused on. Under such circumstances we investigate the infimum of the (average) information ratio and the (average) randomness ratio for any structure pair which consists of the number of the participants and the threshold values of all secrets.

For two structure pairs such that the two numbers of the participants are the same and the two arrays of threshold values have the subset relationship, two leading corollaries are proved following two directions. More specifically, the bound related to the lengths of shares, secrets and randomness for the complex structure pair can be truncated for the simple one; and the linear schemes for the simple structure pair can be combined independently to be a multiple threshold scheme for the complex one. The former corollary is useful for the converse part and the latter one is helpful for the achievability part.

Three new bounds special for the case that the number of secrets corresponding to the same threshold value $t$ is lager than $t$ and two novel linear schemes modified from the Vandermonde matrix for two similar cases are presented. Then come the optimal results for the average information ratio, the average randomness ratio and the randomness ratio. We introduce a tiny example to show that there exists another type of bound that may be crucial for the information ratio, to which we only give optimal results in three cases.

Index Terms:

multi-secret sharing, threshold access structure, the weak secure condition, the Shannon-type inequality, polyhedral cone, projection, generator matrix, linear scheme, Vandermonde matrix, Gaussian Elimination

I introduction

A secret sharing scheme is a method to share a secret among a set of participants such that only certain subsets of participants can recover the secret while any other subset obtains nothing[1].

Establishing bounds on the length of the shares to be given to participants in secret sharing schemes is one of the fundamental problems. If the length of the shares given to participants are too long compared to the length of the secret, the whole scheme may be inefficient. Researchers are interested in the (average) ratio between the length of the shares and the secret, the number of different structures is finite for fixed participant size $N$ and it turns out that linear schemes can achieve the best ratios when the number of participants $N\leq 4$ [2]. If $N=5$ , [3] had already handled most structures. Until recently the work is moved further by introducing the converse for linear schemes and constructing the corresponding generator matrices [4]. While the general results in converse or achievability are far from tight as discussed in [5].

The problem of estimating the amount of random bits necessary to set up the schemes has also received attention recently. As the amount of randomness needed by an algorithm is to be treated as a computational resource, analogously to the amount of time and space needed. [6] initiated a quantitative investigation of the number of random bits needed by secrets sharing schemes and found optimal results for some schemes. Some other results relate to this criteria can be found in [7, 8].

There are some situations where more than one secret is to be shared among participants. [9] introduced the missile battery scenario where not all of the missiles have the same launch enable code. Linear threshold multisecret sharing schemes are studied in [7] where the distributed secrets are in one-to-one correspondence with the sets of $k$ -out-of- $N$ participants, i.e., the number of secrets equals $\binom{N}{k}$ and the decoding condition relies on such set of length $k$ . Distributed multi-user secret sharing scheme is also emerged where secret sharing schemes are implied in the distributed storage systems [10, 11].

From one secret to multiple secrets among the same participants, the decodable condition for the latter can be seen as considering multiple secrets individually. While the secure condition varies depending on two criteria: the strong version and the weak version. For example, the strong secure condition asks that any set of participants which is unable to decode secret $S_{1}$ or secret $S_{2}$ has no information on the whole set of these two secrets, however, the weak secure condition says that such set of participants has no information on any single one secret, which means some information about secrets $S_{1}$ and $S_{2}$ like linear combinations may be known.

In [12], the authors show that under the strong secure condition, when the secrets are statistically independent, the best we can do is combining individual ramp schemes independently. [13] has showed that under the weak secure condition, we may gain more efficiency at the cost of security.

In this paper, we focus on the special model implied by [12]. More specifically, we involve threshold scheme such that any set of participant either decodes the secret or learns nothing, while ramp scheme is more general and has gaps. We follow the assumption that all secrets are statistically independent in order to obtain theoretical results that shining the fundamental limits like in [12]. The weak secure condition is focused on, as we care about multiple threshold scheme of any structure, in particular the case that the number of secrets corresponding to the same threshold value $t$ is lager than $t$ , the existing different-threshold-bound in [13] is not enough. Like the (average) ratio and the randomness criteria discussed for single secret sharing scheme, we pursue the infimum of the (average) information ratio and the (average) randomness ratio of any possible structure for multiple threshold scheme and hope that such four ratios will give a basic understanding of this problem.

In this paper, every possible structure is of concern for us. For fixed number of participants, when two access structure arrays have the subset relationship, in the converse part we find that the region formed by the Shannon-type inequalities and system conditions of the simple structure is completely embedded in the region of the complex one; in the achievability part linear schemes of the simple structure can be combined independently to be a multiple threshold scheme for the complex structure. Thus the bridge between different structures is built and guaranteed theoretically.

The case that the number of secrets corresponding to the same threshold value $t$ is lager than $t$ is special and inspires three new bounds in addition to the different-threshold-bound in [13], which are threshold-sum-difference-bound, threshold-product-bound and threshold-sum-bound. Existing linear scheme when under the weak secure condition is based on the Vandermonde matrix as in [14, 15, 13, 16]. Still in this case we propose two novel linear schemes which are modified from the Vandermonde matrix like in [10] to meet the bounds. And we can learn that as the weak secure condition asks the protection of any single one secret, the assumption that the secrets are statistically independent may promote this requirement.

Finally relate these new findings and existing results to the four ratios, we claim optimality in the average information ratio, the average randomness ratio and the randomness ratio. Still new patterns of bounds need to be investigated further as we only get optimal results for the information ratio in three cases.

II problem formulation

II-A system model

A $(t,N,S)$ threshold scheme is a protocol to distribute a secret $S$ among a set of $N$ participants in such a way that any set of participants of cardinality greater than or equal to $t(t\leq N)$ can decode the secret $S$ and any set of participants of cardinality less than or equal to $t-1(t\geq 2)$ has no information on $S$ , we refer these two conditions as the decodable condition and the secure condition.

Such protocol is treated as a special discrete probability distribution with $N+1$ random variables [2]: the secret $S$ and the $i$ -th share $P_{i}$ of the $i$ -th participant for every $i$ in the set $[N]:=\{1,2,\ldots,N\}(N\geq 2)$ . In this way suppose a dealer wants to share the secret $S=s$ among the $N$ participants, he does this by giving the $i$ -th participant the share $P_{i}=p_{i}$ for every $i\in[N]$ according to the conditional probability $\text{Pr}(P_{1}=p_{1},\ldots,P_{N}=p_{N}|S=s)$ , where $\{s,p_{1},\ldots,p_{N}\}$ are chosen from a finite field. The specificity of this discrete probability distribution corresponds to the two requirements of the protocol. More specifically, given any set of shares of cardinality greater than or equal to $t$ , the conditional probability of the secret $S=s$ is equal to 1 or 0, i.e., the conditional entropy of the secret $S$ given $t$ or more shares equals 0; given any set of shares of cardinality less than or equal to $t-1$ , the conditional probability of the secret $S=s$ is equal to $\text{Pr}(S=s)$ , i.e., the conditional entropy of the secret $S$ given $t-1$ or less shares equals the entropy of the secret $S$ , in other words, the secret $S$ and $t-1$ or less shares are statistically independent.

In this paper we consider the case in which we want to share many secrets among a set of $N$ participants, using the threshold schemes. As every single one secret has its corresponding threshold value $t$ determining the decodable and secure conditions, we naturally arrange the threshold values of all secrets in non-increasing order without loss of generality in an array $\mathcal{T}$ , named as the access structure array.

From one secret to multiple secrets among the same $N$ participants, the decodable condition for the latter can be seen as considering multiple secrets individually, e.g., any set of participants of cardinality greater than or equal to the first element of the access structure array can decode all secrets due to the non-increasing order. While the secure condition varies depending on two criteria: the strong version and the weak version. For example, the strong secure condition asks that any set of participants of cardinality strictly less than the last element of the access structure array has no information on the whole set of $|\mathcal{T}|$ secrets, however, the weak secure condition says that such set of participants has no information on any single one secret, which means some information about all $|\mathcal{T}|$ secrets like linear combinations may be known. Still use the technique of discrete probability distribution, we define a multiple threshold scheme as follows.

Definition 1 (Multiple Threshold Scheme)

The structure of a multiple threshold scheme is denoted by the pair $(N,\mathcal{T}=(T_{1},\ldots,T_{K}))$ , where $N$ is the number of participants, $K$ is the number of unique elements in the access structure array $\mathcal{T}$ since there may be some secrets with the same threshold value, and for any $k\in[K]$ , $T_{k}$ is also an array with length $|T_{k}|$ full of $t_{k}$ , the same threshold value of the corresponding set of secrets $\mathcal{S}_{k}:=\{S_{k,1},\ldots,S_{k,|T_{k}|}\}$ . An $(N,\mathcal{T})$ multiple threshold scheme is a discrete probability distribution with $N+|\mathcal{T}|$ random variables of which the $|\mathcal{T}|$ secrets are assumed to be statistically independent, i.e.,

H(\mathcal{S}_{1},\ldots,\mathcal{S}_{K})=\sum_{k\in[K]}\sum_{j\in[|T_{k}|]}H(S_{k,j}).

(1)

Like threshold scheme, the decodable and secure conditions are made in the following. For any $k\in[K]$ ,

1.

The decodable condition: Any set of at least $t_{k}$ participants can decode the set $\{\mathcal{S}_{k},\ldots,\mathcal{S}_{K}\}$ of secrets. Formally, for all $A\subseteq[N]$ with $|A|\geq t_{k}$ , let $P_{A}:=\{P_{i}|i\in A\}$ , it holds that

$H(\mathcal{S}_{k},\ldots,\mathcal{S}_{K}|P_{A})=0.$ (2)
2.

The strong secure condition: Any set of at most $t_{k}-1$ participants has no information on the set $\{\mathcal{S}_{1},\ldots,\mathcal{S}_{k}\}$ of secrets. Formally, for all $A\subseteq[N]$ with $|A|\leq t_{k}-1$ , it holds that

$H(\mathcal{S}_{1},\ldots,\mathcal{S}_{k}|P_{A})=H(\mathcal{S}_{1},\ldots,\mathcal{S}_{k}).$ (3)
3.

The weak secure condition: Any set of at most $t_{k}-1$ participants has no information on any single one secret $S_{i,j}$ , where $i\in[k]$ and $j\in[|T_{i}|]$ . Formally, for all $A\subseteq[N]$ with $|A|\leq t_{k}-1$ , it holds that

$H(S_{i,j}|P_{A})=H(S_{i,j}).$ (4)

Remark 1

Note that these two secure conditions are different and each will be investigated when combined with the same decodable condition and the assumption that all secrets are statistically independent. When the length of the access structure array $\mathcal{T}$ equals $1$ , the assumption of secrets is meaningless, both strong and weak secure condition are the same, that is, the system conditions of multiple threshold scheme degrade to those of threshold scheme.

The efficiency of a threshold scheme is usually measured by the ratio between the length of a share and the secret. Form a set of entropy of every single share, the information ration is defined as the maximum value of this set divided by the entropy of the secret and the average information ratio is defined similarly except that the numerator is replaced by the average value of the same set. As for an $(N,\mathcal{T})$ multiple threshold scheme, the information ration $\sigma$ and the average information ration $\tilde{\sigma}$ are defined similarly as follows:

	$\displaystyle\sigma=\frac{\max_{i\in[N]}H(P_{i})}{\min_{k\in[K],j\in[\|T_{k}\|]}H(S_{k,j})},$		(5)
	$\displaystyle\tilde{\sigma}=\frac{\sum_{i\in[N]}H(P_{i})/N}{\sum_{k\in[K]}\sum_{j\in[\|T_{k}\|]}H(S_{k,j})/\|\mathcal{T}\|}.$		(6)

Note that the major difference for a multiple threshold scheme is that the denominator of the information ratio is replaced by the minimum of the length of every secret as in [7] and the average information ratio considers the average length of all secrets to divide.

For fixed $N$ participants, since a multiple threshold scheme has more random variables than a threshold scheme, the former is more complicated. Then comes the notion of randomness, a fundamental computation resource because truly random bits are hard to obtain. The total randomness present in an $(N,\mathcal{T})$ multiple threshold scheme is the entropy of the whole $N$ shares, i.e., $H(P_{[N]})$ , which takes into account also the randomness $H(\mathcal{S}_{[K]})$ of all secrets as $N$ shares can decode all secrets. In this paper we mainly consider the randomness for the dealer to set up a multiple threshold scheme for secrets $\mathcal{S}_{[K]}$ , that is, the randomness he uses to generate the $N$ shares given the marginal discrete probability distribution of secrets $\mathcal{S}_{[K]}$ . Therefore, we define the randomness ratio $\tau$ as the difference between the length of $N$ shares and that of $|\mathcal{T}|$ secrets, then divided by the minimum of the set formed by the length of every secret. The definition for the average randomness ratio is similar except that the denominator is replaced by the average value of such set. More specifically,

	$\displaystyle\tau=\frac{H(P_{[N]})-H(\mathcal{S}_{[K]})}{\min_{k\in[K],j\in[\|T_{k}\|]}H(S_{k,j})},$		(7)
	$\displaystyle\tilde{\tau}=\frac{H(P_{[N]})-H(\mathcal{S}_{[K]})}{\sum_{k\in[K]}\sum_{j\in[\|T_{k}\|]}H(S_{k,j})/\|\mathcal{T}\|}.$		(8)

As all secrets are statistically independent by the assumption, the randomness of all secrets can be replaced by the sum of entropy of every single secret as in equation (1).

The problem that we investigate in this paper is to optimize the (average) information ratio and the (average) randomness ratio of multiple threshold schemes. Given the number of participants $N$ and the access structure array $\mathcal{T}$ , we define $(\tilde{\sigma}_{N,\mathcal{T}})\sigma_{N,\mathcal{T}}$ as the infimum of the (average) information ration of all $(N,\mathcal{T})$ multiple threshold schemes, moreover, $\tilde{\tau}_{N,\mathcal{T}}$ and $\tau_{N,\mathcal{T}}$ are defined similarly. For all possible choices of the structure $(N,\mathcal{T})$ , we are interested in determining the above four values via their lower bounds and upper bounds.

II-B lower bound

Note that for any probability distribution with $N+|\mathcal{T}|$ discrete random variables, we can extract its $2^{N+|\mathcal{T}|}-1$ entropies and arrange them into a vector $\mathbf{h}$ . Any such vector $\mathbf{h}$ satisfies the so-called Shannon-type inequalities [17]. More specifically, let $\mathcal{H}_{N+|\mathcal{T}|}$ be a $(2^{N+|\mathcal{T}|}-1)$ -dimension Euclidean space whose coordinates are labeled by $h_{a}$ , $\emptyset\neq a\subseteq\mathcal{O}$ , where $\mathcal{O}$ is the set of $N+|\mathcal{T}|$ random variables $\{P_{i}:i\in[N]\}\cup\{S_{j}:j\in[|\mathcal{T}|]\}$ and we use another notation for the secrets. Then let $\Gamma_{N+|\mathcal{T}|}$ be a polyhedral cone represented by the intersection of two categories of closed half-spaces, which are derived from the Shannon-type inequalities:

1.

Non-decreasing: If $a\subseteq b\subseteq\mathcal{O}$ , then $h_{a}\leq h_{b}$ ,
2.

Submodular: $\forall a,b\subseteq\mathcal{O},h_{a\cup b}+h_{a\cap b}\leq h_{a}+h_{b}$ ,

where $h_{\emptyset}$ is taken to be 0. Note that for every discrete probability distribution and the corresponding vector $\mathbf{h}$ , we have (conditional) entropy and (conditional) mutual information greater than and equal to 0, which correspond to being non-decreasing and submodular respectively, then $\mathbf{h}\in\Gamma_{N+|\mathcal{T}|}$ .

As the independent assumption for secrets (1), the decodable condition (2), the strong secure condition (3) and the weak secure condition (4) can all be handled as homogeneous linear equations involving the coordinates from $\mathcal{H}_{N+|\mathcal{T}|}$ only, for fixed structure $(N,\mathcal{T})$ of any multiple threshold scheme, we add four intersections of hyperplane(s) as follows. Let $[k:K]:=\{k,\ldots,K\}$ , for every $k\in[K]$ and $A\subseteq[N]$ ,

$\displaystyle\mathcal{C}_{0}=$	$\displaystyle\{\mathbf{h}\in\mathcal{H}_{N+\|\mathcal{T}\|}:h_{\mathcal{S}_{[K]}}-\sum_{i\in[K]}\sum_{j\in\|T_{i}\|}h_{S_{i,j}}=0\},$	(9)
$\displaystyle\mathcal{C}_{1}=$	$\displaystyle\{\mathbf{h}\in\mathcal{H}_{N+\|\mathcal{T}\|}:h_{\mathcal{S}_{[k:K]},P_{A}}-h_{P_{A}}=0,\|A\|\geq t_{k}\},$	(10)
$\displaystyle\mathcal{C}_{2}=$	$\displaystyle\{\mathbf{h}\in\mathcal{H}_{N+\|\mathcal{T}\|}:h_{\mathcal{S}_{[k]},P_{A}}-h_{P_{A}}-h_{\mathcal{S}_{[k]}}=0,\|A\|\leq t_{k}-1\},$	(11)
$\displaystyle\mathcal{C}_{3}=$	$\displaystyle\{\mathbf{h}\in\mathcal{H}_{N+\|\mathcal{T}\|}:h_{S_{i,j},P_{A}}-h_{P_{A}}-h_{S_{i,j}}=0,\|A\|\leq t_{k}-1,i\in[k],j\in[\|T_{i}\|]\}.$	(12)

In this way, consider a vector $\mathbf{h}\in\mathcal{H}_{N+|\mathcal{T}|}$ whose components are the $2^{N+|\mathcal{T}|}-1$ entropies obtained from an $(N,\mathcal{T})$ multiple threshold scheme under weak secure condition (4), we have $\mathbf{h}\in\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,3}$ , here we denote $\mathcal{C}_{0}\cap\mathcal{C}_{1}\cap\mathcal{C}_{3}$ by $\mathcal{C}_{0,1,3}$ for ease of notation. And when replace weak secure condition by strong one, it follows that the corresponding vector belongs to $\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,2}$ .

For a fixed structure $(N,\mathcal{T})$ , recall the definitions of the four ratios above, besides their connections with any discrete probability distributions meeting some system conditions, there are also some quantities of interest, i.e., the set of $N+|\mathcal{T}|$ entropies of every share and secret $\{H(P_{i}):i\in[N]\}\cup\{H(S_{j}):j\in[|\mathcal{T}|]\}$ for the (average) information ratio and the set of $1+|\mathcal{T}|$ entropies of $N$ shares and every secret $\{H(P_{[N]})\}\cup\{H(S_{j}):j\in[|\mathcal{T}|]\}$ for the (average) randomness ratio. As for the polyhedral cone $\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3}$ under (strong) weak secure condition, of which we care about the sets of the corresponding coordinates likewise, i.e., $\mathbf{h}_{I}:=\{h_{P_{i}}:i\in[N]\}\cup\{h_{S_{j}}:j\in[|\mathcal{T}|]\}$ for the (average) information ratio and $\mathbf{h}_{R}:=\{h_{P_{[N]}}\}\cup\{h_{S_{j}}:j\in[|\mathcal{T}|]\}$ for the (average) randomness ratio. In this way, the region involving these coordinates is enough to derive the lower bounds for the four ratios. To gain a more exact characterization, a suitable concept is illustrated as follows: A projection [18] of a region $\mathcal{P}$ in $\mathbb{R}^{n}=\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}$ onto its subspace of the first $n_{1}$ coordinates is

\textrm{proj}_{[n_{1}]}(\mathcal{P})=\{\mathbf{x}_{1}\in\mathbb{R}^{n_{1}}:\exists\mathbf{x}_{2},(\mathbf{x}_{1}^{T},\mathbf{x}_{2}^{T})^{T}\in\mathcal{P}\}.

(13)

Then $\text{proj}_{\mathbf{h}_{I}}(\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3})$ and $\text{proj}_{\mathbf{h}_{R}}(\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3})$ are essential for the (average) information ratio and (average) randomness ratio respectively.

Recall that every possible structure $(N,\mathcal{T})$ is of concern for us. For fixed number $N$ of participants, two different access structure arrays $\mathcal{T}^{\prime}=(T_{1}^{\prime},\ldots,T_{K^{\prime}}^{\prime})$ and $\mathcal{T}=(T_{1},\ldots,T_{K})$ may have a relationship similar to the subset concept from set theory, thus we give the following definition with some abuse of notation:

Definition 2 (Subset of Arrays)

$\mathcal{T}^{\prime}\subseteq\mathcal{T}$ if and only if for every $i\in[K^{\prime}]$ , there exists $j\in[K]$ such that $t_{i}^{\prime}=t_{j}$ and $|T_{i}^{\prime}|\leq|T_{j}|$ , where $t_{i}^{\prime}$ is the same threshold value of the sub-array $T_{i}^{\prime}$ .

When $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ and for the same number $N$ of participants, in the polyhedral cone formed by the Shannon-type inequalities, there exist some interesting geometrical properties between two regions $\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3}$ and $\Gamma_{N+|\mathcal{T}^{\prime}|}\cap\mathcal{C}_{0,1,(2)3}^{\prime}$ , where $\mathcal{C}_{.}^{\prime}$ is the intersection of hyperplanes defined from the structure $(N,\mathcal{T}^{\prime})$ . For the ease of notation we reuse coordinates of $\Gamma_{N+|\mathcal{T}^{\prime}|}\cap\mathcal{C}_{0,1,(2)3}^{\prime}$ from $\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3}$ and rearrange the elements of these two access structure arrays such that for every $i\in[|\mathcal{T}^{\prime}|]$ , the two corresponding secrets from $\mathcal{T}^{\prime}$ and $\mathcal{T}$ respectively have the same threshold value, here the non-increasing order of both access structure arrays may be broken due to such forcible arrangement. Denote all coordinates of the former region by $\mathbf{h}_{L}$ and we give the following theorem:

Theorem 1

When the number of participants $N$ is fixed and two access structure arrays have the subset relationship, i.e., $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ , the polyhedral cone formed by the Shannon-type inequalities and system conditions of the structure $(N,\mathcal{T}^{\prime})$ is exactly equal to the projection of the corresponding polyhedral cone of the structure $(N,\mathcal{T})$ , i.e., $\Gamma_{N+|\mathcal{T}^{\prime}|}\cap\mathcal{C}_{0,1,(2)3}^{\prime}=\text{proj}_{\mathbf{h}_{L}}(\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3})$ .

Proof:

The proof is conducted in two directions, i.e., any point of the former is in the later, and vice versa. The detail is put in Appendix A-A. ∎

Remark 2

This theorem offers a theoretical guarantee that some important bounds of the bigger region, after a projection algorithm like Fourier-Motzkin-Elimination, are still feasible and even fundamental for the smaller region. A direct example is the following corollary.

Corollary 1

When the number of participants $N$ is fixed and two access structure arrays have the subset relationship, i.e., $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ , a feasible bound for the polyhedral cone formed by the Shannon-type inequalities and system conditions of the structure $(N,\mathcal{T})$ can be truncated to be a feasible bound of the corresponding polyhedral cone of the structure $(N,\mathcal{T}^{\prime})$ . More specifically, for any vector $\mathbf{h}\in\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3}$ , if there exists a feasible bound such that $\alpha_{0}h_{P_{[N]}}+\sum_{i\in[N]}\alpha_{i}h_{P_{i}}\geq\sum_{j\in[|\mathcal{T}|]}\beta_{j}h_{S_{j}}$ , where every coefficient $\beta_{j}$ is non-negative, then for any vector $\mathbf{h}^{\prime}\in\Gamma_{N+|\mathcal{T}^{\prime}|}\cap\mathcal{C}_{0,1,(2)3}^{\prime}$ , $\alpha_{0}h_{P_{[N]}}^{\prime}+\sum_{i\in[N]}\alpha_{i}h_{P_{i}}^{\prime}\geq\sum_{j\in[|\mathcal{T}^{\prime}|]}\beta_{j}h_{S_{j}}^{\prime}$ .

Proof:

For any $i\in[|\mathcal{T}|]$ , consider a submodular inequality $h_{S_{i}}+h_{P_{1}}-h_{S_{i},P_{1}}\geq 0$ and a non-decreasing one $-h_{P_{1}}+h_{S_{i},p_{1}}\geq 0$ , plus these two together, we get $h_{S_{i}}\geq 0$ . Then $\alpha_{0}h_{P_{[N]}}+\sum_{i\in[N]}\alpha_{i}h_{P_{i}}\geq\sum_{j\in[|\mathcal{T}^{\prime}|]}\beta_{j}h_{S_{j}}$ is also a feasible bound. Based on the equation result of theorem 1, such bound is also feasible for the vectors of the region $\Gamma_{N+|\mathcal{T}^{\prime}|}\cap\mathcal{C}_{0,1,(2)3}^{\prime}$ . ∎

Remark 3

For an access structure array with continuous unique threshold values, the proofs of some bounds may be more read-friendly. And by this corollary, the bound for a non-continuous access structure array $\mathcal{T}^{\prime}$ can be obtained by the truncation from the bound of a continuous access structure array $\mathcal{T}\supseteq\mathcal{T}^{\prime}$ , and it turns out that some bounds obtained in this way are enough for the four ratios.

II-C linear scheme

Before introducing the so-called linear scheme [15], some concepts need to be illustrated. Let $\mathcal{V}$ be a vector space with finite dimension $n$ over a finite field $\mathbb{F}_{q}$ , where $q$ is a prime number. Recall that $\mathcal{O}$ is the set of $N+|\mathcal{T}|$ random variables essential to an $(N,\mathcal{T})$ multiple threshold scheme. For every $i\in\mathcal{O}$ , denote a subset of $\mathcal{V}$ by ${V}_{i}$ , we assume that all vectors of ${V}_{i}$ are linear independent, then the length of such subset is $\text{rk}(V_{i})$ , here $\text{rk}(.)$ calculates the rank of its input. Hereafter, we treat each ${V}_{i}$ as a matrix of shape $n\times\text{rk}(V_{i})$ and stack such $|\mathcal{O}|$ matrices in sequence horizontally (column wise) into a bigger matrix $\mathbf{G}\in\mathbb{F}_{q}^{n\times\sum_{i\in\mathcal{O}}\text{rk}({V}_{i})}$ , referred as a generator matrix.

Then consider a uniform discrete probability distribution whose alphabet is the set of $q^{n}$ different row vectors with length $n$ taking values from $\mathbb{F}_{q}$ . These vectors can be stacked vertically into a matrix $\mathbf{C}\in\mathbb{F}_{q}^{q^{n}\times n}$ . For $\mathbf{CG}\in\mathbb{F}_{q}^{q^{n}\times\sum_{i\in\mathcal{O}}\text{rk}({V}_{i})}$ , with the set of row vectors as the alphabet and that the probability of each equals $1/q^{n}$ , it forms a new discrete probability distribution with random variables from the set $\mathcal{O}$ , where $\forall\emptyset\neq x\subseteq\mathcal{O},H(x)=\text{rk}({V}_{x}):=\text{rk}(\cup_{i\in x}{V}_{i})$ , with the base of the logarithm being $q$ and ${V}_{x}$ denotes a matrix stacked horizontally by the corresponding $|x|$ matrices. Note that if $\text{rk}({V}_{\mathcal{O}})<n$ , then some row vectors of $\mathbf{CG}$ are the same and the corresponding probabilities need to be summed; otherwise, all are unique.

Recall that $K$ is the number of unique elements in the access structure array $\mathcal{T}$ and for any $k\in[K]$ , $T_{k}$ is also an array with length $|T_{k}|$ full of $t_{k}$ , the same threshold value of the corresponding set of secrets $\mathcal{S}_{k}=\{S_{k,1},\ldots,S_{k,|T_{k}|}\}$ . Based on the relationship between discrete probability distribution and generator matrix, consider the latter as a linear scheme, then we give the following definition of linear multiple threshold scheme:

Definition 3 (Linear Multiple Threshold Scheme)

A linear $(N,\mathcal{T})$ multiple threshold scheme is a special generator matrix satisfying the following system conditions:

1.

All secrets are statistically independent: $\text{rk}(V_{\mathcal{S}_{[K]}})=\sum_{k\in[K]}\sum_{j\in[|T_{k}|]}\text{rk}(V_{S_{k,j}})$ .
2.

The decodable condition: For every $k\in[K]$ and all $A\subseteq[N]$ with $|A|\geq t_{k}$ , $\text{rk}(V_{\mathcal{S}_{[k:K]},P_{A}})=\text{rk}(V_{P_{A}})$ .
3.

The strong secure condition: For every $k\in[K]$ and all $A\subseteq[N]$ with $|A|\leq t_{k}-1$ , $\text{rk}(V_{\mathcal{S}_{[k]},P_{A}})=\text{rk}(V_{\mathcal{S}_{[k]}})+\text{rk}(V_{P_{A}})$ .
4.

The weak secure condition: For every $k\in[K]$ and all $A\subseteq[N]$ with $|A|\leq t_{k}-1$ , $\text{rk}(V_{{S}_{i,j},P_{A}})=\text{rk}(V_{{S}_{i,j}})+\text{rk}(V_{P_{A}})$ , where $i\in[k]$ and $j\in[|T_{i}|]$ .

Note that these four conditions are rewritten from (1), (2), (3) and (4) in section II-A, still only one of the two secure conditions is chosen for a corresponding model and for simplicity we do not mention which secure condition is implied in this subsection.

Remark 4

From the view of a linear $(N,\mathcal{T})$ multiple threshold scheme, both the generation of $N$ shares and the decoding of secrets can be treated as linear mappings, which are more neat than the general ones. As every codeword corresponds to $|\mathcal{T}|$ secret values and a distribution of shares, furthermore, the whole probability distribution is uniform, then the length of every share is exactly the number of symbols given to the corresponding participant from the dealer. The decodable condition tells that every vector $\mathbf{a}$ in $V_{\mathcal{S}_{[k:K]}}$ can be written as a linear combination of vectors in $V_{P_{A}}$ , which means that any $t_{k}$ or more shares determine the secrets $\mathcal{S}_{[k:K]}$ linearly. As for the (strong) weak secure condition, all elements of the union of $V_{(\mathcal{S}_{[k]})S_{i,j}}$ and $V_{P_{A}}$ are linear independent, which implies that the random variables $(\mathcal{S}_{[k]})S_{i,j}$ and $P_{A}$ constructed are statistically independent. The independent assumption for all secrets follows similarly.

In this paper we only use linear multiple threshold schemes for achievability. Then the entropy part from all four ratios can be replaced by the the rank part. For a fixed structure $(N,\mathcal{T})$ , if we can construct a corresponding linear multiple threshold scheme, i.e., a generator matrix satisfying the system conditions, we have upper bounds of the four ratios. When upper bound and lower bound match, the optimum can be claimed.

As we care about every possible structure $(N,\mathcal{T})$ , recall that for fixed number of participants $N$ , two different access structure arrays $\mathcal{T}^{\prime}=(T_{1}^{\prime},\ldots,T_{K^{\prime}}^{\prime})$ and $\mathcal{T}=(T_{1},\ldots,T_{K})$ may have a subset relationship similar to two sets according to definition 2. Still for the ease of notation, we rearrange the elements of these two access structure arrays such that for every $i\in[|\mathcal{T}^{\prime}|]$ , the two corresponding secrets from $\mathcal{T}^{\prime}$ and $\mathcal{T}$ respectively have the same threshold value, finally we claim that

Theorem 2

When the number of participants $N$ is fixed and two access structure arrays have the subset relationship, i.e., $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ , any generator matrix $V$ for the structure $(N,\mathcal{T}^{\prime})$ is also a linear $(N,\mathcal{T})$ multiple threshold scheme which reuses the random variable of the former and $\text{rk}(V_{S_{i}})=0,\forall i\in[|\mathcal{T}^{\prime}|+1,|\mathcal{T}|]$ .

Proof:

The proof is carried by checking the system conditions of the definition of linear multiple threshold scheme. The detail can be found in Appendix A-B. ∎

Remark 5

The construction of a linear multiple threshold scheme may be easier when there are not too many secrets to share, i.e., the length of the access structure array is small. In this way, this theorem offers a degradation method to construct a more complicated scheme. As will be discussed below, it turns out to be a building block from simple schemes to a complex one.

Different generator matrices can be combined independently, i.e., in the diagonal, to form a bigger generator matrix of which every rank term equals the sum of those from the original generator matrices. The detail is in the following:

Definition 4 (Independent Combination of Generator Matrices)

For the same set of random variables $\mathcal{O}$ , assume over the same finite field there are $A$ existing generator matrices, each is denoted by $V^{i},\ i\in[A]$ and the corresponding shape is $\text{rk}(V_{\mathcal{O}}^{i})\times\sum_{j\in\mathcal{O}}\text{rk}(V_{j}^{i})$ . The independent combination of these $A$ generator matrices is a bigger generator matrix $V$ , where for any $j\in\mathcal{O}$ the sub-matrix $V_{j}$ is a diagonal arrangement of the corresponding $A$ sub-matrices from the original generator matrices. More specifically, let the shape of the sub-matrix $V_{j}$ be $\sum_{i\in[A]}\text{rk}(V_{\mathcal{O}}^{i})\times\sum_{i\in[A]}\text{rk}(V_{j}^{i})$ and fill $V_{j}$ with zeroes, then for every $i\in[A]$ in turn put $V_{j}^{i}$ in the diagonal of $V_{j}$ .

Note that the we can do Gaussian-Elimination towards the rows of a generator matrix and the corresponding $2^{|\mathcal{O}|}-1$ rank terms do not change, in this way we fix the number of rows of a generator matrix to be the rank of the whole matrix. When there exist an all-zero $V_{j}^{i}$ , we do nothing for the sub-matrix $V_{j}$ of the final bigger generator matrix when it is the turn of the sub-matrix $V_{j}^{i}$ from original generator matrices in the diagonal arrangement.

Remark 6

By the diagonal arrangement and based on the same finite field, it follows that for any non-empty set $B\subseteq\mathcal{O}$

\text{rk}(V_{B})=\sum_{i\in[A]}\text{rk}(V_{B}^{i}).

(14)

The rigorous proof can follow the direct implementation of Gaussian-Elimination horizontally (column wise) and is omitted here.

Via the claim that a simple linear multiple threshold scheme can be treated as a complex one with somewhat of degradation in theorem 2, and using the construction method that independently combing existing linear multiple threshold schemes as in definition 4, we give the following corollary.

Corollary 2

When the number of participants $N$ is fixed and $A+1$ access structure arrays have the subset relationship, i.e., $\mathcal{T}^{i}\subseteq\mathcal{T},\ i\in[A]$ . Assume over the same finite field there are $A$ existing generator matrices, each is denoted by $V^{i}$ and for the structure $(N,\mathcal{T}^{i})$ . Then the independent combination of these $A$ generator matrices is a linear $(N,\mathcal{T})$ multiple threshold scheme.

Proof:

From theorem 2, for any $i\in[A]$ , a linear scheme for the structure $(N,\mathcal{T}^{i})$ is also a linear $(N,\mathcal{T})$ multiple threshold scheme when $\mathcal{T}^{i}\subseteq\mathcal{T}$ . Recall the system conditions of a linear multiple threshold scheme in definition 3, each of them is some equations involving the rank terms only. As the independent combination results in the sum of rank terms as in (14), the conclusion follows. ∎

Remark 7

From one secret to multiple ones, a trivial idea to accomplish the construction of an $(N,\mathcal{T})$ multiple threshold scheme is combining $|\mathcal{T}|$ threshold schemes independently. As for liner schemes, this corollary applies the notion of independence and builds a bridge from some simple schemes to a complex one. It turns out that some linear schemes obtained in this way are enough for the four ratios.

III (Average) information ratio

We firstly discuss multiple threshold schemes with the strong secure condition, of which some results can be modified for the weak one.

III-A strong secure

III-A1 converse

We firstly discuss some converse results that are fundamental for lower bounds of the (average) information ratio.

Lemma 1 (Size of A Secret)

For any $(t,N,S)$ threshold scheme, if $t<N$ , then

H(S)\leq I(P_{i_{1}};P_{i_{2}}|P_{i_{3}},\ldots,P_{i_{t+1}}),

where $(i_{1},\ldots,i_{t+1})$ are $t+1$ different values chosen from the set $[N]$ .

Proof:

To improve readability, we replace the index $t_{i}$ by $i$ , the final result can be transformed back later. Hereafter, we use this trick in the following whole paper.

	$\displaystyle H(S)=$	$\displaystyle H(S\|P_{3},\ldots,P_{t+1})-H(S\|P_{1},P_{3},\ldots,P_{t+1})$
		$\displaystyle-H(S\|P_{2},P_{3},\ldots,P_{t+1})+H(S\|P_{1},\ldots,P_{t+1})$
	$\displaystyle=$	$\displaystyle I(S;P_{1}\|P_{3},\ldots,P_{t+1})-I(S;P_{1}\|P_{2},P_{3},\ldots,P_{t+1})$
	$\displaystyle=$	$\displaystyle H(P_{1}\|P_{3},\ldots,P_{t+1})-H(P_{1}\|S,P_{3},\ldots,P_{t+1})$
		$\displaystyle-H(P_{1}\|P_{2},P_{3},\ldots,P_{t+1})+H(P_{1}\|S,P_{2},P_{3},\ldots,P_{t+1})$
	$\displaystyle=$	$\displaystyle I(P_{1};P_{2}\|P_{3},\ldots,P_{t+1})-I(P_{1};P_{2}\|S,P_{3},\ldots,P_{t+1})$
	$\displaystyle\leq$	$\displaystyle I(P_{1};P_{2}\|P_{3},\ldots,P_{t+1})$

Note that the first equation is nothing but the decodable and secure conditions of a $(t,N,S)$ threshold scheme, the other equations are from the definitions of (conditional) entropy and (conditional) mutual information, and the last inequality uses the submodular property. ∎

Remark 8

Existing result shows that the length of a share must be bigger than or equal to the length of a secret [5], for example, if $t=N$ , $H(S)=H(S|P_{i_{2}},\ldots,P_{i_{t}})-H(S|P_{i_{1}},\ldots,P_{i_{t}})=I(S;P_{i_{1}}|P_{i_{2}},\ldots,P_{i_{t}})\leq H(P_{i_{1}}|P_{i_{2}},\ldots,P_{i_{t}})\leq H(P_{i_{1}})$ . While this lemma tells that the length of a secret is not larger than the mutual information between any two shares given any other $t-1$ shares. In this sense, this bound is tighter and will be a building block for other interesting bounds of this paper.

From one secret to multiple ones, when under the strong secure condition, the following bound is enough for the investigation of the (average) information ratio and even the heterogeneous-secret-size problem as in [12].

Lemma 2

For any $(N,\mathcal{T})$ multiple threshold scheme with the strong secure condition, it holds that $\sum_{k\in[K]}\sum_{j\in[|T_{k}|]}H(S_{k,j})\leq H(P_{i})$ , $\forall i\in[N]$ .

Proof:

The proof is based on the mutual information bound as in lemma 1. The detail is in Appendix B-A. ∎

Remark 9

This bound says that when under the strong secure condition, the sum of the length of every secret is no bigger than the length of any single share. This is implied by the work from [12], while our proof may be more read-friendly due to the building block in lemma 1. Then consider the (average) information ratio, for any $(N,\mathcal{T})$ multiple threshold scheme, we apply this bound and it turns out that $\sigma_{N,\mathcal{T}}\geq|\mathcal{T}|$ and $\tilde{\sigma}_{N,\mathcal{T}}\geq|\mathcal{T}|$ , i.e., lower bounds are formed.

III-A2 achievability

Then we discuss some linear schemes that are crucial for upper bounds of the (average) information ratio.

Still we want to link the known results of a single secret to multiple ones. For a linear $(t,N,S)$ threshold scheme, its generator matrix is closely related to the Vandermonde matrix over a finite field. More specifically, let $V(t,[N+1])$ fully denote the following matrix from $\mathbb{F}_{q}^{t\times(N+1)}$ , where $q$ is a prime number larger than $N+1$ . In this notation, $t$ and $[N+1]$ means the number of rows of the matrix and the elements of the second row in increasing order respectively.

Definition 5 (The Transpose of A Vandermonde Matrix)

V(t,[N+1]):=\begin{bmatrix}1&1&1&\cdots&1\\ 1&2&3&\cdots&N+1\\ 1&2^{2}&3^{2}&\cdots&(N+1)^{2}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&2^{t-1}&3^{t-1}&\cdots&(N+1)^{t-1}\end{bmatrix},

(15)

here we let the first column be the sub-matrix $V_{S}$ , the second column correspond to the first share $P_{1}$ and so on. Due to the determinant of a Vandermonde matrix, any $t$ columns corresponding to any $t$ shares are full rank, so are any $t-1$ columns corresponding to any $t-1$ shares combined with the first column corresponding to the secret $S$ , then $V(t,[N+1])$ is a linear $(t,N,S)$ threshold scheme.

Recall that from one secret to multiple ones, we can imply the independent combination of $|\mathcal{T}|$ linear threshold schemes to get a linear $(N,\mathcal{T})$ multiple threshold scheme according to corollary 2. More specifically, given any structure $(N,\mathcal{T})$ , we prepare a linear $(t_{k},N,S_{k,j})$ threshold scheme based on $V(t_{k},[N+1])$ for any $k\in[K],j\in[|T_{k}|]$ , each of them is also a degradation version of linear $(N,\mathcal{T})$ multiple threshold scheme with the strong secure condition. The independent combination of these $|\mathcal{T}|$ generator matrices leads to a linear $(N,\mathcal{T})$ multiple threshold scheme with the strong secure condition such that $H(S_{k,j})=1,\forall k\in[K],j\in[|T_{k}|]$ and $H(P_{i})=|\mathcal{T}|,\forall i\in[N]$ . And the order of the underlying finite field is still larger than $N+1$ . Then we have $\sigma_{N,\mathcal{T}}\leq|\mathcal{T}|$ and $\tilde{\sigma}_{N,\mathcal{T}}\leq|\mathcal{T}|$ . Finally the optimum can be claimed.

Theorem 3

The infimum of the (average) information ratio equals the number of the secrets, i.e., $(\tilde{\sigma}_{N,\mathcal{T}})\sigma_{N,\mathcal{T}}=|\mathcal{T}|$ , when under the strong secure condition.

Proof:

The proof follows from the above illustrations. ∎

Remark 10

The novelty of this theorem compared to the known results of [12] is embedding the two criteria, i.e., the average information ratio and information ratio. Both criteria show that the more secrets, the less efficiency.

III-B weak secure

III-B1 converse

We firstly discuss some converse results that are fundamental for lower bounds of the (average) information ratio when under the weak secure condition.

Lemma 3 (Different-Threshold-Bound)

For any $(N,\mathcal{T})$ multiple threshold scheme with the weak secure condition, for any share index $i\in[N]$ and secret index $j_{k}\in[|T_{k}|]$ of the sub-array $T_{k}$ , it holds that

\displaystyle\sum_{k\in[K]}H(S_{k,j_{k}})\leq H(P_{i}).

(16)

Proof:

Recall that the difference between the strong secure condition (3) and the weak one (3) is the knowledge of secrets. More specifically, substitute the secrets $H(\mathcal{S}_{k}^{\prime})$ of the bound in the proof of lemma 2 by a single secret $H(S_{k,j_{k}})$ , the result follows. ∎

Remark 11

Recall that the access structure array $\mathcal{T}$ can be divided into $K$ different sub-arrays based on $K$ unique threshold values. In this way different-threshold-bound says that the sum of the length of different kinds of secrets is no bigger than the length of any secret, which is a weak version of lemma 2 due to the weak secure condition. This bound is already known as a special case of the result from [13]. We find that it is crucial for the (average) information ratio. More specifically, for any structure $(N,\mathcal{T})$ , the infimum of the information ratio $\sigma_{N,\mathcal{T}}\geq K$ .

As mentioned before, we care about every possible structure $(N,\mathcal{T})$ , and it leads to a discovery of two new bounds. Recall that the access structure array $\mathcal{T}$ consists of $K$ sub-arrays, for any $i\in[K]$ each array $T_{i}$ is full of the same threshold value $t_{i}$ .

Lemma 4 (Threshold-Sum-Difference-Bound)

For any $(N,\mathcal{T})$ multiple threshold scheme with the weak secure condition, fix an index $k\in[K]$ , similar to lemma 3 let index $j_{i}$ be any element of the set $[|T_{i}|]$ , also let $(i_{1},\ldots,i_{t_{k}})$ be $t_{k}$ different values chosen from the set $[N]$ like lemma 1, then

t_{k}\sum_{i\in[k-1]}H(S_{i,j_{i}})+\sum_{i\in[k:K]}\sum_{j\in[|T_{i}|]}H(S_{i,j})+\sum_{i\in[k+1:K]}(t_{k}-t_{i})H(S_{i,j_{i}})\leq\sum_{j\in[t_{k}]}H(P_{i_{j}}).

(17)

Proof:

The proof can be divided into three parts, each results in a special bound. The detail is in Appendix B-B. ∎

Remark 12

This bound is novel and is important for the (average) information ratio. More specifically, for any structure $(N,\mathcal{T})$ , the infimum of the information ratio $\sigma_{N,\mathcal{T}}\geq\max_{k\in[K]}(K-1+|T_{k}|/t_{k}+(\sum_{i\in[k+1:K]}|T_{i}|-t_{i})/t_{k})$ .

Lemma 5 (Threshold-Product-Bound)

For any $(N,\mathcal{T})$ multiple threshold scheme with the weak secure condition, similar to lemma 1 let $(i_{1},\ldots,i_{t_{1}})$ be $t_{1}$ different values chosen from the set $[N]$ , then

\sum_{i\in[K]}\frac{\prod_{k\in[K]}t_{k}}{t_{i}}\sum_{j\in[|T_{i}|]}H(S_{i,j})\leq\prod_{k\in[2:K]}t_{k}\sum_{j\in[t_{1}]}H(P_{i_{j}}).

(18)

Proof:

The proof uses induction, where two pattern inequalities are summed at every turn. The detail is in Appendix B-C. ∎

Remark 13

This bound is novel and is used for the information ratio only. More specifically, for any structure $(N,\mathcal{T})$ , the infimum of the information ratio $\sigma_{N,\mathcal{T}}\geq\sum_{i\in[K]}|T_{i}|/t_{i}$ .

We give a lower bound for the average information ratio using different-threshold-bound and threshold-sum-difference-bound only. Recall that the access structure array $\mathcal{T}$ consists of $K$ sub-arrays, for any $i\in[K]$ each array $T_{i}$ of them is full of the same threshold value $t_{i}$ .

Lemma 6

For any $(N,\mathcal{T})$ multiple threshold scheme under the weak secure condition, the average information ratio is closely related to the a unique threshold value of the access structure array $\mathcal{T}$ and the number of secrets corresponding to it. More specifically, infimum of the average information ratio

\displaystyle\tilde{\sigma}_{N,\mathcal{T}}\geq\frac{|\mathcal{T}|}{\max_{i\in[K]}(\min(t_{i},|T_{i}|))}.

(19)

Proof:

The proof uses different-threshold-bound (16) and threshold-sum-difference-bound (17). The detail is in Appendix B-D. ∎

Remark 14

We will show in the achievability part that this lower bound is tight, which means a specific sub-array $T_{i}$ of the access structure array $\mathcal{T}$ plays a central role for the average information ratio and for a fixed threshold value $t_{i}$ , a suitable number $|T_{i}|$ of secrets improves this performance criteria.

As for the information ratio, the above three bounds may not be enough to obtain the optimum results, i.e., efforts in investigating more bounds are needed. For example, consider the structure $(N=3,\mathcal{T}=(3,3,3,3,2,2,2))$ , a new bound is that

\displaystyle H(S_{1,1})+\sum_{j\in[4]}H(S_{1,j})+2\sum_{j\in[3]}H(S_{2,j})\leq\sum_{i\in[3]}H(P_{i})+H(P_{3}).

(20)

Proof:

Still rewrite the bound (35), we have

2H(P_{[3]})+H(\mathcal{S}_{2})\leq\sum_{i\in[3]}H(P_{[3]/\{i\}}).

Consider that $H(P_{[3]})=H(\mathcal{S}_{[2]},P_{[3]})\geq H(\mathcal{S}_{[2]})$ and $H(P_{[3]})=H(\mathcal{S}_{[2]},P_{[3]})\geq H({S}_{1,1},P_{[2]})=H({S}_{1,1})+H(P_{[2]})$ , the result follows. ∎

Remark 15

However, we do not know how to generalize this kind of bound as we care about all possible structure $(N,\mathcal{T})$ and whether this new bound plays an important role for the information ratio is unclear. In this way, the infimum of the information ratio is claimed for some special cases only as will be discussed in the achievability part.

III-B2 achievability

Then we discuss some linear schemes that are crucial for upper bounds of the (average) information ratio and even the (average) randomness ratio.

Let $t$ and $a$ be two positive integers, recall that $V(t,[a])$ is a transpose of a Vandermonde matrix from $\mathbb{F}_{q}^{t\times a}$ , where $q$ is a prime number larger than $a$ , $t$ means the number of rows and $[a]$ is exactly the set of elements of the second row. When under the weak secure condition, we give the following building block for linear multiple threshold schemes:

Lemma 7

For an $(N,\mathcal{T})$ multiple threshold scheme whose access structure array consists of only one unique threshold value, i.e., $|\mathcal{T}|=|T_{1}|$ . Let $n=\min(t_{1},|T_{1}|)$ , then $V(t_{1},n+N)$ is a linear $(N,\mathcal{T})$ multiple threshold scheme under the weak secure condition where each column corresponds to a random variable, e.g., the first column is $S_{1,1}$ , the $n-th$ one is $S_{1,n}$ , the $(n+1)-th$ one is $P_{1}$ and so on.

Note that in this way we have $H(S_{1,i})=H(P_{j})=1,\forall i\in[n],j\in[N]$ and $H(S_{1,i})=0,\forall i\in[n+1:|\mathcal{T}|]$ when the number of secrets is bigger than the threshold value.

Proof:

In $V(t_{1},n+N)$ , any $t_{1}$ columns are full rank. As $n\leq t_{1}$ , $n$ secrets are statistically independent. The decodable condition follows as the threshold value $t_{1}$ equals the number of rows. Since $t_{1}-1+1=t_{1}$ , the weak secure condition is guaranteed. When $|\mathcal{T}|>t_{1}$ , the generator matrix $V(t_{1},t_{1}+N)$ is actually a linear $(N,\mathcal{T}^{\prime})$ multiple threshold scheme where $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ , from theorem 2 the result follows. ∎

Remark 16

Such construction of multiple threshold scheme when under the weak secure condition is already known [15, 13].

Recall that the access structure array $\mathcal{T}$ consists of $K$ sub-arrays, for any $i\in[K]$ each array $T_{i}$ of them is full of the same threshold value $t_{i}$ . Fix an index $k\in[K]$ such that $a=\min(t_{k},|T_{k}|)$ is the maximum among all $K$ chooses. It follows from lemma 7 and theorem 2 that $V(t_{k},a+N)$ is a linear $(N,\mathcal{T})$ multiple threshold scheme such that $\sum_{i\in[N]}H(P_{i})=N$ , $\sum_{i\in[K]}\sum_{j\in[|T_{i}|]}H(S_{i,j})=a$ , and we have an upper bound of the infimum of the average information ratio $\tilde{\sigma}_{N,\mathcal{T}}\leq{|\mathcal{T}|}/{\max_{i\in[K]}(\min(t_{i},|T_{i}|))},$ which matches lemma 6 and the optimum is obtained.

Theorem 4

The infimum of the average information ratio is decided by a specific access structure sub-array, more specifically,

\displaystyle\tilde{\sigma}_{N,\mathcal{T}}=\frac{|\mathcal{T}|}{\max_{i\in[K]}(\min(t_{i},|T_{i}|))},

(21)

when under the weak secure condition.

Proof:

The proof follows from the above illustrations. ∎

Remark 17

From this criteria of efficiency of a multiple threshold scheme with the weak secure condition, we can learn that for a unique threshold value $t$ , the number of secrets corresponding to $t$ is best controlled within $t$ . And compared to the strong secure condition, weak one improves the performance by a factor related to the number of secrets, which is also limited by the threshold value.

Theorem 5

As for the information ratio, we obtain the optimal results in three cases only:

1.

When $|T_{i}|\leq t_{i},\forall i\in[K]$ , $\sigma_{N,\mathcal{T}}=K$ .
2.

When $|T_{i}|\geq t_{i},\forall i\in[K]$ , $\sigma_{N,\mathcal{T}}=\sum_{i\in[K]}|T_{i}|/t_{i}$ .
3.

When there exists only one index $i\in[K]$ such that $|T_{i}|>t_{i}$ , $\sigma_{N,\mathcal{T}}=\max(K,K-1+|T_{k}|/t_{k}+(\sum_{i\in[k+1:K]}|T_{i}|-t_{i})/t_{k})$ .

Proof:

The proof follows from the following illustrations. ∎

In the first case consider different-threshold-bound (16) only, based on which the derivation of the lower bound for the infimum of the information ratio is carried in the following:

\displaystyle K\min_{k\in[K],j\in[|T_{k}|]}H(S_{k,j})\leq\sum_{k\in[K]}H(S_{k,j_{k}})\leq H(P_{i})\leq\max_{i\in[N]}H(P_{i}),

(22)

note that any share index $i$ is feasible and secret index $j_{k}$ is anyone of the set $[|T_{k}|]$ from the sub-array $T_{k}$ .

The number of participants is fixed to be $N$ , and for every sub-array index $i\in[K]$ , introduce an auxiliary access structure array $T_{i}$ extracted from the original access structure array $\mathcal{T}$ , we have $T_{i}\subseteq\mathcal{T}$ and $V(t_{i},|T_{i}|+N)$ is a linear $(N,T_{i})$ multiple threshold scheme and also for the structure $(N,\mathcal{T})$ by theorem 2. As the second and third terms of (22) from any such linear scheme are equal. Over a unified finite field whose order is sufficiently large, e.g., bigger than $\max_{i\in[K]}|T_{i}|+N$ , an independent combination of these $K$ generator matrices leads to a linear $(N,\mathcal{T})$ multiple threshold scheme, which facilitates all four terms in (22) to be equal.

Finally we have $\sigma_{N,\mathcal{T}}=K$ when $|T_{i}|\leq t_{i},\forall i\in[K]$ , which means for the information ratio criteria, when the number of secrets corresponding to the same threshold value $t$ is within $t$ , the number of different threshold values determines the performance.

In the second case we use threshold-product-bound (18) only and apply the same framework above. Similarly for any sub-array index $i\in[K]$ the generator matrix $V(t_{i},t_{i}+N)$ is a building block for structure $(N,{T_{i}})$ such that both sides of (18) are equal. The $K$ underlying finite fields are unified with a prime number bigger than $\max_{i\in[K]}t_{i}+N$ . Note that the length of every share is equal after any combination since each building block guarantees this property.We still need an independent combination of these $K$ building blocks to make the length of every secret to be equivalent.

An example is that for each $i\in[K]$ , consider $\binom{|T_{i}|}{t_{i}}$ different permutations of secrets from the same sub-array $T_{i}$ , then an initial independent combination is a linear $(N,T_{i})$ multiple threshold scheme $V_{i}$ such that $H(S_{i,j})=\binom{|T_{i}|-1}{t_{i}-1},\forall j\in[|T_{i}|]$ and $H(P_{j})=\binom{|T_{i}|}{t_{i}},\forall j\in[N]$ . In this way the length of secrets from any sub-array of the access structure array $\mathcal{T}$ are equal. As for all secrets, for any $i\in[K]$ we firstly independently combine the same $V_{i}$ for $(\prod_{j\in[K]}\binom{|T_{j}|-1}{t_{j}-1})/\binom{|T_{i}|-1}{t_{i}-1}$ times to get $V_{i}^{\prime}$ , then the final independent combination is carried on $\{V_{1}^{\prime},\ldots,V_{K}^{\prime}\}$ directly.

At last we have $\sigma_{N,\mathcal{T}}=\sum_{i\in[K]}|T_{i}|/t_{i}$ when $|T_{i}|\geq t_{i},\forall i\in[K]$ , which means for the information ratio criteria, when the number of secrets corresponding to the same threshold value $t$ is bigger than $t$ , the influence is individual for different kinds of threshold values, and the more secrets, the less efficiency.

Before introducing the last case, a new special linear scheme needs to be illustrated.

Lemma 8

For the structure $(N,\mathcal{T}=(T_{1},T_{2}))$ such that $|T_{1}|>t_{1}>t_{2}>|T_{2}|$ , there exists a linear multiple threshold scheme $B(N,T_{1},T_{2})$ satisfying $H(S_{1,j})=t_{2}-|T_{2}|,\forall j\in[|T_{1}|]$ , $H(S_{2,j})=|T_{1}|-t_{1},\forall j\in[|T_{2}|]$ and $H(P_{j})=t_{2}-|T_{2}|+|T_{1}|-t_{1},\forall j\in[N]$ . The number of rows of $B(N,T_{1},T_{2})$ is $|T_{1}|t_{2}-t_{1}|T_{2}|$ and the order of the underlying finite field is bigger than $\max((|T_{1}|+N)(t_{2}-|T_{2}|),N(|T_{1}|-t_{1}))$ and needs to be sufficiently large based on the weak secure condition for secrets in $\mathcal{T}_{2}$ as will be shown in the proof. The specific form of $B(N,T_{1},T_{2})$ needs the help of $V(|T_{1}|t_{2}-t_{1}|T_{2}|,[(|T_{1}|+N)(t_{2}-|T_{2}|)])$ and $V((|T_{1}|-t_{1})t_{2},[N(|T_{1}|-t_{1})])$ . The former can be divided into $|T_{1}|+N$ sub-matrices each with $t_{2}-|T_{2}|$ columns, then the first $|T_{1}|$ ones correspond to secrets from the sub-array $T_{1}$ and the last $N$ ones are part of the shares. Similarly the latter can be divided into $N$ sub-matrices each with $|T_{1}|-t_{1}$ columns, stack the $i$ -th sub-matrix with an all-zero one vertically to be a matrix with $|T_{1}|t_{2}-t_{1}|T_{2}|$ rows, and then stack the the former part and this matrix horizontally, we get the sub-matrix corresponding to the $i$ -th share. Finally consider an identity matrix with $|T_{2}|(|T_{1}|-t_{1})$ columns, stack it with an all-zero matrix vertically to have $|T_{1}|t_{2}-t_{1}|T_{2}|$ rows, then the matrix can be divided into $|T_{2}|$ sub-matrices each with $|T_{1}|-t_{1}$ columns and these matrices correspond to secrets from the sub-array $T_{2}$ . For example,

B(3,(3,3,3,3),(2))=\setcounter{MaxMatrixCols}{11}\begin{bmatrix}1&1&1&1&1&1&1&1&1&1&1\\ 1&2&3&4&0&5&1&6&2&7&3\\ 1&2^{2}&3^{2}&4^{2}&0&5^{2}&0&6^{2}&0&7^{2}&0\\ 1&2^{3}&3^{3}&4^{3}&0&5^{3}&0&6^{3}&0&7^{3}&0\\ 1&2^{4}&3^{4}&4^{4}&0&5^{4}&0&6^{4}&0&7^{4}&0\end{bmatrix}.

(23)

Proof:

The proof is carried by checking the system conditions of the definition of linear multiple threshold scheme. The detail can be found in Appendix B-E. ∎

Remark 18

This construction is novel and plays an important role for the information ratio and the (average) randomness ratio.

For the third case, both different-threshold-bound (16) and threshold-sum-difference-bound (17) are considered. In this case assume that $|T_{k}|>t_{k},k\in[K]$ and $|T_{i}|\leq t_{i},\forall i\in[K]/\{k\}$ , then we combine the two terms of the information ratio with threshold-sum-difference-bound (17) targeted on $k$ :

		$\displaystyle((K-1)t_{k}+\|T_{k}\|+\sum_{i\in[k+1:K]}\|T_{i}\|-t_{i})\min_{k\in[K],j\in[\|T_{k}\|]}H(S_{k,j})\leq$		(24)
		$\displaystyle t_{k}\sum_{i\in[k-1]}H(S_{i,j_{i}})+\sum_{i\in[k:K]}\sum_{j\in[\|T_{i}\|]}H(S_{i,j})+\sum_{i\in[k+1:K]}(t_{k}-t_{i})H(S_{i,j_{i}})$		(25)
		$\displaystyle\leq\sum_{j\in[t_{k}]}H(P_{i_{j}})\leq t_{k}\max_{i\in[N]}H(P_{i}),$		(26)

the declaration of $j_{i}$ and $i_{j}$ follows (17).

Then we prepare a linear scheme for the structure $(N,\mathcal{T})$ by independent combination like above. For any $i\in[k-1]$ the generator matrix $V(t_{i},|T_{i}|+N)$ is a building block for structure $(N,{T_{i}})$ such that both sides of (18) or (17) are equal, so are the building block $B(N,T_{k},T_{i}),i\in[k+1:K]$ for the structure $(N,(T_{k},T_{i}))$ when $|T_{i}|<t_{i}$ and the building block $V(t_{i},[t_{i}+N])$ for the structure $(N,T_{i})$ if $|T_{i}|=t_{i}$ . As the value of $\sum_{i\in[k+1:K]}t_{i}-|T_{i}|$ minus $|T_{k}|-t_{k}$ cased by the latter $K-k$ generator matrices may not be zero. We introduce two more pattern building blocks in order to make the length of every secret to be equivalent, i.e., the generator matrix $V(t_{k},t_{k}+N)$ for the structure $(N,T_{k})$ , it only fulfills threshold-sum-difference-bound (17), and the generator matrix $V(t_{i},|T_{i}|+N),i\in[k+1:K]$ for structure $(N,{T_{i}})$ while this only fulfills different-threshold-bound (16) when $|T_{i}|<t_{i}$ .

As in the second case the specific combination coefficients are tedious and by the above introduction of four pattern building blocks we give the conclusion directly. If $\sum_{i\in[k+1:K]}t_{i}-|T_{i}|\geq|T_{k}|-t_{k}$ , $\sigma_{N,\mathcal{T}}=K$ ; otherwise, $\sigma_{N,\mathcal{T}}=K-1+|T_{k}|/t_{k}+(\sum_{i\in[k+1:K]}|T_{i}|-t_{i})/t_{k}$ . It means for the information ratio criteria, when the circumstances that the number of secrets corresponding to the same threshold value $t$ is bigger than $t$ and less than $t$ both exist, the optimization is complicated and needs further insight.

IV (Average) randomness ratio

We firstly discuss multiple threshold scheme with the strong secure condition, of which some results can be modified for the weak secure condition.

IV-A strong secure

We firstly discuss a converse result which is fundamental for lower bounds of the (average) randomness ratio when under the strong secure condition.

Lemma 9

For any $(N,\mathcal{T})$ multiple threshold scheme with the strong secure condition, it holds that $\sum_{k\in[K]}\sum_{j\in[|T_{k}|]}t_{k}H(S_{k,j})\leq H(P_{[N]})$ .

Proof:

The proof is based on the mutual information bound as in lemma 1. The detail is in Appendix C-A. ∎

Remark 19

This bound says that when under the strong secure condition, the randomness of any $(N,\mathcal{T})$ multiple threshold scheme is at least the sum of the product of length of every secret and the corresponding threshold value. This is implied by the work from [12], while our proof may be more read-friendly due to the building block in lemma 1. Then consider the (average) randomness ratio, for any $(N,\mathcal{T})$ multiple threshold scheme, we apply this bound and it turns out that $\tau_{N,\mathcal{T}}\geq\sum_{k\in[K]}\sum_{j\in[|T_{k}|]}(t_{k}-1)$ and $\tilde{\tau}_{N,\mathcal{T}}\geq|\mathcal{T}|(t_{K}-1)$ , i.e., lower bounds are formed.

As for the achievability part, recall that from one secret to multiple ones, we can imply independent combination of $|\mathcal{T}|$ linear threshold schemes to get a linear $(N,\mathcal{T})$ multiple threshold scheme according to corollary 2. More specifically, given any structure $(N,\mathcal{T})$ , we prepare a linear $(t_{k},N,S_{k,j})$ threshold scheme based on $V(t_{k},[N+1])$ for any $k\in[K],j\in[|T_{k}|]$ , each of them is also a degradation version of linear $(N,\mathcal{T})$ multiple threshold scheme with the strong secure condition. The independent combination of these $|\mathcal{T}|$ generator matrices leads to a linear $(N,\mathcal{T})$ multiple threshold scheme with the strong secure condition such that $H(S_{k,j})=1,\forall k\in[K],j\in[|T_{k}|]$ and $H(P_{[N]})=\sum_{k\in[K]}\sum_{j\in[|T_{k}|]}t_{k}$ . Then we have $\tau_{N,\mathcal{T}}\leq\sum_{k\in[K]}\sum_{j\in[|T_{k}|]}(t_{k}-1)$ . We also derive an upper bound for the infimum of the average randomness ratio by a single generator matrix $V(t_{K},[N+1])$ , i.e., $\tilde{\tau}_{N,\mathcal{T}}\leq|\mathcal{T}|(t_{K}-1)$ .

Theorem 6

When under the strong secure condition, the infimum of the randomness ratio $\tau_{N,\mathcal{T}}=\sum_{k\in[K]}|T_{k}|(t_{k}-1)$ and the average randomness ratio $\tilde{\tau}_{N,\mathcal{T}}=|\mathcal{T}|(t_{K}-1)$ .

Proof:

The proof follows from the above illustrations. ∎

Remark 20

The novelty of this theorem compared to the known results of [12] is embedding the two criteria, i.e., the average randomness ratio and randomness ratio. Like the average information ratio, a specific threshold value determines the optimal complexity performance by the average randomness ratio criteria. The more secrets, the more complexity.

IV-B weak secure

IV-B1 converse

We firstly discuss some converse results that are fundamental for lower bounds of the (average) randomness ratio when under the weak secure condition.

Lemma 10 (Threshold-Value-Bound)

For any $(N,\mathcal{T})$ multiple threshold scheme with the weak secure condition, for any secret index $j_{k}\in[|T_{k}|]$ of the sub-array $T_{k}$ , it holds that

\displaystyle\sum_{k\in[K]}t_{k}H(S_{k,j_{k}})\leq H(P_{[N]}).

(27)

Proof:

Recall that the difference between the strong secure condition (3) and the weak one (3) is the knowledge of secrets. More specifically, substitute the secrets $H(\mathcal{S}_{k}^{\prime})$ of the bound in the proof of lemma 9 by a single secret $H(S_{k,1})$ , the result follows. ∎

Remark 21

Recall that the access structure array $\mathcal{T}$ can be divided into $K$ different sub-arrays based on $K$ unique threshold values. In this way threshold-value-bound says that the randomness of any $(N,\mathcal{T})$ multiple threshold scheme is at least the sum of the product of length of different kinds of secret and the corresponding threshold values, which is a weak version of lemma 9 due to the weak secure condition. This bound is novel as we investigate randomness under the weak secure condition. We find that it is crucial for the (average) randomness ratio. Consider the $\prod_{i\in[K]}|T_{i}|$ different permutations of threshold-value-bound, the sum is equivalent to the following bound

\sum_{k\in[K]}\sum_{j\in[|T_{k}|]}\frac{t_{k}}{|T_{k}|}H(S_{k,j})\leq H(P_{[N]}).

(28)

When under the weak secure condition, there is another novel bound similar to threshold-sum-difference-bound (17).

Lemma 11 (Threshold-Sum-Bound)

For any $(N,\mathcal{T})$ multiple threshold scheme with the weak secure condition, fix an index $k\in[K]$ , similar to lemma 3 let index $j_{i}$ be any element of the set $[|T_{i}|]$ , then

\sum_{i\in[k-1]}t_{i}H(S_{i,j_{i}})+\sum_{i\in[k:K]}\sum_{j\in[|T_{i}|]}H(S_{i,j})\leq H(P_{[N]}).

(29)

Proof:

The proof can be divided into two parts, each results in a special bound. The detail is in Appendix C-B. ∎

Remark 22

We find that it is crucial for the (average) randomness ratio. Consider the total $\prod_{i\in[k-1]}|T_{i}|$ different permutations of threshold-sum-bound, the sum is equivalent to the following bound

\sum_{i\in[k-1]}\sum_{j\in[|T_{i}|]}\frac{t_{i}}{|T_{i}|}H(S_{i,j})+\sum_{i\in[k:K]}\sum_{j\in[|T_{i}|]}H(S_{i,j})\leq H(P_{[N]}).

(30)

IV-B2 achievability

Then we discuss some linear schemes that are crucial for upper bounds of the (average) information ratio.

Recall that linear scheme like $V(t,[N+1])$ in definition 5 and lemma 7 for multiple threshold scheme under the (strong) weak secure condition is already known by the information theory community, and in the last section we propose a new generator matrix $B(N,T_{1},T_{2})$ which can be seen as a modified version of $V(t,[N+1])$ for specific structure. Here we continue this idea and give the following lemma.

Lemma 12

For the structure $(N,\mathcal{T}=(T_{1}))$ such that $|T_{1}|>t_{1}$ , there exists a linear multiple threshold scheme $A(N,T_{1},a)$ where integer $a\in[t_{1}-1]$ such that $H(S_{1,j})=a,\forall j\in[|T_{1}|]$ , $H(P_{i_{j}})=a,\forall j\in[t_{1}-a]$ and $H(P_{i_{j}})=|T_{1}|-t_{1}+a,\forall j\in[t_{1}-a+1:N]$ , here $(i_{1},\ldots,i_{N})$ are $N$ different values chosen from the set $[N]$ . The number of rows of $A(N,T_{1},a)$ is $a|T_{1}|$ and the order of the underlying finite field is bigger than $\max(a(|T_{1}|+N),(N-t_{1}+a)(|T_{1}|-t_{1}))$ . The specific form of $A(N,T_{1},a)$ needs the help of $V(a|T_{1}|,[a(|T_{1}|+N)])$ and $V(a(|T_{1}|-t_{1}),[(N-t_{1}+a)(|T_{1}|-t_{1})])$ . The former can be divided into $|T_{1}|+N$ sub-matrices each with $a$ columns, then the first $|T_{1}|$ ones correspond to secrets from the sub-array $T_{1}$ , the next $t_{1}-a$ ones for shares $\{P_{i_{1}},\ldots,P_{i_{t_{1}-a}}\}$ and the last $N-t_{1}+a$ ones are part of the other $N-t_{1}+a$ shares. Similarly the latter can be divided into $N-t_{1}+a$ sub-matrices each with $|T_{1}|-t_{1}$ columns, stack the $j$ -th sub-matrix with an all-zero one vertically to be a matrix with $a|T_{1}|$ rows, and then stack the the former part and this matrix horizontally, we get the sub-matrix corresponding to the $i_{t_{1}-a+j}$ -th share. For example,

A(3,(2,2,2),1)=\begin{bmatrix}1&1&1&1&1&1&1&1\\ 1&2&3&4&5&0&6&0\\ 1&2^{2}&3^{2}&4^{2}&5^{2}&0&6^{2}&0\end{bmatrix}.

(31)

Proof:

The proof is carried by checking the system conditions of the definition of linear multiple threshold scheme. The detail can be found in Appendix C-C. ∎

Remark 23

This construction is novel, has different size of shares and plays the extreme direction role [19] for the projection $\text{proj}_{\mathbf{h}_{I}}(\Gamma_{N+|T_{1}|}\cap\mathcal{C}_{0,1,3})$ when $t_{1}<N$ . When $t_{1}=N$ , the cases for $a\in[2:t_{1}-1]$ are not extreme directions as the threshold-sum-difference-bound (17) is unique, while the case that $a=1$ is an extreme direction. Recall that for a fixed structure $(N,T_{1})$ with $|T_{1}|>t_{1}$ , in the $(2^{N+|T_{1}|}-1)$ -dimension Euclidean space we denote the coordinates related with $N$ shares and $|T_{1}|$ secrets by $\mathbf{h}_{I}$ , and the projection is from the polyhedral cone formed by the Shannon-type inequalities and system conditions of the structure $(N,T_{1})$ .

Consider the average randomness ratio firstly and there are two cases. Recall that the access structure array $\mathcal{T}$ consists of $K$ sub-arrays.

The first one is that for any structure $(N,\mathcal{T})$ when there at least exists one index $i\in[K]$ satisfying $|T_{i}|\geq t_{i}$ . We use threshold-sum-bound (29) for $k=1$ and have a lower bound of the infimum of the average randomness ratio $\tilde{\tau}_{N,\mathcal{T}}\geq 0$ . Then the corresponding linear scheme can be $A(N,T_{i},1)$ or $V(t_{i},[t_{i}+N])$ for the structure $(N,\mathcal{T})$ by theorem 2 and it turns out that $\tilde{\tau}_{N,\mathcal{T}}\leq 0$ . The optimum is claimed and means that no additional randomness is needed in this case for the weak secure condition.

The second case is the opposite, that is, for every index $i\in[K]$ , the number of secrets corresponding to the same threshold value $t_{i}$ is less than $t_{i}$ , i.e., $|T_{i}|<t_{i}$ . Use the permutation version of threshold-value-bound (28) we have $\tilde{\tau}_{N,\mathcal{T}}\geq|\mathcal{T}|\cdot\min_{i\in[K]}(t_{i}-|T_{i}|)/|T_{i}|$ . Assume $k$ is the index matching this minimum value, a linear scheme $V(t_{k},[|T_{k}|+N])$ for the structure $(N,\mathcal{T})$ leads to the upper bound $\tilde{\tau}_{N,\mathcal{T}}\leq|\mathcal{T}|(t_{k}-|T_{k}|)/|T_{k}|$ . The optimum is claimed and means that under the weak secure condition we can benefit from the number of secrets corresponding to the same threshold value when consider randomness.

Theorem 7

For any structure $(N,\mathcal{T})$ , the infimum of the average randomness ratio

\displaystyle\tilde{\tau}_{N,\mathcal{T}}=|\mathcal{T}|\cdot\max(\min_{i\in[K]}(t_{i}-|T_{i}|)/|T_{i}|,0).

(32)

Proof:

The proof follows from the two cases mentioned above. ∎

As for the randomness ratio, still two cases will be discussed.

Similarly the first case is that the number of secrets corresponding to the same threshold value $t_{k}$ is bigger than $t_{k}$ , fix the smallest index from $[K]$ to be $k$ . Introduce the permutation version of threshold-sum-bound (30) towards $k$ and we have a lower bound of the infimum of the randomness ratio $\tau_{N,\mathcal{T}}\geq\sum_{i\in[k-1]}t_{i}-|T_{i}|$ . For any index $i\in[k-1]$ we prepare $V(t_{i},[|T_{i}|+N])$ for the structure $(N,T_{i})$ , the linear scheme $A(N,T_{k},1)$ is for the structure $(N,T_{k})$ and for every index $i\in[k+1]$ , if $|T_{i}|<t_{i}$ , the generator matrix $B(N,T_{k},T_{i})$ is used; otherwise, we only prepare $A(N,T_{i},1)$ or $V(t_{i},[t_{i}+N])$ . Let the order be sufficiently large we have a unified finite field, and the independent combination of these generator matrices leads to a linear $(N,\mathcal{T})$ multiple threshold scheme under the weak secure condition such that $\tau_{N,\mathcal{T}}\leq\sum_{i\in[k-1]}t_{i}-|T_{i}|$ . Finally the optimum is claimed and we can indeed learn that more secrets help to reduce randomness.

The second case is still the opposite, that is, for any index $i\in[K]$ , $|T_{i}|\leq t_{i}$ . Use the permutation version of threshold-value-bound (28) we have ${\tau}_{N,\mathcal{T}}\geq\sum_{i\in[K]}t_{i}-|T_{i}|$ . We prepare a generator matrix $V(t_{i},[|T_{i}|+N])$ for every sub-array $T_{i}$ . Still let the order be sufficiently large, over the unified finite field the independent combination of these $K$ generator matrices leads to $\tau_{N,\mathcal{T}}\leq\sum_{i\in[K]}t_{i}-|T_{i}|$ . The optimum is claimed.

Theorem 8

For any structure $(N,\mathcal{T})$ , the infimum of the randomness ratio

\displaystyle{\tau}_{N,\mathcal{T}}=\sum_{i\in[b]}t_{i}-|T_{i}|,

(33)

where b depends on the access structure array $\mathcal{T}$ . More specifically, if there exists an index $k\in[K]$ such that $|T_{k}|>t_{k}$ , let $b$ be the smallest such index minus 1; otherwise, $b=K$ .

Proof:

The proof follows from the two cases mentioned above. ∎

V Conclusions and future direction

TABLE I: four ratios under two secure conditions

	strong	weak
$\tilde{\sigma}_{N,\mathcal{T}}$	$\|\mathcal{T}\|$	$\|\mathcal{T}\|/\max_{i\in[K]}(\min(t_{i},\|T_{i}\|))$
${\sigma}_{N,\mathcal{T}}$	$\|\mathcal{T}\|$	$K$
		$\sum_{i\in[K]}\|T_{i}\|/t_{i}$
		$\max(K,K-1+\|T_{k}\|/t_{k}+(\sum_{i\in[k+1:K]}\|T_{i}\|-t_{i})/t_{k})$
		Unknown
$\tilde{\tau}_{N,\mathcal{T}}$	$\|\mathcal{T}\|(t_{K}-1)$	$\|\mathcal{T}\|\cdot\max(\min_{i\in[K]}(t_{i}-\|T_{i}\|)/\|T_{i}\|,0)$
${\tau}_{N,\mathcal{T}}$	$\sum_{k\in[K]}\|T_{k}\|(t_{k}-1)$	$\sum_{i\in[b]}t_{i}-\|T_{i}\|$

In table I we conclude the results of the four ratios. We can see that when under the weak secure condition, multiple threshold scheme has improved performance of both efficiency and complexity, compared to the strong secure condition.

When under the weak secure condition, we find that these three new bounds come from the case that the number of secrets corresponding to the same threshold value $t$ is lager than $t$ . As leaded by corollary 1, we conjecture that the projection $\text{proj}_{\mathbf{h}_{I}}(\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,3})$ may have all patterns of bounds, where $N=4$ , $\mathcal{T}=(T_{1},T_{2},T_{3})$ with $t_{1}=4,|T_{1}|=5$ , $t_{2}=3,|T_{2}|=4$ and $t_{3}=2,|T_{3}|=3$ . However, existing numerical experiments may be difficult to carry on due to the tremendous number of the Shannon-type inequalities involved. So the bound (20) may also be a good direction to attack.

Appendix A proofs for problem formulation

A-A proof of theorem 1

Let $\mathcal{P}:=\Gamma_{N+|\mathcal{T}^{\prime}|}\cap\mathcal{C}_{0,1,(2)3}^{\prime}$ and $\mathcal{Q}:=\text{proj}_{\mathbf{h}_{L}}(\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3})$ for ease of notation.

$(\Rightarrow)$ Form a set of $|\mathcal{T}|-|\mathcal{T}^{\prime}|$ excluded secrets $B:=\{S_{j}:|\mathcal{T}^{\prime}|+1\leq j\leq|\mathcal{T}|\}$ and recall that $\mathcal{O}$ is the set of $N+|\mathcal{T}|$ random variables. For any vector $\mathbf{x}\in\mathcal{P}$ , there exists a vector $\mathbf{X}\in\mathcal{H}_{N+|\mathcal{T}|}$ such that $\mathbf{X}_{\mathbf{h}_{L}}=\mathbf{x}$ , where $\mathbf{X}_{\mathbf{h}_{L}}$ is a vector extracted from the original vector $\mathbf{X}$ according to the coordinates of the region $\mathcal{P}$ . More specifically, for any non-empty $a\subseteq\mathcal{O}$ , let $X_{a}=x_{a/B}$ , where $x_{\emptyset}=0$ and $/$ means the difference of two sets, in this way it follows that $\mathbf{X}_{\mathbf{h}_{L}}=\mathbf{x}$ . The vector $\mathbf{X}$ satisfies the Shannon-type inequalities since for $a\subseteq b\subseteq\mathcal{O}$ , $X_{b}=x_{b/B}\geq x_{a/B}=X_{a}$ and for $a,b\subseteq\mathcal{O}$ , $X_{a}+X_{b}=x_{a/B}+x_{b/B}\geq x_{a\cup b/B}+x_{a\cap b/B}=X_{a\cup b}+X_{a\cap b}$ . $\mathbf{X}\in\mathcal{C}_{0}$ because $X_{S_{1},\ldots,S_{|\mathcal{T}|}}=x_{S_{1},\ldots,S_{|\mathcal{T}^{\prime}|}}=\sum_{i\in[|\mathcal{T}^{\prime}|]}x_{i}=\sum_{i\in[|\mathcal{T}|]}X_{i}$ . With the degeneration of the secrets in the set $B$ from the construction of the vector $X$ and by the definitions of decodable condition and (strong) weak condition similar to the independent assumption of all secrets, we have $\mathbf{X}\in\mathcal{C}_{1,(2)3}$ . Finally, $\forall\mathbf{x}\in\mathcal{P},\mathbf{x}\in\mathcal{Q}$ .

$(\Leftarrow)$ For any vector $\mathbf{X}\in\Gamma_{N+|\mathcal{T}|}\cap\mathcal{C}_{0,1,(2)3}$ , from which extract a vector $\mathbf{x}$ according to the coordinates of the region $\mathcal{P}$ . As $\mathbf{X}$ satisfies the Shannon-type inequalities for $N+|\mathcal{T}|$ random variables, it follows that $\mathbf{x}\in\Gamma_{N+|\mathcal{T}^{\prime}|}$ by the definitions of non-decreasing and submodular properties. With the help of the Shannon-type inequalities, we have $X_{S_{[|\mathcal{T}^{\prime}|]}}+\sum_{j=|\mathcal{T}^{\prime}|+1}^{j=|\mathcal{T}|}X_{S_{j}}\geq X_{S_{[|\mathcal{T}|]}}=\sum_{j\in[|\mathcal{T}|]}X_{S_{j}}$ and $\sum_{j\in[|\mathcal{T}^{\prime}|]}X_{S_{j}}\geq X_{S_{[|\mathcal{T}^{\prime}|]}}$ , then $\mathbf{x}\in\mathcal{C}_{0}^{\prime}$ . For $a\subseteq b\subseteq c\subseteq\mathcal{O}$ , similarly we have $X_{c}-X_{a}\geq X_{b}-X_{a}$ and when $X_{c}-X_{a}=0$ , it follows that $X_{b}-X_{a}=0$ , then $\mathbf{x}\in\mathcal{C}_{1}^{\prime}$ . For three disjoint sets $a,b,c\subseteq\mathcal{O}$ , we have $X_{a,b}+X_{a,c}\geq X_{a,b,c}+X_{c}$ and when $X_{a,b,c}=X_{a,b}+X_{c}$ , it follows that $X_{a,c}=X_{a}+X_{c}$ , then if we consider the strong secure condition, $\mathbf{x}\in\mathcal{C}_{2}^{\prime}$ . The case of $\mathcal{C}_{3}^{\prime}$ follows for reasons similar to the Shannon-type inequalities for different numbers of random variables above. Hence we have $\forall\mathbf{x}\in\mathcal{Q},\mathbf{x}\in\mathcal{P}$ .

A-B proof of theorem 2

Note that we have assumed all vectors of any sub-matrix $V_{i}$ of a generator matrix are linear independent, if $V_{i}$ is all-zero, we call such matrix a dummy one since $\text{rk}(V_{i})=0$ . Form a set of $|\mathcal{T}|-|\mathcal{T}^{\prime}|$ excluded secrets $B:=\{S_{j}:j\in[|\mathcal{T}^{\prime}|+1,|\mathcal{T}|]\}$ . We have already known that the generator matrix $V$ satisfies the system conditions of the structure $(N,\mathcal{T}^{\prime})$ , and we will show that after the construction of dummy matrices for the set of excluded secrets $B$ , $V$ is also for $(N,\mathcal{T})$ .

For the independent assumption of secrets, $\text{rk}(V_{S_{[|\mathcal{T}|]}})=\text{rk}(V_{S_{[|\mathcal{T}^{\prime}|]}})=\sum_{i\in[|\mathcal{T}^{\prime}|]}\text{rk}(V_{S_{i}})=\sum_{i\in[|\mathcal{T}|]}\text{rk}(V_{S_{i}})$ , the first equation is from the all-zero matrices, the second is by the property of $V$ and the third is still via the dummy construction. If we have $\text{rk}(V_{{S}_{C},P_{A}})=\text{rk}(V_{P_{A}}),A\subseteq[N],C\subseteq[|\mathcal{T}^{\prime}|]$ under the decodable condition, from the dummy construction it follows that $\text{rk}(V_{S_{B},{S}_{C},P_{A}})=\text{rk}(V_{{S}_{C},P_{A}})=\text{rk}(V_{P_{A}})$ , which is enough for the structure $(N,\mathcal{T})$ . Similarly consider the (strong) weak secure condition, if $\text{rk}(V_{{S}_{C},P_{A}})=\text{rk}(V_{P_{A}})+\text{rk}(V_{S_{c}}),A\subseteq[N],C\subseteq[|\mathcal{T}^{\prime}|]$ , as the additional matrices are all-zero, $\text{rk}(V_{S_{B},{S}_{C},P_{A}})=\text{rk}(V_{{S}_{C},P_{A}})=\text{rk}(V_{P_{A}})+\text{rk}(V_{S_{B},S_{c}})$ , which is also sufficient.

Appendix B proofs for (average) information ratio

B-A proof of lemma 2

Recall that the access structure array $\mathcal{T}$ has $K$ sub-arrays, each of them is denoted by $T_{k}$ full of $t_{k}$ , the same threshold value of the corresponding set of secrets $\mathcal{S}_{k}=\{S_{k,1},\ldots,S_{k,|T_{k}|}\}$ . In this way the non-increasing property of $\mathcal{T}$ says that $t_{1}>\cdots>t_{K}$ .

Based on corollary 1, we introduce an auxiliary access structure array $\mathcal{T}^{\prime}\supseteq\mathcal{T}$ . More specifically, $\mathcal{T}^{\prime}$ has $t_{1}-1$ sub-arrays with $t_{1}^{\prime}=t_{1},t_{2}^{\prime}=t_{1}-1,\ldots,t_{t_{1}-1}^{\prime}=2$ , and the length of each is larger than or equal to the corresponding sub-array of $\mathcal{T}$ , i.e., for any $k\in[t_{1}-1]$ , if there exists $j\in[K]$ such that $t_{k}^{\prime}=t_{j}$ , then $|T_{k}^{\prime}|=|T_{j}|$ ; otherwise, $|T_{k}^{\prime}|=1$ . Then our proof is towards the structure $(N,\mathcal{T}^{\prime})$ , and the result for the structure $(N,\mathcal{T})$ will be obtained from truncation.

For any $k\in[2:t_{1}-1]$ , from the strong secure condition (3), for all $A\subseteq[N]$ with $|A|\leq t_{k}^{\prime}-1$ , we have that $H(\mathcal{S}_{k}^{\prime}|P_{A})=H(\mathcal{S}_{k}^{\prime})$ ; and from the decodable condition (2), for all $B\subseteq[N]$ with $|B|\geq t_{k}^{\prime}$ , it holds that $H(\mathcal{S}_{k}^{\prime}|P_{B})=0$ . Substitute the single secret $S$ from lemma 1 by the set of secrets $\mathcal{S}_{k}^{\prime}$ , we have

H(\mathcal{S}_{k}^{\prime})\leq I(P_{1};P_{t_{1}-k+2}|P_{2},\ldots,P_{t_{1}-k+1}),

where we use the relation that $t_{k}^{\prime}=t_{1}-k+1$ due to the continuous nature.

And the boundary case is that

H(\mathcal{S}_{1}^{\prime})\leq H(P_{1}|P_{2},\ldots,P_{t_{1}}).

Sum these $t_{1}-1$ inequalities together, we have $\sum_{k\in[t_{1}-1]}H(\mathcal{S}_{k}^{\prime})\leq H(P_{1}|P_{2})\leq H(P_{1})$ . From the assumption that all secrets all statistically independent, the permutation of the indices of shares as mentioned in the proof of lemma 1 and the truncation technique from corollary 1, the final result follows.

B-B proof of lemma 4

Still we use plain number instead of index like $j_{1}$ as in the proof of lemma 1 for simplicity, and an auxiliary access structure array $\mathcal{T}^{\prime}\supseteq\mathcal{T}$ is introduced like the proof in lemma 2. More specifically, the access structure array $\mathcal{T}^{\prime}$ consists of $t_{1}-1$ continuous natural numbers from $t_{1}$ to $2$ , we replace the starting index $1$ by $k+t_{k}-t_{1}$ , i.e., $t_{k+t_{k}-t_{1}}^{\prime}=t_{1},\ldots,t_{k+t_{k}-2}^{\prime}=2$ , in this way we have $t_{k}^{\prime}=t_{k}$ from the relation $t_{i}^{\prime}=k+t_{k}-i$ . Fix an index $k\in[K]$ , three parts of inequalities will be presented.

The first part is about the right hand side of secrets $\mathcal{S}_{k}^{\prime}$ , based on the bound of lemma 1, for any index $i\in[k+1:k+t_{k}-2]$ , we prepare $i-k$ inequalities in the following:

	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{1};P_{k+t_{k}-i+1}\|P_{2},\ldots,P_{k+t_{k}-i}),$
	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{2};P_{k+t_{k}-i+2}\|P_{3},\ldots,P_{k+t_{k}-i+1}),$
		$\displaystyle\cdots$
	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{i-k};P_{t_{k}}\|P_{i-k+1},\ldots,P_{t_{k}-1}).$

Then the sum of these $\sum_{i=k+1}^{k+t_{k}-2}(i-k)$ inequalities leads to the following bound

\sum_{i=k+1}^{k+t_{k}-2}(i-k)H(S_{i,1}^{\prime})\leq\sum_{i\in[t_{k}-2]}H(P_{i}|P_{i+1})+H(P_{t_{k}-1},P_{t_{k}})-H(P_{[t_{k}]}).

(34)

Note that $t_{k}^{\prime}-t_{i}^{\prime}=i-k$ , $H(P_{i}|P_{i+1})\leq H(P_{i})$ and $H(P_{t_{k}-1},P_{t_{k}})\leq H(P_{t_{k}-1})+H(P_{t_{k}})$ . This concludes the first part and note that if the initial choose $t_{k}$ equals the last element of the auxiliary access structure array $\mathcal{T}^{\prime}$ , i.e., $2$ , this part is ignored.

The second part includes the secrets $\mathcal{S}_{k}^{\prime}$ compared to the fist part, i.e., the secrets $\mathcal{S}_{[k:k+t_{k}-2]}^{\prime}$ are considered here. When $N>t_{k}$ , based on the non-negativeness of conditional mutual information, we list $t_{k}$ inequalities in the following:

	$\displaystyle I(P_{1};P_{2},\ldots,P_{t_{k}+1}\|\mathcal{S}_{[k:k+t_{k}-2]}^{\prime})$	$\displaystyle\geq 0,$
	$\displaystyle I(P_{2};P_{3},\ldots,P_{t_{k}+1}\|P_{1},\mathcal{S}_{[k:k+t_{k}-2]}^{\prime})$	$\displaystyle\geq 0,$
		$\displaystyle\cdots$
	$\displaystyle I(P_{t_{k}};P_{t_{k}+1}\|P_{1},\ldots,P_{t_{k}-1}\mathcal{S}_{[k:k+t_{k}-2]}^{\prime})$	$\displaystyle\geq 0.$

Consider the sum of these $t_{k}$ inequalities and recall the decodable condition (2), substitute $H(P_{1},\ldots P_{t_{k}},\mathcal{S}_{[k:k+t_{k}-2]}^{\prime})$ by $H(P_{1},\ldots P_{t_{k}})$ , for any $i\in[t_{k}]$ replace the conditional entropy $H(P_{i}|P_{[t_{k}+1]/\{i\}},\mathcal{S}_{[k:k+t_{k}-2]}^{\prime})$ by $H(P_{i}|P_{[t_{k}+1]/\{i\}})$ , and via the independent assumption of secrets (1) we finally have

\sum_{i\in[k:k+t_{k}-2]}\sum_{j\in|T_{i}^{\prime}|}H(S_{i,j}^{\prime})\leq H(P_{[t_{k}]})-\sum_{i\in[t_{k}]}H(P_{i}|P_{[t_{k}+1]/\{i\}}).

(35)

When $N=t_{k}$ we use $\sum_{i\in[k:k+t_{k}-2]}\sum_{j\in|T_{i}^{\prime}|}H(S_{i,j}^{\prime})\leq H(P_{[t_{k}]})$ by the decodable condition directly.

The third part considers the rest secrets, i.e., $\mathcal{S}_{[k+t_{k}-t_{1}:k-1]}^{\prime}$ . Still based on the bound of lemma 1, for any index $i\in[k+t_{k}-t_{1}+1:k-1]$ , $t_{k}$ inequalities are prepared in the following:

	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{1};P_{k+t_{k}-i+1}\|P_{[t_{k}]/\{1\}},P_{t_{k}+1},\ldots,P_{k+t_{k}-i}),$
	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{2};P_{k+t_{k}-i+1}\|P_{[t_{k}]/\{2\}},P_{t_{k}+1},\ldots,P_{k+t_{k}-i}),$
		$\displaystyle\cdots$
	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{t_{k}};P_{k+t_{k}-i+1}\|P_{[t_{k}]/\{t_{k}\}},P_{t_{k}+1},\ldots,P_{k+t_{k}-i}).$

For the boundary case $i=k+t_{k}-t_{1}$ , we introduce $t_{k}$ conditional entropy bounds instead of conditional mutual information ones like the boundary part in the proof of lemma 2.

	$\displaystyle H(S_{k+t_{k}-t_{1},1}^{\prime})$	$\displaystyle\leq H(P_{1}\|P_{[t_{k}]/\{1\}},P_{t_{k}+1},\ldots,P_{t_{1}}),$
	$\displaystyle H(S_{k+t_{k}-t_{1},1}^{\prime})$	$\displaystyle\leq H(P_{2}\|P_{[t_{k}]/\{2\}},P_{t_{k}+1},\ldots,P_{t_{1}}),$
		$\displaystyle\cdots$
	$\displaystyle H(S_{k+t_{k}-t_{1},1}^{\prime})$	$\displaystyle\leq H(P_{t_{k}}\|P_{[t_{k}]/\{t_{k}\}},P_{t_{k}+1},\ldots,P_{t_{1}}).$

Then the sum of these $(t_{1}-t_{k})t_{k}$ inequalities leads to the following bound

t_{k}\sum_{i=k+t_{k}-t_{1}}^{k-1}H(S_{i,1}^{\prime})\leq\sum_{i\in[t_{k}]}H(P_{i}|P_{[t_{k}+1]/\{i\}}).

(36)

This concludes the third part and note that if the initial choose $t_{k}$ equals the first element of the auxiliary access structure array $\mathcal{T}^{\prime}$ , i.e., $t_{1}$ , or $k=1$ for short, this part is ignored.

From the permutation of the indices of shares as mentioned in the proof of lemma 1 and the truncation technique from corollary 1, the final result follows by the sum of these three parts.

B-C proof of lemma 5

Recall that the access structure array $\mathcal{T}$ has $K$ sub-arrays, if $K=1$ , this bound follows by $H(\mathcal{S}_{1},P_{[t_{1}]})=H(P_{[t_{1}]})\geq H(\mathcal{S}_{1})$ .

When $K\geq 2$ , we introduce an auxiliary access structure array $\mathcal{T}^{\prime}\supseteq\mathcal{T}$ as in lemma 2. More specifically, $\mathcal{T}^{\prime}$ has $t_{1}-1$ sub-arrays with $t_{1}^{\prime}=t_{1},t_{2}^{\prime}=t_{1}-1,\ldots,t_{t_{1}-1}^{\prime}=2$ , and the length of each is larger than or equal to the corresponding sub-array of $\mathcal{T}$ , i.e., for any $k\in[t_{1}-1]$ , if there exists $j\in[K]$ such that $t_{k}^{\prime}=t_{j}$ , then $|T_{k}^{\prime}|=|T_{j}|$ ; otherwise, $|T_{k}^{\prime}|=1$ . Then our proof is towards the structure $(N,\mathcal{T}^{\prime})$ , and the result for the structure $(N,\mathcal{T})$ will be obtained from truncation and dividing the same positive integer in both sides of the inequality.

For every $k\in[2:t_{1}-1]$ , we prepare a pattern inequality which is rewritten from the bound (35), one of the three ingredients for the threshold-sum-difference-bound:

t_{k}^{\prime}H(P_{[t_{k}^{\prime}+1]})+H(\mathcal{S}_{[k:t_{1}-1]}^{\prime})\leq\sum_{i\in[t_{k}^{\prime}+1]}H(P_{[t_{k}^{\prime}+1]/\{i\}}).

(37)

The core idea is that special permutations of every pattern inequality except the first one are summed to cancel the entropies of shares. More specifically, the term $H(P_{[t_{k}^{\prime}+1]})$ can be permuted to cancel the term $\sum_{i\in[t_{k-1}^{\prime}+1]}H(P_{[t_{k-1}^{\prime}+1]/\{i\}})$ of a new pattern inequality ahead, also this pattern inequality for $k-1$ can be multiplied to maintain integral coefficients. Such induction procedure leads to

\displaystyle\prod_{k\in[2:t_{1}-1]}kH(P_{[t_{1}]})+\sum_{i\in[2:t_{1}-1]}\frac{\prod_{k\in[2:t_{1}]}k}{t_{i-1}t_{i}}H(\mathcal{S}_{[i:t_{1}-1]}^{\prime})\leq\prod_{k\in[2:t_{1}-1]}k\sum_{i\in[t_{1}]}H(P_{i}).

(38)

Note that similar to the case $K=1$ , $H(P_{[t_{1}]})\geq H(\mathcal{S}_{[t_{1}-1]}^{\prime})$ , due to the assumption of mutually independent secrets, the permutation of indices of $N$ shares and the truncation technique from corollary 1, the final result follows.

B-D proof of lemma 6

The proof is carried via case analysis where two cases are involved.

The first case is that for every $i\in[K]$ , the length of the sub-array $T_{i}$ is not bigger than the unique threshold value $t_{i}$ of it, i.e., $|T_{i}|\leq t_{i}$ . Assume $\max_{i\in[K]}(|T_{i}|)=|T_{k}|$ , then we introduce an auxiliary access structure array $\mathcal{T}^{\prime}$ such that $\forall i\in[K],|T_{i}^{\prime}|=|T_{k}|,t_{i}^{\prime}=t_{i}$ . Note that the number of all different different-threshold-bounds (16) is $N|T_{k}|^{K}$ , the sum of them is the following:

\displaystyle N|T_{k}|^{K-1}\sum_{i\in[K]}\sum_{j\in[|T_{k}|]}H(S_{i,j}^{\prime})\leq|T_{k}|^{K}\sum_{i\in[N]}H(P_{i}).

Based on the technique of truncation as in corollary 1 we have $\tilde{\sigma}_{N,\mathcal{T}}\geq{|\mathcal{T}|}/{|T_{k}|}$ .

Another case is the opposite, i.e., there at least exists one sub-array such that the length of it is strictly bigger than the corresponding threshold value, assume the first one is $T_{k}$ and then $|T_{i}|\leq t_{i},i\in[k-1]$ where $[0]$ is the empty set. In this way let $a=\max(|T_{1}|,\ldots,|T_{k}-1|,t_{k})$ and due to the non-increasing assumption of the access structure array it follows that for any $i\in[k+1:K]$ , $a\geq\min(t_{i},|T_{i}|)$ . The auxiliary access structure array $\mathcal{T}^{\prime}$ is constructed similarly, $|T_{i}^{\prime}|=a,i\in[k-1],|T_{i}^{\prime}|=|T_{i}|,i\in[k:K]$ and the $K$ unique threshold values are the same. We only use the first two parts in the left hand side of threshold-sum-difference-bound (17), i.e., such relaxation ignores the difference part. Consider the permutation of secrets firstly, the sum of $a^{k-1}$ such inequalities for fixed $t_{k}$ different shares is the following:

\displaystyle t_{k}a^{k-2}\sum_{i\in[k-1]}\sum_{j\in[|T_{i}|]}H(S_{i,j}^{\prime})+a^{k-1}\sum_{i\in[k:K]}\sum_{j\in[|T_{i}|]}H(S_{i,j}^{\prime})\leq a^{k-1}\sum_{i\in[t_{k}]}H(P_{i}),

note that when $k=1$ , the first part in the left hand side is ignored and $a^{k-1}=t_{k}a^{k-2}$ in the second part; if $k\geq 2$ , we relax the coefficient $a^{k-1}$ of the second part to be $t_{k}a^{k-2}$ . Finally consider the permutation of $N$ shares, the sum is the following:

\displaystyle\binom{N}{t_{k}}t_{k}a^{k-2}\sum_{i\in[K]}\sum_{j\in[|T_{i}|]}H(S_{i,j}^{\prime})\leq\binom{N-1}{t_{k}-1}a^{k-1}\sum_{i\in[K]}H(P_{i}).

Still based on the truncation we have $\tilde{\sigma}_{N,\mathcal{T}}\geq{|\mathcal{T}|}/{a}$ .

B-E proof of lemma 8

Note that in a Vandermonde matrix any sub-matrix is full rank. Denote $B(N,T_{1},T_{2})$ by $V$ for short.

For all secrets we have $\text{rk}(V_{\mathcal{S}_{[2]}})=|T_{2}|(|T_{1}|-t_{1})+|T_{1}|(t_{2}-|T_{2}|)=|T_{1}|t_{2}-t_{1}|T_{2}|$ as the identity matrix in the upper right corner of $V_{\mathcal{S}_{[2]}}$ is full rank, so is the sub-matrix in the lower left corner since it is the sub-matrix of a Vandermonde matrix, and that the lower right corner is all-zero facilitates applying Gaussian-Elimination to obtain rank.

For any $i\in[N]$ split the matrix corresponding to share $P_{i}$ into two parts, that is, let $V_{P_{i}}^{l}$ be the first $t_{2}-|T_{2}|$ columns and the last $|T_{1}|-t_{1}$ columns form $V_{P_{i}}^{r}$ .

As for decodable condition, firstly note that the rank of the matrix formed by any $t_{1}$ shares like $V_{P_{[t_{1}]}}$ equals the number of rows of $V$ . The reason is that the upper $t_{2}(|T_{1}|-t_{1})$ rows of the matrix $V_{P_{[t_{1}]}}^{r}$ , which is the concatenation of the right part of every $V_{P_{i}},i\in[t_{1}]$ horizontally, is full rank as the number of columns is bigger than that of rows, then consider the lower $t_{1}(t_{2}-|T_{2}|)$ rows of the matrix $V_{P_{[t_{1}]}}^{l}$ , it is full rank and such lower rows of $V_{P_{[t_{1}]}}^{r}$ are all-zero. In this way we have $\text{rk}(V_{P_{[t_{1}]}})=t_{2}(|T_{1}|-t_{1})+t_{1}(t_{2}-|T_{2}|)=|T_{1}|t_{2}-t_{1}|T_{2}|$ , which is also the value of $\text{rk}(V_{\mathcal{S}_{[2]},P_{[t_{1}]}})$ . Secondly consider the matrix formed by any $t_{2}$ shares like $V_{P_{[t_{2}]}}$ , of which the upper $t_{2}(|T_{1}|-t_{1})$ rows of the matrix $V_{P_{[t_{2}]}}^{r}$ are full rank and the other rows are all-zero. The upper $|T_{2}|(|T_{1}|-t_{1})$ rows of the matrix corresponding to the secrets $\mathcal{S}_{2}$ are full rank and the other rows are all-zero. As $t_{2}>|T_{2}|$ , then every column of $V_{\mathcal{S}_{2}}$ equals a linear combination of the columns from $V_{P_{[t_{2}]}}^{r}$ , we have $\text{rk}(V_{P_{[t_{2}]}})=\text{rk}(V_{\mathcal{S}_{2},P_{[t_{2}]}})$ .

At last consider weak secure condition. The rank of the matrix formed by any $t_{1}-1$ shares like $V_{P_{[t_{1}-1]}}$ equals $(t_{1}-1)(t_{2}-|T_{2}|)+t_{2}(|T_{1}|-t_{1})$ since both $V_{P_{[t_{1}-1]}}^{r}$ and lower $t_{1}(t_{2}-|T_{2}|)$ rows of $V_{P_{[t_{1}-1]}}^{l}$ are full rank, the lower $t_{1}(t_{2}-|T_{2}|)$ all-zeros rows of $V_{P_{[t_{1}-1]}}^{r}$ facilitate this observation by Gaussian-Elimination. Stack the matrix corresponding to any secret $S_{1,j},j\in[|T_{1}|]$ and $V_{P_{[t_{1}-1]}}$ horizontally, note that the former is extracted from $V(|T_{1}|t_{2}-t_{1}|T_{2}|,[(|T_{1}|+N)(t_{2}-|T_{2}|)])$ , similarly we have $\text{rk}(V_{S_{1,j},P_{[t_{1}-1]}})=\text{rk}(V_{S_{1,j}})+\text{rk}(V_{P_{[t_{1}-1]}})=|T_{1}|t_{2}-t_{1}|T_{2}|$ . Then we need to focus on the matrix formed by any $t_{2}-1$ shares like $V_{P_{[t_{2}-1]}}$ . The $\text{rk}(V_{S_{1,j},P_{[t_{2}-1]}})=\text{rk}(V_{S_{1,j}})+\text{rk}(V_{P_{[t_{2}-1]}})=t_{2}(t_{2}-|T_{2}|)+(t_{2}-1)(|T_{1}|-t_{1})$ part follows the same procedure as for $t_{1}-1$ shares.

The case for any secret $S_{2,j},j\in[|T_{2}|]$ is not straightforward like before. Recall the matrix $V_{S_{2,j}}$ corresponding to secret $S_{2,j}$ , it has an identity matrix embedded between the $(j-1)(|T_{1}|-t_{1})+1$ -th row and the $j(|T_{1}|-t_{1})$ -th row, the other elements of $V_{S_{2,j}}$ are all-zero. Stack it with $V_{P_{[t_{2}-1]}}^{r}$ horizontally, for weak secure condition we only need to consider the rank of a special matrix extracted from $V_{P_{[t_{2}-1]}}^{r}$ , i.e., the concatenation of the first $(j-1)(|T_{1}|-t_{1})$ rows and $(t_{2}-j)(|T_{1}|-t_{1})$ rows between the $j(|T_{1}|-t_{1})+1$ -th row and the $t_{2}(|T_{1}|-t_{1})$ -th row. The determinant of this matrix is related to Schur polynomials [20] which is not $0$ when the order of the underlying finite field is sufficiently large. For example we can calculate the specific determinants in real number field for all cases, any of which is the product of the sum of monomials and Vandermonde determinant, thus bigger than zero, finally choose the finite field order to be larger than any determinant. In this way $\text{rk}(V_{S_{2,j},P_{[t_{2}-1]}})=\text{rk}(V_{S_{2,j}})+\text{rk}(V_{P_{[t_{2}-1]}})=(t_{2}-1)(t_{2}-|T_{2}|)+t_{2}(|T_{1}|-t_{1})$ .

Appendix C proofs for (average) randomness ratio

C-A proof of lemma 9

If $K\geq 2$ , for any $k\in[2:t_{1}-1]$ , from the strong secure condition (3), for all $A\subseteq[N]$ with $|A|\leq t_{k}^{\prime}-1$ , we have that $H(\mathcal{S}_{k}^{\prime}|P_{A})=H(\mathcal{S}_{k}^{\prime})$ ; and from the decodable condition (2), for all $B\subseteq[N]$ with $|B|\geq t_{k}^{\prime}$ , it holds that $H(\mathcal{S}_{k}^{\prime}|P_{B})=0$ . Substitute the single secret $S$ from lemma 1 by the set of secrets $\mathcal{S}_{k}^{\prime}$ , for any index $i\in[t_{1}-k+1]$ where we use the relation that $t_{k}^{\prime}=t_{1}-k+1$ due to the continuous nature, $t_{1}-k+1$ inequalities are prepared in the following:

	$\displaystyle H(\mathcal{S}_{k}^{\prime})$	$\displaystyle\leq I(P_{1};P_{t_{1}-k+2}\|P_{[t_{1}-k+1]/\{1\}}),$
	$\displaystyle H(\mathcal{S}_{k}^{\prime})$	$\displaystyle\leq I(P_{2};P_{t_{1}-k+2}\|P_{[t_{1}-k+1]/\{2\}}),$
		$\displaystyle\cdots$
	$\displaystyle H(\mathcal{S}_{k}^{\prime})$	$\displaystyle\leq I(P_{t_{1}-k+1};P_{t_{1}-k+2}\|P_{[t_{1}-k+1]/\{t_{1}-k+1\}}).$

For the boundary case $k=1$ , we introduce $t_{1}$ conditional entropy bounds instead of conditional mutual information ones like in the proof of lemma 2.

	$\displaystyle H(\mathcal{S}_{1}^{\prime})$	$\displaystyle\leq H(P_{1}\|P_{[t_{1}]/\{1\}}),$
	$\displaystyle H(\mathcal{S}_{1}^{\prime})$	$\displaystyle\leq H(P_{2}\|P_{[t_{1}]/\{2\}}),$
		$\displaystyle\cdots$
	$\displaystyle H(\mathcal{S}_{1}^{\prime})$	$\displaystyle\leq H(P_{t_{1}}\|P_{[t_{1}]/\{t_{1}\}}).$

Then the sum of these $(t_{1}-1)(t_{1}+2)/2$ inequalities leads to the following bound

\sum_{k\in[K]}t_{k}^{\prime}H(\mathcal{S}_{k}^{\prime})\leq H(P_{[t_{1}]})-I(P_{1};P_{2})\leq H(P_{[N]}).

(39)

If $K=1$ , similarly consider the above $t_{1}$ conditional entropy bounds and the second part in the proof of threshold-sum-difference-bound (17). The sum leads to

t_{1}H(\mathcal{S}_{1}^{\prime})\leq H(P_{[t_{1}]})-\sum_{k\in[t_{1}-1]}I(P_{k};P_{[k+1:t_{1}]}|P_{[k-1]})\leq H(P_{[N]}).

(40)

C-B proof of lemma 11

When $k=1$ we use $\sum_{i\in[k+t_{k}-t_{1}:k+t_{k}-2]}\sum_{j\in|T_{i}^{\prime}|}H(S_{i,j}^{\prime})\leq H(P_{[N]})$ by decodable condition directly. Otherwise fix an index $k\in[2:K]$ , two parts of inequalities will be presented.

The first part considers the secrets $\mathcal{S}_{[k:k+t_{k}-2]}^{\prime}$ . Based on the non-negativeness of conditional mutual information, we list $t_{k}$ inequalities in the following:

	$\displaystyle I(P_{1};P_{2},\ldots,P_{t_{k}+1}\|\mathcal{S}_{[k:k+t_{k}-2]}^{\prime})$	$\displaystyle\geq 0,$
	$\displaystyle I(P_{2};P_{3},\ldots,P_{t_{k}+1}\|P_{1},\mathcal{S}_{[k:k+t_{k}-2]}^{\prime})$	$\displaystyle\geq 0,$
		$\displaystyle\cdots$
	$\displaystyle I(P_{t_{k}};P_{t_{k}+1}\|P_{1},\ldots,P_{t_{k}-1}\mathcal{S}_{[k:k+t_{k}-2]}^{\prime})$	$\displaystyle\geq 0.$

\sum_{i\in[k:k+t_{k}-2]}\sum_{j\in|T_{i}^{\prime}|}H(S_{i,j}^{\prime})\leq H(P_{[t_{k}]})-\sum_{i\in[t_{k}]}H(P_{i}|P_{[t_{k}+1]/\{i\}}).

(41)

The second part considers the rest secrets, i.e., $\mathcal{S}_{[k+t_{k}-t_{1}:k-1]}^{\prime}$ . Still based on the bound of lemma 1, for any index $i\in[k+t_{k}-t_{1}+1:k-1]$ , $t_{i}^{\prime}=k+t_{k}-i$ inequalities are prepared in the following:

	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{1};P_{k+t_{k}-i+1}\|P_{[k+t_{k}-i]/\{1\}}),$
	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{2};P_{k+t_{k}-i+1}\|P_{[k+t_{k}-i]/\{2\}}),$
		$\displaystyle\cdots$
	$\displaystyle H(S_{i,1}^{\prime})$	$\displaystyle\leq I(P_{k+t_{k}-i};P_{k+t_{k}-i+1}\|P_{[k+t_{k}-i]/\{k+t_{k}-i\}}).$

For the boundary case $i=k+t_{k}-t_{1}$ , we introduce $t_{1}$ conditional entropy bounds instead of conditional mutual information ones like in the proof of lemma 1.

	$\displaystyle H(S_{k+t_{k}-t_{1},1}^{\prime})$	$\displaystyle\leq H(P_{1}\|P_{[t_{1}]/\{1\}}),$
	$\displaystyle H(S_{k+t_{k}-t_{1},1}^{\prime})$	$\displaystyle\leq H(P_{2}\|P_{[t_{1}]/\{2\}}),$
		$\displaystyle\cdots$
	$\displaystyle H(S_{k+t_{k}-t_{1},1}^{\prime})$	$\displaystyle\leq H(P_{t_{1}}\|P_{[t_{1}]/\{t_{1}\}}).$

Then the sum of these $(t_{1}-t_{k})(t_{1}+t_{k}+1)/2$ inequalities leads to the following bound

\sum_{i=k+t_{k}-t_{1}}^{k-1}(k+t_{k}-i)H(S_{i,1}^{\prime})\leq-H(P_{[t_{k}]})+\sum_{i\in[t_{k}]}H(P_{i}|P_{[t_{k}+1]/\{i\}})+H(P_{[t_{1}]}).

(42)

From the permutation of the indices of shares as mentioned in the proof of lemma 1 and the truncation technique from corollary 1, the final result follows by the sum of these two parts.

C-C proof of lemma 12

Note that in a Vandermonde matrix any sub-matrix is full rank. Denote $A(N,T_{1},a)$ by $V$ for short.

For all secrets we have $\text{rk}(V_{\mathcal{S}_{1}})=a|T_{1}|$ since it is the sub-matrix of a Vandermonde matrix.

For any $t_{1}$ shares, we have $at_{1}$ different columns extracted from $V(a|T_{1}|,[a(|T_{1}|+N)])$ and at least $a(|T_{1}|-t_{1})$ different columns from $V(a(|T_{1}|-t_{1}),[(N-t_{1}+a)(|T_{1}|-t_{1})])$ stacked with an all-zero matrix. From this view stack these two matrices horizontally, we can see that the upper right corner is full rank, so is the sub-matrix in the lower left corner since both are the sub-matrices of Vandermonde matrices, and that the lower right corner is all-zero facilitates applying Gaussian-Elimination to obtain the decodable condition, i.e., $\text{rk}(V_{P_{d}})=\text{rk}(V_{\mathcal{S}_{1},P_{d}})=a|T_{1}|$ where $P_{d}$ denotes any $t_{1}$ shares.

For any $t_{1}-1$ shares, we have $a(t_{1}-1)$ different columns extracted from $V(a|T_{1}|,[a(|T_{1}|+N)])$ , regardless of the number of participants $N$ we assume there are at most $(t_{1}-1)(|T_{1}|-t_{1})$ different columns from $V(a(|T_{1}|-t_{1}),[(|T_{1}|-t_{1})\cdot\max(N-t_{1}+a,t_{1}-1)])$ stacked with an all-zero matrix. From this view stack these two matrices horizontally and denote any $t_{1}-1$ shares by $P_{s}$ we can see that $\text{rk}(V_{P_{s}})=a(t_{1}-1)+a(|T_{1}|-t_{1})=a(|T_{1}|-1)$ as $a\leq t_{1}-1$ and following the similar procedure in decodable condition above. Then consider any secret, we have $a$ different columns extracted from $V(a|T_{1}|,[a(|T_{1}|+N)])$ , stack these two matrices horizontally and the final matrix is still full rank. Finally we have $\text{rk}(V_{S_{1,j},P_{s}})=\text{rk}(V_{S_{1,j}})+\text{rk}(V_{P_{s}})=a|T_{1}|,j\in[|T_{1}|]$ .

When $a=1$ we find that any $|T_{1}|-t_{1}$ columns from $V(a(|T_{1}|-t_{1}),[(N-t_{1}+a)(|T_{1}|-t_{1})])$ form an square matrix which is full rank. Then this part can be substituted by an identity matrix and the order of the underlying finite field may be smaller.

References

[1] Adi Shamir. How to share a secret. Communications of The ACM, 22(11):612–613, 1979.
[2] D. R. Stinson. An explication of secret sharing schemes. Designs, Codes and Cryptography, 2(4):357–390, 1992.
[3] Wen-Ai Jackson and Keith M. Martin. Perfect secret sharing schemes on five participants. Designs, Codes and Cryptography, 9(3):267–286, 1996.
[4] Oriol Farràs, Tarik Kaced, Sebastià Martín, and Carles Padro. Improving the linear programming technique in the search for lower bounds in secret sharing. IEEE Transactions on Information Theory, 66(11):7088–7100, 2020.
[5] Carles Padró. Lecture notes in secret sharing. IACR Cryptology ePrint Archive, 2012:674, 2012.
[6] Carlo Blundo, Alfredo De Santis, and Ugo Vaccaro. Randomness in distribution protocols. Information and Computation, 131(2):111–139, 1996.
[7] Oriol Farràs, Ignacio Gracia, Sebastià Martín, and Carles Padró. Linear threshold multisecret sharing schemes. Information Processing Letters, 112(17-18):667–673, 2012.
[8] Chun-ming Tang and Shu-guang Dai. The complexity and randomness of linear multi-secret sharing schemes with non-threshold structures. Acta Mathematicae Applicatae Sinica, English Series, 30(4):1073–1084, 2014.
[9] Gustavus J Simmons. An introduction to shared secret and/or shared control schemes and their application. 1992.
[10] Ali Khalesi, Mahtab Mirmohseni, and Mohammad Ali Maddah-Ali. The capacity region of distributed multi-user secret sharing. IEEE Journal on Selected Areas in Information Theory, 2(3):1057–1071, 2021.
[11] Mahdi Soleymani and Hessam Mahdavifar. Distributed multi-user secret sharing. IEEE Transactions on Information Theory, 67(1):164–178, 2020.
[12] Alfredo De Santis and Barbara Masucci. Multiple ramp schemes. IEEE Transactions on Information Theory, 45(5):1720–1728, 1999.
[13] Javier Herranz, Alexandre Ruiz, and Germán Sáez. New results and applications for multi-secret sharing schemes. Designs, codes and cryptography, 73(3):841–864, 2014.
[14] Robert J. McEliece and Dilip V. Sarwate. On sharing secrets and reed-solomon codes. Communications of the ACM, 24(9):583–584, 1981.
[15] Ehud Karnin, Jonathan Greene, and Martin Hellman. On secret sharing systems. IEEE Transactions on Information Theory, 29(1):35–41, 1983.
[16] László Csirmaz. How to share secrets simultaneously. Cryptology ePrint Archive, 2011.
[17] Zhen Zhang and R.W. Yeung. On characterization of entropy function via information inequalities. IEEE Transactions on Information Theory, 44(4):1440–1452, 1998.
[18] Bohdan L Kaluzny. Polyhedral computation: a survey of projection methods. 2002.
[19] Bob Pakzad-Hurson, Greg Ference, Veselka Kafedzhieva, Michael Cline, Akinwale Akinbiyi, Ethan Wright, Richard Benjamin, and Douglas Mercer. Linear programming: Penn state math 484 lecture notes. 2014.
[20] Amritanshu Prasad. An introduction to schur polynomials. arXiv preprint arXiv:1802.06073, 2018.

	$\displaystyle H(S)=$	$\displaystyle H(S\|P_{3},\ldots,P_{t+1})-H(S\|P_{1},P_{3},\ldots,P_{t+1})$
		$\displaystyle-H(S\|P_{2},P_{3},\ldots,P_{t+1})+H(S\|P_{1},\ldots,P_{t+1})$
	$\displaystyle=$	$\displaystyle I(S;P_{1}\|P_{3},\ldots,P_{t+1})-I(S;P_{1}\|P_{2},P_{3},\ldots,P_{t+1})$
	$\displaystyle=$	$\displaystyle H(P_{1}\|P_{3},\ldots,P_{t+1})-H(P_{1}\|S,P_{3},\ldots,P_{t+1})$
		$\displaystyle-H(P_{1}\|P_{2},P_{3},\ldots,P_{t+1})+H(P_{1}\|S,P_{2},P_{3},\ldots,P_{t+1})$
	$\displaystyle=$	$\displaystyle I(P_{1};P_{2}\|P_{3},\ldots,P_{t+1})-I(P_{1};P_{2}\|S,P_{3},\ldots,P_{t+1})$
	$\displaystyle\leq$	$\displaystyle I(P_{1};P_{2}\|P_{3},\ldots,P_{t+1})$