Source: http://www.google.com/patents/US8117462?dq=5,598,374
Timestamp: 2016-10-24 00:45:00
Document Index: 154611460

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 577', 'Application No. 2004', 'Application No. 03824536', 'Application No. 03824536', 'Application No. 03739087']

Patent US8117462 - Delivery point validation system - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsSystems 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...http://www.google.com/patents/US8117462?utm_source=gb-gplus-sharePatent US8117462 - Delivery point validation systemAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS8117462 B2Publication typeGrantApplication numberUS 11/231,787Publication dateFeb 14, 2012Filing dateSep 22, 2005Priority dateAug 21, 2000Fee statusPaidAlso published asUS7302582, US8291234, US8677140, US20040128274, US20060143434, US20080077804, US20130246804, WO2002017262A2, WO2002017262A3Publication number11231787, 231787, US 8117462 B2, US 8117462B2, US-B2-8117462, US8117462 B2, US8117462B2InventorsRobert F. Snapp, James D. WilsonOriginal AssigneeUnited States Postal ServiceExport CitationBiBTeX, EndNote, RefManPatent Citations (52), Non-Patent Citations (45), Referenced by (17), Classifications (21), Legal Events (1) External Links: USPTO, USPTO Assignment, EspacenetDelivery point validation system
US 8117462 B2Abstract
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 of the bits is low, then the inquiry item is determined not to be part of the original list.
1. A method for processing data using a computer, comprising:
receiving, by the computer, a data element including at least a name or an address;
forming, by the computer utilizing a cryptographic procedure, a cryptographic value from the data element;
extracting a plurality of samples from a binary representation of the cryptographic value, each of the plurality of samples comprising one or more bits of said binary representation of the cryptographic value, the samples identifying one or more bits of previously stored data, the previously stored data representing a list of valid data elements and being formed by the cryptographic procedure from the list;
querying whether the received data element is included in the list of the valid data elements;
checking bit values of the bits of the previously stored data based on each of the plurality of bit samples; and
determining, using the computer, whether the data element is included in the list based on a result of the checking.
2. The method of claim 1, wherein the cryptographic procedure comprises a hash function.
3. The method of claim 1, wherein each of the samples includes a first portion and a second portion, and the first portion and the second portion identify a bit of the previously stored data.
4. The method of claim 3, wherein the first portion identifies a block of the previously stored data, and the second portion identifies the bit with respect to the block.
determining that the data element is included in the list if the bit values of the bits identified by the extracted samples match a predetermined value.
6. The method of claim 4, wherein the block includes one or more bytes.
7. The method of claim 4, wherein each of the samples includes a plurality of bytes.
8. The method of claim 7, wherein the samples include a first sample and a second sample, and at least a portion of the first sample overlaps the second sample.
9. The method of claim 1, further comprising: normalizing the data element.
standardizing the data element; and
padding the standardized data element to a predetermined length.
the previously stored data include 2x bits, x being an integer number; and
each sample includes at least x bits.
triggering a process utilizing the data element, if a result of the checking indicates that the bit values of the bits of the previously stored data match a predetermined value.
13. The method of claim 1, wherein the samples include a first sample and a second sample, and at least a portion of the first sample overlaps the second sample.
15. A non-transitory computer-readable storage medium including program code, which, when executed by a processor, causes the processor to perform a method for processing data, the method comprising:
extracting a plurality of samples from a binary representation of the cryptographic value, each of the each of the plurality of samples comprising one or more bits of said binary representation of the cryptographic value, the samples identifying one or more bits of previously stored data, the previously stored data representing a list of valid data elements and being formed by the cryptographic procedure from the list;
16. The non-transitory computer-readable storage medium of claim 15, wherein the cryptographic procedure comprises a hash function.
17. the non-transitory computer-readable storage medium of claim 16, wherein each of the samples includes a first portion and a second portion, and the first portion and the second portion identify a bit of the previously stored data.
18. The non-transitory computer-readable storage medium of claim 17, wherein the first portion identifies a block of the previously stored data, and the second portion identifies the bit with respect to the block.
19. The non-transitory computer-readable storage medium of claim 17, wherein the method further comprises:
20. The non-transitory computer-readable storage medium of claim 17, wherein the block includes one or more bytes.
21. The non-transitory computer-readable storage medium of claim 17, wherein each of the samples includes a plurality of bytes.
22. The non-transitory computer-readable storage medium of claim 21, wherein the samples include a first sample and a second sample, and at least a portion of the first sample overlaps the second sample.
23. The non-transitory computer-readable storage medium of claim 15, wherein:
the previously stored data include 2x bits, x being an integer number; and each sample includes at least x bits.
24. A system for processing data comprising:
a receiver that receives a data item comprising at least a name or an address;
an encoder that forms, by utilizing a cryptographic procedure, a cryptographic value from the data element;
an extraction circuit that extracts a plurality of samples from a binary representation of the cryptographic value, each of the plurality of samples comprising one or more bits of said binary representation of the cryptographic value, the samples identifying one or more bits within previously stored data, the previously stored data representing a list of valid data elements and being formed by the cryptographic procedure from the list; and
a validation component that query whether the received data element is included in the list of the valid data elements, checks bit values of the bits of the previously stored data based on each of the plurality of bit samples, and determines whether the data element is included in the list based on a checking result.
25. The system of claim 24, wherein each of the samples includes a first portion and a second portion, and the first portion and the second portion identify a bit of the previously stored data.
26. The system of claim 25, wherein the first portion identifies a block of the previously stored data, and the second portion identifies the bit with respect to the block.
27. The system of claim 26, wherein the validation component further determines that the data element is included in the list if the bit values of the bits identified by the extracted samples match a predetermined value.
28. The system of claim 26, wherein the block includes one or more bytes.
29. The system of claim 26, wherein each of the samples includes a plurality of bytes.
This is a continuation of, and claims the benefit of, U.S. application Ser. No. 10/344,990, filed Feb. 20, 2003 now U.S. Pat. No. 7,302,582, which was the National Stage of International Application No. PCT/US01/26125, filed Aug. 21, 2001, which claims the benefits of U.S. Provisional Application No. 60/226,568, filed Aug. 21, 2000, U.S. Provisional Application No. 60/277,622, filed Mar. 22, 2001, and U.S. Provisional Application No. 60/281,411, filed Apr. 5, 2001, all of which are hereby incorporated herein by reference.
The present invention relates to a system and method for validating or confirming information.
Many occasions arise when validation or confirmation of information is desired before taking a particular action. For example, a person may want to confirm that an address is a valid address before sending a valuable item or sensitive information to the address. As another example, a delivery business may want to confirm an address before sending a product. There are also occasions when validating an address can be lifesaving. For example, fire departments, ambulance companies, and police departments may want to confirm an address to efficiently respond to an emergency. There are times when other types of information, besides addresses, need to be validated or confirmed. For example, a traffic officer may need to confirm that a driver's license is valid before permitting a person to drive.
Despite the need to validate or confirm information, in today's information technology age, businesses and individuals are concerned about privacy and information security. Furthermore, businesses consider information to be a valuable company asset. Because of the concerns about information security and the view that information is an asset, owners of information may want to keep their information private and secure. On the other hand, an owner of information may also want to exploit the information by providing the information to others. For example, an owner of information comprising a list of all persons with access to a building may want to provide the list to a security company so that the security company may confirm whether a person seeking entrance into the building is on the list. However, for privacy reasons, the owner may not want to reveal to the security company all persons on the list. That is, the owner may feel that the list should only be revealed one person at a time as a person seeks entrance to the building. If a person on the list never seeks entrance to the building, then the security company never needs to know that the person is on the list. Based on the above concerns, it would be advantageous if an owner of information could provide the information to others for inquiry purposes, the information being in an encrypted format so that information may remain confidential.
In accordance with the invention, there is provided a method for representing a list of items using a bit array wherein each bit in the bit array is initialized to a first value. The method comprises converting each item into a N-bit object and determining bit positions based on the N-bit object. The method further comprises setting bits of the bit array to a second value at the determined bit positions.
There is further provided a method for determining whether an inquiry item is on a list of items. The list of items is represented by a bit array having first and second values. The method comprises converting the inquiry item into a N-bit object in a same manner that an item on a list of items is converted to produce a bit array representing the list of items. The method further comprises determining bit positions based on the N-bit object in a same manner that bit positions are determined for producing the bit array. Still further, the method comprises determining that the inquiry item is on the list if the bits of the bit array equal a second value at the determined bit positions and determining that the inquiry item is not on the list if at least one bit of the bit array does not equal a second value at the predetermined bit positions.
FIG. 1 illustrates a process of converting a list of items into a bit array consistent with an embodiment of the present invention.
FIG. 2 illustrates a process of determining whether an inquiry item is on a list represented by a bit array consistent with an embodiment of the present invention.
FIG. 3 illustrates an encoder for encoding a list of items into a bit array consistent with an embodiment of the present invention.
FIG. 4 illustrates an exemplary method of extracting bit samples consistent with an embodiment of the present invention.
FIG. 5 illustrates a validation system for determining whether an inquiry item is on a list consistent with an embodiment of the present invention.
FIG. 6 illustrates an exemplary method of standardizing an address consistent with an embodiment of the present invention.
FIG. 7 illustrates an exemplary system network consistent with a disclosed embodiment.
Systems and methods consistent with the present invention encode a list so that users of the list may make inquires to the coded list without the entire content of the list being revealed to the users. FIG. 1 illustrates an example of a coded list 110 that may be derived from a list 105 based on an encoder 107 in accordance with the present invention. The list 105 may comprise addresses, names, license numbers, or any other type of information. In this example, the coded list 110 is an array of bits (i.e., 1, 2, 3, etc.) The size of the bit array 110 may be chosen to reduce the number of false positives that may result when a user makes an inquiry to the list 105, as discussed in greater detail below.
Each item 102 in the list 105 turns on one or more bits in the bit array 110. That is, initially all the bits in the bit array 110 are low and are changed to high based on an item 102 in the list 105. More specifically, each item 102 in the list 105, once encoded by encoder 107, indicates which bit or bits to turn on in the bit array 110 to represent the item 102. For example, the first item 102 in the list 105 may turn on bits 1, 3, 11, as shown in FIG. 1. The second item 102 in the list 105 may turn on bits 5, 7, and 10, and so on. Multiple items 102 in the list 105 may turn on the same bit. For example, a first, fourth, and tenth item 102 in the list 105 may turn on bit 11. Practically speaking, once a bit is turned on by an item 102, it remains on and is unaffected if other items 102 indicate that it should be turned on.
Each item 102 may turn on one or multiple bits in the bit array 110. In the example above, each item 102 turns on three (3) bits. However, a greater or lesser number of bits may be turned on for each item 102. The number of bits to turn on may be chosen to reduce the number of false positives that may result when a user makes an inquiry to the list 105, as discussed in greater detail below.
Once the encoder 107 has encoded each item 102 in the list 105, a bit array 110 with high and low values is used to represent the items 102 in the list 105. The bit array 110 may then be used by third parties for inquiry purposes without the content of the list 105 being revealed. Referring to FIG. 2, the bit array 110 may be embodied in a validation system 207 for allowing users to query the list 105 to determine whether an inquiry item 202 is on the list 105. For example, assume that the bit array 110 represents a list of all person with access to a building. Users of the bit array 110 may query the list 105 to determine whether a name is on the list 105 by inputting the name, i.e., the inquiry item 202, into the validation system 207. The validation system 207 may return a “yes” response, indicating that the name is on the list, or may return a “no” response, indicating the name is not on the list.
The inquiry item 202 undergoes the same encoding process that an original list item 102 undergoes. That is, the validation system 207 executes the same encoding process executed by the encoder 107. Recall that for the original list items 102, the encoder 107 determines which bits of the bit array 110 to turn on. For an inquiry item 202, the validation system 207 determines which bits of the bit array 110 to check. If all the bits checked are high, then the inquiry item 202 is determined to be part of the list. If at least one of the bits checked is low, then the inquiry item 202 is determined not to be part of the original list 105. For example, assume that that the validation system 207 processes the inquiry item 202, determining which bits to check. In FIG. 2A, the validation system 207 checks bits 1, 5, and 7. Because bits 1, 5, and 7 are all high, the validation system 207 determines that the inquiry item 202 is on the original list 105 and returns an affirmative. As another example, in FIG. 2B, the validation system 207 checks bits 2, 3, and 11. Because bit 2 is low, the validation system 207 determines that the inquiry item 202 is not on the original list 105 and returns a negative response. In this way, an owner of a list may provide a coded list to third parties to determine whether an item is on a list, without revealing the content of the list.
FIG. 7 illustrates an exemplary system network 700 in which to practice the present invention. The network 700 consists of a server 710, a workstation 720, and a communication link 730. The server 710 may store the bit array 110 and validation system 207 used to determine whether an inquiry item 202 is on a list 105. The workstation 720 may be a personal computer having a keyboard for inputting an inquiry item 202. The communication link 730 transmits the inquiry item 202 to the server 710 wherein the validation system 207 processes the inquiry item 202 and returns an affirmative or negative response via the communication link 730 to the workstation 720. The network 700 may be a local area network (LAN) or a wide area network (WAN) to include the Internet, for example. The network 700 may be wireless. In an alternate embodiment, a stand-alone workstation may store the bit array 110 and validation system 207 and a user may input an inquiry item 202 via the workstation's keyboard or other input device to determine locally whether the inquiry item 202 is on a list 105.
FIG. 3 illustrates an exemplary encoder 107 for encoding a list 105, resulting in an array of bits 110, as described above. The encoder 107 comprises a standardizer 310, a hashing function unit 320, an extraction circuit 330, and an offset circuit 340.
The standardizer 310 converts an input into a standard format prior to encoding. This step may be desirable for a list that may contain multiple variations of the same information. For example, a list that contains addresses may have multiple entries of the same address in different formats. It may be more efficient to encode a single representation of the same item than to encode each variation of the item. For instance, assume that multiple variations for an address are provided on a list. The entries include: 123 Main Street, Apartment 456; 123 Main St., Apt. 456; and 123 Main St., # 456. The standardizer 310 may convert each of these entries to 123 Main St. 456 and encode this representation of the address rather than encoding each variation of the address.
The standardizer 310 may standardize a list in accordance with the teachings disclosed in the provisional application entitled, “A Method For Standardizing A Mailing Address, Enhanced Modified Delivery Point”, by Robert Snapp, filed on Mar. 22, 2001, which is incorporated by reference. The provisional application discloses a method for standardizing a mailing address into a numeric string. As shown in FIG. 6, a mailing address may be standardized by concatenating the nine-digit zip code of the address; a seven digit segment comprising the address number (i.e., the primary number) preceding the address name and the address number (i.e., the secondary number) following the address name (e.g., the suite or apartment number); and a three digit segment comprising a numeric representation of up to two alphanumeric characters which may appear in the primary or secondary number (e.g., Apt. K). The seven-digit segment may be padded with leading zeros if the total number of digits in the primary number and secondary number is less than seven digits. For the three digit segment, the numeric representation of a single alphanumeric character in the primary or secondary number may be as follows: space=0, A=1, B−2, . . . , Z=26. The numeric representation of two alphanumeric characters in the primary or secondary number may be determined by multiplying the numeric value of the first alphanumeric character by 27 and then adding the value of the second alphanumeric character (e.g., AA=1�27+1; ZZ=26�27+26). It will be understood by those of ordinary skill in the art that a different standardization technique may be used to standardize a list of items.
Once a list item 102 is standardized, it is input to the hashing function unit 320. The hashing function unit 320 may execute a one-way hash function, i.e., a function that transforms an input item making it difficult to impossible to reproduce the input. For example, a one-way hash function may take an input and produce an N-bit object having no obvious relationship to the input. Furthermore, a hash function may produce significantly different outputs for similar, but not identical, inputs. In an exemplary embodiment, the hashing function unit 320 executes a secure hashing algorithm, SHA-1, which was developed by the National Institute of Standards and Technology (NIST) and is an ANSI standard encryption technique.
The SHA-1 transforms an input into a 160-bit (20 byte) object called a message digest. The SHA-1 sequentially processes blocks of 512 bits when computing the message digest. Therefore, the SHA-1 pads an input bit string to produce a bit string with a length that is a multiple, n, of 512 prior to processing the input bit string. The SHA-1 pads the input bit string by appending a “1” to the input bit string, followed by a number of “0”s depending on the original length of the input bit string, followed by a 64-bit integer representing the original length of the input bit string. The number of “0”s appended to the input bit string equals a number which will produce a bit string with a length that is a multiple of 512 once the “1”, the “0”s, and the 64-bit integer is added to the input bit string. For example, to pad an input bit string with a length of 40, a “1” is appended to the input bit string, followed by 407 “0”s, followed by a 64-bit integer representing the length of the input bit string (i.e., 40).
The padded input bit string is viewed as a sequence of n blocks M1, M2, . . . , Mn, where Mi contains 16 words. Constant words K0, K1, . . . , K79 are used in the SHA-1, where, in hex:
Kt = 5A827999
(0 ≦ t ≦ 19)
Kt = 6ED9EBA1
((20 ≦ t ≦ 39)
Kt = 8F1BBCDC
(40 ≦ t ≦ 59)
Kt = CA52C1D6
(60 ≦ t ≦ 79)
To generate the 160-bit message digest, the SHA-1 processes the blocks, Mi, for i=1, . . . , n. For each block, Mi, the SHA-1 computes constants words H0, H1, H2, H3, and H4. Initially, for block M1, H0=67452301, H1=EFCDAB89, H2=98BADCFE, H3=10325476, and H4=C3D2E1F0 (all in hex). Hj for j=0, 1, 2, 3, 4 for subsequent blocks, Mi, initially equals the Hj computed for the previous block. The H0, H1, H2, H3, and H4 computed for block Mn is the 160-bit message digest.
Each block, Mi, is processed in the following manner. First, block Mi is divided into 16 words, W0, W1, . . . ., W15. In addition, the following variables are initialized: A=H0, B=H1, C=H2, D=H3, and E=H4. For t=0 to 79, the SHA-1 computes the following equations:
After the above equations have been computed, Hj is computed as follows:
H 0 =H 0 +A H 1 =H 1 +B H 2 =H 2 +C H 3 =H 3 +D H 4 =H 4 +E As stated above, the H0, H1, H2, H3, and H4 computed for block Mn is the 160-bit message digest.
The extraction circuit 330 extracts multiple n-bit samples from the N-bit object input from the hashing function unit 320. If the size of the bit array 110 is equal to 2x bits, then the size of each sample extracted from the N-bit object should be equal to or greater than x bits. The number of samples to extract from the N-bit sample may correspond to the number of bits that are turned on during the encoding process for each list item 102. In the case of the SHA-1, for example, the extraction circuit 330 may extract nine (9) 32-bit samples from the 160-bit object input from the hashing function unit 320. FIG. 4 illustrates an example of how an extraction circuit 330 may extract multiple 32-bit samples 1 through 9 from a 160-bit object 410. Each number block (i.e., 0, 1, 2, etc.) represents a byte. The multiple n-bit samples extracted by the extraction circuit 330 are input to the offset circuit 340. It will be understood by a person of ordinary skill in the art that a different extraction technique may be employed.
The offset circuit 340 determines which bits in the bit array 110 to turn on based on the n-bit samples from the extraction circuit 330. Each n-bit sample turns on a bit in the bit array 110. Therefore, in FIG. 4, a total of 9 bits in the bit array 110 will be turned based on the bit samples 1 through 9, respectively. FIG. 4 illustrates how a 32-bit sample for the 160-bit object 410 may be used to determine which bit in a bit array 110 to turn on. As shown in FIG. 4, a 32-bit sample is divided into 2 objects. The first object comprises the leftmost three bits in the 32-bit sample. The second object comprises the remaining 29 bits in the 32-bit sample. The second object determines which byte in the bit array 110 contains the bit to be turned on. The first object determines which bit in the byte to turn on. For example, a second object may determine that the first byte of a bit array 110 contains the bit to be turned on. The first object may determine that the third bit of the first byte of the bit array 110 is to be turned on, as illustrated in FIG. 1. It will be understood by a person of ordinary skill in the art that a different technique may be employed to determine which bits to turn on in the bit array 110.
The encoder 107 may be implemented in software, firmware, hardware, or any combination thereof. The bit array 110 may be stored in any semi-permanent or permanent holding place for digital data, such as a magnetic disk (e.g., floppy disk or hard disk), optical disk (e.g., CD, CD-ROM, DVD-ROM), or magnetic tape.
As discussed above, the size of the bit array 110 or the number of bits the encoder 107 turns on may be chosen to reduce the number of false positives that may result when a user makes an inquiry to the list 105. False positives result when the validation system 207 returns an affirmative response although an inquiry item 202 is not on the list 105. This occurs because all the bits checked by the validation system 207 for the inquiry item 202 coincidentally where turned on by one or more other list items 102 during the encoding process. The probability of a false positive equals
( S M ) k , where M equals the number of bits in the bit array 110, S equals the total number of bits turned on in the bit array 110, and k equals the number of bits the encoder 107 turns on per list item 102. Furthermore, S, the total number of bits turned on in the bit array 110, is approximately equal to
M ( 1 - ⅇ - Nk M ) , where N equals the number of list items 102. M, the number of bits in the bit array 110, and k, the number of bits turned on per list item 102, may be chosen to minimize the number of false positives based on the above equations. However, a higher false positive rate above the minimum may be chosen based on other considerations such as processing speed.
FIG. 5 illustrates an exemplary validation system 207 for validating an inquiry item 202. As discussed above, the validation system 207 utilizes the same encoding process as used by the encoder 107. Therefore, the validation system 207 of FIG. 5 is similar to the encoder 107 of FIG. 3. The validation system 207 comprises a standardizer 510, a hashing function unit 520, an extraction circuit 530, and an offset circuit 540.
When an inquiry is made to determine whether an inquiry item 202 is on a list, it may be desirable to standardize the inquiry item 202 prior to determining whether the inquiry item 202 is on the list. If an inquiry item 202 is not standardized, the validation system 207 may incorrectly determine that the inquiry item 202 is not on the list simply because it is in a different format. The standardizer 510 may eliminate this problem by converting the inquiry item 202 into a standard format prior to validating. The standardizer 510 may operate in a same manner as the standardizer 310. Once an inquiry item 202 is standardized, it is input to the hashing function unit 520.
The hashing function unit 520 executes the same one-way hash function that is executed by the hashing function unit 320, generating an N-bit object. The N-bit object is input to the extraction circuit 530.
The extraction circuit 530 extracts multiple n-bit samples from the N-bit object in the same manner that the extraction circuit 330 extracts multiple n-bit samples. The multiple n-bit samples extracted by the extraction circuit 530 are input to the offset circuit 540.
The offset circuit 540 determines which bits in the bit array 110 to test based on the n-bit samples from the extraction circuit 530. The offset circuit 540 makes this determination in the same manner that the offset circuit 340 determines which bits in the bit array 110 to turn on. The validation system 207 tests the bits indicated by the offset circuit 540. As discussed above, if the bits tested are all high, then the validation system 207 determines that the inquiry item 202 is on the list 105; if at least one of the bits is low, then the validation system 207 determines that the inquiry item 102 is not on the list 105.
The validation system 207 may be implemented in software embodied locally in a workstation or in a server as shown in FIG. 2. Alternatively, the validation system 207 may be implemented in firmware, hardware, or any combination of software, firmware, and hardware.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4187551Nov 21, 1977Feb 5, 1980Ferranti LimitedApparatus for writing data in unique order into and retrieving same from memoryUS4290105Apr 2, 1979Sep 15, 1981American Newspaper Publishers AssociationMethod and apparatus for testing membership in a set through hash coding with allowable errorsUS4498148Feb 23, 1983Feb 5, 1985International Business Machines CorporationComparing input words to a word dictionary for correct spellingUS4538240Dec 30, 1982Aug 27, 1985International Business Machines CorporationMethod and apparatus for performing hashing operations using Galois field multiplicationUS4871903 *Jul 31, 1987Oct 3, 1989General Electric CompanyApparatus for rapidly accessing a large data base employing an optical disc reading system with multiple heads and track position compensation meansUS5204966Mar 9, 1990Apr 20, 1993Digital Equipment CorporationSystem for controlling access to a secure system by verifying acceptability of proposed password by using hashing and group of unacceptable passwordsUS5343529Sep 28, 1993Aug 30, 1994Milton GoldfineTransaction authentication using a centrally generated transaction identifierUS5420403May 26, 1992May 30, 1995Canada Post CorporationMail encoding and processing systemUS5491752Sep 2, 1994Feb 13, 1996Digital Equipment Corporation, Patent Law GroupSystem for increasing the difficulty of password guessing attacks in a distributed authentication scheme employing authentication tokensUS5742807May 31, 1995Apr 21, 1998Xerox CorporationIndexing system using one-way hash for document serviceUS5819291Aug 23, 1996Oct 6, 1998General Electric CompanyMatching new customer records to existing customer records in a large business database using hash keyUS5893120Jan 2, 1997Apr 6, 1999Nemes; Richard MichaelMethods and apparatus for information storage and retrieval using a hashing technique with external chaining and on-the-fly removal of expired dataUS5903651May 14, 1996May 11, 1999Valicert, Inc.Apparatus and method for demonstrating and confirming the status of a digital certificates and other dataUS5933604Nov 5, 1996Aug 3, 1999Fujitsu LimitedNetwork resource monitoring system and method for providing notice of changes in resources in a networkUS5953502Feb 13, 1997Sep 14, 1999Helbig, Sr.; Walter AMethod and apparatus for enhancing computer system securityUS5966542Aug 10, 1998Oct 12, 1999Sun Microsystems, Inc.Method and system for loading classes in read-only memoryUS6006200May 22, 1998Dec 21, 1999International Business Machines CorporationMethod of providing an identifier for transactionsUS6289334Jan 31, 1997Sep 11, 2001Sun Microsystems, Inc.Apparatus and method for decomposing database queries for database management system including multiprocessor digital data processing systemUS6289450May 28, 1999Sep 11, 2001Authentica, Inc.Information security architecture for encrypting documents for remote access while maintaining access controlUS6308247May 22, 1997Oct 23, 2001International Business Machines CorporationPage table entry management method and apparatus for a microkernel data processing systemUS6347376Aug 12, 1999Feb 12, 2002International Business Machines Corp.Security rule database searching in a network security environmentUS6457012Jun 10, 1997Sep 24, 2002Pitney Bowes Inc.Method and system of updating address records utilizing a clientserver interfaceUS6516320Mar 8, 1999Feb 4, 2003Pliant Technologies, Inc.Tiered hashing for data accessUS6625592Aug 10, 1999Sep 23, 2003Harris-Exigent, Inc.System and method for hash scanning of shared memory interfacesUS6675163Apr 6, 2000Jan 6, 2004International Business Machines CorporationFull match (FM) search algorithm implementation for a network processorUS6754785Nov 30, 2001Jun 22, 2004Yan Chiew ChowSwitched multi-channel network interfaces and real-time streaming backupUS6763344Apr 14, 2000Jul 13, 2004International Business Machines CorporationMethod of and system for dynamically controlling access to data recordsUS7062655Jan 23, 2002Jun 13, 2006International Business Machines CorporationMethod, system, and storage medium for determining trivial keyboard sequences of proposed passwordsUS7124408Jun 28, 2000Oct 17, 2006Microsoft CorporationBinding by hashUS7159119Jun 11, 2003Jan 2, 2007United States Postal ServiceMethod and system for efficiently retrieving secured data by securely pre-processing provided access informationUS7302582Aug 21, 2001Nov 27, 2007United States Postal ServiceDelivery point validation systemUS7350078Mar 4, 2002Mar 25, 2008Gary OdomUser selection of computer loginUS7587408Feb 28, 2003Sep 8, 2009United States Postal ServiceMethod and system for storing and retrieving data using hash-accessed multiple data storesUS20010044783Feb 16, 2001Nov 22, 2001Seth WeisbergOn-line value-bearing indicium printing using DSAUS20020049670Mar 9, 2001Apr 25, 2002Hitachi, Ltd.Electronic payment method and systemUS20030028783Jul 19, 2002Feb 6, 2003Mark CollinsSecurity systemUS20030177021Dec 4, 2002Sep 18, 2003Rana DuttaTraceable business reply envelopesUS20040065598Jun 16, 2003Apr 8, 2004Ross David JustinAddress disambiguation for mail-piece routingUS20040111443May 3, 2002Jun 10, 2004Wong Thomas K.Apparatus and methods for caching objects using main memory and persistent memoryUS20040128247Dec 16, 2003Jul 1, 2004Hitachi., Ltd.Bank system program, credit service program and IC cardUS20040181670Mar 10, 2003Sep 16, 2004Carl ThuneSystem and method for disguising dataUS20040210763Nov 6, 2003Oct 21, 2004Systems Research & DevelopmentConfidential data sharing and anonymous entity resolutionUS20050060556Dec 31, 2003Mar 17, 2005Jonas Jeffrey J.Authorized anonymous authenticationUS20050066182Mar 24, 2004Mar 24, 2005Systems Research & DevelopmentSecure coordinate identification method, system and programCN1311486AFeb 28, 2000Sep 5, 2001金容杰Comprehensive search method for intermediat station information in electronic trade businessDE4421640C1Jun 21, 1994Aug 3, 1995Siemens AgHash addressing and storage for distribution and recovery of dataEP0381418A2Jan 29, 1990Aug 8, 1990International Business Machines CorporationA small fast lookup table for use in a data processing systemJP2001043135A Title not availableJP2002202938A Title not availableJPH08235040A Title not availableJPH11306676A Title not availableWO2004023711A1Jun 11, 2003Mar 18, 2004United States Postal ServiceMethod and system for efficiently retrieving secured data by securely pre-processing provided access information* Cited by examinerNon-Patent CitationsReference1"Application of DB2 Anonymous Resolution to the Financial Services Industry," Whitepaper of IBM Corporation, USA, May 2005 (17 pages).2"DB2 Anonymous Resolution for Public Safety, Corrections, & Criminal Intelligence," Publication of IBM Corporation, USA, Feb. 2005 (2 pages).3"DB2 Anonymous Resolution," Publication of IBM Corporation, USA, May 2005 (2 pages).4"IBM DB2 Anonymous Resolution Version 3.8 Technical Information," Publication of IBM Corporation, USA, May 2005 (2 pages).5Bellare et al., "Collision-Resistant Hashing: Towards Making UOWHFs Practical," Advances in Cryptology Conference (CRYPTO); Germany; vol. Conf. 17, pp. 470-484, (1997).6Carter et al., "Exact and Approximate Membership Testers," ACM 10th STOC, pp. 59-65, (1978).7First Examination Report, dated Dec. 1, 2006, for India Patent Application No. 577/KOLNP/2005 (3 pages).8Friedrich, Andrew, "IBM DB2 Anonymous Resolution: Knowledge Discovery Without Knowledge Disclosure," Whitepaper of IBM Corporation, USA, May 2005 (23 pages).9International Search Report for PCT/US01/26125, 3 pages mailed Mar. 26, 2002.10Interview Summary, dated Nov. 30, 2004, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (2 pages).11Interview Summary, dated Sep. 21, 2005, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (2 pages).12Lohr, Steve, "I.B.M. Software Aims to Provide Security Without Sacrificing Privacy," The New York Times, May 24, 2005 (2 pages).13Notice of Allowance and Allowability, dated Jan. 13, 2009, for U.S. Appl. No. 11/235,243 (6 pages) with Response to Office Action, filed Nov. 12, 2008, including listing of allowed claims (18 pages).14Notice of Allowance and Allowability, dated Jul. 15, 2009, for U.S. Appl. No. 11/638,445 (6 pages), with Reply to Office Action, filed Nov. 14, 2008, including listing of allowed claims (19 pages).15Notice of Allowance and Allowability, dated Jul. 17, 2007, for U.S. Appl. No. 10/344,990 (6 pages).16Notice of Allowance and Allowability, dated Jun. 30, 2009, for U.S. Appl. No. 11/231,989 (12 pages).17Notice of Allowance and Allowability, dated May 17, 2006, for U.S. Appl. No. 10/459,013 (16 pages).18Notice of Allowance and Allowability, dated May 4, 2009, for U.S. Appl. No. 10/377,989 (4 pages).19Office Action, dated Apr. 15, 2005, for U.S. Appl. No. 10/377,989, filed Feb. 28, 2003 (4 pages).20Office Action, dated Apr. 4, 2006, for U.S. Appl. No. 10/344,990, filed Feb. 20, 2003 (8 pages).21Office Action, dated Aug. 7, 2008, for U.S. Appl. No. 11/231,989, filed Sep. 22, 2005 (15 pages).22Office Action, dated Jan. 5, 2010, in Japanese Patent Appl. No. 2007-000658, filed Jan. 5, 2007 (12 pages).23Office Action, dated Jul. 16, 2008, for U.S. Appl. No. 11/638,445, filed Dec. 14, 2006 (8 pages).24Office Action, dated Jun. 3, 2008, for U.S. Appl. No. 11/235,243, filed Sep. 27, 2005 (8 pages).25Office Action, dated Mar. 24, 2005, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (14 pages).26Office Action, dated May 20, 2010, in European Patent Appl. No. 03 739 087.9-1525, filed Apr. 6, 2005 (5 pages).27Office Action, dated May 26, 2009, for Japanese Application No. 2004-534223, filed Jun. 11, 2003 (9 pages).28Office Action, dated May 8, 2009, for Chinese Application No. 03824536.1, filed Jun. 11, 2003 (8 pages).29Office Action, dated Nov. 21, 2008, for Chinese Application No. 03824536.1, filed Jun. 11, 2003 (11 pages).30Office Action, dated Nov. 28, 2006, for U.S. Appl. No. 10/344,990, filed Feb. 20, 2003 (4 pages).31Office Action, dated Oct. 27, 2005, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (12 pages).32Office Action, dated Sep. 20, 2004, for U.S. Appl. No. 10/377,989, filed Feb. 28, 2003 (4 pages).33Office Action, dated Sep. 3, 2004, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (12 pages).34PCT International Examination Report, mailed Nov. 12, 2003 (completed Oct. 31, 2003), for International Application No. PCT/US03/06672 (4 pages).35PCT International Preliminary Examination Report, completed May 6, 2003, for International Application No. PCT/US01/26125 (4 pages).36PCT International Search Report, mailed Mar. 26, 2002, for International Application No. PCT/US01/26125 (4 pages).37PCT International Search Report, mailed May 23, 2003, for International Application No. PCT/US03/06672 (5 pages).38PCT International Search Report, mailed Oct. 17, 2003, for International Application No. PCT/US03/18412 (7 pages).39PCT Written Opinion, dated Sep. 7, 2006, for International Application No. PCT/US03/12711 filed Apr. 24, 2003 (8 pages).40PCT Written Opinion, mailed Aug. 2, 2004, for International Application No. PCT/US03/18412 (5 pages).41PCT Written Opinion, mailed Feb. 13, 2003, for International Application No. PCT/US01/26125 (4 pages).42Pre-Interview Communication, dated Sep. 12, 2008, for U.S. Appl. No. 11/231,989, filed Sep. 22, 2005 (3 pages).43Pre-Interview First Office Action, dated Dec. 2, 2008, for U.S. Appl. No. 11/231,989, filed Sep. 22, 2005 (3 pages).44Second Supplemental Preliminary Amendment, filed Aug. 20, 2008, for U.S. Appl. No. 11/231,989, filed Sep. 22, 2005, including listing of claims (9 pages).45Supplementary European Search Report, dated Feb. 17, 2009, for European Application No. 03739087.9-1525 (3 pages).Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8712922Feb 2, 2011Apr 29, 2014United Parcel Service Of America, Inc.Computer system for routing package deliveriesUS8712923Feb 2, 2011Apr 29, 2014United Parcel Service Of America, Inc.Computer system for routing package deliveriesUS8918340Apr 30, 2010Dec 23, 2014United Parcel Service Of America, Inc.Computer system for routing package deliveriesUS8924312Oct 8, 2010Dec 30, 2014United Parcel Service Of America, Inc.Computer system for routing package deliveriesUS9081672May 30, 2013Jul 14, 2015Richard Michael NemesMethods and apparatus for information storage and retrieval using a caching technique with external-chain hashing and dynamic resource-dependent data sheddingUS9430191Nov 8, 2013Aug 30, 2016Micron Technology, Inc.Division operations for memoryUS9437256Mar 17, 2015Sep 6, 2016Micron Technology, Inc.Data shiftingUS9449674May 26, 2015Sep 20, 2016Micron Technology, Inc.Performing logical operations using sensing circuitryUS9449675Oct 31, 2013Sep 20, 2016Micron Technology, Inc.Apparatuses and methods for identifying an extremum value stored in an array of memory cellsUS9455020May 18, 2015Sep 27, 2016Micron Technology, Inc.Apparatuses and methods for performing an exclusive or operation using sensing circuitryUS9466340Jan 23, 2015Oct 11, 2016Micron Technology, Inc.Apparatuses and methods for performing compare operations using sensing circuitryUS9472265Oct 8, 2015Oct 18, 2016Micron Technology, Inc.Apparatuses and methods for performing logical operations using sensing circuitryUS20040133446 *Oct 28, 2003Jul 8, 2004United Parcel Service Of America, Inc.Alternate delivery location methods and systemsUS20100223173 *Apr 30, 2010Sep 2, 2010United Parcel Service Of America, Inc.Computer system for routing package deliveriesUS20110029447 *Oct 8, 2010Feb 3, 2011United Parcel Service Of America, Inc.Computer system for routing package deliveriesUS20110125664 *May 26, 2011Nagesh KadabaComputer system for routing package deliveriesUS20110125665 *May 26, 2011Nagesh KadabaComputer system for routing package deliveries* Cited by examinerClassifications U.S. Classification713/189, 726/5, 713/192, 713/193, 726/2, 713/194, 713/190, 726/6, 713/191, 726/3, 726/4International ClassificationH04L9/00, G06F11/30, H04L9/32, G07B17/00, G06Q10/00Cooperative ClassificationG07B17/00435, G06F21/602, G06Q10/08, G07B2017/00725European ClassificationG06Q10/08Legal EventsDateCodeEventDescriptionAug 14, 2015FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services