# Multiple Observations for Secret-Key Binding with SRAM PUFs
## 3 Multiple Enrollment Observations for Increased Secret-Key Capacity  
In this section, we describe a secret-key binding scheme with multiple enrollment observations, see Figure 3. We derive the achievable secret-key rate for the used statistical model and show that the rate can improve significantly when more enrollment observations are considered. These results motivate us to design a helper data scheme that can approach such rates in Section 4. As in the classic (single enrollment) key binding scheme in Figure 1, we distinguish between an enrollment and a reconstruction phase. During enrollment, the secret key \(s\in\{1,2,\ldots,|\mathcal{S}|\}\) is generated uniformly at random. An encoder obtains the secret key \(s\) and \(t\) observation vectors \(\left(x_{1}^{n},x_{2}^{n},\ldots,x_{t}^{n}\right)\), and generates corresponding helper data \(w\in\mathcal{W}\). The helper data alphabet \(\mathcal{W}\) is specified by the encoding function that is used, see Section 4. We assume that the helper data \(w\) is stored and/or communicated in the public domain. Therefore, the helper data by itself should not reveal any information about the key. During reconstruction, a decoder observes a reconstruction vector \(y^{n}\) as well as the helper data \(w\) and maps this input to an estimate \(\delta\) of the secret key. Reconstruction is successful when the estimate is equal to the original key, i.e., when \(\delta=s\). We are now interested in the achievable secret-key rate of the scheme when enrollment is performed using \(t\) observation vectors of the SRAM-PUF, and where achievable rate is defined as follows. **Definition 1**. : _A secret-key rate \(R_{t}\) is called achievable after \(t\) enrollment observations, if for all \(\delta>0\) and for all \(n\) large enough, there exist encoders and decoders such that_  
\[\Pr\big{(}\hat{S}\
eq S\big{)} \leq\delta, \tag{11}\] \[\frac{1}{n}H(S) =\frac{1}{n}\log_{2}|\mathcal{S}| \geq R_{t}-\delta,\] (12) \[\frac{1}{n}I(S;W) \leq\delta. \tag{13}\]  
_The secret-key capacity \(C_{t}\) is the maximum achievable secret-key rate with \(t\) enrollment observations._  
Here (11) requires that the key reconstruction is reliable, (12) that the key is uniformly distributed, and (13) limits the information leakage by the helper data about the key. Theorem 1 gives the fundamental limit on achievable secret-key rate for key binding schemes with \(t\) enrollment observations, and it follows from the results presented in [24; 25]. Figure 3: Secret-key binding with \(t\) observations by the encoder and a single observation by the decoder. **Theorem 1**. : _A secret-key rate \(R_{t}\) is achievable after \(t\) enrollment observations if and only if_  
\[R_{t}\leq I(Y;X_{1},X_{2},\ldots,X_{t}). \tag{14}\]  
_The secret-key capacity \(C_{t}=I(Y;X_{1},X_{2},\ldots,X_{t})\)._  
In Figure 4, we plot the secret-key capacity for an example SRAM-PUF. Here, we have assumed a symmetric distribution of the one-probabilities, and average error probability \(\overline{\psi}\approx 0.15\), see Figure 2 for the \(\Theta\)-distribution. The mutual information increases from 0.26 for a single enrollment observation, to 0.50 after 20 enrollment observations. This corresponds to almost doubling the secret-key rate regarding single enrollment. In the plot, we also visualize an upper bound to the secret-key capacity, given by  
\[I(Y;X_{1},X_{2},\ldots,X_{t})\leq I(Y;X_{1},X_{2},\ldots,X_{t}, \Theta)=I(Y;\Theta)+I(Y;X_{1},X_{2},\ldots,X_{t}|\Theta)\] \[\stackrel{{(a)}}{{=}}I(Y;\Theta)=H(Y)-\int_{0}^{1}H( Y|\Theta=\theta)p_{\Theta}(\theta)\,d\theta, \tag{15}\]  
where \((a)\) follows from the Markov chain \(Y\leftrightarrow\Theta\leftrightarrow(X_{1},X_{2},\ldots,X_{t})\). From the weak law of large numbers, i.e., \(\lim_{t\rightarrow\infty}\Pr\left(\left|\frac{1}{t}\sum_{i=1}^{t}x_{i}-E[X_{i }]\right|>\epsilon\right)=0\) for any \(\epsilon>0\), it follows that \(\frac{1}{t}\sum_{i=1}^{t}x_{i}\) converges (in probability) to \(\theta\) for \(t\rightarrow\infty\).