# Multiple Observations for Secret-Key Binding with SRAM PUFs
## 4 Multiple-Observations Helper Data Scheme
### Achievable Secret-Key Rate  
Third, we derive the achievable rate over the channel from the encoder to the decoder. The channel is described by the conditional distribution \(\Pr(M_{t}=m_{t},Y=y|C=c)\), and  
Figure 5: MO helper data scheme: \(t\) observations of the SRAM-PUF are used to generate a helper data \(m_{t}^{n}\) that is published and that can be used by the decoder (together with an additional SRAM-PUF observation) to reconstruct the key.  
it follows from the channel coding theorem (see, e.g., [20], Chapter 3) that the maximum achievable rate is given by the mutual information maximized over the input distribution. Furthermore, \(C\) is uniform here, since we are using a linear code. We therefore evaluate this mutual information next  
\[\begin{array}{rcl}R_{\text{MO},t}^{*}&\stackrel{{\Delta}}{{=}}&I (C;M_{t},Y)=I(C;M_{t})+I(C;Y|M_{t})\\ &\stackrel{{(a)}}{{=}}&H(Y|M_{t})-H(Y|M_{t},C)\\ &\stackrel{{(b)}}{{=}}&H(Y|M_{t})-H(Y|w_{H}(X_{1},X_{2},\ldots,X_ {t}),C)\\ &\stackrel{{(c)}}{{=}}&1-H(Y|w_{H}(X_{1},X_{2},\ldots,X_{t}))\\ &\stackrel{{(d)}}{{=}}&H(Y)-H(Y|X_{1},X_{2},\ldots,X_{t})\\ &=&I(Y;X_{1},X_{2},\ldots,X_{t}).\end{array} \tag{21}\]  
Please note that \((a)\) follows from zero leakage (see (24)), and \((b)\) holds since (by (18)) the Hamming weight \(w_{H}(x_{1},x_{2},\ldots,x_{t})\) is uniquely determined by \(m_{t}\) given \(c\) and vice-versa. Furthermore, \((c)\) follows from (22) below and since the key and thus codebit \(c\) are generated independently from the SRAM-PUF observations. Finally, \((d)\) follows from the fact that the symmetric SRAM-PUF is unbiased (5), and by the fact that the conditional probability of the next observation given \(t\) previous observations \((x_{1},x_{2},\ldots,x_{t})\) only depends on the number of observed ones (7). The following derivation shows that the helper data integer \(m_{t}\) by itself does not reveal any information about the reconstruction observation \(y\), and thus \(H(Y|M_{t})=1\).  
\[\begin{array}{rcl}\Pr(Y=1|M_{t}=m_{t})&\stackrel{{(a)}}{{=}}& \sum_{c\in\{0,1\}}\Pr(C=c)\Pr(Y=1|M_{t}=m_{t},C=c)\\ &\stackrel{{(b)}}{{=}}&\frac{1}{2}\Pr(Y=1|w_{H}(X_{1},\ldots,X_ {t})=m_{t},C=0)\\ &+\frac{1}{2}\Pr(Y=1|w_{H}(X_{1},\ldots,X_{t})=t-m_{t},C=1)\\ &\stackrel{{(c)}}{{=}}&\frac{1}{2}\Pr(Y=1|w_{H}(X_{1},\ldots,X_ {t})=m_{t})\\ &+\frac{1}{2}\Pr(Y=0|w_{H}(X_{1},\ldots,X_{t})=m_{t})=\frac{1}{2},\end{array} \tag{22}\]  
where \((a)\) follows from (23), \((b)\) follows from the definition of the helper data (18), and in \((c)\) we use the fact that the key and codebit \(c\) is generated independently from the SRAM-PUF observations, and furthermore we use the symmetry property for the conditional distribution (8) that we have derived for symmetric SRAM-PUF in Section 2. In the above derivation we use that  
\[\Pr(C=c|M_{t}=m_{t})=\Pr(C=c), \tag{23}\]  
which can be derived from (19) by observing that  
\[I(C;M_{t})\stackrel{{(a)}}{{\leq}}I(S;M_{t}^{n})=0, \tag{24}\]  
where \((a)\) follows from the data processing inequality (see [19], Chapter 2) for the Markov Chain  
\[C\leftrightarrow C^{n}\leftrightarrow S\leftrightarrow M_{t}^{n}\leftrightarrow M _{t}. \tag{25}\]  
It follows from the derivations in Sections 4.2 and 4.3 that the MO helper data scheme achieves secret-key rate \(R_{\text{MO},t}^{*}\), where achievable secret-key rate is defined in Definition 1. Furthermore, \(R_{\text{MO},t}^{*}=C_{t}\) is equal to the secret-key capacity for \(t\) enrollment observations as given by Theorem 1, which shows that the MO helper data scheme is optimal.