System and method of hash string extraction

• US 7,564,997 B2
• Filed: 10/24/2005
• Issued: 07/21/2009
• Est. Priority Date: 07/25/2001
• Status: Expired due to Term

• Current Assignee: Activcard Ireland, Limited (Assa Abloy AB)
• Original Assignee: Activcard Ireland, Limited (Assa Abloy AB)
• Inventors: Hamid, Larry
• Primary Examiner(s): Strege; John B
• Application Number:
  US11/257,367
• Publication Number:
  US 20060050937A1
• Time in Patent Office: 1,366 Days
• Field of Search: 382/115, 382/124, 382/125, 340/5.83, 713/186
• US Class Current: 382/124
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction
• 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
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A method of hash string extraction from biometric information is disclosed. The method comprises the steps of providing a biometric information sample in the form of a fingerprint for example, extracting features from the biometric information sample and encoding the features based on their location within the biometric information sample; and, generating a string of values based on the extracted features and their determined locations. The method further comprises the steps of hashing the string of symbols to produce a plurality of hash values for comparing the plurality of hash values against a stored hash value for identifying a user.

Claims

1. A method of generating biometric data comprising:

extracting feature data from a set of biometric data corresponding to a biometric sample;

encoding the extracted feature data with a processor to create one or more enrollment templates of encoded features, said encoding including determining a plurality of features in the extracted feature data, determining at least a parameter associated with each of the plurality of features, and providing subset data corresponding to a plurality of overlapping subsets of the features, at least some of the overlapping subsets including fewer than all of the features within the set of data; and

generating an enrollment string of symbols representing said encoded features with the processor.

2. The method of claim 1 wherein the at least a parameter associated with the features comprises data relating to a feature type.

3. The method of claim 1 wherein the at least a parameter associated with the features comprises data indicative of a position of the feature relative to a first feature.

4. The method of claim 1, further comprising hashing the enrollment string using a hashing algorithm to generate a hash enrollment value.

5. The method of claim 4 wherein the hashing algorithm is insensitive to the order of data provided thereto.

6. The method of claim 1, further comprising authenticating a user by:

extracting user feature data from a set of biometric data derived from a biometric sample of a user;

encoding the extracted user feature data to create one or more templates of encoded user features;

generating one or more user strings of symbols representing said encoded user features;

hashing the user strings of symbols using a hashing algorithm to generate one or more user hash values; and

comparing the user hash values with the hash enrollment value to determine if the biometric sample of the user corresponds to the biometric sample.

7. The method of claim 6 wherein hashing the user strings of symbols comprises using a hashing algorithm that is insensitive to the order of data provided thereto.

8. The method of claim 6 wherein the user strings of symbols take into account a number of feature deletions allowed in said extracted feature data, a number of permitted quantization errors in said extracted feature data, and a number of re-quantization possibilities for said extracted feature data.

9. The method of claim 1, further comprising authenticating a user by:

extracting user feature data from a set of user biometric data derived from a biometric sample of a user;

encoding the extracted user feature data to create a template of encoded user features;

generating a user string of symbols representing said encoded user features; and

comparing the user string with the enrollment string to determine if the biometric sample of the user corresponds to the biometric sample.

10. A system for generating biometric data, comprising:

a contact imager configured to extract feature data from a set of biometric data corresponding to a biometric sample; and

a processor configured to encode the extracted feature data to create one or more enrollment templates of encoded features, determine a plurality of features in the extracted feature data, determines at least a parameter associated with each of the plurality of features, provides subset data corresponding to a plurality of overlapping subsets of the features, and generates an enrollment string of symbols representing said encoded features, wherein at least some of the overlapping subsets including fewer than all of the features within the set of data.

11. The system of claim 10 wherein the at least a parameter associated with the features comprises data relating to a feature type.

12. The system of claim 10 wherein the at least a parameter associated with the features comprises data indicative of a position of the feature relative to a first feature.

13. The system of claim 10 wherein the processor includes a hashing algorithm that hashes the enrollment string to generate a hash enrollment value.

14. The system of claim 13 wherein the hashing algorithm is insensitive to the order of data provided thereto.

15. The system of claim 13 wherein the processor further authenticates a user by extracting user feature data from a set of user biometric data derived from a biometric sample of a user, by encoding the extracted user feature data to create one or more templates of encoded user features, and by generating one or more user strings of symbols representing said encoded user features, wherein the hashing algorithm hashes the user strings of symbols to generate one or more user hash values and the processor compares the user hash values with the hash enrollment value to determine if the biometric sample of the user corresponds to the biometric sample.

16. The system of claim 15 wherein the hashing algorithm is insensitive to the order of data provided thereto.

17. The system of claim 15 wherein the user strings of symbols take into account a number of feature deletions allowed in said extracted feature data, a number of permitted quantization errors in said extracted feature data, and a number of re-quantization possibilities for said extracted feature data.

18. The system of claim 10 wherein the processor further authenticates a user by extracting user feature data from a set of user biometric data derived from a biometric sample of a user, by encoding the extracted user feature data to create a template of encoded user features, by generating a user string of symbols representing said encoded user features, and by comparing the user string with the enrollment string to determine if the biometric sample of the user corresponds to the biometric sample.

19. A computer-readable storage medium whose contents cause a computing system to perform a method for generating biometric data, the method comprising:

extracting feature data from a set of biometric data corresponding to a biometric sample;

encoding the extracted feature data to create one or more enrollment templates of encoded features, said encoding including determining a plurality of features in the extracted feature data, determining at least a parameter associated with each of the plurality of features, and providing subset data corresponding to a plurality of overlapping subsets of the features, wherein at least some of the overlapping subsets including fewer than all of the features within the set of data; and

generating an enrollment string of symbols representing said encoded features.

20. The computer-readable storage medium of claim 19 wherein the at least a parameter associated with the features comprises data relating to a feature type.

21. The computer-readable storage medium of claim 19 wherein the at least a parameter associated with the features comprises data indicative of a position of the feature relative to a first feature.

22. The computer-readable storage medium of claim 19, further comprising a hashing algorithm that hashes the enrollment string to generate a hash enrollment value.

23. The computer-readable storage medium of claim 22 wherein the hashing algorithm is insensitive to the order of data provided thereto.

24. The computer-readable storage medium of claim 19, further comprising:

extracting user feature data from a set of user biometric data derived from a biometric sample of a user;

encoding the extracted user feature data to create one or more templates of encoded user features;

generating one or more user strings of symbols representing said encoded user features;

hashing the user strings of symbols using a hashing algorithm to generate one or more user hash values; and

comparing the user hash values with the hash enrollment value to determine if the biometric sample of the user corresponds to the biometric sample.

25. The computer-readable storage medium of claim 24 wherein the hashing algorithm is insensitive to the order of data provided thereto.

26. The computer-readable storage medium of claim 24 wherein the user strings of symbols take into account a number of feature deletions allowed in said extracted feature data, a number of permitted quantization errors in said extracted feature data, and a number of re-quantization possibilities for said extracted feature data.

27. The computer-readable storage medium of claim 19, further comprising:

extracting user feature data from a set of user biometric data derived from a biometric sample of a user;

encoding the extracted user feature data to create a template of encoded user features;

generating a user string of symbols representing said encoded user features; and

comparing the user string with the enrollment string to determine if the biometric sample of the user corresponds to the biometric sample.

28. A method of password generation comprising:

determining from a biometric information sample a first string including a plurality of symbols, the symbols based on features within the biometric information sample;

determining a plurality of strings in dependence upon predetermined characteristics in relation to the first string;

hashing the strings from the determined plurality of strings with a processor to produce a plurality of hash values; and

comparing each hash value from the plurality of hash values against a stored hash value determined during an enrollment process with the processor for determining at least one hash string from the plurality of hash strings indicative of a match,

wherein upon a match between a hash value from the plurality of hash values and the stored hash value, the string from the plurality of strings and associated with the matching hash value is provided as the generated password.

29. The method of claim 28 wherein the first string is ordered based upon its symbol content.

30. The method of claim 29 wherein the strings from the plurality of strings are ordered based upon their symbol content.

31. The method of claim 28 wherein determining a plurality of strings in dependence upon predetermined characteristics comprises:

capturing an image of a biometric information sample from a biometric information source;

extracting a number r of features from the biometric information sample and encoding r symbols, one per feature; and

extracting a number δ

of extra features, and encoding δ

extra symbols, one per extra feature,

wherein comparing the string includes determining a number of symbols within the string that are absent from the previously stored string and deleting those symbols.

32. The method of claim 28 wherein when the comparison of each hash value from the plurality of hash values against a stored hash value determined during an enrollment process is indicative of other than at least one hash string from the plurality of hash strings matches, verifying if the plurality of hash strings includes all the hash strings that can be generated within predetermined characteristics.

33. The method of claim 28 wherein the generated password is an unordered generated password.

34. The method of claim 28, further comprising determining at least a feature type of features within the biometric information sample and encoding symbols from the plurality of symbols in dependence upon the determined feature type.

35. The method of claim 28 wherein a symbol is encoded as an n-bit value.

36. A method of password generation comprising:

determining a location of an alignment feature within a biometric information sample from an individual;

extracting features from the biometric information sample;

determining from the extracted features a first string of symbols based on locations of extracted features within the biometric information sample relative to the alignment feature;

determining a plurality of error strings in dependence upon predetermined parameters defining an error region about the extracted first string;

hashing the first string and at least some of the error strings from the determined plurality of strings with a processor to produce a plurality of hash values; and

comparing each produced hash value from the plurality of hash values with a predetermined stored hash value for determining a hash value from the plurality of hash values indicative of a match, wherein upon a match between a hash value from the plurality of hash values and the stored hash value, the string from which the matching hash value was derived is provided as the generated password.

37. The method of claim 36, further comprising providing an indication of the alignment feature.

38. The method of claim 37 wherein providing an indication of the alignment feature includes selecting the alignment feature from a plurality of alignment features.

39. The method of claim 37 wherein providing an indication of the alignment feature includes selecting a region within the biometric information sample, the region being indicative of an alignment feature from a plurality of potential alignment features.

40. A system for generating passwords, comprising:

means for determining from a biometric information sample a first string including a plurality of symbols and for determining a plurality of strings in dependence upon predetermined characteristics in relation to the first string, wherein the symbols are based on features within the biometric information sample;

means for hashing the strings from the determined plurality of strings to produce a plurality of hash values; and

means for comparing each hash value from the plurality of hash values against a stored hash value determined during an enrollment process for determining at least one hash string from the plurality of hash strings indicative of a match, wherein upon a match between a hash value from the plurality of hash values and the stored hash value, the string from the plurality of strings and associated with the matching hash value is provided as the generated password.

41. The system of claim 40 wherein the first string is ordered based upon its symbol content.

42. The system of claim 41 wherein the strings from the plurality of strings are ordered based upon their symbol content.

43. The system of claim 40 wherein the means for determining a plurality of strings in dependence upon predetermined characteristics further comprises means for capturing an image of a biometric information sample from a biometric information source, means for extracting a number r of features from the biometric information sample and encoding r symbols, one per feature, and means for extracting a number δ

of extra features, and encoding δ

extra symbols, one per extra feature, wherein the comparing means determines a number of symbols within the string that are absent from the previously stored string and deletes those symbols.

44. The system of claim 40 wherein when the comparing means compares each hash value from the plurality of hash values against a stored hash value determined during an enrollment process and determines the hash value to be indicative of other than at least one hash string from the plurality of hash strings matches, the comparing means verifies if the plurality of hash strings includes all the hash strings that can be generated within predetermined characteristics.

45. The system of claim 40 wherein the generated password is an unordered generated password.

46. The system of claim 40 wherein the determining means determines at least a feature type of features within the biometric information sample, further comprising encoding means for encoding symbols from the plurality of symbols in dependence upon the determined feature type.

47. The system of claim 40 further comprising encoding means for encoding a symbol as an n-bit value.

48. A system for generating a password, comprising:

means for determining a location of an alignment feature within a biometric information sample from an individual;

means for extracting features from the biometric information sample;

means for determining from the extracted features a first string of symbols based on locations of extracted features within the biometric information sample relative to the alignment feature;

means for determining a plurality of error strings in dependence upon predetermined parameters defining an error region about the extracted first string;

means for hashing the first string and at least some of the error strings from the determined plurality of strings to produce a plurality of hash values; and

means for comparing each produced hash value from the plurality of hash values with a predetermined stored hash value for determining a hash value from the plurality of hash values indicative of a match, wherein upon a match between a hash value from the plurality of hash values and the stored hash value, the string from which the matching hash value was derived is provided as the generated password.

49. The system of claim 48, further comprising means for providing an indication of the alignment feature.

50. The system of claim 49 wherein the means for providing an indication of the alignment feature includes means for selecting the alignment feature from a plurality of alignment features.

51. The system a of claim 49 wherein the means for providing an indication of the alignment feature includes means for selecting a region within the biometric information sample, the region being indicative of an alignment feature from a plurality of potential alignment features.

52. A computer-readable storage medium whose contents cause a computing system to perform a method for generating passwords, the method comprising:

determining from a biometric information sample a first string including a plurality of symbols, the symbols based on features within the biometric information sample;

determining a plurality of strings in dependence upon predetermined characteristics in relation to the first string;

hashing the strings from the determined plurality of strings to produce a plurality of hash values; and

comparing each hash value from the plurality of hash values against a stored hash value determined during an enrollment process for determining at least one hash string from the plurality of hash strings indicative of a match,

wherein upon a match between a hash value from the plurality of hash values and the stored hash value, the string from the plurality of strings and associated with the matching hash value is provided as the generated password.

53. The computer-readable storage medium of claim 52 wherein the first string is ordered based upon its symbol content.

54. The computer-readable storage medium of claim 53 wherein the strings from the plurality of strings are ordered based upon their symbol content.

55. The computer-readable storage medium of claim 52, further comprising:

determining the plurality of strings in dependence upon predetermined characteristics by capturing an image of a biometric information sample from a biometric information source;

extracting a number r of features from the biometric information sample and encoding r symbols, one per feature;

extracting a number δ

of extra features, and encoding δ

extra symbols, one per extra feature,

wherein comparing the string includes determining a number of symbols within the string that are absent from the previously stored string and deleting those symbols.

56. The computer-readable storage medium of claim 52 wherein when the comparison of each hash value from the plurality of hash values against a stored hash value determined during an enrollment process is indicative of other than at least one hash string from the plurality of hash strings matches, verifying if the plurality of hash strings includes all the hash strings that can be generated within predetermined characteristics.

57. The computer-readable storage medium of claim 52 wherein the generated password is an unordered generated password.

58. The computer-readable storage medium of claim 52, further comprising determining at least a feature type of features within the biometric information sample and encoding symbols from the plurality of symbols in dependence upon the determined feature type.

59. The computer-readable storage medium of claim 52 wherein a symbol is encoded as an n-bit value.

60. A computer-readable storage medium whose contents cause a computing system to perform a method for generating passwords, the method comprising:

determining a location of an alignment feature within a biometric information sample from an individual;

extracting features from the biometric information sample;

determining from the extracted features a first string of symbols based on locations of extracted features within the biometric information sample relative to the alignment feature;

determining a plurality of error strings in dependence upon predetermined parameters defining an error region about the extracted first string;

hashing the first string and at least some of the error strings from the determined plurality of strings to produce a plurality of hash values; and

comparing each produced hash value from the plurality of hash values with a predetermined stored hash value for determining a hash value from the plurality of hash values indicative of a match,

wherein upon a match between a hash value from the plurality of hash values and the stored hash value, the string from which the matching hash value was derived is provided as the generated password.

61. The computer-readable storage medium of claim 60, further comprising providing an indication of the alignment feature.

62. The computer-readable storage medium of claim 61 wherein providing an indication of the alignment feature includes selecting the alignment feature from a plurality of alignment features.

63. The computer-readable storage medium of claim 61 wherein providing an indication of the alignment feature includes selecting a region within the biometric information sample, the region being indicative of an alignment feature from a plurality of potential alignment features.