Order invariant fuzzy commitment system

• US 7,602,904 B2
• Filed: 11/26/2001
• Issued: 10/13/2009
• Est. Priority Date: 11/27/2000
• Status: Active Grant

• Current Assignee: RSA Security LLC (Symphony Technology Group LLC)
• Original Assignee: RSA Security Incorporated (Symphony Technology Group LLC)
• Inventors: Sudan, Madhu, Juels, Ari
• Primary Examiner(s): Smithers; Matthew B
• Assistant Examiner(s): WILLIAMS, JEFFERY L
• Application Number:
  US09/994,476
• Publication Number:
  US 20020120592A1
• Time in Patent Office: 2,878 Days
• Field of Search: 713/202
• US Class Current: 380/28
• CPC Class Codes: H04L 9/304 based on error correction codes, e.g. McEliece
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3231 Biological data, e.g. fingerprint, voice or retina network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861

Abstract

A system provides an order-invariant fuzzy commitment scheme. In an exemplary embodiment, the scheme includes receiving a first set of elements and selecting a polynomial for encoding an item under the first set of elements to generate an order-invariant fuzzy commitment of the item. The system utilizes an error-correcting code for decommitting the item if a second set of elements has a specified level of overlap with the first set of elements.

Claims

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₁, . . . , 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_ith 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.

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₁, . . . b_m) from the predetermined set;

receiving the first sequence;

constructing a derived set of values (X′

=x₁′

, . . . ,x_m′

) representing respectively the at least one value (b₁. . . , 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.

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₁, . . . , 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₁′

, . . . , x_m′

) representing respectively the at least one value (b₁, . . . , 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.

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₁, . . .,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_ith 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.

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₁, . . . , 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₁, . . . , 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₁, . . . , 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₁, . . . , 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₁, . . . , 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₁, . . . , b_m) from the predetermined set (F);

receiving the first sequence (E);

constructing a derived set of values (X′

x₁′

, . . . ,x_m′

) representing respectively the at least one value (b₁, . . . , 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₁,w₁), (a₂,w₂), . . . , (a_n,w_n) wherein each of the at least one a_ivalues 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₂,w₂), . . . , (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.