Implementation of algorithms from the paper Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data

PinSketch (the BCH-based secure sketch) has been implemented in C++ by Kevin Harmon and Leonid Reyzin using Victor Shoup's NTL. The implementation includes, in particular, sublinear-time syndrome encoding and decoding of BCH codes, as described in this excerpt from the fuzzy extractors paper called bch-excerpt.pdf. It provides an efficient way to find differences between two sets without having to communicate the sets, and with minimum information leakage.

• pinsketch.txt: Brief description of the implementation (for more information on what this is good for, see the fuzzy extractors paper).
• bch.cpp: The code for binary BCH syndrome encoding and decoding in sublinear time if that's all you are interested in (this does not have any interface routines)
• pinsketch.zip: The zip archive of the entire implementation (includes all source files, pinsketch.txt, and bch-excerpt.pdf).

The improved Juels-Sudan secure sketch has been implemented by Soren Johnson and Leonid Reyzin, also using NTL. It also provides a way (though less efficient, at least as currently implemented) to find differences between two sets without having to communicate the sets. The implementation includes, in particular, Welch-Berlekamp decoding for Reed-Solomon codes, which may be useful for other purposes.

• ijssketch.txt: Brief description of the implementation (for more information on what this is good for, see the fuzzy extractors paper).
• WelchBerlekamp.cpp: The code for decoding Reed-Solomon codes, time, if that's all you are interested in (this does not have any interface routines)
• ijssketch.zip: The zip archive of the entire implementation (includes also the above files).