Bounds on the Communication Rate Needed to Achieve SK Capacity in the Hypergraphical Source Model Manuj Mukherjee† Chung Chan‡ Navin Kashyap† Qiaoqiao Zhou‡ 6 Abstract—In the multiterminal source model of Csisza´r and upper bounds on RSK. The SK generation protocol in [1] 1 Narayan,thecommunicationcomplexity,RSK,forsecretkey(SK) goes through omniscience, i.e., all the terminals recovering 0 generation is the minimum rate of communication required to the entire information of all the other terminals. Thus, the an 2 RoafomcCrhOnite,ihsvwceeihehSniycKcpheec.irasIgnprtahatchpeiihtmsyi.cpianAalipnmseorouubmwrvceierodaumetseroiuvodpefeplca,eorwbmebhmtoitceuuhrnnudiiscpatapotiesoRrpnSbeKcroieuaiqsnludgiinirvtseoetdnaRnfbSocKyre mvailnIindimtuhupimspperarapbteeoru,ownfdecoocnomnmRsiuSdnKei.rcaatsiopnecfioalrcoamsenoisfctiheencme,ulRtitCeOrm, iisnaal J ofthemultiterminalsourcemodel.Theupperboundisbasedon source model, namely the hypergraphical source model stud- 8 theideaof fractional removal of hyperedges. Itisfurthershown iedpreviouslyin[5]and[3].Thehypergraphicalsourcemodel 2 that this upperbound can be computed in polynomial time. We conjecturethat our upperboundistight. Forthespecial case of is inspired by the coded co-operative data exchange (CCDE) ] a graphical source model, we also give an explicit lower bound problemintroducedin[6],andhasbeenstudiedinthecontext T on R . Thisbound,however, isnot tight,as demonstrated bya of the “one-shot”SK generationproblem,in [7]–[9]. One can SK .I counterexample. also viewthe hypergraphicalsourcemodelas a generalization s of the pairwise independentnetwork (PIN) modelof [10] and c I. INTRODUCTION [ [11]. The main contribution of this paper is an upper bound The problem of secret key (SK) generation for multiple onR forthehypergraphicalsourcemodel.Theproofofthis 2 terminals observing i.i.d. sequences of correlated random SK v upperboundisbasedontheideaofdecrementalSKagreement variables was first studied by Csisza´r and Narayan in [1]. 7 studiedin[12].Theideaistokeeponremoving“randomness” Theterminalsareallowedtocommunicateinteractivelyovera 7 from the hyperedges as long as the SK capacity does not 3 public noiseless channel. After the communication the termi- decrease,andthen use the R of the resultinghypergraphas CO 5 nals must agree upon an SK, secured from any eavesdropper anupperboundonR oftheoriginalhypergraph.Wefurther 0 having access to the public channel. The SK capacity, i.e., SK show that the upper bound on R thus derived is at least as . SK 1 the maximum rate of secret key that can be generated was good as R . Computation of this upper bound requires the 0 derived in [1]. A quantity of interest in the SK generation CO solutionofalinearprogram,whoseseparationoracleperforms 6 problemis the communicationcomplexity1, R , which is the 1 SK submodular function minimization. As a result the bound is minimum rate of communication required to generate an SK : computable in polynomial time. In fact, for the special case v of maximum rate. when the underlying hypergraph of the source model is a Xi Tyagiin [2, Theorem3] has given a complete characteriza- graph, the upper bound reduces to a simple expression. We tion of R for the case of two terminals. Tyagi’s arguments r SK believe that the upper bound is actually tight. Unfortunately, a have been extended by [3, Theorem 2] to give a lower bound wedonothaveaproofofthisyet,andthereforewestateitas onR forthegeneralmultiterminalsetting.Thislowerbound SK a conjecture. We also give a simple expression for the lower was computed and was shown to be tight for a special class bound on R derived in [3, Theorem 2], for sources defined SK of sources in [3, Theorem 6]. However, computing this lower on graphs. Using this expression we are able to construct an bound for a general multiterminal source remains an open example and show that the lower bound in [3] is not tight in problem. Also, [3] did not provide any discussion on the general. tightness of this lower bound. Hence, it is useful to derive We would like to compare and contrast our work with †M. Mukherjee and N. Kashyap are with the Department of Electrical those of Courtade et al. in [8] and [9]. Courtade et al. Communication Engineering, Indian Institute of Science, Bangalore. Email: consider a “one shot” model with each terminal observing {manuj,nkashyap}@ece.iisc.ernet.in. only one instance of a random variable. They restrict the ‡C. Chan and Q. Zhou are with the Institute of Network Coding at the communication to linear functions of the source randomness. Chinese University of Hong Kong. Email: [email protected], qiao- [email protected]. In [9, Theorem 11], they evaluate the minimum number of bits of communication required to generate a fixed number 1Ouruseof“communicationcomplexity”differsfromtheuseprevalentin of bits of SK. It is also shown in [9, Theorem 4] that there thetheoreticalcomputerscienceliteraturewhere,following[4],itreferstothe exist sources where non-linear communication can strictly totalamountofcommunication, inbits,requiredtoperformsomedistributed computation. outperformanylinearcommunication,in termsofthenumber of bitsof communication.On the otherhand,ourmajorfocus [5] and [3] are but a special case of the model studied here, istheasymptoticmodelinvolvingi.i.d.sequencesofcorrelated obtained by restricting w to be integer-valued. If we further random variables at each terminal. We also do not impose restrict w(e) to take non-zero values only for subsets e⊆M any linearity restriction on the communication. However, we of size 2, we obtain the pairwise independent network (PIN) consider communication complexity for generating SKs of model of [11]. maximum rate only, contrary to the arbitrary number of bits Theterminalscommunicatethroughanoiselesspublicchan- of SK considered by Courtade et al. It should be mentioned nel,anycommunicationsentthroughwhichisaccessibletoall here that the proofsof Courtadeet al. proceedby finding“in- terminals and to potential eavesdroppers as well. An interac- herently connected subhypergraphs” obtained by completely tive communication is a communication f = (f ,f ,···,f ) 1 2 r removing certain hyperedges, as opposed to the “fractional withfinitelymanytransmissionsf ,inwhichanytransmission j removal”ofhyperedgesinourproofs.Thedifferenceisdueof sent by the ith terminal is a deterministic functionof Xn and i thefactthatCourtadeetal.consideraone-shotmodel,whereas allthepreviouscommunication,i.e.,ifterminalitransmitsf , j we look into an asymptotic scenario. Therefore, restricting thenf isa functiononlyofXn andf ,...,f . We denote j i 1 j−1 ourselves to complete removal of hyperedges only will lead the random variable associated with f by F; the support of F to weaker upper bounds, as demonstrated in Example III.1 is a finite set F. The rate of the communication F is defined appearing later in the paper. as 1 log|F|. Note that f, F and F implicitly depend on n. n The paper is organized as follows. The basic definitions Definition 1. A common randomness (CR) obtained from and conceptsare introducedin Section II. SectionIII presents an interactive communication F is a sequence of random our main result, an upper bound to R . In Section IV, we SK variables J(n), n ∈ N, which are functions of Xn , such evaluate the lower bound to RSK stated in [3, Theorem 2], M that for any 0 < ǫ < 1 and for all sufficiently large for the special case of graphical source models. The paper n, there exist J = J (Xn,F), i = 1,2,...,m, satisfying concludes with Section V. i i i Pr[J =J =···=J =J(n)]≥1−ǫ. 1 2 m II. PRELIMINARIES When J(n) = Xn , we say that the terminals in M have M In this section we will introduce the major concepts and attained omniscience. The communication F which achieves definitionsusedinthispaper.Throughout,weuseNtodenote this is called a communication for omniscience. It was shown the set of positive integers. A weighted hypergraphis defined in Proposition 1 of [1] that the minimum rate achievableby a by the pair H = (M,w) with M = {1,2,...,m} denoting communication for omniscience, denoted by R , is equal to CO the set of vertices and w:2M →R+∪{0} being the weight m function on the subsets of the vertices. We will often view w min Ri, where the region RCO is given by asa vectorwhosecoordinatesareindexedbye⊆M.Theset (R1,R2,...,Rm)∈RCOXi=1 of hyperedges is obtained from the weight function as the set E , {e ∈ 2M : w(e) > 0} of subsets of M with non-zero RCO = (Ri)i∈M : Ri ≥ w(e),B (M . (1) weights. (cid:26) iX∈B e∈XE:e⊆B (cid:27) Wesaythatarandomvector(Xi :i∈M)isahypergraph- Henceforth, we will refer to RCO as the “minimum rate ical source defined on the weighted hypergraph H if we can of communication for omniscience”. Note that the point write Xi =(ξe :e∈E,i∈e) for some randomvariables ξe’s (R1,R2,...,Rm) defined by Ri = H(Xi) for all i lies in such that H(ξe) = w(e) and ξe’s are mutually independent RCO, and hence RCO ≤ mi=1H(Xi)<∞. across e ∈ E. Whenever E consists only of subsets e of size Definition 2. A real nuPmber R ≥ 0 is an achievable SK 2, we refer to the source as a graphical source, and refer to rate if there exists a CR K(n), n ∈ N, obtained from an the hyperedgesas edges. interactive communicationF satisfying, for any ǫ>0 and for Forthehypergraphicalsource,Mdenotesasetofterminals. allsufficientlylargen,I(K(n);F)≤ǫand 1H(K(n))≥R−ǫ. Eachterminali∈Mobservesni.i.d.repetitionsofa random n The SK capacity is defined to be the supremum among all variable X . The n i.i.d. copies of the random variable are i achievable rates. The CR K(n) is called a secret key (SK). denoted by Xn = (ξn : e ∈ E,i ∈ e).2 For any subset A ⊆ i e M, X and Xn denote the collections of random variables From now on, we will drop the superscript (n) from both A A (Xi : i ∈ A) and (Xin : i ∈ A), respectively. It is easy to J(n) and K(n) to keep the notation simple. check that H(XA) = e∈E:e∩A6=∅w(e) and H(XA|XAc) = The SK capacity can be expressed as [1, Theorem 1] w(e). We∈eE:pe⊆oiAntoutherethPatthehypergraphicalsourcemodelisa C(M)=H(XM)−RCO. (2) P specialcaseofthemultiterminalsourcemodelof[1],whichis Other equivalent characterizations of C(M) exist in the liter- defined for an arbitrary joint distribution of X over a finite M ature. One such characterization of SK capacity can be given support size. Note that the hypergraphical models studied in via the notion of multivariate mutual information defined as follows: 2Eachi.i.d.sequenceofrandomvariablesξen,e∈E,shouldbethoughtof I(X ),minI (X ) (3) asanSKinitially sharedamongtheterminals ine. M P M P with I (X ) , 1 H(X )−H(X ) and Toproceed,weneedtointroducesomenotation.Definethe P M |P|−1 A∈P A M the minimum being taken over all partitions P = set Γ to be the set of all fractional packings x, satisfying the (cid:2)P (cid:3) {A ,A ,···,A } of M, of size ℓ ≥ 2. Note that I(Xn ) = following constraints: 1 2 ℓ M nI(X ). The quantity I(X ) is a generalization of the x≤w, (5) M M mutual information to a multiterminal setting; indeed, for ∃r=(r ) such that r ≥ x(e),∀B (M, m = 2, we have I(X ,X ) = I(X ;X ). It was shown in i i∈M i 1 2 1 2 Theorem 1.1 of [5] and Theorem 4.1 of [13] that Xi∈B e∈EX:e⊆B (6) m C(M)=I(XM). (4) x(e)− r =I(X ). (7) i M For the rest of this paper we shall use C(M) and I(XM) Xe∈E Xi=1 interchangeably. Note that Γ is non-empty since w∈Γ. This follows immedi- We will denote by P∗ the finest partition that achieves the ately by choosing (r1,r2,...,rm) ∈ RCO that achieves RCO minimum in (3). Theorem 5.2 of [13] guarantees that P∗ and by noting (2) and the fact that H(X ) = w(e). M e∈E exists and is unique, and will henceforth be referred to as Denote by Γ∗ the set of fractional packings x satisfying the fundamental partition. In particular, we call the partition I(Xx ) = I(X ), i.e., the fractional packingPx does not M M {{1},{2},...,{m}} consisting of m singleton cells as the decrease the SK capacity. It is easy to see that w ∈ Γ∗, and singleton partition and denote it by S. The sources satisfying hence it is non-empty. P∗ =S will be referred to as Type S sources. We now state the upper bound to R in the following SK We are now in a position to make the notion of communi- theorem. cation complexity rigorous. Theorem 1. For a hypergraphicalsource model X defined M Definition3. ArealnumberR≥0issaidtobeanachievable on the weighted hypergraph H=(M,w) we have rate of interactive communication for maximal-rate SK if for R ≤ x∗(e)−I(X ), all ǫ > 0 and for all sufficiently large n, there exist (i) an SK M interactivecommunicationFsatisfying 1 log|F|≤R+ǫ,and Xe∈E (ii)anSKK obtainedfrom F suchthat n1H(K)≥I(X )−ǫ. where x∗ is an optimal solution for the linear program The infimum among all such achievanble rates is calMled the min x(e) subject to the constraints x∈Γ. e∈E communicationcomplexityofachievingSKcapacity,denoted SiPnce, x∗ ≤ w, by (2) we have that the upper bound in by R . SK Theorem 1 is at least as good as R . We will need the CO The proof of Theorem 1 in [1] shows that there exists an following lemma in order to prove Theorem 1. interactive communication F that enables omniscience at all Lemma 2. For a hypergraphical source X defined on the M terminalsandfromwhichamaximal-rateSKcanbeobtained. weighted hypergraph H=(M,w) we have Therefore, we have R ≤ R < ∞. Hence, in terms of SK CO communication complexity, the sources that satisfy R = Γ=Γ∗. SK R are the worst-case sources. We will henceforth refer to CO Proof: To begin with note that H(Xx ) = x(e). themasR -maximalsources.Suchsourcesdoexist,asshown M e∈E SK It is straightforward to see that the constraints in (6) are in Section VI of [3]. P nothing but the R constraints of (1) for the source defined CO onHx.Therefore,theconstraint(7)alongwith(2)showsthat III. UPPERBOUND ONRSK a fractionalpackingx∈Γ doesnotdecreasethe SK capacity, In this section we derive an upper bound on R based on and so x∈Γ∗. Therefore, Γ⊆Γ∗. SK the notion of decremental SK agreement studied in [12]. The On the other hand, any fractional packing x∈Γ∗ does not idea is to “fractionally remove” hyperedges from the original decrease the SK capacity. Hence, by (2), there exists a rate hypergraph. To be precise, consider a hypergraphical source point r satisfying the R constraints, i.e., the constraints in CO X defined on the weighted hypergraph H = (M,w). A (6),aswellastheconstraint(7).So,x∈ΓandhenceΓ∗ ⊆Γ, M non-negative vector x satisfying x ≤ w (coordinatewise) is which completes the proof. called a fractional packing of the hypergraph H. For any We are now in a position to prove Theorem 1. fractional packing x, define a new hypergraphical source on Proof of Theorem 1: To begin with, consider any x ∈ the weighted hypergraph Hx = (M,x). Observe that since Γ. By Lemma 2, we also have that x ∈ Γ∗. Since any SK x≤w, the source defined on Hx is obtained by “removing” generation protocol for Xx is also a valid SK generation M some randomness from X . protocolforX , the factthatI(Xx )=I(X ) impliesthat M M M M We denote the relevant quantities for the source defined on R ≤ Rx ≤ Rx . Using (2), we have Rx = H(Xx )− SK SK CO CO M Hx by adding a superscript x to the original notation. For I(Xx ) = x(e) − I(X ). Therefore, combining the M e∈E M example, we use Xx , Rx , Rx etc. It is easy to see that above results we have for any x ∈ Γ, R ≤ x(e)− I(Xx )≤I(X ), sMince aCnOySKSKgenerationprotocolforXx I(X ).InoPrdertogetthebestupperbounSdKwesimep∈lEychoose is alMso a valid SMK generation protocol for X . M x∗ wMhichminimizes x(e)amongallpossiPblex∈Γ. M e∈E P Before proceeding, we provide an example where we ex- We first prove that for every A ∈ P∗ with |A|≥ 2, there plicitly evaluate the upper bound in Theorem 1. exists at least one edge of G contained in A. Otherwise, any refinement of P∗ to some P˜ by arbitrarily splitting A into Example III.1. Consider the hypergraph H=(M,w), with |M|=4 and weight vector w given as follows: two parts will satisfy EP˜ = EP∗, and hence, w(e) = eX∈EP w(e)=1,e={1,4},{2,3},{3,4} w(e). That would imply IP∗(XM) > IP˜(XM), violat- =2,e={1,2} eX∈EP˜ ing the optimality of P∗ in (3). Hence, we can fix a e˜⊆A. =0, otherwise. Next we obtain a fractional packing x 6= w by removing OnecaneasilycheckthatP∗ ={{1,2},{3},{4}},I(X )= randomnessfrome˜.Letǫ=minP(IP(XM)−IP∗(XM)),the M 1.5andR =3.5.Solvingthe linearprograminTheorem1, minimum being taken over all partitions P =6 P∗ which are CO we see that the optimal fractional packing x∗ is given by notcoarserversionsofP∗.P∗ beingthefundamentalpartition x∗({1,2})=1.5 and x∗(e)=w(e) for all e6={1,2}. Thus, (and P∗ 6= S) we have ǫ > 0; choose 0 < δ < ǫ. We claim Theorem 1 gives the upper bound R ≤3<R . that the fractional packing x, defined by x(e˜) = w(e˜)−δ, It is not difficult to check that noSiKnteger-valuCeOd x 6= w is and x(e) = w(e), for all e 6= e˜, lies in Γ. This will violate possible without decreasing the SK capacity. Thus even if w the fact that Γ = {w} and hence we will have the result by contradiction. To complete the proof we require to show that is integer-valued,removinga hyperedgeby an integeramount x∈Γ(=Γ∗). or completely need not be optimal, and fractional removal is To proceed, consider the graph Gx. Observe that by (8), a better thing to do. IP∗(XMx ) = IP∗(XM) and hence IP∗(XMx ) = I(XM). For We now turnourattentionto evaluatingthe upperboundin any partition P˜ which is a coarser version of P∗, we have Theorem1.EvaluatingtheupperboundinTheorem1requires I (Xx )=I (X )≥I(X ),using(8).Ontheotherhand, P˜ M P˜ M M the knowledge of I(XM), which in turn can be calculated in consideranypartitionP′ whichisnotP∗ oracoarserversion stronglypolynomialtime asshownin [13]. KnowingI(XM), ofit.Bythechoiceofxwehave, x(e)≥ w(e)−δ. theupperboundinTheorem1canbecomputedinpolynomial e∈XEP′ e∈XEP′ time. This is because the separation oracle for the constraints in (6), i.e., i∈Bri ≥ e∈E:e⊆Bx(e) = H(XBx|XBxc), for Thus,using(8)wehave,IP′(XMx )≥ |P′1|−1(cid:20) e∈EP′ w(e)− allB (M,isbutaninstanceofasubmodularfunctionmini- P mization givPen by min P r −H(Xx|Xx ) ≥0. δ ≥IP′(XM)−δ >IP′(XM)−ǫ≥I(XM).Hence,by(3), B(M i∈B i B Bc w(cid:21)e have I(Xx )≥I(X ). Since I(Xx )≤I(X ) always Thefactthatsubmodularfun(cid:26)ctionminimizationcanbe(cid:27)carried M M M M P holds, the result follows. out in polynomial time (see Theorem 45.1 of [14]), implies We now prove Theorem 3. that the upper bound in Theorem 1 can also be computed in Proof of Theorem 3: We first show that the source Xx∗ polynomial time (see Theorem 5.10 of [14]). definedontheweightedgraphGx∗ isTypeS.Ifnot,LemmaM4 It turns out that for the special case of graphical models, will imply that there exists a fractional packing x′ ≤ x∗ i.e., when E consists only of sets of size 2, the upper bound of (M,x∗), satisfying I(Xx′) = I(Xx∗) = I(X ). This M M M in Theorem 1 reduces to a very simple expression. in turn implies that x′ ∈ Γ∗ = Γ, thereby violating the optimality of x∗. Hence, Xx∗ is Type S. As a result we GTh=eo(rMem,w3.)Fwoerhaavseource XM defined on a weighted graph have, I(X ) = I(Xx∗) =MI (Xx∗) = 1 x∗(e). M M S M m−1 e∈E RSK ≤(m−2)I(XM). Therefore,theboundinTheorem1reducesto(m−X2)I(XM) as required. Before proceeding, observe that for a graphical model, we We would like to remark here that for the special case of have 1 PIN models on graphs, which is obtained by restricting w I (X )= w(e), (8) P M |P|−1 in the graphical model to be integer-valued, the same upper eX∈EP bound was also derived in Lemma 9 of [3], using protocols where EP denotes the set of edges e ∈ E which are not for SK generation developed in [11] based on spanning tree contained in any parts of the partition P. We require the packing. following lemma to prove Theorem 1. It was shown in the proof of Theorem 3 that the source Xx∗ is Type S. Therefore, Theorem 6 of [3] shows that Xx∗ Lemma 4. For a source X defined on the graph G = M M (M,w), we have Γ=Γ∗ ={Mw} only if X is Type S. is RSK-maximal. As a result, we have using Theorem 3 and M (2)thatRx∗ =(m−2)I(X ).SinceXx∗ wasobtainedfrom SK M M Proof: We shall prove the lemma by contradiction. Sup- X by throwing away some randomness that did not affect M pose that Γ = {w} but P∗ 6= S. We will show that there the SK capacity, we believe that it should not affect R as SK exists a fractional packing x 6= w which lies in Γ, thereby well.Hence,weconjecturethattheupperboundinTheorem3 contradicting the assumption P∗ 6=S. is tight. In fact, this leads us to believe that the upper bound in Theorem 1 is tight which is stated as a conjecture below. Definition 5. A real number R ≥ 0 is an achievable CI W (resp. CI) rate if there exists a CI L (resp. a CI L=(J,F)) Conjecture. TheupperboundsinTheorems1and3aretight. W such that for all ǫ>0, we have 1H(L)≤R+ǫ for all suffi- n IV. LOWERBOUNDS ONRSK ciently large n. We denote the infimum among all achievable CI (resp. CI) rates by CI (X ) (resp. CI(X )). In this section, we restrict our attention to source models W W M M definedongraphsonlyandshowthatthelowerboundderived With these definitions in hand, we summarize some of the in Theorem 2 of [3] reduces to a very simple expression. For resultsof[3]neededforthissectioninthefollowingtheorem. the hypergraphicalmodelin its full generality computing that Theorem 6. For a source X , we have boundisdifficult,exceptforthespecialcaseofTypeS sources M on t-uniform hypergraphs as shown in Theorem 6 of [3]. I(X )≤CI (X )≤CI(X )≤H(X ), M W M M M Theorem 5. For a source XM defined on a weighted graph and G =(M,w) we have R ≥CI(X )−I(X ). SK M M |P∗|−2 R ≥ w(e), To proceed, we will need a variant of the Lemma 7 of [3] SK |P∗|−1 for graphs. e∈XEP∗ where EP∗ ⊆E denotes the set of edges not contained within Lemma 7. For any function L of a source Xn defined on a M any of the cells of the partition P∗. weighted graph G = (M,w) with fundamental partition P∗, we have Toprovethistheoremweneedtointroducesomedefinitions I(Xn;L)≤2H(L). andresultsfrom[3].Webeginbyintroducingthedefinitionof A conditional multivariate mutual information, which is a gen- AX∈P∗ eralization of conditional mutual information to the multiter- minalsetting.Theconditionalmultivariatemutualinformation The proof follows on the lines of Lemma 7 of [3] and can of X given a random variable L is defined as3 befoundinAppendixA.Thefollowinglemmadeterminesthe M minimumrateofinteractivecommoninformationCI(X )for 1 M I(X |L), H(X |L)−H(X |L) . (9) graphical models. M |P∗|−1 A M (cid:20)A∈P∗ (cid:21) X Lemma 8. For the source X defined on a weighted graph M ThedefinitionofI(XM|L)appliestoanycollectionofjointly G =(M,w), with fundamental partition P∗, we have distributedrandomvariablesX ;inparticularitappliestothe M collection XMn . To be clear, CI(XM)= w(e). 1 e∈XEP∗ I(Xn |L), H(Xn|L)−H(Xn |L) . M |P∗|−1 A M (cid:20)A∈P∗ (cid:21) Proof:Tobeginwith, weobservethatitsufficestoprove X We use this definition of I(XMn |L) to extend to the multi- that CIW(XM)= e∈EP∗ w(e). Indeed, consider F to be a terminal setting an asymptotic version of two-terminalWyner broadcast of all the random variables ξn associated with the common information (see [15]) appearing in [2].4 edgesine∈EP∗.LPetJ=(ξen :e∈EP∗e).Itisstraightforward to verify that I(Xn |J,F) = 0, since H(Xn|J,F) = Definition 4. A (multiterminal) Wyner common information H(Xn |J,F) = M w(e). TherefAo∈reP,∗the paAir (J,F) (CIW)forXM isasequenceoffinite-valuedfunctionsL(n) = constiMtutesaCIwhosee∈/rEaPte∗is wP(e).Hence,wewould iLn(tne)r(aXctMinve) csoumchmtohnatinn1foIr(mXaMntio|Ln(n()C)I)→for0 Xas nis→a∞W.ynAenr have CI(XM) ≤ Pe∈EP∗ wP(e)e∈=EPC∗IW(XM), which along M with Theorem 6 would give the result. common information of the form L(n) = (J,F), where F is The proof of CPI (X ) = w(e) follows along an interactive communicationandJ is a CR obtainedfrom F. W M e∈EP∗ the lines of the proof of Theorem 6 of [3]. At first choosing P Similar to Definitions1 and 2 we shall dropthe superscript L = (ξen : e ∈ EP∗), it follows immediately that I(XMn |L) = (n)fromL(n) fornotationalsimplicity.Wynercommoninfor- 0. Thus, L is a CIW for XMn , and so CIW(XM) ≤ mationsL do exist: for example,the identitymap L=XMn is e∈EP∗ w(e). Next, we prove CIW(XM) ≥ e∈EP∗ w(e). aCI .ToseethatCIs(J,F)alsoexist,observethatJ=Xn To proceed, let L be any function of Xn . Then, we have W M P M P and a communication F enabling omniscience constitute a 1 CI , and hence, a CI. I(Xn |L)= H(Xn|L)−H(Xn |L) W M |P∗|−1 A M (cid:20)A∈P∗ (cid:21) X 3It should be noted that the definition of conditional multivariate mutual 1 information usedhere is slightly different from what wecalled “conditional = (H(Xn,L)−H(L)) multipartite information” in [3]. However, the main results of all of these |P∗|−1(cid:20)A∈P∗ A workscontinue toholdevenwiththecurrentdefinition. X 4Onepossiblegeneralization ofthenon-asymptotic Wynercommoninfor- −H(Xn ,L)+H(L) mationappearing in[15]tothemultiterminal settingiscarriedoutin[16]. M (cid:21) =H(Xn ,L)−H(L) Lemma 8. M 1 Unfortunately, it turns out that the lower bound in Theo- + |P∗|−1 (H(XAn,L)−H(XMn ,L)) rem 5 is not tight in general as illustrated by the following (cid:20)AX∈P∗ (cid:21) example. 1 =H(Xn )−H(L)− H(Xn |Xn,L) M |P∗|−1 Ac A Example IV.1. Consider the source XM defined on a AX∈P∗ weighted graph G = (M,w) with |M| = 4. The weight (10) vector w is given by w(e) = 1 for e = {1,2},{1,3},{2,3} =H(XMn )−H(L) and {3,4}, and w(e) = 0 otherwise. Thus, E = 1 {{1,2},{1,3},{2,3},{3,4}}. It is straightforward to verify − H(Xn )−H(Xn)−H(L|Xn) |P∗|−1 M A A that P∗ = {{1,2,3},{4}} and I(XM) = 1. Theorem 5 A∈P∗(cid:20) (cid:21) X gives the lower bound R ≥ 0 for this source. However, (11) SK it is clear that the combined observations of terminal 1 and |P∗| =n w(e) 1− 2, i.e., Xn , is completely independent of Xn. Hence, a |P∗|−1 {1,2} 4 e∈E (cid:18) (cid:19) communication of positive rate would certainly required for X + n w(e)+ w(e) −H(L) achieving SK capacity. Thus, RSK >0, which implies that the |P∗|−1 lower bound in Theorem 5 is loose. (cid:20)Xe∈E e∈XEP∗ (cid:21) + 1 H(L|Xn) (12) V. CONCLUDING REMARKS |P∗|−1 A A∈P∗ The upper bound in Theorem 1 is the first reported upper = n Xw(e) bound on RSK for any instance of the multiterminal source |P∗|−1 modelof[1].We showedthatthisboundisatleastasgoodas e∈XEP∗ the obvious upper bound of R , and can in fact be stronger CO 1 − I(Xn;L)−H(L) as illustrated by Example III.1. We further show that this |P∗|−1"A∈P∗ A # upperboundcanbecomputedinpolynomialtime.Webelieve X that this upper bound is tight. Due to the lack of a proof = n w(e)− 1H(L) we have left it as a conjecture. We have also evaluated the |P∗|−1 n  lower bound on R stated in [3, Theorem 2] for the special e∈XEP∗ case of graphical SsKource models. The evaluation enabled us   − 1 I(Xn;L)−2H(L) to construct an example showing that the lower bound is not |P∗|−1"A∈P∗ A # tight in general. X n 1 ACKNOWLEDGEMENTS ≥ w(e)− H(L) , (13) |P∗|−1 n  TheauthorswouldliketothankNavidNouriforstimulating e∈XEP∗ discussionswhichhelpedinwritingthispaperandgainabetter   where(10)and(11)followfromthefactthatLisafunctionof understanding of the problem at hand. Xn ;(12)followsfromthefactthatH(Xn )=n w(e) M M e∈E and A∈P∗H(XAn)=n e∈Ew(e)+ e∈EP∗Pw(e) ; and PROAOPFPOEFNDLIEXMAMA7 (cid:20) (cid:21) (13) is due to Lemma 7. P P P The lemma essentially follows from Lemma 7 in [3]. A Now, consider L to be any CI so that for any ǫ > 0, we have 1I(Xn |L) < W ǫ for all suffi- weightedhypergraph(M,w)ist-uniformifallhyperedgesin n M (|P∗|−1) E = {e ∈ 2M : w(e) > 0} have size exactly t. In particular, ciently large n. The bound in (13) thus yields 1H(L) > n a weighted graph satisfies this definition with t=2. We then w(e)−ǫ for all sufficiently large n. Hence, it fol- lowe∈sEtPh∗at CI (X ) ≥ w(e). Therefore, we obtain have the following lemma. CPI (X )=W M w(ee)∈.EP∗ Lemma 9 ([3], Lemma 7). Let X be a source defined on W M e∈EP∗ P M We now prove Theorem 5. a t-uniform weighted hypergraph. For any n ∈ N and any P Proof of Theorem 5: For the source X we have function L of Xn , we have M M m R ≥CI(X )−I(X ) (14) SK M M I(Xn;L)≤tH(L). 1 i = w(e)− w(e) (15) i=1 |P∗|−1 X e∈XEP∗ e∈XEP∗ |P∗|−2 It shouldbe clarified that Lemma 7 in [3] is stated onlyfor = |P∗|−1 w(e) hypergraphswithinteger-valuedweightfunctionsw.However, e∈XEP∗ thisrestrictionisnotessentialfortheproofgivenin[3],sothat where, (14) follows from Theorem 6 and (15) follows from it applies to any real-valued weight function w just as well. We will need the above lemma only for the case of graphical [7] T.A.Courtade andR.D.Wesel,“Codedcooperative dataexchange in source models (i.e., t=2). multihopnetworks,”IEEETrans.Inf.Theory,vol.60,no.2,pp.1136– 1158,Feb.2014. To prove our Lemma 7, consider the given weighted graph [8] T. A. Courtade and T. R. Halford, “Coded cooperative data exchange G = (M,w), with edge set E = {e ∈ 2M : w(e) > 0}, forasecretkey,”inProc.2014IEEEInt.Symp.Inf.Theory(ISIT2014), and the fundamental partition P∗ = (A ,...,A ) of the Honolulu, Hawai’i, USA,June29–July4,2014,pp.776–780. 1 k [9] T. A. Courtade and T. R. Halford, “Coded cooperative data exchange correspondingsource X . FromX , we constructa closely M M forasecretkey,”arXiv:1407.0333v1. related graphical source X˜ on a vertex set V, as described [10] S.Nitinawarat, C.Ye,A.Barg,P.NarayanandA.Reznik,“Secret key V next. generationforapairwiseindependentnetworkmodel,”IEEETrans.Inf. Theory,vol.56,pp.6482–6489, Dec.2010. For each pair of cells A ,A of P∗, with i < j, let E i j i,j [11] S. Nitinawarat and P. Narayan, “Perfect omniscience, perfect secrecy denote the set of edges of G with one endpoint in A and the andSteinertreepacking,”IEEETrans.Inf.Theory,vol.56,no.12,pp. i otherin A .We furtherletE bethesetofedgesofG thatare 6490–6500, Dec.2010. j i [12] C.Chan,A.Al-BashabshehandQ.Zhou,“Incrementalanddecremental contained within A , i = 1,2,...,k. Now, let {a ,...,a } i 1 k secret key agreement”, submitted to2016 IEEEInt. Symp. Inf. Theory and {a′,...,a′} be two disjoint sets of size k = |P∗| each, (ISIT2016),Barcelona, Spain,July10–15,2016. 1 k and let V = {a ,...,a } ∪ {a′,...,a′}. Define a weight [13] C.Chan,A.Al-Bashabsheh, J.Ebrahimi,T.KacedandT.Liu,“Multi- 1 k 1 k variate mutual information inspired bysecret keyagreement,” inProc. function w˜ on 2-subsets of V as follows: for each pair of ofIEEE,vol.103,no.10,pp.1883-1913, Oct.2015. integers i < j, we set w˜({a ,a }) = w(e); and for [14] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, i = 1,2,...,k, set w˜({a ,a′i})=j ew∈˜E(ie,j). For all other VolumeA–C,Springer, 2004. 2-subsets e˜of V, we set iw˜(ei˜)=0. e∈PAi [15] vAa.riDab.leWs,”ynIeEr,EE“TThreancso.mImnfo.nThinefoorrym,avtoiol.nITo-f21tw,onod.ep2e,npdpe.nt16r3an–d1o7m9, We take X˜ to be a source definPed on the weighted graph Mar.1975. V (V,w˜). To be precise, let ξ , e∈E, be the random variables [16] G.Xu,W.LiuandB.Chen,“Wyner’scommoninformation:Generaliza- e tionsandanewlossysourcecodinginterpretation,”arXiv:1301.2237v1. associated with the edges of the graphical source X . In M X˜ , we associate with each 2-subset (edge)e˜of V, a random V variable ξ˜ as below: e˜ (ξ :e∈E ) if e˜={a ,a } e i,j i j ξ˜ = (ξ :e∈E ) if e˜={a ,a′} e˜  e i i i 0 otherwise. As usual, for any v ∈ V, X˜v refers to the random variable (ξ : v ∈ e˜). Observe, in particular, that X˜ = X , for e˜ ai Ai i=1,2,...,k. Now, to complete the proof of Lemma 7, we note that for any function L of Xn , we have M k I(Xn;L) = I(X˜n;L) A ai A∈P∗ i=1 X X ≤ I(X˜n;L) v v∈V X ≤ 2H(L) by Lemma 9 (with t=2). REFERENCES [1] I. Csisza´r and P. Narayan, “Secrecy capacities for multiple terminals,” IEEETrans.Inf.Theory,vol.50,pp.3047–3061, Dec.2004. [2] H.Tyagi,“Commoninformationandsecretkeycapacity,” IEEETrans. Inf.Theory,vol.59,no.9,pp.5627–5640, Sep.2013. [3] M. Mukherjee, N. Kashyap, Y. Sankarasubramaniam, “On the public communication needed to achieve SK capacity in the multiterminal sourcemodel,”arXiv:1507.02874. [4] A. C. Yao, “Some complexity questions related to distributed comput- ing,” in Proc. 11th Annu. ACM Symp. Theory of Computing (STOC), 1979. [5] C.ChanandL.Zheng,“Mutualdependence forsecretkeyagreement,” inProc.44thAnnualConference onInformation Sciences andSystems (CISS),2010. [6] S.ElRouayheb, A.Sprintson, andP.Sadeghi, “Oncoding forcooper- ative data exchange,” in Proc. 2010 IEEE Inf. Theory Workshop (ITW 2010),Cairo,Egypt,6–8Jan.2010,pp.1–5.