Order invariant fuzzy commitment system

1. A computer-implemented method for creating an order-invariant fuzzy commitment, comprising:

(a) receiving a first input element comprising a sequence of at least one value (a 1 , . . . , a n ) from a predetermined set;

(b) generating a codeword of an error-correcting code for generating the commitment;

(c) constructing a first sequence of coordinate sets (x i ,y i ), for i in {1, . . . n}, each of the coordinate sets having a first value (x i ) corresponding to a representation of an associated one (a i ) of the at least one value of the first input element and a second value (y i ) corresponding to a symbol in the codeword, wherein the symbol corresponds to the x i th symbol in the codeword, wherein an order-invariant fuzzy commitment is formed, the commitment having the property that it may be algorithmically combined with at least one set of values comprising at least one value of the first input element so as to yield the codeword;

reordering the first sequence based upon the first value;

outputting the first sequence; and

utilizing the first sequence, in response to receiving a second input element from a user, to authenticate the user to a secured system associated with the first sequence.

2. The method according to claim 1 , wherein the representation of the first value in the first sequence of coordinate set is an integer representation.

3. The method according to claim 1 , further including deriving the first input element from a measurement of a biometric associated with a user.

4. The method according to claim 3 , further including selecting the biometric from the group consisting of fingerprint information, retinal scan information, iris scan information, bloodflow-pattern information, thermal imaging information, handwritten-signature dynamics information, physiognomic information, hand geometry information, and voice information.

5. The method according to claim 1 , further including adding chaff to the first sequence.

6. The method according to claim 5 , further including adding the chaff as sets of pairs of the form (x,y) such that x does not lie in the input sequence and y is generated at random.

7. The method according to claim 5 , further including adding the chaff as sets of pairs of the form (x,y) such that one or more values x do lie in the input sequence and y is generated at random.

8. A computer-implemented method for creating an order-invariant fuzzy commitment, comprising:

(a) receiving a first input element comprising a sequence of at least one value (a 1 , . . .,a n ) from a predetermined set;

(b) generating a codeword of an error-correcting code for generating the commitment;

(c) constructing a first sequence of coordinate sets (x i ,y i ), for i in {I, . . . n}, each of the coordinate sets having a first value (x i ) corresponding to a representation of an associated one (a i ) of the at least one value of the first input element and a second value (y i ) corresponding to a symbol in the codeword, wherein the symbol corresponds to the x i th symbol in the codeword, wherein an order-invariant fuzzy commitment is formed, the commitment having the property that it may be algorithmically combined with at least one set of values comprising at least one value of the first input element so as to yield the codeword;

adding the chaff as sets of pairs of the form (x,y) such that x does not lie in the input sequence and y is generated at random; and

reordering the first sequence based upon the first value;

outputting the first sequence; and

utilizing the first sequence, in response to receiving a second input element from a user, to authenticate the user to a secured system associated with the first sequence.

9. The method according to claim 8 , further including reordering the first sequence in ascending order based upon the first value.

10. The method according to claim 1 , further including applying a bijective function to an input secret to obtain the codeword for the symbol corresponding to the second value.

11. The method according to claim 1 , further including decommitting the order-invariant commitment by

receiving a second input element including a second sequence of at least one value (b 1 , . . . b m ) from the predetermined set;

receiving the first sequence;

constructing a derived set of values (X′=x 1 ′, . . . ,x m ′) representing respectively the at least one value (b 1 . . . , b m ) in the second sequence;

selecting a subset of the coordinate sets {(x i , y i )} in the first sequence (E) such that for each pair (x′,y′) in the subset, the first value in the pair (x′) lies in the derived set of values (X′); and

applying an error-correcting function to the subset.

12. The method according to claim 11 , wherein the error-correcting function includes a Reed-Solomon code.

13. The method according to claim 1 , further including selecting a polynomial to generate the codeword.

14. The method according to claim 1 , further including utilizing a decodable design for decommitting the order-invariant commitment.

15. A computer-implemented method for creating a reordering-tolerant fuzzy commitment comprising:

(a) receiving a first input element A including a first sequence of at least one value;

generating a first codeword c of an error-correcting code for the commitment;

(c) constructing a sequence E of one or more data elements responsive to the first input element A and the first code word c of the error-correcting code;

outputting the sequence E;

(e) receiving a second input element B including a second sequence of at least one value and the sequence E, wherein the second sequence has a number of elements m;

(f) applying a function d responsive to the second input element B and the sequence E, wherein the function yields as output a value of a second codeword (c′d(B,E)), the function having a property such that d(V,E)=c for at least one possible value of V, where V comprises a third sequence having a number of elements m v , wherein the at least one value of the first sequence differs from the at least one value of the third sequence in at least m v /2 values;

(g) outputting the second codeword (c′d(B,E)); and

(h) utilizing the second codeword (c′d(B,E), in response to receiving a second input element from a user, to authenticate the user to a secured system associated with the first sequence.

16. A computer-implemented method for creating an order-invariant fuzzy commitment, comprising:

(a) receiving a first input element (A) comprising a sequence of at least one value (a 1 , . . . , a n ) from a predetermined set (F);

(b) generating a codeword (c) of an error-correcting code for generating the commitment;

(c) constructing a first sequence (E) of coordinate sets (x i ,y i ) for i in {1, . . . k}for integer k >0, each of the coordinate sets having a first value (x i ) corresponding to a representation of an associated one (a i ) of the at least one value of the first input element (A) and a second value (y i ) corresponding to a symbol in the codeword (c), wherein the symbol is selected in a manner responsive to the first value x i , wherein an order-invariant fuzzy commitment is formed;

reordering the first sequence based upon the first value;

outputting the first sequence; and

utilizing the first sequence, in response to receiving a second input element from a user, to authenticate the user to a secured system associated with the first sequence.

17. A computer-implemented method for creating an order-invariant fuzzy commitment, comprising:

(a) receiving a first input element (A) comprising a sequence of at least one value (a 1 , . . . , a n ) from a predetermined set (F);

(b) generating a codeword (c) of an error-correcting code for generating the commitment;

(c) constructing a first sequence (E) of coordinate sets (x i ,z i ,y i ), for i in {1, . . . ,k}> each of the coordinate sets having a first value (x i ) corresponding to a representation of an associated one (a i ) of the at least one value of the first input element (A) and a second value (z i ) constructed in a manner responsive to a pattern of occurrence of the associated one (a i ) of the at least one value of the first input element (A) in the sequence (a i , . . . , a n ) and a third value (y i ) corresponding to a subset of symbols in the codeword (c), wherein the subset of symbols is selected in a manner responsive to at least one of the first and second values of the coordinate set (x i and z i ), wherein an order-invariant fuzzy commitment is formed;

(d) outputting the first sequence; and

(e) utilizing the first sequence, in response to receiving a second input element from a user, to authenticate the user to a secured system associated with the first sequence.

18. A method according to claim 17 , further including decommitting the order-invariant commitment by

receiving a second input element B including a second sequence of at least one value (b 1 , . . . , b m ) from the predetermined set (F);

receiving the first sequence (E);

constructing a derived set of values (X′=x1′, . . . , x m ′) representing respectively the at least one value (b 1 , . . . , b m ) in the second sequence (B);

selecting a subset (E′) of the coordinate sets {(x i , y i )} in the first sequence (E) such that for each pair (x′,z′,y′) in the subset (E′), the first value in the pair (x′) lies in the derived set of values (X′); and

applying an error-correcting function to the subset (E′).

19. A computer-implemented method for creating an order-invariant fuzzy commitment, comprising:

(a) receiving a first input element (A) comprising a sequence of at least one value (a 1 , . . . , a n ) from a predetermined set;

(b) generating a codeword (c) of an error-correcting code for generating the commitment;

(c) constructing a first sequence (E) of coordinate sets (x i ,z i ,y i ), for i in {1 , . . . ,k} for integer k>0, each of the coordinate sets having a first value (x i ) corresponding to a representation of an associated one (a i ) of the at least one value of the first input element (A) and a second value (z i ) constructed in a manner responsive to information in the first input element (A), and a third value (y i ) corresponding to a subset of symbols in the codeword (c), wherein the subset of symbols i selected in a manner responsive to at least one of the first and second values (x i and z i ) of the coordinate set, wherein an order-invariant fuzzy commitment is formed;

(d) outputting the first sequence; and

(e) utilizing the first sequence, in response to receiving a second input element from a user, to authenticate the user to a secured system associated with the first sequence.

20. The method according to claim 19 , further including decommitting the order-invariant commitment by

receiving a second input element (B) including a second sequence of at least one value (b 1 , . . . , b m ) from the predetermined set (F);

receiving the first sequence (E);

constructing a derived set of values (X′x 1 ′, . . . ,x m ′) representing respectively the at least one value (b 1 , . . . , b m ) in the second sequence (B); and

selecting a subset (E′) of the coordinate sets {(x i ,y i )} in the first sequence (E) such that for each pair (x′,z′,y′) in the subset (E′), the first value in the pair (x′) lies in the derived set of values (X′); and

applying an error-correcting function to the subset (E′).

21. A computer-implemented method for creating an order-invariant fuzzy commitment, comprising:

(a) receiving a first input element (A) comprising a sequence of at least one pair of values (a 1 ,w 1 ), (a 2 ,w 2 ), . . . , (a n ,w n ) wherein each of the at least one a i values is from a first predetermined set (F) and each of the at least one w i values is from a second predetermined set (G);

(b) generating a codeword (c) of an error-correcting code for generating the commitment;

(c) constructing a first sequence (B) of coordinate sets (x i ,z i ,y i ), for i in {l, . . ., k} for integer k>0, each of the coordinate sets having a first value (x i ) corresponding to a representation of an associated one ((a i ,w i )) of the at least one pair of values of the first input element (A) and a second value (x i ) constructed in a manner responsive to an associated one ((a i ,w i )) of the at least one value of the first input element (A) in the sequence (a i ,w i ), (a 2 ,w 2 ), . . . , (a n ,w n ) and a third value (y i ) corresponding to a subset of symbols in the codeword (c), wherein the subset of symbols is selected in a manner responsive to at least one of the first and second values of the coordinate set (x i and z i ), wherein an order-invariant fuzzy commitment is formed;

outputting the first sequence; and

utilizing the first sequence, in response to receiving a second input element from a user, to authenticate the user to a secured system associated with the first sequence.

22. The method of claim 3 , further including decommitting the order-invariant commitment by:

receiving a second input element including a second sequence of at least one value (b 1 , . . . , b m ) from the predetermined set, the second input element being derived from a measurement of a biometric associated with a user;

receiving the first sequence;

constructing a derived set of values (X′=x 1 ′, . . . , x m ′) representing respectively the at least one value (b 1 , . . . , b m ) in the second sequence;

selecting a subset of the coordinate sets {(x i , y i )} in the first sequence (E) such that for each pair (x′,y′) in the subset, the first value in the pair (x′) lies in the derived set of values (X′);

applying an error-correcting function to the subset; and

authenticating the user to the secured system associated with the first sequence.