FIELD OF THE INVENTION

Embodiments of the invention relate to the field of data encryption, decryption and security.

BACKGROUND OF THE INVENTION

Today, massive amounts of data live in many organizations, with barriers between them, erected by mistrust, economic incentives and regulatory hurdles. When secret data, such as personal or medical data is involved, privacy becomes a major concern for all parties involved, as that information can be used to identify or exploit the individuals.

To encourage collaboration, while still protecting data secrecy, cryptosystems have been developed that allow parties to operate and execute computations on encrypted data sets (i.e., ciphertexts) in an encrypted domain. Multiple different parties may provide multiple different respective encrypted data sets, each of which is independently encrypted by its individual party with a different party-specific encryption key that cannot be decrypted by other parties. Often, the multiple encrypted datasets may have interrelated, overlapping, or complementary data. For example, one encrypted dataset may represent medical data for a patient, while another encrypted dataset may represent genetic data for the same patient. It may be desirable to merge these datasets, for example, to study common trends, correlations, etc. (e.g., joint computations), where the contributions from the combination of datasets is greater than their independent parts.

These types of joint computations, however, introduce security risks as the encrypted data sets often use secret information such as sensitive identifiers (e.g., social security numbers, credit card numbers, etc.) to identify and thus link common records in the datasets. To keep these identifiers secure, they too may be independently encrypted by their respective parties. Correlating encrypted identifiers in an encrypted space may be difficult and prohibitively slow using current methods, such as, fully homomorphic encryption comparisons. This inefficiency is only exacerbated as dataset size and thus the number of associated identifiers grows, which results in an exponential increase of pairwise combinations of identifier comparisons.

Accordingly, there is a long felt need in the art for secure and efficient techniques to link interrelated data from different encrypted datasets encrypted by different independent parties in an encrypted space.

SUMMARY OF EMBODIMENTS OF THE INVENTION

Embodiments of the invention solve this long felt need in the art by providing a device, system, and method for linking two or more encrypted datasets based on common identifiers (IDs) (or their hashes or derivative thereof). The IDs (or their hashes or derivatives) may also be encrypted.

In an embodiment of the invention, a device, system and method is provided for linking encrypted data sets using common encrypted identifiers in an encrypted space. A first and second parties' respective encrypted data sets may include first and second respective encrypted data and associated first and second respective encrypted identifiers. The data and identifiers typically cannot be unencrypted without one or more secret decryption keys. The first and second encrypted identifiers may be converted into a first and second respective sets of a plurality of elemental identifier components. Each of the plurality of elemental identifier components in each component set characterizes a distinct numeric property of the corresponding converted encrypted identifier. The first and second sets of the plurality of elemental identifier components may be composed, component-by-component, to generate a plurality of component-specific results. If the plurality of component-specific results are determined to satisfy a matching criterion indicating that the first and second encrypted identifiers match, the first and second encrypted data associated with the first and second matching encrypted identifiers may be linked. Joint computations may be executed on the linked first and second encrypted data in the encrypted and/or unencrypted space.

In an embodiment of the invention, a device, system and method is provided, in which one data set may be encrypted by an external (e.g., first) party, while another data set remains unencrypted by another (e.g., second) party that e.g., executes the identifier comparison internally without exposing the unencrypted data to any other party. An encrypted data set may be received, from the external party, including encrypted data and associated encrypted identifiers, but typically not receiving one or more secret encryption keys required to decrypt the encrypted data and encrypted identifiers. An unencrypted plaintext data set may be retrieved, from memory, comprising unencrypted data and associated unencrypted identifiers. The encrypted and unencrypted identifiers may be converted into respective encrypted and unencrypted sets of a plurality of elemental identifier components. Each of the plurality of elemental identifier components in each component set may represent a distinct numeric property of the corresponding respective converted encrypted and unencrypted identifier. The encrypted and unencrypted sets of the plurality of elemental identifier components may be composed, e.g., component-by-component, to generate a plurality of component-specific results. It may be determined if the plurality of component-specific results satisfy a matching criterion indicating that the encrypted and unencrypted identifiers match. The encrypted and unencrypted data associated with the encrypted and unencrypted matching encrypted identifiers match may be linked. The external party may be sent an indication of the linking to decrypt the encrypted data and link the decrypted data and the retrieved unencrypted data. Joint computations may be executed on the linked first and second data in the encrypted and/or unencrypted space.

