---
abstract: 'Noisy measurements of a physical unclonable function (PUF) are used to store secret keys with reliability, security, privacy, and complexity constraints. A new set of low-complexity and orthogonal transforms with no multiplication is proposed to obtain bit-error probability results significantly better than all methods previously proposed for key binding with PUFs. The uniqueness and security performance of a transform selected from the proposed set is shown to be close to optimal. An error-correction code with a low-complexity decoder and a high code rate is shown to provide a block-error probability significantly smaller than provided by previously proposed codes with the same or smaller code rates.'
address: |
    Information Theory and Applications Chair, Technische Universität Berlin\
    {[guenlue]{}, [rafael.schaefer]{}}[@tu-berlin.de]{}\
bibliography:
- 'references.bib'
title: |
    LOW-COMPLEXITY AND RELIABLE TRANSFORMS FOR\
    PHYSICAL UNCLONABLE FUNCTIONS
---

physical unclonable function (PUF), no multiplication transforms, secret key agreement, low complexity.

Introduction
============

Biometric identifiers such as fingerprints are useful to authenticate a user. Similarly, secret keys are traditionally stored in non-volatile memories (NVMs) to authenticate a physical device that contains the key. NVMs require hardware protection even when the device is turned off since an attacker can try to obtain the key at any time. A safe and cheap alternative to storing keys in NVMs is to use physical identifiers, e.g., fine variations of ring oscillator (RO) outputs, as a randomness source. Since invasive attacks to physical identifiers permanently change the identifier output, there is no need for continuous hardware protection for physical identifiers [@pufintheory].

Physical unclonable functions (PUFs) are physical identifiers with reliable and high-entropy outputs [@GassendThesis; @PappuThesis]. PUF outputs are unique to each device, so they are used for safe and low-complexity key storage in digital devices. These keys can be used for private authentication, secure computation, and encryption. Replacing such identifiers is expensive, so key-storage methods should limit the information the public data leak about the identifier outputs. Moreover, the same device should be able to reconstruct a secret key generated from the noiseless outputs by using the noisy outputs and public information. The ultimate secret-key vs. privacy-leakage rate tradeoffs are given in [@IgnaTrans; @LaiTrans; @benimdissertation]. The secret-key and privacy-leakage rate limits for a suboptimal chosen-secret (CS) model called *fuzzy commitment scheme* (FCS) [@FuzzyCommitment] are given in [@IgnatenkoFuzzy]. We consider the FCS to compare different post-processing methods applied to PUFs. Asymptotically optimal CS model constructions are given in [@bizimWZ] and similar comparison results can be obtained by using these constructions.

Physical identifier outputs are highly correlated and noisy, which are the two main problems in using PUFs. If errors in the extracted sequences are not corrected, PUF reliability would be low. If correlations are not eliminated, machine learning algorithms can model the PUF outputs [@MLPUF]. To solve the two problems, the discrete cosine transform (DCT) is used in [@bizimtemperature] to generate a uniformly-distributed bit sequence from PUFs under varying environmental conditions. Similarly, the discrete Walsh-Hadamard transform (DWHT), discrete Haar transform (DHT), and Karhunen-Loève transform (KLT) are compared in [@bizimMDPI] in terms of the maximum secret-key length, decorrelation efficiency, reliability, security, and hardware cost. The DCT, DWHT, and DHT provide good reliability and security results, and a hardware implementation of the DWHT in [@bizimMDPI] shows that the DWHT requires a substantially smaller hardware area than other transforms. There are two main reasons why the DWHT can be implemented efficiently. Firstly, the matrix that represents the DWHT has elements $1$ or $-1$, so there is no matrix multiplication. Secondly, an input-selection algorithm that is an extension of the algorithm in [@InputSelection] allows to calculate two-dimensional (2D) DWHT recursively. Based on these observations, we propose a new set of transforms that preserve these properties and that significantly improve the reliability of the sequences extracted from PUFs.

The FCS requires error-correction codes (ECCs) to achieve the realistic block-error probability of $\displaystyle P_\text{B}\!=\!10^{-9}$ for RO PUFs. The ECCs proposed in [@bizimMDPI] have better secret-key and privacy-leakage rates than previously proposed codes, but in some cases it is assumed that if multiple bits are extracted from each transform coefficient, each bit is affected by independent errors. This assumption is not valid in general. Thus, we extract only one bit from each transform coefficient. The contributions of this work are as follows.

-   We propose a new set of 2D orthogonal transforms that have low-complexity hardware implementations and no matrix multiplications. The new set of transforms are shown to provide an average bit-error probability smaller than the most reliable transform considered in the PUF literature, i.e., DCT.

-   Bit sequences extracted using a transform selected from the new set of transforms are shown to give good uniqueness and security results that are comparable to state-of-the-art results.

-   We propose a joint transform-quantizer-code design method for the new set of transforms in combination with the FCS to achieve a block-error probability substantially smaller than the common value of $10^{-9}$ with perfect secrecy.

This paper is organized as follows. In Section \[sec:fuzzycommitment\], we review the FCS. The transform-coding algorithm to extract secure sequences from RO PUFs is explained in Section \[sec:commonsteps\]. A new set of orthogonal transforms that require a small hardware area and that result in bit-error probabilities smaller than previously considered transforms is proposed in Section \[sec:neworth\]. In Section \[sec:comparisons\], we compare the new transforms with previous methods and show that the proposed ECC provides a block-error probability for the new selected transform (ST) that is smaller than for previously considered transforms.

Review of the Fuzzy Commitment Scheme {#sec:fuzzycommitment}
=====================================

Fig. \[fig:fuzzycommitment\] shows the FCS, where an encoder ${\mathsf{Enc}}(\cdot)$ adds a codeword $\displaystyle C^N$, uniformly distributed over a set with cardinality $|\mathcal{S}|$, modulo-2 to the binary noiseless PUF-output sequence $\displaystyle X^N$ during enrollment. We show in Section \[sec:commonsteps\] that the sequence $X^N$ and its noisy version $Y^N$ can be obtained by applying the post-processing steps in Fig. \[fig:postprocessing\] to RO outputs $\widetilde{X}^L$ and its noisy version $\widetilde{Y}^L$, respectively. The sum $\displaystyle W^N=C^N{\mathbin{\oplus}}X^N$ is publicly sent through a noiseless and authenticated channel, and it is called *helper data*. The modulo-2 sum of $W^N$ and the noisy PUF-output sequence $Y^N =X^N {\mathbin{\oplus}}E^N$, where $E^N$ is the binary error vector, gives the noisy codeword $\displaystyle C^N{\mathbin{\oplus}}E^N$. Using the noisy codeword, a channel decoder $\displaystyle {\mathsf{Dec}}(\cdot)$ estimates the secret key $S$ during reconstruction. A reliable secret-key agreement is possible by using $X^N$, $Y^N$, and $W^N$ [@AhlswedeCsiz; @Maurer].

One can achieve a (secret-key, privacy-leakage) rate pair $ (R_\text{s}\text{,}R_\ell)$ using the FCS with perfect secrecy if, given any $\epsilon\!>\!0$, there is some $N\!\geq\!1$, and an encoder and a decoder for which $\displaystyle R_\text{s}=\frac{\log|\mathcal{S}|}{N}$ and $$\begin{aligned}
{2}
&\Pr[S\ne\hat{S}] \leq \epsilon && (\text{reliability}) \label{eq:reliabilityconst}\\
&I\big(S;W^N\big)\!=\!0 && (\text{perfect secrecy})\label{eq:secrecyconst}\\
&\frac{1}{N}I\big(X^N;W^N\big) \leq R_\ell+\epsilon. \quad\quad\quad&&(\text{privacy})  \label{eq:privacyconst}\end{aligned}$$ Condition (\[eq:secrecyconst\]) ensures that the public side information $W^N$ does not leak any information about the secret key, so one achieves perfect secrecy. The normalized information that $W^N$ leaks about the PUF output sequence $X^N$ is considered in (\[eq:privacyconst\]). If one should asymptotically limit the unnormalized privacy leakage $I(X^N;W^N)$, private keys available during enrollment and reconstruction are necessary [@IgnaTrans], which is not realistic or practical; see the discussions in [@bizimWZ].

Suppose the measurement channel $P_{Y|X}$ is a binary symmetric channel (BSC) with crossover probability $p$, and $X$ is independent and identically distributed (i.i.d.) according to a uniform distribution. Define $\displaystyle H_b(p)\!=\!-p\log p-(1\!-p)\log(1\!-p)$ as the binary entropy function. The region $\displaystyle \mathcal{R}$ of all achievable (secret-key, privacy-leakage) rate pairs for the FCS with perfect secrecy is [@IgnatenkoFuzzy] $$\begin{aligned}
\mathcal{R}\! =\! \big\{ \left(R_\text{s},R_\ell\right)\!\colon\!\quad 0\leq R_\text{s}\leq 1-H_b(p),\quad R_\ell\geq 1\!-\!R_\text{s} \big\}.\label{eq:ls0}\end{aligned}$$ We plot this region in Section \[sec:comparisons\] to evaluate the secret-key and privacy-leakage rates achieved by the proposed ECC.

The FCS is a particular realization of the CS model. The region $\mathcal{R}_{\text{cs}}$ of all achievable (secret-key, privacy-leakage) rate pairs for the CS model, where a generic encoder is used to confidentially transmit an embedded secret key to a decoder that observes $Y^N$ and the helper data $W^N$, is given in [@IgnaTrans; @LaiTrans] as the union over all $P_{U|X}$ of the set of achievable rate pairs $\left(R_\text{s},R_\ell\right)$ such that $$\begin{aligned}
\Big\{0\leq R_\text{s}\leq I(U;Y),\qquad R_\ell\geq I(U;X)-I(U;Y)\!\Big\}\label{eq:chosensecret}\end{aligned}$$ where $P_X$ is the probability distribution of $X$ and the alphabet $\mathcal{U}$ of the auxiliary random variable $U$ can be limited to have the size $\displaystyle |\mathcal{U}|\!\leq\!|\mathcal{X}|+1$ as $U-X-Y$ forms a Markov chain. The FCS achieves a boundary point of $\mathcal{R}_{\text{cs}}$ for a BSC $P_{Y|X}$ only at the point $\displaystyle (R_\text{s}^*,R_\ell^*)\!=\!(1\!-\!H_b(p),H_b(p))$. To achieve the other points on the rate-region boundary, one should use a nested code construction as in [@bizimWZ] or a binning based construction as in [@MatthieuPolar], both of which require careful polar code [@Arikan] designs. This is not necessary to illustrate the gains from the new set of transforms and it suffices to combine the new set with the FCS.

Post-processing Steps {#sec:commonsteps}
=====================

We consider a 2D array of $r\!\times\!c$ ROs. Denote the continuous-valued outputs of $L\!=\!r\!\times\!c$ ROs as the vector random variable $\widetilde{X}^L$, distributed according to $\displaystyle f_{\widetilde{X}^L}$. Suppose that the noise component $\widetilde{E}_j$ on the $j$-th RO output is Gaussian distributed with zero mean for all $j=1,2,\ldots,L$ and that the noise components are mutually independent. Denote the noisy RO outputs as $\widetilde{Y}^L\!=\!\widetilde{X}^L\!+\!\widetilde{E}^L$. We extract binary vectors $X^N$ and $Y^N$ from $\widetilde{X}^L$ and $\widetilde{Y}^L$, respectively, and define binary error variables $\displaystyle E_i\!=\!X_i{\mathbin{\oplus}}Y_i$ for $i\!=\!1,2,\ldots,N$.

![The transform-coding steps.[]{data-label="fig:postprocessing"}](./Transformcodingmodel.eps){width="48.50050%" height="0.5005\textheight"}

The post-processing steps used during the enrollment (and reconstruction) to extract a bit sequence $X^N$ (and its noisy version $Y^N$) are depicted in Fig. \[fig:postprocessing\]. These steps are transformation, histogram equalization, quantization, Gray mapping, and concatenation. Since RO outputs $\widetilde{X}^L$ are correlated, we apply a transform $\emph{T}_{r\!\times\!c}(\cdot)$ for decorrelation. We model all transform coefficients and noise components as random variables with Gaussian marginal distributions. A transform-coefficient output $T$ that comes from a distribution with mean $\mu\neq 0$ and variance $\sigma^2\neq 1$ is converted into a standard Gaussian random variable during histogram equalization, which reduces the hardware area when multiple bits are extracted. Independent bits can be extracted from transform coefficients by setting the quantization boundaries of a $K$-bit quantizer to $$\label{eq:quantsteps}
b_k=Q^{-1}\left(1-\dfrac{k}{2^K}\right) \text{ for } k=0,1,\dots,2^K$$ where $Q(\cdot)$ is the $Q$-function. Quantizing a coefficient $\hat{T}$ to $k$ if $\displaystyle b_{k-1}\!<\!\hat{T}\!\leq\!b_k$ ensures that $X^N$ is uniformly distributed, which is necessary to achieve the rate point where the FCS is optimal.

One can use scalar quantizers without a performance loss in security if the RO output statistics satisfy certain constraints [@benimdissertation]. We do not use the first transform coefficient, i.e., DC coefficient, for bit extraction since it corresponds to the average over the RO array, known by an attacker [@benimdissertation]. Furthermore, Gray mapping ensures that the neighboring quantization intervals result in only one bit flip. This is a good choice as the noise components $E_i$ for all $i=1,2,\ldots,N$ have zero mean. The sequences extracted from transform coefficients are concatenated to obtain the sequence $X^N$ (or $Y^N$).

New Orthogonal Transforms {#sec:neworth}
=========================

A useful metric to measure the complexity of a transform is the number of operations required for computations. Consider only RO arrays of sizes $ r\!=\!c\!=\!8$ and $16$, which are powers of 2, so fast algorithms are available. In [@benimdissertation], the DWHT is suggested as the best candidate among the set of transforms {DCT, DHT, KLT, DWHT} for RO PUF applications with a low-complexity constraint such as internet of things (IoT) applications.

In [@bizimMDPI], we extend an input-selection algorithm to compute the 2D $16\times16$ DWHT by applying a $2\times2$ matrix operation recursively to illustrate that the DWHT requires a small hardware area in a field programmable gate array (FPGA) since it does not require any multiplications. Following this observation, we propose a set of transforms that are orthogonal (to decorrelate the RO outputs better), that have matrix elements $1$ or $-1$ (to eliminate multiplications), and that have size of $16\times16$ (to apply the input-selection algorithm given in [@bizimMDPI] to further reduce complexity). We show in the next section that these transforms provide higher reliability than other transforms previously considered in the literature.

Orthogonal Transform Construction and Selection {#subsec:orthtransselection}
-----------------------------------------------

Consider an orthogonal matrix $A$ with elements $1$ or $-1$ and of size $k\times k$, i.e., $AA^{T}= I$, where $T$ is the matrix transpose and $I$ is the identity matrix of size $k\times k$. It is straightforward to show that the following matrices are also orthogonal: $$\begin{aligned}
&\Biggl[ \begin{matrix}
A&A\\ A&\!-\!A
\end{matrix} \Biggr],
\Biggl[ \begin{matrix}
A&A\\ \!-\!A&A
\end{matrix} \Biggr],
\Biggl[ \begin{matrix}
A&\!-\!A\\ A&A
\end{matrix} \Biggr],
\Biggl[ \begin{matrix}
\!-\!A&A\\ A&A
\end{matrix} \Biggr],\nonumber\\
\Biggl[ &\begin{matrix}
\!-\!A&\!-\!A\\\! -\!A&A
\end{matrix} \Biggr],
\Biggl[ \begin{matrix}
\!-\!A&\!-\!A\\ A&\!-\!A
\end{matrix} \Biggr],
\Biggl[ \begin{matrix}
\!-\!A&A\\ \!-\!A&\!-\!A
\end{matrix} \Biggr],
\Biggl[ \begin{matrix}
A&\!-\!A\\ \!-\!A&\!-\!A
\end{matrix} \Biggr].\label{eq1}\end{aligned}$$ Since $2^{k^2}$ possible matrices should be checked for orthogonality, we choose $k\!=\!4$ to keep the complexity of the exhaustive search for orthogonal matrices low. The result of the exhaustive search is a set of orthogonal matrices $A$ of size $4\!\times\! 4$. By applying the matrix construction methods in (\[eq1\]) twice consecutively, we obtain $12288$ unique orthogonal transforms of size $16\!\times\! 16$ with elements $1$ or $\displaystyle -1$.

We apply these orthogonal transforms, one of which is the DWHT, to an RO dataset to select the orthogonal transform whose maximum bit-error probability over the transform coefficients is minimum. This selection method provides reliability guarantees to every transform coefficient. An ECC that has a higher code dimension than it is achievable according to the Gilbert-Varshamov (GV) bound [@GilbertGV; @varshamovGV] for the maximum error probability over the transform coefficients of the ST, is given in Section \[subsec:codeselection\]. This illustrates that our selection method is conservative and the block-error probability is substantially smaller than $10^{-9}$.

There are also other orthogonal transforms of size $16\times 16$ but we illustrate in the next section that the new set suffices to significantly increase the reliability of the extracted bits as compared to previously considered transforms and previous RO PUF methods.

Performance Evaluations {#sec:comparisons}
=======================

We use RO arrays of size $16\!\times \!16$ from the RO dataset in [@ROPUF] and apply the transform-coding steps in Fig. \[fig:postprocessing\] to compare the previously considered transforms with the new set of transforms in terms of their reliability, uniqueness, and security. We illustrate that a Bose-Chaudhuri-Hocquenghem (BCH) code can be used for error correction in combination with the FCS to achieve a block-error probability smaller than the common value of $10^{-9}$.

Transform Comparisons
---------------------

We compare the orthogonal transform selected from the new set, i.e., the ST, with the DCT and DWHT in terms of the bit-error probabilities of the $255$ transform coefficients obtained from the RO dataset in [@ROPUF]. Fig. \[fig:BERComparisonsofTrans\] illustrates the bit-error probabilities of the DCT, DWHT, and the ST. The mean of the ST is smaller than the means of the DCT and DWHT. Furthermore, the maximum bit-error probability of the DCT and ST are almost equal and are less than the maximum error probability of the DWHT. Most importantly, the ST has a large set of transform coefficients with bit-error probabilities close to zero, so an ECC design for the maximum or mean bit-error probability of the ST would give pessimistic rate results. We propose in the next section an ECC for the ST to achieve a smaller block-error probability than the block-error probability for the DCT.

Uniqueness and Security {#subsec:uniqueness}
-----------------------

A common measure to check the randomness of a bit sequence is uniqueness, i.e., the average fractional Hamming distance (HD) between the sequences extracted from different RO PUFs [@bizimpaper]. The rate region in (\[eq:ls0\]) is valid if the extracted bit sequences are uniformly distributed, making the uniqueness a valid measure for the FCS.

Uniqueness results for the DCT, DWHT, KLT, and DHT have a mean HD of $0.5000$ and HD variances of approximately $\displaystyle 7\!\times \!10^{-4}$ [@bizimMDPI], which are close to optimal and better than previous RO PUF results. For the ST, we obtain a mean HD of $0.5001$ and a HD variance of $\displaystyle 2.69\!\times \!10^{-2}$. This suggests that the ST has good average uniqueness performance, but there might be a small set of RO PUFs from which slightly biased bit sequences are extracted. The latter can be avoided during manufacturing by considering uniqueness as a parameter in yield analysis of the chip that embodies the PUF. We apply the national institute of standards and technology (NIST) randomness tests [@NIST] to check whether there is a detectable deviation from the uniform distribution in the sequences extracted by using the ST. The bit sequences generated with the ST pass most of the randomness tests, which is considered to be an acceptable result [@NIST]. A correlation thresholding approach in [@bizimtemperature] further improves security.

Code Selection {#subsec:codeselection}
--------------

Consider the scenario where secret keys are used as an input to the advanced encryption standard (AES), a symmetric-key cryptosystem, with a key size of $128$ bits, so the code dimension of the ECC should be at least $128$ bits. The maximum error probability over the transform coefficients of the ST is $p_{\text{max}}=0.0149$, as shown in Fig. \[fig:BERComparisonsofTrans\]. Furthermore, assume that we use an ECC with a bounded minimum distance decoder (BMDD) to keep the complexity low. A BMDD can correct all error patterns with up to $\lfloor\frac{d_{\text{min}-1}}{2}\rfloor$ errors, where $d_{\text{min}}$ is the minimum distance of the code. It is straightforward to show that the ECC should have at least a minimum distance of $d_{\text{min}}=41$ to achieve a block-error probability of $P_\text{B}\leq 10^{-9}$ if all transform coefficients are assumed to have a bit-error probability of $p_{\text{max}}$. None of binary BCH and Reed-Solomon (RS) codes, which have good minimum-distance properties, can satisfy these parameters. Similarly, the GV bound computed for $p_{\text{max}}$ shows that there exists a linear binary ECC with code dimension $98$. Consider the binary BCH code with the block length $255$, code dimension $131$ that is greater than the code dimension of $98$ given by the GV bound, and minimum distance $\displaystyle d_{\text{min,BCH}}=37$ that is close to the required value of $d_{\text{min}}=41$. We illustrate in the next section that this BCH code provides a block-error probability significantly smaller than $10^{-9}$.

Reliability, Privacy, and Secrecy Analysis of the Code
------------------------------------------------------

We now show that the proposed ECC satisfies the block-error probability constraint. The block-error probability $P_\text{B}$ for the $\text{BCH}(255,131,37)$ code with a BMDD is equal to the probability of having more than $18$ errors in the codeword, i.e., we have $$\begin{aligned}
 P_\text{B} = \sum_{j=19}^{255}\Bigg[\sum_{\mathcal{D}\in\mathcal{F}_j}\prod_{i\in \mathcal{D}}p_{i}\,\bigcdot\prod_{i\in \mathcal{D}^{c}}(1-p_{i}) \Bigg] \label{eq:blockerrorforbch}\end{aligned}$$ where $p_{i}\leq p_{\text{max}}$ is the bit-error probability of the $i$-th transform coefficient, as in Fig. \[fig:BERComparisonsofTrans\], for $i\!=\!2,3,\ldots,256$, $\displaystyle \mathcal{F}_j$ is the set of all size-$j$ subsets of the set $\displaystyle\{2,3,\ldots,256\}$, and $\mathcal{D}^{c}$ denotes the complement of the set $\mathcal{D}$. The bit-error probabilities $p_{i}$ represent probabilities of independent events due to the mutual independence assumption for transform coefficients and one-bit quantizers used.

The evaluation of (\[eq:blockerrorforbch\]) requires $ \sum_{j=0}^{18}{255\choose j}\approx 1.90\!\times\!10^{27}$ different calculations, which is not practical. We therefore apply the discrete Fourier transform - characteristic function (DFT-CF) method [@DFTCF] to (\[eq:blockerrorforbch\]) and obtain the result $P_\text{B}\!\approx\!2.860\!\times\!10^{-12}\!<\!10^{-9}$. This value is smaller than the block-error probabilitiy $P_{\text{B,DCT}}= 1.26\times 10^{-11}$ obtained in [@benimdissertation] for the DCT with the same code. The block-error probability constraint is thus satisfied by using the $\text{BCH}$ code although the conservative analysis suggests otherwise.

The rate regions given in (\[eq:ls0\]) and (\[eq:chosensecret\]) are asymptotic results, i.e., they assume $N\rightarrow \infty$. Since separate channel and secrecy coding is optimal for the FCS, we can use the finite length bounds for a BSC $P_{Y|X}$ with crossover probability $p\!=\! \frac{1}{L-1}\sum_{i=2}^Lp_{i}\!\approx\!0.0088$, i.e., the error probability averaged over all used coefficients. In [@benimdissertation], we show that the $\text{BCH}(255,131,37)$ code achieves $(R_{\text{s,BCH}},R_{\ell,\text{BCH}})\approx(0.514,\,0.486)$ bits/source-bit, significantly better than previously proposed codes in the RO PUF literature, so it suffices to compare the proposed code with the best possible finite-length results for the FCS. We use Mrs. Gerber’s lemma [@WZ], giving the optimal auxiliary random variable $U$ in (\[eq:chosensecret\]), to compute all points in the region $\mathcal{R}_{\text{cs}}$. We plot all achievable rate pairs, the (secret-key, privacy-leakage) rate pair of the proposed BCH code, and a finite-length bound for the block length of $N=255$ bits and $P_\text{B}\!=\!10^{-9}$ in Fig. \[fig:ratecomparison\].

The maximum secret-key rate is $R_\text{s}^*\!\approx\!0.9268$ bits/source-bit with a corresponding minimum privacy-leakage rate of $R_\ell^*\!\approx\!0.0732$ bits/source-bit. The gap between the points $(R_{\text{s,BCH}},R_{\ell,\text{BCH}})$ and $(R_{\text{s}}^*,R_\ell^*)$ can be partially explained by the short block length of the code and the small block-error probability. The finite-length bound given in [@Polyanskiy Theorem 52] shows that the rate pair $(R_\text{s},R_\ell)\!=\!(0.7029,0.2971)$ bits/source-bit is achievable by using the FCS, as depicted in Fig. \[fig:ratecomparison\]. One can thus improve the rate pairs by using better codes and decoders with higher hardware complexity, which is undesirable for IoT applications. Fig. \[fig:ratecomparison\] also illustrates the fact that there are operation points of the region $\mathcal{R}_{\text{cs}}$ that cannot be achieved by using the FCS and, e.g., a nested polar code construction from [@bizimWZ] should be used to achieve all points in $\mathcal{R}_{\text{cs}}$.

Conclusion {#sec:conclusion}
==========

We proposed a new set of transforms that are orthogonal (so that the decorrelation efficiency is high), that have elements $1$ or $-1$ (so that the hardware complexity is low), and that have a size of $k\times k$ where $k$ is a power of 2 (so that an input-selection algorithm can be applied to further decrease complexity). By using one-bit uniform quantizers for each transform coefficient obtained by applying the ST, we obtained bit-error probabilities that are on average smaller than the bit-error probabilities obtained from previously considered transforms. We proposed a BCH code as the ECC for RO PUFs in combination with the FCS. This code achieves the best rate pair in the RO PUF literature and it gives a block-error probability for the ST that is substantially smaller than for the DCT. We illustrated that the FCS cannot achieve all possible rate points. In future work, in combination with the new set of transforms, we will apply a joint vector quantization and error correction method by using nested polar codes to achieve rate pairs that cannot be achieved by the FCS.
