## 3 Proposed Structure
### PUF Database Bloom Filter (PDBF)  
The role of the PDBF is to store all the challenge information and challenge length held on the authentication server to improve the security of the pm-PUF. The PDBF is the structure referred to in [52; 56; 57] in which one cell stores two bits, and the false negative of the CBF is removed. Additionally, the cell positions are shifted from the hash indices by the challenge length. Figure 2 shows the PDBF programming procedure. As an example of the programming procedure, let \(S_{crp}=\{C_{1},C_{2},C_{3}\}\) represent a challenge in the authentication server. Assume that the challenge length is four bits and the number of hash indices \(k\) is three. Program it in the cell positions shifted by four bits of challenge length from the hash indices. The hash indices of \(C_{1}\) are 0, 5, and 13, and the challenge length is 4, so \(C_{1}\) is programmed in the cell positions 4, 9, and 1 shifted by 4 as in Figure 1(a). If two challenges are mapped to cells 4 and 11 as in Figure 1(b), the cells are represented by 2. If more than two challenges are mapped as shown for cell 9 in Figure 1(b), the corresponding cell is represented by X.  
The purpose of querying the PDBF is to determine whether the input challenge exists in the authentication server. Figure 3 shows the PDBF querying procedure. If all of the cells contain 1, 2, or X, the result of PDBF is termed a positive. If any one of the cells contains 0, the result of PDBF is termed a negative. For example, in Figure 2(a), the challenge \(C_{3}\) of input is queried. The hash indices of \(C_{3}\) are 5, 7, and 9, and the challenge length of \(C_{3}\) is 4, so \(C_{3}\) is queried to the cell positions 9, 11, and 13 shifted by 4. Since the values of the corresponding cells are X, 2, and 1, it is termed positive and challenge \(C_{3}\) is transmitted to the pm-PUF. The PDBF querying for an attack challenge \(A\) is shown in Figure 2(b). Assuming the hash indices of \(A\) are 1, 6, and 9, and the challenge length of \(A\) is 3. \(A\) is queried to the cell positions 4, 9, and 12 shifted by 3. The value in cell 12 of the PDBF is 0, so the result is termed a negative. When the PDBF produces a negative result, the input challenge is dropped and is not transmitted to the pm-PUF.  
Figure 2: Programming procedure for a PDBF.  
Another role of the PDBF is to avoid the reuse of CRPs. The PDBF deletes a used challenge and produces a negative result when the same challenge is presented again. The deletion procedure for the PDBF is performed after the response is transmitted to the authentication server as a positive result of CRPBF in Section 3.2 and the transmitted response is successfully authenticated. If the cell values are 1 and 2, they are reduced to 0 and 1, respectively. If the cell contains X, it is not deleted. For example, assume that CRPBF produces a positive result for challenge \(C_{3}\) and transmitted response succeeds in authentication. The hash indices of \(C_{3}\) are 5, 7, and 9, and the cell positions shifted by the challenge length are 9, 11, and 13. Since the values of cells 11 and 13 are 2 and 1, respectively, they are changed to 1 and 0. However, since the value of the cell 9 is X, it is not deleted. The PDBF procedure is shown in Algorithm 1.