Delivery point validation system

• US 8,291,234 B2
• Filed: 08/20/2007
• Issued: 10/16/2012
• Est. Priority Date: 08/21/2000
• Status: Active Grant

• Current Assignee: United States Postal Service (Government of the United States of America)
• Original Assignee: United States Postal Service (Government of the United States of America)
• Inventors: Snapp, Robert F., Wilson, James D.
• Primary Examiner(s): Arani, Taghi
• Assistant Examiner(s): Rahman, Mahfuzur
• Application Number:
  US11/892,175
• Publication Number:
  US 20080077804A1
• Time in Patent Office: 1,884 Days
• Field of Search: 713/186
• US Class Current: 713/186
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G07B 17/00435 Details specific to central, non-customer apparatus, e.g. servers at post office or vendor
• CPC Class Codes: G07B 2017/00725 Reading symbols, e.g. OCR

Abstract

Systems and methods consistent with the present invention encode a list so users of the list may make inquiries to the coded list without the entire content of the list being revealed to the users. Once each item in the list has been encoded by an encoder, a bit array with high and low values may be used to represent the items in the list. The bit array may be embodied in a validation system for allowing users to query the list to determine whether an inquiry item is on the list. The validation system determines which bits to check by executing the same coding process executed by the encoder. If all the bits are high, then the inquiry item is determined to be part of the list, if at least one bit is low, then the inquiry item is determined not to be part of the original list.

Claims

1. A method, implemented using a computer system, for representing a list comprising names using a bit array wherein bits in the bit array are initialized to a first value, comprising:

extracting portions of a name, using the computer system;

combining the portions, using the computer system, to create a standardized item that is smaller than the name from which the portions were extracted;

converting the standardized item to a cryptographic value using a cryptographic algorithm and the computer system;

extracting a plurality of n-bit samples from the cryptographic value, the n-bit samples including at least a first field and a second field, the first field identifying a group of bits of the bit array, and the second field identifying one or more bit positions within the group of bits; and

setting, using the computer system, bits at the bit positions to a second value according to the first field identifying the group of bits and the second field identifying the bit positions within the group of bits.

2. The method according to claim 1, further comprising:

storing the bit array on a device in communication with the computer system; and

determining whether an inquiry item is on the list by testing whether specific bits are set to the second value in the bit array as stored.

3. The method according to claim 1, wherein the converting comprises computing a hash function for the standardized item.

4. The method according to claim 3, wherein the hash function utilizes a secure hashing algorithm.

5. The method according to claim 1, wherein the group of bits is a byte.

6. The method according to claim 1, further comprising:

adding additional information not found in the name to at least one of the portions, using the computer system, wherein the additional information corresponds to information related to the name.

7. The method according to claim 1, wherein the converting comprises converting the standardized item to N-bit object.

8. A method, implemented using a computer system, for determining whether an inquiry item is on a list comprising names, wherein the names on the list have been standardized, wherein the list is represented by a bit array, and wherein the bit array was produced by converting the names into cryptographic values using a cryptographic algorithm and setting bits in the bit array to a set value based on bit samples of the cryptographic values, the method comprising:

standardizing an inquiry item, using the computer system, in a same manner as applied to the names on the list to create a standardized inquiry item;

converting the standardized inquiry item into a cryptographic value using the cryptographic algorithm and the computer system, in a same manner as the names are converted to produce the bit array;

extracting a plurality of n-bit samples from the cryptographic value, the n-bit samples including at least a first field and a second field, the first field identifying a group of bits of the bit array and the second field identifying one or more bit positions within the group of bits;

determining specific bits at the bit positions according to the first field identifying the group of bits and the second field identifying the bit positions within the group of bits; and

using the computer system, determining that the inquiry item is on the list if the specific bits at the bit positions of the bit array equal the set value and determining that the inquiry item is not on the list if at least one of the specific bits at the bit positions of the bit array does not equal the set value.

9. The method according to claim 8, further comprising outputting, using the computer system, a result indicating whether the inquiry item is or is not on the list.

10. The method according to claim 8, wherein the converting comprises computing a hash function for the standardized inquiry item.

11. The method according to claim 10, wherein the hash function utilizes a secure hashing algorithm.

12. The method according to claim 8, wherein the group of bits is a byte.

13. The method according to claim 8, wherein the standardizing an inquiry item comprises:

extracting portions of the inquiry item; and

combining the portions to create the standardized inquiry item.

14. The method according to claim 13, further comprising:

adding additional information not found in an inquiry item to at least one of the portions, using the computer system, wherein the additional information corresponds to information related to the inquiry item.

15. The method according to claim 8, wherein the cryptographic value is an N-bit object.

16. A computer for representing a list comprising names using a bit array wherein bits in the bit array are initialized to a first value, the computer comprising:

a memory having programming instructions; and

a processor, responsive to the programming instructions, configured to;

extract portions of a name;

combine the portions to create a standardized item;

convert the standardized item to a cryptographic value using a cryptographic algorithm;

extract a plurality of n-bit samples from the cryptographic value, the n-bit samples including at least a first field and a second field, the first field identifying a group of bits of the bit array, and the second field identifying one or more bit positions within the group of bits; and

set bits at the bit positions of the bit array to a second value according to the first field identifying the group of bits and the second field identifying the bit positions within the group of bits.

17. The computer according to claim 16, wherein the processor is further configured to:

store the bit array; and

determine whether an inquiry item is on the list by testing whether specific bits are set to the second value in the bit array as stored.

18. The computer according to claim 16, wherein the processor is further configured to convert the standardized item by computing a hash function for the standardized item.

19. The computer according to claim 18, wherein the hash function utilizes a secure hashing algorithm.

20. The computer according to claim 16, wherein the group of bits is a byte.

21. The computer according to claim 16, wherein the processor is further configured to add additional information not found in the name to at least one of the portions, wherein the additional information corresponds to information related to the name.

22. The method according to claim 16, wherein the cryptographic value is an N-bit object.

23. A computer for determining whether an inquiry item is on a list comprising names, wherein the names on the list have been standardized, wherein the list is represented by a bit array having bits set to a first value and bits set to a second value, and wherein the bit array was produced by converting the names into cryptographic values using a cryptographic algorithm and setting bits of the bit array to the second value based on bit samples of the cryptographic values, the computer comprising:

a memory having programming instructions; and

a processor, responsive to the programming instructions, configured to;

standardize an inquiry item in a same manner as applied to the names on the list to create a standardized inquiry item;

convert the standardized inquiry item into a cryptographic value using the cryptographic algorithm in a same manner as the names are converted to produce the bit array;

extract a plurality of n-bit samples from the cryptographic value, the n-bit samples including at least a first field and a second field, the first field identifying a group of bits of the bit array, and the second field identifying one or more bit positions within the group of bits;

determine specific bits at the bit positions of the bit array according to the first field identifying the group of bits and the second field identifying the bit positions within the group of bits; and

determine that the inquiry item is on the list if the specific bits at the bit positions of the bit array equal the second value and determine that the inquiry item is not on the list if at least one of the specific bits at the bit positions of the bit array does not equal the second value.

24. The computer according to claim 23, wherein the processor is further configured to output a result indicating whether the inquiry item is or is not on the list.

25. The computer according to claim 23, wherein the processor is further configured to convert the standardized inquiry item by computing a hash function for the standardized inquiry item.

26. The computer according to claim 25, wherein the hash function utilizes a secure hashing algorithm.

27. The computer according to claim 23, wherein the group of bits is a byte.

28. The computer according to claim 23, wherein the processor is further configured to:

extract portions of the inquiry item; and

combine the portions to create the standardized inquiry item.

29. The computer according to claim 28, wherein the processor is further configured to add additional information not found in an inquiry item to at least one of the portions, wherein the additional information corresponds to information related to the inquiry item.

30. The method according to claim 23, wherein the cryptographic value is an N-bit object.

31. A system for representing a list comprising names using a bit array wherein bits in the bit array are initialized to a first value, comprising:

a standardizer configured to extract portions of a name and combine the portions to create a standardized item;

a hashing function unit configured to convert the standardized item to a cryptographic value;

an extraction circuit configured to extract a plurality of n-bit samples from the cryptographic value, the n-bit samples including at least a first field and a second field, the first field identifying a group of bits of the bit array, and the second field identifying one or more bit positions within the group of bits; and

an offset circuit configured to set bits at the bit positions of the bit array to a second value according to the first field identifying the group of bits and the second field identifying the bit positions within the group of bits.

32. The system according to claim 31, further comprising:

a memory configured to store the bit array; and

a processor configured to determine whether an inquiry item is on the list by testing whether specific bits are set to the second value in the bit array as stored.

33. The system according to claim 31, wherein the hashing function unit is further configured to compute a hash function for the standardized item.

34. The system according to claim 33, wherein the hash function utilizes a secure hashing algorithm.

35. The system according to claim 31, wherein the group of bits is a byte.

36. The system according to claim 31, further comprising:

means for adding additional information not found in the name to at least one of the portions, wherein the additional information corresponds to information related to the name.

37. A system for determining whether an inquiry item is on a list comprising names, wherein names on the list have been standardized, wherein the list is represented by a bit array having bits that are set to a first value and bits that are set to a second value, and wherein the bit array was produced by converting the names into cryptographic values using a cryptographic algorithm and setting bits in the bit array to the second value based on bit samples of the cryptographic values, the system comprising:

a standardizer configured to standardize an inquiry item in a same manner as applied to the names on the list to create a standardized inquiry item;

a hashing function unit configured to convert the standardized inquiry item into a cryptographic value using the cryptographic algorithm in a same manner as the names are converted to produce the bit array;

an extraction circuit configured to extract a plurality of n-bit samples from the cryptographic value, the n-bit samples including at least a first field and a second field, the first field identifying a group of bits of the bit array, and the second field identifying one or more bit positions within the group of bits;

an offset circuit configured to determine specific bits at the bit positions in the bit array according to the first field identifying the group of bits and the second field identifying the bit positions within the group of bits; and

a processor configured to determine that the inquiry item is on the list if the specific bits at the bit positions of the bit array equal the second value and determine that the inquiry item is not on the list if at least one of the specific bits at the bit positions of the bit array does not equal the second value.

38. The system according to claim 37, further comprising means for outputting a result indicating whether the inquiry item is or is not on the list.

39. The system according to claim 37, wherein the hashing function unit is further configured to compute a hash function for the standardized inquiry item.

40. The system according to claim 39, wherein the hash function utilizes a secure hashing algorithm.

41. The system according to claim 37, wherein the group of bits is a byte.

42. The system according to claim 37, wherein the standardizer comprises:

means for extracting portions of the inquiry item in a same manner as applied to the names; and

means for combining the portions to create a standardized inquiry item in a same manner as applied to the names.

43. The system according to claim 42, further comprising:

means for adding additional information not found in an inquiry item to at least one of the portions, wherein the additional information corresponds to information related to the inquiry item.

44. The method according to claim 37, wherein the cryptographic value is an N-bit object.

45. A method, implemented using a computer system, for representing a list comprising license numbers using a bit array wherein the bit array is initialized to a first value, comprising:

extracting portions of a license number, using the computer system;

combining the portions, using the computer system, to create a standardized item that is smaller than the license number from which the portions were extracted;

converting the standardized item to a cryptographic value using a cryptographic algorithm and the computer system;

extracting a plurality of n-bit samples from the cryptographic value, the n-bit samples including at least a first field and a second field, the first field identifying a group of bits of the bit array, and the second field identifying one or more bit positions within the group of bits;

setting bits at the bit positions of the bit array to a second value according to the first field identifying the group of bits and the second field identifying the bit positions within the group of bits; and

storing the bit array for use in determining whether an inquiry item is on the list.

46. The method according to claim 45, wherein the converting comprises computing a hash function for the standardized item.

47. The method according to claim 45, wherein the group of bits is a byte.

48. The method according to claim 45, further comprising:

adding additional information not found in the license number to at least one of the portions, using the computer system, wherein the additional information corresponds to information related to a license corresponding to the license number.

49. The method according to claim 45, wherein the cryptographic value is an N-bit object.

50. A method, implemented using a computer system, for determining whether an inquiry item is on a list comprising license numbers, wherein the license numbers on the list have been standardized by extracting and combining portions of the license numbers, wherein the list is represented by a bit array, and wherein the bit array was produced by converting the license numbers into cryptographic values using a cryptographic algorithm and setting bits in the bit array to a set value based on bit samples of the cryptographic values, the method comprising:

extracting portions of the inquiry item, using the computer system, in a same manner as applied to the license numbers;

combining the portions to create a standardized inquiry item in a same manner as applied to the license numbers;

converting the standardized inquiry item into a cryptographic value using the cryptographic algorithm and the computer system in a same manner as the license numbers are converted to produce the bit array;

extracting a plurality of n-bit samples from the cryptographic value, the n-bit samples including at least a first field and a second field, the first field identifying a group of bits of the bit array, and the second field identifying one or more bit positions within the group of bits;

determining specific bits at the bit positions of the bit array according to the first field identifying the group of bits and the second field identifying the bit positions within the group of bits;

using the computer system, determining that the inquiry item is on the list if the specific bits at the bit positions of the bit array equal the set value and determining that the inquiry item is not on the list if at least one of the specific bits at the bit positions of the bit array does not equal the set value; and

outputting a result, using the computer system, indicating whether the inquiry item is or is not on the list.

51. The method according to claim 50, wherein the converting comprises computing a hash function for the standardized inquiry item.

52. The method according to claim 50, wherein the group of bits is a byte.

53. The method according to claim 50, further comprising:

adding additional information not found in an inquiry item to at least one of the portions, using the computer system, wherein the additional information corresponds to information from a license corresponding to the license number.

54. The method according to claim 50, wherein the cryptographic value is an N-bit object.