Implementation of Secure Sketches and Set Reconciliation

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).

If you find a use for this code, I'd love to hear about it.

This material is based upon work supported by the National Science Foundation under Grants CCR-0311485, CCF-0515100 and CNS-0202067. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).

The improved Juels-Sudan secure sketch has been implement by Soren Johnson and Leonid Reyzin. We are working out some minor details and hope to post the implementation shortly. Please contact me if you'd like to receive an email as soon as it's posted.