US 5,956,400 A · Partitioned information storage systems with controlled retrieval

Abstract

An information storage system includes one or more information update terminals, a mapper, one or more partial-databases, and one or more query terminals, exchanging messages over a set of communication channels. An identifier-mapping mechanism provides (to an update terminal) a method for delegating control over retrieval of the data stored at the partial-databases to one or more mappers, typically operated by one or more trusted third parties. Update terminals supply information, that is stored in fragmented form by the partial-databases. Data-fragment identifiers and pseudonyms are introduced, preventing unauthorized de-fragmentation of information--thus providing compliance to privacy legislation--while at the same time allowing query terminals to retrieve (part of) the stored data or learn properties of the stored data. The mapper is necessarily involved in both operations, allowing data access policies to be enforced and potential abuse of stored information to be reduced. Introduction of multiple mappers acts to distribute information retrieval control among multiple trusted third parties. Introducing so-called `groupers` increases the efficiency of data retrieval for a common set of queries and further reduces potential abuse of information.

Claims54

Dependent claims

A method for transforming an input data object to an output data object, involving a sender, a mapper and a receiver, while hiding from the said receiver the correspondence between the said input data object and the said output data object, the method comprising the steps of:

the said sender sending a first message to the mapper, the said first message containing the input data object consisting of a first piece of data and a second piece of data and a third piece of data, the said second piece of data identifying the first piece of data and the said third piece of data identifying the said receiver;
the said mapper responding to the said first message by constructing the said output object consisting of a fourth piece of data and a fifth piece of data, the said fourth piece of data being constructed by applying a first transformation method to the said first piece of data so that the said fourth piece of data and the said first piece of data are substantially uncorrelated, and the said fifth piece of data identifying the said fourth piece of data and being constructed by applying a second transformation method to the said second piece of data so that the said fifih piece of data and the said second piece of data are substantially uncorrelated,
the said mapper sending the said output object in a second message to the receiver identified in the said third piece of data;
and
the said receiver responding to the said second message by accepting it.

2 more elements

A method for transforming an input data object to a set of output data objects, involving a sender, a mapper and a set of receivers, while hiding from each of the said receivers the correspondence between the input data object and each of the output data objects and between the output objects mutually, the method comprising the steps of:

the said sender sending a first message to the mapper, the first message containing the input data object consisting of a first set of data-elements, each data-element of the said first set consisting of a first piece of data and a second piece of data and a third piece of data, the said second piece of data identifying the first piece of data and the said third piece of data identifying one of the said receivers;
the said mapper responding to the said first message by constructing a second set of data-elements, the said second set having the same cardinality as the said first set, each data-element of the said second set being based on a different data-element of the said first set and each data-element of the said second set consisting of a fourth piece of data and a fifth piece of data, the said fourth piece of data being constructed by applying a first transformation method to the said first piece of data of the said data-element of the said first set so that the said fourth piece of data and the said first piece of data are substantially uncorrelated, and the said fifth piece of data identifying the said fourth piece of data and being constructed by applying a second transformation method to the said second piece of data of the said data-element of the said first set so that the said fifth piece of data and the said second piece of data are substantially uncorrelated;
the said mapper sending each data-element of the said second set in a second message to the receiver identified in the said third piece of data of the said related data-element of the said first set;
and
every receiver responding to the said second message by accepting it.

2 more elements

A method for storing an information record partitioned, involving update terminals, a mapper and partial-databases;

updating the said stored information record, involving the said update terminals, the said mapper and the said partial-databases;
and querying multiple of the said stored information records, involving query terminals and the said partial-databases, and being controlled by the said mapper;
the storing of an information record comprising steps of:
one of the said update terminals dividing the said information record into parts and constructing a first set of data-elements, the type of information record to be stored and the applied division being known to all parties, and each data-element of the said first set consisting of a first piece of data and a second piece of data and a third piece of data, the said first piece of data being constructed by applying a first transformation method to one of the said parts so that the said first piece of data and the said part are substantially uncorrelated, the said second piece of data identifying the said part and the said third piece of data identifying one of the said group of partial-databases;
the said update terminal sending the said first set in a first message to the said mapper;
the said mapper responding to the said first message by constructing a second set of data-elements, the second set having the same cardinality as the first set, each data-element of the said second set being based on a different data-element of the said first set and each data-element of the said second set consisting of a fourth piece of data and a fifth piece of data, the said fourth piece of data being constructed by applying a second transformation method to the said first piece of data of the said data-element of the said first set, the said second transformation method being only known to the said mapper and reversing the said first transformation method, and the said fifth piece of data identifying the said fourth piece of data and being constructed by applying a third transformation method to the said second piece of data of the said data-element of the said first set so that the said fifth piece of data and the said second piece of data are substantially uncorrelated, the said third transformation method being only known to the said mapper;
the said mapper storing the correspondence between all the said second piece of data of the said first set;
the said mapper sending each data-element of the said second set in a second message to the partial-database identified in the said third piece of data of the said related data-element of the said first set;
and
each of the said partial-databases responding to the said second message by accepting it and storing the said data-element;
and
the updating of a stored information record comprising steps of:
one of the said update terminals dividing the said update information into update parts corresponding to the division of parts being performed during the storing of the said information record and constructing a third set of data-elements, each data-element of the said third set consisting of a sixth piece of data and a second piece of data and a third piece of data, the said sixth piece of data being constructed by applying the said first transformation method to one of the said update parts so that the said sixth piece of data and the said update part are substantially uncorrelated, the said second piece of data identifying the said part to be updated and the said third piece of data identifying the partial-databases where the part to be updated is stored;
the said update terminal sending the said third set in a third message to the said mapper;
the said mapper responding to the said third message by constructing a fourth set of data-elements, the fourth set having the same cardinality as the third set, each data-element of the said fourth set being based on a different data-element of the said third set and each data-element of the said fourth set consisting of a seventh piece of data and a fifth piece of data, the said seventh piece of data being constructed by applying the said second transformation method to the said sixth piece of data of the said data-element of the said third set, and the said fifth piece of data identifying the said fourth piece of data and being constructed by applying the said third transformation method to the said second piece of data of the said data-element of the said third set;
the said mapper sending each data-element of the said fourth set in a fourth message to the partial-database identified in the said third piece of data of the said related data-element of the said third set;
and
each of the said partial-databases responding to the said fourth message by accepting it and updating the said fourth piece of data identified by the said fifth piece of data with the update information in the said seventh piece of data;
and
the querying of the said information records comprising steps of:
one of the said query terminals constructing a first query over the said information records, the said query consisting of a set of sub-queries and a description, each of the said sub-queries being a query over information stored at one of the said partial-databases and the said description being interpretable by the mapper and describing how to construct the answer to the said first query based on the answers to the said sub-queries and also based on the said correspondence information stored by the mapper during the storing of the said information records;
the said query terminal sending the said first query in a fifth message to the said mapper;
the said mapper responding to the said fifth message by submitting each of the said sub-queries to the relating partial-database in a sixth message;
each of the said partial-databases responding to the said sixth message by solving the said sub-query using the data-elements stored by the said partial-database and sending the resulting sub-query answer to the said mapper in a seventh message;
the said mapper responding to each the said seventh message by accepting it, combining all the said sub-query answers and the said stored correspondence information to a query answer according to the said first description, and sending the said query answer to the said query terminal in an eighth message;
and
the said query terminal responding to the said eighth message by accepting it.

24 more elements

A method for introducing a pseudonym for an entity, involving a local terminal, a grouper, a first mapper and a matcher;

updating a dossier on an entity using a pseudonym, involving a local terminal, a second mapper and a database;
and, querying a dossier on an entity using a pseudonym, involving a local terminal, a grouper, the said second mapper and the said database;
the introducing of the said pseudonym for the said entity comprising steps of:
a local terminal obtaining a first piece of data containing information identifying the said entity and being interpretable by the said local terminal and by the said matcher;
the said local terminal selecting a first pseudonym for the said entity, the said first pseudonym being previously unused and unique, the said first pseudonym and the said first piece of data being substantially uncorrelated, and the correspondence between the said first pseudonym and the said first piece of data being only known to the said local terminal;
the said local terminal retaining the said first pseudonym and the said first piece of data and their correspondence;
the said local terminal preparing a first message containing the said first pseudonym and a second piece of data, the said second piece of data being constructed by applying a first transformation method to the said first piece of data so that the said first piece of data and the said second piece of data are substantially uncorrelated, an inverse transformation method of the said first transformation method being only known to the said matcher;
the said local terminal sending the said first message to the said first mapper;
the said first mapper responding to the said first message by preparing a second message containing the said second piece of data and a second pseudonym, the said second pseudonym being constructed by applying a second transformation method to the said first pseudonym so that the said first pseudonym and the said second pseudonym are substantially uncorrelated, the said second transformation method being reproducible and only known to the said first mapper and the correspondence between the said first pseudonym and the said second pseudonym being only known to the said first mapper;
the said first mapper sending the said second message to the said matcher;
the said matcher responding to the said second message by constructing a third piece of data by applying a third transformation method to the said second piece of data, the said third transformation method reversing the said first transformation method and being only known to the said matcher;
the said matcher retaining the identifying information of the said entity from the said third piece of data, retaining the said second pseudonym and retaining their correspondence;
the said matcher searching, in all previously retained identifying information, for identifying information that matches the said received identifying information, the matching of identifying information being concluding that identifying information is related to the same entity;
the said matcher preparing a third message containing a fourth piece of data containing all retained pseudonyms corresponding to retained identifying information matching the said received identifying information;
the said matcher sending the said third message to the said first mapper;
the said first mapper responding to the said third message by preparing a fourth message containing a fifth piece of data containing the same number of pseudonyms as the said fourth piece of data, each of the said pseudonyms of the said fifth piece of data being constructed by applying a fourth transformation method to a different pseudonym of the said fourth piece of data, the said fourth transformation method reversing the said second transformation method and being only known to the said first mapper;
the said first mapper sending the said fourth message to the said grouper;
and
the said grouper responding to the said fourth message by retaining the correspondence between all pseudonyms of the said fifth piece of data;
and
the updating of a dossier on an entity comprising steps of:
a local terminal obtaining information, interpretable by the said local terminal, identifying the said entity, and retrieving a third pseudonym corresponding to the said identifying information;
the said local terminal preparing a fifth message containing the said third pseudonym and a sixth piece of data, the said sixth piece of data holding dossier update information, interpretable by the said database;
the said local terminal sending the said fifth message to the said second mapper;
the said second mapper responding to the said fifth message by preparing a sixth message containing the said sixth piece of data and a fourth pseudonym, the said fourth pseudonym being constructed by applying a fifth transformation method to the said third pseudonym so that the said third pseudonym and the said fourth pseudonym are substantially uncorrelated, the said fifth transformation method being reproducible and only known to the said second mapper and the correspondence between the said third pseudonym and the said fourth pseudonym being only known to the said second mapper;
the said second mapper sending the said sixth message to the said database;
and
the said database responding to the said sixth message by using the update information from the said sixth piece of data to update the retained dossier information corresponding to the said fourth pseudonym, and retaining the result of the said update;
and
the querying of a dossier on an entity comprising steps of:
a local terminal obtaining information, interpretable by the said local terminal, identifying the said entity, and retrieving a fifth pseudonym corresponding to the said identifying information;
the said local terminal preparing a seventh message containing the said fifth pseudonym and a query, the said query being a query over dossier information on the said entity retained at the said database and the said query being interpretable by the said database;
the said local terminal sending the said seventh message to the said grouper;
the said grouper responding to the said seventh message by preparing an eighth message containing the said query and an seventh piece of data, the said seventh piece of data containing a set holding all pseudonyms retained by the said grouper and corresponding to the said fifth pseudonym;
the said grouper sending the said eighth message to the said second mapper;
the said second mapper responding to the said eighth message by preparing a ninth message containing the said query and a eighth piece of data, the said eighth piece of data containing the same number of pseudonyms as the said seventh piece of data, each of the said pseudonyms of the said eighth piece of data being constructed by applying the said fifth transformation method to a different pseudonym of the said seventh piece of data;
the said second mapper sending the said ninth message to the said database;
the said database responding to the said ninth message by preparing a tenth message containing a ninth piece of data, the said ninth piece of data holding an answer to the said query, the said answer being interpretable by the said local terminal and being the result of solving the query over all retained dossier information related to the pseudonyms of the said eighth piece of data;
the said database sending the said tenth message to the said local terminal;
and
the said local terminal responding to the said tenth message by accepting it and processing the answer.

38 more elements

Dependencies are inferred from the claim text.

Partitioned information storage systems with controlled retrieval

Life of this patent

Partitioned information storage systems with controlled retrieval

Life of this patent

Abstract

Claims54