Multi-Entity and Multi-Enrollment Key Agreement with Correlated Noise

A natural source of randomness is biometric identifiers such as fingerprints that are generally transformed into a frequency domain and quantized to obtain bit sequences that are unique to an individual [1]. Similarly, physical identifiers such as fine variations of ring oscillator (RO) outputs or random start-up values of static random access memories (SRAMs) that are caused by uncontrollable manufacturing variations, are safer and cheaper alternatives to key storage in a non-volatile memory [2]. Physical identifiers for digital devices such as Internet-of-Things (IoT) devices can be implemented using physical unclonable functions (PUFs) [2]. One can use PUFs in various coding schemes as a source of local randomness [3, Chapter 1], e.g., in the randomized encoder of the wiretap channel [4] and of the strong coordination problem [5, 6].

We use the basic source model for key agreement from [7, 8] to find achievable rate regions for key agreement with PUFs and biometric identifiers. In this classic model, an encoder observes a source output to generate a secret key and sends public side information, i.e., helper data, to a decoder, so the decoder can reliably reconstruct the same secret key by observing another source output and the helper data. The main constraints are that the information leaked about the secret key, i.e., secrecy leakage, is negligible and the information leaked about the identifier output, i.e., privacy leakage, is small [9, 10]. Furthermore, the amount of public storage should also be minimized to limit the hardware cost [11].

Suppose the encoder generates a key from a noisy measurement of a hidden (or remote) source output, and a decoder has access to another noisy measurement of the same source and the helper data to reconstruct the same key. We call this model the generated-secret (GS) model with a hidden source. This model is introduced in [12] as an extension of the visible (noiseless) source outputs observed by the encoder, considered in [9, 10]. Similarly, for the chosen-secret (CS) model, an embedded (or chosen) key and noisy identifier measurements are combined by the encoder to generate the public helper data. We consider both models to address different applications.

Consider hidden identifier outputs $X^{n}$ that are i.i.d. according to a probability distribution $P_{X}$. The hidden (or remote) source with outputs $X^{n}$ is common to all honest entities that enroll the same identifier, but they observe different noisy measurements of the same hidden source. If there are a finite number $J$ of honest entities that use the same identifer, the $j$-th encoder and decoder pair observes noisy source measurements that are outputs of a BC $P_{\widetilde{X}_{j}Y_{j}|X}$, with abuse of notation, for all $j\in[1:J]$, where $\mathcal{\widetilde{X}}_{j}$, $\mathcal{Y}_{j}$, and $\mathcal{X}$ are finite sets.

For the GS model illustrated in Fig. 1$(a)$ for $J=2$ honest entities, the $j$-th encoder $f_{\text{GS},j}(\cdot)$ generates helper data $W_{j}$ and a secret key $S_{j}$ from its observed sequence $\widetilde{X}^{n}_{j}$. All secret keys are stored in a secure database, whereas helper data are stored in a public database so that an eavesdropper has access only to the helper data. Using the helper data $W_{j}$ and its observed sequence $Y^{n}_{j}$, the $j$-th decoder $g_{j}(\cdot,\cdot)$ generates the key estimate $\hat{S}_{j}$. Similar steps are applied for the CS model in Fig. 1$(b)$ also for $J=2$ honest entities, except that each $S_{j}$ should be embedded into the $j$-th encoder $f_{\text{CS},j}(\cdot,\cdot)$.

Denote a set of secret keys as

and a set of helper data as

for any $\mathcal{K}\subseteq[1:J]$. A (secret-key, privacy-leakage, storage), or key-leakage-storage, rate tuple is denoted as $(R_{\text{s}},R_{\ell},R_{\text{w}})$. Similarly, we denote a set of secret-key rates, for any $\mathcal{K}\subseteq[1:J]$, as

and a set of storage rates as

We next define the multi-entity key-leakage-storage regions.

Both secret-key uniformity (6) and storage rate (10) constraints correspond to $J$ separate constraints. However, reliability (5), strong and mutual key independence (7), privacy-leakage rate (8), and secrecy leakage (9) constraints are joint constraints for all $J$ honest entities. Suppose after a key generation, an honest entity has access only to its corresponding secret key and it does not have access to other entities’ keys or sequences or even to the sequence it observed to generate its secret key.

The mutual key independence constraint in (7) is not imposed in the multi-enrollment key agreement problem considered in [16]. Furthermore, a normalized (weak) version of this constraint is imposed in the multi-enrollment key agreement problem considered in [14], where the $j$-th decoder $g_{j}(\cdot,\cdot)$ is assumed to have access to the set of helper data $\mathcal{W}_{[1:j]}$ for all $j\in[1:J]$. The lack of the mutual key independence constraint and the assumption of availability of all previous helper data require that different encoder and decoder pairs should trust each other after key agreement. This can be the case, e.g., if all enrollments are made by the same entity. Therefore, the multi-entity key agreement problem imposes strictly more stringent constraints than the multi-enrollment key agreement problem.

The unnormalized secrecy leakage constraint (9) provides strong secrecy, which is a stronger notion than the weak secrecy considered in [9, 10, 12, 28, 16, 14]. Furthermore, (9) is more stringent than the set of individual secrecy leakage constraints $I(S_{j};\mathcal{W}_{[1:J]})$ imposed for all $j\in[1:J]$, considered in [16] for symmetric SRAM PUF outputs in combination with the suboptimal FCS.

The unnormalized privacy leakage $I(X^{n};\mathcal{W}_{[1:J]})$ cannot be bounded by a finite number in general. We illustrate special strong privacy cases in the next section.

We are interested in characterizing the optimal trade-off among the secret-key, privacy-leakage, and storage rates with strong secrecy for BC measurements at the encoders and decoders of any finite number $J$ of entities that use the same hidden identifier outputs for the multi-entity key agreement problem. We give achievable rate regions for the GS and CS models in Theorem 1. The proofs are given in Section V.

Denote

and define a function $\max\{\cdot,\cdot\}$ that gives the maximum of the input values as its output.

The proof of Corollary 1 follows from Theorem 1 because $I(U_{j};X)-I(U_{j};Y_{j})\leq 0$ for all $j\in[1:J]$ for BCs considered in Corollary 1.

Corollary 1 illustrates that it is possible to obtain strong privacy, i.e., negligible unnormalized privacy leakage, without the requirement of a common randommness that is hidden from an eavesdropper assumed in [9, 10, 24]. This is the case because the observation $Y^{n}_{j}$ of each decoder is “better” than the observation $\widetilde{X}^{n}_{j}$ of the corresponding encoder with respect to the hidden source $X^{n}$ for all entities.

We next give simple outer bounds for the multi-entity key-leakage-storage regions $\mathcal{C}_{\text{gs}}$ for the GS model and $\mathcal{C}_{\text{cs}}$ for the CS model when the BCs $P_{XY_{j}|\widetilde{X}_{j}}$ for all $j\in[1:J]$ are PD BCs or LN BCs, as defined in Corollary 1. These simple outer bounds give insights into the reason for different bounds on the secret-key rates. Based on these insights, we show a special multi-enrollment case in the next section with a less stringent secrecy constraint, for which the inner and outer bounds differ only in the Markov chains imposed and we illustrate that they match for simpler models.

The proof of Lemma 1 follows straightforwadly by following the steps in [12, Section VI], defining the auxiliary random variables $U_{j,i}=(S_{j},W_{j},Y_{j}^{i-1})$ for all $j\in[1:J]$ and $i\in[1:n]$, and by bounding $I(X^{n};\mathcal{W}_{[1:J]})\geq 0$; therefore, we omit the proof.

The outer bounds do not include the inequalities in (15) and (17). Furthermore, the secret-key rate achieved by the inner bound in (12) is smaller than the outer bound given in (20), where the difference is the term $-I(U_{j};\mathcal{U}_{[1:J]\setminus\{j\}})$. This term is a result of the constraint in (44) that is imposed to satisfy the strong and mutual key independence constraint given in (7). Therefore, we next consider a model without the constraint in (7) and use a secrecy-leakage constraint that is less stringent than the one in (9), i.e., replace (9) by

which is also a strong secrecy metric. Due to the lack of a mutual key independence constraint, the model in the next section is not a multi-entity model but rather a multi-enrollment model. For a special case of this multi-enrollment key agreement problem, we establish inner and outer bounds for the key-leakage-storage regions that comprise the same bounds but for different Markov chains.

Consider next the multi-enrollment model, where the strong and mutual key independence constraint (7) of the multi-entity model is not imposed. Assume further $J=2$ entities that measure noisy outputs of the same hidden source $X^{n}$ through separate channels that have the same channel transition matrices, i.e., for all $j\in[1:2]$, $\tilde{x}_{j}\in\mathcal{\widetilde{X}}$, and $y_{j}\in\mathcal{\widetilde{X}}$ we have

This model is common for SRAM PUFs, for which each measurement channel is modeled as a BSC with the same crossover probability corresponding to a worst case scenario[30]. Using (23), we define a multi-enrollment model.

We characterize in Theorem 2 inner and outer bounds for $\mathcal{\widebar{C}}_{\text{gs},J=2}$ and $\mathcal{\widebar{C}}_{\text{cs},J=2}$. The proofs of Theorem 2 are given in Section VI, where the reason for the necessity of the secrecy-leakage constraint in (27) that is less stringent than the joint secrecy-leakage constraint in (9) is given in Remark 2. Similarly, the reason for the necessity of the strong helper data (storage) independence constraint in (29) is discussed in Remark 4. We remark that the equalities in (25), (26), and (28) are required in the outer bounds in Theorem 2 to provide both upper and lower bounds on $\widebar{R}_{\ell}$ and $\widebar{R}_{\text{w},j}$ in terms of Shannon entropy terms.

Denote

The inner and outer bounds differ because the outer bounds define rate regions for the Markov chains $U_{1}-\widetilde{X}_{1}-X-Y_{1}$ and $U_{2}-\widetilde{X}_{2}-X-Y_{2}$, which are larger than the rate regions defined by the inner bounds that satisfy (40). For instance, in the achievability proof of Theorem 2, we apply the properties of the Markov chain $U_{2}-\widetilde{X}_{2}-U_{1}$ in (86)(b), which does not form a Markov chain for the choice of $U_{1}$ and $U_{2}$ in the outer bounds. Therefore, inner and outer bounds do not match in general.

We provide a proof that follows from the output statistics of random binning (OSRB) method, proposed in [32] and further extended in [33], by applying the steps in [34, Section 1.6].