A trivial debiasing scheme for Helper Data Systems

The past decade has seen a lot of interest in the field of security with noisy data. In several security applications it is necessary to reproducibly extract secret data from noisy measurements on a physical system. One such application is read-proof storage of cryptographic keys using physical unclonable functions (PUFs) [5, 16, 18‐20]. Another application is the privacy-preserving storage of biometric data.

Storage of keys in nonvolatile digital memory can often be considered insecure because of the vulnerability to physical attacks. (For instance, fuses can be optically inspected with a microscope; flash memory may be removed and read out.) PUFs provide an alternative way to store keys, namely in analog form, which allows the designer to exploit the inscrutability of analog physical behavior. Keys stored in this way are sometimes referred to as Physically Obfuscated Keys (POKs) [12]. In both the biometrics and the PUF/POK case, one faces the problem that some form of error correction has to be performed, but under the constraint that the redundancy data, which are visible to attackers, do not endanger the secret extracted from the physical measurement. This problem is solved by a special security primitive, the Helper Data System (HDS). A HDS in its most general form is shown in Fig. 1. The Gen procedure takes as input a measurement X. It outputs a secret S and (public) Helper Data W. The helper data are stored. In the reconstruction phase, a fresh measurement \(X'\) is obtained. Typically, \(X'\) is a noisy version of X, close to X (in terms of, e.g., Euclidean distance or Hamming distance) but not necessarily identical. The Rec (reconstruction) procedure takes \(X'\) and W as input. It outputs \(\hat{S}\), an estimate of S. If \(X'\) is not too noisy then \(\hat{S}=S\).

Two special cases of the general HDS are the Secure Sketch (SS) and the fuzzy extractor (FE) [10]. The Secure Sketch has \(S=X\) (and \(\hat{S}=\hat{X}\), an estimator for X). If X is not uniformly distributed, then S is not uniform. The SS is suitable for privacy-preserving biometrics, where high entropy of S (given W) is required, but not uniformity. The fuzzy extractor is required to have a (nearly) uniform S given W. The FE is typically used for extracting keys from PUFs and POKs.

By way of example we briefly present the code offset method [4, 9, 10, 14, 21], the oldest and most well-known HDS. The COM makes use of a linear code \({\mathcal {C}}\) with k-bit messages and n-bit codewords. The syndrome function is denoted as \(\mathtt{Syn}: \{0,1\} ^n\rightarrow \{0,1\} ^{n-k}\). The code supports a syndrome decoding algorithm \(\mathtt{SynDec}:\) \( \{0,1\} ^{n-k}\) \(\rightarrow \{0,1\} ^n\) that maps syndromes to error patterns. Use is also made of a key derivation function \(\mathtt{KeyDeriv}: \{0,1\} ^n\times \{0,1\} ^*\rightarrow \{0,1\} ^\ell \), with \(\ell \le k\). Below we show how the COM can be used as a FE for either uniform or non-uniform source X.

\({ {Enrollment:}}\)

The enrollment measurement gives \(X\in \{0,1\} ^n\). The helper data are computed as \(W=\mathtt{Syn}\,X\). The key is computed as \(S=\mathtt{KeyDeriv}(X,R)\), where R is (optional) public randomness. The W and R are stored.

\({ {Reconstruction:}}\)

A fresh measurement of the PUF gives \(X'\in \{0,1\} ^n\). The estimator for X is computed asand the reconstructed key is \(\hat{S}=\mathtt{KeyDeriv}(\hat{X},R)\).

After seeing the helper data W as specified above, an attacker has uncertainty \(\mathsf{H}(X|W)\) about X.¹ As W is a function of X, we have \(\mathsf{H}(X|W)=\mathsf{H}(X|\mathtt{Syn}\, X)=\mathsf{H}(X)-\mathsf{H}(\mathtt{Syn}\,X)\). Let us consider the simplest possible noise model, the binary symmetric channel (BSC). In the case of a BSC with bit error rate \(\beta \), the code’s redundancy has to satisfy \(n-k\ge n h(\beta )\) in order for the error correction to work. (Here, h denotes the binary entropy function, \(h(\beta )= -\beta \log \beta -(1-\beta )\log (1-\beta )\), with ‘log’ the base 2 logarithm.) More generally, \(\mathsf{H}(\mathtt{Syn}\,X)\) has at least to be equal to the entropy of the noise. Hence, the COM helper data in the BSC case leak at least \(nh(\beta )\) bits of information about X. This becomes a problem when X itself does not have much entropy, which occurs for instance if the bits in X are highly biased [13, 15]. Note that the problem is not fundamental: if the bias parameter (see Sect. 2) is denoted as p, the secrecy capacity is \(nh(p+\beta -2p\beta )-nh(\beta )\), which is positive.

A solution was proposed by Maes et al. [17]. Their approach is to combine debiasing with error correction. For the debiasing they use the von Neumann algorithm in a single-pass or multi-pass manner. Their helper data comprise a selection ‘mask’ that helps the reconstruction algorithm to identify the locations where von Neumann should yield output.

In this paper we follow a simpler approach similar to the Index-Based Syndrome (IBS) method [22]. In IBS the helper data consist of an ordered list of pointers to locations in X; the content of X in those locations together forms a codeword.

We introduce an alternative solution to the bias problem in helper data systems. We follow the condense-then-fuzzy-extract philosophy proposed by Canetti et al. [7] as one of the available options when faced with ‘more noise than entropy’ scenarios. Condensing means mapping the source variable X to a smaller space such that most of the entropy of X is retained, but the noise entropy is greatly reduced. Our way of condensing the source is to restrict X to the bit positions \({\mathcal {U}}\), with \({\mathcal {U}}\subset \{1,\ldots ,n\}\) a random subset containing all the rare symbols. The set \({\mathcal {U}}\) becomes part of the helper data.

Our \({\mathcal {U}}\) bears some similarity to the von Neumann mask in [17], but there are important differences. (i) The size of \({\mathcal {U}}\) is tunable. (ii) We can extract source information based on the legitimate party’s ability to distinguish \({\mathcal {U}}\) from fake instances of \({\mathcal {U}}\) when a ‘spamming’ technique similar to [21] is applied.

The outline of this paper is as follows. Section 2 gives the details of the scheme. Section 3 analyzes the extractable entropy and the practicality of the ‘spamming’ option. In Sect. 5 we make some remarks on the use of min-entropy. Section 6 summarizes and suggests future work.

Below we present a barebones version of our proposed scheme. We omit details concerning the protection of the stored data. There are well-known ways to protect helper data, using either Public Key Infrastructure or one-way functions [6]. We also omit details that have to do with the verification of the reconstructed key. These details can be trivially added.

\({ {System setup}}\)

The following system parameters are fixed. An integer u satisfying \(np< u<n\), representing the size of \({\mathcal {U}}\); a list length L; a pseudorandom generator f that takes as input a seed \(\sigma \) and a counter j, and outputs a subset \(f(\sigma ,j)\subset [n]\) such that \(|f(\sigma ,j)| =u\); a Secure Sketch \((\mathtt{Gen},\mathtt{Rec})\) that acts on a source in \( \{0,1\} ^u\) and is able to handle bit error rate \(\beta \); a key derivation function \(\mathtt{KDF}: \{0,1\} ^u\times [L]\rightarrow \{0,1\} ^\ell \). All these parameters are public.

\({ {Enrollment}}\)\({ {Reconstruction}}\)We will typically consider \(u\ge 2np\). With an exponentially small probability it may occur that \(w(X)\ge u\), leading to \(X_{\mathcal {U}}=1^u\) in step E2. Even if such an exceptional PUF is encountered, the scheme still works.

The effect of steps E4,E5 is to create a list of \({\mathcal {U}}\)-candidates, of which only entry z is correct. To an attacker (who knows u but does not know X or \(X'\)) the L candidates are indistinguishable.³

Steps R3–R5 allow for a quick search to identify the index z of the correct \({\mathcal {U}}\)-candidate. Note that the reconstruction algorithm compares a permuted \({\mathcal {M}}\) to \({\mathcal {L}}\)-entries instead of \({\mathcal {M}}\) to permuted \({\mathcal {L}}\)-entries; this improves speed. To further optimize for speed, steps R4 and R5 can be combined in a loop to select good z values on the fly as soon as a new \({\mathcal {L}}_j\) is generated.

Note that extremely fast pseudorandom generators exist which spew out more than 8 bits per clock cycle [1, 2]. This makes it practical to work with large values of L, as long as not too many plausible z-candidates are generated. See Sect. 3.3. Even on CPU-constrained devices⁴ (clock speed of MHz order) it should be possible to achieve \(L=2^{10}\).

We did not explicitly specify how to map a seed to a size-u subset of [n]. A very straightforward algorithm would be to pick u pseudorandom locations in [n].

We did not specify an algorithm for determining the permutation \(\pi \), nor did we specify in which form \(\pi \) is stored. These are minor details and have no impact on the overall efficiency of the scheme, since steps E5 and R3 are performed only once. The computational bottleneck is R4, R5. For details about permutations we refer to [3, 11].

Note that inputting z into the key derivation function increases the entropy of S by \(\log L\) bits. If the PUF has ample entropy then \(L=1\) suffices, and one can skip all steps involving the seed \(\sigma \) and the permutation \(\pi \); the \({\mathcal {U}}\) itself is stored as helper data. This yields a scheme that is very fast and implementable on resource-constrained devices.

The Hamming weight of X carries very little information. Let us assume for the moment that \(T=w(X)\in \{0,\ldots ,u\}\) is known to the attacker⁵, just to simplify the analysis.

Even if the attacker knows t and \({\mathcal {U}}\) (i.e., z), there are \({u\atopwithdelims ()t}\) equally probable possibilities for Y. Hence,The inequality follows from Stirling’s approximation.

As (2) does not depend on z, the entropy \(\mathsf{H}(Y|T=t)\) is also given by (2). A lower bound on \(\mathsf{H}(Y|T)\) is obtained by taking the expectation over t. This turns out to be rather messy, since the distribution of t is a truncated binomial. (It is given that \(t\le u\), while originally \(w(X)\in \{0,\ldots ,n\}\)). As t equals approximately np on average, the result is \(\mathsf{H}(Y|T)\approx u h(\frac{np}{u})\). A more precise lower bound is given in Theorem 1 below.

The entropy of Y is obtained as follows,The \(\mathsf{H}(T)\) is the entropy of the truncated binomial distribution.

The complicated expression (6) can be well approximated by \(uh(np/u)-u/np\). Note that the difference between the original source entropy \(\mathsf{H}(X)=nh(p)\) and the condensed form \(\mathsf{H}(Y)\approx uh(np/u)-u/np\) is considerable. For example, setting \(n=640\), \(p=0.1\), \(u=128\) yields \(\mathsf{H}(Y)\approx 126\) and \(\mathsf{H}(X)\approx 300\). A small part of this huge difference can be regained using the trick with the entropy of Z. The practical aspects are discussed in Sect. 3.3.

Note also that our scheme outperforms simple von Neumann debiasing by a factor of at least 2. The von Neumann algorithm takes n / 2 pairs of bits; each pair has a probability \(2p(1-p)\) of generating a (uniform) output bit; hence, the extracted entropy is \(np(1-p)<np\). In our scheme, if we set \(u\approx 2np\) we get \(\mathsf{H}(Y)\approx 2np-2\). Furthermore, \(\mathsf{H}(Y)\) is an increasing function of u.

The code offset method applied to \(Y\in \{0,1\} ^u\) leaks at least \(u h(\beta )\) bits of information about Y. In case of a ‘perfect’ error-correcting code, the length of a noise-robust key reconstructed with the COM is \(\mathsf{H}(Y)-uh(\beta )\). In Fig. 2 we plot \(\mathsf{H}(Y)-uh(\beta )\) for some example parameter settings. (Note that in all cases shown here \(\beta \ge p\) holds; the COM acting on the original source X would be unable to extract any entropy.) Clearly, there is an optimal u for given \((n,p,\beta )\). In practice one is given p and \(\beta \) and has to find (n, u) such that the \(\mathsf{H}(Y)-uh(\beta )\) is large enough.

We briefly discuss how large L can be made before the reconstruction procedure sketched in Sect. 2 starts to produce too many candidates for z. We define \(\tilde{p}=p+\beta -2p\beta \).

On the one hand, there is the number of ‘1’ symbols in \(X'_{\mathcal {U}}\) for the correct \({\mathcal {U}}\). The number of 1’s in \(X_{\mathcal {U}}\) is on average np. Of these, on average \(np(1-\beta )\) will be a ‘1’ in \(X'\). The \((u-np)\) zeroes in \(X_{{\mathcal {U}}}\) will generate on average \((u-np)\beta \) 1’s in \(X'\). Hence, the number of 1’s in \(X'_{\mathcal {U}}\) is expected to be around \(np(1-\beta )+(u-np)\beta =np+(u-2np)\beta \).

On the other hand, there is the number of 1’s for incorrect \({\mathcal {U}}\)-candidates. The number of 1’s in \(X'\) is approximately \(n\tilde{p}\). We pretend that \(n\tilde{p}\) is integer, for notational simplicity. We denote by \(A\in \{0,\ldots ,n\tilde{p}\}\) the number of 1’s in \(X'_{{\mathcal {V}}}\) for a randomly chosen subset \({\mathcal {V}}\), with \(|{\mathcal {V}}|=u\). The A follows a hypergeometric probability distributionThe first expression looks at the process of selecting u out of n positions with exactly a 1’s hitting the \(n\tilde{p}\) existing 1’s in \(X'\); the second expression looks at the process of selecting \(n\tilde{p}\) positions in \(X'\) such that exactly a of them lie in \({\mathcal {V}}\). We have \({\mathbb {E}}_a\,a=u\tilde{p}\) and \({\mathbb {E}}_a(a-u\tilde{p})^2=u\tilde{p}(1-\tilde{p})(n-u)/(n-1)<u\tilde{p}\). In other words, a is sharply peaked around \(u\tilde{p}\).

We can put a threshold \(\theta \) somewhere in the gap between \(u\tilde{p}\) and \(np+(u-2np)\beta \), and declare a \({\mathcal {U}}\)-candidate \({\mathcal {V}}\) to be bad if the Hamming weight of \(X'_{\mathcal {V}}\) is lower than \(\theta \). Let us set \(\theta =np+(u-2np)\beta -c\cdot \sqrt{np}\) with c sufficiently large to avoid false negatives (i.e., missing the correct \({\mathcal {U}}\)). In a way analogous to (3), we can bound the false positive probability asThese bounds are obtained by applying (3) and replacing \(u\rightarrow \theta \), \(n\rightarrow u\), \(p\rightarrow \tilde{p}\). Figure 3 shows how many bits of entropy (\(b\approx -\log \mathrm{Pr}[A>\theta ]\)) can be obtained from z without running into false positives in step R5. To extract b bits of entropy, a list length \(L=2^b\) is needed. Figure 3 serves just to show the orders of magnitude and is by no means an exhaustive treatment of the whole parameter space \(n,p,\beta ,u,\theta \). We remark that the curves depend quite strongly on the threshold parameter c.

It is important to note that it is perfectly possible to make L extremely large. Then, many false positives occur, but this is not a fundamental problem. It requires extra work: one key reconstruction and one verification (e.g., of a key hash) per false positive. Depending on the available n, the computing platform, etc., this may be a viable option.