pinsketch.txt

关于BCH编码的一个应用

INTRODUCTION

The files pinsketch.h, sketch.cpp, differ.cpp, io.cpp and bch.cpp contain
an implementation of PinSketch, the BCH-based secure sketch from "Fuzzy
Extractors: How to Generate Strong Keys from Biometrics and Other Noisy
Data" by Dodis, Ostrovsky, Reyzin and Smith (preliminary version in the
proceedings of Eurocrypt 2004; current version to be maintained at
http://eprint.iacr.org/2003/235).  The implementation is by Kevin Harmon
and Leonid Reyzin ([e-mail]).  It uses Victor Shoup's NTL (A
Library for doing Number Theory), which must be installed before it will
compile; see http://www.shoup.net.

Given an input set A of any number of (nonzero) m-bit strings and a
parameter t, the program "sketch" will produce as output a sketch of A of
size tm bits.  Then, if the size of the symmetric difference between sets A
and B is at most t, the program "differ" will find the symmetric difference
between A and B given only B and the sketch of A (thus, in particular,
recovering elements of A that are not in B without seeing A).  In fact,
"differ" can work given just the sketches of A and B (even if the sketches
were computed with different values of t, as long as the number of
differences is at most the smaller of the two).

These programs provide an efficient way to find differences between two
sets without having to communicate the sets.  They also allow for
information-reconciliation with minimum information leakage.  For more
details and applications, see the aforementioned "Fuzzy Extractors" paper.

The mathematical meat of the implementation is in bch.cpp, which is based
on "Syndrome Encoding and Decoding of BCH Codes in Sublinear Time"
(excerpted from the aforementioned "Fuzzy Extractors" paper).  The code in
bch.cpp is of greatest general interest; the rest of the code is specific
to the formats chosen by this implementation.

WARNINGS AND LIMITATIONS

The programs will not behave correctly if any of the following occurs.

1) There are duplicate elements in A or duplicate elements in B (i.e., if A
or B are multisets).

2) A or B contains a string of all zeroes.

3) t is greater than or equal to 2^{m-1}

4) The input or sketch files do not follow the prescribed format.

5) The size of the symmetric difference between the two sets is greater
than t (then "differ" will output an error message in most cases, but may
output an incorrect set difference).

Note that cases 1, 2, 3, and 4 can be taken care of at the input stage (but
currently are not).  Case 5 is impossible to fix completely, although there
are techniques that will reduce the likelihood of an incorrect output at
the expense of a larger sketch.


USAGE DETAILS

To compile, make sure you have NTL (A Library for doing Number Theory)
installed (see http://www.shoup.net) and issue command 

make

If the compilation fails, see the comments in the file called Makefile.
Once everything compiles, invoking

./sketch A.set

will produce A.ss (note that file must end in .set).  The format of A.set
is

t=<integer>
m=<integer>
[<int1> <int2> ... ]

where <intj> is a nonzero m-bit integer written in decimal. 

For example,

t=2
m=10
[2 347 532 87 876 39]

(Note that the choice to have inputs be decimal integers was arbitrary, and
the program can be easily modified to accept other inputs).

The sketch file A.ss will contain information on the input parameters and
generating polynomial of GF(2^m), followed by the tm bits of the sketch in
human-readable form as t elements of GF(2^m).  Of course, in a system where
the input parameters are fixed, only the tm bits are needed.

Invoking

./differ A.ss B.set

will output the symmetric difference between A and B if it has at most t
elements, and an error message or an incorrect answer otherwise.
Note that the order of elements in the symmetric difference is arbitrary.
The format of B.set is the same as of A.set; however, its t and m values will
be ignored.

Invoking

./differ A.ss B.ss

(assuming B.ss was computed using sketch B.set) will also output the
symmetric difference between A and B.  If A and B were computed with
respect to different m (or the same m but different generating polynomials,
which should not happen the way sketch is currently coded), an error
message will be output.  If A.ss was computed with respect to t1 and B.ss
was computed with respect to t2, then the difference must have no more than
min(t1, t2) elements; else an error message will be output, or possibly an
incorrect answer.

Sample files X.set, Y.set X.ss, Y.ss are included with the implementation.