Using Convolutional Codes for Key Extraction in
SRAM Physical Unclonable Functions
Sven Müelich∗ , Sven Puchinger∗, Martin Bossert∗

arXiv:1704.01306v2 [] 10 Jan 2018

∗

Ulm University, Institute of Communications Engineering, 89081 Ulm, Germany
Email: {sven.mueelich, sven.puchinger, martin.bossert}@uni-ulm.de

Abstract—Physical Unclonable Functions (PUFs) exploit variations in the manufacturing process to derive bit sequences from
integrated circuits, which can be used as secure cryptographic
keys. Instead of storing the keys in an insecure, non-volatile memory, they can be reproduced when needed. Since the reproduced
sequences are not stable due to physical reasons, error correction
must be applied. Recently, convolutional codes were shown to be
suitable for key reproduction in PUFs based on SRAM. This
work shows how to further decrease the reconstruction failure
probability and PUF implementation size using codes with larger
memory length and decoding concepts such as soft-information
and list decoding.
Index Terms—Physical Unclonable Functions, Key Generation
and Storage, Convolutional Codes, Sequential Decoding

I. M OTIVATION

AND

P RELIMINARY W ORK

Generating cryptographic keys by using Pseudo Random
Number Generators (PRNGs) and storing them in non-volatile
memory has several drawbacks. First, PRNGs do not provide
true randomness and hence violate the demand for unique
and unpredictable keys. Second, storing keys makes them
vulnerable to physical attacks and hence requires expensive
protecting mechanisms which need additional chip area and
power consumption. Physical Unclonable Functions (PUFs)
are devices which extract unique cryptographic keys from intrinsic randomness like delay characteristics of digital circuits
or initialization behavior of memory cells. All devices (even
with the same functionality) differ regarding this intrinsic
randomness, which is unique for each device and cannot be
controlled during the manufacturing process due to technical
and physical limitations. A PUF uses this randomness to
extract a random, unique and unpredictable sequence of bits
which can be used as cryptographic key. Since the randomness
is reproducible, the key can simply be regenerated when
needed instead of storing it permanently. Hence, PUFs implement secure key generation and secure key storage.
Since derived bit sequences suffer from environmental conditions like temperature or voltage supply, responses may
vary slightly. To circumvent this problem, error-correcting
codes have to be used. Therefore, the initial PUF response
is used to obtain helper data, which is needed for reliable
key reproduction. Since enough uncertainty remains when
knowing the helper data, a protected memory is not required.
Extraction of helper data and using them to reproduce a key
can be done by different helper data schemes, cf. [1], [2], [3],
[4].

Previous work most often used concatenated schemes for
error correction. [5] suggested different ordinary concatenated
schemes consisting of a repetition code as inner code and
BCH, Reed–Muller and Golay Codes respectively as outer
code. [6] applied an ordinary code concatenation consisting
of a BCH and a repetition code. Generalized concatenated
codes were applied for the first time to PUFs in [7] using
Reed–Muller codes, while a similar construction using BCH
and Reed–Solomon codes was given in [8].
In [3], convolutional codes were used the first time for
error correction in PUFs. Decoding was performed using a
hard-decision Viterbi algorithm. As channel model, a binary
symmetric channel (BSC) with variable crossover probabilities
pi was assumed, where pi corresponds to the probability of
a bit flip in the i-th SRAM cell. In order to increase the key
reproduction reliability, unreliable SRAM cells were ignored,
i.e., for a given threshold pT , only cells with pi < pT were
used, resulting in an implementation overhead.
In [9] the decoding failure rate was further decreased using
an estimator for the decoding output reliability (simplified
ROVA) in combination with multiple readouts.
In this paper, we show that using full soft information at
the Viterbi decoder’s input, the decoding failure rate can be
reduced significantly in the considered scenario.1 Furthermore,
more unreliable bit positions can be included without losing
error correction capability compared to [3], [9]. Thus, the
decoding overhead vanishes. We show, that the use of list
decoding further improves the scheme in terms of failure
probability and provides decoding reliability for free as an
alternative to simplified ROVA. Also, the combination of list
decoding and multiple readouts can improve the results of [9].
Our simulations indicate that convolutional codes with
larger memory length result in smaller failure probabilities,
which is a well-known fact in coding theory. In order to make
decoding of codes with a memory length up to 25 feasible,
we apply sequential decoding. To our knowledge, sequential
decoding is applied to the PUF scenario for the first time.

1 Full soft information at the decoder’s input was used for the first time
in [10]. However, instead of convolutional codes and Viterbi algorithm, a
concatenation of short block codes was used. The use of convolutional codes
was labeled inefficient without further study, due to apparently required very
long code sequences. In contrast to that statement, [3], [9] as well as our
analysis show that sufficiently short length can be achieved.

II. P HYSICAL U NCLONABLE F UNCTIONS (PUF S )
There is a variety of ways to realize PUFs. In this work
we mainly focus on SRAM PUFs which were introduced
in [11]. Dependent on the mismatch of two inverters of an
SRAM cell (which is caused by manufacturing variations) and
electrical noise, every SRAM cell converges to either 0 or 1
when powering-up the device. Since the mismatch is static
and dominates over the noise, most cells always power-up
with either 0 or 1. However, some of the cells do not have
a preferred behavior and hence sometimes initialize with 0
and sometimes with 1. It is possible to produce reliability
information of the individual cells by obtaining statistics
during an enrollment phase. Based on such statistics, [12]
derived a cumulative density function (cdf) and a probability
density function (pdf) which approximate the measured oneprobability Pone of SRAM cells:
cdf Pone (x) = Φ(λ1 · Φ−1 (x) − λ2 )
pdf Pone (x) =

λ1 · ϕ(λ2 − λ1 · Φ
ϕ(Φ−1 (x))

−1

(x))

(1)
(2)

In Equations (1)–(2), Φ denotes the standard normal cumulative distribution function. For these functions we use
λ1 = 0.51 and λ2 = 0 according to [12], in order to obtain a
model which is equivalent to a BSC with crossover probability
p = 0.15, which is often used in the PUF scenario. [12] also
derived a cumulative density function and a probability density
function of the error probability Pe of an SRAM cell:
cdf Pe (x) = cdf Pone (x) + 1 − cdf Pone (1 − x)
(
pdf Pone (x) + pdf Pone (1 − x) , if x < 0.5,
pdf Pe (x) =
0
, otherwise.

cf. Figure 1 for a (2, 1, [2]) encoder with G0 = (1, 1),
G1 = (1, 0), G2 = (1, 1). Initially, all memory elements
contain zeros. Information block ir is mapped to codeword
cr,1 cr,2 by applying linear operations. Then all bits move one
memory element to the right. Bit ir enters the leftmost memory
element, bit ir−2 is dropped. Encoding continues with block
ir+1 .
cr,1
ir

Fig. 1. Encoder of a (2, 1, [2]) convolutional code.

B. Viterbi Algorithm
The Viterbi algorithm realizes efficient maximum-likelihood
decoding [17]. We can visualize decoding using a graph
structure called trellis (cf. Figure 2 for the trellis of the
(2, 1, [2]) code introduced in Section III-A). The nodes in the
trellis represent the 2µ states of the shift register. Each node
has two outgoing edges for encoding a 0 (dashed lines) or a 1
(solid lines). Since the register is initialized with zeros, not all
states occur in the beginning. The edges are labeled with the
corresponding codeword and represent the transitions to the
next memory state. Hence, each path in the trellis represents a
possible code sequence c. The decoder aims to find the code
sequence which was transmitted with highest probability when
the sequence y was received, hence it maximizes p(y|c).
00

00

00

00

00

00

11
10

11
10

11

10

11
10
01
11

01
11

01

11

01

00
01

00
01

10

10

00
01

Convolutional codes, introduced by Elias [13], are widely
used in applications. Efficient methods for implementations
in hardware make them suited for PUFs. [3] applied convolutional codes to PUFs for the first time. An optimized
FPGA Viterbi decoder adapted to PUFs was designed in [14].
We explain encoding and decoding briefly, for a detailed
description of convolutional codes we refer to [15], [16].

10

Convolutional codes can be described using the parameters
(n, k, [µ]). Using a code of rate nk , we partition an information
sequence into blocks of length k. Each information block is
mapped to a codeword of length n > k. In contrast to block
codes, the codeword cr depends on information block ir and
on the µ previous information blocks ir−1 , . . . , ir−µ .
Encoding of an information block can be done by calculating cr = ir G0 + ir−1 G1 + . . . ir−µ Gµ , or equivalently
cr = (ir , ir−1 , . . . ir−µ ) · (GT0 , GT1 , . . . , GTµ )T , using (k × n)
generator matrices G0 , G1 , . . . , Gµ . This process can be implemented by using a linear shift register for each of the k
inputs, n outputs and µ memory elements per shift register,

ir-2

cr,2

III. C ONVOLUTIONAL C ODES

A. Description and Encoding

ir-1

11

11

Fig. 2. Trellis diagram for decoding a (2, 1, [2]) code.

Let c = (c1 , c2 , . . . ) denote the code sequence which is sent
over a noisy channel, ci denotes a length-n block. Analog to
this notation, y denotes the received sequence. We define a
submetric and a metric.
Definition 1. For every edge, the submetric is defined as
(
pi
, yi 6= cj
.
λi = p(yi |ci ) =
1 − p i , y i = ci
where distH (ci , yi ) denotes the Hamming distance of codeword ci and received word yi . The metric of a P
node is the
η
sum over all η submetrics λi on a path, i.e. Λ = i=1 λi .

Viterbi calculates the metric for all nodes in the trellis. To
calculate the metric for a specific node, for each incoming
edge Viterbi adds the incoming submetric to the metric of the
corresponding node on the left side of the segment. Viterbi

C. Sequential Decoding
Viterbi’s algorithm provides maximum-likelihood decoding.
However, its complexity grows exponentially when increasing µ. In this section we briefly discuss sequential decoding, introduced in [19]. Since for this class of algorithms,
complexity does not depend on the constraint length, larger
constraint lengths can be used. Sequential decoding is a almost
maximum-likelihood decoding and can easily be implemented.
A further advantage in comparison to Viterbi is a runtime
depending on the number of errors in the received sequence.
There exist different algorithms to realize sequential decoding,
e.g. ZJ [20], [21] and Fano [22]. We decided to use the Fano
algorithm which is suitable for hardware implementations,
since it requires essentially no memory [16, Chapter 6] and
hence is a reasonable choice for the PUF scenario. Compared
to ZJ, the complexity of the Fano algorithm is slightly higher.
However, the higher complexity is only relevant in cases where
many errors occur, since Fano backtracks more often than
in cases with fewer errors. For a small number of errors,
ZJ is practically not faster, since it uses a stack which must
be maintained during the decoding is performed. The Fano
algorithm is said to be the most practical sequential decoding
algorithm [16, Section 6.10].
Sequential Decoding belongs to the class of backtracking
algorithms which perform a depth first search in a tree. The
Fano algorithm traverses the code tree from the root until a
leaf node is reached. At each node, the algorithm can move
either to one of its child nodes, or to its root. The decision
is based on the Fano metric: The bit metric for a BSC with
crossover probability pi and rate R is given by
(
log2 2pi − R
if yi 6= ci ,
M (yi |ci ) =
(3)
log2 2(1 − pi ) − R if yi = ci .
The metric of a new node is calculated by adding the metric
of the corresponding edge to the metric of the current node.

1
relative number of ignored bits

stores the maximum reached metric for the node as its metric
and adds the edge which contributes to this metric to its
survivor path. To circumvent error propagation, often m tail
bits are inserted after L information bits to reset the register
(cf. Figure 2, segments 5 and 6). The bold path in Figure 2
is the survivor, which gives us c with p(y|c) maximized. The
complexity of Viterbi increases exponentially in µ and k, and
linearly in the number of info bits.
There is also a list decoding variant by [18]. Using this
modification of the Viterbi algorithm, each node stores the
difference between the metric of the survivor and the second
best path in addition to the metric. When the maximum
likelihood path was determined, the minimum of the metric
differences of all nodes on the ML path is selected, since the
most unreliable decision was taken at the corresponding node.
At that node, we take the non-surviving edge to differ from the
surviving path, and follow the second path backwards until it
merges again with the survivor path. By recursively applying
this decision process, we can generate the L most likely code
sequences.

0.8
0.6
0.4
0.2
0

0

0.1

0.2

0.3

0.4

0.5

pT
Fig. 3. Relative number of ignored bits for a given threshold pT

In each iteration, the algorithm examines which of the child
nodes of the current node maximizes the metric (3), moves to
that node and updates the metric. This process continues, until
the metric falls below a threshold T , what happens when it
becomes unlikely that the correct path was chosen. In that case,
the next best path starting at the current node is examined.
If all paths beginning at the current node are examined and
the metric becomes lower than the threshold in all cases,
the algorithm backtracks to the previous level. If the metric
value of that preceding node also is below the threshold, the
threshold is decreased by a threshold increment ∆. Every time
a node is visited the first time, the threshold is increased by
the maximum multiple of ∆ such that the metric value is still
larger than the threshold.
More information about sequential decoding with full length
examples can be found in [15, Chapter 13].
IV. S ETUP

AND

R ESULTS

In a first approach we extract t bits from a PUF. Using the
model described in Section IV-B, each of these t bits can be
modeled as a BSC with crossover probability pi (i = 1, ..., t).
We select s ≤ t Bits ri (i = 1, ..., s) which belong to BSCs
with crossover probabilities pi < pT , where pT is a chosen
threshold. Thus, unreliable PUF bits are ignored.
In a second step, we replace Viterbi by Fano algorithm,
which is a sequential decoding approach, in order to gain
performance for codes with large constraint lengths.
Figure 3 shows the amount of wasted bits in our first
approach. In a third step we use all extracted bits without
refusing the unreliable ones. Our goal is to study, whether
the good channels compensate the bad ones when using soft
information at the input of the decoder. For a fair comparison
we have to adjust the code rate for this scenario.
A. Coding Theoretical Concepts
Instead of using the SRAM reliability information only
for choosing reliable bits from the PUF response, we can
additionally translate them into soft information which can

to further improve the results. For our experiments we used
information sequences of length 256 and responses of length
512 + µ. We want to emphasize, that in contrast to [9] we do
not use ROVA.

TABLE I
C ONVOLUTIONAL CODES USED IN THIS WORK .
k
1
1
1
1
1
1
1
1
1
1
1

n
2
2
2
2
2
2
3
3
3
3
3

µ
2
6
7
10
14
16
6
7
8
9
10

polynomials used (in octal)
g2
g1
g0
5
7
133
171
247
371
3645
2671
63057
44735
313327
231721
133
165
171
225
331
367
557
663
711
1117
1365
1633
2353
2671
3175

1) Full Soft Information: In a first experiment, we use the
same scenario as in [9], using thresholds pT ∈ {0.3, 0.2, 0.1}.
Instead of hard decision decoding, we use full soft information
at the input of the Viterbi algorithm.

be used at the input of Viterbi’s algorithm to improve the
decoding results. We calculate soft information
(j)

si

(j)

= (−1)hi ⊕ri · (log(1 − pei ) − log(pei ))

(4)

for cell i at time instance j, where ri is the i-th response
bit and pei is the error probability of SRAM cell i. This
formula is already given in [12], however the authors use
short linear block codes with soft decision decoding instead of
convolutional codes. We obtain pei for all cells i by using the
model described in Section II. In a practical scenario, the soft
information can be obtained during the enrollment phase by
doing multiple measurements for every individual PUF[12],
[10]. A technique how to obtain soft information from one
single measurement was described in [23].
The simplified ROVA used in [9], has the drawback, that it
calculates error probabilities for each symbol in order to compute the total error probability for the whole code sequence.
As alternative to the calculation of error probabilities, we use a
list decoding variant of the Viterbi algorithm according to [18],
which determines the L most reliable paths. After computing
a list, we can obtain reliability values by calculating
n
Y
p(ci |r)
p(r|ci )
qi
=
, where p(ci |r) =
p(r|cj )
p(cj |r)
i=1
(
pi
, ri 6= ci
and qi =
.
1 − pi , ri = ci

(5)
(6)

for all candidate solutions ci , cj and hence decide for the most
likely code sequence.
Table I lists all convolutional codes used within this work.
Length of the used information sequence is 256 Bits with
termination.
B. Simulation Results
The results presented in this section are based on the
SRAM model introduced in [12] and discussed in Section II.
We perform simulations to compare our ideas to the results
in [9]. According to [9], we aim for an error probability
in the order of 10−6 . For comparability we use (2, 1, [6])
and (2, 1, [7]) convolutional codes. Additionally, we use rate
1
2 convolutional codes with memory length 10, 14, and 16

The results in Table II show, that using soft information as
input results in smaller error probabilities compared to [9].
This becomes clear when comparing Column 4 and Column 7
in Table II. E.g., using a (2,1,[7]) code with pT = 0.1, [9]
achieved Perr = 4.86·10−3, using full soft information results
in Perr = 7.63 · 10−4 .
2) Full Soft Information and List Decoding: Applying list
decoding allows to increase pT without loss. This can be seen
when studying for example the (2,1,[6]) code in Table II. In
[9] a key error probability of 1.08 · 10−2 was obtained using
pT = 0.1. Using list decoding with list size L = 4 results
in a key error probability of the same order, however we can
increase pT to 0.2. Since more PUF bits can be used for the
key, we can save 13 of the extracted bits, as can be seen in
Figure 3.
3) Additional Use of Multiple Readouts: The goal in this
section is to further decrease the error probabilities gained in
Section IV-B2, by additionally using multiple readouts as done
in [9]. Table III presents the error probabilities obtained from
simulations with list size L and using m readouts. Applying
multiple readouts results in an essential improvement. For
example, considering a (2,1,[6]) code with p = 0.1, using full
soft information with list size 3 and m readouts is as good as
using m+ 1 readouts in [9]. We can also use the same number
of multiple readouts as in [9] and do not use list decoding to
result in the desired error probability 10−6 . For convolutional
codes with larger memory lengths, pT can be larger in order
to achieve Perr ≈ 10−6 .
Figure 4 compares the key error probability of the (2,1,[6])
code from [9] with our soft information input and list decoding
approach for different values of pT . Note that the threshold
measure used in [9], pmax , is specific for the Differential Sequence Coding (DSC) scheme implemented in that reference,
and hence is translated to pT in our tables. Figure 5 compares
convolutional codes with different memory length, using soft
information input, list size 3 and multiple readouts.
4) Sequential Decoding: Our results using the Viterbi algorithm show that the error probability depends on the memory
length, which is a well-known fact in coding theory. As
indicated by the tables, to reach an error probability of 10−6 ,
a comparably large memory length is needed. However, the
complexity of the Viterbi decoder depends exponentially on
the memory and becomes infeasible for µ ≈ 20 in case of
k = 1 and even lower values for k > 1. This drawback can
be circumvented by using sequential decoding as discussed in
Section III-C. Table IV shows our results.

U SING RATE

TABLE II
C OMPARISON OF [9] WITH HARD DECISION DECODING (HD) AND SOFT DECISION DECODING (SD), USED WITH LIST SIZE L.
E XTR . MEANS THE NUMBER OF SIMULATED KEY EXTRACTIONS . ∗ ONLY 500.000 EXTRACTIONS WERE USED IN [9].

1
CODES .
2

Code
(2,1,[6])

pT
0.3
0.2
0.1
0.3
0.2
0.1
0.3
0.2
0.1
0.3
0.2
0.1
0.3
0.2
0.1

(2,1,[7])
(2,1,[10])
(2,1,[14])
(2,1,[16])

Extractions
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000
500.000
500.000
500.000
500.000
500.000
500.000

Ref.[9]
4.11e-01∗
6.98e-02∗
≤1.98e-02
–
–
≤4.86e-03
–
–
–
–
–
–
–
–
–

HD, L = 3
6.72e-01
1.83e-01
1.04e-02
4.98e-01
8.37e-02
2.68e-03
3.05e-01
2.66e-02
3.20e-04
1.20e-01
3.37e-03
1.60e-05
1.56e-03
<2e-06
<2e-06

HD, L = 4
6.66e-01
1.80e-01
1.02e-02
4.91e-01
8.18e-02
2.62e-03
2.98e-01
2.57e-02
3.09e-04
1.16e-01
3.24e-03
1.60e-05
1.5e-03
1.5e-03
<2e-06

SD, L = 1
1.86e-01
3.62e-02
2.15e-03
1.18e-01
1.80e-02
7.63e-04
2.97e-02
2.28e-03
3.90e-05
4.17e-03
8.60e-05
<2e-06
2.00e-05
<2e-06
<2e-06

SD, L = 3
1.29e-01
2.09e-02
1.09e-03
7.92e-02
1.01e-02
3.80e-04
1.85e-02
1.21e-03
1.80e-05
2.54e-03
4.20e-05
<2e-06
<2e-06
<2e-06
<2e-06

SD, L = 4
1.27e-01
2.05e-02
1.07e-03
7.74e-02
9.90e-03
3.73e-04
1.79e-02
1.17e-03
1.80e-05
2.45e-03
4.00e-05
<2e-06
<2e-06
<2e-06
<2e-06

TABLE III
A DDING THE CONCEPT OF USING m READOUTS TO THE TECHNIQUES OF SOFT INFORMATION AND LIST DECODING . U SING RATE
Code

pT

Extractions

(2,1,[6])

0.3

500.000
10.000.000
500.000
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000

0.2
0.1
0.3
0.2
0.1
0.3
0.2
0.1

(2,1,[7])
(2,1,[10])

Ref.[9]
m=1
4.11e-01
–
4.11e-01
–
≤1.98e-02
–
–
≤4.86e-03
–
–
–

Ref.[9]
m=3
–
–
–
–
7.6e-07
–
–
<1e-07
–
–
–

HD, L = 3
m=3
6.32e-01
6.32e-01
1.84e-01
1.84e-01
3.27e-02
4.89e-01
1.05e-01
2.66e-02
3.25e-01
6.43e-02
3.98e-02

SD, L = 1,
m=3
7.81e-03
7.86e-03
5.40e-05
6.10e-05
<1e-07
2.19e-03
8.00e-06
<1e-07
4.70e-05
<1e-07
<1e-07

SD, L = 3,
m=2
3.58e-02
3.59e-02
1.35e-03
1.36e-03
6.00e-06
1.49e-02
3.44e-04
1.00e-06
1.02e-03
5.00e-06
<1e-07

1
CODES .
2

SD, L = 3,
m=3
4.93e-03
4.91e-03
3.40e-05
3.20e-05
<1e-07
1.32e-03
4.00e-06
<1e-07
2.85e-04
<1e-07
<1e-07

100

100

10-1
10-1

key error probability

key error probability

10-2
10-2

10

-3

10-4

10-4
10-5
10-6

10-5

10-6
0.3

10-3

0.28

0.26

0.24

0.22

0.2

0.18

0.16

0.14

0.12

0.1

10-7
0.3

0.28

0.26

0.24

0.22

0.2

0.18

0.16

0.14

0.12

0.1

Fig. 4. (2, 1, [6]) code with soft information at the input, list decoding, and
m readouts.

Fig. 5. Comparison of convolutional codes with different memory lengths,
soft input information, list decoding with list size L, and m readouts.

TABLE IV
P ERFORMANCE OF SEQUENTIAL DECODING USING FANO ’ S A LGORITHM
WITH SOFT INFORMATION INPUT, L = 1, AND pT = 0.3

5) Without Refusing Unreliable Bits: A drawback of the
approaches described so far is, that not all response bits are
used. Hence more bits than needed have to be extracted from
the PUF, what can be time- and area-consuming (cf. Figure 3).

Code
(2,1,[16])
(2,1,[20])
(2,1,[24])

Extractions
10.000.000
10.000.000
10.000.000

SD2
∼ 10−5
∼ 10−6
∼ 10−7

2 Due to time restrictions, the numbers in the table are estimations based
on simulations with similar parameters. Simulations will have finished until
the final deadline and numbers in the table will be replaced.

A PPLYING A

TABLE V

1

RATE 3 CONVOLUTIONAL CODE , USING ALL RESPONSE BITS , EVEN THE UNRELIABLE ONES . T HE PARAMETERS µ, L, m DENOTE MEMORY
LENGTH , LIST SIZE AND NUMBER OF READOUTS RESPECTIVELY.

Code
(3,1,[6])
(3,1,[7])
(3,1,[8])
(3,1,[9])
(3,1,[10])

Extractions
10.000.000
10.000.000
10.000.000
10.000.000
10.000.000

SD, L = 1
3.98e-02
1.73e-02
9.72e-03
5.07e-03
2.30e-03

HD, L = 3
6.59e-01
5.93e-01
5.09e-01
4.28e-01
3.39e-01

Instead of refusing response bits with an error probability
higher than a certain threshold pT , we can use all response bits
and use their reliability information as soft input to a Viterbi
decoder. The idea is, that the soft information of reliable
bits compensates unreliable bits. As seen in Figure 3, using
pT ≈ 0.2 results in ≈ 13 of ignored bits. For a fair comparison
with [9], we therefore use rate 31 instead of rate 12 codes.
The results in Table V show that this method significantly
improves the previous approaches. This is obvious by comparing the columns “SD, L = 1” in Tables II and V. For
example we can realize, that the results for (2,1,[6]), (2,1,[7]),
and (2,1,[10]) for pT = 0.2 in Table II coincide with the
corresponding results in Table V. We want to emphasize, that
this implies advantages to the previous results. First, we do
not ignore extracted PUF bits, second, ROVA can be avoided.
V. C ONCLUSION
This work studied how previous approaches that use convolutional codes for PUFs can be improved by using soft
information, list decoding and sequential decoding. Our results
show that the selection of reliable bits from a PUF response
is not needed. Reliability values of the individual response
bits are translated into soft information which is used at
the input of Viterbi. Using these soft information, reliable
channels compensate unreliable ones. A rate 31 convolutional
code of memory length 7 is sufficient in order to result in
a key error probability of order 10−6 . The obtained error
probabilities can further be decreased by increasing memory
length or using a larger list size for list decoding. Using a
convolutional code with more than 8 memory elements, the
error probability becomes smaller than 10−7 . Using sequential
decoding decreases decoding complexity when using codes
with large memory length. To summarize, our strategy has
two advantages compared to previous approaches. First, all
response bits are used. Second, we avoid overhead since our
work does not require ROVA.
R EFERENCES
[1] J.-P. Linnartz and P. Tuyls, “New Shielding Functions to Enhance
Privacy and Prevent Misuse of Biometric Templates,” in Audio- and
Video-based Biometric Person Auth. Springer, 2003, pp. 393–402.
[2] Y. Dodis, L. Reyzin, and A. Smith, “Fuzzy Extractors: How to Generate
Strong Keys from Biometrics and other Noisy Data,” in Advances in
Cryptology-Eurocrypt. Springer, 2004, pp. 523–540.

SD, L = 3
2.24e-02
9.43e-03
5.14e-03
2.65e-03
1.17e-03

SD, L = 3, m = 3
5.70e-05
6.00e-06
1.00e-06
<1e-07
<1e-07

[3] M. Hiller, M. Weiner, L. Rodrigues Lima, M. Birkner, and G. Sigl,
“Breaking Through Fixed PUF Block Limitations with Differential
Sequence Coding and Convolutional Codes,” in TrustED. ACM, 2013,
pp. 43–54.
[4] S. Müelich and M. Bossert, “A New Error Correction Scheme for
Physical Unclonable Functions,” in ITG SCC, 2017.
[5] C. Bösch, J. Guajardo, A.-R. Sadeghi, J. Shokrollahi, and P. Tuyls,
“Efficient helper data key extractor on fpgas,” Cryptographic Hardware
and Embedded Systems–CHES 2008, pp. 181–197, 2008.
[6] R. Maes, A. Van Herrewege, and I. Verbauwhede, “Pufky: A fully functional puf-based cryptographic key generator,” Cryptographic Hardware
and Embedded Systems–CHES 2012, pp. 302–319, 2012.
[7] S. Müelich, S. Puchinger, M. Bossert, M. Hiller, and G. Sigl, “Error
correction for physical unclonable functions using generalized concatenated codes,” Int. Workshop on Algebraic and Combinatorial Coding
Theory, 2014.
[8] S. Puchinger, S. Müelich, M. Bossert, M. Hiller, and G. Sigl, “On
error correction for physical unclonable functions,” in SCC 2015; 10th
International ITG Conference on Systems, Communications and Coding;
Proceedings of. VDE, 2015, pp. 1–6.
[9] M. Hiller, A. G. Önalan, G. Sigl, and M. Bossert, “Online Reliability
Testing for PUF Key Derivation,” in Proc. of the 6th Int. Workshop on
Trustworthy Embedded Devices. ACM, 2016, pp. 15–22.
[10] R. Maes, P. Tuyls, and I. Verbauwhede, “Low-overhead implementation
of a soft decision helper data algorithm for sram pufs.” in CHES, vol. 9.
Springer, 2009, pp. 332–347.
[11] J. Guajardo, S. S. Kumar, G.-J. Schrijen, and P. Tuyls, “FPGA Intrinsic
PUFs and their Use for IP Protection,” in CHES. Springer, 2007, pp.
63–80.
[12] R. Maes, P. Tuyls, and I. Verbauwhede, “A Soft Decision Helper Data
Algorithm for SRAM PUFs,” in IEEE ISIT. IEEE, 2009, pp. 2101–
2105.
[13] P. Elias, “Coding for Noisy Channels,” in Proceedings of the Institute
of Radio Engineers, no. 3, 1955, pp. 37–46.
[14] M. Hiller, L. R. Lima, and G. Sigl, “Seesaw: An Area-Optimized FPGA
Viterbi Decoder for PUFs,” in 17th Euromicro Conference on Digital
System Design. IEEE, 2014, pp. 387–393.
[15] D. Costello and S. Lin, “Error Control Coding,” New Jersey, 2004.
[16] R. Johannesson and K. Zigangirov, “Fundamentals of Convolutional
Codes,” 1999.
[17] A. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,” IEEE Transactions on Information
Theory, vol. 13, no. 2, pp. 260–269, 1967.
[18] G. Schmidt, V. Sidorenko, V. V. Zyablov, and M. Bossert, “Finding a
List of Best Paths in a Trellis,” in IEEE ISIT, 2004.
[19] J. M. Wozencraft, “Sequential Decoding for Reliable Communication,”
1957.
[20] K. Zigangirov, “Some Sequential Decoding Procedures,” Problemy
Peredachi Informatsii, vol. 2, no. 4, pp. 13–25, 1966.
[21] F. Jelinek, “A Fast Sequential Decoding Algorithm Using a Stack,” IBM
Journal of Research and Development, vol. 13, no. 6, pp. 675–685, 1969.
[22] R. Fano, “A Heuristic Discussion of Probabilistic Decoding,” IEEE
Transactions on Information Theory, vol. 9, no. 2, pp. 64–74, 1963.
[23] V. Van der Leest, B. Preneel, and E. Van der Sluis, “Soft decision error
correction for compact memory-based pufs using a single enrollment.”
in CHES. Springer, 2012, pp. 268–282.

