Privacy preserving data search

CROSS REFERENCE TO RELATED APPLICATIONS

0001This application is a continuation of U.S. application Ser. No. 15/697,031, filed Sep. 6, 2017, now U.S. Pat. No. 10,242,216, which application is a continuation of U.S. application Ser. No. 14/034,470, filed Sep. 23, 2013, now U.S. Pat. No. 9,785,786, which application claims the benefit of Provisional Application No. 61/704,667 filed on Sep. 24, 2012, all of which are incorporated herein by reference in their entirety.

FIELD OF ART

0002This disclosure relates to database security, and in particular, to providing increased database search security through data indexing.

BACKGROUND

0003Many devices, websites, services, and applications implement various data protection techniques. Certain techniques involve the use of an encryption key or password that can be subject to interception or brute force guessing. Other methods may protect data but require extensive computing resources to encode and decode data. Such methods often fail to utilize various data format or indexing advantages when protecting the data. Often, systems implementing data protection techniques are required to protect date information, but also allow for different level of access to search the protected data based on a user's access rights. Thus, it may be advantageous to implement data protection techniques that allow the data to be searched with different access levels.

SUMMARY

0004A database management system is configured to protect data stored in a database by using access rights based indexing and searching in combination with encryption and tokenization of the data. The database management system maintains a plurality of indices for data in a database table, each index have a specific level of granularity relative to the data that each index value maps to. Each index stores one or more references to the location of data associated with each reference. For example, data that is organized into cells in a table having numbered rows and columns can be indexed by a row index that includes row numbers as values and a column index that includes column numbers as values.

0005The granularity of a database index is based upon a measure of the number of data entries associated with each index value, for example the average number of data entries for each index value. Indices with high granularity have on average a low number of data entries per index value, while indices with low granularity have a high number of data entries per index value. The granularity for an index is indirectly controlled by the range of index values, where a wider range allows for a higher granularity. For example, a “month” index that associates all date entries within a given month with a single index value necessarily has a higher granularity than a “day” index which associates all date entries with a given day with the corresponding “day” index value.

0006The database management system determines which indices to use for searching the database based on the level access rights of a user requesting the search. For a user having a high level of access rights, the search system performs a user search of the data using an index of high granularity, resulting in fewer and more relevant search results being returned to the user. Likewise, for a user having a low level of access rights the search system performs a user search of the data using an index of low granularity, resulting in a greater number of search results being returned. Returning a greater number of search results increases the ambiguity of individual data, resulting in an increase in privacy of sensitive information associated with the results.

0007In one embodiment, searching a database indexed with a plurality of indexes is implemented by a computer system. The computer system utilizes multiple indexes, each indexing a portion of the database. Each index is associated with a different level of access rights of a user to the database. The computer system receives a query to search the indexed portion of the database from a user. The computer system then determines the level of access rights associated with the user. The computer system selects a particular index based on the determined level of access rights. Based on the selected index the system maps the query to a search key based. The mapping translates the query into values and a format that the computer system can compare with the values of the selected index when searching the index. Upon determining a match between the search key and values of the selected index, the computer system outputs data that is associated with the matched values.

0008The features and advantages described in this summary and the following detailed description are not all-inclusive. Many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims hereof.

BRIEF DESCRIPTION OF DRAWINGS

0009<figref idref="DRAWINGS">FIG. 1</figref> is a system environment diagram for an information retrieval system, according to one embodiment.

0010<figref idref="DRAWINGS">FIG. 2</figref> illustrates non-hashed and hashed examples of an indexed database within the information retrieval system of <figref idref="DRAWINGS">FIG. 1</figref>, according to one embodiment.

0011<figref idref="DRAWINGS">FIG. 3</figref> illustrates data search and retrieval within the information retrieval system of <figref idref="DRAWINGS">FIG. 1</figref> by users having different levels of access rights, according to one embodiment.

0012<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart illustrating the process of searching an indexed database within the information retrieval system of <figref idref="DRAWINGS">FIG. 1</figref>, according to one embodiment.

0013The figures (Figs.) depict embodiments for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein can be employed without departing from the principles of the invention described herein.

DETAILED DESCRIPTION

0014Reference will now be made in detail to several embodiments, examples of which are illustrated in the accompanying figures. It is noted that wherever practicable, similar or like reference numbers can be used in the figures and can indicate similar or like functionality. The figures depict embodiments of the disclosed system (or method) for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein can be employed without departing from the principles described herein.

Information Retrieval Overview

0015Data in a database can be protected through various means of information retrieval, for instance using access rights based indexing and searching in addition to hashing any search indexes. The database management system indexes data entries within a database using a set of index values and mapping each database entry to one or more of the index values. A search of indexed data identifies one or more index values associated with the search, and will return all database entries that are mapped to the identified one or more index values. In one embodiment, the shorter the length of index values, the greater the number of database entries that are mapped to each index value, and the greater the number of results returned in response to performing a search of the indexed data (and, thereby, the lower the granularity of the index).

0016The granularity of an index refers to the average number of database entries mapped to each index value. An index with fewer index values will have a relatively large number of database entries are mapped to each index value, and is said to have low or coarse granularity. Conversely, an index with more index values will tend to have a relatively smaller number of database entries mapped to each index value, and is said to have high or fine granularity. Performing a search on an index with a low granularity results in (on average) a greater number of, and often less relevant, search results. Likewise, performing a search on an index with a high granularity results in (on average) a smaller number of, and often more relevant, search results.

0017All or part of the data stored in a database may be indexed. In addition, multiple indexes may be used to index portions of the data within the database, and portions of the database may be indexed with multiple indexes. In one embodiment, each column in a database is indexed using multiple different indexes having different granularities. Any type of data index may be used herein, such as a non-clustered index, a clustered index, a bitmap index, a dense index, a sparse index, a reverse index, and the like. The mapping of database entries to index values may be based on all or part of the database entries. It should be noted that although the embodiments described herein refer to data organized in rows and columns within a database, the operations described herein at equally applicable to any form or format of data.

0018As used herein, a value of an index refers to a string of characters, including but not limited to numeric, symbolic, or alphanumeric characters, and the like. An index value can have the same number of characters as the string of the data that it references, or can have a different number of characters. Further, the index value can have characters of the same type (such as numeric, symbolic, or alphanumeric characters) as the string of characters that the value references or characters of a different type.

0019A search key is used to query an index. A search key can be subject to format and content restrictions. For instance, if an index includes only numeric values, each mapped to one or more database entries, a user query must be mapped to a search key including only numeric values prior to searching the index. A search key therefore depends on the search query and the searched index, and the search query uniquely maps to a particular search key.

0020An index can have a variable granularity, where the number of data entries that are mapped to each index value varies. For instance, if a listing of names contains a disproportionately large number of names that begin with “J” and very few names that begin with “K,” a search query beginning with “K” will return fewer results than a search query beginning with “J.”

0021Such a variable granularity can be overcome by increasing the possible range of index values that an index encompasses. For instance, an index may be designed that maps names beginning with “J” to an index value based on the first two letters of the name (e.g., “Ja” and “Jb” would map to different index values), but maps names beginning with “K” to an index value based only on the first letter of the name (e.g., all names beginning with “K” map to the same index value). Though the database illustrated in <figref idref="DRAWINGS">FIGS. 2 and 3</figref> is small for the purposes of simplicity, a typical large database may have a million or more entries per index value with hundreds or more indexes. In such a database, an index may have thousands or more unique index values, each mapped to (on average) a thousand or more database entries.

0022The index used for searching data within an indexed database is based on the level of access rights associated with a user. By limiting the use of high granularity indexes to users with high levels of access rights, the indexed data is protected from users with low levels of access rights, thereby preserving the privacy associated with the data. For instance, searching data using a low granularity index results in less-specific or relevant and more data entries being returned than searching the same data using a high granularity index, increasing the ambiguity of the returned data entries, and increasing the privacy of each individual data entry.

0023For example, if a user queries a database including names for a person named “Johnson”, and the search system uses a low granularity index to search the data, all names beginning with “J” may be returned. If the data is encrypted, tokenized, or otherwise protected, returning the protected names beginning with “J” will not enable a user to identify the number of “Johnson” names listed in the database, but instead will only enable a user to identify the number of “J” names, increasing the privacy of the individuals listed in the database. Any type of tokenization (described below) or encryption (as known in the art) may be used to protect data within a data in conjunction with the invention described herein.

0024A user's level of access rights can be based on any suitable criteria, such as employment, status, position, rank, or any other criteria or property of the user. In one embodiment where data is indexed using an index of low granularity, an index of medium granularity, and an index of high granularity, an information retrieval system is adopted to use the index of low granularity for a user with basic or limited access rights (e.g., a non-employee), the index of medium granularity for a user with greater access rights (e.g., a non-manager employee), and the index of high granularity for a user with the highest level of access rights (e.g., a manager, executive, database administrator). Prior to a data search of the information retrieval system a user's access rights is authenticated or determined using user credentials (such as a password or keycard), an authorization database (storing access rights for users), or any other means suitable to authenticate a user. A user's access rights may vary among different columns, rows, fields, or databases searched.

Tokenization Overview

0025As used herein, the tokenization of data refers to the generation of tokenized data by querying one or more token tables mapping input values to tokens with the one or more portions of the data, and replacing the queried portions of the data with the resulting tokens from the token tables. Tokenization can be combined with encryption for increased security, for example by encrypting sensitive data using a mathematically reversible cryptographic function (e.g., data type-preserving encryption or DTP), a one-way non-reversible cryptographic function (e.g., a hash function with strong, secret salt), or a similar encryption before or after the tokenization of the sensitive data. Any suitable type of encryption can be used in the tokenization of data. A detailed explanation of the tokenization process can be found in U.S. patent application Ser. No. 13/595,439, filed Aug. 27, 2012, which is hereby incorporated by reference.

0026As used herein, the term token refers to a string of characters mapped to an input string of characters in a token table, used as a substitute for the string of characters in the creation of tokenized data. A token can have the same number of characters as the string being replaced, or can have a different number of characters. Further, the token can have characters of the same type (such as numeric, symbolic, or alphanumeric characters) as the string of characters being replaced or characters of a different type.

0027Any type of tokenization can be used to perform the functionalities described herein. One such type of tokenization is static lookup table (“SLT”) tokenization. SLT tokenization maps each possible input values (e.g., possible character combinations of a string of characters) to a particular token. An SLT includes a first column comprising permutations of input string values, and can include every possible input string value. The second column of an SLT includes tokens, with each associated with an input string value of the first column. Each token in the second column can be unique among the tokens in the second column. Optionally, the SLT can also include one or several additional columns with additional tokens mapped to the input string values of the first column.

0028In some embodiments, to increase the security of tokenization, sensitive data can be tokenized two or more times using the same or additional token tables. For example, the first 8 digits of a 16 digit credit card number can be tokenized with an 8 digit token table to form first tokenized data, and the last 12 digits of the first tokenized data can be tokenized using a 12 digit token table to form second tokenized data. In another example, the first 4 digits of a credit card number are tokenized using a first token table, the second 4 digits are tokenized with a second token table, the third 4 digits are tokenized with a third token table, and the last 4 digits are tokenized with a fourth token table. Certain sections of the sensitive data can also be left un-tokenized; thus a first subset of the resulting tokenized data can contain portions of the sensitive data and a second subset of the tokenized data can contain a tokenized version of the sensitive data.

0029Dynamic token lookup table (“DLT”) tokenization operates similarly to SLT tokenization, but instead of using static tables for multiple tokenizations, a new token table entry is generated each time sensitive data is tokenized. A seed value can be used to generate each DLT. In some embodiments, the sensitive data or portions of the sensitive data can be used as a seed value to generate a DLT. DLTs can in some configurations provide a higher level of security compared to SLT but require the storage and/or transmission of a large amount of data associated with each of the generated token tables. While DLT tokenization can be used to tokenize data according to the principles described herein, the remainder of the description will be limited to instances of SLT tokenization for the purposes of simplicity.

0030The security of tokenization can be further increased through the use of initialization vectors (“IVs”). An initialization vector is a string of data used to modify sensitive data prior to tokenizing the sensitive data. Example sensitive data modification operations include performing linear or modulus addition on the IV and the sensitive data, performing logical operations on the sensitive data with the IV, encrypting the sensitive data using the IV as an encryption key, and the like. The IV can be a portion of the sensitive data. For example, for a 12-digit number, the last 4 digits can be used as an IV to modify the first 8 digits before tokenization. IVs can also be accessed from an IV table, received from an external entity configured to provide IVs for use in tokenization, or can be generated based on, for instance, the identity of a user, the date/time of a requested tokenization operation, based on various tokenization parameters, and the like. Data modified by one or more IVs that is subsequently tokenized includes an extra layer of security—an unauthorized party that gains access to the token tables used to tokenized the modified data will be able to detokenize the tokenized data, but will be unable to de-modify the modified data without access to the IVs used to modify the data.

Information Retrieval System

0031<figref idref="DRAWINGS">FIG. 1</figref> is a system environment diagram for an information retrieval system, according to one embodiment. The environment of <figref idref="DRAWINGS">FIG. 1</figref> includes an information retrieval system <b>100</b>, one or more users (or clients) <b>110</b>, and a privacy server <b>115</b>, communicatively coupled through a connecting network <b>105</b>. A user or other entity can use a client <b>110</b> to access the information retrieval system <b>100</b> via the network <b>105</b>. Other embodiments of the system environment can contain different and/or additional components than those shown by <figref idref="DRAWINGS">FIG. 1</figref>.

0032A client <b>110</b> is a computing device capable of processing data as well as transmitting data to and receiving data from the other modules of <figref idref="DRAWINGS">FIG. 1</figref> via the network <b>105</b>. For example, the client <b>110</b> can be a desktop computer, laptop computer, smart phone, tablet computing device, server, payment terminal, or any other device having computing and data communication capabilities. Each client <b>110</b> includes one or more processors, memory, storage, and networking components. Each client <b>110</b> is coupled to the network <b>105</b> and can interact with other modules coupled to the network <b>105</b> using software such as a web browser or other application with communication functionality. Such software can include an interface for communicating with the other modules via the network <b>105</b>. In some embodiments of the environment of <figref idref="DRAWINGS">FIG. 1</figref>, there can be any number of the clients <b>110</b>, privacy servers <b>115</b>, and information retrieval systems <b>100</b> connected to the network <b>105</b> and communicating with one or more other modules.

0033The network <b>105</b> connecting the various modules is typically the Internet, but can be any network, including but not limited to a local area network (LAN), metropolitan area network (MAN), wide area network (WAN), cellular network, wired network, wireless network, private network, virtual private network (VPN), direct communication line, and the like. The network <b>105</b> can also be a combination of multiple different networks.

0034The client <b>110</b> is configured to access data from the information retrieval system <b>100</b>, for instance as part of a search request or query of data records contained within the information retrieval system <b>100</b>, and is configured to provide the search query to the information retrieval system <b>100</b>. The information retrieval system <b>100</b> is configured to receive the search query, to search the data contained within the system <b>100</b>, and to provide results of the search back to the client <b>110</b> that requested the search, or to another client <b>110</b> or entity (such as a bank server, a merchant, and the like). The information retrieval system <b>100</b> includes an interface module <b>120</b>, a search module <b>130</b>, an indexing engine <b>140</b>, an encryption module <b>150</b>, and an indexed database <b>160</b> of indexes and data.

0035The interface module <b>120</b> provides an interface that allows an operator of the information retrieval system to interact with the modules of the information retrieval system <b>100</b>, and is one means for performing this function. To provide an interface to the modules of the information retrieval system <b>100</b>, the interface module <b>120</b> is communicatively coupled to the search module <b>130</b>, the indexing engine <b>140</b>, the encryption module <b>150</b>, and the indexed database <b>160</b> of indexes and data.

0036An operator can, for example, specify various parameters that determine the way the search query received by the information retrieval system <b>100</b> is mapped to a search key and hashed. For example, the operator can select via a graphic user interface provided by the interface module <b>120</b> an index table and/or hash table from the indexed database <b>160</b>. The selected index table and/or hash table can be used by the indexing engine <b>140</b> to convert a search query into a hashed search key based on the granularity of the search. Similarly, an operator can select via the interface module <b>120</b> one or more granularity rules specifying the levels of access rights and corresponding indexes or index tables representing the specified granularity, a search input format, or a search output format. In one embodiment, the encryption module <b>150</b> may require an encryption key for use in decrypting encrypted data contained in the database <b>160</b>, or to encrypt parts of the outputted search results. An operator can provide such an encryption key via the interface module <b>120</b>.

0037The search module <b>130</b> is configured to receive search query and output the search results, and is one means for performing this function. When the information retrieval system <b>100</b> receives a search request from the client <b>110</b>, it provides the search query to the search module <b>130</b>, which generates a search key based on the search query. In some embodiments, generating a search key includes converting search query text into a format used to index data in the indexed database <b>160</b>, hashing or encrypting search query text prior to searching the indexed database <b>160</b>, and the like.

0038Upon mapping the search query to the search key, the search module <b>130</b> identifies and accesses an index for use in searching the indexed database <b>160</b>, and is one means for performing this function. The search module <b>130</b> is configured to look up a level of access rights associated with the user requesting the search from a authentication module (not shown) that sets the level of access rights for a given user, for instance based on user authentication information (such as a password and/or user credentials). The search module <b>130</b> identifies an index based on the determined level of access rights, and accesses the queries the identified index using the search key. In embodiments, in which the indexes used to index the data in the indexed database <b>160</b> are hashed, the search module <b>130</b> is configured to hash the search key prior to querying the identified index.

0039The indexing engine <b>140</b> generates a plurality of indexes for data stored in the indexed database <b>160</b>, and is one means for performing this function. Each index is associated with a level of access rights. The indexing engine <b>140</b> can also access one or more hash tables, and can hash the indexes used to index the data in the indexed database <b>160</b>. In some embodiments, the indexing engine <b>140</b> can receive indexes and/or hash tables from the privacy server <b>115</b> via the network <b>105</b> for use in generating the indexes. The indexing engine <b>140</b> can periodically re-generate the indexes, and/or can periodically re-hash the indexes, for instance ever 6 hours or once a day. The indexed database <b>160</b> stores the indexes associated with the levels of access rights, and the indexed data.

0040The encryption module <b>150</b> encrypts data, indexes, hashes and other information stored in the indexed database <b>160</b>, and is one means for performing this function. In some embodiments, the encryption preserves the data type of the original unencrypted data by using only a certain character set and maintaining the length of the encrypted data, though in practice any type or format of encryption can be used. In embodiments where the indexed data is encrypted, the encryption module <b>150</b> can decrypt the data prior to returning search results, or can return encrypted search results. In embodiments with encrypted indexes, the encryption module <b>150</b> can decrypt the indexes prior to querying the indexes, or can encrypt the search key prior to querying the indexes. The encryption module <b>150</b> may encrypt the search key using an encryption key provided by a querying user in a search request. In such embodiments, queries made with a search key encrypted with an incorrect encryption key may return incorrect results or no results, while queries made with a search key encrypted with the correct encryption key will return correct results. Such embodiments provide an additional layer of security by guaranteeing correct results only to queries that include the same encryption key used to encrypt an index.

0041The information retrieval system <b>100</b> may be implemented using a single computer, or a network of computers, including cloud-based computer implementations. The operations of the information retrieval system <b>100</b> as described herein can be controlled through either hardware or through computer programs installed in computer storage and executed by the processors of such servers to perform the functions described herein. The information retrieval system <b>100</b> includes other hardware elements necessary for the operations described here, including network interfaces and protocols, input devices for data entry, and output devices for display, printing, or other presentations of data. The functions and operations of the information retrieval system <b>100</b> are sufficiently complex as to require implementation on a computer system, and cannot be performed in the human mind simply by mental steps.

Protection of Private Data Using Multiple Granularity Database Indices

0042<figref idref="DRAWINGS">FIG. 2</figref> illustrates non-hashed and hashed examples of an indexed database, <b>160</b><i>a </i>and <b>160</b><i>b, </i>respectively, within the information retrieval system of <figref idref="DRAWINGS">FIG. 1</figref>, according to one embodiment. Each example database <b>160</b><i>a </i>and <b>160</b><i>b </i>includes a name column <b>210</b><i>a </i>and <b>210</b><i>b </i>within tables <b>220</b><i>a </i>and <b>220</b><i>b. </i>The name column <b>210</b><i>a </i>holds clear text data, whereas the name column <b>210</b><i>b </i>contains encrypted data. As illustrated, the name column <b>210</b><i>a </i>in the database includes the clear text surnames “Johnson”, “Johnson”, “Janson”, and “Anderson”. The encryption module <b>150</b> encrypts the clear text names of column <b>210</b><i>a </i>and stores them in column <b>210</b><i>b </i>as the encrypted values “LXwv+NiGiaQ=”, “LXwv+NiGiaQ=”, “02enc1MV1/o=”, and “3Rbi5hSHFjU=”.

0043Name column <b>210</b><i>a </i>is indexed using three different non-hashed indexes: index<b>1</b>(<i>a</i>), index<b>2</b>(<i>a</i>) and index<b>3</b>(<i>a</i>), whereas name column <b>210</b><i>b </i>uses three respective hashed indexes: index<b>1</b>(<i>b</i>), index<b>2</b>(<i>b</i>) and index<b>3</b>(<i>b</i>). The index<b>1</b>(<i>a</i>) is based on the clear text value of the first character of the name column entries from the name column <b>210</b><i>a, </i>the index<b>2</b>(<i>a</i>) is based on the clear text value of the first two characters of the name column entries from the name column <b>210</b><i>a, </i>and the index<b>3</b>(<i>a</i>) is based on the clear text value of the first three characters of the name column entries from the name column <b>210</b><i>a. </i>Of the three indexes, the index<b>3</b>(<i>a</i>) has the highest level of granularity, and the index<b>1</b>(<i>a</i>) has the lowest level of granularity.

0044The indexed values in index<b>1</b>(<i>a</i>), index<b>2</b>(<i>a</i>) and index<b>3</b>(<i>a</i>) are hashed by the indexing engine <b>140</b>, resulting in these indexes being mapped to hashed index<b>1</b>(<i>b</i>), hashed index<b>2</b>(<i>b</i>), and hashed index<b>3</b>(<i>b</i>), respectively. In one embodiment, a first hash table or hash function is used by the indexing engine <b>140</b> to map the index<b>1</b>(<i>a</i>) to the hashed index<b>1</b>(<i>b</i>). A second hash table or hash function is used by the indexing engine <b>140</b> to map the index<b>2</b>(<i>a</i>) to the hashed index<b>2</b>(<i>b</i>), and a third hash table or hash function is used by the indexing engine <b>140</b> to map the index<b>3</b>(<i>a</i>) to the hashed index<b>3</b>(<i>b</i>). The search module <b>130</b> can perform a search of the databases <b>160</b><i>a </i>or <b>160</b><i>b </i>using the non-hashed or hashed indexes, respectively, as will be discussed next with regards to <figref idref="DRAWINGS">FIG. 3</figref>.

0045A hash function typically uses a fixed-length data value that is a shortened substitute reference to the original non-hashed data value. For example, the trivial hash function maps the original non-hashed data value on itself as the hashed value when the range of data value is small enough and can be represented by computer architecture's internal data type, e.g. a 32-bit integer. Such a trivial hash function is computationally inexpensive and perfect, meaning the mapping is injective. Or integer values i can be mapped to hashed integers of fixed length n using by a hash function of i mod n. A cryptographic hash function randomly maps data values to a fixed-length bit string such that even slight changes of the data values lead to very different hashed bit string values.

0046The index used by the search module <b>130</b> in performing a user requested search depends on the user's access rights level. For a user with a high level of access rights, the search module <b>130</b> will use a high granularity index (such as index<b>3</b>(<i>a</i>) or index<b>3</b>(<i>b</i>)); for a user with a medium level of access rights, the search module <b>130</b> will search the data using a medium granularity index (such as index<b>2</b>(<i>a</i>) or index<b>2</b>(<i>b</i>)); and for a user with a low level of access rights, the search module <b>130</b> will search the data with a low granularity index (such as index<b>1</b>(<i>a</i>) or index<b>1</b>(<i>b</i>)).

0047As indicated in <figref idref="DRAWINGS">FIG. 2</figref>, the first three entries (rows) of the index<b>1</b>(<i>a</i>) are identical, having the value “J”, because the first three names in name column <b>210</b><i>a </i>in table <b>220</b><i>a </i>start with “J”. Accordingly, when the name column <b>210</b><i>a </i>is searched by the search module <b>130</b> using the index<b>1</b>(<i>a</i>), a search key beginning with the letter “J” will result in the first three entries (values) of the name column <b>210</b><i>a </i>being returned, namely “Johnson”, “Johnson”, and “Janson”. The index<b>2</b>(<i>a</i>) indexes the name column by the first two characters of data within the name column <b>210</b><i>a. </i>Thus, when the name column <b>210</b><i>a </i>is searched using the index<b>2</b>(<i>a</i>), a search key beginning with “Jo” will result in the first two entries of the name column being returned, namely “Johnson” and “Johnson”. Thus, based on a higher level of access rights searching the index<b>2</b>(<i>a</i>) returns fewer results that closer represent the search key than searching index<b>1</b>(<i>a</i>), which is the index accessed by a user with lower access rights.

0048The embodiment of <figref idref="DRAWINGS">FIG. 3</figref> illustrates data search and retrieval within the information retrieval system of <figref idref="DRAWINGS">FIG. 1</figref> by users having different levels of access rights, according to one embodiment. The indexed database includes index<b>1</b>(<i>c</i>), index<b>2</b>(<i>c</i>) and index<b>3</b>(<i>c</i>), corresponding to hashed index<b>1</b>(<i>b</i>), index<b>2</b>(<i>b</i>) and index<b>3</b>(<i>b</i>) of <figref idref="DRAWINGS">FIG. 2</figref>, respectively. The hashed index values of these three indexes have been truncated in index<b>1</b>(<i>c</i>), index<b>2</b>(<i>c</i>) and index<b>3</b>(<i>c</i>) to include only the first character of the hashed index values. Truncating index values can result in additional results being returned in response to searches performed using the index, resulting in greater data protection and privacy. Index<b>1</b>(<i>c</i>) has the lowest granularity of the three indexes, and index<b>3</b>(<i>c</i>) has the highest granularity of the three indexes.

0049Users <b>1</b>, <b>2</b>, and <b>3</b> are associated with different levels of access rights to the indexed database <b>160</b><i>c. </i>Particularly, User <b>1</b> has a low level of access rights, User <b>2</b> has a medium level of access rights, and User <b>3</b> has a high level of access rights. In response to a search of the data by Users <b>1</b>, <b>2</b>, and <b>3</b>, the search module <b>130</b> searches the data using index<b>1</b>(<i>c</i>) for User <b>1</b>, index<b>2</b>(<i>c</i>) for User <b>2</b>, and index<b>3</b>(<i>c</i>)for User <b>3</b>, responsive to the respective level of access rights of Users <b>1</b>, <b>2</b>, and <b>3</b>. Although not shown in <figref idref="DRAWINGS">FIG. 3</figref>, Users <b>1</b>, <b>2</b>, and <b>3</b> have authenticated themselves to the indexed database <b>160</b><i>b </i>prior to having access rights granted.

0050<figref idref="DRAWINGS">FIG. 3</figref> illustrates search results for Users <b>1</b>, <b>2</b>, and <b>3</b> in response to a search query for “Johnson” of the indexed database <b>160</b><i>c. </i>Prior to searching the database for the term “Johnson”, the search system <b>260</b> hashes the term “Johnson” for each of the indexes into a search key. For User <b>1</b>, the search module <b>130</b> hashes the term “Johnson” using a first hash function described above to produce the hashed search key “Aa”, which is then truncated to “A”. Searching index<b>1</b><b>300</b> using the truncated and hashed search key “A” yields four encrypted results <b>330</b><i>a </i>for the name column that are returned to User <b>1</b>. For User <b>2</b>, the search module <b>130</b> hashes the term “Johnson” using the second hash function described above to produce the hashed search key “Cd”, which is then truncated to “C”. Searching index<b>2</b>(<i>c</i>) using the truncated and hashed search key “C” yields three encrypted results <b>330</b><i>b </i>for the name column that are returned to User <b>2</b>. For User <b>3</b>, the search module <b>130</b> hashes the term “Johnson” using the third hash function to produce the hashed search key “Ge”, which is then truncated to “G”. Searching index<b>3</b>(<i>c</i>) using the truncated and hashed search key “G” yields two encrypted results <b>330</b><i>c </i>for the name column that are returned to User <b>3</b>.

0051As seen in <figref idref="DRAWINGS">FIG. 3</figref>, the granularity of the index used to search the data can affect the number of search results returned, and thus the amount of data protection and privacy implemented during searches of the data. As User <b>1</b> has the lowest level of access rights, the search module <b>130</b> searched the data on behalf of User <b>1</b> using the index of the lowest granularity, resulting in the greater number of results. By returning additional search results, the quantity of returned data is increased, increasing the privacy of the data in view of User <b>1</b>'s access of the data. This privacy is increased by providing User <b>1</b> only with the encrypted results, thus eliminating the possibility of User <b>1</b> identifying the results that directly correspond to the search query.

0052In comparison, fewer results are returned in response to the search performed on behalf of User <b>2</b> using the index of medium granularity, and fewer still are returned in response to the search performed on behalf of User <b>3</b>. The lower number of results returned for User <b>2</b> and <b>3</b> is a product of the use of indexes of increasing granularity to search the data, which is a response to the greater access rights of Users <b>2</b> and <b>3</b>. By limiting access to the highest granularity indexes to the most trusted users (users with the greatest access rights), data protection and privacy are maximized.

0053<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart illustrating the process of searching an indexed database within the information retrieval system of <figref idref="DRAWINGS">FIG. 1</figref>, according to one embodiment. A search query is received <b>400</b> to search a database indexed with multiple indexes. A level of access rights associated with the request is determined <b>410</b>, and an index is selected <b>420</b> based on the determined level of access rights. A search key is generated <b>430</b> based on the search query, and the selected index is searched <b>440</b> using the search key. A selected index value associated with the search key is identified <b>450</b>, and data entries associated with the selected index value are outputted <b>460</b>.

Additional Configuration Considerations

0054The present invention has been described in particular detail with respect to one possible embodiment. Those of skill in the art will appreciate that the invention may be practiced in other embodiments. First, the particular naming of the components and variables, capitalization of terms, the attributes, data structures, or any other programming or structural aspect is not mandatory or significant, and the mechanisms that implement the invention or its features may have different names, formats, or protocols. Also, the particular division of functionality between the various system components described herein is merely exemplary, and not mandatory; functions performed by a single system component may instead be performed by multiple components, and functions performed by multiple components may instead performed by a single component.

0055It should be noted that various functionalities described herein may be combined in ways not explicitly described. For instance, data can be indexed to include one or more rules regarding access rights levels such that the search results represents higher dimensional access rights. Similarly, index values can be single hashed or hashed multiple times. These aspects of multi-dimensional indexing and hashing may be performed in concert or independently, and the resulting hashed index can be same or higher dimension than the sum of the dimension of the index and hash function.

0056Some portions of above description present the features of the present invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. These operations, while described functionally or logically, are understood to be implemented by computer programs. Furthermore, it has also proven convenient at times, to refer to these arrangements of operations as modules or by functional names, without loss of generality.

0057Unless specifically stated otherwise as apparent from the above discussion, it is appreciated that throughout the description, discussions utilizing terms such as “determine” refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission or display devices.

0058Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. It should be noted that the process steps and instructions of the present invention could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by real time network operating systems.

0059The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may include a general-purpose computer selectively activated or reconfigured by a computer program stored on a non-transitory computer readable medium that can be accessed by the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of computer-readable storage medium suitable for storing electronic instructions, and each coupled to a computer system bus. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability.

0060The algorithms and operations presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may also be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will be apparent to those of skill in the art, along with equivalent variations. In addition, the present invention is not described with reference to any particular programming language. It is appreciated that a variety of programming languages may be used to implement the teachings of the present invention as described herein, and any references to specific languages are provided for invention of enablement and best mode of the present invention.

0061The present invention is well suited to a wide variety of computer network systems over numerous topologies. Within this field, the configuration and management of large networks include storage devices and computers that are communicatively coupled to dissimilar computers and storage devices over a network, such as the Internet.

0062Finally, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.