Distributed Private Randomness Distillation
Dong Yang Karol Horodecki Andreas Winter












theoremTheorem
acknowledgement[theorem]Acknowledgement
algorithm[theorem]Algorithm
axiom[theorem]Axiom
claim[theorem]Claim
conclusion[theorem]Conclusion
condition[theorem]Condition
conjecture[theorem]Conjecture
corollary[theorem]Corollary
criterion[theorem]Criterion
definition[theorem]Definition
example[theorem]Example
exercise[theorem]Exercise
lemma[theorem]Lemma
notation[theorem]Notation
problem[theorem]Problem
observation[theorem]Observation
proposition[theorem]Proposition

solution[theorem]Solution
summary[theorem]Summary


 











` 
` ="8000

` =:
  
  



  
R 
C
N  
[ [1]#1
        
        |⟩⟨|[2]|#1⟩⟨#2|
        [1]| #1⟩⟨ #1 |[1]⟨#1⟩
        Rank[2]Tr⊗†↓𝒜ℬ𝒞𝒟ℰℱ𝒢ℋℐ𝒥𝒦ℒℳ𝒩𝒪𝒫ℛ𝒮𝒯𝒳𝒵csuppqsuppvar→⟶polylog𝕀idℝℂ𝔽ℕℤℙℚ𝕌𝔼⟩⟨
        dyang@cjlu.edu.cnLaboratory for Quantum Information, China Jiliang University, 310018 Hangzhou, ChinaDepartment of Informatics, University of Bergen, 5020 Bergen, Norwaykhorodec@inf.ug.edu.plInternational Centre for Theory of Quantum Technologies, University of
        Gdańsk, Wita Stwosza 63, 80-308 Gdańsk, PolandInstitute of Informatics, Department of Physics, Mathematics and Informatics, National Quantum Information Centre, University of Gdańsk, 80-308 Gdańsk, Polandandreas.winter@uab.catICREA & 
        Física Teòrica: Informació i Fenòmens Quàntics, 
        Departament de Física, Universitat Autònoma de Barcelona, 
        08193 Bellaterra (Barcelona), Spain
        We develop the resource theory of private randomness extraction in 
        the distributed and device-dependent scenario. 
        We begin by introducing the notion of independent random bits, which 
        are bipartite states containing ideal private randomness for each party, 
        and motivate the natural set of free operations. As a conceptual tool, we introduce Virtual Quantum State Merging, 
        which is essentially the flip side of Quantum State Merging, without
        communication. 
        We focus on the bipartite case and find the rate regions achievable in 
        different settings. Surprisingly, it turns out that local noise 
        can boost randomness extraction. 
        As a consequence of our analysis, we resolve a long-standing problem by giving 
        an operational interpretation for the reverse coherent information (up to a constant 
        term log d) as the number of private random bits obtained by sending quantum 
        states from one honest party (server) to another one (client) via the eavesdropped 
        quantum channel. 
        Distributed private randomness distillation
            Andreas Winter
            30 August 2019
        ===========================================
        
        
         Introduction.–
        Randomness is an important notion, having various applications 
        in science and technology. Usually only pseudo-randomness is produced 
        in the classical world, for instance by certain complex algorithms in a 
        computer, where the pseudo-random value is determined by a hidden variable 
        so that it is already implicitly known beforehand. 
        Conceptually, the most straightforward way to ensure
        a uniformly random bit sequence is to generate it by measuring a quantum
        state, e.g., the σ_Z eigenstate |0⟩ in the σ_X
        eigenbasis |±⟩. In this way the measurement outcome is completely 
        unpredictable and, thus, private against any eavesdropper. Here the privacy comes from the fact that a pure state naturally excludes any correlation with other systems. 
        The problem of randomness extraction from a general mixed state  
        has been considered in <cit.> by the decoupling approach <cit.>, where Alice's system is correlated with the system of an eavesdropper Eve via a mixed state ρ_AE and the goal of Alice is to generate randomness private against Eve. An implicit assumption in this setting is that Bob, who holds 
        the purifying system of ρ_AE, is a trusted but otherwise completely 
        passive party. The reason is that Alice herself cannot figure out the correlation with Eve without Bob's assistance. So in the spirit of being cautious in cryptography, we have to assume that Eve holds all the purifying system of ρ_A, i.e. ρ_AE is pure, unless Alice knows that Bob holds part of it. 
        
        
        We make Bob active, where Alice and Bob trust each other and collaborate to  extract independent randomness private against Eve. This is a novel scenario: distributed private randomness extraction, which is dual to the Slepian-Wolf problem of distributed data compression <cit.> in information theory. Surprisingly, a natural dual setting to Slepian-Wolf does not exist in the classical framework, yet quantumly it does.
        In this Letter, we study the distributed and device-dependent
        scenario for randomness extraction (for an alternative approach, the so-called device-independent
        scenario, see <cit.> and references therein). 
        We begin with defining the notion of
        independent random bits (ibits), in a picture dual to the standard one, as 
        bipartite states that contain ideal private randomness, and justifying 
        the set of allowed operations which do not increase randomness. 
        Then we introduce our conceptual tool, the 
        Virtual Quantum State Merging (VQSM) protocol, to study two-sided and one-sided 
        randomness extraction. VQSM originates from the 
        Quantum State Merging (QSM) protocol <cit.> and represents the other face of 
        QSM, less noticed in the literature. In the two-sided setting, we obtain the achievable 
        rate regions in various scenarios, including either free or no communication
        and either free or no local noise. It follows that there is no bound randomness.
        Surprisingly, local noise, usually regarded as useless,
        can extend the rate region. In the one-sided setting, we determine the optimal rates 
        of randomness extraction in two extremal classes, pure entangled 
        states and separable states, and provide a computable 
        upper bound for general states.  
        Finally, we resolve a long-standing problem by giving an operational 
        interpretation for the reverse coherent information in terms of the number of ibits obtained by sending quantum 
        state from one honest party to another one via an 
        eavesdropped quantum channel. In the following, we state and discuss the 
        results carefully, while all proofs are in the appendix <cit.>.  
        
        
         Ibits and CLODCC.–
        In the standard approach, a state having one ideal random bit with respect to Eve has the form 
        ρ_K_AE=1/2(|0⟩⟨0|+|1⟩⟨1|)_K_A⊗ρ_E where ρ_E is an arbitrary state of Eve. 
        In the dual picture, where the purifying system is included and Eve's system is excluded, 
        an equivalent form is 
        α_K_AA'B' = 1 2∑_i,j=0^1|i⟩⟨j|_K_A⊗ U_i σ_A'B' U_j^†, 
        where K_A is the key part that generates randomness if a measurement were 
        performed in the basis {|0⟩,|1⟩}_K_A, U_i are unitary operators on A'B',
        and σ_A'B' is an arbitrary state. A'B' is known as the shield system 
        possibly distributed over Alice's and Bob's spaces, 
        protecting privacy against Eve <cit.>. Similarly, a state with two independent random bits at Alice's and Bob's 
        side, respectively, called ibit, has the following form:
         
        A bipartite quantum state having two independent random bits private against Eve is of the form
        α_K_AK_BA'B' = 1/4∑_i,j,k,ℓ=0^1|i⟩⟨j|_K_A⊗|k⟩⟨ℓ|_K_B⊗ U_ikσ_A'B' U_jℓ^†.
        
        
        It is important to note that getting (approximate) ibits is equivalent to obtaining the state in the exact (approximate) standard form:
        ρ_K_AK_BE=1/4(|0⟩⟨0|+|1⟩⟨1|)_K_A⊗ (|0⟩⟨0|+|1⟩⟨1|)_K_B⊗ρ_E,
        
        see the proof of Lemma <ref> in <cit.>. The security of randomness is measured by the trace distance <cit.> and, thus, is composable <cit.>. 
        
        Now we ask what kind of operations are allowed for free in randomness extraction. Notice that a pure state |0⟩_K_A is a special form of ibit where K_B and A'B' are dimension one, so we cannot allow pure states for free. It is safe to assume a closed system paradigm, like the framework for distilling thermodynamical work represented by pure states <cit.>. Also it is natural to assume that free operations should allow for local unitary transformation and some form of communication. A good candidate is the set of operations formed by Closed Local Operations (CLO) and Dephasing Channel Communication (DCC) <cit.>, designed for quantifying the localizable purity in a quantum state, where DCC simulates classical communication. In our setting, partial trace is not needed since we can always put the partial-tracing subsystem into the shield without harming privacy. In total, the set of free operations consists of the following two and their compositions:
        (i) local unitary transformations and
        (ii) sending a subsystem through a dephasing channel, where the dephasing channel environment goes to Eve. W.l.o.g. the dephasing basis is chosen to be the fixed computational one and these operations are named CLODCC. By Lemma <ref>, the picture of distilling ibits without measurement is equivalent to that of getting randomness in the standard form after performing measurement on the key part. We can therefore exchange both pictures freely. 
        
        It might seem that our framework for randomness reduces to that for 
        purity since we have similar operations and purity can generate randomness. 
        This would be true if we considered randomness extraction under global operations, 
        but it is very different in the distributed setting on which we focus in this work. 
        Also, it is possible to study randomness extraction by assuming other 
        free operations, e.g., incoherent operations <cit.>.  
        
        Having defined the free operations, we now ask the key question: For a bipartite quantum state ρ_AB whose purification is with Eve, how much private randomness can Alice and Bob obtain against Eve under CLODCC? We mainly consider the asymptotic i.i.d. setting which means we count the rates. It turns out that another seemingly useless resource–local noise, can act as a booster in the process. Here local noise means a maximally mixed state on Alice's or Bob's side, whose purification is under Eve's control, i.e. Alice or Bob share a maximally entangled state with Eve. It is clear that from local noise alone, Alice cannot produce randomness unknown to Eve by measuring her half, because the outcome is perfectly correlated with Eve. However local noise may help when combined with other states. An illuminating example is entanglement swapping: Alice shares one singlet with Bob and another one with Eve, i.e. the tripartite state is |Φ⟩_A_1B⊗|Φ⟩_A_2E. Here the state 1/2_A_2 is understood as the local noise on Alice's side. Observe that in entanglement swapping, the outcome of the Bell measurement by Alice is completely random against each of Bob and Eve separately (no communication between them). Thus we get that in the case of no communication between Alice and Bob, Alice can obtain two random bits unknown to Eve. However without the local noise, 
        Alice can get only one random bit. We therefore have several different settings 
        depending on whether randomness is to be distilled on two sides or one side, 
        whether local noise is available or not, and whether communication is allowed or not. 
        Before stating our findings on the rate regions,
        we introduce the conceptual tool.
        
        
         VQSM.–Entanglement swapping shows that local noise can play an important role 
        in the distributed scenario. If local noise is not freely available, Alice and Bob have the option of creating it from the resource. 
        In the case of no communication, Alice can put one copy of her systems A into 
        the shield A', meaning that it will not be touched by her any more. This does not change Bob's state. We may pretend that A' is with Eve, making things only worse for Bob, but now it is a pure state with Eve, the definition of local noise. In the case of communication, Alice can send one of her systems to Bob through the dephasing channel. Since randomness in the copy is not extracted, these options may reduce the overall rate of randomness distillation if the proportion of the wasted copies is not negligible. 
        However, there is a more efficient way, which produces some private
        randomness for Alice and simultaneously gives Bob local noise. To gain 
        intuition, let us look at the QSM protocol <cit.>.
        For our goal, B is the reference system and QSM is performed from A to E, 
        i.e., the task is to transform n copies of a tripartite state |ψ⟩_ABE into 
        |ϕ⟩_A_1A_2B^nE'E_1E_2 by LOCC such that 
        ϕ_E_1B^nE'≈(|ψ⟩⟨ψ|_ABE)^⊗ n, 
        where ϕ_E_1B^nE'=_A_1A_2E_2ϕ_A_1A_2B^nE'E_1E_2. 
        In the asymptotic i.i.d. case, if 
        S(A|E)_ψ = S(ψ_AE)-S(ψ_E)>0, the protocol requires 
        an additional rate of S(A|E)_ψ ebits (the unit entanglement in a two-qubit maximally entangled state) shared between systems A and E. 
        However, when S(A|E)_ψ<0, not only does it not need entanglement, 
        but also creates a rate of -S(A|E)_ψ ebits on A_2E_2.
        In the protocol, Alice transforms A^n into A_1A_2 by a unitary, 
        then measures subsystem A_1 in the computational basis and announces 
        the outcome to Eve, who further, according to the outcomes, transforms E^n into E'E_1E_2 
        by proper unitaries. The amount of classical communication
        is the size of A_1, its rate is the mutual information between Alice and Bob,
        I(A:B)_ψ = S(ψ_A)+S(ψ_B)-S(ψ_AB). 
        
        
        Roughly speaking, the measurement outcome on A_1 in QSM is independent of Bob and private against Eve. The intuition is the following: Bob's state remains invariant, so the measurement outcome is independent of Bob; the necessity to send the measurement outcome from Alice to Eve implies that Eve cannot predict it by herself and, thus, it is private against Eve. Technically, the measurement outcome is almost decoupled from Eve. This weak correlation can be deleted by the technique of 
        privacy amplification (PA) <cit.>; 
        it amounts to tracing out a little bit more from A_1, not affecting the rate of randomness. 
        A further observation is that Bob's system is purely entangled with 
        Eve's, conditional on the measurement outcomes, and in our setting, Bob need not care about 
        whether Eve performs the rotations or not. In this way, Alice can extract randomness independent of Bob and 
        private against Eve at the rate I(A:B)_ψ, while at the same time 
        Bob's system is virtually entangled with Eve, acting as
        noise that can help Bob extract randomness later. The composition of QSM and PA we call Virtual Quantum State Merging. 
        The formal claim that the rate of randomness extractable by Alice in the QSM setting equals to I(A:B)_ψ is encapsulated in a double-decoupling theorem, <cit.>. Its composability, i.e. Alice's and Bob's randomness is independent when Bob extracts randomness later assisted by local noise, is proved in <cit.>. Theorem <ref>, which may be of independent interest itself, is our main tool to derive randomness distillation rates. 
        
        
        
         Two-sided randomness distillation.–
        Having developed the tool, we are ready to state the main results.  
        It is clear that given a state ρ_AB, we can 
        obtain the randomness at the rate R_G(ρ_AB):=log|AB|-S(ρ_AB) if global 
        unitary operations on AB are allowed <cit.>. 
        We now ask the same question when the parties are distributed so only local 
        unitary operations are allowed: What is the rate region of achievable pairs
        (R_A, R_B), representing that 
        Alice produces randomness at rate R_A and Bob at rate R_B, and their 
        randomness is independent and secret against Eve, who has the purifying system?
        We have four different settings in which we allow free or no local noise,
        and free or no communication in form of the dephasing channel. 
        The answer is our first main result, Theorem <ref>. 
        
        
         
        For a given state ρ_AB, the following rate regions are achievable
        (and tight in settings 1, 2 and 3):
        
        1) For no communication and no noise, 
        R_A       ≤log|A| - S(A|B)_+, 
        R_B       ≤log|B| - S(B|A)_+, and
        R_A + R_B ≤ R_G,
        where [t]_+=max{0,t};
        
        2) for free noise but no communication, 
        R_A       ≤log|A| - S(A|B), 
        R_B       ≤log|B| - S(B|A), and 
        R_A + R_B ≤ R_G;
        
        3) for free noise and free communication, 
        R_A≤ R_G, R_B≤ R_G, and R_A+R_B≤ R_G;
        
        4) for free communication but no noise, 
        R_A       ≤log|AB| - max{S(B),S(AB)}, 
        R_B       ≤log|AB| - max{S(A),S(AB)}, and
        R_A + R_B ≤ R_G.
        
        Note how the solutions to 1) and 2) appear to be dual to the Slepian-Wolf theorem on distributed data compression <cit.>. In 3), the rate R_G can be realised on either side as randomness (but not necessarily as purity). We prove only achievability in 4) and leave its tightness open. 
        
        
        
        
        
        It is easy to see that, if non-zero randomness can be extracted by global operations, which 
        means R_G>0, then from Theorem <ref> there exists a pair (R_A,R_B) satisfying R_A+R_B=R_G>0 achievable even in the most restrictive setting 1). Therefore, an immediate conclusion from Theorem <ref> is the non-existence of bound randomness states.
        
         Given a state ρ_AB, if randomness can be extracted by 
        global operations on AB, then non-zero randomness can be extracted by CLODCC operations.
        
        
        
        
         One-sided randomness distillation.–
        We will focus on a pair rate (R_A,0) in setting 4) to understand it a bit better. The task is that Bob helps Alice to extract randomness against 
        Eve as much as possible. Free communication is allowed but local noise is not. Other 
        settings are understood already in Theorem <ref> from the tightness of the rate regions, which imply that the extremal points are optimal. First, we derive a formula for the optimal rate, unfortunately involving regularization.  
        
        
        The randomness that can be extracted from ρ_AB on Alice's side is
        R_A(ρ)=log|AB|-inf1/nmax{ S(E'^(n)), S(B'^(n)) },
        where the infimum is taken over all n, and E'^(n) and B'^(n) are the output
        systems under CLODCC acting on ρ^⊗ n_AB.
        At first sight, this theorem is not very useful as it involves complex CLODCC processing 
        and suffers from the notorious regularization problem. 
        But the further observation that 
        S(E'^(n))≥ nS(E), because Eve's entropy is non-decreasing in every use of the 
        dephasing channel, gives the exact optimal rate for a large class of states. Namely,
        for ρ_AB satisfying S(B)≤ S(E), R_A(ρ)=log|AB|-S(AB)=R_G, 
        so all the randomness can be localized on Alice's side. A large class of bipartite states satisfy this property, e.g. the 
        positive-partial-transpose states, which include separable states. 
        Note that possibly two-way communication is needed to localize the global purity on Alice's 
        side, but only one-way communication is needed to localize randomness. 
        An example for this is the cq-state 
        ρ_AB=∑_i p_i|i⟩⟨i|_A⊗ρ^i_B, when ρ^i_B do not commute.  
        
        Whether the regularization is needed or not is an open problem. We give a partial answer 
        to this in that R_A is at least not strongly additive, i.e. 
        R_A(ρ⊗σ)≠ R_A(ρ)+R_A(σ), by presenting an 
        example with the activation effect: R_A(Φ_AB⊗σ_AB)=3 while 
        R_A(Φ_AB)=3/2 and R_A(σ_AB)=1, where Φ_AB is a singlet 
        and σ_AB=1/2(|00⟩⟨00|+|11⟩⟨11|). The nontrivial
        R_A(Φ_AB)=3/2 comes from Theorem <ref>, and the other two are
        straightforward. 
        
        
        The optimal randomness that can be extracted from ρ_AB on Alice's 
        side is upper bounded by R_A(ρ)≤log|AB|-1/2max{S(A),S(B)}. The upper bound is tight for pure states.
        
        
        Hence, for |ϕ⟩_AB, R_A=log|AB|-1/2S(A)_ϕ. Furthermore, the rate of the secret key that can be distilled from the pure state is K_D=S(A)_ϕ<cit.>. When |A|=|B|=d, we have an appealing formula exhibiting 
        the exact balance between localisable and shareable privacy
        R_A+1/2K_D=2log d.
        For mixed states K_D(ρ_AB)≤ S(ρ_A), 
        we get R_A+1/2K_D≤ 2log d,
        which can be treated as complementarity between private
        randomness and key in analogy to complementarity between purity and 
        entanglement <cit.>. 
        It captures the fact that R_A attains 2log d on a pure product state 
        while K_D attains the maximal value on a maximally entangled state.
        
        
        
        
        
         Private randomness capacity.–
        It is well known that channel capacity formulas usually involve regularization 
        <cit.>, i.e., optimisation over growing numbers of channel uses due to 
        non-additivity of the relevant quantities 
        <cit.>, making a 
        head-on numerical approach impossible. However, this does not prevent the 
        regularized non-additive quantities from having physical interpretations: the optimal rate to transmit information faithfully through a channel. Ironically, there are additive quantities that however
        lack an interpretation <cit.>, one of these being the 
        reverse coherent information, which is additive 
        <cit.>, but whose interpretation was missing for a long time. The quantity was defined in <cit.> and introduced in <cit.> as the “negative cb-entropy” of a channel.
        In <cit.>, it was rediscovered independently as  reverse coherent information (RCI) and 
        shown to be a lower bound for the entanglement 
        distribution capacity of a channel assisted by classical feedback communication by using the hashing inequality <cit.> (see <cit.> in this context). See  <cit.> for the extension to the continuous-variable case and the very recent papers on RCI <cit.>. Here we provide its exact operational interpretation.  
        
        Consider the task of generating private randomness by communicating 
        through a quantum channel. A client Bob wanting to produce private randomness, has the measurement device but cannot prepare a quantum state himself. 
        He has access to but does not trust quantum systems being at his disposal, which are potentially entangled with Eve's system. However, there is a quantum channel to Bob from a trusted server Alice who can prepare any quantum state, although the channel itself is eavesdropped by Eve. 
        First, we argue that the model is well motivated and that it captures the server-client structure possibly realised in future 
        quantum networks: the server having huge devices and being able to 
        prepare and manipulate quantum states and a client being able to only perform 
        limited operations, e.g., unitaries and measurement. 
        The server provides a service to the client via a quantum channel. 
        Second, this new cryptographic model is completely in line with the standard model of 
        transmitting information and, thus, can be regarded 
        as a new character of a quantum channel. Now the natural capacity question is: 
        “What is the maximal rate of private randomness that can be extracted at Bob's side when 
        Alice sends quantum states through the channel?” Amazingly, we can answer
        it completely.
        
        
        The private randomness capacity of a channel 
        𝒩:A'⟶ B is given by
        R( N) = log|B| 
                       + max_|ϕ_AA'{ S(ϕ_A)-S(𝕀_A⊗ N(ϕ_AA')) }.
        The second term is just the reverse coherent information of the channel. So, for the first time, we provide an operational interpretation for it in a
        natural Shannon-theoretic model. [After our work, Mark Wilde pointed out that the same quantity R( N) can be derived from <cit.> and, thus, can be explained in quantum hypothesis testing for channels.] As a matter of fact, the randomness generated at the client is private not only to the eavesdropper but also to the server. 
        The single-letter formula is concave w.r.t. the input state <cit.> and, thus, efficiently computable. 
        We can draw an interesting comparison between private randomness capacity and 
        purity capacity: 
        Pure( N)=log|B|-inf_n 1/n S_min( N^⊗ n), where 
        S_min( N)=min_ϕS( N(ϕ)) is the minimum output entropy. 
        From <cit.>, we know that S_min( N) is not additive; thus regularisation is required. 
        
        
        
        
         Summary and outlook.–
        We have initiated the study of randomness extraction in the distributed scenario and provided the tool to tackle this situation. We found the exact achievable rate regions for various settings of distillation protocols and gave the long-sought operational interpretation
        of the reverse coherent information of a quantum channel.
        
        This work opens up a new area, suggesting a wide range of generalisations 
        and extension of the considered scenarios, including the multipartite case and 
        the one-shot scenario based on one-shot QSM <cit.>,
        as well as other cryptographic variants such as the honest-but-curious scenario. The structural analogy between private states and independent states also needs further exploration. These directions will be developed elsewhere <cit.>. Two notable topics are under study. One is distributed randomness extraction under the framework of coherence theory <cit.>, where the allowed operations are incoherent, and the other is the strong converse problem for the private randomness capacity. Indeed, there are rare cases <cit.> where we have a single-letter formula on capacity, and the strong converse theorem is proved only for such cases <cit.>. 
        
        
        
        
         Acknowledgements.–
        The authors thank Omer Sakarya for confirming the direct relation between secret sharing schemes and the structure of independent states, and Mark Wilde and Stefano Pirandola for comments on an earlier version.
        
        DY was supported by the NSFC (grant nos. 11375165, 11875244), and by the NFR project ES564777.
        
        KH was supported by the grant Sonata Bis 5 (grant no. 2015/18/E/ST2/00327) from the National Science Center, and by the Foundation for Polish Science (IRAP project, ICTQT, contract no. 2018/MAB/5, co-financed by EU via Smart Growth Operational Programme).
        
        AW was supported by the European Research Council (Advanced Grant IRQUAT), the European Commission (STREP project RAQUEL), the Spanish MINECO, projects FIS2013-40627-P and FIS2016-80681-P, as well as by the Generalitat de Catalunya, CIRIT projects 2014-SGR-966 and 2017-SGR-1127.
        
        
        
        
        99
        BFW
        M. Berta, O. Fawzi, and S. Wehner, 
        IEEE Trans. Inf. Theory 60, 1168 (2014).
        
        merging
        M. Horodecki, J. Oppenheim, and A. Winter, 
        Nature 436, 673 (2005); 
        Commun. Math. Phys. 269, 107 (2007).
        
        decoupling
        F. Dupuis, PhD thesis, arXiv[quant-ph]:1004.1641.
        
        decouple
        F. Dupuis, M. Berta, J. Wullschleger, and R. Renner, 
        Commun. Math. Phys. 328, 251 (2014).
        
        SW
        D. S. Slepian and J. K. Wolf, 
        IEEE Trans. Inf. Theory 19, 471 (1973).
        
        Bera et al
        M. N. Bera, A. Acín, M. Kuš, M. Mitchell, and M. Lewenstein,
        Rep. Prog. Phys. 80, 124001 (2017).
        
        SM
        See Supplemental Material for details, which includes 
        additional references <cit.>.
        
        Uhlmann
        A. Uhlmann,
        Rep. Math. Phys. 9, 273 (1976).
        
        FG
        C. A. Fuchs and J. van de Graaf, 
        IEEE Trans. Inf. Theory 45, 1216 (1999).
        
        gentle
        A. Winter,
        IEEE Trans. Inf. Theory 45, 2481 (1999).
        
        continuity
        R. Alicki and M. Fannes, 
        J. Phys. A: Math. Gen. 37,  L55 (2004).
        
        
        Er
        V. Vedral, M. B. Plenio, M. A. Rippin, and P. L. Knight, 
        Phys. Rev. Lett. 78, 2275 (1997).
        
        Schumacher
        B. W. Schumacher, 
        Phys. Rev. A 51, 2738 (1995).
        
        
        Winter-thesis
        A. Winter, Ph.D. dissertation, quant-ph/9907077 (1999).
        
        Ye
        M.-Y. Ye, Y.-K. Bai, and Z. D. Wang, Phys. Rev. A 78, 030302 (2008).
        
        Cover-Thomas
        T. A. Cover and J. A. Thomas, Elements of Information Theory, John Wiley and Sons, Inc. (2006). 
        
        pptkey
        K. Horodecki, M. Horodecki, P. Horodecki, and J. Oppenheim, 
        Phys. Rev. Lett. 94, 160502 (2005); 
        IEEE Trans. Inf. Theory 55, 1898 (2009).
        
        Christandl-thesis
        M. Christandl, PhD thesis, arXiv:quant-ph/0604183.
        
        Ben
        M. Ben-Or, M. Horodecki, D. W. Leung, D. Mayers, and J. Oppenheim, 
        Theory of Cryptography, TCC 2005, Lecture Notes in Computer Science, vol 3378, pp. 386-406 (Springer Verlag 2005).
        
        RK
        R. Renner and R. König, 
        Theory of Cryptography, TCC 2005, Lecture Notes in Computer Science, vol 3378, pp. 405-427 (Springer Verlag 2005).
        
        OHHH2001
        J. Oppenheim, M. Horodecki, P. Horodecki, and R. Horodecki, 
        Phys. Rev. Lett. 89, 180402 (2002).
           
        huge-delta
        M. Horodecki, P. Horodecki, R. Horodecki, J. Oppenheim, A. Sen(De), U. Sen, 
        and B. Synak-Radtke, 
        Phys. Rev. A 71, 062307 (2005).
        
        HZ
        M. Hayashi and H. Zhu,  Phys. Rev. A  97, 012302 (2018).
        
        
        JO
        J. Oppenheim, K. Horodecki, M. Horodecki, P. Horodecki, and R. Horodecki, 
        Phys. Rev. A 68, 022307 (2003).
        
        
        
        
        Smith G. Smith,
        arXiv[quant-ph]:1007.2855.
        
        Hastings
        M. B. Hastings,
        Nature Physics 5, 255 (2009).
        
        DiVincenzo-Qnonadditive
        D. P. DiVincenzo, P. W. Shor, and J. A. Smolin, 
        Phys. Rev. A 57, 830 (1998).
        
        Li-Winter
        K. Li, A. Winter, X.B. Zou, and G.C. Guo, 
        Phys. Rev. Lett. 103, 120501 (2009).
        
        Smith-privacy 
        G. Smith and J. A. Smolin, 
        Phys. Rev. Lett. 103, 120503 (2009).
        
        uni-additivity
        A. W. Cross, K. Li, and G. Smith, 
        Phys. Rev. Lett. 118, 040501 (2017).
        
        DJKR
        I. Devetak, M. Junge, C. King, and M. B. Ruskai,
        Comm. Math. Phys. 266, 37 (2006).
        
        Hayashi
        M. Hayashi, Quantum Information: An Introduction,
        Springer (2006).
        
        reverse-coh
        R. Garcia-Patron, S. Pirandola, S. Lloyd, and J. H. Shapiro, 
        Phys. Rev. Lett. 102, 210501 (2009).
        
        DevetakWinter-hash 
        I. Devetak and A. Winter, 
        Proc. R. Soc. Lond. A 461, 207 (2005). 
        
        MPRHorodecki
        M. Horodecki, P. Horodecki, and R. Horodecki,
        Phys. Rev. Lett. 85, 433 (2000).
        
        continuous-1
        S. Pirandola, R. Garcia-Patron, S. L. Braunstein, and S. Lloyd,
        Phys. Rev. Lett. 102, 050503 (2009).
        
        continuous-2
        S. Pirandola, R. Laurenza, C. Ottaviani, and L. Banchi,
        Nature Comm. 8, 15043 (2017).
        
        SKG
        K. P. Seshadreesan, H. Krovi, and S. Guha, 
        Phys. Rev. A 100, 022315 (2019).
        
        GW
        G. Gour, M. M. Wilde, arXiv:1808.06980 (2018).
        
        
        
        KW
        E. Kaur and M. M. Wilde,
        Phys. Rev. A 96, 062318 (2017).
        
        Junge1
        L. Gao, M. Junge, and N. LaRacuente,
        Comm. Math. Phys. 364, 83 (2018).
        
        Junge2
        L. Gao, M. Junge, and N. LaRacuente,
        J. Math. Phys. 59, 122202 (2018).
        
        GES
        K. Goodenough, D. Elkouss, and S. Wehner, 
        New J. Phys. 18, 063005 (2016).
        
        VA
        V. V. Albert et al, 
        Phys. Rev. A 97, 032346 (2018).
        
        Pirandola3
        S. Pirandola, R. Laurenza, and L. Banchi,
        Annals of Physics 400, 289 (2019).
        
        
        
        Pirandola5
        C. Ottaviani, R. Laurenza, T. P. W. Cope, G. Spedalieri, S. L. Braunstein, and S. Pirandola,
        Proc. SPIE 9996, Quantum Information Science and Technology II, 999609 (2016).
        
        hypothesis
        T. Cooney, M. Mosonyi, M. M. Wilde,
        Comm. Math. Phys. 344, 797 (2016).
        
        Holevo
        A. S. Holevo,
        J. Math. Phys. 43, 4326 (2002).
        
        Berta-ms
        M. Berta, Diploma thesis, arXiv[quant-ph]:0912.4495.
        
        elsewhere
        K. Horodecki, O. Sakarya, M. Winczewski, A. Winter, and D. Yang 
        (in preparation).
        
        Aberg
        J. Åberg, 
        arXiv:quant-ph/0612146.
        
        BCP
        T. Baumgratz, M. Cramer, and M. B. Plenio, 
        Phys. Rev. Lett. 113, 140401 (2014).
        
        WY
        A. Winter and D. Yang, 
        Phys. Rev. Lett. 116, 120404 (2016).
        
        ent-assist
        C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, 
        Phys. Rev. Lett. 83, 3081 (1999).
        
        EBC
        P. W. Shor,
        J. Math. Phys. 43, 4334 (2002).
        
        reverse-Shannon
         C. H. Bennett, I. Devetak, A. W. Harrow, P. W. Shor, and A. Winter,
        IEEE Trans. Inf. Theory 60, 2926 (2014).
        
        WWY
        M. M. Wilde, A. Winter, and D. Yang, 
        Comm. Math. Phys. 331, 593 (2014). 
        
        
        
        
        § SUPPLEMENTAL MATERIAL
        
        
        § A. MISCELLANEOUS FACTS AND LEMMAS
        
        In this appendix, we collect some standard facts about various functionals 
        we use and prove some lemmas that we need in the proofs of main results. 
        
        
        Recall that the fidelity between two mixed states is defined as
        
            F(ρ,σ): = √(ρ)√(σ)_1 
                              = √(√(ρ)σ√(ρ)),
        
        and the trace distance is 1/2ρ-σ_1.
        We use the notation Xϵ≈Y to mean X-Y_1≤ϵ.
        
        
        
        The fidelity is alternatively characterized by the relation
        
            F(ρ_A,σ_A) = max_U_B |⟨ϕ|_A⊗ U_B|ψ⟩|,
        
        where |ϕ⟩_AB and |ψ⟩_AB are purifications of ρ_A and 
        σ_A, respectively, and U_B ranges over unitaries.
        
        For any two states ρ and σ, 
        fidelity and trace distance are related by
        
            1-F(ρ,σ) ≤1/2ρ-σ_1 ≤√(1-F(ρ,σ)^2).
        
        
        For a subnormalized state ρ, i.e. ρ≥ 0 and ρ≤ 1, and operator 0≤ X≤, if ρ X≥ 1-λ, then
        
            ρ-√(X)ρ√(X)_1≤√(8λ) .
        
        
        For two states ρ_XY and σ_XY on H_X⊗ H_Y, if ρ_XY-σ_XY_1≤λ≤1, then 
        
            |S(X|Y)_ρ-S(X|Y)_σ|≤ 4λlog|X|+2h(λ),
        
        where h(λ):=-λlogλ-(1-λ)log(1-λ).
        
        
          Given a state ρ_AE, let ϵ>0 and :A→ B be a 
          CPTP map with Choi-Jamiołkowski representation 
          τ_RB=(𝕀_R⊗)Φ_RA. Then,
          
            ∫_U_A   (U_Aρ_AEU_A^†) - τ_B⊗ρ_E_1dU 
               ====≤ 2^-1/2[H^ϵ_min(A|E)_ρ+H^ϵ_min(R|B)_τ]
                                  +12ϵ,
        
          where the integral is over the Haar measure on the unitary group 𝒰(A).
         
        The function defined by g(ρ_AB):=S(ρ_AB)+E_r(ρ_AB) is non-decreasing under CLODCC.
         
        
        Here,
        
            E_r(ρ_AB):=min_σ_AB∈SEPS(ρ_ABσ_AB)
        
        is the relative entropy of entanglement <cit.>, where the minimum is taken over 
        the separable states (SEP), and D(XY)= X(log X-log Y) is the relative entropy.
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        In the proof of Lemma <ref>, we need the concept of typical operator and its properties. For a mixed state ρ, write it in its eigenbasis, ρ=∑_iλ_i|i⟩⟨i|. Consider n copies of the state,
        
            ρ^⊗ n=∑_i^nλ_i^n|i^n⟩⟨i^n|,
        
        where i^n=i_1i_2⋯ i_n. For δ>0, the typical projector is defined as
        
            Π_δ^n=∑_i^n∈ T_δ^n|i^n⟩⟨i^n|,
        
        where T_δ^n:={i^n:|-1/nlogλ_i^n-S(ρ)|≤δ}. The typical subspace is the supporting space of the the projector. From <cit.>, we have
        
            ρ^⊗ nΠ_δ^n≥1-ϵ,
            
            2^n[S(ρ)+δ]≥Π_δ^n≥(1-ϵ)2^n[S(ρ)-δ],
        
        with ϵ:=e^-cδ^2n and c a constant.
         
        For n copies of a pure tripartite state |ψ⟩_ABE, let Ã and B̃ be the typical subspaces of A^n and B^n respectively, and Π_Ã and Π_B̃ the typical projectors onto these typical subspaces, that is,
        
            Π_Ãψ_A^⊗ n≥1-ϵ,
            Π_B̃ψ_B^⊗ n≥1-ϵ.
        
        Denote 
        
            |Ω⟩_ÃB̃E^n   =Π_Ã⊗Π_B̃|ψ⟩_ABE^⊗ n,
            |Ψ⟩_ÃB̃E^n   =1/⟨Ω|Ω⟩|Ω⟩_ÃB̃E^n,
        
        and write Π_Ã and Π_B̃ in their eigenbasis respectively
        
            Π_Ã   =∑_i |i⟩⟨i|_Ã,
            Π_B̃   =∑_j |j⟩⟨j|_B̃,
        
        where |i⟩_Ã∈ H_A^n and |j⟩_B̃∈ H_B^n. By typicality in Eq. (<ref>), we have
        
            log|Ã|/n   ≈S(ψ_A),
            log|B̃|/n   ≈S(ψ_B).
        
        We now decompose H_A^n and H_B^n as
        
            H_A^n   = H_A_I⊗ H_A_P,
             H_B^n   = H_B_I⊗ H_B_P,
        
        by unitaries U:A^n→ A_IA_P and V:B^n→ B_IB_P satisfying
        
            U|i⟩_Ã   =|i⟩_A_I⊗|0⟩_A_P,
            
            V|i⟩_B̃   =|i⟩_B_I⊗|0⟩_B_P.
        
        Notice that |Ã|=|A_I| and |B̃|=|B_I|, so we get
        
            U⊗ V|Ψ⟩_ÃB̃E^n=|Ψ⟩_A_IB_IE^n⊗|0⟩_A_P⊗|0⟩_B_P.
        
        We call A_I, B_I the information parts, and A_P, B_P the purity parts.
        
        
        Given δ >0 and ϵ=e^-cδ^2n with a constant c, for n
        copies of a pure tripartite state |ψ⟩_ABE where n is large, and unitary operators U and V in Eqs. (<ref>) (<ref>), 
        
            U⊗ V(|ψ⟩⟨ψ|)^⊗ n U^†⊗ V^†-.
                .|Ψ⟩⟨Ψ|_A_IB_IE^n⊗|0⟩⟨0|_A_P⊗|0⟩⟨0|_B_P_1≤ 2ϵ+4√(ϵ),
        
        with log|A_I|/n=log|Ã|/n≈S(ψ_A), log|B_I|/n=log|B̃|/n≈S(ψ_B), and log|A_P|/n≈log |A|-S(ψ_A), log|B_P|/n≈log |B|-S(ψ_B), and all the entropy relations in |Ψ⟩_A_IB_IE^n is almost the same as those in |ψ⟩_ABE^⊗ n.
        
        By the operator inequality 
        
            _A^n⊗_B^n-Π_Ã⊗Π_B̃≤_A^n⊗(_B^n-Π_B̃)+(_A^n-Π_Ã)⊗_B^n,
        
        we get
        
            ⟨Ω|Ω⟩_ÃB̃E^n≥ 1-2ϵ.
        
        By Lemma <ref>, we have
        
            (|ψ⟩⟨ψ|)^⊗ n-|Ω⟩⟨Ω|_1≤4√(ϵ),
        
        from which, 
        
            (|ψ⟩⟨ψ|_ABE)^⊗ n-(|Ψ⟩⟨Ψ|)_ÃB̃E^n_1≤ 2ϵ+4√(ϵ)=:ϵ'
        
        that implies Ineq. (<ref>) under unitary operators U and V. 
        
        Notice that U and V are local unitaries, thus the entropies and the conditional entropies in ψ_ABE^⊗ n remain invariant. By the non-increasing property of trace norm for Ineq. (<ref>) and Lemma <ref> (including entropies), we get 
        
            |S(A|B)_ψ^⊗ n-S(A_I|B_I)_Ψ|≤ 4nϵ'log|A|+2h(ϵ'),
            
            |S(A)_ψ^⊗ n-S(A_I)_Ψ|≤ 4nϵ'log|A|+2h(ϵ'),
         
        and similar other relations. Notice that ϵ' is exponentially small in n, so we conclude that |Ψ⟩_A_IB_IE^n encodes almost all information in |ψ⟩_ABE^⊗ n.
        
        
         For a state ρ_AB, if global operations are allowed, 
        the randomness extraction rate is R_G(ρ_AB)=I_G(ρ_AB)=log|AB|-S(ρ_AB).
        It is clear that a pure state |0⟩ is the simplest ibit. So given a state ρ_AB, 
        if global operations are allowed, then we can obtain purity at the rate 
        I_G=log|AB|-S(ρ_AB), by data compression and algorithmic cooling <cit.>.
        From the purity the same amount of randomness can be obtained which implies R_G≥ I_G 
        
        On the other side, any randomness extraction ends up in a state close to α state of Eq. (<ref>), 
        on which we can undo the twisting U=∑_i,k|ik⟩⟨ik|_K_AK_B⊗ U_ik to get a pure state on the key part which means 
        I_G≥ R_G. So we conclude I_G=R_G.
        
        
        If states in an ensemble {p_i,ρ_i} are close to a fixed state σ on average, then most of the ensemble states are close to the fixed state. To be precise, if 
        ∑_i p_iρ_i-σ_1≤ϵ,
        
        then
        ∑_i: ρ_i-σ_1≤√(ϵ) p_i≥1-√(ϵ).
        
        This is an instance of Markov's inequality. It is obvious that 
        ∑_i: ρ_i-σ_1≥√(ϵ)√(ϵ)p_i
            ≤∑_ i: ρ_i-σ_1≥√(ϵ) p_iρ_i-σ_1 ≤ϵ,
        
        thus
        ∑_{i: ρ_i-σ_1≥√(ϵ)} p_i≤√(ϵ),
        
        concluding the proof.
        
        
        § B. PROOFS
        
        In this appendix, we provide the detailed proofs of the results claimed in the main text. 
        
        We begin with the precise definition of the rate of private randomness distillation, both in the standard picture and in the dual one. In the standard picture <cit.>, the protocol of extracting randomness from a bipartite state ρ_AE is to perform a unitary map U_A→ K_AA' followed by the measurement map
        
        M_A→ K_A⊗ I_E(·)=∑_i,j=1^|K_A||A'||i⟩⟨i|_K_A⊗⟨ij|(·)|ij⟩_K_AA'
        to approximate a state with log|K_A| randomness of the form 1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A⊗ρ_E, where H_A= H_K_A⊗ H_A' and {i}_K_A and {j}_A' is the computational basis for subsystem K_A and A' respectively, and ρ_E=_Aρ_AE. This is equivalent to performing the unitary U_A→ K_AA' operation followed by the partial tracing of A' and then a dephasing map on K_A in the computational basis Δ_K_A(·)=∑_i=1^|K_A|⟨i|(·)|i⟩_K_A|i⟩⟨i|_K_A. Notice that after the measurement map, the state of K_A represents the classical outcome, so it cannot be involved in any further quantum processing, otherwise any initial state in d-dimensional space can always be used to generate log d private random bits by a projective measurement in an arbitrary basis followed by a further measurement in the complementary basis. Extending to the distributed scenario, the protocol of extracting independent randomness from a pure tripartite state |ψ⟩_ABE is: i) Alice performs a unitary U_1: A→ A_1A_2 and sends A_2 through the dephasing channel to Bob; ii) Bob performs a unitary V_1: BA_2→ B_1B_2 and sends B_2 through the dephasing channel to Alice; iii) Alice and Bob start the second round with the new state |ψ^(2)⟩_A^(2)B^(2)E^(2)=W_B_2∘ V_1∘ W_A_2∘ U_1|ψ⟩_ABE, where W_X=∑_i=1^|X||i⟩_E_X|i⟩_X⟨i| is the isometry of the dephasing channel on X in the computational basis, and A^(2)=A_1B_2 and B^(2)=B_1, E^(2)=EE_A_2E_B_2; iv)  After some finite rounds, Alice and Bob perform local unitaries followed by the measurement map of the form (<ref>) to approximate a state with independent randomness log|K_A| at Alice's side and log|K_B| at Bob's side 1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A⊗1/|K_B|∑_i=1^|K_B||i⟩⟨i|_K_B⊗ψ_E_f, where ψ_E_f is the final reduced state at Eve. Randomness generated in the intermediate measurement is required to be private against the final state of Eve, therefore the measurement can be postponed to the final stage of the protocol. So does for the intermediate partial trace. Denote the operation class composed by the four steps as MCLODCC and we are ready to define the rate of private randomness distillation in the standard picture. 
        
        
        A protocol with {|K_A|, |K_B|,ϵ(n)}, which distills private randomness from n copies of |ψ⟩_ABE in the standard form, is an operation Λ̃_n∈ MCLODCC: A^nB^nE^n→ K_AK_BE^n_f, where |K_A| and |K_B| are the sizes of the randomness parts dependent on n and ϵ(n) is the error measured by the trace distance from the ideal standard form 
        
            Λ̃_n((|ψ⟩⟨ψ|_ABE^⊗ n)-ρ_K_AK_BE^n_f_1≤ϵ(n),
        
        where 
        
            ρ_K_AK_BE^n_f
            
            =1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A⊗1/|K_B|∑_i=1^|K_B||i⟩⟨i|_K_B⊗ψ_E^n_f.
        
        The pair rate (R_A, R_B) achieved by the protocol is defined as R_A=lim_n→∞log |K_A|/n and R_B=lim_n→∞log |K_B|/n, when lim_n→∞ϵ(n)= 0.
        
        
        Similarly we define the pair rate of private randomness distillation in the dual picture where the goal state is the α state and the allowed operations come from the CLODCC class.
        
        
        A protocol with {|K_A|, |K_B|,ϵ(n)}, which distills private randomness from n copies of |ψ⟩_ABE in the dual picture, is an operation Λ_n∈ CLODCC: A^nB^n→ K_AA'K_BB', where |K_A| and |K_B| are the sizes of the randomness parts and 
        ϵ(n) is the distance from the α_K_AA'K_BB' state
        
            Λ_n(ψ_AB^⊗ n)-α_K_AA'K_BB'_1≤ϵ(n),
        
        and
        
            α_K_AA'K_BB'
            
            =   1/|K_A||K_B|∑_i,j=1^|K_A|∑_k,ℓ=1^|K_B||i⟩⟨j|_K_A⊗|k⟩⟨ℓ|_K_B⊗ U_ikσ_A'B' U_jℓ^†.
        
        The pair rate (R_A, R_B) achieved by the protocol is defined as R_A=lim_n→∞log |K_A|/n and R_B=lim_n→∞log |K_B|/n, when lim_n→∞ϵ(n)= 0.
        
        From Definitions <ref><ref> and the proof of Lemma <ref>, we can establish a corollary that extracting private randomness in the two pictures are equivalent.
         
         If there exists a protocol to distill private randomness at the pair rate lim_n→∞(log |K_A|/n,log |K_B|/n), getting a   state that approximates the state ρ_K_AK_BE^n_f under MCLODCC in the standard picture, then there exists a protocol achieving the same pair rate, getting a state that approximates α_K_AA'K_BB' under CLODCC in the dual picture. The converse statement is true as well.  
          of Lemma <ref>.
        In the usual approach, a quantum state having two independent 
        random bits private against Eve is of the form
        ρ_K_AK_BE=1/4∑_i,j=0^1|i⟩⟨i|_K_A⊗|j⟩⟨j|_K_B⊗ρ_E.
        
        Consider a pure state |ϕ_K_AA'K_BB'E whose marginal state ϕ_K_AK_BE turns 
        into ρ_K_AK_BE after measuring subsystems K_A and K_B in the computational basis. 
        We denote the dephasing map in the computational basis by Δ, so the 
        dephased state of ϕ_K_AK_BE is 
        
            (Δ_K_A⊗Δ_K_B)ϕ_K_AK_BE:=
            ∑_ij|i⟩⟨i|_K_A⊗|j⟩⟨j|_K_B⊗⟨ij|ϕ_K_AK_BE|ij⟩_K_AK_B.
        
        When written in the computational basis, the global state has the form
        
          |ϕ_K_AA'K_BB'E=1/2∑_i,j=0^1|i⟩_K_A|j⟩_K_B⊗|ϕ_ij⟩_A'B'E.
        
        The dephased state is 
        
            ρ_K_AA'K_BB'E 
               = 1/4∑_i,j=0^1|i⟩⟨i|_K_A⊗|j⟩⟨j|_K_B⊗|ϕ_ij⟩⟨ϕ_ij|_A'B'E.
        
        Because ρ_K_AK_BE=_A'B'ρ_K_AA'K_BB'E is of the form Eq. (<ref>), 
        |ϕ_ij⟩_A'B'E satisfy the condition 
        _A'B'|ϕ_ij⟩⟨ϕ_ij|_A'B'E=ρ_E for 
        all i and j. Then, by the Schmidt decomposition, there exist unitary 
        operators U_ij acting on A'B' such that the following holds:
        
          |ϕ_ij_A'B'E=U_ij|ϕ_0_A'B'E,
        
        where |ϕ_0_A'B'E is a fixed purification for ρ_E. Using this 
        form and tracing the E part in Eq. (<ref>), 
        we get the state α_K_AA'K_BB' of the claimed structure. 
        A similar reasoning gives the state α_K_AA'B' 
        when random bit is only on one side. 
        
        The robust version of Lemma <ref> is also true in the following sense,
        which we state directly for general amounts of randomness for Alice and Bob:
        Let, for positive integers a and b,
        
            ρ_K_AK_BE      = 1/ab∑_i=0^a-1∑_j=0^b-1|i⟩⟨i|_K_A⊗|j⟩⟨j|_K_B⊗ρ_E, 
               α_K_AA'K_BB' = 1/ab∑_i,j=0^a-1∑_k,ℓ=0^b-1|i⟩⟨j|_K_A⊗|k⟩⟨ℓ|_K_B⊗ U_ikσ_A'B' U_jℓ^†,
        
        the ideal private randomness state and the ideal idit, respectively.
        They descend from the common pure state
        
          |ϕ_K_AA'K_BB'E = 1/√(ab)∑_i=0^a-1∑_j=0^b-1|i⟩_K_A|j⟩_K_B⊗ U_ij|ϕ_0⟩_A'B'E,
        
        with a suitable purification |ϕ_0⟩ of ρ_E, by which we mean 
        (Δ_K_A⊗Δ_K_B)ϕ_K_AK_BE=ρ_K_AK_BE, and |ϕ_K_AA'K_BB'E 
        is a purification of α_K_AA'K_BB': _E ϕ = α_K_AA'K_BB'.
        
        
          If a ccq-state ρ_K_AK_BE is such that 
          1/2ρ_K_AK_BE - ρ_K_AK_BE_1≤ϵ,
          then for any pure state |ϕ̃⟩_K_AA'K_BB'E satisfying 
          (Δ_K_A⊗Δ_K_B)ϕ̃_K_AK_BE=ρ̃_K_AK_BE,
          1/2ϕ̃_K_AA'K_BB' - α_K_AA'K_BB'_1 
                      ≤δ =√(f(ϵ)(2-f(ϵ)))
          with f(ϵ)→ 0 as ϵ→ 0, for an α of the form 
          (<ref>) with suitable σ_A'B' and unitaries U_ik acting on A'B'.
          
          Conversely, if α_K_AA'K_BB' is such that
          1/2α_K_AA'K_BB' - α_K_AA'K_BB'_1≤ϵ,
          then for any purification |ϕ̃⟩_K_AA'K_BB'E of α,
          1/2(Δ_K_A⊗Δ_K_B)ϕ̃_K_AK_BE - ρ_K_AK_BE_1 
                                                        ≤δ=√(ϵ(2-ϵ)),
          for a ρ of the form (<ref>) with a suitable ρ_E.
        
        
        For the forward direction, suppose the ccq-state 
        ρ_K_AK_BE=∑_ijp_ij|i⟩⟨i|_K_A⊗|j⟩⟨j|_K_B⊗ρ̃_E^ij 
        satisfies 1/2ρ_K_AK_BE - ρ_K_AK_BE_1≤ϵ. 
        We have a pure state 
        
            |ϕ̃⟩_K_AA'K_BB'E=∑_ij√(p_ij)|i⟩_K_A|j⟩_K_B|ϕ̃_ij⟩_A'B'E'
         
        such that (Δ_K_A⊗Δ_K_B)ϕ̃_K_AK_BE=ρ_K_AK_BE, 
        where |ϕ̃_ij⟩_A'B'E are the purifications of ρ̃_E^ij. 
        Denote a fixed purification of ρ_E as |ϕ_0⟩_A'B'E. 
        From Uhlmann's theorem <cit.>, we can choose unitaries U_ij on A'B' 
        satisfying ⟨ϕ̃_ij|U_ij|ϕ_0⟩=F(ρ̃_E^ij,ρ_E),
        and form the state |ϕ⟩_K_AA'K_BB'E in Eq. (<ref>), which is clearly 
        the purification for some α_K_AA'K_BB'. We claim that |ϕ̃⟩_K_AA'K_BB'E 
        is close to |ϕ⟩_K_AA'K_BB'E that is sufficient to prove ϕ̃_K_AA'K_BB' 
        is close to α_K_AA'K_BB'. 
        
        By the triangle inequality for the trace norm and its monotonicity under 
        partial trace, we get
        
            ∑_ij    p_ijρ̃_E^ij-ρ_E_1
               =∑_ij p_ij|ij⟩⟨ij|⊗ρ̃_E^ij-∑_ij p_ij|ij⟩⟨ij|⊗ρ_E_1
               ≤∑_ij p_ij|ij⟩⟨ij|⊗ρ̃_E^ij-1/ab∑_ij|ij⟩⟨ij|⊗ρ_E_1
               =
             +1/ab∑_ij|ij⟩⟨ij|⊗ρ_E-∑_ij p_ij|ij⟩⟨ij|⊗ρ_E_1
            ≤ 4ϵ.
        
        From Lemma <ref>, there exists a good index set 
        K={ij:ρ̃_E^ij-ρ_E_1≤√(4ϵ)}, 
        with ∑_ij∈ K p_ij≥ 1-√(4ϵ). We denote K̅ as the complement of K.
        From Lemma <ref>, we have ⟨ϕ̃_ij|U_ij|ϕ_0⟩≥ 1-√(ϵ) for every ij∈ K
        and ∑_ij∈ K√(p_ij)√(1/ab)≥ 1-ϵ. Then we compute the fidelity,
        
            ⟨ϕ̃|ϕ⟩   _K_AA'K_BB'E
               =    ∑_ij√(p_ij)√(1/ab)⟨ϕ̃_ij|U_ij|ϕ_0⟩
               ≥ (1-√(ϵ))∑_ij∈ K√(p_ij)√(1/ab)
               =    (1-√(ϵ))(∑_ij√(p_ij)√(1/ab)-∑_ij∈K̅√(p_ij)√(1/ab)) 
               ≥ (1-√(ϵ))[(1-ϵ)
                                      -1/2∑_ij∈K̅(p_ij
                                                                      +1/ab)] 
               ≥ (1-√(ϵ))[(1-ϵ)
                          -1/2∑_ij∈K̅(|p_ij-1/ab|
                                                                         +2p_ij)] 
               ≥ (1-√(ϵ))[(1-ϵ)-ϵ-√(4ϵ)]          
               =    (1-√(ϵ))(1-2ϵ-2√(ϵ))=:1-f(ϵ),
        
        where Ineq. (<ref>) comes from ⟨ϕ̃_ij|U_ij|ϕ_0⟩≥ 0 
        and ⟨ϕ̃_ij|U_ij|ϕ_0⟩≥ 1-√(ϵ) for ij∈ K, (<ref>) from √(x)√(y)≤1/2(x+y), (<ref>) from x-y≤|x-y|, and (<ref>) from 1/2∑_ij∈K̅|p_ij-1/ab|≤1/2∑_ij|p_ij-1/ab|≤ϵ and ∑_ij∈ K p_ij≥ 1-√(4ϵ). 
        Then we get, by monotonicity of the fidelity, that
        
            F(ϕ̃_K_AA'K_BB',α_K_AA'K_BB') ≥ 1-f(ϵ),
        
        and so
        
            1/2ϕ̃_K_AA'K_BB'-α_K_AA'K_BB'_1 
                                         ≤√(f(ϵ)(2-f(ϵ))) =: δ.
        
                                     
        For the opposite direction, we proceed in a simpler way,
        namely by Uhlmann's theorem we have that there exists a unitary V_E
        such that
        
            |⟨ϕ̃|⊗ V|ϕ⟩| 
                  = F(α_K_AA'K_BB',α_K_AA'K_BB')≥ 1-ϵ.
        
        Then we get, by monotonicity of the fidelity, that
        
            F((Δ_K_A⊗Δ_K_B)ϕ̃_K_AK_BE,
                   (Δ_K_A⊗Δ_K_B)(Vϕ_K_AK_BEV^†)) 
               ≥ 1-ϵ,
        
        and so
        
            1/2(Δ_K_A⊗Δ_K_B)ϕ̃_K_AK_BE
                         -(Δ_K_A⊗Δ_K_B)(Vϕ_K_AK_BEV^†)_1 
               ≤√(ϵ(2-ϵ)) =: δ.
        
        As before, (Δ_K_A⊗Δ_K_B)(Vϕ_K_AK_BEV^†) has 
        the same structure as ρ_K_AK_BE.
        
         
        Given ϵ,δ >0, for n
        copies of a pure tripartite state |ψ⟩_ABE where n is large, there exists a 
        unitary U:A^n→ KA' with a fixed basis {|i⟩} 
        of subsystem K, (U_A^n⊗_B^nE^n)|ψ⟩_ABE^⊗ n
           = ∑_i=1^|K|√(p_i)|i⟩_K|ψ_i⟩_A'B^nE^n, such that after measurement on K in the fixed basis,
        
            ∑_i=1^|K|p_i|i⟩⟨i|_K⊗ψ^i_B^n
                      - 1/|K|∑_i=1^|K||i⟩⟨i|_K⊗ψ_B^⊗ n_1
              ≤ϵ, 
            ∑_i=1^|K|p_i|i⟩⟨i|_K⊗ψ^i_E^n
                      - 1/|K|∑_i=1^|K||i⟩⟨i|_K⊗ψ_E^⊗ n_1
              ≤ϵ,
        
        when 1/nlog|K| = min{I(A:E)_ψ, I(A:B)_ψ}-δ.
        
        
        First we prove a one-shot version of Theorem <ref>.
        Namely, for a pure tripartite state |ψ_ABE, there exists a unitary 
        U:A→ KA' with  a fixed standard basis {|i⟩} of subsystem K, 
        such that the state of K after the von Neumann measurement simultaneously 
        decouples from Bob and Eve, as follows:
        
            ∑_i=1^|K|p_i|i⟩⟨i|_K⊗ψ^i_B
                        - 1/|K|∑_i=1^|K||i⟩⟨i|_K⊗ψ_B_1 
               =====≤ 2(2^-1/2[H^ϵ_min(A|B)_ψ+H^ϵ_min(R|K)_τ]+12ϵ),
        
            ∑_i=1^|K|p_i|i⟩⟨i|_K⊗ψ^i_E
                        - 1/|K|∑_i=1^|K||i⟩⟨i|_K⊗ψ_E_1 
               =====≤ 2(2^-1/2[H^ϵ_min(A|E)_ψ+H^ϵ_min(R|K)_τ]+12ϵ),
        
        where (U_A⊗_BE)|ψ⟩_ABE=∑_i=1^|K|√(p_i)|i⟩_K|ψ_i⟩_A'BE
        and τ_RK=(𝕀_R⊗ T)Φ_RA is the Choi-Jamiołkowski state of the 
        CPTP map
        
            T_A→ K(ρ)=∑_i|i⟩⟨i|(_A'ρ)|i⟩⟨i|,
        
        with A=A'K, that is tracing A' first and then performing a von 
        Neumann measurement on K. Notice that τ_K=_K/|K|. 
        Now borrowing the idea from <cit.>, and Lemma <ref>, it is 
        easy to see that more than half of the unitary operators U satisfy 
        Ineq. (<ref>) and more than half satisfy Ineq. (<ref>). 
        So there must exist a common unitary such that both inequalities are satisfied.  
        
        Now, by the asymptotic equipartition property, the ϵ-smooth 
        conditional min-entropy reduces to conditional entropy in the asymptotic 
        i.i.d. setting, and
        S(A|E)_ψ^⊗ n = n(S(B)-S(E)), 
        S(A|B)_ψ^⊗ n=n(S(E)-S(B)), as well as
        S(R|K)_τ=nS(A)-log|K| when we restrict to the typical subspace of 
        ψ_A^⊗ n. Counting the rates, we get that if 
        1/nlog|K| = min{I(A:B),I(A:E)}-δ, then the first term 
        will decay exponentially with n. So we can get randomness in K simultaneously 
        independent of Bob's and of Eve's system. 
        Remark  Theorem <ref> can be 
        generalized to multipartite states.
        
        
        
        Given ϵ, δ>0 and sufficiently large n,m, for a state 
        |ψ⟩_ABE satisfying S(A|B)>0>S(B|A), there exist local 
        unitaries U:A^n+m→ K_AA' and V:B^n+m→ K_BB', 
        and fixed bases {|i⟩}_K_A  and {|j⟩}_K_B,
        
            U⊗ V|ψ⟩_ABE^⊗ (n+m)
               =∑_i,j=1^|K_A|,|K_B|√(p_ij)|i⟩_K_A|j⟩_K_B|ψ_ij⟩_A'B'E^nE^m,
        
        so that after measurements on K_A,  K_B in the fixed bases,
        
            ∑_i,j p_ij|ij⟩⟨ij|_K_AK_B⊗ψ^ij_E^nE^m-_K_A/|K_A|⊗_K_B/|K_B|⊗ψ_E^⊗ (n+m)_1 
            ≤   f'(ϵ):=2ϵ+5√(2ϵ)+2√(4√(2ϵ)-2ϵ),
        
        
        
        
        assuming log|K_A|=nI(A:B)-nδ and log|K_B|=min{mI(B:A),mI(B:E)+2nS(B)}-mδ. By choosing m/n=-S(B|A)/S(B), log|K_B|=mI(A:B)-mδ.
        
        Here S(A|B)>0>S(B|A) implies that I(A:E)>I(A:B)>I(B:E). From Theorem <ref>, we know that Alice can distill private randomness at the rate I(A:B) but Bob cannot achieve the rate I(A:B) directly. In the proof of Theorem <ref>, we will see that I(A:B) is the optimal rate at which private randomness can be distilled from the information part. To that end, Bob will make use of the local noise created from Alice's randomness distillation. 
        
        
        Essentially Theorem <ref> says that Theorem <ref> is 
        composable in the following way. Suppose n copies of |ψ⟩_ABE 
        and m copies of |ψ⟩_ABE are given. 
        From Theorem <ref>, we know that Alice can get nI(A:B)_ψ
        bits of randomness in K_A from 
        |ψ⟩_ABE^⊗ n. Notice that Bob could virtually regard his 
        state ψ_B^⊗ n as local noise in the sense that it is entangled 
        with A'E even assuming A' is at Eve's control which is the worst case 
        (but of course Eve does not really have access to A' whose state may 
        have information on the randomness). And he can make use of this noise 
        to help extract randomness with the fresh state |ψ⟩_ABE^⊗ m, 
        where the randomness in subsystem K_B will decouple from the system A'E. 
        All together, the randomness in K_A and K_B is independent and secure 
        against Eve. 
        
        The first step is for Alice to extract randomness from |ψ⟩_ABE^⊗ n. 
        From Theorem <ref>, we know that there exists 
        a unitary U:A^n→ K_AA' such that 
        
        U|ψ⟩_ABE^⊗ n
           = ∑_i=1^|K_A|√(p_i)|i⟩_K_A|ψ_i⟩_A'B^nE^n,
        
        satisfying 
        ∑_i=1^|K_A|p_i|i⟩⟨i|_K_A⊗ψ^i_B^n
                  - 1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A⊗ψ_B^⊗ n_1
          ≤ϵ,
        ∑_i=1^|K_A|p_i|i⟩⟨i|_K_A⊗ψ^i_E^n
                  - 1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A⊗ψ_E^⊗ n_1
          ≤ϵ, 
        when log|K_A|=n[I(A:B)-δ]. 
        By the monotonicity of trace norm, we have 
        
            ∑_i=1^|K_A|p_i|i⟩⟨i|_K_Aϵ≈1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A .
        
        By triangle inequality of the trace norm, we then get
        
            1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A⊗ψ^i_B^n2ϵ≈1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A⊗ψ_B^⊗ n.
        
        From Lemma <ref>, we have 
        ∑_i: ψ^i_B^n√(2ϵ)≈ψ_B^⊗ n1/|K_A|≥ 1-√(2ϵ).
        
        Similarly we have
        ∑_i: ψ^i_E^n√(2ϵ)≈ψ_E^⊗ n1/|K_A|≥ 1-√(2ϵ).
        
        For both to be true, we have
        ∑_K_A1/|K_A|≥ 1-2√(2ϵ),
        
        where 
        K_A:={i: ψ^i_B^n√(2ϵ)≈ψ_B^⊗ n & ψ^i_E^n√(2ϵ)≈ψ_E^⊗ n}.
        Denoting R_A=[K_A]∖K_A, we can write
        
            1/|K_A|∑_i=1^|K_A||i⟩⟨i|_K_A   ⊗ψ^i_A'B^nE^n
               = 1/|K_A|∑_i∈K̃_A|i⟩⟨i|_K_A⊗ψ^i_A'B^nE^n
               =
                + 1/|K_A|∑_i∈ R_A|i⟩⟨i|_K_A⊗ψ^i_A'B^nE^n.
        
        
        The next step is for Bob to extract randomness by applying a unitary 
        V: B^(n+m)→ K_BB' to the state 
        |ϕ⟩_B^n(A'E^n)⊗|ψ⟩_ABE^⊗ m, 
        where A'E^n is virtually at Eve's side and |ϕ⟩_B^n(A'E^n) 
        is any state satisfying ϕ_B^n=ψ_B^⊗ n. We assume a unitary W: A'E^n→ E_v^n such that W|ϕ⟩_B^n(A'E^n)=|ϕ⟩_BE_v^⊗ n. From Theorem <ref>, we have
        
            V|ϕ⟩_BE_v^⊗ n⊗|ψ⟩_ABE^⊗ m=∑_j=1^|K_B|√(q_j)|j⟩_K_B|ϕ_j⟩_B'A^mE_v^nE^m,
        
        satisfying
        
            ∑_j=1^|K_B|q_j|j⟩⟨j|_K_B⊗ϕ^j_A^m-1/|K_B|∑_j=1^|K_B||j⟩⟨j|_K_B⊗ψ_A^⊗ m_1 
                     ≤ϵ,
               ∑_j=1^|K_B|q_j|j⟩⟨j|_K_B⊗ϕ^j_E_v^nE^m. 
               =====. -∑_j=1^|K_B|1/|K_B||j⟩⟨j|_K_B⊗ϕ_E_v^⊗ n⊗ψ_E^⊗ n_1 
              ≤ϵ,
        
        when log|K_B|=min{mI(B:A), mI(B:E)+2nS(B)}-mδ. Here the additional term 2nS(B) comes from the mutual information between B^n and E_v^n in the state of noise |ϕ⟩_BE_v^⊗ n. Applying W^†: E_v^n→ A'E^n to reverse the action of W does not change the above relations but recover states on A'E^n. Thus Theorem <ref> can be applied though |ϕ⟩_B^n(A'E^n) is not of product form. Notice that V is determined entirely by Bob's local states ϕ_B^n=ψ_B^⊗ n and 
        |ψ⟩_ABE^⊗ m, and is independent of the local state ϕ_A'E^n. 
        Thus Bob can apply V blindly to all states of the form 
        |ψ_i⟩_A'B^nE^n⊗|ψ⟩_ABE^⊗ m. 
        
        Suppose now that
        
            V|ψ_i⟩_B^n(A'E^n)⊗|ψ⟩_ABE^⊗ m=∑_j=1^|K_B|√(q_j|i)|j⟩_K_B|ψ_j|i⟩_B'A^mA'E^nE^m.
        
        For i∈K̃_A, we have 
        ψ^i_B^n√(2ϵ)≈ψ_B^⊗ n=ϕ_B^n. 
        Using Uhlmann's theorem (precisely, first using Lemma <ref>, then Lemma <ref>),  
        there exist unitary operators W_i acting on A'E^n such that the purification 
        W_i(ϕ_B^n(A'E^n))W_i^†=ϕ^i_B^n(A'E^n)ϵ'≈ψ^i_B^n(A'E^n) 
        with ϕ^i_B^n=ψ_B^⊗ n and 
        ϕ^i_A'E^nϵ'≈ψ^i_A'E^n, where 
        ϵ'=√(4√(2ϵ)-2ϵ). Then we have
        
        V|ψ_i⟩_B^n(A'E^n)⊗|ψ⟩_ABE^⊗ mϵ'≈V⊗ W_i|ϕ⟩_B^n(A'E^n)⊗|ψ⟩_ABE^⊗ m.
        
        From Eq. (<ref>), we get
        
            ∑_jq_j|i   |j⟩⟨j|_K_B⊗ψ^j|i_A'E^nE^m
               ϵ'≈∑_jq_j|j⟩⟨j|_K_B⊗ W_iϕ^j_A'E^nE^mW^†_i 
               ϵ≈1/|K_B|∑_j|j⟩⟨j|_K_B⊗ W_iϕ_A'E^nW^†_i⊗ψ_E^⊗ m
               ϵ'≈1/|K_B|∑_j|j⟩⟨j|_K_B⊗ψ^i_A'E^n⊗ψ_E^⊗ m,
        
        where Eq. (<ref>) comes from Eq. (<ref>) and the monotonicity of trace norm 
        under the dephasing operation on K_B and tracing out A^m, 
        Eq. (<ref>) from (<ref>), and Eq. (<ref>) from 
        W_iϕ_A'E^nW^†_i=ϕ^i_A'E^nϵ'≈ψ^i_A'E^n.
        Summing the errors, we have for i∈K̃_A
            ∑_jq_j|i   |j⟩⟨j|_K_B⊗ψ^j|i_A'E^nE^m
               2ϵ'+ϵ≈1/|K_B|∑_j|j⟩⟨j|_K_B⊗ψ^i_A'E^n⊗ψ_E^⊗ m.
        
        
        For i∈K̃_A, we also have 
        ψ^i_E^n√(2ϵ)≈ψ_E^⊗ n, 
        and by monotonicity of the trace norm under tracing out A',
        
            ∑_jq_j|i   |j⟩⟨j|_K_B⊗ψ^j|i_E^nE^m
               2ϵ'+ϵ≈1/|K_B|∑_j|j⟩⟨j|_K_B⊗ψ^i_E^n⊗ψ_E^⊗ m
               √(2ϵ)≈1/|K_B|∑_j|j⟩⟨j|_K_B⊗ψ_E^⊗ n⊗ψ_E^⊗ m
               =1/|K_B|∑_j|j⟩⟨j|_K_B⊗ψ_E^⊗ (m+n).
        
        Summing the errors, we get
        
            ∑_jq_j|i   |j⟩⟨j|_K_B⊗ψ^j|i_E^nE^m
               ϵ”≈1/|K_B|∑_j|j⟩⟨j|_K_B⊗ψ_E^⊗ (m+n),
        
        where ϵ”:=2ϵ'+ϵ+√(2ϵ).
        
        Now combining the two steps and considering the dephasing state, we get
        
            ∑_i∈K_A   p_i |i⟩⟨i|_K_A⊗∑_j∈K_Bq_j|i|j⟩⟨j|_K_B⊗ψ^j|i_E^nE^m
               ϵ≈1/|K_A|∑_i∈K_A|i⟩⟨i|_K_A⊗∑_j∈K_Bq_j|i|j⟩⟨j|_K_B⊗ψ^j|i_E^nE^m
               =
             1/|K_A|∑_i∈K̃_A|i⟩⟨i|_K_A⊗∑_j∈K_Bq_j|i|j⟩⟨j|_K_B⊗ψ^j|i_E^nE^m
               =
             +1/|K_A|∑_i∈R_A|i⟩⟨i|_K_A⊗∑_j∈K_Bq_j|i|j⟩⟨j|_K_B⊗ψ^j|i_E^nE^m
               ϵ”≈1/|K_A|∑_i∈K̃_A|i⟩⟨i|_K_A⊗1/|K_B|∑_j|j⟩⟨j|_K_B⊗ψ_E^⊗ (n+m)
               =
             +1/|K_A|∑_i∈R_A|i⟩⟨i|_K_A⊗∑_j∈K_Bq_j|i|j⟩⟨j|_K_B⊗ψ^j|i_E^nE^m
               4√(2ϵ)≈1/|K_A|∑_i∈K_A|i⟩⟨i|_K_A⊗1/|K_B|∑_j|j⟩⟨j|_K_B⊗ψ_E^⊗ (n+m),
        
        where Eq. (<ref>) comes from ∑_i∈R_A1/|K_A|≤ 2√(2ϵ) 
        and ρ_1-ρ_2_1 ≤ 2 for any two states.
        We sum up all the errors and get
        
            ∑_i∈K_Ap_i|i⟩⟨i|_K_A⊗∑_j∈K_Bq_j|i|j⟩⟨j|_K_B⊗ψ^j|i_E^nE^m.
               =. -1/|K_A|∑_i∈ K_A|i⟩⟨i|_K_A⊗1/|K_B|∑_j∈ K_B|j⟩⟨j|_K_B⊗ψ_E^⊗ (n+m)_1  
               ====≤  2ϵ+5√(2ϵ)+2√(4√(2ϵ)-2ϵ)=:f'(ϵ).
        
        The protocol can be composed iteratively in a new round by tackling the indices of K_AK_B together. Notice that only the existence of the good index set is required in the proof, which is used to construct the ideal control state. Alice and Bob need not know how to select the good index set because the unitary operation, as explained by argument below Eq. (<ref>), depends only on the average local state. Thus they can apply the decoupling unitary locally such that the dephasing state on the randomness subsystem will approximate the ideal randomness state. Indeed iterating the protocol in finite rounds renders the security of the “ping-pong” protocol in the proof of Theorem <ref>.
        
         of Theorem <ref>.
        We first prove it for the setting 1) of no noise and no communication. 
        The other three settings can be reduced to setting 1), making
        a couple of simple observations.
        
        The proof for setting 1) proceeds by the analysis of four cases. A common feature is that Alice and Bob preprocess their states by Lemma <ref>, separating the purity parts that can be exchanged when dephasing channels are allowed, and the information parts that contain 
        the correlation. The private randomness contributed from purity part is equal to the purity. Then we only need to deal with the information part and apply iteratively Theorem <ref> for the special state ψ_A_IB_IE satisfying the conditions S(B_I)=log|B_I| and S(A_I)=log|A_I|. When I(A:B)≤ I(A:E) or I(A:B)≤ I(B:E), we can distill private randomness at the rate I(A:B) without need of local noise. Otherwise, we will employ or create local noise such that the rate is still equal to I(A:B) by noticing that local noise implies increasing I(A:E) or I(B:E) but keeping I(A:B) invariant. Then we need Theorem <ref> to guarantee that the randomness generated at both sides is independent.
        
        Case 1. S(A|E)<0 and S(B|E)< 0: By the duality relation between conditional entropies of a pure tripartite state |ψ⟩_ABE, that is S(A|E)+S(A|B)=0 and S(B|E)+S(B|A)=0, 
        The claimed region is
        
            R_A          ≤log|A| - S(A|B), 
            
              R_B          ≤log|B| - S(B|A), 
            
              R_A + R_B    ≤ R_G.
        
        The extremal points are given by the rate pairs (R_A,R_B)=(log|A|+S(B)-S(AB),log|B|-S(B))
        and (R_A,R_B)=(log|A|-S(A),log|B|+S(A)-S(AB)). The first point is simply achieved by Alice extracting randomness from her
        local purity part at rate log|A|-S(A) and from the information part I(A:B) by Theorem <ref>, and Bob 
        just extracting randomness from the local purity part at rate log|B|-S(B). Exchanging the role gives the second point.   
        The rate region is achieved by time-sharing. Time-sharing is a technique used in the asymptotic iid setting in information theory. By sharing time in a sense that for np out of n runs, protocol 1 is performed, and for n(1-p) out of n, protocol 2 is performed, if the rates R_1 and R_2 are achievable in protocol 1 and 2 respectively, then the rate R=pR_1+(1- p)R_2 with 0<p<1 is also achievable <cit.>.
        
        Case 2. S(A|E)< 0 and S(B|E)≥ 0: By the duality relation, the claimed region is 
        
            R_A          ≤log|A| - S(A|B), 
            
              R_B          ≤log|B|, 
            
              R_A + R_B    ≤ R_G.
        
        One of the extremal points is (log|A| - S(A|B), log|B|-S(B)) by the same 
        protocol as above. The other extremal point is (log|A|-S(AB),log|B|), which
        is achieved as follows:
        Alice distills local purity from all copies, then distills randomness from pn copies 
        of the informational part by Theorem <ref>. This produces 
        R_A=log|A|-S(A)+pI(A:B) of randomness on Alice's side, and at the same time creates local noise ψ^⊗ pn_(A'E):B for Bob; Then Bob extracts randomness from the state ψ^⊗ (1-p)n_ABE⊗ψ^⊗ pn_(A'E):B=:ψ'. The randomness comes from local purity for all copies that contribute the rate log|B|-S(B), and the informational part for (1-p)n copies under the assistance of local noise ψ^⊗ pn_(A'E):B. By Theorem <ref>, if we choose p satisfying the
        I(B:E)_ψ'=I(B:A)_ψ', i.e. (1-p)S(B|E)-pS(B)=0 then it will produce (1-p)I(A:B) of randomness from the informational part. The sum of  the two parts gives log|B| on Bob. Replacing p in R_A then gives R_A=log|A|-S(AB). That the randomness at both sides is independent and private against Eve comes from Theorem <ref>.
        
        
        Case 3. S(A|E)≥ 0 and S(B|E)< 0 is analogous to case 2.
        
        Case 4. S(A|E)> 0 and S(B|E)> 0: The claimed region is
        
            R_A          ≤log|A|, 
            
              R_B          ≤log|B|, 
            
              R_A + R_B    ≤ R_G.
        
        Its extremal points are (R_A,R_B)=(log|A|,log|B|-S(AB))
        and (R_A,R_B)=(log|A|-S(AB),log|B|). 
        We suppose Alice and Bob preprocess their states by local compression,
        separating the purity parts and the information parts that contain 
        the correlation. We only deal with the information part. Neither Alice nor Bob 
        can directly distill randomness at the rate I(A:B). We will show the “ping-pong” protocol achieves the two extremal points. 
        Alice and Bob will take a “ping-pong” strategy 
        to help each other obtain required virtual local noise between Alice and Eve, and Bob 
        and Eve in order to distill randomness at the rate I(A:B). It is an activation process and it works only 
        if the process could be amplified to more and more copies. So it 
        has to satisfies some constraints. However finally we find that the constraint 
        is always satisfied. So there is no constraint at all!   
        
        In detail, the “ping-pong” protocol works as follows: suppose that initially Bob puts x of his copies into his shield system (the copies 
        consumed will be negligible when we count the rate at the end) and will not use 
        them any more. Alice can imagine Bob's x part is in Eve's hands, i.e. ψ_A:(BE)^⊗ x, so she would 
        share xS(A) ebits with Eve by her x systems. Then Alice distills randomness on 
        n_1 fresh copies using xS(A)=1 ebits. Now we apply Theorem <ref> to the state ψ_ABE^⊗ n_1⊗ψ_A:(BE)^⊗ x. If n_1 satisfies n_1I(A:B)=n_1I(A:E)+2, i.e. n_1S(A|E)=1, then Alice can distill randomness at the rate I(A:B). Notice that the rate would be I(A:E) if no local noise is used, which is less than I(A:B) from the condition S(A|E)>0. In this sense we say that   
        one ebit can boost randomness distillation of n_1 copies at the rate I(A:B). 
        Alice's randomness distillation on n_1  copies creates new virtual ebits between Bob and Eve, the number of which is 
        n_1S(B). Then Bob distills randomness on n_2 fresh copies under 
        the assistance of n_1S(B) ebits, where n_2 satisfies n_2S(B|E)=n_1S(B). 
        After Bob's action, Alice would virtually share n_2S(A) ebits with Eve. This
        is one round. The process can be amplified if n_2S(A)>1, which reads S(A)S(B)>S(A|E)S(B|E). 
        This is always satisfied, unless we are in a trivial situation.
        By symmetry, if Bob does first, still we have the same constraint 
        (i.e., no constraint). Now consider the initial step is performed on xK copies, 
        where K is large such that Theorem <ref> is applied. Because at any step of 
        any round, the extraction randomness rate is the same equal to I(A:B), 
        so overall the rate is also I(A:B). In addition with the local purity, the sum 
        achieves the global purity. 
        
        Now we compute the rate: denote r:=S(A)S(B)/S(A|E)S(B|E)>1. Suppose 
        the “ping-pong” protocol ends at Alice's side after L rounds with a large 
        finite number L. Then Alice gets the randomness from N_A copies 
        where
        
            N_A    = n_1+n_3+⋯+n_L+1
               = K/S(A|E)(1+r+r^2+⋯+r^L+1) 
               = K/S(A|E)r^L+2-1/r-1,
        
        and Bob from
        
            N_B    = n_2+n_4+⋯+n_L                               
               = KS(B)/S(A|E)S(B|E)(1+r+r^2+⋯+r^L) 
               = KS(B)/S(A|E)S(B|E)r^L+1-1/r-1,
        
        and the total number of copies is N=N_A+N_B. The randomness rate depends only 
        on the proportion of copies that randomness distiallion is performed on. So 
        N_B/N_A≈S(B)/rS(B|E)=S(A|E)/S(A) and 
        N_A/N=S(A)/I(A:B) for large L. Thus we get  
        R_A=N_A/NI(A:B)+log|A|-S(A)=log|A| and R_B=log|B|-S(AB);
        exchanging the role of Alice and Bob we get the rate pair (log|A|-S(AB),log|B|). That the randomness generated at both sides is independent and secure against Eve comes from Theorem <ref>.
        
        
         Proofs for the other settings.
        
        2) Free noise but no communication means that we are effectively applying
        the result in setting 1) to states ρ_AB⊗/|A'|⊗/|B'| 
        with large local dimension of A' and B' instead of ρ_AB. In this way,
        the two conditional entropies S(AA'|BB') and S(BB'|AA') in setting 1) can be made positive while the local dimension increases,
        hence the entire rate region becomes
        
            R_A          ≤log|A| - S(A|B) , 
            
              R_B          ≤log|B| - S(B|A) , 
            
              R_A + R_B    ≤ R_G = log|AB| - S(AB).
        
        
        3) Free noise and free communication: The rate region is 
        characterised by 
        
        
            R_A≤ R_G, R_B≤ R_G, and R_A+R_B≤ R_G,
        
        i.e. the entire global purity can be realised on either side as
        randomness (but not necessarily as purity!). To see this consider
        an extreme point of the free-noise region, Eq. (<ref>):
        R_A=log|A|-S(AB)+S(B)=log|A|-S(A)+I(A:B), R_B=log|B|-S(B). 
        In this case, Bob's entire randomness, and the part log|A|-S(A) of Alice
        are realised as purity obtained by first compressing their respective systems.
        But purity can be exchanged freely via the dephasing channel, so 
        the rate sum can be concentrated at Alice's side. Similarly for Bob.
        
        4) For free communication but no noise we have only an achievable
        region from combining setting 1) with the sharing of purity
        observed in setting 3): We can certainly achieve all rate pairs with
        
            R_A          ≤log|A| - max{S(B),S(AB)} , 
            
              R_B          ≤log|B| - max{S(A),S(AB)} , 
            
              R_A + R_B    ≤ R_G = log|AB| - S(AB).
        
         Proof of tightness.
        We prove the tightness of the rate regions in three of these settings:
        scenario 1), scenario 2), and scenario 3),
        but leave 4) open.
        In all settings, R_A+R_B ≤ R_G = log|AB|-S(AB), which clearly cannot
        be beaten, even if Alice and Bob can freely cooperate. 
        For setting 3): It clearly cannot be improved, because R_G is reached 
        for both parties, and nothing can be better. 
        Setting 2): Since there is no communication, whatever Alice does, she cannot effect the purity log|B|-S(B) of Bob's state which can be used to  generate randomness. Hence R_A ≤ R_G - (log|B|-S(B)) = log|A|-S(A|B). Similarly  
        for Bob's rate. 
        Setting 1): Even with free noise, R_A ≤log|A|-S(A|B), so
        this bound is still true without free noise. But also R_A ≤log|A| always because
        Alice has only her system A to work on. So R_A is bounded by 
        the minimum of the two; likewise for Bob.
        
        
        We arrive at the form of the one-sided irreducible ibit states by which 
        we mean that all the randomness is in the key part at Alice's side and no extra randomness 
        can be gained from the shield part. So any optimal protocol must reach 
        this kind of state, asymptotically. 
        
        
        Every irreducible ibit state with randomness only on Alice's side, is of the form
        
            α_K_AA'B' = 1/|K_A|∑_i,j=1^|K_A||i⟩⟨j|_K_A⊗1/|A'||B'|U_iU_j^†,
        
        where U_i are unitaries acting on A'B'.
        
        Suppose the purification for the irreducible state is |ϕ_K_AA'B'E, 
        where the randomness part is K_A and A'B' is the shield part. 
        From the form of α_K_AA'B', we know
        
            |ϕ_K_AA'B'E=1/√(|K_A|)∑_i=1^|K_A||i⟩_K_A⊗ U_i|ϕ_0⟩_A'B'E.
        
        Because it is an irreducible state which means the optimal rate of 
        randomness that can be extracted under CLODCC is log |K_A|, and so no protocol 
        can produce more than log |K_A| bits of randomness. 
        Now consider the Berta-Fawzi-Wehner protocol <cit.>,
        which is naturally a CLODCC protocol where Bob does nothing. 
        It creates log|K_A|+log|A'|+S(AA'|E)_- bits which should be not larger 
        than log |K_A|, where we use the denotation [t]_-=min{0,t}. Then we get log|A'|+S(K_AA'|E)_-≤ 0 that implies 
        S(K_AA'|E)=S(B')-S(E)≤ 0. So we have log|A'|+S(B')-S(E)≤ 0. 
        Notice that α_B'=1/|B'| (or Bob can do local compression 
        to get purity and send the purity to Alice), and 
        S(E)=S(A'B')_ϕ_i≤ S(A')_ϕ_i+S(B')_ϕ_i≤log|A'|+log|B'| for every |ϕ_i⟩_A'B'E=U_i|ϕ_0⟩_A'B'E. Then  the equality holds 
        if and only if ϕ_iA'B'=1/|A'|_A'⊗1/|B'|_B' for every |ϕ_i⟩_A'B'E, which means that |ϕ_i⟩_A'B'E=U_iE_1E_2^⊤|Φ⟩_A'E_1⊗|Φ⟩_B'E_2=U_iA'B'|Φ⟩_A'E_1⊗|Φ⟩_B'E_2, where U_iE_1E_2^⊤ is the transpose of U_iE_1E_2. Tracing out the E part, we get the desired form.
        
        From Lemma <ref>, it is clear the last step of an optimal protocol 
        is VQSM when Eve's system is included. 
        The irreducible form shows that entropy of Eve is not less than Bob's entropy. 
        
        
         of Theorem <ref>.
        Denote the quantity at the right-hand side as .
        
        “R_A≥”: For any CLODCC that transforms n copies of ρ_AB to 
        a state σ_A'B' whose purification is denoted as |ϕ⟩_A'B'E'. 
        We notice that in the case of free communication and no noise in the two-side 
        randomness scenario, Alice can get randomness at rate 
        
            log|A'B'|-   max{S(B'),S(E')}
               = nlog|AB|-max{S(B'),S(E')},
         
        which holds because under CLODCC, Alice and Bob can only exchange
        qubits, but the total number of their shared degrees of freedom remains 
        constant.
        So we have R_A≥sup_n [log|AB|-max{1/n S(B'),1/n S(E')}],
        which is the RHS.
        
        “R_A≤”: Given n copies of ρ_AB, a protocol to extract 
        randomness ends in a state ω_KA'B' that is close to the state 
        α_KA'B'=1/K∑_i,j=1^K|i⟩⟨j|_K⊗ U_iσ_A'B'U_j^† 
        in the sense that ω_KA'B'-α_KA'B'_1 ≤ϵ(n)→ 0 (as n→∞). 
        Now suppose the purifying state for ω_KA'B' is ω_E'. 
        From the continuity of entropy, we get 
        
            |S(ω_KA'B')-S(α_KA'B')|≤ϵ(n)log|AB|^n+h(ϵ(n)),
        
        which amounts to
        
            |S(ω_E')-S(α_E')|    ≤ϵ(n)log|AB|^n+h(ϵ(n)),  and
            
              |S(ω_B')-S(α_B')|    ≤ϵ(n)log|B'|+h(ϵ(n)).
        
        From the structure of α_KA'B', we know that 
        S(α_E')=S(σ_A'B')≤log|A'B'|. Hence,
        
            log|K|   =log|KA'B'|-log|A'B'| 
               ≤ nlog|AB|-S(α_E') 
               ≤ nlog|AB|-S(ω_E')+ϵ(n)log|AB|^n+h(ϵ(n)).
        
        Thus we have
        
            1/nlog|K| ≤log|AB|-1/n S(ω_E')+ϵ(n)log|AB|+h(ϵ(n)).
         
        At the same time we have 
        
            1/nlog|K|    ≤log|AB|-1/nlog|B'| 
               ≤log|AB|-1/n S(α_B') 
               ≤log|AB|-1/n S(ω_B')+ϵ(n)log|AB|+h(ϵ(n)).
        
        Take the supremum over n, and notice that if for a finite n, the supremum is 
        obtained, then for any mn, it is achieved. So we get R_A=sup_n 1/nlog|K| ≤.
        
         of Theorem <ref>.
        First we prove that the optimal randomness that can be extracted from ρ_AB on Alice's 
        side is upper bounded as
        
            R_A(ρ) ≤log|AB|-max{1/2[E_r^∞(ρ_AB)+S(AB)], S(AB)},
        
        where E_r(ρ)=inf_σρ(logρ-logσ), σ running over separable states,
        and E^∞_r(ρ)=lim_n→∞1/nE_r(ρ^⊗ n)
        are the relative entropy of entanglement <cit.> and its regularisation. Then from E^∞_r(ρ_AB)≥max{S(A)-S(AB),S(B)-S(AB)}<cit.>, we get 
        
        the easy upper bound R_A(ρ)≤log|AB|-1/2max{S(A),S(B)}. 
        
        
        
        
        It is straightforward to see that the randomness R_A that can be extracted 
        on Alice's side is not larger than the randomness extracted by global operation 
        which is equal to the global purity. So R_A(ρ)≤log|AB|-S(AB). Suppose 
        that for n copies of ρ_AB whose purification is |ϕ⟩_ABE, 
        with E on Eve's side, we get an approximate irreducible state α̃_KA'B' 
        under CLODCC operations, where K is the randomness part and A'B' is the shield 
        part, KA' is on Alice's side and B' on Bob's, and its purification part is 
        denoted as E'. Then,
        
            log   |K| ≤ nlog|AB|-S(E'),
               =   nlog|AB|-[S(E')-nS(E)]-nS(E),
               ≤ nlog|AB|-[E_r(ρ_AB^⊗ n)-E_r(α̃_KA':B')]-nS(E),
               ≤ nlog|AB|-E_r(ρ_AB^⊗ n)-nS(E)+S(B'),
               ≤ nlog|AB|-E_r(ρ_AB^⊗ n)-nS(E)+log|B'|,
               =   nlog|AB|-E_r(ρ_AB^⊗ n)-nS(E) 
               ==========
                    +log|KA'B'|-log|KA'|,
               ≤ 2nlog|AB|-E_r(ρ_AB^⊗ n)-nS(AB)-log |K|,
        
        where Ineq. (<ref>) comes from the Berta-Fawzi-Wehner protocol <cit.>, Eq. (<ref>) from nS(E)-nS(E)=0, Eq. (<ref>) from Lemma <ref>, Ineq. (<ref>) from the fact that E_r(ρ_XY)≤ S(ρ_Y) which follows from ρ_XY=_X'(|ρ⟩⟨ρ|_X'X:Y) where |ρ⟩_X'XY is a purification state for ρ_XY, and the nonincreasing property of entanglement under partial trace, Ineq. (<ref>) from S(ρ_X)≤log|X|, and Ineq. (<ref>) from that the dimension of AB is invariant.  
        So we obtain log |K|≤ nlog|AB|-n/2[E^∞_r(ρ_AB)+S(ρ_AB)]. 
        Since it holds for any randomness extraction, we 
        get R_A=sup_n 1/nlog |K|≤log|AB|-1/2 [E^∞_r(ρ_AB)+S(ρ_AB)].
        
        
        To prove the tightness for pure states, we first show it is tight for a singlet, that is R_A=3/2.
        We get this by constructing an explicit protocol. Consider two singlets 
        |Φ⟩_A_1B_1⊗|Φ⟩_A_2B_2. Bob sends B_1 through 
        the dephasing channel and the resulting state is 
        1/√(2)(|000⟩+|111⟩)_A_1B_1E when we include Eve. 
        Alice performs a CNOT to get |Φ⟩_A_1E⊗|0⟩_B_1,
        where the pure state |0⟩_B_1 can produce 1 ibit. 
        Then Alice performs a Bell measurement on A_1A_2 to get another
        2 ibits, in total 3 ibits from 2 copies of the state. 
        This is optimal from the upper bound for a singlet. The result can be generalised to a general pure state |ϕ⟩_AB
        by noticing that the local purity log|B|-S(B)=log|B|-S(A) at Bob's side can be transmitted freely through the dephasing channel. First both Alice and Bob turn the shared state into purity parts and information parts. Next Bob sends his purity part to Alice and Alice generates randomness from the purity parts. Then Alice and Bob extract randomness to Alice's side from the information part where the spectrum of the local state is nearly uniform by performing the similar protocol for a singlet. The total randomness comes from three parts, from the local purities of Alice and Bob at the rates log|A|-S(A) and log|B|-S(B) respectively, and from the information part at the rate of 3/2S(A). Noticing S(A)=S(B) and summing up, we get the rate R_A=log|AB|-1/2S(A)_ϕ.
        
         of Theorem <ref>.
        Suppose for n uses of the channel, the final tripartite state among Alice, Bob, and Eve is
        
            |ψ_A^nB^nE^n=V^⊗ n(|ϕ_A^nA'^n),
        
        where V: A'→ BE is an isometric dilation of the channel N. 
        Then with free noise, from scenario 2) of Theorem <ref> we know that
        for such a state, Bob can extract randomness at rate 
        nlog|B|-S(B^n|A^n)_ψ_A^nB^n=nlog |B|+[S(A^n)-S(A^nB^n)]_ψ_A^nB^n. 
        Further, from Theorem <ref>, we know that the randomness value 
        which is represented by the dephased system K_B is decoupled from both 
        system A of the sender, and E of the eavesdropper, thus is private to each 
        of them individually. 
        
        To maximize the quantity amounts to maximizing the second term, which is 
        none other than the reverse coherent information, and from <cit.> we 
        know that the reverse coherent information of a channel is additive. So optimisation over n channel uses is reduced to the optimization over a single channel use. 
        
        For the sake of completeness, we write the proof. We will prove that 
        
            max_|ϕ_A_1A_2A'_1A'_2[S(ϕ_A_1A_2)   -S( N_1⊗ N_2(ϕ_A_1A_2A'_1A'_2))] 
               =  max_|ψ_A_1A'_1[S(ψ_A_1)-S( N_1(ψ_A_1A'_1))] 
               =
                     + max_|φ_A_2A'_2[S(φ_A)-S( N_2(φ_A_2A'_2))],
        
        for quantum channels N_1: A'_1→ B_1 and N_2: A'_2→ B_2.
        
        It is easy to see the direction “≥” holds by taking |ϕ_A_1A_2A'_1A'_2=|ψ_A_1A'_1⊗|φ_A_2A'_2. 
        
        The nontrivial part is the opposite direction “≤”. First we give another equivalent form of the optimisation. Let V: A'→ BE be an isometric dilation of the channel N: A'→ B. Then for an input |ϕ⟩_AA', we have 
        
            _A⊗ V|ϕ⟩_AA'=|ψ⟩_ABE.
        
        From the duality relation between conditional entropies of a pure state |ψ⟩_ABE
            S(A)_ψ-S(AB)_ψ=-S(B|A)_ψ=S(B|E)_ψ,
         
        and ϕ_A=ψ_A, ψ_AB= N(ϕ_AA'), we have
        
        S(ϕ_A)-S( N(ϕ_AA')) =S(B|E)_ψ,
        
        where ψ_BE=Vϕ_A'V^†. In Eq. (<ref>), the optimisation over the input |ϕ⟩_AA' on the left side is reduced to the optimisation over the mixed state ϕ_A' on the right side. So we get the equivalent form of RCI,
        
            max_|ϕ⟩_AA'[S(ϕ_A)-S( N(ϕ_AA'))]=max_ϕ_A'S(B|E)_ψ.
        
         
        Given two channels N_1 and N_2, denote their isometries as V_1: A'_1→ B_1E_1 and V_2: A'_2→ B_2E_2 respectively. Suppose the optimal input state for the two channels is σ_A'_1A'_2 and the output on B_1E_1B_2E_2 is
        
            ρ_B_1E_1B_2E_2=V_1⊗ V_2σ_A'_1A'_2V^†_1⊗ V^†_2.
         
        
        By the chain rule S(XY|Z)=S(X|Z)+S(Y|XZ) and the monotonicity of 
        conditional entropy (coming from the strong subadditivity) S(X|YZ) ≤ S(X|Y), we get
        
            S(B_1B_2|E_1E_2)_ρ   =   S(B_1|E_1E_2)_ρ+S(B_2|B_1E_1E_2)_ρ, 
               ≤ S(B_1|E_1)_ρ+S(B_2|E_2)_ρ,
        
        where ρ_B_1E_1=V_1σ_A'_1V^†_1, ρ_B_2E_2=V_2σ_A'_2V^†_2. So the direction “≤”  is true and we get the result of additivity.  
        
        
        
        
        Next we show that the function S(B|E) on ρ_BE=Vσ_A'V^† is concave with respect to the input state σ_A', thus its optimisation problem is efficiently computable. We will prove that for the input state σ=pσ_1+(1-p)σ_2 with 0≤ p≤ 1, and output
        
            ρ_BE=pρ_1+(1-p)ρ_2=pVσ_1V^†+(1-p)Vσ_2V^†,
        
        we have 
        
        S(B|E)_ρ≥ pS(B|E)_ρ_1+(1-p)S(B|E)_ρ_2.
        
        
        To that end, consider the state 
        
            ρ_BEF = pρ_1⊗|0⟩⟨0|_F+(1-p)ρ_2⊗|1⟩⟨1|_F.
         
        By the monotonicity of the conditional entropy S(B|E)≥ S(B|EF) and the computation of  S(B|E) and S(B|EF), we arrive at Ineq. (<ref>). ]