Abstract:
A computer-implemented method represents a list of informational items using a bit array. The method converts an informational item to a cryptographic value using a cryptographic algorithm and extracts a plurality of n-bit samples from the cryptographic value. The n-bit samples includes at least a first field and a second field. The first field identifies a group of bits of the bit array and the second field identifies one or more individual bits within the group of bits. The individual bits are set to a pre-determined value according to the first field identifying the group of bits and the second field identifying the individual bits within the group of bits.

Description:
This is a continuation of, and claims the benefit of, U.S. application Ser. No. 11/892,175, filed Aug. 20, 2007, now U.S. Pat. No. 8,291,234 which was a continuation 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 incorporated herein by reference. 
    
    
     DESCRIPTION OF THE INVENTION 
     Field of the Invention 
     The present invention relates to a system and method for validating or confirming information. 
     Background of the Invention 
     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&#39;s license is valid before permitting a person to drive. 
     Despite the need to validate or confirm information, in today&#39;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. 
     SUMMARY OF THE INVENTION 
     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. 
     Additional objects and advantages of the invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate one embodiment of the invention and together with the description, serve to explain the principles of the invention. 
         FIG. 1  illustrates a process of converting a list of items into a bit array consistent with an embodiment of the present invention. 
         FIGS. 2A and 2B  illustrate 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 that may be used to practice the invention. 
     
    
    
     DESCRIPTION OF THE EMBODIMENTS 
     Reference will now be made in detail to the present embodiment of the invention, an example of which is illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like parts. 
     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&#39;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 No. 60/277,622 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 M 1 , M 2 , . . . , M n , where M i  contains 16 words. Constant words K 0 , K 1 , . . . , K 79  are used in the SHA-1, where, in hex,: 
     K t =5A827999 (0≦t≦19) 
     K t =6ED9EBA1 ((20≦t≦39) 
     K t =8F1BBCDC (40≦t≦59) 
     K t =CA52C1D6 (60≦t≦79) 
     To generate the 160-bit message digest, the SHA-1 processes the blocks, M i , for i=1, . . . , n. For each block, M i , the SHA-1 computes constants words H 0 , H 1 , H 2 , H 3 , and H 4 . Initially, for block M 1 , H 0 =67452301, H 1 =EFCDAB89, H 2 =98BADCFE, H 3 =10325476, and H 4 =C3D2E1F0 (all in hex). H j  for j=0, 1, 2, 3, 4 for subsequent blocks, M i , initially equals the H j  computed for the previous block. The H 0 , H 1 , H 2 , H 3 , and H 4  computed for block M n  is the 160-bit message digest. 
     Each block, M i , is processed in the following manner. First, block M i  is divided into 16 words, W 0 , W 1 , . . . , W 15 . In addition, the following variables are initialized: A=H 0 , B=H 1 , C=H 2 , D=H 3 , and E=H 4 . For t=0 to 79, the SHA-1 computes the following equations:
 
TEMP= S   5 ( A )+ f   t ( B,C,D )+ E+W   t   +K   t  
 
 E=D;D=C;C=S   30 ( B ); B=A;A =TEMP
 
     where:
         S n (X) is a circular shift of X by n positions to the left   f t (B,C,D)=(B^C) v (˜B^D) (0≦t≦19)   f t (B,C,D)=B XOR C XOR D (20≦t≦39)   f t (B,C,D)=(B^C) v (B^D) v (C^D) (40≦t≦59)   f t (B,C,D)=B XOR C XOR D (60≦t≦79)   W t =S 1 (W t-3  XOR W t-8  XOR W t-14  XOR W t-16 ) (16≦t≦79)   X^Y=bitwise logical “and” of X and Y   X v Y=bitwise logical “inclusive-or” of X and Y   X XOR Y=bitwise logical “exclusive-or” of X and Y   ˜X=bitwise logical “complement” of X   X+Y=(x+y) mod 2 32  converted to a word, where x is the integer of X and y is the integer of Y.       

     After the above equations have been computed, H j  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 H 0 , H 1 , H 2 , H 3 , and H 4  computed for block M n  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 2 x  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 on 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  202  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. 7 . Alternatively, the validation system  207  may be implemented in firmware, hardware, or any combination of software, firmware, and hardware. 
     Other embodiments of the invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and examples be considered as exemplary only, with a true scope and spirit of the invention being indicated by the following claims.