## 3 Proposed Structure
### Challenge-Response Pair Bloom Filter (CRPBF)  
The role of the CRPBF is to verify if the output response from the pm-PUF exists in the authentication server; the CRPBF is a Bloom filter that stores the CRPs contained in an authentication server. The hash index programmed into the CRPBF is obtained by concatenating the challenges and responses in the CRP table of authentication server. Figure 4 shows a CRPBF programming example. If a challenge \(C_{1}\) is 1100 and its response \(R_{1}\) is 110 in the authentication server, their concatenation is 1,100,110. The hash indices of 1,100,110 are 3, 6, and 8, and the corresponding cells of the CRPBF are set to 1.  
Figure 4: Programming procedure for a CRPBF.  
Figure 3: Querying procedure for a PDBF.  
```
FunctionProgramming_PDBF(\(challenge\), \(length_{challenge}\)) for\(i=1\)to kdo if\(\text{BF}[h_{i}(challenge)+length_{challenge}]==0\mid\mid\text{BF}[h_{i}(challenge)+length_{challenge}]==1\)then \(\text{BF}[h_{i}(challenge)+length_{challenge}]=\text{BF}[h_{i}(challenge)+ length_{challenge}]+1\);  end if elseif\(\text{BF}[h_{i}(challenge)+length_{challenge}]==2\)then \(\text{BF}[h_{i}(challenge)+length_{challenge}]=\text{X}\);  end if elseif\(\text{BF}[h_{i}(challenge)+length_{challenge}]==\text{X}\)then  continue;  end if  end if  end for FunctionQuerying_PDBF(\(challenge\), \(length_{challenge}\)) for\(i=1\)to kdo if\(\text{BF}[h_{i}(challenge)+length_{challenge}]==0\)then return negative;  end if  end for return positive;  end for FunctionDeleting_PDBF(\(challenge\), \(length_{challenge}\)) for\(i=1\)to kdo if\(\text{BF}[h_{i}(challenge)+length_{challenge}]==1\mid\mid\text{BF}[h_{i}(challenge)+length_{challenge}]==2\)then \(\text{BF}[h_{i}(challenge)+length_{challenge}]=\text{BF}[h_{i}(challenge)+length_{challenge}]-1\);  end if else  continue;  end if  end for
```  
**Algorithm 1**PDBF procedure  
Figure 5 shows a CRPBF query example. In querying the CRPBF, the hash indices are a concatenation of the input challenge and the output response from the pm-PUF. In Figure 4(a), it is assumed that the output response \(R\) (110) obtained by the pm-PUF from the challenge \(C_{1}\) (1100) of input produces a positive result from the PDBF. The hash indices of 1,100,110, the concatenation of challenge \(C_{1}\) (1100), and response \(R\) (110) are 3, 6, and 10. In Figure 4(a), since the corresponding cells of the CRPBF all contain 1, the CRPBF produces a positive result, and the output response \(R\) from pm-PUF is transmitted to the authentication server for comparison with the CRP table. If any one of the cells contains 0, the CRPBF produces a negative result and the output response is dropped because the output response from the pm-PUF does not exist in the authentication server. In another query example shown in Figure 4(b), it is assumed that the output response \(R_{a}\) from an challenge \(A\) of attacker results in a false positive from the PDBF. The hash indices of \(CRP_{a}\) are 1, 5, and 9. The values in the cells are 0, so the result is negative, and the output response is dropped and is not transmitted to the authentication server. The CRPBF procedure is shown in Algorithm 2.