1. Field of the Invention
The invention relates to the field of information security and privacy and, more specifically, to finding matching entries in sets from two or more parties without revealing all of any party's entries.
2. Discussion of the Prior Art
Modern research and technology have provided society with a wide variety of electronic devices. Some of these modern electronic devices are very powerful and useful to those who use them. For example, the global positioning system (GPS) was initially deployed for United States military purposes, but today can be a useful aid for almost anyone.
For back country travelers, boaters on open waters, or others who navigate off the beaten path, carrying a light weight, battery powered GPS receiver can provide them with their position within several hundred feet. For motorists, a dramatic improvement in convenience and safety can be provided by carrying a GPS receiver integrated with a trouble alert system (perhaps using mobile telephone technology) or a road map database.
GPS receivers can be configured to record the time and position of the trajectories along which they travel. Such information can be maintained within such GPS receiver/recorder device. Periodically, it can be off-loaded onto a personal computer (PC), a personal digital assistant (PDA), or a server, for example.
Such trajectory information can be gathered and recorded with little or no intrusion on the person carrying the GPS receiver/recorder. Thus, a person could record their daily locations and travel over a period of days, years or even indefinitely.
Nevertheless, mining or making use of such information is difficult, both because of the volume of information potentially involved, and because of the privacy and security implications of sharing such information. Few individuals would be willing to make available to anyone else a complete log of where they have been over a period of time of significant duration. Even if certain “private” time periods could be easily deleted or not recorded, many people would consider a voluminous log of their whereabouts to be no business of anyone else.
Additionally, the security implications are daunting. Someone interested in burglarizing even an ordinary residence or place of business would be given a tremendous advantage by knowing the trends or patterns of who comes and goes from the place at what time—let alone if the person carrying the GPS receiver/recorder were a high profile person such as a leading politician or famous entertainer.
On the other hand, many people would be willing or even eager to reveal a limited subset of such trajectory information. For example, it often happens that two individuals who are meeting each other socially or for business have a feeling that they might have met before, but are unable to recall where and when that may have happened.
More generally, two or more individuals or organizations may possess information that can be represented as collections, data points or sets. They may desire to find what entities, elements or individual data points are present in all of the sets, but only if they can do so without revealing to the other participants all of the elements in their set. One example of such a problem includes several diplomats attempting to select where and when they will meet. Another example is two individuals determining if they both belong to any of the same golf courses, fraternal clubs or other organizations, which can be represented as the longitude and latitude of the clubhouse or headquarters.
Yet another example is two individuals selecting the time, date and place for initially meeting on a blind date. Another example is a company whose trucks are equipped with GPS receiver/recorder devices demonstrating that none of their trucks were near the coordinates of an accident. Yet another example is a person demonstrating that they have never gone near a location or region that is forbidden by the conditions of their parole or probation.