Robust Secure Authentication and Data Storage with Perfect Secrecy

Abstract

We consider an authentication process that makes use of biometric data or the output of a physical unclonable function (PUF), respectively, from an information theoretical point of view. We analyse different definitions of achievability for the authentication model. For the secrecy of the key generated for authentication, these definitions differ in their requirements. In the first work on PUF based authentication, weak secrecy has been used and the corresponding capacity regions have been characterized. The disadvantages of weak secrecy are well known. The ultimate performance criteria for the key are perfect secrecy together with uniform distribution of the key. We derive the corresponding capacity region. We show that, for perfect secrecy and uniform distribution of the key, we can achieve the same rates as for weak secrecy together with a weaker requirement on the distribution of the key. In the classical works on PUF based authentication, it is assumed that the source statistics are known perfectly. This requirement is rarely met in applications. That is why the model is generalized to a compound model, taking into account source uncertainty. We also derive the capacity region for the compound model requiring perfect secrecy. Additionally, we consider results for secure storage using a biometric or PUF source that follow directly from the results for authentication. We also generalize known results for this problem by weakening the assumption concerning the distribution of the data that shall be stored. This allows us to combine source compression and secure storage.

1. Introduction

The present work addresses two essential practical problems concerning secrecy in information systems. The first problem is authentication in order to manage access to the system. The second problem is secure storage in public databases. Both problems are of essential importance for further development of future communication systems. The goal of this work is to derive a fundamental characterization of the possible performance of such communication systems that meets very strict secrecy requirements. We show that these strict requirements can be met without loss in performance compared to known results with weaker secrecy requirements.

Information theoretic security has become a very active field of research in information theory in the past ten years, with a large number of promising approaches. For a current presentation, see [1]. In [2], the paper first introducing information theoretic security, the authors suggest requiring perfect secrecy [3] to guarantee security in communication. This means the data available to an attacker should be stochastically independent of the message that should be kept secret (the data and the message are modeled using random variables (RVs)). Thus, an attacker does not benefit from learning these data. In [4], this notion of security is weakened. The authors use weak secrecy [3] instead of perfect secrecy to guarantee secure communication. In many of the works on information theoretic security following [4], one considers weak secrecy or strong secrecy [3], which is yet another security requirement that is also weaker than perfect secrecy. As the name suggests, perfect secrecy is the desired ideal situation in cryptographic applications where an attacker does not get any information about the secret. Considering the roots of information theoretic security and its intuitive motivation, it suggests itself to require perfect secrecy for secure communications. Additionally, in [3], the recommendation is to not use weak secrecy as a secrecy measure. In [5], there is an example of a protocol that is obviously not secure, but meets the weak secrecy requirement.

The authors of the landmark paper [6] derive the capacity for secret key generation requiring perfect secrecy. A different model in information theoretic security has as an essential feature a biometric source or a PUF source. The outputs of biometric sources and the outputs of PUF sources both uniquely characterize a person [7], or a device, respectively [8]. This property qualifies them for being used for authentication as well as for secure storage. In [7,9], the authors consider a model for authentication using the output of a biometric source. They also consider a model that can be interpreted as a model for secure storage using a biometric source. Both of these models are very similar to the model for secret key generation and for both of the models the authors require weak secrecy to hold when defining achievability.

In [6,7,9], the authors assume that the statistics of the (PUF) source are perfectly known. A simple analysis of [6,7,9] shows that the protocols for authentication constructed there heavily depend on the knowledge of the source statistics. Particularly, it is possible that small variations of the source statistics influence the reliability and secrecy of the protocols for authentication or storage, respectively. The assumption that the source statistics are perfectly known is too optimistic in applications. That is why we are interested in considering the uncertainty of the source or PUF source. We assume that we do not know the statistics of the source, but that we know a set of source statistics that contains the actual source statistic. Thus, we consider a compound version of the source model. We want to develop robust protocols that work for all source statistics in a given set. The compound model also allows us to describe an attack scenario where the attacker is able to alter the source statistics. There are relatively few results concerning compound sources. The compound version of the source model from [6] is considered in [10].

One of our contributions in the present work is the generalization of the model for authentication from [7], by considering authentication using a compound PUF source (or equivalently a biometric source). Additionally, our work differs from the state of the art as we consider protocols for authentication that achieve perfect secrecy.

We also consider secure data storage making use of a PUF source (or equivalently a biometric source). The corresponding information theoretic model is very similar to the second model presented in [7], but, in contrast to [7], we define achievability requiring perfect secrecy and we consider source uncertainty of the PUF source. Our considerations concerning perfect secrecy in this work answer the question posed in the conclusion of [11].

Some of the results for secure authentication described in this work have already been published in [12]. Here, we additionally present the proofs that have been omitted in [12], i.e., the proofs of Theorem 4 and Theorem 5 and some more discussion. The results concerning secure storage have been presented in [13,14]. As these results heavily depend on [12], we briefly state them here (as well as the corresponding definitions).

In Section 2, we describe the authentication process and define the corresponding information theoretic model. We discuss different definitions of achievability for the model in Section 3. In this context, protocols that achieve perfect secrecy are of special interest. We develop the corresponding definition of achievability in this section. In Section 4, we prove capacity results for the model with respect to the various definitions of achievability. The main result in this section is Theorem 2. In Section 5, we generalize the model for authentication to the case with source uncertainty and define achievability for this model in Section 6. In Section 7, we derive the capacity region for the compound storage model. In Section 8, we consider some results for secure storage that follow from our results for authentication. The key result from authentication that we use for secure storage with perfect secrecy is Theorem 2. In Section 9, we further discuss our results.

For the most part, we use the notation introduced in [3].

2. Authentication Model

At first, we consider authentication using biometric or PUF data. This means we consider a scenario where a user enrolls in a system by giving a certain amount of biometric or PUF data to the system. Later, when the user wants to be authenticated, he again gives biometric or PUF data to the system. The system then decides if the user is accepted, i.e., if it is the same user that is enrolled in the system. In our considerations, we assume that the system can store some data in a public database.

Figure 1 depicts the authentication process as described in [7]. The process consists of two phases. In the first phase, the enrollment phase, the authentication system receives ^Xn from the PUF source and the ID of a user. It generates a helper message M and a secret-key K from ^Xn . It then uses a one-way function f on K and stores the result and M in a public database together with the user’s ID . The second phase is the authentication phase. In this phase, the system receives ^Yn from the PUF source and the ID of a user. It reads the corresponding helper message M and f(K) from the database. From M and ^Yn , it generates a secret-key K^ . Then, the system compares f(K) and f(K^). If they are equal, the user is accepted; otherwise, the user is rejected.

Figure 1. Authentication process considered in [7].

Now, we define an information theoretic model of the authentication process. We use random variables (RVs) to model the data. In the first chapters of this work, we assume that the distribution of the RVs is perfectly known. We drop this assumption in Section 5.

Definition 1.

Let n∈N . The authentication model consists of a discrete memoryless multiple source (DMMS) with generic variables XY [3], the (possibly randomized) encoders [3] Φ:^Xn→M , Θ:^Xn→K and the deterministic decoder ψ:^Yn×M→K^ . Let ^Xn and ^Yn be the output of the DMMS. The RVs M and K are generated from ^Xn using Φ and Θ. The RV K^ is generated from ^Yn and M using ψ. We use the term authentication protocol for (Φ,Θ,ψ) .

Remark 1.

It is possible to define the authentication protocol in a more general way by permitting randomized decoders Ψ, but one can argue that in our definition of achievability a randomized Ψ does not improve the performance of the protocols ([3], Problem 17.11). For convenience, we use the less general definition.

Remark 2.

We model the PUF source as a DMMS. Due to physically induced distortions, we model the biometric/PUF data read in the two phases as jointly distributed RVs.

Remark 3.

The distribution of XY is assumed to be known and can be used for the generation of the RVs. Thus, the encoders and the decoder are allowed to depend on the distribution.

3. Various Definitions of Achievability

For the authentication model, we define achievable secret-key rate versus privacy-leakage rate pairs. Intuitively, we want the probability that a legitimate user is rejected in the authentication phase to be small. Thus, Pr(K=K^) should be large to fulfill this reliability condition. Additionally, the probability that an attacker is accepted in the authentication phase should be as small as possible. Thus, we consider the maximum false acceptance probability (mFAP) [15], which is the probability that an attacker using the best possible attack strategy is accepted in the authentication phase averaged over all public messages m∈M . As we want the mFAP to be as small as possible, we are interested in the largest possible set of secret keys K . This reasoning is explained below. The system uses the output of a PUF source as input so it should leak as little information about ^Xn as possible [7]. This motivates the following definition of achievable rate pairs.

Definition 2.

A tuple (R,L) , R,L≥0 , is an achievable secret-key rate versus privacy-leakage rate pair for the authentication model if for every δ>0 there is an _n0=_n0(δ) such that for all n≥_n0 there exists an authentication protocol such that

Pr(K=K^)≥1−δ,mFAP≤1|K|,1nlog|K|≥R−δ,1nI(M;^Xn)≤L+δ.

We denote the corresponding authentication protocols by FAP-Protocols (False-Acceptance- Probability-Protocols).

Remark 4.

In [15], a very similar definition of achievability is used. Instead of considering the relation between the mFAP and the set of secret-keys (1), the authors define the false-acceptance exponent that describes the exponential decrease of the mFAP in n. A rate pair (R,L) that is achievable using FAP-protocols is also achievable according to the definition in [15], R playing the role of the false-acceptance exponent.

We now clarify the bound on the mFAP in Inequality (1) and our interest in large secret-key rates. For this purpose, we consider the following observation.

Lemma 1.

For a communication protocol fulfilling the reliability condition, it holds that

mFAP≥1−δ|K|.

Proof.

Introduce the RV E, setting E=1 for K≠K^ and E=0, otherwise. Thus,

mFAP=∑m∈M_PM(m)max^yn∈^Yn_PK|M(ψ(^yn,m)|m)≥∑m∈M_PM(m)max^yn∈^Yn_PK|ME(ψ(^yn,m)|m,0)_PE|M(0|m)=(a)∑m∈M_PME(m,0)maxk∈K_PK|ME(k|m,0)≥∑m∈M_PME(m,0)1|K|≥(b)(1−δ)1|K|.

Here, (a) follows as _PK|ME(k|m,0)=0 if there is no ^yn∈^Yn such that ψ(^yn,m)=k and (b) follows from the δ -recoverability of K from K^. ☐

Thus, Lemma 1 shows that requiring Inequality (1) is in fact equivalent to requiring the mFAP to be as small as possible. It also justifies our interest in a large set K.

There is another way to define achievable secret-key rate versus privacy-leakage rate pairs for the authentication model. Here, we want to keep the key secret from the attacker. H(K|M) can be interpreted as the average information required to specify k when m is known ([16], Chapter 2). Thus, we want H(K|M) to be as large as possible instead of requiring a small mFAP. This means we require log|K|=H(K|M) . This condition is equivalent to the combination of the perfect secrecy condition I(K;M)=0 [5] and the uniform distribution of the key, i.e., H(K)=log|K|. Thus, we define achievability as follows.

Definition 3.

A tuple (R,L) , R,L≥0 , is an achievable secret-key rate versus privacy-leakage rate pair for the authentication model if for every δ>0 there is an _n0=_n0(δ) such that for all n≥_n0 there exists an authentication protocol such that

Pr(K=K^)≥1−δ,(2)H(K)=log|K|,(3)I(M;K)=0,1nlog|K|≥R−δ,1nI(M;^Xn)≤L+δ.

We denote the corresponding authentication protocols by PSA-Protocols (Perfect-Secrecy-Authentication-Protocols).

Remark 5.

In [6], the authors derive the secret-key capacity for the source model. They define achievability requiring perfect secrecy and uniform distribution of the key. They do not consider the privacy-leakage in contrast to our definition of achievability.

It is interesting to compare the rate pairs achievable with respect to the restrictive Definition 3 with commonly used weaker requirements. In ([7], Definition 3.1), the authors give a different definition of achievable secret-key rate versus privacy-leakage rate pairs. Instead of Eqation (2), they require

H(K)≥log|K|−δ

and instead of Equation (3) they require

1nI(M;K)≤δ,

which is called the weak secrecy condition [5]. Thus, we get a third definition of achievability.

Definition 4

([7]). A tuple (R,L) , R,L≥0 , is an achievable secret-key rate versus privacy-leakage rate pair for the authentication model if for every δ>0 there is an _n0=_n0(δ) such that for all n≥_n0 there exists an authentication protocol such that

Pr(K=K^)≥1−δ,H(K)≥log|K|−δ,1nI(M;K)≤δ,1nlog|K|≥R−δ,1nI(M;^Xn)≤L+δ.

We denote the corresponding authentication protocols by WSA-Protocols (Weak-Secrecy-Authentication-Protocols).

Definition 5.

The set of achievable rate pairs that are achievable using PSA-Protocols is called the capacity region _RPSA . The set of achievable rate pairs that are achievable using WSA-Protocols is called the capacity region _RWSA and the set of achievable rate pairs that are achievable using FAP-Protocols is called the capacity region _RFAP .

Now, we look at some straightforward relations between these capacity regions. We can directly see that Definition 3 is more restrictive than Definition 4 so a PSA-Protocol is also a WSA-Protocol and thus

_RPSA⊂_RWSA.

We now show that a PSA-Protocol is also a FAP-Protocol.

Lemma 2.

It holds that

_RPSA⊂_RFAP.

Proof.

As Equations (2) and (3) imply, _PK|M(k|m)=1|K| for all (k,m)∈K×M, we have

mFAP=∑m∈M_PM(m)max^yn∈^Yn_PK|M(ψ(^yn,m)|m)≤∑m∈M_PM(m)maxk∈K_PK|M(k|m)=1|K|.

☐

4. Capacity Regions for the Authentication Model

In ([7], Theorem 3.1), the authors derive the capacity region _RWSA.

Theorem 1

([7]). It holds that

_RWSA=⋃U{(R,L):0≤R≤I(U;Y),L≥I(U;X)−I(U;Y)}.

The union is over all RVs U such that U−X−Y . We only have to consider RVs U with |U|≤|X|+1 .

Remark 6.

The authors of [7] do not consider randomized encoders. In contrast, we permit randomization of the encoders in the enrollment phase. Using the strategy described in ([3], Problem 17.15), one can use the converse for deterministic encoders to prove the converse for randomized encoders with the same bounds on the secret-key rate and the privacy-leakage rate. Thus, the converse in [7] also holds true when randomization is permitted.

The following theorem is one of our main results.

Theorem 2.

It holds that

_RPSA=_RWSA.

Proof.

We do not prove Theorem 2 here but prove a more general result in the remainder of the text. This result is Theorem 5. It is more general as it is concerned with a compound version of the authentication model. The authentication model is a special case of the compound authentication model where the compound set consists of a single DMMS. ☐

We now strengthen Lemma 2.

Theorem 3.

It holds that

_RPSA=_RFAP.

Proof.

The achievability result is implied by Lemma 2. For the converse, we use a result of [15]. As discussed in Remark 4, a rate pair (R,L), which is achievable according to Definition 2 is also achievable according to the definition of achievability used in [15], where R plays the role of the false acceptance exponent E. Thus, we use ([15], Theorem 4), which says that a rate pair (E,L)∉_RWSAis not achievable. This implies our converse. ☐

5. Compound Authentication Model

We now consider authentication when the data source is not perfectly known. Figure 2 shows the corresponding authentication process. The only difference to the authentication process in Section 2 is the source uncertainty. As one can see in Figure 2, we even assume that an attacker can influence the source in the sense that the state of the source is altered, i.e., it generates another statistic. If the protocol for authentication is not robust, then authentication will not work.

Figure 2. Authentication process with source uncertainty (as considered in [12]).

We define the following information theoretic model for this authentication process with source uncertainty.

Definition 6.

Let n∈N . The compound authentication model consists of a set S of DMMSs with generic variables _{Xs Ys} , s∈S , (all on the same alphabets X and Y ), the (possibly randomized) encoders Φ:^Xn→M , Θ:^Xn→K and the (possibly randomized) decoder Ψ:^Yn×M→K^ . Let ^Xn and ^Yn be the output of one of the DMMSs in S , i.e., _PXY=_{PXs Ys} for an s∈S , but s is not known. The RVs M and K are generated from ^Xn using Φ and Θ. The RV K^ is generated from ^Yn and M using Ψ. We use the term compound authentication protocol for (Φ,Θ,Ψ) .

Remark 7.

The uncertainty of the data source is modeled making use of a compound DMMS, that is, the DMMS modeling the PUF source is not known, but we know a set of DMMSs to which the actual DMMS belongs.

Remark 8.

S is assumed to be known and can be used for the generation of the RVs, that is, the encoder and the decoder can depend on these distributions.

Definition 7.

Given S , we define the set

I(s^)={s∈S:∑y∈Y_{PXs Ys}(x,y)=_PXs^ (x)∀x∈X}

for s^∈S . The sets I(s^) , s^∈S , form a partition of S , as they form the equivalence classes for the corresponding equivalence relation. We denote a set of representatives by S^ .

6. Achievability for the Compound Model

For the compound authentication model, we define achievable secret-key rate versus privacy-leakage rate pairs.

Definition 8.

A tuple (R,L) , R,L≥0 , is an achievable secret-key rate versus privacy-leakage rate pair for the compound authentication model if for every δ>0 there is an _n0=_n0(δ) such that, for all n≥_n0 , there exists a compound authentication protocol such that, for all s∈S,

(5)Pr(K=K^)≥1−δ,(6)H(K)=log|K|,(7)I(M;K)=0,1nlog|K|≥R−δ,1nI(M;^Xn)≤L+δ,

where _PXY=_{PXs Ys} . We denote the corresponding authentication protocols by PSCA-Protocols (Perfect-Secrecy-Compound-Authentication-Protocols).

Definition 9.

The set of achievable secret-key versus privacy-leakage rate pairs that are achievable using PSCA-Protocols is called the compound capacity region _RPSCA(S) .

7. Capacity Regions for the Compound Authentication Model

We now derive the compound capacity region _RPSCA(S) for the compound authentication model. We only consider compound sets S such that |S^|<∞ . For the proof, we need the following theorem, which is a generalization of ([3], Theorem 6.10).

Theorem 4.

Given a (possibly infinite) set W of channels W:X→Y , a set A⊂^Xn with ^Pn(A)>η , P∈P(X) , η>0 and ϵ>0 . Then, for every τ>0 and all n large enough, there is a pair of mappings (f,ϕ) , f:_Mf→^Xn , ϕ:^Yn→_Mf , such that (f,ϕ) is an (n,ϵ) -code for all W∈W with codewords in A and

1nlog|_Mf|≥infW∈WI(P;W)−τ.

We call this pair of mappings a compound (n,ϵ) -code for W .

Even though the proof of Theorem 4 is very similar to the proof of ([3], Theorem 6.10), the proof of ([17], Theorem 4.3) and the proof of the results in [18], we prove Theorem 4 for the sake of completeness. The proof can be found in Appendix A.

Theorem 5.

It holds that

_RPSCA(S)=⋂s^∈S^⋃_Us^{(R,L):0≤R≤infs∈I(s^)I(_Us^;_Ys),L≥sups∈I(s^)I(_Us^;_Xs)−I(_Us^;_Ys)}=(a)⋂s^∈S^⋃_Us^Rs^(PSCA)(S,_Us^),

where, for ( a) , we define _Rs^(PSCA)(S,_Us^) appropriately. For all s^∈S^, the union is over all RVs _Us^ such that, for all s∈I(s^), we have _Us^−_Xs−_Ys . For |S|<∞ , we only have to consider RVs _Us^ with |_Us^|≤|X|+|I(s^)| .

Proof.

For all s^∈S^ and all s∈I(s^) , let _Us^ , _Xs and _Ys be RVs where _{Xs Ys} are the output of the DMMS in S with index s and _Xs and _Us^ are connected by the channel _Vs^:X→_Us^ . Thus, we have the Markov chains _Us^−_Xs−_Ys for all s∈I(s^) . Let U=⋃s^∈S^_Us^ . We now show that, given δ>0 , for n large enough we can choose a set C⊂^Un that consists of |M| disjoint subsets _Cmwith the following properties.

1. We consider a partition of the set of all sets _Cm in |S^| subsets. Thus, we denote the sets _Cm by _Cm,s^ , s^∈S^ , indicating to which subset they belong. We denote the set of indices m corresponding to s^ by _Ms^ . For each _Cm,s^, we have

|_Cm,s^|=⌈infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉.

* Each _Cm,s^consists of sequences of the same type.

* It holds that

_PUs^n(C)>1−η

for η>0 and all s^∈S^.

* For each s^∈S^ , one can define pairs of mappings that are compound (n,ϵ) -codes, ϵ>0 , for the channels _Ws:U→Y , _Ws=_PYs|Us^ for all s∈I(s^) in the following way. Define an (arbitrary) bijective mapping _fm:{1⋯|_Cm,s^|}→_Cm,s^ and an appropriate mapping _ϕm:^Yn→{1⋯|_Cm,s^|} . Then, (_fm,_ϕm)is such a code. This means

_Wsn(_ϕm−1(_fm−1(^un))|^un)≥1−ϵ

for all s∈I(s^) and for all codewords ^un in _Cm,s^ . This is possible for all m∈_Ms^.

Let ^δ′>0 . We denote the elements of S^ by _s^1,_s^2,⋯,_s^|S^| . We consider _{TPUs^1 ,ξn},_{TPUs^2 ,ξn},⋯,_{TPUs^|S^| ,ξn} , ξ>0 , which are disjoint subsets of ^Un . We show that they are in fact disjoint subsets of ^Un for ξ small enough. This can be seen as follows. For _s^i,_s^j∈S^ , _s^i≠_s^j , it holds that _PUs^i (u)≠_PUs^j (u) for at least one u∈U . Thus, there is a u∈Uwith

|_PUs^i (u)−_PUs^j (u)|>α

for some α>0.

Now, assume that there is a ^un∈_{TPUs^i ,ξn}∩_{TPUs^j ,ξn} . Denote the type of ^un by _p^un . Thus, there is a u∈Uwith

α<|_PUs^i (u)−_PUs^j (u)|=|_PUs^i (u)−_P^un (u)+_P^un (u)−_PUs^j (u)|≤|_PUs^i (u)−_P^un (u)|+|_PUs^j (u)−_P^un (u)|≤2ξ,

where the last inequality follows from the assumption that ^un∈_{TPUs^i ,ξn}∩_{TPUs^j ,ξn} . Thus, for ξ<α/2 , this is a contradiction and we know _{TPUs^i ,ξn} and _{TPUs^j ,ξn}are disjoint.

We start the construction of C by choosing a set _A1,s^1⊂_{TPUs^1 ,ξn} with _{PUs^1 n}(_A1,s^1)≥^η′ with η>^η′>0 . According to Theorem 4, there is a compound (n,ϵ) -code for the channels _Ws , s∈I(_s^1)with at least

⌈infs∈I(_s^1)expn(I(_Us^1 ;_Ys)−^δ′)⌉

codewords ^un∈_A1,s^1 for n large enough. We denote the set of these codewords by _C1,s^1′ . As there are less than ^(n+1)|U|types, we know that there is a set of at least

⌈_{infs∈I(s^1)}expn(I(_Us^1 ;_Ys)−^δ′)⌉^(n+1)|U|

codewords in _C1,s^1′with the same type. We only pick these codewords. There are at least

infs∈I(_s^1)expn(I(_Us^1 ;_Ys)−^δ′−|U|log(n+1)n)≥⌈infs∈I(_s^1)expn(I(_Us^1 ;_Ys)−δ)⌉

of them for n large enough. We now pick exactly

⌈infs∈I(_s^1)expn(I(_Us^1 ;_Ys)−δ)⌉

of these codewords and we denote this set by _C1,s^1 . Now, we choose a set _A2,s^1⊂_{TPUs^1 ,ξn}\_C1,s^1 with _PUn(_A2,s^1)≥^η′ . We construct the set _C2,s^1 in the same way as _C1,s^1 . Thus, _C2,s^1is a set of

⌈infs∈I(_s^1)expn(I(_Us^1 ;_Ys)−δ)⌉

codewords of the same type corresponding to an (n,ϵ)-code. We continue this process until we can not find a set

_{A|Ms^1 |+1,s^1}⊂_{TPUs^1 ,ξn}\⋃i∈_{Ms^1 Ci,s^1}

with

_{PUs^1 n}(_{A|Ms^1 |+1,s^1})≥^η′.

This means

_{PUs^1 n}(^{(⋃i∈_{Ms^1 Ci,s^1})c}∩_{TPUs^1 ,ξn})<^η′.

We repeat this process for all s^≠_s^1 , s^∈S^ . Thus, we have for all s^∈S^

_PUs^n(C)≥_PUs^n(⋃i∈_Ms^Ci,s^)=1−_PUs^n(^{(⋃i∈_Ms^Ci,s^)c})=1−_PUs^n(^{(⋃i∈_Ms^Ci,s^)c}∩_{TPUs^ ,ξn})−_PUs^n(^{(⋃i∈_Ms^Ci,s^)c}∩^{(_{TPUs^ ,ξn})c})≥1−_PUs^n(^{(⋃i∈_Ms^Ci,s^)c}∩_{TPUs^ ,ξn})−_PUs^n(^{(_{TPUs^ ,ξn})c}).

Thus, we have Inequality (8) for n large enough.

We now can define the encoders/decoders Φ , Θ and Ψ.

1. We define Φ and Θ as follows. The system gets a sequence ^xn . It checks if ^xn∈_{TPXs^ ,^ξ′n} , ^ξ′>0 , for an s^∈S^ (We can choose ^ξ′ small enough and n large enough such that the _{TPXs^ ,^ξ′n} are disjoint). If this is true for s^ , the channel _Vs^ is used n times to generate ^un from ^xn . For Φ , the system looks in C for ^un . If ^un∈C the system chooses for m the index of the subset _Cm containing ^un . If ^un∉C it chooses an arbitrary m∈M . In addition, if ^xn∉⋃s^∈S^_{TPXs^ ,^ξ′n} , it chooses an arbitrary m∈M . For Θ , the system looks in C for ^un . If ^un∈C , it considers the compound (n,ϵ) -code corresponding to the subset _Cm,s^ containing ^un. If

|_Cm,s^|>mins^∈S^⌈infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉,

we consider the following deterministic mapping _hm:_fm−1(_Cm)→K∪{k˜}. Here,

K={1⋯mins^∈S^⌈infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉}.

The preimage of any k∈K under _hm is a subset of _fm−1(_Cm)of size

|_Cm,s^|_mins^∈S^⌈_infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉.

The rest of the ^k′∈_fm−1(_Cm) is mapped on k˜∉K. If

|_Cm,s^|=mins^∈S^⌈infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉,

the system chooses k=_fm−1(^un) . In this case, we also define _hm:_fm−1(_Cm)→K∪{k˜} where _hm is injective. If ^un∉C , k is chosen at random according to a uniform distribution on the alphabet. The same holds if ^un is mapped on k˜ or if ^xn∉⋃s^∈S^_{TPX,s^,^ξ′n}.

* We define Ψ as follows. The system gets a sequence ^yn and m. It decodes ^yn using the code corresponding to _Cm,s^ . Then, _hm is used on the result. The result is k^ if it differs from k˜ . Otherwise, an arbitrary k^∈Kis chosen.

Using the properties of the communication protocol, we analyse the achievability conditions. We denote the outputs of the DMMS by ^Xn and ^Yn and the output of the channel used on ^Xn by ^Un . Assume the index of the DMMS is s∈I(s^) , s^∈S . Thus, _{P^{Xn Yn}}=_{PXs Ysn}.

1. We define the following events:

_E1={(^xn,^yn,^un)∈^Xn×^Yn×^Un:(^xn,^un)∉_{TPXs Us^,^ξ″n}},_E2={(^xn,^yn,^un)∈^Xn×^Yn×^Un:^un∉C},_E3=⋃m∈M{(^xn,^yn,^un)∈^Xn×^Yn×^Un:^un∈_Cm∧_hm(_fm−1(^un))=k˜},_E4=⋃m∈M{(^xn,^yn,^un)∈^Xn×^Yn×^Un:^un∈_Cm∧_fm−1(^un)≠_ϕm(^yn)}.

According to ([3], Lemma 2.10), we can choose ^ξ″ small enough such that (^xn,^un)∈_{TPXs Us^,^ξ″n} implies ^xn∈_{TPXs ,^ξ′n} and ^un∈_{TPUs^ ,ξn}. We have

_{P^{Xn Yn Un}}(_E1)=1−_{P^{Xn Yn Un}}(_E1c)=(a)1−_{PXs Ys Us^n}(_E1c)=1−_{PXs Us^n}(_{TPXs Us^,^ξ″n})=_{PXs Us^n}(^{(_{TPXs Us^,ξ″n})c}).

Here, (a) follows as for ^xn∈_{TPXs ,^ξ′n} the system uses _Vs^ to generate ^un from ^xn. Thus,

Pr(K≠K^)≤_{P^{Xn Yn Un}}(_E1∪_E2∪_E3∪_E4)=_{P^{Xn Yn Un}}(_E1)+_{P^{Xn Yn Un}}((_E2∪_E3∪_E4)∩_E1c)=_{PXs Us^n}(^{(_{TPXs Us^,ξ″n})c})+_{P^{Xn Yn Un}}(_E2∩_E1c)+_{P^{Xn Yn Un}}((_E3∪_E4)∩_E1c∩(_E2c∪_E1)).

Now, we use

_{P^{Xn Yn Un}}(_E2∩_E1c)≤∑(^xn,^un):^xn∈_{TPXs ,^ξ′n}∧^un∈^Cc_{P^{Xn Un}}(^xn,^un)=∑(^xn,^un):^xn∈_{TPXs ,^ξ′n}∧^un∈^Cc_{PXs Us^n}(^xn,^un)≤∑(^xn,^un):^xn∈^Xn∧^un∈^Cc_{PXs Us^n}(^xn,^un)=_PUs^n(^Cc)

and get

Pr(K≠K^)≤_{PXs Us^n}(^{(_{TPXs Us^,ξ″n})c})+_PUs^n(^Cc)+_{P^{Xn Yn Un}}((_E3∪_E4)∩_E1c∩_E2c)≤_{PXs Us^n}(^{(_{TPXs Us^,ξ″n})c})+_PUs^n(^Cc)+_{P^{Xn Yn Un}}(_E4∩_E1c∩_E2c)+_{P^{Xn Yn Un}}(_E3∩_E1c∩_E2c).

Now, we define the RV E=e(^Xn,^Un) with e:^Xn×^Un→{0,1}

e(^xn,^un)=0,for^un∈C∧^xn∈⋃s^∈S^_{TPXs^ ,^ξ′n},1,otherwise.

We have

Pr(K≠K^)≤_{PXs Us^n}(^{(_{TPXs Us^,ξ″n})c})+_PUs^n(^Cc)+∑m∈M_PM(m)_{P^{Xn Yn Un}|M}(_E4∩_E1c∩_E2c|m)+∑m∈M_PME(m,0)_{P^{Xn Yn Un}|ME}(_E3∩_E1c∩_E2c|m,0)

as for all m∈M

_{P^{Xn Yn Un}|ME}(_E3∩_E1c∩_E2c|m,1)=0.

As ^un∈C and ^un∈_{TPUs^ ,ξn} imply ^un∈_Cm for an m∈_Ms^, we know

_{P^{Xn Yn Un}|M}(_E4∩_E1c∩_E2c|m)=0

and

_{P^{Xn Yn Un}|M}(_E3∩_E1c∩_E2c|m)=0

for m∉_Ms^. Thus, we have

Pr(K≠K^)≤_{PXs Us^n}(^{(_{TPXs Us^,ξ″n})c})+_PUs^n(^Cc)+∑m∈_Ms^PM(m)_{P^{Xn Yn Un}|M}(_E4∩_E1c∩_E2c|m)+∑m∈_Ms^PME(m,0)_{P^{Xn Yn Un}|ME}(_E3∩_E1c∩_E2c|m,0).

We know for m∈_Ms^

_{P^{Xn Yn Un}|M}(_E4∩_E1c∩_E2c|m)≤∑(^xn,^yn,^un):_fm−1(^un)≠_ϕm(^yn)∧^un∈_Cm∧^xn∈_{TPXs ,^ξ′nP^{Xn Yn Un}|M}(^xn,^yn,^un|m)=∑(^xn,^yn,^un):_fm−1(^un)≠_ϕm(^yn)∧^un∈_Cm∧^xn∈_{TPXs ,^ξ′nP^Xn|^{Un Yn}M}(^xn|^un,^yn,m)_P^Yn|^UnM(^yn|^un,m)_P^Un|M(^un|m).

Using M−^Un−^Yn, we have

_{P^{Xn Yn Un}|M}(_E4∩_E1c∩_E2c|m)≤∑(^xn,^yn,^un):_fm−1(^un)≠_ϕm(^yn)∧^un∈_Cm∧^xn∈_{TPXs ,^ξ′nP^Xn|^{Un Yn}M}(^xn|^un,^yn,m)_P^Yn|^Un(^yn|^un)_P^Un|M(^un|m)=∑(^xn,^yn,^un):_fm−1(^un)≠_ϕm(^yn)∧^un∈_Cm∧^xn∈_{TPXs ,^ξ′nP^Xn|^{Un Yn}M}(^xn|^un,^yn,m)_Wsn(^yn|^un)_P^Un|M(^un|m)≤∑(^xn,^yn,^un):_fm−1(^un)≠_ϕm(^yn)∧^un∈_{CmP^Xn|^{Un Yn}M}(^xn|^un,^yn,m)_Wsn(^yn|^un)_P^Un|M(^un|m)=∑(^yn,^un):_fm−1(^un)≠_ϕm(^yn)∧^un∈_CmWsn(^yn|^un)_P^Un|M(^un|m)=∑^un∈_CmWsn(^{(_ϕm−1(_fm−1(un)))c}|^un)_P^Un|M(^un|m).

Thus, using Inequality (9), we have

∑m∈_Ms^PM(m)_{P^{Xn Yn Un}|M}(_E4∩_E1c∩_E2c|m)≤ϵ

for n large enough. Now, consider ^un∈_Cm , m∈M. We get

_P^Un|ME(^un|m,0)=∑^xn∈^Xn_{P^{Un Xn}|ME}(^un,^xn|m,0)=∑s^∈S^∑^xn∈_{TPXs^ ,^ξ′nP^{Un Xn}|ME}(^un,^xn|m,0)

as

_{P^{Un Xn}|ME}(^un,^xn|m,0)=0

for ^xn∉_{⋃s^∈S^ TPXs^ ,^ξ′n} . We realize that, for ^un∈_Cm and ^xn∈_{⋃s^∈S^ TPXs^ ,^ξ′n},

_{P^{Un Xn}|ME}(^un,^xn|m,0)=_{P^{Un Xn}ME}(^un,^xn,m,0)_PME(m,0)=_{P^{Un Xn}}(^un,^xn)_PME(m,0)_{PME|^{Un Xn}}(m,0|^un,^xn)=_{P^{Un Xn}}(^un,^xn)_PME(m,0),

where the last step follows as

_{PME|^{Un Xn}}(m,0|^un,^xn)=1.

Thus, we get

_P^Un|ME(^un|m,0)=∑s^∈S^∑^xn∈_{TPXs^ ,^ξ′nP^{Un Xn}}(^un,^xn)_PME(m,0)=∑s^∈S^∑^xn∈_{TPXs^ ,^ξ′nPXsn}(^xn)_Vs^n(^un|^xn)_PME(m,0)=∑s^∈S^∑p∈P(n,X):|p(x)−_pXs^ (x)|≤^ξ′∀x∈X∑^xn∈_{Tpn∏i=1n PXs} (_xi)_Vs^(_ui|_xi)_PME(m,0).

The last term is constant for all ^unof the same type. Thus,

_P^Un|ME(^un|m,0)=_pCm

is constant for ^un∈_Cm. As

_P^Un|ME(^un|m,0)=0

for ^un∉_Cm, we have

_P^Un|ME(^un|m,0)=1|_Cm|

for ^un∈_Cm. Now, we get

_{P^{Xn Yn Un}|ME}(_E3∪_E1c∪_E2c|m,0)≤∑(^xn,^yn,^un):∧^un∈_Cm∧^xn∈_{TPXs ,^ξ′n}∧_hm(_fm−1(^un))=k˜_{P^{Xn Yn Un}|ME}(^xn,^yn,^un|m,0)≤∑^un∈_Cm∧_hm(_fm−1(^un))=k˜_P^Un|ME(^un|m,0)=|_hm−1(k˜)|_pCm .

We have

|_hm−1(k˜)|=|_Cm|−mins^∈S^⌈infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉|_Cm|_mins^∈S^⌈_infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉

and get

_{P^{Xn Yn Un}|ME}(_E3∪_E1c∪_E2c|m,0)≤1|_Cm|(|_Cm|−mins^∈S^⌈infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉(|_Cm|_mins^∈S^⌈_infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉−1))=_mins^∈S^⌈_infs∈I(s^)expn(I(_Us^;_Ys)−δ)⌉|_Cm|≤2exp(nϵ˜)

or

_{P^{Xn Yn Un}|ME}(_E3∪_E1c∪_E2c|m,0)=0

respectively, if, for the source state s, it holds that s∈I(s^) for the s^ corresponding to the smallest _Cm,s^. Here,

ϵ˜=infs∈I(s^)I(_Us^;_Ys)−min^{s^′}∈S^infs∈I(^{s^′})I(_U^{s^′} ;_Ys).

Thus, for n large enough,

_Pe≤_{PXs Us^n}(^{(_{TPXs Us^,ξ″n})c})+η+ϵ+2exp(nϵ˜)

and Inequality (5) is fulfilled for small enough constants and n large enough.* We define k˜:^Un×M→{0,1}

k˜(^un,m)=1,for^un∈_fm(_hm−1(k˜)),0,otherwise,

and the RV K˜=k˜(^Un,M). We have

_PK|MEK˜(k|m,0,0)=_P^Un|MEK˜(_fm(_hm−1(k))|m,0,0).

Now, consider ^un∈_Cm. It holds that

_P^Un|MEK˜(^un|m,0,0)=_P^Un|ME(^un|m,0)_PK˜|ME(0|m,0)_PK˜|ME^Un(0|m,0,^un).

We know

_PK˜|ME^Un(0|m,0,^un)=1

for ^un∉_fm(_hm−1(k˜)). Thus,

_PK|MEK˜(k|m,0,0)=_P^Un|ME(_hm−1(k)|m,0)_PK˜|ME(0|m,0)=_pCm |_hm−1(k)|_PK˜|ME(0|m,0)

for all k∈K. This means

_PK|MEK˜(k|m,0,0)=1|K|,

as |_hm−1(k)| is constant for all k∈K. We also know

H(K|M=m,E=e,K˜=k˜)=log|K|

for _PMEK˜(m,e,k˜)>0 , (e,k˜)≠(0,0) as k is chosen according to a uniform distribution on Kin this case. Thus,

log|K|≥H(K|M)≥H(K|MEK˜)=∑(m,e,k˜)∈M×{0,1}×{0,1}_PMEK˜(m,e,k˜)H(K|M=m,E=e,K˜=k˜)=log|K|.

This means Equations (6) and (7) are fulfilled.* For the secret-key rate, we have

1nlog|K|≥mins^∈S^infs∈I(s^)I(_Us^;_Ys)−δ.

* Finally, we analyse the privacy-leakage rate. We have

I(^Xn;M)=H(M)−H(M|^Xn)−H(M|^Un)+H(M|^Un)=I(^Un;M)−H(M|^Xn),

where we use H(M|^Un)=0 for the second equality (see ([3], Problem 3.1)). Now, we use

_PME(_Ms^,0)≥_{P^{Xn Yn Un}}(_E1c∪_E2c)=_{PXs Ys Us^n}(_E1c∪_E2c)≥_{PXs Ys Us^n}(_E1c)+_{PXs Ys Us^n}(_E2c)−1=_{PXs Us^n}(_{TPXs Us^,^ξ″n})+_PUs^n(C)−1≥1−η−_{PXs Us^n}(^{(_{TPXs Us^,ξ″n})c})≥1−ζ

for ζ>0 and n large enough. We also use _P^Un|ME(^un|m,0)=1|_Cm| for ^un∈_Cmand get

H(^Un|M)≥H(^Un|ME)≥∑m∈_Ms^PME(m,0)H(^Un|M=m,E=0)≥(1−ζ)(mins∈I(s^)I(_Us^;_Ys)−δ)n.

Thus,

I(^Xn;M)≤H(^Un)−H(M|^Xn)−nmins∈I(s^)I(_Us^;_Ys)+nδ+ζnmins∈I(s^)I(_Us^;_Ys).

We now use

I(^Xn;^Un)=H(_Xsn)−H(^Xn|^Un)≤H(_Xsn)−H(^Xn|^UnT)≤H(_Xsn)−H(^Xn|^UnT=1)(1−^ϵ′)=H(_Xsn)−H(_Xsn|_Us^nT=1)(1−^ϵ′)=H(_Xsn)−H(_Xsn|_Us^nT=1)(1−^ϵ′)−H(_Xsn|_Us^nT=0)^ϵ′+H(_Xsn|_Us^nT=0)^ϵ′≤I(_Xsn;_Us^nT)+^ϵ′log|X|n=^ϵ′log|X|n+I(_Xsn;_Us^n)+I(T;_Xsn|_Us^n)≤^ϵ′log|X|n+I(_Xsn;_Us^n)+log2,

where T=t(^Xn) , t:^Xn→{0,1}

t(^xn)=1,^xn∈_{TPXs ,^ξ′n},0,else.

Thus, ^ϵ′is arbitrarily small for large n.

Thus, we get

I(^Xn;M)≤H(^Un)−H(M|^Xn)−ninfs∈I(s^)I(_Us^;_Ys)+nδ+ζninfs∈I(s^)I(_Us^;_Ys)+^ϵ′log|X|n+I(_Xsn;_Us^n)+log2−I(^Xn;^Un).

Again, using ([3], Problem 3.1), we get

H(^Un)−H(M|^Xn)−I(^Xn;^Un)=H(^Un|^Xn)−H(M|^Xn)=H(^UnM|^Xn)−H(M|^Xn)=H(^Un|M^Xn).

We also know that

0≤I(^Un;^Yn|^XnM)=H(^Yn|^XnM)−H(^Yn|^{Xn Un}M)=H(^Yn|^XnM)−H(^Yn|^{Xn Un})≤H(^Yn|^Xn)−H(^Yn|^{Xn Un})=I(^Yn;^Un|^Xn)=0.

Here, we use ([3], Problem 3.1) and M−^Xn−^Yn. Thus,

I(^Un;^{Xn Yn}M)=I(^Un;^XnM)=I(^Un;^YnM)+I(^Un;^Xn|^YnM).

Thus,

I(^Un;^XnM)≥I(^Un;^YnM).

It follows that

H(^Un|M^Xn)≤H(^Un|M^Yn).

Now, we bound the right hand side of Inequality (11) using Inequality (12) and use Fano’s inequality. Thus, we have

1nI(^Xn;M)≤sups∈I(s^)I(_Xs;_Us^)−I(_Us^;_Ys)(13)+δ+ζI(_Us^;_Ys)+^ϵ′log|X|+1nlog2+_Pelog(|U|−1)+h(_Pe)n.

1nI(^Xn;M)≤sups∈I(s^)I(_Xs;_Us^)−I(_Us^;_Ys)(13)+δ+ζI(_Us^;_Ys)+^ϵ′log|X|+1nlog2+_Pelog(|U|−1)+h(_Pe)n.

Here, we use

I(_Xs;_Us^)−infs∈I(s^)I(_Us^;_Ys)=sups∈I(s^)I(_Xs;_Us^)−I(_Us^;_Ys)

I(_Xs;_Us^)−infs∈I(s^)I(_Us^;_Ys)=sups∈I(s^)I(_Xs;_Us^)−I(_Us^;_Ys)

as I(_Xs;_Us^) I(_Xs;_Us^) is constant for all s∈I(s^) s∈I(s^).

Using these results, we conclude from Inequalities (10) and (13) that

^R(PSCA)(S)⊇⋃_Us^1 ,⋯,_Us^|S^| ⋂s^∈S^_Rs^(PSCA)(S,_Us^).

^R(PSCA)(S)⊇⋃_Us^1 ,⋯,_Us^|S^| ⋂s^∈S^_Rs^(PSCA)(S,_Us^).

Using the distributive law for sets, we can see that this is equivalent to

^R(PSCA)(S)⊇⋂s^∈S^⋃_Us^Rs^(PSCA)(S,_Us^)

^R(PSCA)(S)⊇⋂s^∈S^⋃_Us^Rs^(PSCA)(S,_Us^)

(see Appendix B). We now consider the converse. Assume ^{Xn Yn Xn Yn} are distributed i.i.d. according to _{PXs Ys PXs Ys} for an arbitrary s∈S s∈S . The following calculations hold for all s∈S s∈S . Similarly to the converse part of the proof of ([7], Theorem 3.1), we have

log|K|=(a)H(K)=I(K;K^)+H(K|K^)≤(b)I(K;M^Yn)+F=I(K;M)+I(K;^Yn|M)+F≤(c)I(^Yn;MK)+F=∑i=1nI(KM^Yi−1;_Yi)+F,

log|K|=(a)H(K)=I(K;K^)+H(K|K^)≤(b)I(K;M^Yn)+F=I(K;M)+I(K;^Yn|M)+F≤(c)I(^Yn;MK)+F=∑i=1nI(KM^Yi−1;_Yi)+F,

where we use Equation (6) for (a), Fano’s inequality with F=δnlog|K|+1 F=δnlog|K|+1 and the data processing inequality in combination with K−M^Yn−K^ K−M^Yn−K^ , which follows from the definition of the compound authentication protocol for (b) and Equation (7) for (c). From the definition of the compound authentication protocol, we also know that ^Yn−^Xn−MK ^Yn−^Xn−MK . Using the definition of Markov chains, this implies ^Yi−1−^Xi−1−MK_Yi ^Yi−1−^Xi−1−MK_Yi for all i∈{2⋯n} i∈{2⋯n} (see Appendix C). (From ^Yn−^Xi−1 _Xin−MK, ^Yn−^Xi−1 _Xin−MK, we get ^Yi−1 _Yi−^Xi−1−MK_Xin ^Yi−1 _Yi−^Xi−1−MK_Xin using Implications (A11) and (A13). Then, we use Implication (A12) to get ^Yi−1−^Xi−1 _Yi−MK ^Yi−1−^Xi−1 _Yi−MKand from this we get the desired result using Implication (A13).)

The equation

I(_YiKM;^{Xi−1 Yi−1})=I(_YiKM;^Xi−1)

I(_YiKM;^{Xi−1 Yi−1})=I(_YiKM;^Xi−1)

is equivalent to ^Yi−1−^Xi−1−MK_Yi ^Yi−1−^Xi−1−MK_Yi ([3], Definition 3.9). This is equivalent to

H(_Yi|KM^{Xi−1 Yi−1})=H(_Yi|KM^Xi−1)+(H(KM|^Xi−1)−H(KM|^{Xi−1 Yi−1})).

H(_Yi|KM^{Xi−1 Yi−1})=H(_Yi|KM^Xi−1)+(H(KM|^Xi−1)−H(KM|^{Xi−1 Yi−1})).

Thus, H(_Yi|KM^Yi−1)≥H(_Yi|KM^Xi−1) H(_Yi|KM^Yi−1)≥H(_Yi|KM^Xi−1). Thus, we have

I(KM^Yi−1;_Yi)≤I(KM^Xi−1;_Yi),

I(KM^Yi−1;_Yi)≤I(KM^Xi−1;_Yi),

so

log|K|≤∑i=1nI(KM^Xi−1;_Yi)+F.

log|K|≤∑i=1nI(KM^Xi−1;_Yi)+F.

Now, we define _Ui=KM^Xi−1 _Ui=KM^Xi−1 for all i∈{1⋯n} i∈{1⋯n} . This implies _Ui−_Xi−_{Yi Ui}−_Xi−_Yi for all i∈{1⋯n} i∈{1⋯n} , which can again be seen using the results from Appendix C. Let Q be a time sharing RV independent of all others and uniformly distributed on Q={1⋯n} Q={1⋯n} and let U=Q_UQ U=Q_UQ , X=_XQ X=_XQ and Y=_YQ Y=_YQ. Then,

_PUXY((u,q),x,y)=_{PQUq Xq Yq}(q,u,x,y)=(a)_PQUq|Xq(u,q|x)_{PXq Yq}(x,y)

_PUXY((u,q),x,y)=_{PQUq Xq Yq}(q,u,x,y)=(a)_PQUq|Xq(u,q|x)_{PXq Yq}(x,y)

for all (u,q,x,y)∈_Uq×Q×X×Y (u,q,x,y)∈_Uq×Q×X×Y , where (a) a) follows from _Uq−_Xq−_{Yq Uq}−_Xq−_Yqand the independence of Q. We have

_PXY(x,y)=∑q,u_{PQUq Xq Yq}(q,u,x,y)=∑i=1n1n_{PXi Yi}(x,y)=(a)_{PXs Ys}(x,y)=_{PXq Yq}(x,y)

_PXY(x,y)=∑q,u_{PQUq Xq Yq}(q,u,x,y)=∑i=1n1n_{PXi Yi}(x,y)=(a)_{PXs Ys}(x,y)=_{PXq Yq}(x,y)

for an arbitrary q∈Q q∈Q and (x,y)∈X×Y (x,y)∈X×Y , where (a) (a) follows as _{PXi Yi}=_{PXs Ys PXi Yi}=_{PXs Ys} for all i∈Q i∈Q as the RVs ^{Xn Yn Xn Yn} are generated i.i.d. We also have for all (u,q,x)∈_Uq×Q×X (u,q,x)∈_Uq×Q×X

_PU|X(u,q|x)=_{∑y∈Y PQUq Xq Yq}(q,u,x,y)_PX(x)=_{PQUq Xq}(q,u,x)_PXq (x)=_PQUq|Xq(q,u|x).

_PU|X(u,q|x)=_{∑y∈Y PQUq Xq Yq}(q,u,x,y)_PX(x)=_{PQUq Xq}(q,u,x)_PXq (x)=_PQUq|Xq(q,u|x).

Thus, _PUXY((u,q),x,y)=_PXY(x,y)_PU|X(u,q|x), _PUXY((u,q),x,y)=_PXY(x,y)_PU|X(u,q|x), which means U−X−Y U−X−Y. We also have

log|K|≤∑i=1nI(_Ui,_Yi)+F=n∑i=1n1nI(_UQ,Y|Q=i)+F=nI(_UQ;Y|Q)+F=nH(Y|Q)−H(Y|_UQQ)+F≤n(H(Y)−H(Y|_UQQ))+F=nI(_UQQ;Y)+F=nI(U;Y)+F.

log|K|≤∑i=1nI(_Ui,_Yi)+F=n∑i=1n1nI(_UQ,Y|Q=i)+F=nI(_UQ;Y|Q)+F=nH(Y|Q)−H(Y|_UQQ)+F≤n(H(Y)−H(Y|_UQQ))+F=nI(_UQQ;Y)+F=nI(U;Y)+F.

Thus, using the definition of F, we get

1nlog|K|≤^(1−δ)−1(I(U;Y)+1n),

1nlog|K|≤^(1−δ)−1(I(U;Y)+1n),

which implies

1nlog|K|≤I(U;Y)+δ

1nlog|K|≤I(U;Y)+δ

for δ>0 δ>0and n large enough. We also consider

I(^Xn;M)=H(M)−H(M|^Xn)≥H(M|^Yn)−H(KM|^Xn)=H(KM|^Yn)−H(K|^YnM)−H(KM|^Xn).

I(^Xn;M)=H(M)−H(M|^Xn)≥H(M|^Yn)−H(KM|^Xn)=H(KM|^Yn)−H(K|^YnM)−H(KM|^Xn).

From the definition of the compound storage model, we know K−M^Yn−K^ K−M^Yn−K^ . Using the data processing inequality, we get I(K;M^Yn)≥I(K;K^), I(K;M^Yn)≥I(K;K^), which means H(K|M^Yn)≤H(K|K^)≤F H(K|M^Yn)≤H(K|K^)≤F, where the last inequality follows from Fano’s inequality. Thus,

I(^Xn;M)≥H(KM|^Yn)−H(KM|^Xn)−F=I(KM;^Xn)−I(KM;^Yn)−F=∑i=1nI(KM;_Xi|^Xi−1)−∑i=1nI(KM;_Yi|^Yi−1)−F=(a)∑i=1nI(KM^Xi−1;_Xi)−∑i=1_nkI(KM^Yi−1;_Yi)−F≥(b)∑i=1nI(KM^Xi−1;_Xi)−∑i=1nI(KM^Xi−1;_Yi)−F,

I(^Xn;M)≥H(KM|^Yn)−H(KM|^Xn)−F=I(KM;^Xn)−I(KM;^Yn)−F=∑i=1nI(KM;_Xi|^Xi−1)−∑i=1nI(KM;_Yi|^Yi−1)−F=(a)∑i=1nI(KM^Xi−1;_Xi)−∑i=1_nkI(KM^Yi−1;_Yi)−F≥(b)∑i=1nI(KM^Xi−1;_Xi)−∑i=1nI(KM^Xi−1;_Yi)−F,

where (a) follows as _{Xi Xi} and _{Yi Yi}are i.i.d. and (b) follows from Inequality (14). With our definition of U, X and Y and the same argumentation as before, we get

1nI(^Xn;M)≥I(U;X)−I(U;Y)−Fn≥(a)I(U;X)−I(U;Y)−δ

1nI(^Xn;M)≥I(U;X)−I(U;Y)−Fn≥(a)I(U;X)−I(U;Y)−δ

for n large enough, where, for ((a) (a) , we use the definition of F and Inequality (16). We have for all (u,q,x)∈_Uq×Q×X (u,q,x)∈_Uq×Q×X

_PUX((q,u),x)=_PQ(q)_{PUq Xq}(u,x)=_{PKM^Xq−1 Xq}(k,m,^xq−1,_xq)_PQ(q)=_PQ(q)∑_xq+1nPKM^Xn(k,m,^xn)=(a)_PQ(q)∑_xq+1nP^Xn (^xn)_PM|^Xn(m|^xn)_PK|^Xn(k|^xn)=_PQ(q)∑_xq+1nP^Xn (^xn)Θ(^xn)Φ(^xn),

_PUX((q,u),x)=_PQ(q)_{PUq Xq}(u,x)=_{PKM^Xq−1 Xq}(k,m,^xq−1,_xq)_PQ(q)=_PQ(q)∑_xq+1nPKM^Xn(k,m,^xn)=(a)_PQ(q)∑_xq+1nP^Xn (^xn)_PM|^Xn(m|^xn)_PK|^Xn(k|^xn)=_PQ(q)∑_xq+1nP^Xn (^xn)Θ(^xn)Φ(^xn),

where (a) follows from M−^Xn−K M−^Xn−K , which follows from the definition of the compound authentication protocol. As _{P^Xn P^Xn} is the same for all s∈I(s^) s∈I(s^) , s^∈S^ s^∈S^ , this result implies that _{PUX PUX} is the same for all s∈I(s^) s∈I(s^) , s^∈S^ s^∈S^ . We get the bounds (16) and (17) for each s∈S s∈S . We denote the corresponding RVs UXY UXY by _{Us Xs Ys Us Xs Ys} for all s∈S s∈S . The joint distribution of _{Xs Ys Xs Ys} is _{PXs Ys}∈S _{PXs Ys}∈S as we see from Equation (15). Thus, Equation (18) and the Inequalities (16) and (17) for all s∈S s∈Simply

_RPSCS(S)⊆⋃_Us^1 ,⋯,_Us^|S^| ⋂s^∈S^_Rs^(PSCA)(S,_Us^).

_RPSCS(S)⊆⋃_Us^1 ,⋯,_Us^|S^| ⋂s^∈S^_Rs^(PSCA)(S,_Us^).

We again use the distributive law for sets to get our result. The bounds on the cardinality of the alphabet of the auxiliary random variables can be derived as in [19]. ☐

Remark 9.

This result implies Theorem 2 as we use a deterministic decoder for the achievability proof.

Remark 10.

In [19], the authors also derive the compound capacity region for |S|<∞ |S|<∞ , but, in contrast to this work, they consider deterministic protocols and require strong secrecy instead of perfect secrecy when defining achievability. This compound capacity region equals _RPSCA(S) _RPSCA(S) .

8. Secure Storage

We now discuss some other applications of the already proven results apart from authentication. For this purpose, we take a look at some results for secure storage from [13,14], which follow directly from our results for authentication. Here, we again consider compound sets S S with |S^|<∞ |S^|<∞.

In [13], we consider the following model for secure storage with source uncertainty, where the corresponding scenario is depicted in Figure 3.

Figure 3. Secure storage process with source uncertainty (as considered in [13]).

Definition 10.

Let n∈N n∈N . The compound storage model consists of a set S⊆P(X×Y) S⊆P(X×Y) of DMMSs with generic variables _{Xs Ys Xs Ys} , s∈S s∈S , (all on the same alphabets X X and Y Y ), a source _PDn ∈P(_Dn) _PDn ∈P(_Dn) that puts out a RV _{Dn Dn} , the (possibly randomized) encoder _Φn:^Xn×_Dn→M _Φn:^Xn×_Dn→M and the (possibly randomized) decoder _Ψn:^Yn×M→_{D^n Ψn}:^Yn×M→_D^n . Let ^{Xn Xn} and ^{Yn Yn} be the output of one of the DMMSs in S S , i.e., _PXY=_{PXs Ys PXY}=_{PXs Ys} for an s∈S s∈S , but s is not known. _{Dn Dn} is independent of ^{Xn Yn Xn Yn} . The RV M is generated from ^{Xn Xn} and _{Dn Dn} using _{Φn Φn} . The RV _{D^n D^n} is generated from ^{Yn Yn} and M using _{Ψn Ψn} . We use the term compound storage protocol for (_Φn,_Ψn) (_Φn,_Ψn) . Additionally, it holds that, for all δ>0 δ>0 , there is an _n0=_n0(δ) _n0=_n0(δ) such that for all n≥_n0 n≥_n0

1nD(_PDn ∥_UDn )<δ.

1nD(_PDn ∥_UDn )<δ.

We define achievability for this model.

Definition 11.

A tuple (R,L) (R,L) , R,L≥0 R,L≥0 , is an achievable storage rate versus privacy-leakage rate pair for the compound storage model if for every δ>0 δ>0 there is an _n0=_n0(δ) _n0=_n0(δ) such that for all n≥_n0 n≥_n0 there exists a compound storage protocol such that for all s∈S s∈S

Pr(_Dn=_D^n)≥1−δ,I(M;_Dn)=0,1nlog|_Dn|≥R−δ,1nI(M;^Xn)≤L+δ,

Pr(_Dn=_D^n)≥1−δ,I(M;_Dn)=0,1nlog|_Dn|≥R−δ,1nI(M;^Xn)≤L+δ,

where _PXY=_{PXs Ys PXY}=_{PXs Ys} . We denote the corresponding storage protocols by PSCS-Protocols (Perfect-Secrecy- Compound-Storage-Protocols).

Definition 12.

The set of achievable rate pairs that are achievable using PSCS-Protocols is called the compound capacity region _RPSCS(S) _RPSCS(S) .

We then can prove the following result.

Theorem 6.

It holds that

_RPSCS(S)=_RPSCA(S).

_RPSCS(S)=_RPSCA(S).

Remark 11.

The compound storage model is essentially equivalent to a compound version of the chosen secret system in [7]. For this reason, Theorem 6 follows using the same approach as the authors of [7].

We combine source compression and secure storage in [14] by considering the following model, which models the scenario depicted in Figure 4.

Figure 4. Secure storage of a source (as considered in [14]).

Definition 13.

Let k,_nk∈N k,_nk∈N . The compound source storage model consists of a set S⊆P(X×Y) S⊆P(X×Y) of DMMSs with generic variables _{Xs Ys Xs Ys} , s∈S s∈S , (all on the same alphabets X X and Y Y ), a general source V V [20] that fulfills the strong converse property, the (possibly randomized) encoder _Φk:^X_nk ×^Vk→M _Φk:^X_nk ×^Vk→M and the (possibly randomized) decoder _Ψk:^Y_nk ×M→^{V^k} _Ψk:^Y_nk ×M→^{V^k} . Let ^{X_nk X_nk} and ^{Y_nk Y_nk} be the output of one of the DMMSs in S S , i.e., _PXY=_{PXs Ys PXY}=_{PXs Ys} for an s∈S s∈S , but s is not known. The RV M is generated from ^{X_nk X_nk} and ^{Vk Vk} using _{Φk Φk} . The RV ^{V^k V^k} is generated from ^{Y_nk Y_nk} and M using _{Ψk Ψk} . We use the term compound source storage protocol for (_Φk,_Ψk) (_Φk,_Ψk) .

For this model, we define achievability where we consider the output of the PUF source as a resource.

Definition 14.

A tuple (B,L) (B,L) , B,L≥0 B,L≥0 , is an achievable performance pair for the compound source storage model if, for every δ>0 δ>0 , there is a _k0=_k0(δ) _k0=_k0(δ) such that, for all k≥_k0, k≥_k0, there exists a compound source storage protocol such that, for all s∈S, s∈S,

Pr(^Vk=^{V^k})≥1−δ,I(M;^Vk)=0,_nkk≤B+δ,1_nkI(M;^X_nk )≤L+δ,

Pr(^Vk=^{V^k})≥1−δ,I(M;^Vk)=0,_nkk≤B+δ,1_nkI(M;^X_nk )≤L+δ,

where _PXY=_{PXs Ys PXY}=_{PXs Ys} . We denote the corresponding compound source storage protocols by PSCSS-Protocols (Perfect-Secrecy-Compound-Source-Storage-Protocols).

Definition 15.

The set of achievable performance pairs that are achievable using PSCSS-Protocols is called the optimal performance region _RPSCSS(S,V) _RPSCSS(S,V) .

We then can prove the following results.

Theorem 7.

It holds that

_RPSCSS(S,V)⊇⋂s^∈S^⋃_Us^{(B,L):B≥H¯(V)_infs∈I(s^)I(_Us^;_Ys),L≥sups∈I(s^)I(_Us^;_Xs)−I(_Us^;_Ys)}=(a)⋂s^∈S^⋃_{Us^Rs^(PSCSS)}(S,V,_Us^),

_RPSCSS(S,V)⊇⋂s^∈S^⋃_Us^{(B,L):B≥H¯(V)_infs∈I(s^)I(_Us^;_Ys),L≥sups∈I(s^)I(_Us^;_Xs)−I(_Us^;_Ys)}=(a)⋂s^∈S^⋃_{Us^Rs^(PSCSS)}(S,V,_Us^),

where for (a) (a) we define _Rs^(PSCSS)(S,V,_Us^) _Rs^(PSCSS)(S,V,_Us^) appropriately. For all s^∈S^ s^∈S^ , the union is over all RVs _{Us^ Us^} such that, for all s∈I(s^), s∈I(s^), we have _Us^−_Xs−_{Ys Us^}−_Xs−_Ys .

Theorem 8.

For stationary ergodic sources V V , it holds that

_RPSCSS(S,V)=⋂s^∈S^⋃_{Us^Rs^(PSCSS)}(S,V,_Us^).

_RPSCSS(S,V)=⋂s^∈S^⋃_{Us^Rs^(PSCSS)}(S,V,_Us^).

For all s^∈S^ s^∈S^ , the union is over all RVs _{Us^ Us^} such that, for all s∈I(s^) s∈I(s^) , we have _Us^−_Xs−_{Ys Us^}−_Xs−_Ys . For |S|<∞ |S|<∞ , we only have to consider RVs _{Us^ Us^} with |_Us^|≤|X|+|I(s^)| |_Us^|≤|X|+|I(s^)| .

9. Conclusions

We derived the capacity region for the (compound) authentication model requiring perfect secrecy and uniform distribution of the key generated for authentication and compared the result to existing results where only strong secrecy and a weaker condition on the key distribution is required. The two capacity regions are the same. We could prove this result by allowing for randomized encoders, which are not necessarily used when deriving the capacity region corresponding to the weaker definition of achievability. We saw that we can use the results for authentication to prove corresponding results for secure storage.

As already mentioned, compound sources do not only model source uncertainty but also model attacks where an attacker can influence parameters of the source while the legitimate parties do not know which parameters the attacker chose. It is essential that in this scenario the parameter is constant for all symbols read from the source. An attack where the parameter can be varied while the source is used is fundamentally stronger. A characterization of achievable rates for this attack scenario is not known, except for the source model for secret key generation, which has been derived in [21]. For an overview of these types of attacks, see [22]. Recently, the corresponding problem for wiretap channels could be solved [23,24]. For the source model, the attacker can choose his strategy depending on the public data, which is a difficulty that does not appear for wiretap channels. Nevertheless the authors hope that, using techniques from the works concerning the wiretap channel, the open problem for the source model can be solved.

Acknowledgments

Funding is acknowledged from the German Research Foundation (DFG) via grant BO 1734/20-1 and from the Federal Ministry of Education and Research (BMBF) via grant 16KIS0118K. Holger Boche would like to thank Rainer Plaga, Federal Office for Information Security (BSI), for the discussion on PUFs and issues concerning different secrecy measures.

Author Contributions

Sebastian Baur and Holger Boche conceived this study and derived the results. Sebastian Baur wrote the manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Proof of Theorem 4

Proof.

We prove the result for compound codes with the additional constraint on the decoding sets that, for ζ>0, ζ>0,it holds that

^ϕ−1(m)⊂⋃W∈W_TW,ζn(f(m))

^ϕ−1(m)⊂⋃W∈W_TW,ζn(f(m))

for all messages m∈_Mf m∈_Mf . Additionally, for ^ζ′>0, ^ζ′>0,we require

f(m)∈A˜=A∩_TP,^ζ′n

f(m)∈A˜=A∩_TP,^ζ′n

for all m∈_Mf m∈_Mf . First, consider the case that W W is a finite set. Let (f,ϕ) (f,ϕ) be such a code that can not be extended. Thus, for all ^xn∈A˜ ^xn∈A˜ , there is a W∈W W∈Wsuch that

^Wn(⋃W˜∈W_TW˜,ζn(^xn)\B|^xn)1−ϵ,

^Wn(⋃W˜∈W_TW˜,ζn(^xn)\B|^xn)1−ϵ,

where B=_⋃m∈Mf ^ϕ−1(m) B=_⋃m∈Mf ^ϕ−1(m). It also holds that

^Pn(A˜)≥^Pn(A)+^Pn(_TP,^ζ′n)−1≥η/2

^Pn(A˜)≥^Pn(A)+^Pn(_TP,^ζ′n)−1≥η/2

for n large enough. We now consider the set

_A˜W={^xn∈A˜:^Wn(⋃W˜∈W_TW˜,ζn(^xn)\B|^xn)1−ϵ}.

_A˜W={^xn∈A˜:^Wn(⋃W˜∈W_TW˜,ζn(^xn)\B|^xn)1−ϵ}.

We know _{⋃W∈W A˜W}=A˜ _{⋃W∈W A˜W}=A˜ , as for all ^xn∈A˜ ^xn∈A˜ there is at least one W∈W W∈W with Inequality (A3). Thus,

η/2≤^Pn(⋃W∈W_A˜W)≤∑W∈W^Pn(_A˜W)≤|W|maxW∈W^Pn(_A˜W).

η/2≤^Pn(⋃W∈W_A˜W)≤∑W∈W^Pn(_A˜W)≤|W|maxW∈W^Pn(_A˜W).

Thus, there is a W¯∈W W¯∈W such that for all ^xn∈_A˜W¯ ^xn∈_A˜W¯

^W¯n(⋃W˜∈W_TW˜,ζn(^xn)\B|^xn)1−ϵ

^W¯n(⋃W˜∈W_TW˜,ζn(^xn)\B|^xn)1−ϵ

and

^Pn(_A˜W¯)≥η2|W|.

^Pn(_A˜W¯)≥η2|W|.

Thus,

^W¯n(^Bc|^xn)+^W¯n(⋃W˜∈W_TW˜,ζn(^xn)|^xn)−^W¯n(^Bc∪⋃W˜∈W_TW˜,ζn(^xn)|^xn)=^W¯n(⋃W˜∈W_TW˜,ζn(^xn)\B|^xn)1−ϵ,

^W¯n(^Bc|^xn)+^W¯n(⋃W˜∈W_TW˜,ζn(^xn)|^xn)−^W¯n(^Bc∪⋃W˜∈W_TW˜,ζn(^xn)|^xn)=^W¯n(⋃W˜∈W_TW˜,ζn(^xn)\B|^xn)1−ϵ,

which means

^W¯n(B|^xn)>ϵ−δ

^W¯n(B|^xn)>ϵ−δ

for all ^xn∈_A˜W¯ ^xn∈_A˜W¯ as ^W¯n(^Bc|^xn)=1−^W¯n(B|^xn) ^W¯n(^Bc|^xn)=1−^W¯n(B|^xn) , ^W¯n(_{⋃W˜∈W TW˜,ζn}(^xn)|^xn)≥1−δ ^W¯n(_{⋃W˜∈W TW˜,ζn}(^xn)|^xn)≥1−δ for δ>0 δ>0 and n large enough and ^W¯n(^Bc∪_{⋃W˜∈W TW˜,ζn}(^xn)|^xn)≤1 ^W¯n(^Bc∪_{⋃W˜∈W TW˜,ζn}(^xn)|^xn)≤1. Thus, we have

^W¯n(B∩⋃^x¯n∈_{TP,^ζ′nTW¯,ζn}(^x¯n)|^xn)≥^W¯n(B|^xn)+^W¯n(⋃^x¯n∈_{TP,^ζ′nTW¯,ζn}(^x¯n)|^xn)−1≥ϵ−δ+(1−ξ)−1=ϵ−ξ−δ

^W¯n(B∩⋃^x¯n∈_{TP,^ζ′nTW¯,ζn}(^x¯n)|^xn)≥^W¯n(B|^xn)+^W¯n(⋃^x¯n∈_{TP,^ζ′nTW¯,ζn}(^x¯n)|^xn)−1≥ϵ−δ+(1−ξ)−1=ϵ−ξ−δ

for all ^xn∈_A˜W¯ ^xn∈_A˜W¯ , ξ>0 ξ>0 and n large enough. (We choose ϵ ϵ , δ δ and ξ ξ such that ϵ−ξ−δ>0 ϵ−ξ−δ>0 .) Thus, ^B′=B∩_{⋃^x¯n∈TP,^ζ′n TW¯,ζn}(^x¯n) ^B′=B∩_{⋃^x¯n∈TP,^ζ′n TW¯,ζn}(^x¯n) is an ϵ−ξ−δ ϵ−ξ−δ image of _{A˜W¯ A˜W¯} (see [3]). Thus,

|B∩⋃^x¯n∈_{TP,^ζ′nTW¯,ζn}(^x¯n)|≥_g^W¯n (_A˜W¯,ϵ−ξ−δ),

|B∩⋃^x¯n∈_{TP,^ζ′nTW¯,ζn}(^x¯n)|≥_g^W¯n (_A˜W¯,ϵ−ξ−δ),

where _g^W¯n (_A˜W¯,ϵ−ξ−δ) _g^W¯n (_A˜W¯,ϵ−ξ−δ) is defined as in [3]. We have

^(PW¯)n(^B′)=∑^yn∈^B′∏i=1n∑a∈XP(a)W¯(_yi|a)=(a)∑^yn∈^B′∑^xn∈^Xn∏i=1nP(_xi)W¯(_yi|_xi)≥∑^yn∈^B′∑^xn∈_A˜W¯^Pn(^xn)^W¯n(^yn|^xn)=∑^xn∈_A˜W¯^Pn(^xn)∑^yn∈^B′W¯n(^yn|^xn)≥(ϵ−δ−ξ)^Pn(_A˜W¯)≥η/2(ϵ−δ−ξ)1|W|,

^(PW¯)n(^B′)=∑^yn∈^B′∏i=1n∑a∈XP(a)W¯(_yi|a)=(a)∑^yn∈^B′∑^xn∈^Xn∏i=1nP(_xi)W¯(_yi|_xi)≥∑^yn∈^B′∑^xn∈_A˜W¯^Pn(^xn)^W¯n(^yn|^xn)=∑^xn∈_A˜W¯^Pn(^xn)∑^yn∈^B′W¯n(^yn|^xn)≥(ϵ−δ−ξ)^Pn(_A˜W¯)≥η/2(ϵ−δ−ξ)1|W|,

where (a) can be shown with induction. Using ([3], Lemma 2.14), we get for n large enough

1nlog|^B′|≥H(PW¯)−(γ+1nlog|W|)

1nlog|^B′|≥H(PW¯)−(γ+1nlog|W|)

with γ>0 γ>0. Additionally, we have

|^B′|=(a)|⋃m∈_Mf^ϕ−1(m)∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)|=|⋃m∈_Mf^ϕ−1(m)∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)|≤∑m∈_Mf|^ϕ−1(m)∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)|≤(b)∑m∈_Mf|⋃W∈W_TW,ζn(f(m))∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)|,

|^B′|=(a)|⋃m∈_Mf^ϕ−1(m)∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)|=|⋃m∈_Mf^ϕ−1(m)∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)|≤∑m∈_Mf|^ϕ−1(m)∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)|≤(b)∑m∈_Mf|⋃W∈W_TW,ζn(f(m))∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)|,

where (a) follows from the definition of B and (b) follows from Subset Relationship (A1). We now define

_Wm*={W∈W:_TW,ζn(f(m))∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)≠∅}.

_Wm*={W∈W:_TW,ζn(f(m))∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)≠∅}.

As

_TW¯,ξn(f(m))∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)≠∅

_TW¯,ξn(f(m))∩⋃^xn∈_{TP,^ζ′nTW¯,ζn}(^xn)≠∅

for all m∈_Mf m∈_Mf , which follows form Relation (A2), we have

|^B′|≤∑m∈_MfmaxW∈_Wm*|_TW,ζn(f(m))|·|W|.

|^B′|≤∑m∈_MfmaxW∈_Wm*|_TW,ζn(f(m))|·|W|.

Let

^W*=argmaxW∈_{⋃m∈Mf Wm*}|_TW,ζn(f(m))|.

^W*=argmaxW∈_{⋃m∈Mf Wm*}|_TW,ζn(f(m))|.

Thus, we get the upper bound

|^B′|≤|_Mf|exp(n(H(^W*|P)+^γ′+log|W|n)),

|^B′|≤|_Mf|exp(n(H(^W*|P)+^γ′+log|W|n)),

^γ′>0 ^γ′>0 ([3], Lemma 2.13).

For all W∈_Wm* W∈_Wm* and all m∈_Mf m∈_Mf there is a ^yn∈^{Yn yn}∈^Yn such that ^yn∈_TW,ζn(f(m)) ^yn∈_TW,ζn(f(m)) and ^yn∈_TW¯,ζn(^xn) ^yn∈_TW¯,ζn(^xn) for a ^xn∈_TP,^ζ′n ^xn∈_TP,^ζ′n . Using Relation (A2), we have ^yn∈_{TPW,(ζ+^ζ′)|X|n} ^yn∈_{TPW,(ζ+^ζ′)|X|n} and ^yn∈_{TPW¯,(ζ+^ζ′)|X|n} ^yn∈_{TPW¯,(ζ+^ζ′)|X|n} (see ([3], Lemma 2.10)). Let ^ζ″=(ζ+^ζ′)|X| ^ζ″=(ζ+^ζ′)|X|. Thus,

∥PW−PW¯_∥1=∑b∈Y|PW(b)−PW¯(b)|=∑b∈Y|PW(b)−N(b|^yn)/n+N(b|^yn)/n−PW¯(b)|≤∑b∈Y|PW(b)−N(b|^yn)/n|+|N(b|^yn)/n−PW¯(b)|≤2|Y|^ζ″.

∥PW−PW¯_∥1=∑b∈Y|PW(b)−PW¯(b)|=∑b∈Y|PW(b)−N(b|^yn)/n+N(b|^yn)/n−PW¯(b)|≤∑b∈Y|PW(b)−N(b|^yn)/n|+|N(b|^yn)/n−PW¯(b)|≤2|Y|^ζ″.

Using ([3], Lemma 2.7), we have |H(PW)−H(PW¯)|≤2|Y|^ζ″log12^ζ″ |H(PW)−H(PW¯)|≤2|Y|^ζ″log12^ζ″ for all W∈_Wm* W∈_Wm* and all m∈_Mf m∈_Mf . Using Inequalities (A4), (A5) and the fact that ^W*∈_Wm* ^W*∈_Wm* for a m∈_Mf m∈_Mf , we get for γ γ , ^{γ′ γ′} , ζ ζ and ^{ζ′ ζ′}small enough and n large enough

1nlog|_Mf|≥H(PW¯)−H(^W*|P)−γ−^γ′−2log|W|n≥H(P^W*)−2|Y|^ζ″log12^ζ″−H(^W*|P)−γ−^γ′−2log|W|n≥I(P;^W*)−τ≥minW∈WI(P;W)−τ.

1nlog|_Mf|≥H(PW¯)−H(^W*|P)−γ−^γ′−2log|W|n≥H(P^W*)−2|Y|^ζ″log12^ζ″−H(^W*|P)−γ−^γ′−2log|W|n≥I(P;^W*)−τ≥minW∈WI(P;W)−τ.

Now, consider the case of an infinite set W W . Let M∈N M∈N , M≥^2|Y|2 M≥^2|Y|2 . We construct the set ^{W* W*} of channels ^W*:X→Y ^W*:X→Y with the following properties. For all W∈W W∈W , there is a ^W*∈^{W* W*}∈^W*with

|W(y|x)−^W*(y|x)|≤|Y|M

|W(y|x)−^W*(y|x)|≤|Y|M

for all (x,y)∈X×Y (x,y)∈X×Y,

W(y|x)≤^W*(y|x)^e2|Y|2/M

W(y|x)≤^W*(y|x)^e2|Y|2/M

for all (x,y)∈X×Y (x,y)∈X×Yand

|^{W* |≤(1+M)|X||Y|}.

|^{W* |≤(1+M)|X||Y|}.

Such a construction is possible as described in [18]. Using Inequalities (A9) and (A6), we know that there is a compound (n,^ϵ′) (n,^ϵ′) -code, ϵ>^ϵ′>0 ϵ>^ϵ′>0 , for ^{W* W*}with

1nlog|_Mf|≥minW∈^W*I(P;W)−τ

1nlog|_Mf|≥minW∈^W*I(P;W)−τ

if M depends on n polynomially. We now show that this code is a compound (n,ϵ) (n,ϵ) -code for W Wwith

1nlog|_Mf|≥infW∈WI(P;W)−τ.

1nlog|_Mf|≥infW∈WI(P;W)−τ.

Let ^W*=arg_minW∈^W*I(P;W) ^W*=arg_minW∈^W*I(P;W) and let W∈W W∈W be the W corresponding to ^{W* W*}. Then, we have

infW∈WI(P;W)≤(a)I(P;W)≤(b)I(P;^W*)+β=(c)minW∈^W*I(P;W)+β,

infW∈WI(P;W)≤(a)I(P;W)≤(b)I(P;^W*)+β=(c)minW∈^W*I(P;W)+β,

β>0 β>0 , where (a) follows from the definition of the infimum, (b) follows as Inequality (A7) implies

∥W(·|a)−^W* _(·|a)∥1≤^|Y|2M

∥W(·|a)−^W* _(·|a)∥1≤^|Y|2M

for all a∈X a∈X . Thus, using ([3], Lemma 2.7), we have

|I(P;W)−I(P;^W*)|=|H(W|P)−H(^W*|P)|=|∑a∈XP(a)(H(W(·|a))−H(^W*(·|a)))|≤∑a∈XP(a)|H(W(·|a))−H(^W*(·|a))|≤^|Y|2MlogM|Y|.

|I(P;W)−I(P;^W*)|=|H(W|P)−H(^W*|P)|=|∑a∈XP(a)(H(W(·|a))−H(^W*(·|a)))|≤∑a∈XP(a)|H(W(·|a))−H(^W*(·|a))|≤^|Y|2MlogM|Y|.

For M=ⁿ² M=ⁿ² , we get (b) for n large enough. Finally, (c) follows from the choice of ^{W* W*} . Additionally, it holds that for each W∈W W∈W there is a ^W*∈^{W* W*}∈^W*with

^Wn(^yn|^xn)≤^{e2|Y|2n/M (W*)n}(^yn|^xn),

^Wn(^yn|^xn)≤^{e2|Y|2n/M (W*)n}(^yn|^xn),

which follows from Inequality (A8). Thus, for all m∈_Mf m∈_Mf, we have

^Wn(^(ϕ−1(m))c|f(m))≤^(W*)n(^(ϕ−1(m))c|f(m))^e2|Y|2n/M≤a)^{e2|Y|2/n ϵ′},

^Wn(^(ϕ−1(m))c|f(m))≤^(W*)n(^(ϕ−1(m))c|f(m))^e2|Y|2n/M≤a)^{e2|Y|2/n ϵ′},

where (a) follows from our choice of M. Thus, for n large enough and ^{ϵ′ ϵ′}small enough, we have

^Wn(^(ϕ−1(m))c|f(m))≤ϵ.

^Wn(^(ϕ−1(m))c|f(m))≤ϵ.

☐

Appendix B. Equivalence of Rate Regions

We have

⋃_Us^1 ,⋯,_Us^|S^| ⋂s^∈S^_Rs^(PSCA)(S,_Us^)=(a)⋃_Us^1 ⋃_Us^2 ,⋯,_Us^|S^| ⋂s^∈S^\{_s^1}_Rs^(S,_Us^)∩_Rs^1 (S,_Us^1 ),

⋃_Us^1 ,⋯,_Us^|S^| ⋂s^∈S^_Rs^(PSCA)(S,_Us^)=(a)⋃_Us^1 ⋃_Us^2 ,⋯,_Us^|S^| ⋂s^∈S^\{_s^1}_Rs^(S,_Us^)∩_Rs^1 (S,_Us^1 ),

where we drop the (PSCA) (PSCA)for a shorter notation in (a). We now use the distributive law for sets and get

⋃_Us^1 ⋃_Us^2 ,⋯,_Us^|S^| ⋂s^∈S^\{_s^1}_Rs^(S,_Us^)∩_Rs^1 (S,_Us^1 ).

⋃_Us^1 ⋃_Us^2 ,⋯,_Us^|S^| ⋂s^∈S^\{_s^1}_Rs^(S,_Us^)∩_Rs^1 (S,_Us^1 ).

Now, we use the distributive law again and get

⋃_Us^2 ,⋯,_Us^|S^| ⋂s^∈S^\{_s^1}_Rs^(S,_Us^)∩⋃_{Us^1 Rs^1} (S,_Us^1 ).

⋃_Us^2 ,⋯,_Us^|S^| ⋂s^∈S^\{_s^1}_Rs^(S,_Us^)∩⋃_{Us^1 Rs^1} (S,_Us^1 ).

Following these steps for all s^∈S^ s^∈S^, we get

⋂s^∈S^⋃_Us^Rs^(PSCS)(S,_Us^).

⋂s^∈S^⋃_Us^Rs^(PSCS)(S,_Us^).

Appendix C. Modifying Markov Chains

Theorem A1.

Let A, B, C and D be jointly distributed RVs. It holds that

(A10)A−B−C⇔C−B−A,(A11)AB−C−D⇒B−C−D,(A12)AB−C−D⇒A−BC−D,_PABC(a,b,c)=_PAB(a,b)_PC(c)∀(a,b,c)∈A×B×C,(A13)∧A−BC−D⇒A−B−CD.

(A10)A−B−C⇔C−B−A,(A11)AB−C−D⇒B−C−D,(A12)AB−C−D⇒A−BC−D,_PABC(a,b,c)=_PAB(a,b)_PC(c)∀(a,b,c)∈A×B×C,(A13)∧A−BC−D⇒A−B−CD.

Proof.

We give a proof for each of the statements.

1. We have

_PABC(a,b,c)=(a)_PA|B(a|b)_PBC(b,c)=_PA|B(a|b)_PC|B(c|b)_PB(b)=_PAB(a,b)_PC|B(c|b)

_PABC(a,b,c)=(a)_PA|B(a|b)_PBC(b,c)=_PA|B(a|b)_PC|B(c|b)_PB(b)=_PAB(a,b)_PC|B(c|b)

for all (a,b,c)∈A×B×C (a,b,c)∈A×B×C . Here, (a) (a) follows from A−B−C A−B−C . Thus, we see that Equivalence (A10) is true.

2. We have _PABCD(a,b,c,d)=_PAB|C(a,b|c)_PCD(c,d) _PABCD(a,b,c,d)=_PAB|C(a,b|c)_PCD(c,d) for all (a,b,c,d)∈A×B×C×D (a,b,c,d)∈A×B×C×D from AB−C−D AB−C−D . Summing both sides over all b∈B b∈B, we get Implication (A11).

3. We have

_PABCD(a,b,c,d)=(a)_PAB|C(a,b|c)_PCD(c,d)=_PB|C(b,c)_PA|BC(a|b,c)_PCD(c,d)=(b)_PA|BC(a|b,c)_PB|CD(b|c,d)_PCD(c,d)=_PA|BC(a|b,c)_PBCD(b,c,d)

_PABCD(a,b,c,d)=(a)_PAB|C(a,b|c)_PCD(c,d)=_PB|C(b,c)_PA|BC(a|b,c)_PCD(c,d)=(b)_PA|BC(a|b,c)_PB|CD(b|c,d)_PCD(c,d)=_PA|BC(a|b,c)_PBCD(b,c,d)

for all (a,b,c,d)∈A×B×C×D (a,b,c,d)∈A×B×C×D , where (a) (a) follows from AB−C−D AB−C−D and (b) (b)from Implication (A11). This means Implication (A12) is true.

4. We have

_PABCD(a,b,c,d)=(a)_PA|BC(a|b,c)_PBCD(b,c,d)=_PA|BC(a|b,c)_PD|BC(d|b,c)_PBC(b,c)=(b)_PAB(a,b)_PC(c)_PD|BC(d|b,c)=_PA|B(a|b)_PB(b)_PC(c)_PD|BC(d|b,c)=(c)_PA|B(a|b)_PBC(b,c)_PD|BC(d|b,c)=_PA|B(a|b)_PBCD(b,c,d)

_PABCD(a,b,c,d)=(a)_PA|BC(a|b,c)_PBCD(b,c,d)=_PA|BC(a|b,c)_PD|BC(d|b,c)_PBC(b,c)=(b)_PAB(a,b)_PC(c)_PD|BC(d|b,c)=_PA|B(a|b)_PB(b)_PC(c)_PD|BC(d|b,c)=(c)_PA|B(a|b)_PBC(b,c)_PD|BC(d|b,c)=_PA|B(a|b)_PBCD(b,c,d)

for all (a,b,c,d)∈A×B×C×D (a,b,c,d)∈A×B×C×D , where (a) (a) follows from A−BC−D A−BC−D and (b) b) and (c) c) follow as C is independent of AB AB. Thus, we have Implication (A13).

☐

References

1. Schaefer, R.F.; Boche, H.; Khisti, A.; Poor, H.V. Information Theoretic Security and Privacy of Information Systems; Cambridge University Press: Cambridge, UK, 2017.

2. Shannon, C.E. Communication theory of secrecy systems. Bell Syst. Tech. J. 1949, 28, 656–715.

3. Csiszár, I.; Körner, J. Information Theory: Coding Theorems for Discrete Memoryless Systems; Cambridge University Press: Cambridge, UK, 2011.

4. Wyner, A.D. The wire-tap channel. Bell Syst. Tech. J. 1975, 54, 1355–1387.

5. Bloch, M.; Barros, J. Physical-Layer Security: From Information Theory to Security Engineering; Cambridge University Press: Cambridge, UK, 2011.

6. Ahlswede, R.; Csiszár, I. Common randomness in information theory and cryptography. Part I: Secret sharing. IEEE Trans. Inf. Theory 1993, 39, 1121–1132.

7. Ignatenko, T.; Willems, F.M. Biometric security from an information theoretical perspective. Found. Trends Commun. Inf. Theory 2012, 7, 135–316.

8. Grigorescu, A.; Boche, H.; Schaefer, R.F. Robust PUF based authentication. In Proceedings of the IEEE International Workshop on Information Forensics and Security (WIFS), Rome, Italy, 16–19 November 2015; pp. 1–6.

9. Lai, L.; Ho, S.-W.; Poor, H.V. Privacy-security tradeoffs in biometric security systems. In Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing, Urbana-Champaign, IL, USA, 23–26 September 2008; pp. 268–273.

10. Boche, H.; Wyrembelski, R.F. Secret key generation using compound sources-optimal key-rates and communication costs. In Proceedings of the 2013 9th International ITG Conference on Systems, Communication and Coding (SCC), München, Germany, 21–24 January 2013.

11. Grigorescu, A.; Boche, H.; Schaefer, R.F. Robust Biometric Authentication from an Information Theoretic Perspective. Entropy 2017, 19, 480.

12. Baur, S.; Boche, H. Robust authentication and data storage with perfect secrecy. In Proceedings of the 2017 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Atlanta, GA, USA, 1–4 May 2017; pp. 553–558.

13. Baur, S.; Boche, H. Robust Secure Storage of Data Sources with Perfect Secrecy. In Proceedings of the IEEE Workshop on Information Forensics and Security, Rennes, France, 4–7 December 2017.

14. Baur, S.; Boche, H. Storage of general data sources on a public database with security and privacy constraints. In Proceedings of the 2017 IEEE Conference on Communications and Network Security (CNS), Las Vegas, NV, USA, 9–11 October 2017; pp. 555–559.

15. Willems, F.; Ignatenko, T. Authentication based on secret-key generation. In Proceedings of the 2012 IEEE International Symposium on Information Theory Proceedings (ISIT), Cambridge, MA, USA, 1–6 July 2012; pp. 1792–1796.

16. Gallager, R. Information Theory and Reliable Communication; Springer: Berlin, Germany, 1968.

17. Wolfowitz, J. Coding Theorems of Information Theory; Springer: Berlin, Germany, 1978.

18. Blackwell, D.; Breiman, L.; Thomasian, A.J. The capacity of a class of channels. Ann. Math. Stat. 1959, 30, 1229–1241.

19. Tavangaran, N.; Baur, S.; Grigorescu, A.; Boche, H. Compound biometric authentication systems with strong secrecy. In Proceedings of the 2017 11th International ITG Conference on Systems, Communication and Coding (SCC), Hamburg, Germany, 6–9 February 2017.

20. Han, T.S. Information-Spectrum Methods in Information Theory; Springer Science & Business Media: New York, NY, USA, 2013; Volume 50.

21. Boche, H.; Cai, N. Common Random Secret Key Generation on Arbitrarily Varying Source. In Proceedings of the 23rd International Symposium on Mathematical Theory of Networks and Systems (MTNS2018), Hong Kong, China, 16–20 July 2018. in press.

22. Schaefer, R.F.; Boche, H.; Poor, H.V. Secure Communication Under Channel Uncertainty and Adversarial Attacks. Proc. IEEE 2015, 103, 1796–1813.

23. Wiese, M.; Nötzel, J.; Boche, H. A Channel Under Simultaneous Jamming and Eavesdropping Attack—Correlated Random Coding Capacities Under Strong Secrecy Criteria. IEEE Trans. Inf. Theory 2016, 62, 3844–3862.

24. Nötzel, J.; Wiese, M.; Boche, H. The Arbitrarily Varying Wiretap Channel—Secret Randomness, Stability, and Super-Activation. IEEE Trans. Inf. Theory 2016, 62, 3504–3531.