# Fuzzy Extractor for Binary Sequence

I was implementing Fuzzy Extractor on two close (noisy data). It's straight forward to use it to reconcile two close sets as per implementation given in https://www.cs.bu.edu/~reyzin/code/fuzzy.html, given contents of set are decimal number because: 1. It compares sets, hence position of numbers in set does not matter. If I have two binary sequence extracted from close secrets can I use this extractor to correct two close binary sequence, say 10% of bits are mismatching?

As per documentation of Pinsketch we cannot use $0s$. Since set matters, $[10011]$ and $[01011]$ will match as contents are same except order of $0$ and $1$.

Papers like [LLYM17] report of using Binary bit stream but I cannot find how this implementation based on works of Dodis et.al can be used here.

[LLYM17]: Xinghua Li, Jiajia Liu, Qingsong Yao, Jianfeng Ma, Efficient and Consistent Key Extraction Based on Received Signal Strength for Vehicular Ad Hoc Networks, in IEEE Access 2017.

• [LLYM17] is fascinating: it claims establishing a shared session key between two parties communicating by e.g Wifi, without a prior common reference, in presence of an eavesdropper (under some physical model of that), by processing Received Strength Signal Indicator measurements using a fuzzy extractor (with error-correction data exchanged thru a public channel, per their useful figure 3). While the security/cryptographic arguments are rather ad hoc, the claim of experimentally achieving key agreement is remarkable. They carefully cite references.
– fgrieu
Jul 11, 2017 at 21:09

You can use pin sketch. Consider the set of number [0,1,2,3,4,5,6,7]. The presence of a number can represent the presence of a 1 at that bit position in an 8 bit number.

E.G.

[0,2,4,6] == 10101010 == 0x55

[0,1,2,3] == 11110000 == 0xF0

Extend to a useful size (like 2040 bits which maps nicely to a BCH code) and you are comparing sets that have on average 1020 unique values, each showing the positions of the ones.

• That said - We use code offset in our products it's a lot simpler in hardware and there is sufficient entropy left over to get a 256 bit key out of an SP800-90B compliant extractor. Feb 2, 2019 at 19:45

Quoting discussion: We shouldn't use pinsketch then, which was designed for set difference. Instead, one need fuzzy extractors for Hamming distance. To build such a thing, you will need find an implementation of binary error-correcting codes, and then apply Construction 2 and 3 from http://www.cs.bu.edu/~reyzin/papers/fuzzy.pdf or the randomized construction from https://eprint.iacr.org/2006/020.pdf (basically, randomly permute the bit order first, then apply the code).

I think other people may have implemented something like that already. You may want to look in the literature on generating keys from PUFs, which uses fuzzy extractors for Hamming distance, and see if you can find any code. This paper can be a direction, https://people.csail.mit.edu/devadas/pubs/secure-robust-ecc-puf.pdf.