Back to results
US 2002/0120592 A1Published application
Order invariant fuzzy commitment system
AssigneeRSA Security Inc.
InventorsAri Juels, Madhu Sudan
Life of this patent
Estimating the term…
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 decommiting the item if a second set of elements has a specified level of overlap with the first set of elements.
Claims45
A 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.
A method for decommitting an order-invariant fuzzy commitment comprising:
- receiving a first input element including a sequence of one or more values from a predetermined set;
- receiving an order-invariant fuzzy commitment sequence;
- constructing a set of integers having a predetermined number of elements representing respectively values in the first input element;
- selecting a subset of the coordinate sets in the first sequence such that the first value in each subset coordinate set corresponds to the first value of at least one coordinate set in the first sequence;
- and
- applying an error-correcting function to the subset.
3 more elements
A 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;
- (b) 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 error-correcting code c;
- (d) 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;
- and
- (g) outputting the second codeword c′.
5 more elements
A method for generating an order invariant fuzzy commitment of an item of information, comprising:
- receiving a first set of elements;
- and
- selecting a polynomial for encoding the item under the first set of elements to generate an order-invariant fuzzy commitment of the item.
A system for generating an order-invariant fuzzy commitment, comprising:
- a first input device for receiving first elements of information and providing a first set of elements;
- a commitment module for encrypting an item of information over the first set of elements using an order-invariant fuzzy commitment scheme;
- a second input device for receiving second elements of information and providing a second set of elements;
- and
- a decommitment module for selectively decrypting the item of information based upon a level of overlap between the first set of elements and the second set of elements.
2 more elements
A biometric system, comprising:
- a scanner for receiving first biometric information from a user;
- a commitment module for generating an order-invariant fuzzy commitment of an item of information over the first biometric information;
- and
- a decommitment module for selectively decommitting the item of information from a level of overlap between the first biometric information and second biometric information.
1 more element
A computer readable medium, comprising code for enabling the steps of:
- (a) receiving a first input element comprising a sequence of at least one value from a predetermined set;
- (b) generating a codeword of an error-correcting code;
- and
- (c) constructing a first sequence of coordinate sets, each of the coordinate sets having a first value corresponding to a representation of an associated one of the at least one value of the first input element and a second value corresponding to a symbol in the codeword, wherein the symbol is associated with the corresponding first value.
1 more element
A 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.
A 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} for integer k>0, each of the coordinate sets having a first value (xi) corresponding to a representation of an associated one (as) 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 (as) of the at least one value of the first input element (A) in the sequence (a1, . . . , 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.
A 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 is 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.
A 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 ai values 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 (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,wi)) of the at least one pair of values of the first input element (A) and a second value (zi) 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 (a1,w1), (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.
Dependencies are inferred from the claim text.