A Novel Key Generation Method for Group-Based Physically Unclonable Function Designs

Abstract

In recent years, physically unclonable functions (PUFs) have gained significant attraction in IoT security applications, such as cryptographic key generation and entity authentication. PUFs extract the uncontrollable production characteristics of different devices to generate unique fingerprints for security applications. When generating PUF-based secret keys, the reliability and entropy of the keys are vital factors. This study proposes a novel method for generating PUF-based keys from a set of measurements. Firstly, it formulates the group-based key generation problem as an optimization problem and solves it using integer linear programming (ILP), which guarantees finding the optimum solution. Then, a novel scheme for the extraction of keys from groups is proposed, which we call positioning syndrome coding (PSC). The use of ILP as well as the introduction of PSC facilitates the generation of high-entropy keys with low error correction costs. These new methods have been tested by applying them on the output of a capacitor network PUF. The results confirm the application of ILP and PSC in generating high-quality keys.

1. Introduction

The internet of things (IoT) has already changed our way of living and the way we interact with a range of devices, such as cars, home appliances, and wearables [1]. We become more dependent on IoT devices every day. Connected devices that are available everywhere means that a security issue can lead to irrecoverable consequences. One important security aspect of IoT devices is the security of data, such as microprocessor program data, sensor data, or communication data [2]. Keeping in mind that IoT devices usually need to be lightweight and low cost, there is a need for simple, cheap, and strong security mechanisms to help with the provisioning of data security. Physically unclonable functions (PUF) have proven to be a potentially robust solution for such IoT security needs [3]. They leverage the inherent features of hardware to generate unique fingerprints for security applications.

Many studies have been conducted to improve the reliability, uniqueness, and entropy of PUFs. In this way, different materials and devices have been evaluated as PUF candidates. Most PUFs proposed in the literature are silicon-based, including arbiter [4,5], ring oscillator (RO) [6], static RAM (SRAM) and butterfly [7], latch [8], and flip-flop [9] PUFs. Moreover, some designs based on other materials and technologies have also been presented, such as printed electronics (PE) [10], touchscreens [11], solar cells [12], photodiodes [13], and the electric signals of personal computers [14].

This work aims to maximize the length of cryptographic keys derived from PUF responses while keeping the cost of error correction low. More specifically, we propose an optimum key generation method for the cases where the raw output of the PUF is a set of analog measurements. The so-called grouping algorithm has been proposed in the literature as a means of deriving longer keys from a set of PUF measurements. However, no evidence is provided to show that the grouping algorithm finds the optimum solution to maximize the length of the generated key. In this study, the problem of maximizing PUF key length is formulated as an integer linear programming (ILP) optimization problem. It will be shown that ILP is able to find the optimum solution for the problem and maximize the key length. Moreover, a new syndrome coding method is proposed to improve the entropy of the generated key while lowering the number of error bits.

This paper is organized as follows. Section 2 covers the background and the state of the current literature. Section 3 explains the proposed solution for group-based key generation as well as positioning syndrome coding. Finally, in Section 4, the results of applying the proposed methods on real PUF datasets are presented.

2. Background and Previous Works

PUF studies fall into several categories. Some of them examine different materials and propose novel PUF designs. Several works look for new applications for PUFs. There are also studies which try to evaluate PUF security levels by performing attacks, while some researchers propose methods to make PUFs more resilient against such attacks. In this work, the focus is on the studies that propose methods to derive secure keys from PUF measurements, especially group-based key generation methods.

2.1. PUF Key Generation

In the PUF context, when using a device for secret key generation, higher entropy is desirable, which means extracting as many reliable bits from the PUF as possible. Changing environmental conditions, such as temperature and relative humidity, affect the reliability of PUFs. In general, reliable bits are independent of each other, and can be reproduced even under the impact of environmental variations. Moreover, ideally, the aging of the device should not have any effect on the reliability of the bits.

In the literature, several works focus on expanding the length of secret keys while generating reliable keys from PUF measurements under temporal and environmental variations. The authors of [15] proposed a one-out-of-eight masking scheme to generate one bit from eight ring oscillators. To increase the key length, [16] introduced a method to generate up to n-1 bits from n PUF measurements. Authors in [17] proposed the longest increasing sequence-based algorithm (LISA) to enhance secret key generation by grouping PUF measurement results. They have also introduced compact syndrome coding (CSC) to generate keys from the groups that resulted from the LISA. However, the complexity of the proposed grouping algorithm, the presence of bias in the generated keys, and the high number of error bits caused by temporal variations are some drawbacks of their work. Their work later has been improved by simplifying the grouping algorithm and combining it with Kendall syndrome coding (KSC) to generate longer keys with fewer bit errors [18]. However, this study also fails to find the optimum solution for the group-based key generation method. Our proposed key generation method, which is explained later in this paper, targets the limitations of these two works.

2.2. Group-Based Key Generation

The main idea of group-based key generation is to compare multiple PUF measurement values, rather than comparing them pairwise, in order to generate longer secret keys. The idea has been initially proposed in [17] using the LISA. Suppose that there is a group of four PUF measurement values, $g_1=\left\{f_1{,f}_2{,f}_3{,f}_4\right\}$. A simple pairing algorithm can generate two pairs from these four elements, which leads to the generation of two secure bits. However, if all four elements are compared together, $4\text{!}=24$ different orderings are possible. As shown in Figure 1, by assigning a binary code to each ordering according to CSC, five bits can be generated from these four elements. Therefore, group-based key generation is able to improve the entropy of the generated key compared to the pairwise method.

The ideal case for key generation is to put all the PUF measurements in the same group. As an example, putting six PUF measurements in the same group leads to 720 different ordering possibilities, which can be encoded in 10 bits. Conversely, putting these PUF measurements in two groups of three elements generates only six bits. However, PUF measurements do not always give the same results under different environmental conditions. That means that if two PUF measurements in the same group have a very close value, after remeasuring, their order in the group might swap. Hence, a generated key from a set of PUF measurements may not be reproduced. To overcome this issue, only the PUF measurements which do not change their order under different conditions may be put together in the same group. The LISA is proposed to create a partition between PUF measurements with the aim of maximizing the key length. The LISA requires measuring every PUF value at the two extreme environmental conditions. In order to avoid bit errors, the ordering of group elements under these different conditions should give the same result for both measurements.

The definition of the problem for the group-based key generation is as follows:

Take $n$ measured values $G$ and put them in m subgroups to form the partition $P$:

$$P=\left\{\begin{array}{c}{g}_1\\ g_2\\ \begin{array}{c}⋮\\ g_m\end{array}\end{array}\right\}=\left\{\begin{array}{c}\left\{f_{11}{,f}_{12},\dots \right\}\\ \left\{f_{21}{,f}_{22},\dots \right\}\\ \begin{array}{c}⋮\\ \left\{f_{m1}{,f}_{m2},\dots \right\}\end{array}\end{array}\right\}$$

(1)

The following conditions apply when creating the partition:

• $g_i\cap g_j=\varnothing$
• $g_1\cup g_2\cup \dots \cup g_m=G$
• $\mathrm{if}{f}_{j{i}_{min}}<f_{j{k}_{min}},\mathrm{then}{f}_{j{i}_{max}}<f_{j{k}_{max}}$ for all elements in the same subgroup
• $\left|f_{j{i}_{min}}–f_{j{k}_{min}}\right|{\text{>}f}_{\mathrm{th}};\left|f_{j{i}_{max}}–f_{j{k}_{max}}\right|{\text{>}f}_{\mathrm{th}}$ for all elements in the same subgroup

Where $f_{\mathit{ji}}$ and $f_{\mathit{jk}}$ represent the $i$th and $k$th elements of the subgroup $j$, respectively. Moreover, min and max subscripts represent the minimum and maximum values of the corresponding element, respectively. Conditions 1 and 2 guarantee the formation of a partition, which indicates that all $f_r$ values have been used. Conditions 3 and 4 ensure that there is a minimum distance between PUF measurements inside a subgroup so that by changing the environment, no swap occurs by comparing elements of the subgroup. Note that a threshold value, $f_{\mathrm{th}}$, is defined to ensure a minimum distance between PUF measurements in the same group. The above problem should be solved to maximize the following cost function which indicates the number of generated bits:

$$\mathrm{Max}{\displaystyle \sum }_{i=1}^m{\log }_2\left(\left|g_i\right|\text{!}\right)$$

(2)

Authors in [17] proposed using a grouping algorithm to solve the above problem. However, they failed to prove that their algorithm is able to find the optimum solution, i.e., the maximum key length.

In [18], a simpler grouping algorithm has been proposed, which requires only one measurement. To achieve this, the authors also defined a threshold value, which should be the minimum distance between each pair of elements in a group. This eliminates conditions 3 and 4 from the group-based key generation problem. The new problem is defined with the following conditions:

• $g_i\cap g_j=\varnothing$
• $g_1\cup g_2\cup \dots \cup g_m=G$
• $\left|f_{\mathrm{ji}}{–f}_{jk}\right|{\text{>}f}_{\mathrm{th}}$ for all elements in the same subgroup

Authors of this work also presented an algorithm for solving this problem which is called the constructive grouping algorithm (CGA). However, they have also not provided any evidence that the CGA finds the optimum solution.

2.3. Syndrome Coding

As discussed before, in [17], CSC has been proposed to generate binary keys from a group of PUF measurements (Figure 1). Since CSC does not utilize all possible numbers that can be generated from n number of bits (in the case of five bits it only uses the range 0–23 and it never uses 24–31) the number of 0s in a key generated using CSC tends to be larger than the number of 1s, which causes bit aliasing. This makes the keys non-random and vulnerable to modeling attacks. To overcome this issue, one can shift the above range to 4–27 to make it symmetric with respect to the whole range. However, another problem with CSC is that a swap in the ordering due to temporal variations will cause several bit errors which increases the cost of error correction. For example, it can be seen in Figure 1 that a swap between $f_1$ and $f_2$ leads to the key 00110, which suffers from two bits error compared to the original key 00000. Moreover, in order to implement CSC in an IoT device, for each group length, a look-up table similar to Figure 1 should be stored. This increases the storage costs of the IoT device.

To solve the above issues with CSC, Kendall syndrome coding (KSC) has been introduced in [18]. The idea of KSC is to compare all the elements in a subgroup pairwise. Suppose subgroup $g_i$ has $k$ elements. The result of applying KSC to $g_i$ is derived from Equation (3):

$$S_{g_i}=\mathsf{\delta }\left(1,2\right)\mathsf{\delta }\left(1,3\right)\dots \mathsf{\delta }\left(1,k\right)\mathsf{\delta }\left(2,3\right)\dots \mathsf{\delta }\left(2,k\right)\dots \mathsf{\delta }\left(k-1,k\right)$$

(3)

where $\mathsf{\delta }\left(i,j\right)=0$ if $f_i{\text{<}f}_j$, and $\mathsf{\delta }\left(i,j\right)=1$ otherwise. The main advantage of KSC is that, in the case of a flip between two adjacent $f_r$, it limits the number of bit errors to one, because only the result of comparison between the swapped values will change. However, KSC reduces the entropy of the generated key by introducing redundancy. For example, suppose that KSC is being applied on the three elements $f_1{,f}_2{,f}_3$, and the ordering of the elements is $f_3{\text{>}f}_1{\text{>}f}_2$. When pairs (1,2) and (1,3) are compared in a triple, the result of the pair (2,3) comparison is already revealed, and the third generated bit does not add any entropy to the output key. This makes the PUF prone to security attacks.

3. Proposed Key Generation Method

3.1. Positioning Syndrome Coding

To overcome the abovementioned coding issues, we propose a novel coding scheme and name it positioning syndrome coding (PSC). In this scheme, when the elements of subgroup $g_i$ are measured and ordered by their values, we take the elements one by one and generate a code based on the position of each element in the ordered subgroup. For example, suppose $g_1=\left\{f_1{,f}_2{,f}_3{,f}_4\right\}$ and $f_2{\text{>}f}_4{\text{>}f}_3{\text{>}f}_1$. The ordered subgroup will be $g_1{}_{\mathit{ordered}}=\left\{f_2{,f}_4{,f}_3{,f}_1\right\}$. The position of $f_1$ in $g_1{}_{\mathit{ordered}}$ from four possibilities is four. One can encode these four possibilities into two bits as 00, 01, 11, and 10. Therefore, 10 is assigned to $f_1$, as it is shown in step 1 in Figure 2. Note that for encoding the position values, Gray code has been used. For the next element, $f_2$, there are three possibilities in the ordering, since position four is already determined to be $f_1$. According to step 2 in Figure 2, the three positioning possibilities for $f_2$ are encoded as 00, 01, and 11. Since it is the largest value in the remaining elements of the group $\left\{f_2{,f}_3{,f}_4\right\}$, the code 00 is assigned to $f_2$. Element $f_3$ is in the second position from the two remaining positions. These two positions are encoded with one bit as 0 and 1 (step 3 in Figure 2). Therefore, 1 is assigned to $f_3$. Finally, since the position of the last element, $f_4$, is already determined by positioning the other elements, no code can be generated from this element and it is automatically positioned as seen in step 4 in Figure 2. By concatenating the generated codes, the generated key from subgroup $g_1$ is ${\mathit{key}}_{g_1}$ = 10,001.

The fact that the placement result of each element is independent of that of the previously placed elements indicates that there will be no redundancy issue in the final key. Moreover, the employment of Gray code to encode the placement result lowers the error correction cost because every flip between two adjacent elements in the ordering will cause only one bit error. In the above example, suppose that $f_2$ and $f_4$ flip in the measurement. The final key will be 10011, which only differs one bit from the original key. It is worth noting that using the conventional error correction methods, e.g., BCH codes, along with PSC leads to reproducible secret keys with low costs.

Another benefit of employing Gray code is that it reduces the bit aliasing of the generated key. The positioning of a specific number of elements produces more 0s, while another number of elements tends to produce more 1s. In the long run these tendencies cancel out each other, preventing bit aliasing. For example, positioning five elements produces more 0s because the first five Gray codes contain more 0s than 1s. On the other hand, six elements produce the same number of 1s and 0s, seven elements produce more 1s, eight elements produce the same number of 1s and 0s, and so on.

3.2. Integer Linear Programming

The length of the generated key as a result of applying PSC to a single subgroup is calculated by:

$$L_{g_i}={\displaystyle \sum }_{j=2}^{\left|g_i\right|}[{\log }_{2}j]$$

(4)

where $\left|g_i\right|$ is the number of elements of subgroup $g_i$. Note that in Equation (4), the length of the key is the summation of the bits generated by positioning each element of the subgroup. The length of the final key from a partition with $m$ subgroups is calculated by:

$$L_{\mathit{key}}={\displaystyle \sum }_{i=1}^m{\displaystyle \sum }_{j=2}^{\left|g_i\right|}[{\log }_{2}j]$$

(5)

The goal of the group-based key generation is to maximize $L_{\mathit{key}}$ and increase the PUF secret key length. This cost function, in addition to the previously defined constraints, form an optimization problem. Here, this problem is formulated and solved using an ILP optimization method. This method formulates and solves a problem with a linear cost function and constraints and integer decision variables. The generic form of an ILP problem [19] is:

$$\begin{array}{c}\begin{array}{c}\underset{x}{\min }{C}^{T}x\\ \end{array}\\ \mathrm{Subject}\mathrm{to}\text{:}\{\begin{array}{c}\mathit{Ax}\le B\\ A_{\mathit{eq}}{x=B}_{\mathit{eq}}\\ \mathit{lb}\le x\le \mathit{ub}\end{array}\end{array}$$

(6)

where $x$ is the decision variables vector. This generic form of the problem consists of inequality constraints, equality constraints, and the boundaries of the decision variables.

In a group-based key generation problem, $n$ elements of group $G$ form partition $P$ with $m$ subgroups. Each element can be the member of only one subgroup. The decision variables are defined by:

$$x_{\mathit{ji}}=\{\begin{array}{cc}1& {,f}_i\in g_{\mathrm{j}}\\ 0& {,f}_i\notin g_{\mathrm{j}}\end{array}$$

(7)

Figure 3 shows the relationship between the elements, subgroups, and decision variables.

Problem constraints are categorized into two main categories:

• Each measured value cannot be the member of more than one subgroup:

  $$x_{1i}{+x}_{2i}{+\dots +x}_{\mathit{mi}}\le 1;1\le i\le n$$

  (8)
• If the distance between two PUF measurements is less than the threshold value, they cannot be members of the same subgroup:

  $$\mathrm{if}\left|f_i{-f}_k\right|{<f}_{\mathrm{th}}\to x_{\mathit{ji}}{+x}_{\mathit{jk}}\le 1$$

  (9)

The first category adds $n$ inequality constraints to the problem. The number of constraints in the second category depends on the measured values of the elements. Note that, while being out of the scope of this work, care must be taken when choosing $f_{\mathrm{th}}$, since it should consider the effect of environmental conditions, such as temperature and humidity, as well as the effect of aging on the PUF measurements. However, it is inevitable that in some conditions, even the elements that are carefully distanced by $f_{\mathrm{th}}$ swap and cause bit errors. That makes the employment of error correction methods, such as BCH codes, necessary.

Obviously, it is not possible to formulize Equation (6) as a linear function of the decision variables. However, one can find an equivalent linear cost function which, when optimized, guarantees the maximum length of the key. It should be noted that putting as many elements in the first group as possible yields longer keys. For example, the optimum case for six elements is putting all of them in one subgroup to generate 11 bits, while all other grouping possibilities yield shorter keys (Figure 4). Therefore, the cost function can be defined in a way that the ILP solver first tries to make the first subgroup as large as possible, then from the remaining elements finds the second largest subgroup, and so on. It is formulized as a function of decision variables:

$$C^T{x=c}_1\left(x_{11}{+x}_{12}{+\dots +x}_{1n}\right){+c}_2\left(x_{21}{+x}_{22}{+\dots +x}_{2n}\right){+\dots +c}_m\left(x_{m1}{+x}_{m2}{+\dots +x}_{\mathit{mn}}\right)$$

(10)

$$c_j=-\frac{m-\left(j-1\right)}{m};1\le j\le m$$

(11)

Equations (11) and (12) force the ILP solver to first make the first subgroup as large as possible, then the second subgroup, and so on. The negative sign for the $c_j$ coefficients is due to the fact that the solver tries to minimize the cost function. One benefit of ILP is that while its solution gives the key with the highest entropy, the key is still as robust as any shorter key produced by other group-based methods, as long as the threshold value is the robustness and reliability anchor. This is because ILP respects the threshold value throughout the problem constraints when looking for the solution, equal to other methods.

The final form of an ILP problem for group-based key generation is shown in Equation (12). When solved, ILP gives the decision variables $x_{\mathit{ji}}$. Using $x_{\mathit{ji}}$ values, the elements of every group are determined according to Figure 3. When partition P is formed, PSC is applied to every subgroup and the derived bit sequences are concatenated to generate the final key. It has been proven that ILP is an NP-complete problem [19], which means that when a solution is found for the problem, it can be verified quickly that the solution is correct and “optimum”. Therefore, employing ILP guarantees that the generated key is maximized with regard to the problem constraints. It should be noted that for each PUF, the ILP is applied only once at the enrollment phase to determine partition P, while PSC is performed every time the key needs to be derived in the regeneration phase.

$$\underset{x}{\text{min}}\left[\begin{array}{ccc}\begin{array}{cc}{c}_{\text{1}}& \text{|}\end{array}& \begin{array}{cc}{c}_{\text{2}}& \text{|}\end{array}& \begin{array}{ccc}\cdots & \text{|}& c_{\text{m}}\end{array}\end{array}\right]\left[\begin{array}{c}\underset{\_}{\begin{array}{c}\begin{array}{c}{x}_{\text{11}}\\ x_{12}\end{array}\\ ⋮\\ x_{\text{1n}}\end{array}}\\ \underset{\_}{\begin{array}{c}\begin{array}{c}{x}_{21}\\ x_{\text{22}}\end{array}\\ ⋮\\ x_{\text{2n}}\end{array}}\\ \begin{array}{c}\begin{array}{c}\underset{\_}{ ⋮ }\\ x_{\text{m1}}\end{array}\\ x_{\text{m2}}\\ \begin{array}{c}⋮\\ x_{\text{mn}}\end{array}\end{array}\end{array}\right] \text{Subject} \text{to}:\{\left[\begin{array}{c}{A}_1\\ A_2\\ \begin{array}{c}⋮\\ A_L\end{array}\end{array}\right]\left[\begin{array}{c}\underset{\_}{\begin{array}{c}\begin{array}{c}{x}_{11}\\ x_{12}\end{array}\\ ⋮\\ x_{\text{1n}}\end{array}}\\ \underset{\_}{\begin{array}{c}\begin{array}{c}{x}_{21}\\ x_{22}\end{array}\\ ⋮\\ x_{\text{2n}}\end{array}}\\ \begin{array}{c}\begin{array}{c}\underset{\_}{ ⋮ }\\ x_{\text{m1}}\end{array}\\ x_{\text{m2}}\\ \begin{array}{c}⋮\\ x_{\text{mn}}\end{array}\end{array}\end{array}\right]\le \left[\begin{array}{c}\text{1}\\ \text{1}\\ \begin{array}{c}⋮\\ \text{1}\end{array}\end{array}\right];\left[\begin{array}{c}\text{0}\\ \text{0}\\ \begin{array}{c}⋮\\ \text{0}\end{array}\end{array}\right]\le \left[\begin{array}{c}\underset{\_}{\begin{array}{c}\begin{array}{c}{x}_{\text{11}}\\ x_{\text{12}}\end{array}\\ ⋮\\ x_{\text{1n}}\end{array}}\\ \underset{\_}{\begin{array}{c}\begin{array}{c}{x}_{\text{21}}\\ x_{\text{22}}\end{array}\\ ⋮\\ x_{\text{2n}}\end{array}}\\ \begin{array}{c}\begin{array}{c}\underset{\_}{ ⋮ }\\ x_{\text{m1}}\end{array}\\ x_{\text{m2}}\\ \begin{array}{c}⋮\\ x_{\text{mn}}\end{array}\end{array}\end{array}\right]\le \left[\begin{array}{c}\text{1}\\ \text{1}\\ \begin{array}{c}⋮\\ \text{1}\end{array}\end{array}\right]$$

(12)

4. Results and Discussions

4.1. Datasets for Testing

In order to validate the findings of this work, the proposed methods have been applied to data from two different types of PUF. These datasets were collected in previous studies on PUF at our institution. They were measured several times in different environmental conditions in order to analyze the effect of environment on the outputs.

The first dataset is from DiffC-PUF [3], which utilizes a resistor-transistor-logic inverter array (Figure 5a). By applying the same supply voltage and measuring the output voltage of all inverters, a set of PUF measurements is produced. The manufacturing variations of transistors and resistors makes the output voltage of every inverter unique. DiffC-PUF includes 80 inverters, and the output voltage of each inverter has been measured 20 times and the average voltage is calculated to reduce the measurement error.

The second PUF being used for evaluation is the switched capacitor network PUF (SCN-PUF) [20], which contains several capacitor networks in its circuit (Figure 5b). At the initial time, all reference capacitors $C_{ref}$ are charged with the same reference voltage, $V_{ref}$. Then, $C_{ref}$ capacitors are connected to the circuit one by one by enabling the corresponding switch $s_i$, and then discharged into the circuit. By choosing different permutations of the reference capacitors being connected to the circuit, different output voltages ($V_{PM}$ in Figure 5b) are generated due to uncontrollable capacitance differences between seemingly similar capacitors. The employed PUF for this work consists of eight capacitor networks and produces $8!=40320$ unique voltage values, from which we have randomly chosen 100 voltage values.

4.2. Key Generation

In order to evaluate the proposed ILP, its output has been compared with the CGA outputs for the DiffC-PUF and the SCN-PUF. After the derivation of group data using ILP and CGA, the output key is generated using PSC. Figure 6 and Figure 7 show the number of reliable bits generated from these two methods for DiffC-PUF and SCN-PUF, respectively. The results show a roughly 10 percent improvement in the number of output bits when using ILP. Increasing the threshold value in both PUFs results in stricter constraints when putting measurement values in the groups, which in turn reduces the length of the output key. It is worth noting that, by employing the non-group-based key generation methods mentioned in Section 2.1, the best result comes from the method proposed in [16], which produces 79 bit and 99 bit keys from DiffC-PUF and SCN-PUF, respectively. It is evident that on average, our method improved the key entropy approximately three times compared to the non-group-based key generation methods.

4.3. Positioning Syndrome Coding

For the assessment of PSC, after forming groups of PUF measurements by solving the group-based key generation problem with ILP, PSC and CSC have been applied to the group data to generate an output key. In Figure 8, the number of reliable bits versus different threshold values obtained by applying PSC and CSC for DiffC-PUF is depicted. They have also been applied to SCN-PUF data, and the results are shown in Figure 9. The results for both PUFs confirms the superiority of PSC over CSC for generating keys with more reliable bits. As explained above, since KSC produces low-entropy keys, and it has been eliminated from the comparisons in this section.

4.4. Reliability Analysis

As discussed before, when employing CSC, a single swap in the ordering of the members of a group can cause several error bits. On the other hand, by using PSC, each swap leads to only one bit error. In order to evaluate PSC, the reliability of the keys generated from this method have been compared with those generated by CSC. Figure 10 shows the reliability of the keys when generated using DiffC-PUF measurements by employing PSC and CSC in different threshold voltages. It is evident that the reliability has been improved by roughly 2%, reaching 98% when PSC is used. The datasets used for key generation in this work show significant variations with temperature [3,20]. However, this reliability analysis shows that even for the PUFs which are sensitive to environmental conditions, our proposed method offers close to ideal reliability results.

5. Conclusions

In this work, we reformulated the group-based key generation problem using ILP which gives the optimum solution. It has been shown that it improves the output key length by around 10 percent compared to previous methods. Moreover, we have shown that with the proposed PSC method, an average reliability of 98% could be achieved, which improves the reliability by 2% compared to conventional methods. In the end, in order to confirm the findings of this work, they have been evaluated using the datasets from two different PUFs that can be found in the literature.