Secure Groupcast with Shared Keys
Hua Sun
cs.IT cs.CR math.IT





















Secure Groupcast with Shared Keys


    Hua Sun 


    
====================================




Hua Sun (email: hua.sun@unt.edu) is with the Department of Electrical Engineering at the University of North Texas. 


Secure Groupcast with Shared Keys


    Hua Sun 


    
====================================




We consider a transmitter and K receivers, each of which shares a key variable with the transmitter. Through a noiseless broadcast channel, the transmitter wishes to send a common message W securely to N out of the K receivers while the remaining K-N receivers learn no information about W. We are interested in the maximum message rate, i.e., the maximum number of bits of W that can be securely groupcast to the legitimate receivers per key block and the minimum broadcast bandwidth, i.e., the minimum number of bits of the broadcast information required to securely groupcast the message bits.

We focus on the setting of combinatorial keys, where every subset of the K receivers share an independent key of arbitrary size. Under this combinatorial key setting, the maximum message rate is characterized for the following scenarios - 1) N=1 or N=K-1, i.e., secure unicast to 1 receiver with K-1 eavesdroppers or secure groupcast to K-1 receivers with 1 eavesdropper, 2) N=2, K=4, i.e., secure groupcast to 2 out of 4 receivers, and 3) the symmetric setting where the key size for any subset of the same cardinality is equal for any N,K. Further, for the latter two cases, the minimum broadcast bandwidth for the maximum message rate is characterized.







§ INTRODUCTION

The first theoretical analysis of cryptography and secrecy system was carried out by Shannon in the groundbreaking 1949 work <cit.>, where the mathematical framework of information theoretic security was introduced to establish the fundamental limits of secure point-to-point communication. Shannon studied the one-time pad system (see Fig. <ref>.1), where Alice shares a key Z with Bob and wishes to send an independent message W to Bob such that even if the transmit signal X is fully eavesdropped by Eve, Eve cannot learn anything about W as long as Eve has no knowledge of the key Z. The simple one-time pad scheme X = W + Z, where `+' represents bit-wise binary addition is proved information theoretically secure and communication-wise optimal in the following sense.



  * To send one bit of the message W securely, one bit of the key Z must be shared. That is, the maximum message rate is 1 bit per key bit.

  * To send one bit of the message W securely, one bit of the transmit signal X must be broadcast (seen by everyone). That is, the minimum broadcast bandwidth is 1 bit per message bit.








In this work, motivated by the need of secure group (beyond point-to-point) communication under complex adversarial scenario (beyond a single eavesdropper knowing nothing about the key), we consider the following secure groupcast communication scenario. A transmitter shares a key variable Z_k, k ∈{1,2,⋯, K} with Receiver k and Z_k may be arbitrarily correlated (see Fig. <ref>.2). Aided by the shared keys, the transmitter wishes to send a common message W securely to N out of the K receivers through broadcasting the signal X to all receivers, in a way that any one of the remaining K-N receivers learns no information about W in the information theoretic sense.

This secure groupcast problem naturally generalizes Shannon's one-time pad system, which is a special case of secure unicast (N=1) over a K=2 receiver broadcast channel and the eavesdropping receiver knows nothing about the key of the legitimate receiver. Following the communication metrics considered by Shannon, we focus on the following two questions regarding the fundamental limits of secure groupcast.


  * What is the maximum message rate, defined as the maximum number of bits of the message W that can be securely groupcast per key block (a classic Shannon theoretic formulation where we may code over a long key block and the block size is allowed to approach infinity)? 

  * What is the minimum broadcast bandwidth, defined as the minimum number of bits of the broadcast information X required to securely groupcast a message of certain rate?

Beyond being an elemental model for information theoretic security, the above shared key secure groupcast problem arises naturally in many applications, where we interpret the keys either as digital tokens or information from memory devices (e.g., in premiere streaming or game distribution), 
or more generally as side-information variables that could be sensed from the environment or obtained from prior communication (e.g., in wireless networking). In addition, the model can be easily extended from groupcasting a single message for a single group to multiple messages, each exclusively for an arbitrary group under various security constraints, i.e., the secure groupcast model is introduced to enable broadcasting to a selected set of qualified receivers while unqualified receivers obtain no useful information.



 §.§ Combinatorial Key Setting

As an initial step, we mainly focus on the combinatorial key setting, where every subset 𝒰 of the K receivers share an independent key S_𝒰 of arbitrary size. An example is shown in Fig. <ref>, where S_1 denotes the key that is known only to Receiver 1 (and the transmitter), S_145 (abbreviation of S_{1,4,5} for simplicity) is known to Receiver 1, Receiver 4 and Receiver 5 etc. Further, the S variables with different subscripts are independent of each other.






The combinatorial key setting turns out to be technically challenging due to the necessity of highly structured coding of the message symbols and the key symbols (for which the setting in Fig. <ref> is a representative example even when the S variables all have the same size), and the abundance of parameters (as the key size for different subsets may be different so that overall the order of parameters is exponential in K). The essence is to accommodate for and utilize the complex correlation among the keys so that legitimate receivers can decode the common message 
while eavesdropping receivers cannot obtain anything from the correlated keys (i.e., need to avoid leakage under multiple correlated views). 
Our results are summarized next.



 §.§ Main Results and Techniques

The main results of this work include the exact characterization of the maximum message rate and the minimum broadcast bandwidth for settings listed below.



  * N=1, any K: This is the secure unicast setting, with only 1 desired receiver. Both the maximum message rate and the minimum broadcast bandwidth are characterized. The achievable scheme is based on random linear coding over the key symbols. Refer to Theorem <ref>.

  * N=K-1, any K: This can be viewed as the secure multicast setting, with only 1 eavesdropper. The maximum message rate is characterized (and the minimum broadcast bandwidth when K≤ 4 or when the total secure key size is the same for all receivers). The achievable scheme is based on random linear coding over the message symbols. Refer to Theorem <ref>.

  * N=2, K=4: Both the maximum message rate and the minimum broadcast bandwidth are characterized. The achievable scheme requires a delicate structured decomposition to basic components according to the key sizes. Refer to Theorem <ref>.

  * The symmetric setting for any N, K, where the size of the key S_𝒰 only depends on |𝒰| (i.e., the cardinality of the subset): Both the maximum message rate and the minimum broadcast bandwidth are characterized. The achievable scheme requires an intricate coding over keys from various subsets that handles correctness and security jointly. Refer to Theorem <ref>.

  * The converse bounds on the message rate for all results above are given by a simple conditional entropy term (refer to Theorem <ref>); the converse bounds on the broadcast bandwidth for all results above have an interesting unified form that can be interpreted through common information (refer to Theorem <ref>). 

  * The simple conditional entropy converse bound in Theorem <ref> is not tight in general. Specifically, a stronger bound is derived for the setting in Fig. <ref> when the S variables have the same size and the maximum message rate is characterized with  a matching vector linear coding scheme (refer to Theorem <ref>). 


We have also explored the generalization to the following scenarios.


  * The rate region of secure groupcasting multiple messages. Specifically, we consider 2 legitimate receivers with 3 desired messages (1 for each individual receiver so that the other receiver learns nothing and a common message for both receivers) and all these 3 messages must be kept fully secure to an eavesdropping receiver. Refer to Theorem <ref>.


  * The discrete memoryless key setting. Interestingly, the scenarios where random linear codes suffice for the combinatorial key setting (i.e., N=1 and N=K-1) generalize fully to discrete memoryless keys by random binning. Refer to Theorem <ref>.


We start with the problem statement and defer the discussion of related prior work in key agreement, 
latent capacity region, secure broadcasting, and secure index coding to Section <ref>.

Notation: For positive integers K_1, K_2, K_1 ≤ K_2, we use the notation [K_1:K_2] = {K_1, K_1+1,⋯, K_2}. The notation |𝒰| is used to denote the cardinality of a set 𝒰 and the notation |X| is used to denote the number of elements of a vector X.  
For a matrix V, V(i,j) represents the element in the i-th row and j-th column. For two matrices V_1,  V_2 (with the same number of columns), [ V_1;  V_2] denotes the row stack of V_1,  V_2. A binomial coefficient KU is defined as 0 if K < U.




§ PROBLEM STATEMENT

Define K discrete random variables z_1, z_2,⋯, z_K of finite cardinality, drawn from an arbitrary joint distribution P_z_1, z_2,⋯, z_K. Following the convention, Z_1, Z_2,⋯, Z_K denote L length extensions of z_1, z_2,⋯, z_K, i.e., Z_1, Z_2,⋯, Z_K are sequences of length L, such that the sequence of tuples [Z_1(l), Z_2(l), ⋯, Z_K(l)]_l=1^L is produced i.i.d. according to P_z_1, z_2,⋯, z_K.

Consider a transmitter that knows the keys Z_1, Z_2,⋯, Z_K, and K receivers such that Receiver k knows Z_k, k ∈ [1:K]. The transmitter wishes to send a common message W securely to the first N receivers, where 1≤ N ≤ K-1. The message W consists of L_W i.i.d. uniform symbols from a finite field[As usual for an information theoretic formulation, the actual size of the message is allowed to approach infinity. We allow the optimization of both parameters of the key block length L and the field size p, to match the code dimensions and simplify the presentation of the coding scheme.] 𝔽_p for a prime power p, so H(W) = L_W log_2 p bits. We assume that the message W is independent of the key variables Z_1, Z_2,⋯, Z_K.

    I(W; Z_1, Z_2,⋯, Z_K) = 0.


The communication channel is a noiseless broadcast channel, i.e., the transmit signal X is sent by the transmitter and seen by every receiver. To securely groupcast the message W, the transmit signal X consists of L_X symbols from 𝔽_p.

From the transmit signal X and the key Z_k, each legitimate receiver must be able to decode the message W, with probability of error P_e. The probability of error must approach zero as the key block length L approaches infinity[If P_e is required to be exactly zero, then the o(L) term can be replaced with 0. The situation is similar if zero leakage instead of vanishing leakage is required in the security constraint (<ref>).]. From Fano's inequality, we have

    H(W | X, Z_k) = o(L),  ∀ k ∈ [1:N]

where any function of L, say f(L), is said to be o(L) if lim_L→∞ f(L)/L = 0. From the transmit signal X and the key Z_k, each eavesdropping receiver obtains a negligible amount of information about the message W.

    I(W; X, Z_k) = o(L), ∀ k ∈ [N+1:K].


The groupcast rate characterizes how many bits of the message are securely groupcast per key block, and is defined as follows.

    R = H(W)/L = L_Wlog_2 p/L.

A rate R is said to be achievable if there exists a sequence of secure groupcast schemes (indexed by L), each of rate greater or equal to R, for which P_e → 0 as L →∞ (i.e., the correctness constraint (<ref>) and the security constraint (<ref>) are satisfied). The supremum of achievable rates is called the capacity C.

The broadcast bandwidth β(R) characterizes how many bits of the transmit signal are broadcast per key block to securely groupcast a message of rate R, and is defined as follows.

    β(R) = L_Xlog_2 p/L.

The achievable broadcast bandwidth is defined similarly, i.e., broadcast bandwidth β(R) is said to be achievable if there exists a sequence of secure groupcast schemes, each of rate greater than or equal to R and each of broadcast bandwidth smaller than or equal to β(R), for which  P_e → 0 as L →∞. The infimum of achievable broadcast bandwidth is called the minimum broadcast bandwidth β^*(R).

We will be mainly interested in the capacity, C and the minimum broadcast bandwidth when the rate value is the capacity, β^*(C).



 §.§ Combinatorial Keys

The combinatorial key setting refers to a specific type of joint distribution of the keys and is defined as follows. Consider 2^K-1 independent random variables s_𝒰, where 𝒰 may be any non-empty subset of [1:K]. For example, when K=3, we have[For s_𝒰, we may simplify the subscript when the elements of 𝒰 are easy to list, e.g., we may write s_{1,2} as s_12.] s_1, s_2, s_3, s_12, s_13, s_23, s_123.

    H(s_1, s_2, ⋯, s_𝒰, ⋯, s_1:K) = H(s_1) + H(s_2) + ⋯ + H(s_𝒰) + ⋯ + H(s_1:K).

We assume that s_𝒰 consists of an integer number, say L_𝒰, of i.i.d. uniform symbols from 𝔽_p.

    H(s_𝒰) = L_𝒰log_2 p  .

The variable z_k is the collection of all s_𝒰 variables such that k ∈𝒰.

    z_k = (s_𝒰 : k ∈𝒰).

For example, when K=3, z_2 = (s_2, s_12, s_23, s_123). The symmetric setting is defined as follows.

    H(s_𝒰_1) = H(s_𝒰_2), 
    ∀𝒰_1, 𝒰_2     |𝒰_1| = |𝒰_2|.


The extension of the above system model to include multiple groupcast messages is immediate and will be presented when we consider this generalization in Section <ref>.



§ MAIN RESULTS

In this section, we summarize our main results along with illustrative examples and observations.


 §.§ Converse on Rate R and Broadcast Bandwidth β(R)

We present a simple converse bound on the groupcast rate R in the following theorem.


[Rate Converse]
For any secure groupcast problem (to the first N of K receivers), 

    R ≤ H(z_q | z_e),  ∀ q ∈ [1:N], ∀ e ∈ [N+1:K].


The proof of Theorem <ref> is presented in Section <ref>. The conditional entropy bound (<ref>) is very intuitive, because W must be decoded by any qualified Receiver q ∈ [1:N] and cannot be learned by any eavesdropping Receiver e ∈ [N+1:K]. Surprisingly, this simple conditional entropy bound turns out to be tight for many settings of interest (see below). However, it is not sufficient in general (refer to Remark <ref> after Theorem <ref>).

Next, we present an interesting converse bound on the broadcast bandwidth β(R) in the following theorem. 


[Broadcast Bandwidth Converse]
For any secure groupcast problem (to the first N of K receivers), consider any set of qualified receivers 𝒬≜{q_1, ⋯, q_|𝒬|}⊂ [1:N] and consider any random variable u_e that is a function of the key of an eavesdropping Receiver e ∈ [N+1:K], i.e., H(u_e|z_e) = 0.

    β(R)    ≥    |𝒬| R - ( ∑_i=1^|𝒬| H(z_q_i | u_e) - H(z_q_1, z_q_2, ⋯, z_q_|𝒬| | u_e) ) 
       =     |𝒬| R - ∑_i=1^|𝒬|-1 I(z_q_1, ⋯, z_q_i; z_q_i+1 | u_e).



The proof of Theorem <ref> is presented in Section <ref>. The negative term on the RHS of (<ref>) captures the benefits of correlated keys in reducing the broadcast bandwidth. On one extreme when the keys are fully independent, this negative term is zero and we have to send the message W to all |𝒬| qualified receivers one by one, so that the broadcast bandwidth is |𝒬| times of the rate, R of the message, i.e., β(R) ≥ |𝒬|R. On the other extreme when the keys are identical and independent of the key at the eavesdropping receiver (i.e., z_q_1 = ⋯ = z_q_𝒬), this negative term becomes (|𝒬|-1) H(z_q_1). Now suppose R = H(z_q_1), then the broadcast bandwidth bound becomes β(R) ≥ R and it might suffice to simply send out the one-time pad signal W + Z_q_1. In general, between the two extremes, the saving is given by the difference between the sum of individual entropy of each key and the joint entropy of all keys, which can be interpreted as a form of common information. Interestingly, this common information type of term can also be written as the sum of a chain of mutual information terms.





Equipped with the above converse results, we are now ready to proceed to consider the combinatorial key setting, which is referred to as the combinatorial secure groupcast problem for short. Note that for combinatorial secure groupcast, all achievable schemes satisfy zero error and zero leakage (i.e., o(L) is replaced with 0 in (<ref>), (<ref>)).



 §.§ Secure Unicast N=1 and Secure Multicast N=K-1 Settings

When there is only N= 1 desired receiver, secure groupcast reduces to secure unicast, and this combinatorial secure unicast problem can be solved by random linear coding over the key symbols for the achievability side and the bounds given above for the converse side. This result is presented in the following theorem.


[Secure Unicast]
For the combinatorial secure unicast problem (to the first of K receivers), the capacity and the minimum broadcast bandwidth for capacity achieving schemes are

    C    =   min_e∈ [2:K] H(z_1 | z_e) = min_e ∈ [2:K]∑_c𝒰⊂ [1:K]: 
    
    1 ∈𝒰, e ∉𝒰 H(s_𝒰), 
    
    
    β^*(C)    =    C.




The proof of Theorem <ref> is presented in Section <ref>. The achievability is based on creating a key from what the legitimate Receiver 1 knows so that any one of the K-1 eavesdropping receivers cannot learn anything about the created key. This key can be created by random linear coding and after the key is created, one-time pad coding suffices to achieve the capacity and the minimum broadcast bandwidth. An example is presented below to explain this idea.


Consider a combinatorial secure unicast instance with K=4 receivers, where the key configurations are given as follows. 

    z_1 = (s_12, s_13, s_14, s_134),  z_2 = (s_12),  z_3 = (s_13, s_134),  z_4 = (s_14, s_134); 
    
    H(s_12) = 4 log_2 p,  H(s_13) = 2 log_2 p,  H(s_14) = log_2 p,  H(s_134) = 3 log_2 p.

For example, s_12∈𝔽_p^4× 1 contains 4 symbols from 𝔽_p.
From Theorem <ref>, we have

    C = min(H(s_13)+H(s_14)+H(s_134), H(s_12)+H(s_14), H(s_12)+H(s_13)) = 5 log_2 p , 
          β^*(C) = C = 5 log_2 p.

The converse follows immediately from Theorem <ref> (taking the minimum converse bound over all eavesdropping receivers) and Theorem <ref> (taking 𝒬 = {1} so that β(R) ≥ R). The achievable scheme is presented next. Consider L=1 block of the keys (then Z_k = z_k) and we wish to send L_W = 5 message symbols from 𝔽_p by broadcasting L_X = 5 symbols, i.e., W, X are both 5× 1 vectors over 𝔽_p. The combinatorial key variables are each precoded by a beamforming matrix to produce a mixed key, which is then added with the message W to produce the transmit signal X.

    X = W +  V_12 s_12 +  V_13 s_13 +  V_14 s_14 +  V_134 s_134

where the precoding matrices have 5 rows each and the number of columns matches the dimension of the key variables, e.g., V_12∈𝔽_p^5× 4. The correctness constraint (<ref>) is trivially satisfied. For eavesdropping Receiver 2, after canceling the known key, he can recover

    W +  V_13 s_13 +  V_14 s_14 +  V_134 s_134  = W + [ V_13  V_14  V_134] 
    [ [  s_13;  s_14; s_134 ]]

so that in order to make sure nothing is revealed, we need 

    [ V_13  V_14  V_134]_5× 6 .
           [ V_12  V_14 ]_5× 5 
    
    and        [ V_12  V_13]_5× 6 .

That is, we simply need the matrices to have full rank, which is easily satisfied by generic MDS matrices, e.g., Cauchy matrices over a properly large field. The details are deferred to the proof presented in Section <ref>. Finally, the rate and broadcast bandwidth achieved match the converse.


We next consider the (somewhat) dual of secure unicast (a single legitimate receiver and any number of eavesdroppers) - secure multicast (a single eavesdropper and any number of legitimate receivers), whose capacity is solved by a similar random linear coding idea (but over the message symbols instead of over the key symbols). This result is presented in the following theorem.


[Secure Multicast]
For the combinatorial secure multicast problem (to the first K-1 of K receivers), the capacity is 

    C = min_q∈[1:K-1] H(z_q|z_K) = min_q∈[1:K-1]∑_𝒰⊂ [1:K-1]: q∈𝒰
    H(s_𝒰).

Further, the minimum broadcast bandwidth for capacity achieving schemes is characterized in the following two cases.

    1.  H(z_1|z_K) = ⋯ = H(z_K-1|z_K):  β^*(C) = ∑_𝒰⊂[1:K-1] H(s_𝒰). 
          2.  K=4  (): 
          β^*(C) =H(s_123)+ max(2H(s_1)+H(s_12)+2H(s_13), 3H(s_1)+2H(s_12)+2H(s_13)-H(s_23)).



The proof of Theorem <ref> is presented in Section <ref>. To achieve the capacity, we simply generate random linear combinations of the message symbols and mix them with each of the combinatorial keys. Each legitimate receiver can decode the message after collecting a sufficient number of coded message symbols. This idea is explained in the following example.


Consider a combinatorial secure multicast instance with K=4 receivers, where the key configurations are given as follows. 

    z_1 = (s_1, s_13),  z_2 = (s_23),  z_3 = (s_13, s_23),  z_4=(); 
    
    H(s_1) = log_2 p,  H(s_13) = 2 log_2 p,  H(s_23) = 3 log_2 p.

From Theorem <ref>, we have

    C = min(H(s_1) + H(s_13), H(s_23), H(s_13) + H(s_23)) = 3log_2 p,
          β^*(C) = max(2H(s_1)+2H(s_13), 3H(s_1)+2H(s_13)-H(s_23)) = 6 log_2 p.

The rate converse is simply given by the minimum entropy of the legitimate key variables (and follows from Theorem <ref>). The broadcast bandwidth converse is given by Theorem 2, where 𝒬 = {1,2} and u_e = () so that β(C) ≥ 2C - I(z_1;z_2) = 2C. The achievable scheme is presented next. Consider L=1 and W ∈𝔽_p^3 × 1. The transmit signal X∈𝔽_p^6× 1 is produced as follows.

    X = [[   V_1 W + s_1; V_13 W + s_13; V_23 W + s_23 ]]

where the dimensions of the precoding matrices are specified as V_1 ∈𝔽_p^1× 3,  V_13∈𝔽_p^2× 3,  V_23∈𝔽_p^3× 3. For the secure multicast problem, security is trivial as the keys known by the eavesdropping receiver are never used and correctness requires that 

    [ V_1;  V_13]  ,  [ V_23]  , 
           [ V_13;  V_23]  .

The above constraints can be satisfied by generic (e.g., Cauchy or any MDS) matrices and details are deferred to the full proof presented in Section <ref>. 



While the capacity of secure multicast is solved simply by random linear codes, the minimum broadcast bandwidth for capacity achieving schemes is generally an open problem (e.g., when K≥ 5). When K≤ 4, we need to analyze carefully which combinatorial key has redundancy and quantify the amount so as to use only the minimum required (see Section <ref>). 


Interestingly, the above random coding idea for both combinatorial secure unicast and secure multicast generalizes to the discrete memoryless key setting, where corresponding results are obtained using standard existing random binning arguments (see Theorem <ref>). 



 §.§ Secure Groupcast to N=2 of K=4 Receivers

The capacity and minimum broadcast bandwidth for the combinatorial secure groupcast problem to 2 out of 4 receivers are characterized in the following theorem.

[N=2, K=4] 
For the combinatorial secure groupcast problem to the first N=2 of K=4 receivers, the capacity is

    C = min_q∈{1,2}, e∈{3,4} H(z_q | z_e) = H(s_12) + min( H(s_1)+H(s_14) + H(s_124), H(s_1)+H(s_13) + H(s_123), 
    
    H(s_2)+H(s_24) + H(s_124), H(s_2)+H(s_23) + H(s_123) )

and the minimum broadcast bandwidth for capacity achieving schemes is 

    β^*(C) = 2C - H(s_12) - min( H(s_123), H(s_124) ).



The proof of Theorem <ref> is presented in Section <ref>. The complexity mainly lies in the abundance of the parameters so that we need to decompose the problem instance into multiple basic components (also how to identify basic components) and depending on the key configurations, there are many case studies. To this end, we need a decomposition result of two achievable schemes with two independent sets of keys, stated in the following lemma. 

Consider two sets of independent keys (Z_1^[1], ⋯, Z_K^[1]) and (Z_1^[2], ⋯, Z_K^[2]) such that L_W^[1] and L_W^[2] symbols of the messages W^[1], W^[2] can be securely groupcast with L_X^[1] and L_X^[2] symbols of the transmit signals X^[1], X^[2], respectively. Then we can concatenate the two schemes to one such that the keys are Z_k = (Z_k^[1], Z_k^[2]), k ∈ [1:K], L_W = L_W^[1] + L_W^[2] symbols of W = (W^[1], W^[2]) are securely groupcast with L_X = L_X^[1] + L_X^[2] symbols of X = (X^[1], X^[2]).

Proof: The proof is almost immediate. As long as each component scheme is correct and secure, the concatenated scheme will be correct and secure as the keys are independent and the message and transmit signal symbols are also independent. Further, this concatenation generalizes trivially to any number of independent key sets.


We are now ready to give an example of the combinatorial secure groupcast problem to 2 of 4 receivers, to illustrate the main idea.

Consider a combinatorial secure groupcast instance to 2 of 4 receivers, where the key configurations are given as follows. Remember that z_k = (s_𝒰: k ∈𝒰), k ∈{1,2,3,4}.

    (H(s_1), H(s_2), H(s_13), H(s_14), H(s_23), H(s_24), H(s_123), H(s_124)) = (1,2,2,3,1,2,2,1).

From Theorem <ref>, we have

    C = min_q∈{1,2}, e∈{3,4} H(z_q | z_e) = min(5, 5, 5, 5) = 5,
          β^*(C) = 2C - 0 - min(2,1) = 9.

The rate converse follows from the conditional entropy bound in Theorem <ref> and the broadcast bandwidth converse follows from Theorem <ref> by setting 𝒬 = {1,2} and u_e = z_3 or z_4. The achievable scheme is shown in the following figure, where we decompose the instance into 3 sub-networks. We operate over the binary field 𝔽_2, i.e., p=2 and key block size is L=1. The total number of bits in the message and the transmit signal match the converse above (5 and 9, respectively). All key bits are used, e.g., H(s_14) = 3 so that we have 3 bits of s_14, and sub-network 1 uses 1 bit and sub-network 3 uses 2 bits (see Fig. <ref>). Correctness and security are easy to verify.








 §.§ Secure Groupcast: Symmetric Setting

We consider now the symmetric setting, where the key size only depends on the cardinality of the set of the receivers that have the same key. For any set 𝒰⊂ [1:K] with cardinality |𝒰| = u, u ∈ [1:K], we denote the key size as H(s_𝒰) = L^[u]log_2 p. The capacity and minimum broadcast bandwidth for the symmetric setting are characterized in the following theorem.


[Symmetric Setting]
For the symmetric combinatorial secure groupcast problem (to the first N of K receivers), the capacity and the minimum broadcast bandwidth for capacity achieving schemes are

    C = ∑_u=1^K K-2u-1L^[u]log_2 p,   β^*(C) = ∑_u=1^K ( K-1u - K-N-1u) L^[u]log_2 p.



We refer to a key that is known to u receivers as a u-key. From the capacity and broadcast bandwidth formula, we see that it suffices to consider  u-keys separately for distinct u values, i.e., joint coding across different u-keys is not necessary. This is generally not true (e.g., see Fig. <ref>.1) and greatly simplifies the problem. After we notice this simplification (we may limit to only u-keys of one u value), the problem still requires an intricate decomposition of the keys, depending on how many qualified receivers and how many eavesdropping receivers know the key. An example is presented below to illustrate the main idea and the full proof is presented in Section <ref>.


Consider a symmetric combinatorial secure groupcast instance to N=3 of K=6 receivers, where we only have 3-keys, i.e., 63 keys of the same length L^[3] = 1. 

From Theorem <ref>, we have

    C = 42log_2 p = 6log_2 p,   β^*(C) = 53log_2 p = 10 log_2 p.

The rate converse follows from the conditional entropy bound in Theorem <ref>, where we may pick any qualified receiver and any eavesdropping receiver such that the qualified receiver knows 42 keys that are not known to the eavesdropping receiver. The broadcast bandwidth converse follows from Theorem <ref> by setting 𝒬 = [1:3] and u_e = z_6 so that β(C) ≥  H(z_1, z_2, z_3 | z_6) = 53log_2 p.

The achievability is designed based on dividing the 3-keys into 3 groups. 


  * The first group involves the key that is known only to 3 qualified receivers, i.e., s_123. As s_123 is not known to the eavesdropping receivers, we simply send 1 message symbol with 1 symbol of one-time pad transmit signal, i.e., we have achieved R^1 = β^[1](R^1) = log_2 p. 

  * The second group involves the keys that are known to 2 qualified receivers and 1 eavesdropping receiver. We need to further divide these keys depending on the set of 2 qualified receivers. Suppose the set of qualified receivers is {1,2}, i.e., we are considering the keys (s_124, s_125, s_126) that are common to qualified Receiver 1 and qualified Receiver 2. Further, any eavesdropping receiver only knows 1 key from (s_124, s_125, s_126). In other words, we have the secure unicast situation (note that here Receiver 1 and Receiver 2 both require the same message and hold the same key) where the desired receiver has 4 equal-size combinatorial key variables while the eavesdropping receivers have 1 combinatorial key each. Therefore, combining generic linear coding ideas for key symbols in Theorem <ref> and for message symbols in Theorem <ref>, we can send 3-1=2 symbols securely to Receiver 1 and Receiver 2 by transmitting

    X^2,12 =  V^w_12 W^2 +  V^s_124 s_124 +  V^s_125 s_125 +  V^s_126 s_126
 
where V^s_124,  V^s_125,  V^s_126∈𝔽_p^2× 1 and V^w_12∈𝔽_p^2× 4 (the reason of setting this size will be clear soon).
We repeat the same coding procedure for the other 32 - 1 = 2 sets of keys, i.e., (s_134, s_135, s_136) (common keys to qualified Receiver 1 and qualified Receiver 3) and (s_234, s_235, s_236) (common to Receiver 2 and Receiver 3).

    X^2,13 =  V^w_13 W^2 +  V^s_134 s_134 +  V^s_135 s_135 +  V^s_136 s_136
    
    X^2,23 =  V^w_23 W^2 +  V^s_234 s_234 +  V^s_235 s_235 +  V^s_236 s_236
 
where V^s ∈𝔽_p^2× 1,  V^w ∈𝔽_p^2× 4. From the transmit signal X^2 = (X^2,12, X^2,13, X^2,23), each qualified receiver can obtain 4 generic desired message combinations (so the size of V^w is chosen to match this total number of combinations), from which 4 symbols of W^2 can be recovered as long as the V^w matrices are chosen in a generic manner. For example, qualified Receiver 1 can obtain ( V^w_12 W^2,  V^w_13 W^2). Security is guaranteed as long as the V^s matrices are chosen generically so that eavesdropping receivers see a sufficiently number of generic key combinations. 
To sum up, the overall rate and broadcast bandwidth achieved for all keys in the second group are

    R^2 = 3-12-12log_2 p = 4log_2 p,   β^2(R^2) = 32 2 log_2 p = 6log_2p.


  * The third group involves the keys that are known to 1 qualified receiver and 2 eavesdropping receivers. We need to further divide these keys depending on the identity of the qualified receiver. Suppose the qualified receiver is Receiver 1, i.e., we are considering the keys (s_145, s_146, s_156) such that any eavesdropping receiver knows 2 of these 3 keys (e.g., eavesdropping Receiver 4 knows s_145, s_146). From the result of secure unicast (refer to Theorem <ref>), we can achieve R = β(R) = (2-1)log_2 p = log_2 p for these 3 keys. Repeat the same procedure for (s_245, s_246, s_256) and (s_345, s_346, s_356). The overall rate and broadcast bandwidth achieved for all keys in the third group are

    R^3 = log_2 p,   β^3(R^3) = 3 log_2 p.


Finally, we combine the performance of all 3 groups (using Lemma <ref> for independent keys), so the total rate and broadcast bandwidth achieved are

    R = R^1 + R^2 + R^3 = 6 log_2 p,   β(R) = β^1(R^1) +  β^2(R^2) +  β^3(R^3) = 10log_2 p

which match the converse.




 §.§ A Secure Groupcast Instance with N=2, K=5

For all capacity results presented above, the conditional entropy converse bound in Theorem <ref> turns out to be tight. We wonder if the bound is always tight. Along this line, we find that the answer is negative. We identify a simplest setting of combinatorial secure groupcast instance to N=2 of K=5 receivers (note that all settings with smaller N,K values are settled by the converse bound in Theorem <ref>) where a strictly stronger converse is required. The setting turns out to be that in Fig. <ref> and is redrawn here with simplified notations (refer to Fig. <ref>). We have characterized its capacity and minimum broadcast bandwidth, and this result is presented in the following theorem.






For the combinatorial secure groupcast instance in Fig. <ref>, the capacity and the minimum broadcast bandwidth for capacity achieving schemes are

    C = 5/3,   β^*(C) = 10/3.



The achievable scheme is shown in Fig. <ref>. Correctness is easy to verify, e.g., qualified Receiver 1 knows a, b, c such that from the first 5 rows of the transmit signal X, he can obtain all message bits (W_1, W_2, W_3, W_4, W_5). Security is more interesting. Eavesdropping Receiver 3 learns nothing because even if b is known, all message bits in X are protected by c, a, d, e (not known to Receiver 3). Eavesdropping Receiver 4 knows c,d and after canceling c,d, he can obtain 


W_1 +  b_1, W_4 + b_2 , W_1 + b_1, W_2 + b_3 that contains b.

However, nothing is leaked because the first term is the same as the third term (highlighted in blue). 
In fact, this is the key of the design. Therefore,

    I(W; X, c, d)    (<ref>)=    I(W; X | c, d) 
       =    H(X | c,d) - H(X|W, c, d) = 9 - 9 = 0.

The situation for eavesdropping Receiver 5 is similar, where the same noise of b_2 (noise alignment) appears in the same red signal W_4+b_2 (signal alignment). Interestingly, similar alignment view has been proved useful recently in several other security and privacy primitives <cit.>.

We now discuss the rate converse. Here we give an intuitive argument for linear schemes, which guides the design of the achievable scheme, and defer the information theoretic proof to Section <ref>, which is based on the sub-modularity property of entropy functions. Consider qualified Receiver 1, who knows only a, b, c and can decode W. Then W must be fully recoverable from the key variables a, b, c in X. As a is only known to Receiver 1, it can easily be used to transmit L message bits. Then to achieve rate R, the message bits carried by b,c must be (R-1)L bits. As b and c are known to eavesdropping Receiver 3 and eavesdropping Receiver 4, respectively, the (R-1)L message bits must be protected by both b and c. Denote these (R-1)L dimensions of b as B_1. Now consider qualified Receiver 2, who knows b,d,e such that there must exist RL dimensional space of W that is covered by b, d, e. These RL dimensions must be fully covered by d,e as b is known to eavesdropping Receiver 3. As d, e have dimension L each, their overlap is (2 - R)L and each of them separately covers 1/2(R - (2-R))L = (R-1)L dimensions. Therefore, eavesdropping Receiver 4 can fully recover the (R-1)L dimensions covered only by d (and b) as d is known. This (R-1)L dimensional space of b is denoted as B_2. Symmetrically, the (R-1)L space of b (mixed with e) after e is known is denoted as B_3. Finally, we connect B_1, B_2, B_3. The desired message bits in B_2, B_3 are independent, so B_1 ∩ (B_2 ∩ B_3) = ∅. Otherwise, in B_1, we have the same b space (B_2 ∩ B_3) mixed with different desired message bits (security violated). Then

L ≥(B_1) + (B_2 ∩ B_3) ≥ (R-1)L + (2(R-1) - 1)L = (3R - 4)L, and 3R ≤ 5.

We note that the translation of this linear argument into an information theoretic proof with entropy terms is highly non-trivial.
The converse for the broadcast bandwidth is immediate, by setting 𝒬 = {1,2} and[Here we slightly abuse the notation. Note that in u_e, e denotes the index of an eavesdropping receiver and not the combinatorial key e in the secure groupcast instance.] u_e = z_3 = b in Theorem <ref>: β(C) ≥ 2C - I(a, b, c; b, d, e | b) = 2C - I(a,c;d,e | b) = 2C = 10/3.


The conditional entropy converse bound in Theorem <ref> is R ≤ 2 for the secure groupcast instance in Fig. <ref>, which is strictly weaker than the capacity 5/3. Thus the conditional entropy converse bound is not tight in general, for combinatorial secure groupcast (and  for secure groupcast).




§ GENERALIZATIONS

In this section, to show how insights generalize, we consider two extensions of the basic combinatorial secure groupcast model - the first one includes multiple messages and in the second one, keys are discrete memoryless sources.



 §.§ Secure Groupcasting Multiple Messages

We consider an elementary 3 receiver broadcast network with 3 messages (see Fig. <ref>).




We first succinctly describe the model, which generalizes that in Section <ref>. A transmitter wishes to deliver 3 messages W_1, W_2, W_12 (of size L_W_1, L_W_2, L_W_12 i.i.d. uniform bits, respectively) through broadcasting a signal X of size L_X bits such that Receiver 1 only learns W_1, W_12, Receiver 2 only learns W_2, W_12, and Receiver 3 learns nothing. Receiver 1 is equipped with key Z_1 = (S_1, S_12), Receiver 2 is equipped with key Z_2 = (S_2, S_12) and Receiver 3's key is empty. The key variables S_1, S_2, S_12 are L length extensions of uniform bits s_1, s_2, s_12 (of size L_1, L_2, L_12 bits, respectively).

    H(W_1, W_2, W_12, s_1, s_2, s_12) = H(W_1) + H(W_2) + H(W_12) + H(s_1) + H(s_2) + H(s_12).

The correctness and security constraints are as follows.

    H(W_1, W_12 | X, S_1, S_12) = o(L),  I(W_2; X, S_1, S_12) = o(L) 
           H(W_2, W_12 | X, S_2, S_12) = o(L),  I(W_1; X, S_2, S_12) = o(L) 
           I(W_1, W_2, W_12; X ) = o(L).

The rate of the messages and the broadcast bandwidth are defined as follows.

    R_1 = L_W_1/L,  R_2 = L_W_2/L,  R_12 = L_W_12/L,  β(R_1, R_2, R_12) = L_X/L.

The closure of the set of achievable rate tuples (R_1, R_2, R_12) is called the capacity region 𝒞 and the minimum broadcast bandwidth for a rate tuple (R_1, R_2, R_12) is denoted as β^*(R_1, R_2, R_12).

We present the capacity region and the minimum broadcast bandwidth for the 3 message secure groupcast problem in Fig. <ref> in the following theorem.


[Rate Region]
For the 3 message combinatorial secure groupcast problem in Fig. <ref>, the capacity region and the minimum broadcast bandwidth are

    0≤ R_1 + R_12≤ H(s_1) + H(s_12) 
           0≤ R_2 + R_12≤ H(s_2) + H(s_12) 
           0≤ R_1 ≤ H(s_1) 
           0≤ R_2 ≤ H(s_2) 
          β^*(R_1, R_2, R_12) = R_1 + R_2 + max(R_12, 2R_12 - H(s_12)).



The proof of Theorem <ref> is presented in Section <ref>.



 §.§ Discrete Memoryless Keys

The results for secure unicast and multicast with combinatorial keys generalize to discrete memoryless keys and are presented in the following theorem.


[Secure Unicast and Multicast under Discrete Memoryless Keys]
For the secure unicast problem (to the first of K receivers), the capacity and the minimum broadcast bandwidth for capacity achieving schemes are

    C = β^*(C) = min_e ∈ [2:K] H(z_1 | z_e).

For the secure multicast problem (to the first K-1 of K receivers), the capacity is 

    C = min_q∈[1:K-1] H(z_q | z_K).



The converse proof of Theorem <ref> is identical to that under the combinatorial key setting.
The achievability proof of Theorem <ref> is presented in Section <ref>. We give an intuitive overview here. 
First, consider secure unicast. Based on z_1, we wish to generate a key that is secure to any eavesdropping Receiver e ∈ [2:K]. With a discrete memoryless source, we can use random binning (whose mapping does not depend on z_2, ⋯, z_K) to obtain H(z_1 | z_e)L + o(L) secure bits over L key blocks. This step is well known and is typically referred to as privacy amplification <cit.> (refer to Lemma <ref> in Section <ref> for a technical description). Given these secure bits, the rate value of the capacity is easily achieved by one-time pad coding.  
Second, consider secure multicast, which is similar, but with an additional step of communication for omniscience <cit.> (well known as well). This is implemented as follows. We assume the key Z_K known by the eavesdropping Receiver K is globally known (e.g., the transmitter may broadcast Z_K to everyone). Next we wish to make the qualified receivers 1 to K-1 all know Z_1, ⋯, Z_K-1 (i.e., common randomness). To this end, by Slepian Wolf coding <cit.> (random binning), the transmitter needs to broadcast max_q∈[1:K-1] H(z_1, ⋯, z_K-1 | z_q, z_K)L + o(L) bits over L key blocks and note that these bits are available to the eavesdropping Receiver K as well. After this communication for omniscience step, the qualified receivers all know Z_1, ⋯, Z_K-1 so that from privacy amplification (under eavesdropped public communication), they can agree on a key of size (H(z_1, ⋯, z_K-1|z_K) - max_q∈[1:K-1]  H(z_1, ⋯, z_K-1 | z_q, z_K))L + o(L) = min_q∈[1:K-1] H(z_q | z_K) L + o(L) bits that are almost unknown to the eavesdropping Receiver K (i.e., the conditional entropy subtracts the amount of leaked communication). Equipped with these secure key bits, the desired rate can be easily achieved with one-time pad coding.


Similar to combinatorial secure multicast (see Remark <ref>), the minimum broadcast bandwidth of secure multicast under the discrete memoryless key setting is an open problem. In particular, the step of communication for omniscience is not necessary and might cause additional broadcast bandwidth (this statement is also true for the key agreement problem <cit.>).




§ RELATED WORK

The elemental problem of secure groupcast has interesting connections to several problems that have been studied in prior work and this section is devoted to the discussion of these connections. Due to space limits, we will focus on the connections to secure groupcast and leave further details to the references cited.



  §.§.§ Secret Key Agreement (Generation)
 
In the problem of key agreement <cit.>, multiple terminals observing correlated sources wish to agree on a common key through public communication and it is required that an eavesdropper learns nothing about the key from public communication. 


Secret key agreement provides a natural achievable scheme for secure groupcast, where the legitimate receivers first agree on a secret key that is not known to the eavesdropping receivers (with the help of the transmitter and the noiseless broadcast channel). Then the secret key can be used to encrypt the desired message. This idea has been used in Section <ref>. Unfortunately, secret key agreement is only understood when there is a single eavesdropper <cit.> but in secure groupcast, we have multiple eavesdroppers, each with a different view of the source. Also, for key agreement, only the maximum key rate (corresponding to the groupcast rate in secure groupcast) is known and the communication cost (corresponding to the broadcast bandwidth in secure groupcast) remains open in general <cit.>. Lastly, key agreement does not appear necessary for secure groupcast.





  §.§.§ Latent Capacity Region
 
The latent capacity region of broadcast channels <cit.> studies the implication of a rate tuple of common messages for various subsets of receivers being achievable, i.e., how can the achievable rates of certain group of receivers be exchanged for those of other groups of receivers? This interesting open problem is conceptually related to combinatorial secure groupcast, where from a rate exchange perspective, we are asking how to exchange various key variables shared by subsets of receivers to a common message for the group of desired receivers. However, latent capacity region has no security constraint and the required techniques in achievability and converse appear different.



  §.§.§ Secure Broadcasting
 
How to send messages securely over a broadcast channel has been studied along the line of Wyner's wiretap channel <cit.>, and its generalizations to confidential messages (see e.g., <cit.>), and secure broadcasting over wireless channels (see e.g., <cit.>). The enabler of secure communication in this line of work is that different receivers experience different channels, i.e., the channel itself has relative advantage to be exploited. In contrast, in secure groupcast every receiver sees the same noiseless broadcast channel and relative advantage comes from the shared keys. Notably, a recent work has studied a model (with a few users and a simple key structure) where both shared keys and discrete memoryless broadcast channels are simultaneously present <cit.>.



  §.§.§ Secure (Private) Index Coding
 
Index coding <cit.> is a canonical problem that studies how to efficiently broadcast under various side information at the receiver side with a noiseless broadcast channel. There are several variants of index coding that include security constraints (see e.g., <cit.>) with and without shared keys and with and without external eavesdroppers. The main focus of index coding works is on the side information structure and its interplay with multiple desired messages. Secure groupcast highlights the shared key structure and its influence on message rate and broadcast bandwidth.



§ PROOFS



 §.§ Proof of Theorem <ref>: Converse on R
 
Consider any qualified Receiver q ∈ [1:N] and any eavesdropping Receiver e ∈ [N+1:K]. 

    RL    (<ref>)=    H(W)  
       (<ref>)=    H(W | Z_e) 
       (<ref>)=    I(W; X, Z_q | Z_e) + o(L) 
       (<ref>)=    I(W; Z_q | X, Z_e) + o(L) 
       ≤    H(Z_q | Z_e) + o(L) 
       =    L H(z_q | z_e) + o(L).

Normalizing (<ref>) by L and letting L →∞, we have the desired converse bound R ≤ H(z_q | z_e).



 §.§ Proof of Theorem <ref>: Converse on β(R)

To simplify the notations, we set 𝒬 = {1,2,⋯, Q}⊂ [1:N], which has no loss of generality. Let us start with a useful lemma.

For any q ∈ [1:Q-1], we have

    I(X; Z_q+1 | Z_1, ⋯, Z_q, U_e, W) ≥ H(W) - I(Z_1, ⋯, Z_q; Z_q+1 | U_e) + o(L).



Proof:

    I(X; Z_q+1 | Z_1, ⋯, Z_q, U_e, W) 
       (<ref>)=    I(X, W; Z_q+1 | Z_1, ⋯, Z_q, U_e) 
       =     I(X, W,  Z_1, ⋯, Z_q; Z_q+1 | U_e)  -  I(Z_1, ⋯, Z_q; Z_q+1 | U_e) 
       ≥    I(W ; Z_q+1 | U_e, X)  -  I(Z_1, ⋯, Z_q; Z_q+1 | U_e) 
       (<ref>)=    H(W | U_e, X) -  I(Z_1, ⋯, Z_q; Z_q+1 | U_e)  + o(L) 
       (<ref>)=    H(W | U_e) -  I(Z_1, ⋯, Z_q; Z_q+1 | U_e)  + o(L) 
       (<ref>)=    H(W) - I(Z_1, ⋯, Z_q; Z_q+1 | U_e)  + o(L).



Next, we apply Lemma <ref> to decompose the term I(X; W, Z_1, ⋯, Z_Q | U_e).

    I(X; W, Z_1, ⋯, Z_Q | U_e) 
       =    I(X; W, Z_1 | U_e) + ∑_q=1^Q-1 I(X; Z_q+1 | Z_1, ⋯, Z_q, U_e, W) 
       (<ref>)≥    I(X; W | Z_1, U_e) + ∑_q=1^Q-1( H(W) - I(Z_1, ⋯, Z_q; Z_q+1 | U_e)  + o(L) )
       (<ref>)=    I(X, Z_1, U_e; W) + ∑_q=1^Q-1( H(W) - I(Z_1, ⋯, Z_q; Z_q+1 | U_e)  + o(L) ) 
       (<ref>)=    H(W) + o(L) + ∑_q=1^Q-1( H(W) - I(Z_1, ⋯, Z_q; Z_q+1 | U_e)  + o(L) ) 
       =    Q H(W) - ∑_q=1^Q-1 I(Z_1, ⋯, Z_q; Z_q+1 | U_e) + o(L) .


Finally, note that

    β(R) L    (<ref>)=     L_X log_2 p 
       ≥    H(X) 
       ≥    H(X|U_e) 
       ≥    I(X; W, Z_1, ⋯, Z_Q | U_e) .


Combining (<ref>), (<ref>), we have

    β(R) L ≥ Q H(W) - ∑_q=1^Q-1 I(Z_1, ⋯, Z_q; Z_q+1 | U_e) + o(L).

Normalizing (<ref>) by L and letting L →∞, we have the desired converse bound on β(R).



 §.§ Proof of Theorem <ref>: Secure Unicast

The converse bounds for the capacity and the broadcast bandwidth follow immediately from Theorem <ref> and Theorem <ref>, respectively. The achievable scheme is presented as follows. 

We show that rate R = min_e ∈ [2:K]∑_𝒰⊂ [1:K]:  1 ∈𝒰, e ∉𝒰 H(s_𝒰) and broadcast bandwidth β(R) = R are achievable. Set L_W = R/log_2 p and L=1. Set the field size p to be the least prime power such that p ≥ L_W + ∑_𝒰⊂ [1:K]:  1 ∈𝒰 L_𝒰.

    X    =    W + ∑_𝒰⊂ [1:K]:  1 ∈𝒰 V_𝒰 s_𝒰 = W + [ V_1  V_12 ⋯  V_1:K]_≜ V[ [   s_1;  s_12;     ⋮; s_1:K ]]

where X, W ∈𝔽_p^L_W × 1, V_𝒰∈𝔽_p^L_W × L_𝒰, s_𝒰∈𝔽_p^L_𝒰× 1 and V is chosen as a full-rank Cauchy matrix of dimension L_W ×∑_𝒰⊂ [1:K]:  1 ∈𝒰 L_𝒰 such that the element in i-th row and j-th column is given by

    V(i,j) = 1/a_i - b_j,


The correctness constraint (<ref>) is trivially satisfied. We verify the security constraint (<ref>). Consider any eavesdropping Receiver e∈ [2:K].

    I(W; X, Z_e)    (<ref>)(<ref>)=    I(W; W + ∑_𝒰⊂ [1:K]:  1 ∈𝒰 V_𝒰 s_𝒰  | z_e) 
       =    I( W; W + ∑_𝒰⊂ [1:K]:  1 ∈𝒰, e∉𝒰 V_𝒰 s_𝒰  | (s_𝒰 : e ∈𝒰) ) 
       (<ref>)(<ref>)=    I( W; W + ∑_𝒰⊂ [1:K]:  1 ∈𝒰, e∉𝒰 V_𝒰 s_𝒰) 
       (<ref>)=    H(W + ∑_𝒰⊂ [1:K]:  1 ∈𝒰, e∉𝒰 V_𝒰 s_𝒰) - H(∑_𝒰⊂ [1:K]:  1 ∈𝒰, e∉𝒰 V_𝒰 s_𝒰) 
       ≤    L_W log_2 p - L_W log_2 p = 0

where in the last step, the first term of L_W log_2 p follows from the fact that the vector has L_W symbols from 𝔽_p and the second term of -L_W log_2 p follows from the fact that the sub-matrix [ V_𝒰: 𝒰⊂ [1:K], 1 ∈𝒰, e∉𝒰] of the Cauchy matrix V has rank L_W (as it has at least L_W columns and exactly L_W rows) and s_𝒰 are i.i.d. uniform symbols.

Finally, the rate and broadcast bandwidth achieved match the converse such that the proof of Theorem <ref> is complete.



 §.§ Proof of Theorem <ref>: Secure Multicast

We first consider the capacity of combinatorial secure multicast.
The converse follows directly from Theorem <ref> and we consider the achievability.

We show that rate R = min_q∈[1:K-1]∑_𝒰⊂ [1:K-1]:q∈𝒰 H(s_𝒰) is achievable. 
Set L_W = R/log_2 p and L=1. Set the field size p to be the least prime power such that p ≥ L_W + ∑_𝒰⊂ [1:K-1] L_𝒰. The transmit signal has 2^K-1-1 row blocks, each corresponding to a subset of [1:K-1].

    X    =    [X_1; X_2; ⋯; X_𝒰; ⋯; X_1:K-1] 
    
    X_𝒰   =    V_𝒰W + s_𝒰, ∀𝒰⊂ [1:K-1]

where X_𝒰∈𝔽_p^L_𝒰× 1,  V_𝒰∈𝔽_p^L_𝒰× L_W, W∈𝔽_p^L_W× 1, s_𝒰∈𝔽_p^L_𝒰×1 and the precoding matrices V_𝒰 are sub-matrices of a Cauchy matrix, set as follows.

    V   =    [ V_1;  V_2; ⋯;  V_𝒰; ⋯;  V_1:K-1]_∑_𝒰⊂ [1:K-1] L_𝒰× L_W,
     V(i,j)    =   1/a_i - b_j,


Security is guaranteed because the keys known to the eavesdropping Receiver K do not appear in the transmit signal and the s_𝒰 variables are independent. Correctness constraint is satisfied because each qualified Receiver q∈[1:K-1] can recover at least L_W linear combinations of the message symbols W, i.e., ( V_𝒰W : q ∈𝒰⊂[1:K-1]), from which W can be decoded as any sub-matrix of a full-rank Cauchy matrix has full rank.

Next we proceed to the minimum broadcast bandwidth of combinatorial secure multicast. The broadcast bandwidth achieved by the scheme above is β(C) = ∑_𝒰⊂ [1:K-1] H(s_𝒰), which is optimal when H(z_1|z_K) = ⋯ = H(z_K-1|z_K). This follows from Theorem <ref>, where we set 𝒬 = [1:K-1] and u_e = z_K.

    β(C)    ≥    (K-1) C - (∑_q=1^K-1 H(z_q | z_K) - H(z_1, ⋯, z_K-1 | z_K))
       =    H(z_1, ⋯, z_K-1 | z_K) = ∑_𝒰⊂ [1:K-1] H(s_𝒰)

where (<ref>) follows from the fact that C = H(z_1 | z_K) = ⋯ = H(z_K-1 | z_K). The proof when K=4 is more involved as we need to improve the above achievable scheme, and is presented next.



  §.§.§ β^*(C) when K = 4
 
First, we consider the converse. Note that in this case, C = H(z_1|z_4). From (<ref>), we need two converse bounds. 
The first one is obtained by setting 𝒬 = {1,2}, u_e = z_4 in Theorem <ref>,

    β(C)    ≥    2C - I(z_1; z_2|z_4) = 2H(z_1|z_4) - I(z_1; z_2|z_4)  
       =    2H(s_1) + 2H(s_12) + 2H(s_13) + 2H(s_123) - (H(s_12) + H(s_123))
       =    2H(s_1) + H(s_12) + 2H(s_13) + H(s_123).

The second one is obtained by setting 𝒬 = {1,2,3}, u_e = z_4 in Theorem <ref>,

    β(C)    ≥    3C - (I(z_1; z_2|z_4) + I(z_1, z_2; z_3| z_4)) 
       =    3H(s_1) + 3H(s_12) + 3H(s_13) + 3H(s_123) - (H(s_12) +  H(s_13) + H(s_23) + 2H(s_123)) 
       =    3H(s_1) + 2H(s_12) + 2H(s_13) - H(s_23) + H(s_123).


Second, we consider the achievability, where we need to adjust the size of the keys used in (<ref>) depending on the key configuration.
We present the scheme that achieves rate R = H(z_1|z_4) = H(s_1) + H(s_12) + H(s_13) + H(s_123). 
Set L_W = R/log_2 p and L=1. 

We have 3 cases depending on the relationship between H(s_23), H(s_1)+H(s_13), H(s_1)+H(s_12).  
For each case, set the field size p to be the least prime power such that p ≥ L_X + L_W. The transmit signal has 7 row blocks and the 4 blocks X_1, X_12, X_13, X_123 (corresponding to the keys known to Receiver 1) are the same for all 3 cases, where all key symbols are used.

    X    =    [X_1; X_2; X_3; X_12; X_13; X_23; X_123] 
    
    X_1    =    V_1 W + s_1, X_12 =  V_12 W + s_12, X_13 =  V_13 W + s_13, X_123 =  V_123 W + s_123

where the sizes of the matrices and vectors above are the same as before (see (<ref>)).
Note that now Receiver 1 can achieve rate R and in the remaining proof, we only need to consider Receiver 2 and Receiver 3.
The remaining blocks X_2, X_3, X_23 are designed for each case separately, where not all the key symbols may be used. Note that H(s_12) ≤ H(s_13), i.e., L_12≤ L_13.


   Case 1. H(s_23) ≥ H(s_1) + H(s_13).

    X_2 = (), X_3 = (), X_23 =  V_23^[1] W + s_23^[1]

where s_23^[1]∈𝔽_p^(L_1+L_13) × 1 is comprised of the first L_1+L_13 symbols from s_23 (which has more symbols, i.e., L_23≥ L_1+L_13) and V_23^[1]∈𝔽_p^(L_1+L_13)× L_W. We verify that the number of linear combinations of the message decodable by Receiver 2 and Receiver 3 is no less than L_W.

    |X_12| + |X_23| + |X_123| = L_12 + (L_1 + L_13) + L_123 = L_W, 
     |X_13| + |X_23| + |X_123| = L_13 + (L_1 + L_13) + L_123≥ L_W.

The transmit signal size is

    L_X = |X_1| + |X_12| + |X_13| + |X_123| + |X_23| = L_1 + L_12 + L_13 + L_123 + (L_1 + L_13)
 
which matches the converse bound (<ref>) for broadcast bandwidth. The other cases are similar.

   Case 2. H(s_1) + H(s_12) ≤ H(s_23) ≤ H(s_1) + H(s_13).

    X_2 =  V_2^[2] W + s_2^[2], X_3 = (), X_23 =  V_23 W + s_23

where s_2^[2]∈𝔽_p^(L_1+L_13-L_23) × 1 is comprised of the first L_1+L_13 - L_23 symbols from s_2 (which has more symbols, i.e., L_2≥ L_1+L_13 - L_23 because H(z_1|z_4) ≤ H(z_2|z_4)) and V_2^[2]∈𝔽_p^(L_1+L_13 - L_23)× L_W. We verify that the number of linear combinations of the message decodable by Receiver 2 and Receiver 3 is no less than L_W.

    |X_2| + |X_12| + |X_23| + |X_123| = (L_1 + L_13 - L_23) + L_12 + L_23 + L_123
                              = L_1 + L_12 + L_13 + L_123 = L_W, 
           |X_13| + |X_23| + |X_123| = L_13 + L_23 + L_123≥ L_W.

The transmit signal size is

    L_X    =    |X_1| + |X_12| + |X_13| + |X_123| + |X_2| + |X_23| 
       =    L_1 + L_12 + L_13 + L_123 + (L_1 + L_13 - L_23) + L_23
 
which matches the converse bound (<ref>) for broadcast bandwidth.

   Case 3. H(s_23) ≤ H(s_1) + H(s_12).

    X_2 =  V_2^[3] W + s_2^[3], X_3 =  V_3^[3] W + s_3^[3], X_23 =  V_23 W + s_23
           s_2^[3]∈𝔽_p^(L_1+L_13-L_23) × 1,  V_2^[3]∈𝔽_p^(L_1+L_13 - L_23)× L_W
           s_3^[3]∈𝔽_p^(L_1+L_12-L_23) × 1,  V_3^[3]∈𝔽_p^(L_1+L_12 - L_23)× L_W

where L_2≥ L_1+L_13 - L_23 and L_3 ≥ L_1+L_12-L_23 because H(z_1|z_4) ≤min( H(z_2|z_4), H(z_3|z_4)). We verify that the number of linear combinations of the message decodable by Receiver 2 and Receiver 3 is no less than L_W.

    |X_2| + |X_12| + |X_23| + |X_123| = (L_1 + L_13 - L_23) + L_12 + L_23 + L_123
                              = L_1 + L_12 + L_13 + L_123 = L_W, 
           |X_3| + |X_13| + |X_23| + |X_123| = (L_1 + L_12 - L_23) + L_13 + L_23 + L_123
                              = L_1 + L_12 + L_13 + L_123 = L_W.

The transmit signal size is

    L_X    =    |X_1| + |X_12| + |X_13| + |X_123| + |X_2| + |X_3| + |X_23| 
       =    L_1 + L_12 + L_13 + L_123 + (L_1 + L_13 - L_23) + (L_1 + L_12 - L_23) + L_23
 
which matches the converse bound (<ref>) for broadcast bandwidth.


After the sizes are specified, the remaining proof is the same as that presented above, where we set V as a full-rank Cauchy matrix and the correctness and security constraints are satisfied. The proof of β^*(C) when K=4 is thus complete.





 §.§ Proof of Theorem <ref>: The N=2, K=4 Case

The converse of rate and broadcast bandwidth follows from Theorem <ref> and Theorem <ref>, and we present the achievable scheme now. Set p=2 (i.e., binary field) and L=1 (i.e., one key block). The idea is to decompose every instance into multiple component sub-networks, where the basic components are listed in the following figure.




Next, we divide the problem instance into multiple cases, where each case requires a different decomposition. As s_12 is only known to qualified Receiver 1 and Receiver 2, we can easily use s_12 to achieve rate H(s_12) with broadcast bandwidth H(s_12), by one-time pad. 
Without loss of generality, we assume H(s_1)≤ H(s_2), H(s_124) ≤ H(s_123). As such, for all cases we invoke Component 1 H(s_124) times (i.e., use H(s_124) bits of s_123, s_124) and Component 2 H(s_1) times (use H(s_1) bits of s_1, s_2). We write this succinctly as

    H(s_124) × + H(s_1) ×.

We proceed next depending on the key configurations. Specifically, all cases are divided as follows.


   Case 1. H(s_2) - H(s_1) ≥min(H(s_13), H(s_14)). 
We further invoke

    min(H(s_13), H(s_14)) ×

where we can employ the scheme in Component 3 a number of min(H(s_13), H(s_14)) times because we have H(s_2) - H(s_1) bits left of s_2 and H(s_2) - H(s_1) ≥min(H(s_13), H(s_14)).
The remaining steps need further division.
Case 1.1. H(s_14) ≤ H(s_13). No further action is needed. Tracing back, we have invoked one-time pad of s_12, (<ref>), and (<ref>). Therefore we have achieved 

    R = H(s_12) + H(s_124) + H(s_1) + H(s_14),  β(R) = H(s_12) + H(s_124) + 2H(s_1) + 2H(s_14)

which match the converse (<ref>) and (<ref>). Note that the converse bounds are minimum or maximum of several terms and it suffices to show the achievability of one term.
Case 1.2. H(s_14) ≥ H(s_13). We need to further consider the following cases.
Case 1.2.1. min(H(s_14) - H(s_13), H(s_123) - H(s_124), H(s_24)) = H(s_14) - H(s_13). We further invoke

    (H(s_14) - H(s_13)) ×

and the description of the scheme is complete for this case. We trace back and find that

    R = H(s_12) + H(s_124) + H(s_1) + H(s_14),  β(R) = H(s_12) + H(s_124) + 2H(s_1) + 2H(s_14)

are achieved and they are optimal as the formulas match the converse.
Case 1.2.2. min(H(s_14) - H(s_13), H(s_123) - H(s_124), H(s_24)) =  H(s_123) - H(s_124). We further invoke

    (H(s_123) - H(s_124)) ×

and the description of the scheme is complete for this case. We trace back and find that

    R    =    H(s_12) + H(s_1) + H(s_13) + H(s_123), 
    β(R)    =    H(s_12) - H(s_124) + 2H(s_1) + 2H(s_13) + 2 H(s_123)

are achieved and they are optimal as the formulas match the converse.
Case 1.2.3. min(H(s_14) - H(s_13), H(s_123) - H(s_124), H(s_24)) = H(s_24). We further invoke 

    H(s_24) ×

and need to consider the following cases. 


       Case 1.2.3.1. min(H(s_2) - H(s_1) - H(s_13), H(s_14) - H(s_13) - H(s_24), H(s_123) - H(s_124) - H(s_24) ) = H(s_2) - H(s_1) - H(s_13). We further invoke

    ( H(s_2) - H(s_1) - H(s_13) ) ×
           R = H(s_12) + H(s_124) + H(s_24) + H(s_2), 
          β(R) = H(s_12) + H(s_124) + 2H(s_24) + 2H(s_2).


       Case 1.2.3.2. min(H(s_2) - H(s_1) - H(s_13), H(s_14) - H(s_13) - H(s_24), H(s_123) - H(s_124) - H(s_24) ) = H(s_14) - H(s_13) - H(s_24). We further invoke

    ( H(s_14) - H(s_13) - H(s_24) ) ×
           R = H(s_12) + H(s_124) + H(s_1) +  H(s_14), 
          β(R) = H(s_12) + H(s_124) + 2H(s_1) +  2H(s_14).


       Case 1.2.3.3. min(H(s_2) - H(s_1) - H(s_13), H(s_14) - H(s_13) - H(s_24), H(s_123) - H(s_124) - H(s_24) ) = H(s_123) - H(s_124) - H(s_24). 
We further invoke

    ( H(s_123) - H(s_124) - H(s_24) ) ×
           R = H(s_12) + H(s_1) +H(s_13) + H(s_123), 
          β(R) = H(s_12) - H(s_124) + 2H(s_1) +2H(s_13) + 2H(s_123).



   Case 2. H(s_2) - H(s_1) ≤min(H(s_13), H(s_14)). We further invoke

    (H(s_2) - H(s_1)) ×

and consider the following cases.
Case 2.1. min(H(s_24), H(s_14) - H(s_2) + H(s_1), H(s_123) - H(s_124)) = H(s_24). We further invoke

    H(s_24)  ×

and the description of the scheme is complete for this case. We trace back and find that

    R    =    H(s_12) + H(s_124) + H(s_2) + H(s_24), 
    β(R)    =     H(s_12) + H(s_124) + 2H(s_2) + 2H(s_24)

are achieved and they are optimal as the formulas match the converse.
Case 2.2. min(H(s_24), H(s_14) - H(s_2) + H(s_1), H(s_123) - H(s_124)) = H(s_14) - H(s_2) + H(s_1). We further invoke

    ( H(s_14) - H(s_2) + H(s_1))  ×

and the description of the scheme is complete for this case. We trace back and find that

    R    =    H(s_12) + H(s_124)  + H(s_14) + H(s_1), 
    β(R)    =     H(s_12) + H(s_124) + 2H(s_14) + 2H(s_1)

are achieved and they are optimal as the formulas match the converse.
Case 2.3. min(H(s_24), H(s_14) - H(s_2) + H(s_1), H(s_123) - H(s_124)) = H(s_123) - H(s_124). We further invoke

    ( H(s_123) - H(s_124) )  ×

and need to consider the following cases. 
Case 2.3.1. min(H(s_14) - H(s_2) + H(s_1) - H(s_123) + H(s_124), H(s_13) - H(s_2) + H(s_1),  H(s_24) - H(s_123) + H(s_124), H(s_23)) = H(s_14) - H(s_2) + H(s_1) - H(s_123) + H(s_124). We further invoke

    ( H(s_14) - H(s_2) + H(s_1) - H(s_123) + H(s_124) ) ×
           R = H(s_12) + H(s_124) + H(s_14) + H(s_1), 
          β(R) = H(s_12) + H(s_124) +  2H(s_14) +  2H(s_1).

Case 2.3.2. min(H(s_14) - H(s_2) + H(s_1) - H(s_123) + H(s_124), H(s_13) - H(s_2) + H(s_1),  H(s_24) - H(s_123) + H(s_124), H(s_23)) = H(s_13) - H(s_2) + H(s_1). We further invoke

    ( H(s_13) - H(s_2) + H(s_1) ) ×
           R = H(s_12) + H(s_123) + H(s_13) + H(s_1),
          β(R) = H(s_12) - H(s_124) +  2 H(s_123) + 2H(s_13) + 2H(s_1).

Case 2.3.3. min(H(s_14) - H(s_2) + H(s_1) - H(s_123) + H(s_124), H(s_13) - H(s_2) + H(s_1),  H(s_24) - H(s_123) + H(s_124), H(s_23)) = H(s_24) - H(s_123) + H(s_124). We further invoke

    ( H(s_24) - H(s_123) + H(s_124) ) ×
           R = H(s_12) + H(s_124) + H(s_2) + H(s_24)
          β(R) = H(s_12) + H(s_124) +  2 H(s_2) + 2H(s_24)

Case 2.3.4. min(H(s_14) - H(s_2) + H(s_1) - H(s_123) + H(s_124), H(s_13) - H(s_2) + H(s_1),  H(s_24) - H(s_123) + H(s_124), H(s_23)) = H(s_23). We further invoke

    H(s_23) ×
           R = H(s_12) + H(s_2) + H(s_123) + H(s_23),
          β(R) = H(s_12) - H(s_124) +  2 H(s_2) + 2H(s_123) + 2H(s_23).





 §.§ Proof of Theorem <ref>: The Symmetric Setting

The rate converse follows from Theorem <ref>, where among u-keys, any qualified Receiver q ∈ [1:N] knows K-2u-1 keys that are not known to any eavesdropping Receiver e ∈ [N+1:K] because we may pick any u-1 receivers from any K-2 receivers other than Receiver q and Receiver e to form a u-key (note that Receiver q must be included). The broadcast bandwidth converse follows from Theorem <ref>, where we set 𝒬 = [1:N], u_e = z_K and obtain β(C) ≥ H(z_1,⋯,z_N|z_K). Among u-keys, we have K-1u - K-N-1u keys in the term H(z_1,⋯,z_N|z_K) because we pick u-keys from receivers 1 to K-1 and need to remove the ones that are only known to receivers N+1 to K-1. To sum up for the converse part, we have proved that

    C ≤∑_u=1^K K-2u-1L^[u]log_2 p,   β^*(C) ≥∑_u=1^K ( K-1u - K-N-1u) L^[u]log_2 p.

We next show that the above rate and broadcast bandwidth are achievable. Similar to Example <ref>, we consider u-keys separately for different u values and then combine the decomposed schemes using Lemma <ref>. Consider a fixed value of u ∈ [1:K] and further consider the u-keys that are known to i qualified receivers and u-i eavesdropping receivers, where i ∈ [1:u].

We focus on one specific set of i qualified receivers, say receivers from the set ℐ where ℐ⊂ [1:N], |ℐ| = i. That is, we consider the keys (s_𝒰: [1:N] ∩𝒰 = ℐ, |𝒰| = u) and there are K-Nu-i such u-keys. Further these K-Nu-i keys are known to all qualified receivers from ℐ, and each eavesdropping receiver knows K-N-1u-i-1 keys from these keys. Invoking generic linear codes similar to Example <ref>, we can securely send (K-Nu-i - K-N-1u-i-1) L^[u] = K-N-1u-i L^[u] generic message symbols to receivers from ℐ by transmitting K-N-1u-i L^[u] symbols.





    X^[u],ℐ =  V^w_ℐ W^[u] + ∑_𝒰: [1:N] ∩𝒰 = ℐ, |𝒰| = u V^s_𝒰 s_𝒰

where V^w_ℐ is a K-N-1u-i L^[u]×N-1i-1K-N-1u-i L^[u] matrix over 𝔽_p and V^s_𝒰 is a K-N-1u-i L^[u]× L^[u] matrix over 𝔽_p. Repeat the same coding procedure for all sets ℐ such that ℐ⊂ [1:N] and |ℐ| = i. Consider the row stack of all the V^w_ℐ matrices appeared (denoted as V^[u], w) and the column stack of all the V^s_𝒰 matrices appeared (denoted as V^[u], s). Set V^[u], w and V^[u], s as two Cauchy matrices from a sufficiently large field. The exact field size required and detailed analysis of security and correctness are similar to those in Theorem <ref> and Theorem <ref> and thus are not repeated here. Note that when we consider all sets of i qualified receivers, overall there are Ni choices and any particular qualified receiver is picked N-1i-1 times, so the size of W^[u] is set as  N-1i-1K-N-1u-i L^[u]. Security and correctness hold by the generic property of Cauchy matrices over large fields.

Counting all sets of i qualified receivers and all u-keys, where i ∈ [1:u], u ∈ [1:K], we calculate the overall performance as follows. 

    R    =   ∑_u=1^K ∑_i = 1^u H(W^[u]) = ∑_u=1^K ∑_i = 1^u N-1i-1K-N-1u-i L^[u]log_2 p 
       =   ∑_u=1^K ∑_j = 0^u-1N-1jK-N-1u-1-j L^[u]log_2 p = ∑_u=1^K K-2u-1 L^[u]log_2 p

and 

    β(R)    =   ∑_u=1^K ∑_i = 1^u NiK-N-1u-i L^[u]log_2 p 
       =   ∑_u=1^K ( ∑_i = 0^u NiK-N-1u-i - N0K-N-1u) L^[u]log_2 p 
       =   ∑_u=1^K ( K-1u - K-N-1u) L^[u]log_2 p

where both rate and broadcast bandwidth match the converse bounds.
Note that we have used decompositions of schemes with independent u-keys (refer to Lemma <ref>) and for each u, we invoke the generic coding scheme (<ref>) where a specific finite field 𝔽_p is used. To ensure the overall scheme operates over the same field, we will use the maximum field size p required for all component schemes and the Cauchy matrix based scheme in (<ref>) works for any field size that is larger than the minimum required. The proof of Theorem <ref> is thus complete.



 §.§ Proof of Theorem <ref>: Rate Converse for The N=2, K=5 Instance

The rate converse is split into two lemmas. Before presenting the lemmas, we first summarize the entropy identities from the problem description.

    H(a,b,c,d,e) = H(a) + H(b) + H(c) + H(d) + H(e) 
           H(a) = H(b) = H(c) = H(d) = H(e) = L 
           H(W|X, a, b, c) = H(W| X, b, d, e) = o(L) 
           I(W; X, b) = I(W; X, c, d) = I(W; X, c, e) = o(L).


For the secure groupcast instance in Fig. <ref>, we have

    H(d, e | W, X, b) ≤ 2L - H(W) + o(L).



Proof:

    H(d, e | W, X, b)    =    H(d, e | X, b) - I(d, e; W | X, b) 
       (<ref>)≤    2L - H(W | X, b) + H(W| X, b, d, e) 
       (<ref>)(<ref>)=    2L - H(W) + o(L).




For the secure groupcast instance in Fig. <ref>, we have

    H(d, e | W, X, b) ≥ 2H(W) - 3L + o(L).



Proof: Consider eavesdropping Receiver 4 such that X, c, d shall not reveal anything about W.

    H(W,X,c,d)    (<ref>)=    H(W) + H(X, c, d)  + o(L) 
       ≥    H(W) + H(X, b, c, d) - H(b) + o(L).


Symmetrically, consider eavesdropping Receiver 5 such that X, c, e shall not reveal anything about W.

    H(W,X,c,e)    (<ref>)=    H(W) + H(X, c, e)  + o(L) 
       ≥    H(W) + H(X, b, c, e) - H(b) + o(L).


Adding (<ref>) and (<ref>) and applying sub-modularity, we have

    H(W,X,c,d) + H(W,X,c,e) 
       ≥    2H(W) -2H(b) + H(X, b, c, d, e) + H(X, b, c) + o(L)
       (<ref>)≥    2 H(W) - 2H(b) + H(W, X, b, c, d, e) + H(X, a, b, c) - H(a) + o(L)
       (<ref>)≥    2 H(W) - 2H(b) + H(W, X, c, d) + H(W, X, a, b, c) - H(a) + o(L).

Rearranging terms above and applying (<ref>), we have

    2H(W) - 3L + o(L)   ≤    H(W, X, c, e) - H(W, X, a, b, c)  
       ≤    H(W, X, a, b, c, d, e) - H(W, X, a, b, c) 
       =    H(d, e | W, X, a, b, c) 
       ≤    H(d, e | W, X, b).



Finally, combining Lemma <ref> and Lemma <ref>, we have

    2H(W) - 3L + o(L) ≤ 2L - H(W) + o(L) 
       ⇒    R = H(W)/L≤5/3 + o(L)/L

and letting L →∞ produces the desired bound R ≤ 5/3.



 §.§ Proof of Theorem <ref>: Multiple Messages

Let us start with the converse proof, which is a generalization of that in Theorem <ref> and Theorem <ref>. Consider (<ref>) and (<ref>) follows from symmetry.

    (R_1 + R_12) L    =    H(W_1) + H(W_12) 
    
       (<ref>)=    I(W_1, W_12; X, S_1, S_12) + o(L) 
       (<ref>)=    I(W_1, W_12; S_1, S_12 | X) + o(L) 
       ≤    H(S_1, S_12) +o(L) = (H(s_1) + H(s_12)) L + o(L).

Consider (<ref>) and (<ref>) follows from symmetry.

    R_1 L    =    H(W_1) (<ref>)= I(W_1; X, S_1, S_12) + o(L) 
       (<ref>)=    I(W_1; S_1 | X, S_12) + o(L) 
       ≤    H(S_1) +o(L) = H(s_1) L + o(L).

Consider (<ref>).

    β(R_1, R_2, R_12) L    ≥    H(X) ≥ H(X | S_1, S_2, S_12) 
       ≥    I(X; W_1, W_2, W_12 | S_1, S_2, S_12) 
       (<ref>)(<ref>)=    H(W_1, W_2, W_12|S_1, S_2, S_12) + o(L) 
       (<ref>)=    H(W_1) + H(W_2) + H(W_12) + o(L) 
       =    (R_1 + R_2 + R_12) L + o(L), 
    β(R_1, R_2, R_12)    ≥    I(X; W_1, W_2, W_12, Z_1, Z_2) 
       =    I(X; W_1, W_12, Z_1) + I(X; W_2, Z_2 | W_1, W_2, W_12, Z_1) 
       ≥    I(X; W_1, W_12 | Z_1) + I(X; Z_2 | W_1,W_2, W_12, Z_1) 
       (<ref>)=    I(X, Z_1; W_1, W_12) + I(X, W_2, W_12; Z_2 | W_1, Z_1)
       (<ref>)=    H(W_1, W_12) + I(X, W_2, W_12, Z_1; Z_2 | W_1) 
          -I(Z_1; Z_2 | W_1)  + o(L)
       (<ref>)≥    H(W_1, W_12) + I(W_2, W_12; Z_2 | X, W_1) -I(Z_1; Z_2) + o(L)
       (<ref>)=    H(W_1, W_12) + H(W_2, W_12 | X, W_1) -I(Z_1; Z_2) + o(L)
       (<ref>)=    H(W_1, W_12) + H(W_2, W_12 | W_1) -I(Z_1; Z_2) + o(L)
       (<ref>)=    (R_1 + R_12 + R_2 + R_12 - H(s_12))L + o(L).

Next, we consider the achievability. Consider any rational rate tuple (R_1, R_2, R_12) ∈𝒞, i.e., (R_1, R_2, R_12) satisfies (<ref>) - (<ref>). Without loss of generality, assume R_1, R_2, R_12 are integers (for rationals, we may consider blocks over the least common multiple of the denominators so that the number of bits becomes integers). We operate over the binary field and consider L=1 block. The transmit signal is designed as follows. Denote by W^[a_1:a_2] the a_1-th to a_2-th bits in the vector W. We have two cases.


   Case 1. R_12≤ H(s_12).

    X = (
    W_1 + s_1^[1:R_1]; 
    W_2 + s_2^[1:R_2]; 
    W_12 + s_12^[1: R_12]
    ).

The broadcast bandwidth achieved is β(R_1, R_2, R_12) = R_1 + R_2 + R_12.

   Case 2. R_12 > H(s_12).

    X = (
    [ W_1 + s_1^[1:R_1]; 
    W_2 + s_2^[1:R_2]; 
    W_12^[1: H(s_12)] + s_12;          W_12^[H(s_12)+1:R_12] + s_1^[R_1+1 : R_1+R_12- H(s_12)];          W_12^[H(s_12)+1:R_12] + s_2^[R_2+1 : R_2+R_12- H(s_12)];                                                                  ]).

Note that as (R_1, R_2, R_12) satisfies (<ref>) - (<ref>), the key bits in the above scheme exist. The broadcast bandwidth achieved is β(R_1, R_2, R_12) = R_1 + R_2 + 2R_12 - H(s_12).

Thus any rational rate tuple in the capacity region is achievable and as rational tuples are dense over the reals, the proof of Theorem <ref> is complete.



 §.§ Proof of Theorem <ref>: Achievability under Discrete Memoryless Keys

Before presenting the achievability proof for Theorem <ref>, we cite a lemma on privacy amplification[Lemma <ref> on secret key extraction suffices for our purposes over long key block lengths. Stronger non-asymptotic results and more efficient constructions of the random mappings are available in the literature (see e.g., <cit.>).], which encapsulates most technicalities of the achievability proof.

(Lemma 5.18 in <cit.>)
Consider random variables Z_c, Z_e, X_e (with finite cardinality) such that Z_c, Z_e are L length extensions of z_c, z_e and L_X_e denotes the number of bits in X_e. Then there exists a random mapping (independent of Z_e, X_e) from Z_c to a uniform random variable Z with L_Z bits such that

    L_Z = H(z_c | z_e)L - L_X_e + o(L), 
           I(Z; Z_e, X_e) = o(L).



In Lemma <ref>, we may interpret Z as the secret key to be generated from a known variable Z_c such that Z is almost independent of an eavesdropped variable Z_e (that has certain joint distribution with Z_c) and a prior knowledge variable X_e (that is arbitrarily correlated with Z_c, Z_e). The secret key size turns out to be given by the conditional entropy value minus the leaked prior knowledge.

Consider secure unicast first, whose achievability proof follows immediately from Lemma <ref>. Set Z_c = Z_1, i.e., the key for qualified Receiver 1, Z_e as the key for eavesdropping Receiver e ∈ [2:K], and X_e = (). From Lemma <ref>, we know that Receiver 1 can generate a key Z that is almost independent from any eavesdropping receiver. Note that the random mapping used in Lemma <ref> does not depend on the eavesdropped variable Z_e so that the secret key Z generated is simultaneously independent of any eavesdropped variable as long as we pick the key length to be L_Z = min_e ∈ [2:K] H(z_1|z_e) L + o(L).
We use the key to send the desired message through one-time pad, i.e., X = W + Z where the length of W is the same as the length of Z. Correctness and security are easy to verify (as Z is almost independent of Z_e, see (<ref>)). The rate and broadcast bandwidth achieved are R = β(R) = min_e∈[2:K] H(z_1|z_e) as L →∞.






Then consider secure multicast. In Lemma <ref>, we set Z_c = (Z_1, Z_2, ⋯, Z_K-1), Z_e = Z_K, and X_e as the random bin index of (Z_1, Z_2, ⋯, Z_K-1) of length max_q∈[1:K-1]H(z_1,⋯,z_K-1 | z_q, z_K)L + o(L). The key Z is generated from Z_c and has length as specified in Lemma <ref>. The transmit signal sent by the transmitter is X = (Z_K, X_e, W+Z). From Z_K, X_e, every qualified Receiver q, q ∈ [1:K-1] can recover Z_c (by Slepian Wolf coding as the overall information seen by Receiver q, i.e., Z_K, X_e, Z_q has entropy whose value is at least the joint entropy, H(Z_1, ⋯, Z_K)) and then generate Z with the same random mapping used by the transmitter. After extracting the common key Z, W can be decoded with vanishing error by every qualified receiver. Security is guaranteed by Lemma <ref> as Z is almost independent of the information available to the eavesdropping Receiver K, i.e., Z_K, X_e. The rate achieved is R = H(z_1, ⋯, z_K-1 | z_K) - max_q∈[1:K-1]H(z_1,⋯,z_K-1 | z_q, z_K) = min_q∈[1:K-1] H(z_q|z_K) as L →∞.



§ CONCLUSION

We introduce the problem of secure groupcast, where a transmitter wishes to securely communicate with a group of selected receivers while ensuring the other illegitimate receivers are fully ignorant of the desired communication, through noiseless broadcasting and correlated keys.

The communication efficiency of secure groupcast is measured by the message rate (number of message bits securely groupcast) and the broadcast bandwidth resource used (number of bits in the transmit signal). The main emphasis is placed on the most elementary setting of combinatorial keys and one common message, and limited extensions are also explored. Complete answers are obtained for certain preliminary cases, e.g., one legitimate receiver or one eavesdropping receiver, symmetric cases, while other cases remain unsolved. Interesting insights emerge out of this study, e.g., the necessity of decomposition and both structured and generic coding, the quest for tighter general converse bounds, and the potential of alignment view of the correlated key, message and transmit signal spaces. We find secure groupcast to be an interesting and challenging information theoretic security primitive with many open questions, and this work is a first step towards understanding coding opportunities for group communications under multiple correlated eavesdroppers.

<>IEEEtran

