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).
Gergely Ács added Perl interface to our code and has kindly made it available on-line.
An optimizied self-contained implementation by Pieter Wuille, Greg Maxwell, Gleb Naumenko is available here.
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).
If you find a use for this code, or bugs in it, I'd love to hear about it.
This material is based upon work supported by the National Science Foundation un
der 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).