# Pitfall of the Strongest Cells in Static Random Access Memory Physical Unclonable Functions
## 4 Proposed New Fuzzy Extractor
### ERFE Architecture  
The value of sum of 11-bit cells is:  
\[sum(11)=\sum_{o=0}^{10}x_{o} \tag{9}\]  
As explained in the previous section, the power-on value of a cell is almost determined after manufacturing, and can be extracted as a key. After the manufacturing process, \(sum(11)\) is stable too. Due to the linear relationship between the power-on value and the sum value, \(sum(11)\) can be regarded as another type of fingerprint for SRAM. We propose a novel extraction scheme, ERFE, which allows 4-bit errors. ERFE is still divided into two phases: enrollment and reconstruction. In the enrollment phase, _Mask_ and _AddOp_ signals will be generated. In Algorithm 1, _AddOp_ indicates whether the addition or subtraction operation is performed in the reconstruction phase, and the operand of addition or subtraction is \"1\". _Mask_ indicates whether there 11-bit data are valid. When _Mask_ equals 1, 11-bit data are invalid and cannot be used for key extraction. When _AddOp_ and _Mask_ are produced in the enrollment phase, they are also stored in non-volatile memory, which can also be considered a type of helper data. ``` Input: 11-bit responses of SRAM \(x_{0}\), \(x_{1}\), \(x_{2}\),..., \(x_{10}\) Output: Mask, AddOp
1. initialize Mask, AddOp with zero
2. \(sum=x_{0}+x_{1}+x_{2}+\ldots+x_{10}\)
3.if\((sum==0)\)then
4. AddOp = 1; Mask =0;
5.elseif\((sum==2)\)then
6. AddOp = 0; Mask = 0;
7.elseif\((sum==9)\)then
8. AddOp = 1; Mask = 0;
9.elseif\((sum==11)\)then
10. AddOp = 0; Mask = 0;
11.elsethen
12. AddOp = 0; Mask = 1;
13.endif
14. ReturnMask, AddOp

Figure 5: Structure of a 3 \(\times\) 3 cell array in two-dimension space. In the reconstruction phase, the responses \(R^{\prime}\) are divided to multiple blocks, every block contains 11-bit data. For each block, when _Mask_ equals 0, this block is valid, and the \(sum^{\prime}\) is calculated using Equation (9), then we obtain \(sum^{\prime\prime}\) using _AddOp_:

\[sum^{\prime\prime}=\left\{ \begin{array}{l}sum^{\prime}+1,\text{ AddOp}==1\\ sum^{\prime}-1,\text{ AddOp}==0\end{array} \right. \tag{10}\]

Equation (10) contains an addition and subtraction operation. Overflow or underflow may occur when bit error happens. When performing an addition operation and overflow occurs, let \(sum^{\prime\prime}=11\), and \(sum^{\prime\prime}=0\) when underflow occurs. Since we have \(sum^{\prime\prime}\), we can recover the output key:

\[\text{Key}=\left\{ \begin{array}{l}0,\,sum^{\prime\prime}\leq 5\\ 1,\,sum^{\prime\prime}>5\end{array} \right. \tag{11}\]

### ERFE Security Analysis

The main target of the PUF is security and when using this fuzzy extractor, the key clearly cannot be obtained from the helper data, which is accessible to everyone. Figure 6 shows the corresponding diagrams of _AddOp_, _Mask_, _sum_, and _Key_ in the enrollment phase. \"-\" means this area is invalid:

From Algorithm 1 and Equations (10) and (11), _AddOp_ and the final key have a certain overlap. In Figure 6, \(sum=2\) and \(sum=9\) overlap with _AddOp_ and _Key_, _AddOp_ and _Key_ are equal within this overlap interval, and \(r_{0}\) is the accurate rate that _AddOp_ is regarded as _Key_:

\[r_{0}=\frac{p_{sum=2}+p_{sum=9}}{(p_{sum=0}+p_{sum=2}+p_{sum=9}+p_{sum=11})} \tag{12}\]

The rate of using the opposite value of _AddOp_ as the key is \(r_{1}=1-r_{0}\). \(P_{Key}\) is the rate of guessing _Key_ from _AddOp_ and \(P_{Key}=max(r_{0},r_{1})\). \(P_{Key}\) was ideally expected to close to 50% when the sum value is uniformly distributed. The sum value was not uniformly distributed because of the production skew is unpredicted and uncontrollable, so the output of the corresponding _Key_ also has some bias. ### Stability Analysis of \(Erfe\)

The probability that a string of \(n\) bits has more than \(s\)_bits_ errors is calculated as [26]:

\[p_{s}=\sum_{i=s+1}^{n}C_{n}^{i}\;p_{b}^{i}\;(1-p_{b})^{n-i} \tag{13}\]

where \(p_{b}\) is the bit error rate. In Figure 6, when \(sum\in(0,2,9,11)\), _Mask_ equals 0, so 11-bit data is used to extract _Key_.