Privacy-Enhanced Searches Using Encryption
AssigneeAT&T Intellectual Property II, L.P.
InventorsSteven Michael Bellovin, William Roberts Cheswick
Life of this patent
Estimating the term…
Abstract
Encryption with keys that form an Abelian group are used in combination with a semi-trusted party that converts queries that are encrypted with the key of a querier to queries that are encrypted with the key of the encrypted database, without knowing the actual keys. In an illustrative embodiment, encryption is done with Bloom filters that employ Pohlig-Hellman encryption. Since the querier's key is not divulged, neither the semi-trusted party nor the publisher of the database can see the original queries. Provision can be made for fourth party “warrant servers”, as well as “censorship sets” that limit the data to be shared.
Claims20
A method for querying a database that contains data encrypted with key kB, comprising the steps of:
- a mediator party receiving {W}kA from a first party, which is a database query W that was encrypted with a first set of p encryption functions, where p is 1 or more;
- said mediator party transforming said {W}kA to a transformed query {W″}kB that results from encrypting W″ with a second set of q encryption functions;
- sending information that comprises said {W″}kB to a second party that has access to said database;
- said second party applying said information to said database and obtaining therefrom a result;
- and
- outputting said result for processing and delivery to said first party;
- where
- q>0 and q≦p,
- at least one of the encryption functions in the first set is different from the encryption function in the second set,
- said mediator does has no knowledge of the encryption functions that belong to said first set and has no knowledge of the encryption functions that belong to said second set, and
- said mediator, first party, and second party are distinct from each other.
A method for a first party obtaining information from a database that is encrypted with key kB by a second party that has access to said database, comprising the steps of:
- said first party
- formulating a query parameter related to said information, W, that matches zero or more entries in said database,
- encrypting W with an encryption key kA to form an encrypted query parameter {W}kA, and
- sending {W}kA to a third party that possesses key rA,B, which is related to both key kA and key kB, but neither kA nor key kB is known to said third party or derivable from rA,B, and keys kA and kB are such that encrypting with key rA,B develops that which would be developed by encrypting with a key that is the inverse of key kA following by encrypting with key kB;
- said third party
- encrypting {W}kA with key rA,B to develop {W}kB;
- and
- sending {W}kB to said second party;
- and
- said second party
- applying {W}kB to said database to obtain results, and
- sending said results for processing to develop said information from said results and delivering said information to said first party.
Dependencies are inferred from the claim text.