US20040193905A1 - System and method for providing secure transmission, search, and storage of data - Google Patents

Abstract

A system and method for securely transmitting, searching, and storing data. To ensure security on the client side of a communication network, the system and method double encrypt sensitive data and single encrypt non-sensitive data. The system and method also fuzzy searches for user information. Thus, it is possible to find the information for the user in a database knowing only a minimal amount of detail about that user. Privacy and security is provided without impeding performance or compromising any of the standard database search functionality. Capitalizing on the difference in privacy requirements between users, the number of keys required to access sensitive data is minimized by using a single key for each user (e.g., a patient) and two keys for other users (e.g., health care providers).

Description

CROSS REFERENCE TO RELATED APPLICATIONS
• This application is a divisional of U.S. patent application Ser. No. 09/388,025, filed Aug. 31, 1999.[0001]
FIELD OF THE INVENTION
• The present invention relates to computer and network security, and more particularly, a system and method for securely transmitting, searching, and storing data.[0002]
BACKGROUND INFORMATION
• Advances in computer and communications technology have increased a free flow of information within networked computer systems. While a boon to many, such free flow of information can be disastrous to those systems which process sensitive data. In a typical networked computer system, one or more clients are connected over a communication network to a server.[0003]
• The risk of a security breach is compounded when a pathway is provided from a private network to a public network such as the Internet. The Internet is a loose conglomeration of networks connected to a standard network protocol. One of the benefits of accessing the Internet is that the vast amounts of information can be accessed by the user. However, of such unobstructed access, the danger is that there are little or virtually no controls on what individuals can access and what they may do with such access. When data is stored or transmitted which allows parties, to access such data even though they are not authorized to access it, it is necessary to take steps to insure the security of that stored data and to ensure the integrity of data transmitted from one computer to another (e.g., via the Internet).[0004]
• A number of measures, e.g. encryption procedures, have been used to reduce the vulnerability of the networked systems to unauthorized access. Conventional encryption procedures encode data to prevent the unauthorized access, especially during the transmission of the data. Encryption procedure is generally based on one or more keys, or codes, which are essential for decoding, or reverting the data into a readable form.[0005]
• The traditional encryption techniques focus on the security of the transmission and ignore the security of storage. These techniques provide a protection against the first kind of attacks which include intercepting the data as it is being transmitted. The encryption techniques not only allow the authentication of the sender of a message, but also serve to verify the integrity of the message itself, thus proving that the message has not been altered during the transmission. Such techniques include the use of both symmetric and asymmetric keys, as well as digital signatures and hash algorithms.[0006]
• The encryption algorithms or procedures are generally characterized in two categories: symmetric and asymmetric. Symmetric algorithms use one key to encrypt and decrypt a message. An encryption key is a sequence of bits that can be used to encode or decode a message. These symmetric algorithms require that both the sender and the intended receiver of the message (and no one else) know the same key. On the other hand, asymmetric algorithms use two separate keys e.g., a public and a private key to encrypt and/or decrypt a message. The public keys are published, (i.e., in the sense that the public key is available from a particular service; such as a telephone directory) so that everyone knows everyone else's public key. The private keys, on the other hand, are kept secret by the owner.[0007]
• Thus, in a situation where, for example, a patient wanted to send an encrypted message to his or her doctor, the patient would use the doctor's public key to encrypt the message, and then send the encrypted message to the doctor. The doctor would then use his private key to decrypt the message.[0008]
• The practice of using encryption protocols or procedures to authenticate message senders as well as the integrity of messages is well known in the art (see e.g., Bruce Schneier, Applied Cryptography, Protocols, Algorithms, And Source Code In C, 2d ed., John Wiley & Sons, Inc., 1996).[0009]
• Conventional systems and methods suffer from, e.g., at least four deficiencies:[0010]
• 1. Restricted media and time: data management security measures only apply to data transmission, thus exposing stored data to an unauthorized access or unauthorized data manipulation;[0011]
• 2. Exceeded user generality: data management security measures ignore interaction patterns between individuals or user groups;[0012]
• 3. Exceeded application scope: security measures ignore specific requirements of particular applications (e.g., medical use); and[0013]
• 4. Exceeded implementation demands: security measures require n-1 keys for a group of n people. (as discussed in the publication by Schneier listed above).[0014]
• Accordingly, there is a need for a system and method which elevates the security standards across all digital media and prevents compromising data (e.g., patient data) in case of an authorized access of the server. Moreover, there is a need for a system and method that combines security and privacy protection without impeding data processing performance or conventional query scope in a relational database.[0015]
SUMMARY OF THE INVENTION
• The present invention is directed to a method and system that satisfies the need of securely transmitting, searching, and storing data. Such a system and method allows a user to transfer data securely to a private network by pre-encrypting sensitive data with an encryption key, encrypting both non-sensitive data and the pre-encrypted data with a different encryption key and sending this encrypted data to a private network.[0016]
• In an embodiment of the system and method, a server is configured to perform fuzzy searching. The procedure for fuzzy searching include creating trigrams for each record in a record database, sorting the trigrams alphabetically, computing signature vectors for each record in the record database, encrypting the signature vectors with an encryption key, and storing the encrypted signature vectors in an encrypted signature database. In addition, the above steps are performed to obtain an encrypted signature vector for a search query. Thereafter, the closest encrypted signature vector is obtained from an encrypted vector database (i.e., the encrypted signature vector that is closest to the search query encrypted signature vector is obtained).[0017]
• According to another embodiment of the present invention, the record database which contains both non-sensitive data and encrypted sensitive data is searched. This is accomplished by encrypting the search query with an encryption key. Then, one or more records satisfying the search query are found.[0018]
• Another embodiment of the present invention allows authorized users access to the encrypted sensitive data. First, the database which contains information is checked to determine which users are authorized to access certain data, and if the user is authorized to access such data, then the user is allowed to access a master encryption key. With the master encryption key, a further encryption key is decrypted. This further encryption key provides access for the user to the sensitive data.[0019]
BRIEF DESCRIPTION OF THE DRAWINGS
• FIG. 1[0020]ashows an exemplary embodiment of a system according to the present invention.
• FIG. 1[0021]bshows exemplary keys utilized for authenticating the interface server in the system illustrated in FIG. 1a.
• FIG. 1[0022]cshows exemplary keys utilized for transmitting, receiving, and storing data in the system illustrated in FIG. 1a.
• FIG. 1[0023]dshows exemplary keys utilized for fuzzy searching a database in the system illustrated in FIG. 1a.
• FIG. 1[0024]eshows exemplary keys utilized for relational database searching in the system illustrated in FIG. 1a.
• FIG. 1[0025]fshows exemplary keys utilized for accessing sensitive data in the system illustrated in FIG. 1a.
• FIG. 1[0026]hshows an exemplary embodiment of a method in which a user communicates with a private network.
• FIG. 2 shows another exemplary embodiment of a method according to the present invention for authenticating an interface server.[0027]
• FIG. 3 shows another exemplary embodiment of a method according to the present invention for securely transmitting and storing data.[0028]
• FIG. 4 shows another exemplary embodiment of a method according to the present invention for performing the searching operation.[0029]
• FIG. 5 shows another exemplary embodiment of a method according to the present invention for accessing sensitive data.[0030]
DETAILED DESCRIPTION
• Overview[0031]
• The system and method according to the present invention addresses the problems of conventional systems and methods as discussed above by, e.g.: (1) securely transferring and storing sensitive data in a performance enhancing manner by double encrypting preferably only the sensitive data; (2) performing fuzzy searching to allow access to user information knowing a limited amount of information about the user; (3) performing relational database operations on a database that contains unencrypted non-sensitive information and, possibly, encrypted sensitive information; and (4) allowing authorized users access to the sensitive information using a minimum number of keys.[0032]
• To reduce a performance overhead associated with an information protection process, only a subset of the stored data may be protected (e.g. only a subset of the stored data may be encrypted). Initially, the data is segmented into two basic data types using the sensitivity criteria. For example, in the healthcare industry, the time of the day in which a procedure is scheduled is not sensitive information. Every patient ultimately needs to know when a particular doctor is available, and so, this information should be readily available. However, the name of the patient involved is sensitive information which should be protected.[0033]
• The system and method is suitable in a situation where there are two interacting groups of users and two classes of records. The two interacting groups of users are a privileged user group and a non-privileged user group. A user can be generally defined as either a privileged user or a non-privileged user. For example, in the healthcare industry, the two interacting groups of users would be the patients (e.g. the non-privileged user group), and the healthcare providers such as doctors (e.g. the privileged user group). The two classes of records would be, e.g.: (1) patient records (e.g., non-privileged user records) and (2) the doctor records (e.g., privileged user records).[0034]
• For example, the patients grant access privileges (to their records) to some doctors and deny access to all other patients and doctors. The doctors to which privileges were granted, in consultation and agreement with their patients, grant access privileges (to some of those patient records) to some doctors. The doctors also grant access privileges to their research to some other doctors and to some patients (see Table 1 below for a listing of the exemplary privileges which may be granted). The system and method according to the present invention utilizes the asymmetry of the privilege granting scheme to minimize the number of keys used by the participating users.[0035]

  TABLE 1
  Access Privilege Asymmetry

  		Doctor research
  	Patient records	records

  	Patient grants	To some doctors	No
  	access
  	Doctor grants	To some doctors and	To some doctors
  	access	some patients	and some patients

• Thus, an asymmetric key protocol is used for allowing a transmission of a client's request to a private network. Data is encrypted or decrypted using a public or private key. Algorithms for encrypting and decrypting data are known in the art and include Rivest-Shamir-Adleman encryption (“RSA”) and Directory System Agent encryption (“DSA”).[0036]
• FIG. 1[0037]ashows an exemplary embodiment of thesystem10 according to the present invention. An asymmetric key protocol is used for security purposes. A private network (arrangement)150 includes, e.g., anapplication server100, arecord database105, a key-store database115, afuzzy signature database120, and apermission database125.
• A[0038]public network135 can be a network in which all users have access without the need for bypassing security measures. An example of thepublic network135 is the Internet. An interface server130 is coupled between theprivate network150 and thepublic network135 thus allowing users (e.g., physicians and patients) access to information on theprivate network150. Aclient140 may include all of the users who require access to information from theprivate network150. When the present invention is used in the medical setting, theclient140 may be a physician or a patient. Averification processor145 performs a verification function by comparing the two parts of a certificate transmitted by theapplication server100 to determine if these two parts match and if so, the interface server130 is authenticated. Theverification processor145 can be implemented using either hardware or software.
• The[0039]application server100 controls the access and retrieval of data between the various databases. Therecord database105 is a database containing information such as, e.g., patient records (e.g., patient's name, patient's appointments, disease history, disease diagnosis, etc.) and doctor records (e.g., doctor's research on various diseases). Some of this information, such as the patient's name and disease history, is sensitive information and thus is encrypted using the patient's public key.
• The key-[0040]store database115 is a database containing the users' private keys which are encrypted using a key-store master symmetric key. Thefuzzy signature database120 is a database containing signature vectors for each of the users in therecord database105, with each signature vector being encrypted using the user's public key. Thepermission database125 is a database containing information regarding whether a specific user (such as a doctor or patient) has access to a specific file or record.
• The system and method according to the present invention uses an encryption procedure, e.g., at five phases:[0041]
• 1. Selected sensitive information is encrypted at the source level. This information remains encrypted during storage.[0042]
• 2. All data that is to be transmitted is encrypted is encrypted using a key.[0043]
• 3. Private keys are encrypted and stored in the key-[0044]store database115. All doctors may share a single key to decrypt keys in the key-store database115.
• 4. Sensitive query conditions are encrypted to enable standard SQL searching while preventing retrieval of similar but irrelevant sensitive data.[0045]
• 5. Fuzzy signature vectors for every user record in the[0046]record database105 is encrypted with the user's public key. Such encryption allows fuzzy search for data including specific sub-strings by encrypting the sub-strings with the user's public key and searching thefuzzy signature database120.
• FIGS. 1[0047]bto if shows exemplary keys which can be used for encrypting and decrypting data. In this exemplary embodiment, an asymmetric encryption algorithm may be employed using both public and private keys. Once data is encrypted using a public key, it can only be decrypted using the corresponding private key. Alternatively, if data is encrypted using a private key, it can only be decrypted using the corresponding public key. The public keys can be obtained by anyone from, for example, a service similar to a telephone directory. The private keys, however, are kept secret.
• FIG. 1[0048]bshows the keys which may be used to authenticate the interface server130. Theapplication server100 sends a certificate to theclient140. The certificate contains both an unencrypted text part and an encrypted part. The encrypted part of the certificate is encrypted using the private key of theverification processor152. Once the certificate is received by theclient140, the encrypted part of the certificate is decrypted using a public key of theverification processor154.
• FIG. 1[0049]cshows the keys which may be used in transmitting, receiving, and storing data. For example, when theclient140 transmits data to theapplication server100 in theprivate network150, theclient140 pre-encrypts sensitive data using the user's public key158 (i.e., the user whose information is to be found from the record database105). Then theclient140 encrypts both non-sensitive data and the sensitive data using an application server'spublic key160. After the application server100 (in the private network150) receives the encrypted data from theclient140, theapplication server100 decrypts both the sensitive data and the non-sensitive data using an application server's private key161. However, the sensitive data remains secure because that data is only accessible when it is again decrypted using a user's private key164.
• When the[0050]application server100 transmits data to theclient140, it uses the user'spublic key158 to encrypt the requested data. The user'spublic key158, as defined herein, is the public key of the user, for example in the case of a database search, whose data is to be retrieved from therecord database105. When theclient140 receives the encrypted data from theapplication server100, it decrypts that data using the user's private key164. The user's private key164, as defined herein, is the private key of the user, for example in the case of a database search, whose data is to be retrieved from therecord database105.
• FIG. 1[0051]dshows the key which may be used in a fuzzy search. Theapplication server100 encrypts all signature vectors corresponding to all records in therecord database105 using the user'spublic key158. In addition, theapplication server100 encrypts the signature vector for a particular search query using the user'spublic key158.
• FIG. 1[0052]eshows the key which may be used in a relational database search. If the search query relates to or utilizes sensitive data, then theapplication server100 encrypts the search query using the user's (e.g. patient's)public key158. Because sensitive information is encrypted in the database which is to be searched, the encryption of the search query allows standard relational database operations to be performed on encrypted data in such a database. Standard relational database operations include searching using, e.g., the SELECT and IF-THEN command.
• FIG. 1[0053]fshows the keys which may be used for accessing sensitive data. Theapplication server100 uses first user's (e.g., doctor's) key-store master key168 to decrypt the second user's (e.g., patient's) private key164 (which is stored as an encrypted key in the key-store database115). Theapplication server100 accesses the sensitive data in therecord database105 by decrypting the sensitive data using the second user's private key164. The user's private key164, as defined above, is the private key of the user, for example in the case of a database search, whose data is to be retrieved from therecord database105.
• FIG. 1[0054]hshows exemplary steps of the method according to the present invention for allowing aclient140 to communicate with aprivate network150. Instep20, theclient140 authenticates the interface server130 by, e.g., requesting and checking the contents of a certificate. Instep25, theclient140 determines if the interface server130 is properly authenticated. If the interface server130 is not properly authenticated then instep27, theclient140 notifies the user of this authentication failure. If the interface server130 is properly authenticated, then instep30, theclient140 transmits data to theapplication server100. Instep40, theapplication server100 performs the operation requested by theclient140 if theclient140 is authorized to perform that operation. If instep50, theapplication server100 determines that theclient140 is authorized to perform the operation, then instep60, theapplication server100 returns the requested information to theclient140. If, however, theapplication server100 determines instep50 that theclient140 is not authorized to perform the requested operation, then instep70, it notifies theclient140 of the denial.
• Authenticating the Interface Server[0055]
• FIG. 2 represents the process for authenticating the interface server[0056]130. Instep200, theclient140 authenticates the interface server130 by requesting a certificate from the interface server130. The certificate contains two parts, e.g., an encrypted part which is encrypted using the private key of theverification processor145 and a clear text part (an unencrypted part). The certificate also contains the application server's100 public key. Instep205, the interface server130 sends a request for the certificate to theapplication server100. Instep210, theapplication server100 transmits the certificate to theclient140 and encrypts the encrypted portion of the certificate using the private key of theverification processor145.
• In[0057]step215, the client140 (after receiving the certificate from the application server100) separates the certificate into two parts, i.e., the encrypted part and the clear text part. Instep220, the client140 (using the public key of theverification processor154 which was sent with the certificate) decrypts the encrypted part of the certificate and instep225, determines if the decrypted part matches the clear text part. If both parts match, then instep235, theclient140 determines that the interface server130 is properly authenticated. However, if both parts do not match then, instep230, theclient140 displays an error message. This process for authenticating the interface server130 is can be implemented using, e.g., Verisign in the Microsoft Internet Explorer® or Netscape browsers.
• Transmission and Storage of Data[0058]
• FIG. 3 shows exemplary steps of the exemplary embodiment of the present invention which may be used by the client[0059]180 to transmit a secure request to theapplication server100. Instep305, theclient140 retrieves the application server'spublic key160 from the certificate. Instep310, theclient140 pre-encrypts sensitive data in the message using the user's (e.g. patient's)public key158. Instep315, theclient140 encrypts all of the message which results in further encrypting the sensitive data with the application server'spublic key160. Instep320, theclient140 transmits the encrypted message to the interface server130. Instep325, the interface server130 sends the encrypted message to theapplication server100. Instep330, theapplication server100 decodes the message using itsprivate key166. Instep335, theapplication server100 stores the message in therecord database105. The sensitive data stored in therecord database105 remains encrypted with the user'spublic key158.
• The above described method is advantageous because the prior art methods do not perform this double encryption, thus leaving the sensitive information unprotected on the[0060]application server100. (See e.g., Bruce Schneier, Applied Cryptography, Protocols, Algorithms, And Source Code In C, Pg. 28, 2d ed., John Wiley & Sons, Inc., 1996). With the above described method, the sensitive information remains encrypted, and thus protected on theapplication server100. If a break-in of the private network occurs, the sensitive information remains protected because, e.g., only the user's private key164 can decrypt that sensitive information.
• The Search Operation[0061]
• In[0062]step40 of FIG. 1h,theapplication server100 performs the operation requested by theclient140. This operation can be a search for a particular record, or an insertion or deletion of a record. For a search operation, FIG. 4 shows exemplary steps which may be used to search for a particular record. Instep402, theapplication server100 obtains the search query that theclient140 previously transmitted. Instep404, theapplication server100, determines if the search requires fuzzy searching. Fuzzy searching is required if the user sitting at theclient140 selects fuzzy searching rather than performing traditional searching which requires an exact match of the search query with a term in the record.
• If the fuzzy searching is required, then in[0063]step406, theapplication server100 may create trigrams for every record in therecord database105. A trigram is a string of three letters. The set of all trigrams for any given portion of text characterizes that text and may be used for its identification in a limited size environment. For example, the word “cryptography” has the following trigrams: “cry”, “ryp”, “ypt”, “pto”, “tog”, “ogr”, “gra”, “rap”, “aph”, and “phy”. Instep408, the trigrams are sorted, e.g., alphabetically. Thus, for the above example, the trigrams would be ordered as: “aph”, “cry”, “gra”, “ogr”, “phy”, “pto”, “rap”, “ryp”, “tog”, and “ypt”.
• In[0064]step410, theapplication server100 computes a signature vector for each record. The signature vector is a trigram frequency vector for the entire alphabet. In the previous example, the signature vector for the word “cryptography” has0's in all positions starting with “aaa” and ending with “zzz”, except for1's in the positions of “cry”, “ryp”,“ypt”, “pto”, “tog”, “ogr”, “gra”, “rap”, “aph”, and “phy”. For example, the vector for cryptography would have the following values:

  aaa aab aac . . . aph . . . crp . . . gra . . . ogr . . . phy
  0    0   0 . . . 1   . . . 1   . . . 1   . . . 1   . . . 1

• The signature vector can also be calculated using other methods, such as using quadgrams or pentagrams rather than trigrams.[0065]
• In[0066]step412, theapplication server100 encrypts the signature vector using the user's public key158 (i.e., the public key of the user whose information is to be retrieved from the record database105). Instep414, theapplication server100 stores the encrypted signature vector in thefuzzy signature database120. Instep416, using, e.g., the above method employing the trigrams, theapplication server100 computes the signature vector for the search query. Instep418, theapplication server100 encrypts this signature vector using the user'spublic key158 which results in an encrypted fuzzy query.
• In[0067]step420, theapplication server100 finds the encrypted signature vector in thefuzzy signature database120 for which the inner product with the encrypted fuzzy query holds the maximum value. The larger the inner product between the encrypted signature vector and the encrypted fuzzy query, the smaller the cosine of the angle (and thus the smaller the angle) between these two vectors. Computing the inner product is performed using the formula:$\sum _{i=1}^nx\left(i\right)·y\left(i\right)$

  
• where x(i) and y(i) are vectors, and n is the number of dimensions of the vectors. The smaller the angle, the smaller the difference between the vectors which results in finding the signature in the fuzzy signature database that is closest to the query. The system and method according to the present invention, however is not limited to a use of the inner product to find the one vector from a group of vectors that is closest to a query vector. It is also possible to use other conventional methods for finding the one vector from a group of vectors that is closest to the query vector. In[0068]step422, the search query is set to the signature vector whose inner product has the maximum value.
• In[0069]step424, theapplication server100 determines if the search query involves sensitive data (e.g., searching on sensitive data such as the patient's name). If the search query involves sensitive data then instep428, theapplication server100 encrypts the search query using the user'spublic key158 before searching in therecord database105. This encryption should be performed because the sensitive information (such as the patient's name) stored in therecord database105 is encrypted with the user's (e.g., patient's) public key158 (refer to the section above on “Transmission and Storage of Data”).
• If the search query is not encrypted, then standard relational database operations such as SQL queries would not work when searching for encrypted entries in the database. For example, if a doctor was provided with all the appointments for a particular patient, it is not possible to simply execute a SELECT statement where the patient's name is equal to a certain value because the patient's name (which is sensitive data) is encrypted in the database. Moreover, because the patient's name is encrypted with the patient's public key, it can only be decrypted using the patient's private key. By encrypting the search query, sensitive information can remain encrypted in the database and standard SQL search capabilities can be performed using the encrypted search query. In addition, the patient's private key is not required to perform a search, and therefore sensitive information is not compromised.[0070]
• In[0071]step430, theapplication server100 compares the encrypted search query to the sensitive patient information in therecord database105. If the search query does not involve sensitive data, then instep426, theapplication server100 compares the search query with the user information stored in therecord database105.
• In[0072]step432, theapplication server100 determines if the two particular items match. This determination can be made by, for example, comparing the search query or the encrypted search query with the relevant field of a record in therecord database105. If the search query requests all patients with the name “John Doe”, then theapplication server100 searches for all records in therecord database105 whose name field contains the name “John Doe”. If the items match, then instep436, all the records that match the search query are returned. If the items do not match, then instep434, theapplication server100 reports to theclient140 that its request could not be satisfied.
• After searching and finding the desired information, if that found information contains the sensitive information then that information needs to decrypted using the procedure described below.[0073]
• Checking Client Authorization[0074]
• FIG. 5 shows exemplary steps of the exemplary embodiment of the system and method according to the present invention for authorizing the client's request when sensitive information is involved. Such sensitive information resides in the[0075]record database105 and is encrypted with the user's (e.g. patient's)public key158. To decrypt that sensitive information and thus be able to use it, the doctor, patient, or another user must be authorized to access that information. If authorized, theapplication server100 sends the requested information back to theclient140. In this embodiment, a first user (e.g., a doctor) is allowed to access sensitive information of second user (e.g., a patient) using only three encryption keys.
• In[0076]step502, theapplication server100 determines if a first user is authorized to perform the requested operation by checking thepermission database125. Thepermission database125 contains information as to which users (such as doctors and patients) are allowed to perform operations (e.g., view, search, add, delete, etc.) on the sensitive information located in the records of the record database105 (e.g., doctor research records or patient records). See Table 1 above for the list of access privileges that doctors and patients can give with regards to patient records and doctor research records.
• If the first user is not authorized to perform the requested operation on the sensitive information, then in[0077]step506, theapplication server100 sends a message to theclient140 to notify it of the access denial. If the first user is authorized to perform the requested operation on the sensitive information, then instep508, theapplication server100 collects the first user's key-store master key168 which that first user provides. Instep510, theapplication server100, using the first user's key-store master key168, decrypts a second user's private key164. While in the key-store database115, the second user's private key164 is encrypted with the key-store master key. Instep511, theapplication server100 obtains the second user's private key from the key-store database115. Instep512, theapplication server100 uses the second user's private key to decrypt the sensitive data found in the second user's record in therecord database105.
• The above process of using the key-store master key[0078]168 and the key-store database115 provided an improvement in that n-1 keys for n people are no longer required. (See e.g., Bruce Schneier, Applied Cryptography, Protocols, Algorithms, And Source Code In C, 2d ed., John Wiley & Sons, Inc., 1996). By using the key-store master key168 and the key-store database115, only three keys (e.g., the doctor's or first user'spublic key158, the key-store master key168, and the patient's or second user's private key164) are all that may be necessary to give a doctor access to a patient's records.
• The key-[0079]store database115 keeps track of the public and private keys of the users. It enables an authorized user to use another user's private key to decrypt a particular piece of the sensitive data. Usage of the key-store database115 separates the data from the keys. To prevent an intruder of theapplication server100 from gaining access to the users' sensitive data via the patients' private keys stored in the key-store database115, all keys stored in the key-store database115 are encrypted using the key-store master key168.
• Returning Information to the Client[0080]
• The[0081]application server100 may send the client requested information, including the sensitive information, back to theclient140. Instep514, theapplication server100 gathers the data requested by theclient140. Instep516, theapplication server100 encrypts the requested data using the first user'spublic key158. Instep518, theapplication server100 transmits encrypted requested data to the interface server130. Instep520, the interface server130 sends the encrypted requested data to theclient140. Instep522, theclient140 decrypts the encrypted requested data using the first user's private key. The decrypted sensitive information of the second user is now readable by the first user.
• The system and method of the present invention is not limited to the medical industry and in particular where a physician or patient tries to access records of another physician or patient. The system and method may also be applicable in other asymmetric privilege granting environments. For example, the system and method may be used in a corporate environment where an employer has access to employee's records but the employee might have access to only his or her own record, or have access to other employee's records depending on that employee's position in the company (such as a manager of other employees). The company may have various offices such that a public network would need to be used in order to access certain information from a private network. In this situation, the system and method again capitalizes on the asymmetry of the privilege granting scheme to minimize the number of keys used by the participating users.[0082]
• Another example is the banking environment where a customer's own bank statement is accessible to that customer but is not accessible to other customers. It is also accessible to certain bank employees such as the loan department or the payment departments. Because of the asymmetry of the privilege granting scheme, this environment can also capitalize on the asymmetry to minimize the number of keys used by the participating users (e.g., bank customers, bank employees, etc.).[0083]
• While the present invention is described in conjunction with the preferred embodiments, it will be understood that they are not intended to limit the invention to that embodiment. On the contrary, this invention is intended to cover alternatives, modifications, and equivalents, which may be included within the spirit and scope of the invention as defined by the claims. Furthermore, in the previous detailed description of the present invention, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be obvious to one of ordinary skill in the art that the present invention may be practiced without these specific details. In addition, several definitions are provided but it will be appreciated that these definitions are not meant to be limiting but are rather provided for context purposes and that among others, the general definition, as understood by-those skilled in the art, also applies. In other instances, well known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present invention.[0084]

Claims (13)

What is claimed is:

1. A system for generating and storing encrypted data, comprising:

a record database which includes a set of records;

a fuzzy signature database; and

an application server performing the following:

generating a first set of trigrams for each record of the records,

sorting the first set of trigrams for each record of the records,

generating signature vectors using the first set of trigrams,

wherein one of the signature vectors is assigned to a respective record residing in the record database,

encrypting the signature vectors using a key to generate encrypted vectors, wherein one of the encrypted vectors is assigned to the respective record, and

storing the encrypted vectors in the fuzzy signature database.

2. The system according toclaim 1, wherein the application server:

generates a second set of trigrams for a fuzzy query,

sorts the second set of trigrams,

computes a query vector using the second set of trigrams,

encrypts the query vector using the key to generate an encrypted fuzzy query vector, and

locates a particular vector of the encrypted vectors in the fuzzy signature database which substantially corresponds to the encrypted fuzzy query vector.

3. The system ofclaim 1, wherein the first set of trigrams is sorted alphabetically.

4. The system ofclaim 2, wherein the second set of trigrams is sorted alphabetically.

5. The system ofclaim 1, wherein the record database includes non-privileged user records and privileged user records.

6. The system ofclaim 2, wherein the key is a public key of a user.

7. A method for generating and storing encrypted data, comprising the steps of:

generating a first set of trigrams for each record of a record database, the record database including a plurality of records;

for each record of the records, sorting the first set of trigrams;

generating signature vectors using the first set of trigrams, wherein one of the signature vectors is assigned to a respective record of the records;

encrypting the signature vectors using a key to generate the encrypted vectors, wherein one of the encrypted vectors is assigned to the respective record; and

storing the encrypted vectors in a fuzzy signature database.

8. The method ofclaim 7, further comprising the steps of:

generating a second set of trigrams for a fuzzy query;

sorting the second set of trigrams;

computing a query vector using the second set of trigrams;

encrypting the query vector using the key to generate an encrypted fuzzy query vector; and

locating a particular vector of the encrypted vectors in the fuzzy signature database which substantially corresponds to the encrypted fuzzy query vector.

9. The method ofclaim 7, wherein for each record of the records, the first set of trigrams is sorted alphabetically.

10. The method ofclaim 8, wherein the second set of trigrams is sorted alphabetically.

11. The method ofclaim 7, wherein the records include non-privileged user records and privileged user records.

12. The method ofclaim 8, wherein the key is a public key of a user.

13. A machine-readable medium having stored thereon data representing sequences of instructions, the sequences of instructions including particular instructions which, when executed by a processor connected to a communication network, cause the processor to perform the steps of:

generating a first set of trigrams for each record of a record database, the record database including a plurality of records;

for each record of the records, sorting the first set of trigrams;

generating signature vectors using the first set of trigrams, wherein one of the signature vectors is assigned to a respective record of the records;

encrypting the signature vectors using a key to generate encrypted vectors, wherein one of the encrypted vectors is assigned to the respective record; and

storing the encrypted vectors in a fuzzy signature database.

Images