Order invariant fuzzy commitment system
First Claim
Patent Images
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 (a1, . . . , an) 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 (xi,yi), for i in {1, . . . n}, each of the coordinate sets having a first value (xi) corresponding to a representation of an associated one (ai) of the at least one value of the first input element and a second value (yi) corresponding to a symbol in the codeword, wherein the symbol corresponds to the xith 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.
23 Assignments
0 Petitions
Accused Products
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.
-
Citations
22 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 (a1, . . . , an) 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 (xi,yi), for i in {1, . . . n}, each of the coordinate sets having a first value (xi) corresponding to a representation of an associated one (ai) of the at least one value of the first input element and a second value (yi) corresponding to a symbol in the codeword, wherein the symbol corresponds to the xith 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 22)
-
-
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 (a1, . . .,an) 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 (xi,yi), for i in {I, . . . n}, each of the coordinate sets having a first value (xi) corresponding to a representation of an associated one (ai) of the at least one value of the first input element and a second value (yi) corresponding to a symbol in the codeword, wherein the symbol corresponds to the xith 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. - View Dependent Claims (9)
-
-
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 mv, wherein the at least one value of the first sequence differs from the at least one value of the third sequence in at least mv/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 (a1, . . . , an) 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 (xi,yi) for i in {1, . . . k}for integer k >
0, each of the coordinate sets having a first value (xi) corresponding to a representation of an associated one (ai) of the at least one value of the first input element (A) and a second value (yi) corresponding to a symbol in the codeword (c), wherein the symbol is selected in a manner responsive to the first value xi, 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 (a1, . . . , an) 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 (xi,zi,yi), for i in {1, . . . ,k}>
each of the coordinate sets having a first value (xi) corresponding to a representation of an associated one (ai) of the at least one value of the first input element (A) and a second value (zi) constructed in a manner responsive to a pattern of occurrence of the associated one (ai) of the at least one value of the first input element (A) in the sequence (ai, . . . , an) and a third value (yi) 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 (xi and zi), 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. - View Dependent Claims (18)
-
-
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 (a1, . . . , an) 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 (xi,zi,yi), for i in {1 , . . . ,k} for integer k>
0, each of the coordinate sets having a first value (xi) corresponding to a representation of an associated one (ai) of the at least one value of the first input element (A) and a second value (zi) constructed in a manner responsive to information in the first input element (A), and a third value (yi) 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 (xi and zi) 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. - View Dependent Claims (20)
-
-
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 (a1,w1), (a2,w2), . . . , (an,wn) wherein each of the at least one aivalues is from a first predetermined set (F) and each of the at least one wi 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 (xi,zi,yi), for i in {l, . . ., k} for integer k>
0, each of the coordinate sets having a first value (xi) corresponding to a representation of an associated one ((ai,wi)) of the at least one pair of values of the first input element (A) and a second value (xi) constructed in a manner responsive to an associated one ((ai,wi)) of the at least one value of the first input element (A) in the sequence (ai,wi), (a2,w2), . . . , (an,wn) and a third value (yi) 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 (xi and zi), 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.
-
Specification