Document [original]

entropy

Article

Secure and Reliable Key Agreement with Physical

Unclonable Functions †

Onur Günlü 1,*ID , Tasnad Kernetzky 2ID , Onurcan ˙

I¸scan 3ID , Vladimir Sidorenko 1ID ,

Gerhard Kramer 1ID and Rafael F. Schaefer 4ID

1Chair of Communications Engineering, Technical University of Munich, 80333 Munich, Germany;

vladimir[email protected] (V.S.); ger[email protected] (G.K.)

2Associate Professorship of Line Transmission Technology, Technical University of Munich,

80333 Munich, Germany; [email protected]

3Huawei Technologies Duesseldorf GmbH, 80992 Munich, Germany; [email protected]

4Information Theory and Applications Chair, Technische Universität Berlin, 10587 Berlin, Germany;

[email protected]

*Correspondence: onur[email protected]; Tel.: +49-89-289-23470

†

Parts of this paper were presented at the 2016 IEEE Global Conference on Signal and Information Processing

(Washington, DC, USA, 7–9 December 2016) and 2017 IEEE International Conference on Communications

(Paris, France, 21–25 May 2017).

Received: 25 March 2018; Accepted: 27 April 2018; Published: 3 May 2018





Abstract:

Different transforms used in binding a secret key to correlated physical-identifier outputs

are compared. Decorrelation efficiency is the metric used to determine transforms that give

highly-uncorrelated outputs. Scalar quantizers are applied to transform outputs to extract uniformly

distributed bit sequences to which secret keys are bound. A set of transforms that perform well

in terms of the decorrelation efficiency is applied to ring oscillator (RO) outputs to improve the

uniqueness and reliability of extracted bit sequences, to reduce the hardware area and information

leakage about the key and RO outputs, and to maximize the secret-key length. Low-complexity

error-correction codes are proposed to illustrate two complete key-binding systems with perfect

secrecy, and better secret-key and privacy-leakage rates than existing methods. A reference hardware

implementation is also provided to demonstrate that the transform-coding approach occupies a small

hardware area.

Keywords:

key agreement; physical unclonable functions; transform coding; privacy leakage;

hardware implementation

1. Introduction

Secret keys stored in a device can provide intellectual property protection, and device

authentication and identification. Non-volatile memory (NVM) is the traditional storage medium for

secret keys. Securing the NVM is expensive due to its susceptibility to physical attacks [

–

]. A cheap

and safe alternative to the NVM is to use physical identifiers as a source of randomness by applying

the concept of one-way functions [4] to physical systems.

Invasive (physical) attacks to physical identifiers permanently change the identifier output so

that an attacker cannot learn the secret key by using an invasive attack [

]. This property eliminates

the need for continuous hardware protection [

]. Physical identifiers, such as physical unclonable

functions (PUFs), e.g., the random start-up value of an uninitialized static random access memory

(SRAM) [6] or fine variations of ring oscillator (RO) outputs [7], are considered to be random sources

with high entropy [

]. Security applications that use a secret key stored in a NVM can alternatively use

Entropy 2018,20, 340; doi:10.3390/e20050340 www.mdpi.com/journal/entropy

Entropy 2018,20, 340 2 of 19

a PUF for the same purpose. Thus, we can use PUFs for low-complexity key storage in, e.g., internet of

things (IoT) applications like securing a surgical robot against hacking.

There are multiple key-generation, or generated-secret (GS), and key-binding, or chosen-secret (CS),

methods to reconstruct secret keys from noisy PUF outputs, where the key is generated from the PUF

outputs or bound to them, respectively. Code-offset fuzzy extractors [

] are examples of key-generation

methods and the

fuzzy commitment

scheme [

] is a key-binding method. Code constructions based

on Wyner-Ziv (WZ) coding are illustrated in [

] to asymptotically achieve the information-theoretic

limits for the GS and CS models. These constructions might have high complexity, which is undesired

for, e.g., IoT applications. In addition, since a key should be stored in a secure database for both models,

it is more practical to allow a trusted entity to choose the secret key bound to a PUF output. Thus,

in this paper, we aim at further improving reliability, privacy, secrecy, and hardware cost performance

of a transform-coding algorithm, explained next, that is applied to PUF outputs in combination with

the fuzzy commitment scheme.

PUFs have similar features to biometric identifiers like fingerprints. Both identifier types have

correlated and noisy outputs due to surrounding environmental conditions [

]. Correlation in

PUF outputs leaks information about the secret key, which causes secrecy leakage, and about the

PUF output, causing privacy leakage [

–

]. Moreover, noise reduces reliability of PUF outputs

and error-correction codes are needed to satisfy the reliability requirements. The transform-coding

approach [

] in combination with a set of scalar quantizers has made its way into secret-key

binding with continuous-output identifiers. This approach allows to reduce the output correlation and

to adjust the effective noise at the PUF output. For instance, the discrete cosine transform (DCT) is

the building block in [

] to generate a uniformly distributed bit sequence from RO outputs under

varying environmental conditions. Efficient post-processing steps are applied to obtain more reliable

PUF outputs rather than changing the hardware architecture, so standard components can be used.

This transform-coding approach improves on the existing approaches in terms of the reliability under

varying environmental conditions and maximum key length [

]. We apply this algorithm to PUF

outputs with further significant improvements by designing the transformation and error-correction

steps jointly.

Information-theoretic limits for the fuzzy commitment scheme are given in [

]. We use these

information-theoretic limits to compare error-correction codes proposed for the transform-coding

algorithm with the limits. Similar analyses were conducted for biometric identifiers in [

], but their

assumptions such as independent and identically distributed (i.i.d.) identifier outputs and maximum

block-error probability constraint

PB=

−2

are not realistic. We therefore consider highly correlated

RO outputs with the constraint

PB≤

−9

, which are realistic for security applications that use

PUFs [21].

1.1. Summary of Contributions and Organization

We improve the DCT-based algorithm of [

] by using different transforms and reliability metrics.

We also propose error-correction codes that achieve better (secret-key, privacy-leakage) rate tuples

than previous code designs. A summary of the main contributions is as follows.

•

We compare a set of transforms to improve the performance of the transform coding algorithm in

terms of the maximum secret-key length, decorrelation efficiency, uniqueness and security of the

extracted bit sequence, and computational complexity.

•

Two quantization methods with different reliability metrics are proposed to address multiple

design objectives for PUFs. One method aims at maximizing the length of the bit sequence

extracted from a fixed number of ROs, whereas the second method provides reliability guarantees

for each output in the transform domain by fixing the decoding capability of a decoder used for

error correction.

•

We give a reference hardware design for the transform with the smallest computational complexity,

among the set of transforms considered, in combination with the second quantization method

Entropy 2018,20, 340 3 of 19

to illustrate that our algorithm occupies a small hardware area. Our results are comparable to

hardware area results of previous RO PUF designs.

•

Error-correction codes that satisfy the block-error probability constraints for practical PUF systems

are proposed for both quantization methods to illustrate complete key-binding systems with

perfect secrecy. The proposed codes operate at better rate tuples than previously proposed

codes for the fuzzy commitment scheme. Our quantizer designs also allow us to significantly

reduce the gap to the optimal (secret-key, privacy-leakage) rate point achieved by the fuzzy

commitment scheme.

This paper is organized as follows. In Section 2, we define the fuzzy commitment scheme that uses

PUF outputs as the randomness source. The transform-coding algorithm proposed to extract a reliable

bit sequence from RO PUFs is explained in Section 3. We propose two different quantization methods

with different reliability metrics in Section 4. In Section 5, we illustrate the small hardware area of the

proposed algorithm with a reference hardware design, and the gains in terms of reliability, security,

and maximum secret-key length as compared to the existing methods. Our proposed error-correction

codes, and their secrecy and privacy performance are described in Section 6. Section 7concludes

the paper.

1.2. Notation

Upper case letters represent random variables and lower case letters their realizations. A letter

with superscript denotes a string of variables, e.g.,

XN=X1. . . Xi. . . XN

, and a subscript denotes the

position of a variable in the string. A random variable

has probability mass

or probability density

. Calligraphic letters such as

denote sets, and set sizes are denoted as

|X |

. Bold letters such as

represent matrices.

Enc(·)

is an encoder mapping and

Dec(·)

is a decoder mapping.

X−Y−Z

indicates a Markov chain.

Hb(x) = −xlog2x−(

−x)log2(

−x)

is the binary entropy function.

The

∗

-operator is defined as

p∗x=p(

−x) + (

−p)x

. The operator

⊕

represents the element-wise

modulo-2 summation. A binary symmetric channel (BSC) with crossover probability

is denoted

by BSC(

Xn∼Bernn(α)

denotes that

is an i.i.d. binary sequence of random variables with

Pr[Xi=

] = α

for

1, 2,

. . .

Unif [

:|X |]

represents a uniform distribution over the integers from

1 to

|X |

. A linear error-correction code

with parameters

has block length

, dimension

and minimum distance dso that it can correct up to bd−1

2cerrors. .

2. System Model and the Fuzzy Commitment Scheme

Consider an RO as a source that generates a real-valued symbol

. Systematic variations in RO

outputs in a two-dimensional array are less than the systematic variations in one-dimensional ROs [

We thus consider a two-dimensional RO array of size

L=r×c

and represent the array as a vector

random variable

. Suppose there is a single PUF circuit, i.e., a single two-dimensional RO array,

in each device with the same circuit design, and it emits an output

according to a probability density

. Each RO output is disturbed by mutually-independent additive white Gaussian noise (AWGN)

and the vector noise is denoted as

. Define the noisy RO outputs as

YL=e

XL+e

. Observe that

and

are correlated. A secret key can thus be agreed by using these outputs of the same RO

array [13,14,23,24].

One needs to extract random sequences with i.i.d. symbols from e

XLand e

YLto employ available

information-theoretic results for secret-key binding with identifiers. We propose an algorithm that

extracts nearly i.i.d. binary and uniformly distributed random vectors

XN,YN

from

and

respectively. For such

and

, we can define a binary error vector as

EN=XN⊕YN

. The random

sequence

corresponds to a sequence of i.i.d. Bernoulli random variables with parameter

i.e., EN∼Bernn(p). The channel PY|Xis thus a BSC(p).

The fuzzy commitment scheme reconstructs a secret key by using correlated random variables

without leaking any information about the secret key [

]. The fuzzy commitment scheme is depicted

Entropy 2018,20, 340 4 of 19

in Figure 1, where an encoder

Enc

embeds a secret key, uniformly distributed according to

Unif [

:|S|]

into a binary codeword

that is added modulo-2 to the binary PUF-output sequence

during

enrollment. The resulting sequence is the public helper data

, which is sent through an authenticated

and noiseless channel. The modulo-2 sum of the helper data Mand YNgives the result

RN=M⊕YN=CN⊕EN(1)

which is later mapped to an estimate ˆ

Sof the secret key by the decoder Dec during reconstruction.

CN=Enc (S)

PY|X

S=Dec RN

XNYN

Enrollment Reconstruction

Figure 1. The fuzzy commitment scheme.

Definition 1.

A secret-key vs. privacy-leakage rate pair

(Rs,Rl)

is achievable by the fuzzy commitment scheme

with perfect secrecy, i.e., zero secrecy leakage, if, given any

0, there is some

N≥

1and an encoder and decoder

for which Rs=log2|S|

Nand

Pr[S6=ˆ

S]≤e(reliability)(2)

I(S;M)=0(perfect secrecy)(3)

NIXN;M≤Rl+e(privacy). (4)

Theorem 1

([

])

The achievable secret-key vs. privacy-leakage rate region for the fuzzy commitment scheme

with a channel PY|Xthat is a BSC(p), uniformly distributed X and Y, and zero secrecy leakage is

R={(Rs,Rl): 0 ≤Rs≤1−Hb(p),Rl≥1−Rs}. (5)

The region

suggests that any (secret-key, privacy-leakage) rate pair that sums up to

1 bit/source-bit is achievable with the constraint that the secret-key rate is at most the channel capacity

of the BSC. Furthermore, smaller secret-key rates and greater privacy-leakage rates than these rates are

also achievable.

The fuzzy commitment scheme is a particular realization of the CS model. The region

Rcs

of all

achievable (secret-key, privacy-leakage) rate pairs for the CS model with a negligible secrecy-leakage

rate, where a generic encoder is used to confidentially transmit an embedded secret key to a decoder

that observes YNand the helper data M, is given in [13] as

Rcs =[

PU|X((Rs,Rl): 0 ≤Rs≤I(U;Y),Rl≥I(U;X))(6)

where

U−X−Y

forms a Markov chain and the alphabet

of the auxiliary random variable

can be limited to have the size

|U| ≤ |X | +

1. The fuzzy commitment scheme is optimal,

Entropy 2018,20, 340 5 of 19

i.e., it achieves a boundary point of

Rcs

, for a BSC

PY|X

with crossover probability

, only at the

point

(R∗

s,R∗

l)=(1−Hb(p),Hb(p)) [19]

. This point corresponds to the highest achievable secret-key

rate. Note that the region

Rcs

gives an outer bound for the perfect-secrecy case (see [

] for discussions).

3. Transform Coding Steps

The aim of transform coding is to reduce the correlations between RO outputs by using

a linear transformation. We propose a transform-coding algorithm that extends the work in [

Optimizations of the quantization and error-correction parameters to maximize the security and

reliability performance, and a simple method to decrease storage are its main steps. The output

of these post-processing steps is a bit sequence

(or its noisy version

) used in the fuzzy

commitment scheme. We consider the same post-processing steps for the enrollment and reconstruction.

The difference is that during enrollment the design parameters are chosen as a function of the source

statistics by the device manufacturer. It thus suffices to discuss only the enrollment steps. Figure 2

shows the post-processing steps that include transformation, histogram equalization, quantization,

bit assignment, and bit-sequence concatenation.

RO outputs

in an array are correlated due to, e.g., the surrounding logic [

A transform

Tr×c(·)

of size

r×c

is applied to an array of RO outputs to reduce correlations.

Decorrelation performance of a transform depends on the source statistics. We model each real-valued

output

in the transform domain, called transform coefficient, obtained from a RO-output dataset in [

]

by using the corrected Akaike information criterion (AICc) [

] and the Bayesian information criterion

(BIC) [

]. These criteria suggest that a Gaussian distribution can be fitted to each transform coefficient

for the discrete cosine transform (DCT), discrete Walsh-Hadamard transform (DWHT), discrete Haar

transform (DHT), and Karhunen-Loève transform (KLT), which are common transforms considered

in the literature for image processing, digital watermarking, etc. [

]. We use maximum-likelihood

estimation [30] to derive unbiased estimates for the parameters of Gaussian distributions.

Transform

Quant.

Concat.

Hist.

Equali.

Bit Alloc.

with

Gray Map

Post-Processing

rxc

RO Array

rxc

Figure 2. Transform-coding steps.

The histogram equalization step in Figure 2converts the probability density of the

-th coefficient

into a standard normal distribution such that

Ti=Ti−µi

σi

, where

µi

is the mean and

σi

is the

standard deviation of the

-th transform coefficient for all

1, 2,

. . .

. Quantization steps for

all transform coefficients are thus the same. Without histogram equalization, we need a different

quantizer for each transform coefficient. Therefore, the histogram equalization step reduces the

storage for the quantization steps. Transformed and equalized coefficients

are independent if

the transform

Tr×c(·)

decorrelates the RO outputs perfectly and the transform coefficients

are

jointly Gaussian. One can thus use a scalar quantizer for all coefficients without a performance

loss. We propose scalar quantizer and bit extraction methods that satisfy the security and reliability

requirements of the fuzzy commitment scheme with the independence assumption, in combination

with a correlation-thresholding approach, as discussed below.

Entropy 2018,20, 340 6 of 19

4. Quantizer and Code Designs

The aim of the post-processing steps in Figure 2is to extract a uniformly-random bit sequence

We use a quantizer

Q(·)

with quantization-interval values

1, 2,

· · ·

, 2

, where

is the number of

bits we extract from the i-th coefficient b

Tifor i=1, 2, . . . , L. We have

Q(ˆ

ti) = kif bk−1<ˆ

ti≤bk(7)

and we choose

bk=Φ−1k

2Ki

, where

Φ−1(·)

is the quantile function of the standard normal

distribution. The quantizer output

is assigned to a bit sequence of length

. The chosen permutation

of assigned bit sequences does not affect the security performance. However, the most likely error event

when we quantize

is a jump to a neighboring quantization step due to zero-mean noise. We thus

apply a Gray mapping when we assign bit sequences of length

to the integers

1, 2,

. . .

, 2

that neighboring bit sequences change only in one bit position.

We next propose two different reliability metrics for joint quantizer and code designs. The first

metric results in BSC measurements of each extracted bit with approximately the same crossover

probability. This method extracts a different number of bits from each transform coefficient. The code

design is then done for a fixed crossover probability of the BSCs. The second method fixes the

maximum number of erroneous transform coefficients and considers an error-correction code that can

correct all error patterns with up to a fixed number of errors.

4.1. Quantizer Design with Fixed Measurement Channels

Observe that with the quantizer in (7) and a Gray mapping, one can model the channel

between a bit extracted from the enrollment outputs

and the corresponding bit extracted from the

reconstruction outputs

as a BSC with a fixed average crossover probability

. Our algorithm thus

fixes an average crossover probability

such that the error-correction step in the fuzzy commitment

scheme can satisfy the maximum block-error probability of 10

−9

. The algorithm enforces that each

output

results in an average bit error probability as close as possible to, but not greater than,

adapting the number of bits

Ki(pb)

extracted from the

-th coefficient

for all

1, 2,

. . .

. We use the

average fractional Hamming distance

D(K)

between the quantization intervals assigned to the original

and noisy coefficients as a metric to determine Ki(pb). Define

Di(K)= 1

KZ∞

−∞Z∞

−∞ 2K

∑

k=1

Pr[Q(ˆ

t+ˆ

n) = k]HDk(ˆ

t)!·fb

Ti(ˆ

t)fb

Ni(ˆ

n)dˆ

tdˆ

n(8)

where

HDk(ˆ

is the Hamming distance between the bit sequences assigned to the

-th quantization

interval and to the interval

Q(ˆ

, and

represents the Gaussian noise in the

-th coefficient after

histogram equalization. We then determine

Ki(pb)

as the greatest number of bits

such that

Di(K)≤pb.

The first coefficient, i.e., DC coefficient,

is not used since its value is a scaled version of the mean

of the RO outputs in the array, which is generally known by an eavesdropper. Ambient-temperature

and supply-voltage variations have a highly-linear effect on the RO outputs, so the DC coefficient is

the most affected coefficient, which is another reason not to use the DC coefficient [

]. Therefore,

the total number N(pb)of extracted bits from all transform coefficients for a fixed pbis

N(pb) =

∑

i=2

Ki(pb). (9)

Entropy 2018,20, 340 7 of 19

We calculate the maximum secret-key length

Smax

by using (5) for a BSC

(pb)

with the maximum

secret-key rate R∗

s=1−Hb(pb)as

Smax = (1−Hb(pb)) ·N(pb)(10)

which is used to compare different transforms and to decide whether one can use an RO PUF with

fixed number of ROs and

for secret-key binding. For instance, for the advanced encryption standard

(AES), the minimum secret-key length is 128 bits. However, the rate region

in (5) is valid for large

One thus needs to consider the rate loss due to a finite block length for a system design.

4.2. Quantizer Design with Fixed Number of Errors

We now propose a conservative approach, based on the assumption that either all bits extracted

from a transform coefficient are correct or they all flip, to provide reliability guarantees. The correctness

probability

of a transform coefficient is defined to be the probability that all bits associated with

this coefficient are correct. We use this metric to determine the number of bits extracted from each

coefficient such that there is an encoder and a bounded minimum distance decoder (BMDD) that

satisfy the block-error probability constraint

PB≤

−9

. This approach results in reliability guarantees

for the random-output RO arrays.

For a

-bit quantizer and the quantization boundaries

as in (7) for an equalized (i.e., standard)

Gaussian transform coefficient ˆ

T, we obtain the correctness probability

Pc(K)=

2K−1

∑

k=0

bk+1

bk"Qbk−ˆ

σˆ

n−Qbk+1−ˆ

σˆ

n#fb

T(ˆ

t)dˆ

t(11)

where

σ2

is the noise variance and

is the probability density of the standard Gaussian distribution.

Suppose our channel decoder can correct all errors in up to

Cmax

transform coefficients.

Suppose further that coefficient errors occur independently and that the correctness probability

Pc,i(K)

of the

-th coefficient

for

1, 2,

. . .

is at least

Pc(Cmax)

. A sufficient condition for satisfying the

block-error probability constraint PB≤10−9is that Pc(Cmax)satisfies the inequality

∑

c=Cmax+1L

c(1−Pc(Cmax))cPc(Cmax)L−c≤10−9. (12)

We thus determine the number

of bits extracted from the

-th transform coefficient as the

maximum value

such that

Pc,i(K)≥¯

Pc(Cmax)

. Similar to Section 4.1, we choose

K1=

0 so that the

total number N(Cmax)of extracted bits is

N(Cmax)=

∑

i=2

Ki. (13)

In the worst case, the coefficients in error are the coefficients from which the greatest number of

bits is extracted. We sort the numbers

of bits extracted from all coefficients in descending order such

that K0

i≥K0

i+1for all i=1, 2, . . . , L−1. The channel decoder thus must be able to correct up to

e(Cmax) =

Cmax

∑

i=1

i(14)

bit errors, which can be satisfied by using a block code with minimum distance dmin ≥2e(Cmax)+1.

Suppose a key bound to physical identifiers in a device is used in the AES with

a uniformly-distributed secret-key with a length of 128 bits. The block code used in the fuzzy

Entropy 2018,20, 340 8 of 19

commitment scheme should thus have a code length of at most

N(Cmax)

bits, code dimension of

at least 128 bits, and minimum distance of

dmin ≥

e(Cmax) +

1 for a fixed

Cmax

. The code rate should

be as high as possible to operate close to the optimal (secret-key, privacy-leakage) rate point of the

fuzzy commitment scheme. This optimization problem is hard to solve. We illustrate by an exhaustive

search over a set of

Cmax

values and over a selection of algebraic codes that there is a channel code

that satisfies these constraints with a reliability guarantee for each extracted bit. Restricting our search

to codes that admit low-complexity encoders and decoders is desired for IoT applications, for which

complexity is the bottleneck.

Note that the listed conditions are conservative. For a given transform coefficient, the correctness

probability can be significantly greater than the correctness threshold

Pc(Cmax)

. Secondly, due to Gray

mapping, it is more likely that less than

bits are in error when the

-th coefficient is erroneous.

Thirdly, it is also unlikely that the bit errors always occur in the transform coefficients from which the

greatest number of bits is extracted. Therefore, even if a channel code cannot correct all error patterns

with up to

e(Cmax)

errors, it can still be the case that the block-error probability constraint is satisfied.

We illustrate such a case in the next section.

5. Performance Evaluations

Suppose the device output

is a vector random variable with the autocovariance matrix

Consider RO arrays of sizes 8

8 and 16

16. Autocovariance matrix elements of such RO array outputs

and noise are estimated from the dataset in [

]. We compare the DCT, DWHT, DHT, and KLT in terms

of their decorrelation efficiency, maximum secret-key length, complexity, uniqueness, and security.

5.1. Decorrelation Performance

One should eliminate correlations between the RO outputs and make them independent to extract

uniform bit sequences by treating each transform coefficient separately. We use the decorrelation efficiency

ηc

[

] as a decorrelation performance metric. Consider the autocovariance matrix

CTT

of the transform

coefficients, so ηcof a transform is

ηc=1−

∑

a=0

∑

b=0

|CTT(a,b)|1{a6=b}

∑

a=0

∑

b=0

|Ce

X(a,b)|1{a6=b}

(15)

where the indicator function

1{a6=b}

takes on the value 1 if

a6=b

and 0 otherwise. The decorrelation

efficiency of the KLT is 1, which is optimal [

]. We list the average decorrelation efficiency results of

other transforms in Table 1. All transforms have similar and good decorrelation efficiency performance

for the RO outputs in the dataset in [

]. The DCT and DHT have the highest efficiency for 8

8 RO

arrays, whereas for 16

16 RO arrays, the best transform is the DWHT. Table 1indicates that increasing

the array size improves ηc.

Table 1. The average RO output decorrelation-efficiency results.

DCT DWHT DHT

ηcfor 8 ×80.9978 0.9977 0.9978

ηcfor 16 ×16 0.9987 0.9988 0.9986

5.2. Maximum Secret-Key Length

The maximum number of bits extracted with the method given in Section 4.2 depends on the

fixed number of transform coefficients that are in error. Moreover, the method uses a conservative

metric. However, for the method given in Section 4.1, we can optimize the number of bits extracted

Entropy 2018,20, 340 9 of 19

from each coefficient to maximize the secret-key length. We therefore consider only the method in

Section 4.1 for maximum key-length comparisons.

The secret key

should satisfy the length constraints of the cryptographic primitives that use it.

Consider again the AES with a 128-bit secret key. We compare different transforms by calculating the

maximum secret-key lengths

Smax

, defined in (10), for various crossover probabilities

that can be

obtained by applying the post-processing steps in Figure 2. For RO array dimensions 8

8, we show

Smax

results of the considered transforms in Figure 3. For

pb≤

0.05,

R∗

is high but

N(pb)

is small,

Smax

is mainly determined by

N(pb)

, as depicted in Figure 3. For

pb≥

0.07,

N(pb)

is high but

R∗

mainly determines Smax, which is small.

0.05 0.10 0.15 0.20 0.25

100

120

140

160

180

200

220

240

Crossover probability pb

Max. Key Length Smax (bits)

DHT

DWHT

DCT

KLT

Figure 3. The maximum key lengths Smax for 8×8 RO arrays.

The DHT, DWHT, and DCT have similar

Smax

results and the KLT has worse performance

than the others, which is mainly determined by the signal-to-noise ratio (SNR) in the transform

domain. This illustrates that a transform’s

ηc

performance for the estimated RO output distribution

and its

Smax

performance for the estimated RO output and noise distributions can be different.

We determine a crossover probability range

P= [

0.05, 0.07

]

such that the secret-key length of all

transforms are close to their maximum and greater than 128. For a BSC with crossover probability

p∈ P

, we design error-correction codes such that

PB≤

−9

is satisfied. The crossover probability

range considered in [

] is

[

0.12, 0.14

]

, while 0.14 is the only value considered in [

] for the same

constraint. Considering a set of crossover values rather than a single value provides more flexibility in

designing error-correction codes. Our crossover probability range also allows us to use higher-rate

codes than the codes for the range

[

0.12, 0.14

]

since the maximum key rate

R∗

of the fuzzy commitment

scheme increases with decreasing

. The proposed transform-coding algorithm with the first quantizer

method is thus beneficial for code design due to smaller crossover probability pb.

The maximum number of extracted bits, which corresponds to

in (9), for an 8

8 RO array is

16 bits for the 1-out-of-8 masking scheme [

], 32 bits for the non-overlapping RO pairs [

], and 64 bits

for the regression-based distillers [

]. Even if one assumes no errors, i.e.,

R∗

1, for these methods,

their Smax results are much smaller than the Smax results of our algorithm, as shown in Figure 3.

5.3. Transform Complexity

We measure the complexity of a transform in terms of the number of operations required to

compute the transform and the hardware area required to implement it in a field-programmable gate

array (FPGA). We are first interested in a computational-complexity comparison for RO arrays of

Entropy 2018,20, 340 10 of 19

sizes

r=c=

8 and

r=c=

16, which are powers of 2, so that fast algorithms are available for the DCT,

DWHT, and DHT. We then present an RO PUF hardware design for the transform with the minimum

computational complexity.

The computational complexity of the KLT for

r=c=N

O(N3)

, while it is

O(N2log2N)

for the DCT and DWHT, and

O(N2)

for the DHT [

]. There are efficient implementations of the

DWHT without multiplications [

]. The DWHT is thus a good candidate for RO PUF designs for,

e.g., internet of things (IoT) applications.

We now give a reference FPGA implementation for the DWHT without multiplications to illustrate

that the hardware area occupied by the transform-coding algorithm is small and the processing time is

significantly better than previous RO PUF designs.

5.3.1. FPGA Implementation

We use a Xilinx ZC706 evaluation board with a Zynq-7000 XC7Z045 system-on-chip (SoC) to

evaluate our DWHT design. A high level overview of the design is depicted in Figure 4. The Zynq SoC

consists of an FPGA part and an ARM Cortex-A9 dual-core processor, connected with memory-mapped

AXI4 buses [

]. The ARM processor is connected to three components: the RO array, DWHT,

and quantizer. The RO array is connected via a bi-directional memory-mapped AXI bus, and the other

components are connected via AXI streaming buses [

]. We first measure RO outputs with counters,

give the counter values as input to the DWHT, and then quantize the transform coefficients to assign

bits. This is an implementation of the transform-coding algorithm given in Figure 2.

DDR

DWHT

Quantizer

m_ax

Figure 4. Hardware design overview.

We use a standard RO array of size 16

16. All ROs in a row are connected to a counter and ROs

in the same row can be measured serially by using the counter. There is an additional counter that

stops the counting operations after a specified time. For the FPGA we use, it is practically necessary to

use at least five inverters for each RO since using three inverters results in oscillation frequencies of

about 1GHz, which violates the timing constraints of the FPGA. Our RO designs with five inverters

operate reliably and give oscillation frequencies in the range

[

400, 500

]

MHz. Furthermore, we use

16-bit counters so that the minimum duration Tmin to have an overload in a counter is

Tmin =216 −1

500 MHz =131 µs. (16)

We therefore count each RO output for a duration of 100

s, which is less than

Tmin

to avoid

overloads. This results in a total counting duration of 1.6 ms for all 16 columns of the RO array, which is

compared below with the previous RO PUF designs.

Entropy 2018,20, 340 11 of 19

We next implement an extended version of the algorithm, proposed for an 8

8 array, in [

] to

calculate the two-dimensional (2D) 16

16 DWHT without multiplications. The main block we use is

the 4-point (4P)-2D DWHT [34] that takes four inputs [x0,x1,x2,x3]and calculates

"y0y1

y2y3#=1

2"x0+x1+x2+x3x0−x1+x2−x3

x0+x1−x2−x3x0−x1−x2+x3#. (17)

We successively apply the 4P-2D DWHT to the 16

16 RO array according to an extension of

the input-selection algorithm proposed in [

]. We implement a finite state machine (FSM) to control

the input and output AXI streaming interfaces as well as the input-selection algorithm. The building

blocks of our DWHT implementation is depicted in Figure 5, which includes

• a data random access memory (RAM) to store all array elements,

•

a 32-bit index read-only memory (ROM), where each word stores four 8-bit array-element

addresses,

• a multiplexer (MUX) to select the RAM address to be accessed,

• a second MUX to select the ROM input,

• a register for each input to convey different RAM words to different ports.

Control

FSM

Index

ROM

Addr

MUX

Bank

4P - 2D

DWHT Data

MUX

Data

RAM

Control Signals

Data Signals

Address Signals

en sel

sel/en sel en we

Data In

Data Out

Figure 5. Building blocks for the DWHT implementation.

We first store all RO outputs in the data RAM. Then, the first word of the index ROM is fetched.

This word holds the addresses of four array elements to be loaded. These array elements are passed

to the 4P-2D DWHT’s input registers by selecting the corresponding port in the address MUX and

[y0

y3]

are written

back to the locations from where the inputs

[x0

x3]

were fetched. The FSM performs the same

steps for all remaining ROM words and conveys the 2D DWHT coefficients to the AXI output port.

The addition and subtraction operations on four numbers in each 4P-2D DWHT evaluation

requires at most two additional bits, while the subsequent bit shift to implement the division by 2

in (17) removes one bit. Since the 4P-2D DWHT is applied in total four times to each RAM location,

the transform requires 20-bit operations and storage in order to process the 16-bit signed numbers

used for counter values.

The quantizer contains AXI stream ports, an FSM, and one ROM. The ROM holds 2

Ki−

quantization boundaries for the

-th transform coefficient. We remark that the histogram equalization

step in Figure 2is useful when the number of bits

extracted are large, but we choose

Ki=K=

1 for

all used transform coefficients, which is illustrated in combination with an error-correction code design

in Section 6.2. Therefore, we do not apply the histogram equalization step for this case, so the ROM

Entropy 2018,20, 340 12 of 19

contains 255 words and is of size 638 Bytes (

≥

255

20 bits) in total. The FSM compares the quantizer

input with the corresponding quantization boundary to assign a bit 1 for transform-coefficient values

greater than the quantization boundary, and the bit 0 otherwise. The assigned bits are then conveyed

to the output port.

5.3.2. Hardware Design Comparisons

We now compare our results with another RO PUF hardware design given in [

] in terms of

the hardware area and processing times. The number of lookup tables (LUTs), registers, and MUXs

used in [

] are not available. However, our results can be compared with their slice-count and

processing-delay results since the FPGA (Spartan-6) used in [

] also has 4 LUTs, 8 registers and

3 MUXes in each slice, the same as the FPGA used in this work. In addition, the quantizer and DWHT

clock rate is 54MHz, as in [

]. There are alternative RO PUF designs in [

], but their secret-key

lengths are smaller than 128 bits, which makes a comparison with our scheme difficult. Therefore,

we list in Table 2the hardware area occupied by individual components of our RO PUF design and by

the RO PUF design of [21].

Table 2. Hardware area and processing delays for RO PUF designs.

Blocks LUTs Registers MUXes RAM & ROM (Byte)Slices Duration (µs)

Proposed-ROs 1632 397 65 0 729 1600

Proposed-DWHT 326 200 0 1664 99 66

Proposed-Quantizer 43 39 0 638 21 14

Proposed Total (ROPUF) 2001 636 65 2302 849 1680

PUFKY Total (ROPUF) [21] n.a. n.a. n.a. n.a. 952 4611

Table 2illustrates that the RO array causes the highest hardware cost and uses approximately

82% of all occupied LUTs, 62% of registers, and 86% of slices. We do not include the area for RAMs

and ROMs, because we use Block RAM slices that are available in the FPGA. However, we include

the control logic area required to control the Block RAM slices. Our DWHT-based design occupies an

approximately 11% smaller RO PUF hardware area than the RO PUF design proposed in [

] in terms

of the number of slices used. This result can be improved if we re-use the same area for different ROs,

which might increase correlations in the RO outputs. In addition, the DWHT and quantizer constitute

approximately 14% of the total slice count of our RO PUF design. These results illustrate that the

transform-coding approach occupies a small hardware area.

The total counter duration of 1.6ms is a result of the calculation given in (16) to avoid overloads in

the counters, and the choice of this value depends mainly on the number of inverters used for each RO

and counter bit width. The overall processing time of the proposed design is approximately 1.68 ms,

which is significantly better than the processing delay of the RO PUF design in [21].

5.4. Uniqueness and Security

The bit sequence extracted from a physical identifier should consist of uniformly distributed bits

so that the rate region

in (5) is valid. A common measure, called uniqueness, for checking randomness

of a bit sequence is the average fractional Hamming distance between the bit sequences extracted

from different RO PUFs [

]. We obtain similar uniqueness results for all transforms, where the mean

Hamming distance is 0.500 and Hamming distance variance is approximately 7

−4

. All transforms

thus provide close to optimal uniqueness results due to their high decorrelation efficiencies and

equipartitioned quantization intervals. These results are significantly better than the results 0.462 [

]

and 0.473 [26].

The National Institute of Standards and Technology (NIST) provides a set of randomness tests

that check whether a bit sequence can be differentiated from a uniformly random bit sequence [

We apply these tests to evaluate the randomness of the generated sequences. We observe that the bit

Entropy 2018,20, 340 13 of 19

sequences generated from ROs in the dataset [

] with the DWHT pass most of the applicable tests for

short lengths for both reliability metrics, which is considered to be an acceptable result [

]. We also

conclude that the KLT performs the best due to its optimal decorrelation performance. One can apply

a thresholding approach such that the reliable transform coefficients from which the bits are extracted

do not have high correlations, which further improves the security performance [18].

6. Privacy and Secrecy Analysis of Proposed Error-Correction Codes

Suppose that extracted bit sequences are uniformly distributed so that the secrecy leakage is

zero. We propose different codes for the transform-coding algorithm according to the two proposed

reliability metrics.

6.1. Codes for the Quantizer Design with Fixed Measurement Channels

For the first quantizer method given in Section 4.1, fix an average crossover probability

pb=

0.06

to obtain the highest maximum secret-key length, as shown in Figure 3. We illustrate that there

are efficient error-correction codes for the fuzzy commitment scheme with

PB≤

−9

and a small

privacy-leakage rate. Recall that the code dimension has to be at least 128 bits, a requirement of the

AES, so the block length is in the short block-length regime for error-correction codes with high rates

and

128. We expect a rate loss in our code designs due to the small block-error probability constraint

and short block length. One needs finite-length bounds for the fuzzy commitment scheme, which are

not available in the literature. We thus compare the performance of our codes with the region

given

in (5). The basic approach to design codes for small block-error probabilities and reasonable decoding

complexity is to use concatenated codes. Since the hardware complexity of a code design should be

small for IoT applications, we minimize also the field sizes of the codes.

Remark 1.

It would be natural to use iterative decoders in combination with high-performance codes like low

density parity check (LDPC) and turbo codes. However, hardware complexity might increase and it is a difficult

task to simulate these codes for

PB≤

−9

. We thus use concatenated algebraic codes so that we can find

analytical bounds on PBwithout simulations for the outer code.

The first construction uses a Reed-Muller (RM) code

32, 6,16

)

as the inner code and

a Reed-Solomon (RS) code

28, 22, 7

)

that operates with symbols from the Galois field

F26

as the

outer code of a concatenated code. Every symbol of the RS code can be represented by 6 bits and the code

takes 22 symbols as input, which corresponds to 132 input bits that is greater than 128 bits. The majority

logic decoder (MLD) of the inner RM code transforms the BSC with crossover probability

pb=

0.06 into

a channel with errors and erasures by declaring an erasure if there are two codewords with equal distances

to a received vector and makes an error if a wrong codeword is selected. Simulation results show that

the erasure probability after the MLD of the inner code is about 6.57

−5

and the error probability is

about 4.54

−6

. The BMDD for the outer code correctly reconstructs the codeword if 2

×e+ν<d

where

is the number of errors and

is the number of erasures in the received vector [

]. The block-error

probability after decoding the outer RS code is approximately

PB≈

1.37

−11

. The key and leakage rates

of this code are Rs=0.1473 and Rl=0.8527 bits/source-bit, respectively.

An alternative concatenated code is a binary extended Bose-Chaudhuri-Hocquenghem

(BCH) code

256, 132, 36

)

as the outer code and a repetition code

3, 1, 3

)

as the inner

code. The maximum-likelihood decoder for the inner code transforms the BSC with crossover

probability

pb=0.06

into a BSC with

pb=

0.0104 so that the BMDD for the outer BCH code

results in

PB=3.48 ×10−10

. The key-leakage rate pair

(Rs,Rl)

for this code is

(0.1719, 0.8281)

bits/source-bit, which gives better rates than the RM+RS concatenation above and the best

generalized-concatenated-code (GCC) design with the fuzzy commitment scheme in [

] with the

key-leakage rate pair

(0.1260, 0.8740)

bits/source-bit, which is shown to be better than the previous

Entropy 2018,20, 340 14 of 19

results in [

]. The significant improvement in the rates with a low-complexity code is due to the

decrease in pbby using our transform-coding algorithm.

The fuzzy commitment scheme can asymptotically achieve the maximum secret-key rate

R∗

s=0.6726 bits/source-bit

and corresponding minimum privacy-leakage rate

R∗

l=0.3274 bits/source-bit

for a BSC

(pb=

0.06

)

. Better key-leakage rate pairs are thus possible, e.g., by using GCCs or by improving the

decoder for the outer code. However, these constructions would result in increased hardware complexity,

which is not desired for IoT applications.

6.2. Codes for the Quantizer Design with Fixed Number of Errors

We now select a channel code according to Section 4.2 to store a secret key of length 128 bits.

The correctness probabilities defined in (11) for the transform coefficients

with the three highest and

three smallest probabilities are plotted in Figure 6. The indices of the 16

16 transform coefficients

follow the order in the dataset [

], where the coefficient index at the first row and first column is 1,

and it increases columnwise up to 16 so that the second row starts with the index 17, the third row

with the index 33, etc. The most reliable transform coefficients are the low-frequency coefficients,

which are in our case at the upper-left corner of the 2D transform-coefficient array with indices such as

1, 2, 3, 17, 18, 19, 33, 34, 35. The low-frequency transform coefficients therefore have the highest SNRs for

the source and noise statistics obtained from the RO dataset in [

]. The least reliable coefficients are

observed to be spatially away from the transform coefficients at the upper-left or lower-right corners of

the 2D transform-coefficient array. These results indicate that the SNR-packing efficiency, which can be

defined similarly as the energy-packing efficiency, of a transform follows a more complicated scan order

than the classic zig-zag scan order used for the energy-packing efficiency metric [

]. Observe from

Figure 6that increasing the number of extracted bits decreases the correctness probability for all

coefficients since the quantization boundaries get closer so that errors due to noise become more likely,

i.e., the probability Pc(K)defined in (11) decreases with increasing K.

12 3 45678910

0.2

0.4

0.6

0.8

Number of Quantization Bits K

Correctness Probability Pc

Coeff. 2

Coeff. 1

Coeff. 17

Coeff. 128

Coeff. 150

Coeff. 31

Figure 6. The correctness probabilities for transform coefficients.

We fix the maximum number

Cmax

of transform coefficients

allowed to be in error and calculate

the correctness threshold

Pc(Cmax)

using (12), the total number

N(Cmax)

of extracted bits using (13),

and the number

e(Cmax)

of errors the block code should be able to correct using (14). We observe

that if

Cmax ≤

10,

Pc(Cmax)

is so large that

Pc,i(K=

)≤Pc(Cmax)

for all

. . .

. If 11

≤Cmax ≤

15,

N(Cmax)

is less than the required code dimension of 128 bits. Increasing

Cmax

results in a smaller

correctness threshold

Pc(Cmax)

so that the maximum of the number

Kmax(Cmax) = K0

1(Cmax)

of bits

extracted among the

L−

1 used coefficients increases. This approach can increase hardware complexity.

Entropy 2018,20, 340 15 of 19

We thus do not consider the cases where

Cmax >

20. Table 3shows

Pc(Cmax)

N(Cmax)

, and

e(Cmax)

for

the remaining range of Cmax values, which are used for channel-code selection.

Consider again binary (extended) BCH and RS codes, which have good minimum-distance

properties. An exhaustive search does not provide a code with dimension of at least 128 bits and

with parameters satisfying any of the

(N(Cmax)

e(Cmax))

pairs in Table 3. However, the correctness

threshold analysis leading to Table 3is conservative. We therefore choose a BCH code with parameters

as close as possible to a

(N(Cmax)

e(Cmax))

pair and then prove that even if the number

eBCH

of errors

the chosen BCH code can correct is less than

e(Cmax)

, the block-error probability constraint is satisfied.

Consider therefore the BCH code with the block length 255, code dimension 131, and a capability of

correcting all error patterns with eBCH =18 or less errors.

We now show that the proposed code satisfies the block-error probability constraint. First,

we impose the condition that exactly one bit is extracted from each coefficient, i.e.,

Ki=

1 for all

2, 3,

. . .

, so that in total

N=L−

255 bits are obtained. Note that this results in independent

bit errors

. It follows from this condition that the chosen block code should be able to correct all error

patterns with up to

20 bit errors rather than

) =

25 bit errors, which is still greater than the

error-correction capability eBCH =18 of the considered BCH code.

The block error probability

for the BCH code

255, 131, 37

)

with a BMDD corresponds to the

probability of having more than 18 errors in the codeword, i.e.,

PB=

255

∑

j=19 "∑

A∈Fj

∏

i∈A

(1−Pc,i)•∏

i∈Ac

Pc,i#(18)

where

Pc,i

is the correctness probability of the

-th transform coefficient

defined in (11) for

i=2, 3, . . . , 256, Fj

is the set of all size-

subsets of the set

{

2, 3,

. . .

, 256

}

, and

denotes the

complement of the set

. The correctness probabilities

Pc,i

are different and they represent probabilities

of independent events due to the independence assumption for the transform coefficients.

Table 3. Code-parameter constraints.

Cmax 16 17 18 19 20

Pc0.9902 0.9889 0.9875 0.9860 0.9844

Kmax 33333

N144 224 250 255 259

e18 20 21 23 25

One needs to consider

∑18

j=0(255

j)≈

1.90

different cases to calculate (18), which is not

practical. We thus use the discrete Fourier transform - characteristic function (DFT-CF) method [

] to

calculate the block-error probability and obtain the result

PB≈

1.26

−11 <

−9

. The block-error

probability constraint is thus satisfied by using the BCH code

255, 131, 37

)

with a BMDD although

the conservative analysis suggests that it would not be satisfied.

We now compare the BCH code

255, 131, 37

)

with previous codes proposed for binding keys

to physical identifiers with the fuzzy commitment scheme and a secret-key length of 128 bits such

that

PB≤

−9

is satisfied. The (secret-key, privacy-leakage) rate pair for this proposed code is

(Rs

Rl) = (131

255

, 1

−131

255 )≈(

0.514, 0.486

)

bits/source-bit. This pair is significantly better than our

previous results in Section 6.1 proposed for a BSC

(pb=

0.06

)

. The main reason for obtaining a better

(secret-key, privacy-leakage) rate pair is that the quantizer in Section 4.2 allows us to exploit higher

identifier-output reliability by decreasing the number of bits extracted from each transform coefficient.

We compare the secret-key and privacy-leakage rates of the BCH code

255, 131, 37

)

with the

region of all achievable rate pairs for the CS model and the fuzzy commitment scheme for a BSC

PY|X

with crossover probability

pb=

−1

L−1∑L

i=2Pc,i(Ki=

)≈

0.0097, i.e., the probability of being

in error averaged over all used transform coefficients with the quantizer in Section 4.2. We compute

Entropy 2018,20, 340 16 of 19

the boundary points of the region

Rcs

by using Mrs. Gerber’s lemma [

], which gives the optimal

auxiliary random variable

in (6) when

PY|X

is a BSC. We plot the regions of all rate pairs achievable

with the fuzzy commitment scheme and CS model, the maximum secret-key rate point, the (secret-key,

privacy-leakage) rate pair of the proposed code, and a finite-length bound [

] for the block length of

N=255 bits and PB=10−9in Figure 7.

The maximum secret-key rate is

R∗

s≈

0.922 bits/source-bit with a corresponding minimum

privacy-leakage rate of

R∗

l≈

0.079 bits/source-bit. There is a gap between the secret-key rate of

the proposed code and the only operation point where the fuzzy commitment scheme is optimal.

Part of this rate loss can be explained by the short block length of the code and the small block-error

probability constraint. The finite-length bound given in ([

], Theorem 52) establishes that the rate

pair

(Rs

Rl) = (

0.691, 0.309

)

bits/source-bit is achievable by using the fuzzy commitment scheme,

as depicted in Figure 7. One can therefore further improve the rate pairs by using better codes and

decoders with higher hardware complexity, but this may not be possible for IoT applications. Figure 7

also illustrates that there exist other code constructions, e.g., the WZ-coding construction in [

that reduce the privacy-leakage rate for a fixed secret-key rate.

00.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0.2

0.4

0.6

0.8

Privacy-leakage Rate Rl

Secret-key Rate Rs

Proposed Code

Fuzzy Commitment

CS Model

(R∗

l,R∗

Finite-length Bound

Figure 7.

The operation point of the proposed BCH code

255, 131, 37

)

, regions of achievable rate pairs

according to (5) and (6), the maximum secret-key rate point, and a finite-length bound for

255 bits,

PB=10−9, and BSC (0.0097).

7. Conclusions

The reliability, uniqueness, security, computational-complexity, and key-length performance of

various transforms was compared to select the best transforms for reliable secret-key binding for

RO PUFs by using the fuzzy commitment scheme. The DWHT and DHT perform best in terms of

computational-complexity, maximum key length, and reliability. All transforms give close to optimal

uniqueness and good security results. A reference hardware design with the DWHT showed that

the hardware area required by the transform-coding approach is small and less than required by

the existing RO PUF designs. Low-complexity concatenated codes with high secret-key and small

privacy-leakage rates, which are better than previous results, are proposed for a realistic block-error

probability of 10−9.

We further improved the transform-coding algorithm applied to physical identifiers by designing

quantizers with reliability guarantees. This alternative quantizer converts the block-error probability

constraint

PB≤

−9

into a constraint on the number of transform coefficients allowed to be in error.

We proposed a BCH code

255, 131, 37

)

with a higher code rate than our previously proposed codes.

Comparisons with the region of all achievable (secret-key, privacy-leakage) rate pairs for the fuzzy

Entropy 2018,20, 340 17 of 19

commitment scheme show that there is still a gap between the optimal rate pairs and the proposed

code. This gap can be closed by using other channel codes and decoders at the cost of higher hardware

complexity or by designing codes for other CS model constructions. In future work, we will apply an

extension of water-filling techniques to the transform-coefficients in order to improve the reliability

and security performance.

Author Contributions:

O.G., O.˙

I., and G.K. conceived the study; O.G., O.˙

I., T.K., and V.S. designed and

performed the experiments; All authors analyzed the data and a joint effort improved the algorithms presented;

R.F.S. contributed further analysis tools; All authors contributed to the writing of the paper.

Acknowledgments:

Onur Günlü thanks Anes Belkacem and Bernhard C. Geiger for their contributions to one

of the conference papers used in this work. Onur Günlü was supported by the German Research Foundation

(DFG) through the project HoliPUF under the grant KR3517/6-1. Vladimir Sidorenko is on leave from the Institute

for Information Transmission Problems, Russian Academy of Science. Gerhard Kramer was supported by an

Alexander von Humboldt Professorship endowed by the German Federal Ministry of Education and Research.

Conflicts of Interest: The authors declare no conflict of interest.

References

Günlü, O.; ˙

I¸scan, O.; Sidorenko, V.; Kramer, G. Reliable secret-key binding for physical unclonable functions

with transform coding. In Proceedings of the 2016 IEEE Global Conference on Signal and Information

Processing (GlobalSIP), Washington, DC, USA, 7–9 December 2016; pp. 986–991.

Günlü, O.; Belkacem, A.; Geiger, B.C. Secret-key binding to physical identifiers with reliability guarantees.

In Proceedings of the 2017 IEEE International Conference on Communications (ICC), Paris, France,

21–25 May 2017; pp. 1–6.

Suh, G.E.; Clarke, D.; Gassend, B.; Dijk, M.V.; Devadas, S. AEGIS: Architecture for tamper-evident and

tamper-resistant processing. In Proceedings of the 17th Annual International Conference on Supercomputing,

San Francisco, CA, USA, 23–26 June 2003; pp. 160–171.

Pappu, R. Physical One-Way Functions. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge,

MA, USA, 2001.

Böhm, C.; Hofer, M. Physical Unclonable Functions in Theory and Practice; Springer: New York, NY, USA, 2013.

Guajardo, J.; Kumar, S.S.; Schrijen, G.J.; Tuyls, P. FPGA intrinsic PUFs and their use for IP protection.

In Cryptographic Hardware and Embedded Systems; Paillier, P., Verbauwhede, I., Eds.; Springer-Verlag:

Berlin/Heidelberg, Germany, 2007; pp. 63–80.

Suh, G.E.; Devadas, S. Physical unclonable functions for device authentication and secret key generation.

In Proceedings of the ACM/IEEE Design Automation Conference, San Diego, CA, USA, 4–6 June 2007;

pp. 9–14.

Gassend, B. Physical Random Functions. Master’s Thesis, Massachusetts Institute of Technology, Cambridge,

MA, USA, 2003.

Dodis, Y.; Ostrovsky, R.; Reyzin, L.; Smith, A. Fuzzy extractors: How to generate strong keys from biometrics

and other noisy data. Soc. Ind. Appl. Math. J. Comp. 2008,38, 97–139. [CrossRef]

10.

Juels, A.; Wattenberg, M. A fuzzy commitment scheme. In Proceedings of the 6th ACM Conference on

Computer and Communications Security, Kent Ridge Digital Labs, Singapore, 1–4 November 1999; ACM:

New York, NY, USA, 1999; pp. 28–36.

11.

Günlü, O.; ˙

I¸scan, O.; Sidorenko, V.; Kramer, G. Wyner-Ziv coding for physical unclonable functions and

biometric secrecy systems. arXiv 2017, arxiv:1709.00275. [CrossRef]

12. Maes, R. Physically Unclonable Functions; Springer-Verlag: Berlin/Heidelberg, Germany, 2013.

13.

Ignatenko, T.; Willems, F. Biometric systems: Privacy and secrecy aspects. IEEE Trans. Inf. Forensics Secur.

2009,4, 956–973. [CrossRef]

14.

Lai, L.; Ho, S.W.; Poor, H.V. Privacy-security trade-offs in biometric security systems—Part I: Single use case.

IEEE Trans. Inf. Forensics Secur. 2011,6, 122–139. [CrossRef]

15. Günlü, O.; Kramer, G. Privacy, secrecy, and storage with noisy identifiers. arXiv 2016, arxiv:1601.06756.

16.

Günlü, O. Design and Analysis of Discrete Cosine Transform Based Ring Oscillator Physical Unclonable

Functions. Master’s Thesis, Industrial University Munich, Munich, Germany, 2013.

Entropy 2018,20, 340 18 of 19

17.

Günlü, O.; ˙

I¸scan, O. DCT based ring oscillator physical unclonable functions. In Proceedings of the

2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Florence, Italy,

4–9 May 2014; pp. 8198–8201.

18.

Günlü, O.; ˙

I¸scan, O.; Kramer, G. Reliable secret key generation from physical unclonable functions under

varying environmental conditions. In Proceedings of the 2015 IEEE International Workshop on Information

Forensics and Security (WIFS), Rome, Italy, 16–19 November 2015; pp. 1–6.

19.

Ignatenko, T.; Willems, F.M. Information leakage in fuzzy commitment schemes. IEEE Trans. Inf. Forensics Secur.

2010,5, 337–348. [CrossRef]

20.

Ignatenko, T.; Willems, F.M. Privacy-leakage codes for biometric authentication systems. In Proceedings of

the 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Florence, Italy,

4–9 May 2014; pp. 1601–1605.

21.

Maes, R.; Herrewege, A.V.; Verbauwhede, I. PUFKY: A fully functional PUF-based cryptographic key

generator. In Cryptographic Hardware and Embedded Systems; Springer-Verlag: Berlin/Heidelberg, Germany,

2012; pp. 302–319.

22.

Maiti, A.; Schaumont, P. Improved ring oscillator PUF: An FPGA-friendly secure primitive. J. Cryptol.

2011

24, 375–397. [CrossRef]

23.

Ahlswede, R.; Csiszár, I. Common randomness in information theory and cryptography—Part I:

Secret sharing. IEEE Trans. Inf. Theory 1993,3, 1121–1132. [CrossRef]

24.

Maurer, U. Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory

1993,39, 2733–2742. [CrossRef]

25.

Eiroa, S.; Baturone, I. An analysis of ring oscillator PUF behavior on FPGAs. In Proceedings of the 2011

International Conference on Field-Programmable Technology (FPT), New Delhi, India,

12–14 December 2011

;

pp. 1–4.

26.

Maiti, A.; Casarona, J.; McHale, L.; Schaumont, P. A large scale characterization of RO-PUF. In Proceedings

of the 2010 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), Anaheim, CA,

USA, 13–14 June 2010; pp. 94–99.

27.

Sugiura, N. Further analysis of the data by Akaike’s information criterion and the finite corrections.

Commun. Stat. Theory Methods 1978,7, 13–26. [CrossRef]

28. Schwarz, G. Estimating the dimension of a model. Ann. Stat. 1978,6, 461–464. [CrossRef]

29.

Wang, R. Introduction to Orthogonal Transforms: With Applications in Data Processing and Analysis; Cambridge

University Press: Cambridge, UK, 2012.

30. Bishop, C.M. Pattern Recognition and Machine Learning; Springer: New York, NY, USA, 2006; Volume 1.

31. Ohm, J.R. Multimedia Signal Coding and Transmission; Springer-Verlag: Berlin/Heidelberg, Germany, 2015.

32.

Puchinger, S.; Mueelich, S.; Bossert, M.; Hiller, M.; Sigl, G. On error correction for physical unclonable

functions. In Proceedings of the 10th International ITG Conference on Systems, Communications and

Coding, Hamburg, Germany, 2–5 February 2015; pp. 1–6.

33.

Yin, C.E.; Qu, G. Improving PUF security with regression-based distiller. In Proceedings of the 2013 50th

ACM/EDAC/IEEE Design Automation Conference (DAC), Austin, TX, USA, 29 May–7 June 2013; pp. 1–6.

34.

Komatsu, K.; Sezaki, K. Lossless 2D discrete Walsh-Hadamard transform. In Proceedings of the 2001

IEEE International Conference on Acoustics, Speech, and Signal Processing, Salt Lake City, UT, USA,

7–11 May 2001; Volume 3, pp. 1917–1920.

35.

AMBA AXI and ACE Protocol Specification AXI3, AXI4, AXI5, ACE and ACE5. 2017. Available online:

developer.arm.com/docs/ihi0022/latest/amba-axi-and-ace-protocol-specification-axi3-axi4-axi5-ace-

and-ace5 (accessed on 17 April 2018).

36.

AMBA AXI4-Stream Protocol Specification v1.0. 2010. Available online: https://developer.arm.com/docs/

ihi0051/latest/amba-axi4-stream-protocol-specification-v10 (accessed on 17 April 2018).

37.

Sahoo, D.P.; Mukhopadhyay, D.; Chakraborty, R.S. Design of low area-overhead ring oscillator PUF with

large challenge space. In Proceedings of the 2013 International Conference on Reconfigurable Computing

and FPGAs (ReConFig), Cancun, Mexico, 9–11 December 2013; pp. 1–6.

38.

Parrilla, L.; Castillo, E.; Morales, D.P.; García, A. Hardware activation by means of PUFs and elliptic curve

cryptography in field-programmable devices. Electronics 2016,5, 5. [CrossRef]

Entropy 2018,20, 340 19 of 19

39.

Bassham, L.E.; Rukhin, A.L.; Soto, J.; Nechvatal, J.R.; Smid, M.E.; Barker, E.B.; Leigh, S.D.; Levenson, M.;

Vangel, M.; Banks, D.L.; et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for

Cryptographic Applications; Technical Report; National Institute of Standards and Technology: Gaithersburg,

MD, USA, 2010. Available online: https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final

(accessed on 17 April 2018).

40. Lin, S.; Costello, D.J. Error Control Coding; Prentice-Hall: Englewood Cliffs, NJ, USA, 2004.

41. Chen, W.H.; Pratt, W. Scene adaptive coder. IEEE Trans. Commun. 1984,32, 225–232. [CrossRef]

42.

Hong, Y. On Computing the Distribution Function for the Sum of Independent and Nonidentical Random Indicators;

Technical Report; Department of Statistics, Virginia Tech: Blacksburg, VA, USA, 2011.

43.

Wyner, A.D.; Ziv, J. A theorem on the entropy of certain binary sequences and applications: Part I. IEEE Trans.

Inf. Theory 1973,19, 769–772. [CrossRef]

44.

Polyanskiy, Y.; Poor, H.V.; Verdú, S. Channel coding rate in the finite blocklength regime. IEEE Trans.

Inf. Theory 2010,56, 2307–2359. [CrossRef]

2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access

article distributed under the terms and conditions of the Creative Commons Attribution

(CC BY) license (http://creativecommons.org/licenses/by/4.0/).