# A Lightweight and Practical Anonymous Authentication Protocol Based on Bit-Self-Test PUF
## 3 Proposed Scheme
### Proposed Authentication Protocol  
In this paper, an authentication protocol is designed based on BST-PUF [27], and the security authentication can be performed between a cryptographic device with a PUF entity and the server. There is no need to use FE or any ECCs on the device during protocol execution, while pseudorandom functions are used instead of symmetric encryption algorithms, which further reduces the execution overhead of the device. In later sections, we will provide the formal security analysis of it. In order to describe the proposed protocol, the following formal definition is given. * \(\mathbf{y}\xleftarrow{\underline{u}}\mathbf{A}\): \(\mathbf{A}\): \(\mathbf{A}\) is a set, and \(\mathbf{y}\) is a randomly selected element from \(\mathbf{A}\);
* \(\mathbf{y}=\mathbf{A}(\mathbf{x})\): \(\mathbf{A}\) is a probabilistic algorithm and \(\mathbf{y}\) is the output produced by inputting \(\mathbf{x}\) to algorithm \(\mathbf{A}\);
* \(\mathbf{TRNG}\): Truly random number generator, which can derive a truly random number sequence;
* \(\mathbf{PRF}\), \(\mathbf{PRF^{\prime}}\): Pseudorandom function \(\mathbf{K^{\prime}}\times\mathbf{D^{\prime}}\rightarrow\mathbf{R}\) uses the secret key \(\mathbf{k}\in\mathbf{K^{\prime}}\) and the message \(\mathbf{m}\in\mathbf{D^{\prime}}\) as input, an output \(\mathbf{pr}\in\mathbf{R^{\prime}}\);
* \(\mathbf{KEY.Ext}\): \(\mathbf{P^{\prime}}\rightarrow\mathbf{K^{\prime}}\times\mathbf{L^{\prime}}\), uses \(\mathbf{PUF}\) challenge \(\mathbf{c^{\prime}}\in\mathbf{P^{\prime}}\) as input, generates a key \(\mathbf{k}\in\mathbf{K^{\prime}}\) and helper data \(\mathbf{h}\in\mathbf{L^{\prime}}\). The \(\mathbf{KEY.Ext}\) contains a \(\mathbf{BST}\)-\(\mathbf{APUF}\) circuit, which is described in Section 3.1;
* \(\mathbf{KEY.Rec}\): \(\mathbf{P^{\prime}}\times\mathbf{L^{\prime}}\rightarrow\mathbf{K^{\prime}}\), takes as input the PUF noisy response \(\mathbf{r^{\prime}}\in\mathbf{P^{\prime}}\) and helper data \(\mathbf{h}\in\mathbf{L^{\prime}}\) and recovers the key \(\mathbf{k}\in\mathbf{K^{\prime}}\). The protocol execution process includes the setup phase and authentication phase. The setup phase is executed in a secure environment. The device is required to register with  
Figure 4: The HDA based on BST-PUF. the server, for which it generates a random challenge \(c_{1}\) and a temporary \(ID\) and sends it to the device. The device produces the key and helper data \((k_{1},h_{1}):=KEY.Ext(c_{1})\) in the device using \(KEY.Ext\) and sends them to the server to set the initial shared key \(k_{1}=k_{old}\) and initial temporary ID \(ID_{1}=ID_{old}\). When the server and the device want to perform mutual authentication and message transmission, then the authentication phase begins. The specific execution process of mutual authentication is shown in Figure 5.  
In the authentication phase, the server generates and sends a random number \(\{m_{1}\}\) to the device. The device receives \(\{m_{1}\}\) and generates another random number \(\{m_{2}\}\), and  
Figure 5: The proposed protocol. then reads the stored challenge \(c_{1}\) and helper data \(h_{1}\) from NVM and inputs them into the \(KEY.Rec\) to generate the key \(k_{1}\). Using \(k_{1}\), \(m_{1}\parallel m_{2}\) as input, the PRF generates five pseudorandom numbers \(s_{1},\ldots,s_{5}\) for subsequent authentication and encryption operation. At the same time, the \(TRNG\) on the device generates a random challenge \(c_{2}\), which is inputted into the \(KEY.Exc\) to generate key \(k_{1}\) and helper data \(h_{2}\). Performing the XOR operation on \(k_{2}\) and \(s_{2}\) can generate the encrypted data \(u\). Using \(s_{3}\), \(m_{2}\parallel u\) as the input, the \(PRF^{\prime}\) can generate a pseudorandom number \(v\). Then, the message \(\{s_{1},m_{2},u,v,ID_{1}\}\) will be sent to the server for authentication. Among them, the data \(v\) are used as the Message Authentication Code (MAC).