Conceptio › Archive › Google Patents

Google Patentsopen access

Secure search of secret data in a semi-trusted environment using homomorphic … — Duality Technologies, Inc. (US11764940B2)

Duality Technologies, Inc. · Google Patents

Google Patents · Patents · License: Open Access

patent, google patents, intellectual property, US11764940B2, Duality Technologies, Inc., Arina SHAINSKI, en, 2023

ABSTRACT

Abstract

A system and method for secure searching in a semi-trusted environment by comparing first and second data (query and target data). A first data provider may map first secret data to a first plurality of tokens using a token codebook, concatenate the first plurality of tokens to generate a first token signature, and homomorphically encrypt the first token signature. A second data provider may map second data to a second plurality of tokens using the token codebook, concatenate the second plurality of tokens to generate a second token signature, and compare the homomorphically encrypted first token signature and an unencrypted or homomorphically encrypted second token signature to generate a homomorphically encrypted comparison. A trusted party may decrypt the homomorphically encrypted comparison, using a secret homomorphic decryption key, to determine if the token signatures match or not respectively indicating the search query is found or not in the target data.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of U.S. Provisional Application Ser. No. 62/790,696, filed Jan. 10, 2019, which is hereby incorporated by reference in its entirety.

FIELD OF THE INVENTION

Embodiments of the invention are directed to data privacy, security, and encryption of secret data. Embodiments of the invention include systems and methods to encrypt secret data to safely share them with an external or third party, which can then execute queries, searches, or other computations, only on the encrypted secure data, without decrypting and exposing the underlying secret data. In particular embodiments of the invention are directed to fast and efficient searching of homomorphically encrypted (âHEâ) secret data.

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, medical, or financial 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 on encrypted data (i.e., ciphertexts) in an encrypted domain:

Fully Homomorphic Encryption (FHE) cryptosystems allow a third party to evaluate any computation on encrypted data without learning anything about it, such that only the legitimate recipient of the homomorphic calculation will be able to decrypt it using the recipient's secret key. Although FHE can theoretically work on any data, practically, FHE is too computationally burdensome and unrealistic to use in most real-world settings, especially when large amounts of data and complex computations are involved.

Functional Encryption (FE) cryptosystems allow authorized third parties who cannot decrypt, to evaluate selective authorized computations on encrypted data, without decrypting first. Such authorized third parties receive a different secret key for each computation, which enables the calculation of the computation on the data without decryption. In secret-key functional encryption schemes, both decryption and encryption require knowing a secret-key. In public-key functional encryption, decryption requires knowing a secret key, whereas encryption can be performed without knowing a secret-key and does not compromise security.

Proxy re-encryption (PRE) cryptosystems transform data encrypted in one key to data encrypted in another key. PRE may be used in settings involving two or more parties each holding a secret key to a different encryption scheme, and for classical encryption schemes.

However, these cryptosystems are often inefficient, adding extra layers of computations. Further, because the data being operated on is encrypted, it is difficult to find and target specific data. Current operations to search for specific data are often performed across an entire encrypted data set, which becomes prohibitively inefficient, especially when the datasets are large.

Accordingly, there is a need in the art for a fast and efficient technique to search for and target specific data within a ciphertext in the encrypted domain. There is also a need to be able to perform fast and efficient secret searches, such as financial fraud or other types of criminal investigations, in the encrypted domain, on cleartext or ciphertext, which does not compromise the secret search.

SUMMARY OF THE INVENTION

To overcome the aforementioned limitations inherent in the art, embodiments of the invention may provide a fast and efficient targeted search in the encrypted domain, where at least one, or both, of the search query and the targeted data are homomorphically encrypted.

In an embodiment of the invention, a system and method is provided for securely searching data in a semi-trusted environment by comparing first and second data. The first data element may be the search query and the second data element the target data to be searched, or the second data element may be the search query and the first data element the target data to be searched. A first data provider comprising one or more first processors may be configured to map a first data element comprising secret data to a first plurality of tokens using a codebook of tokens to represent data elements, concatenate the first plurality of tokens to generate a first token signature comprising the first plurality of tokens that uniquely represents the first data element, and homomorphically encrypt the first token signature using a public homomorphic encryption key to generate a homomorphically encrypted first token signature representing the first data element. A second data provider comprising one or more second processors may be configured to map a second data element to a second plurality of tokens using the token codebook, wherein one of the first and second data elements is a search query and the other is target data being searched, concatenate the second plurality of tokens to generate a second token signature comprising the second plurality of tokens that uniquely represent the second data element, and compare the homomorphically encrypted first token signature representing the first data element and an unencrypted or homomorphically encrypted second token signature to generate a homomorphically encrypted comparison of the first and second token signatures. The comparison of the first and second token signatures may be a binary indication of whether or not the search query is found in the target data, or a matching score indicating a frequency or certainty with which the search query is found in the target data. A trusted party comprising one or more processors may be configured to decrypt the homomorphically encrypted comparison, using a private homomorphic decryption key, to determine if the first and second token signatures match or not respectively indicating that the search query is found or not in the target data. The first data provider may operate in a trusted environment, the second data provider may operate in a trusted or semi-trusted environment, and the trusted party may operate in a trusted environment. The trusted party may be the first data provider, the second data provider, or a distinct third party system.

In an embodiment of the invention, the first and second data elements may be mapped to tokens by dividing the data element into one or more atomic data units, searching the codebook for a plurality of tokens matching each instance of each atomic data unit, and generating an ordered set of the plurality of tokens for the plurality of atomic units. The codebook of tokens may be dynamically updated by adding new tokens to the codebook and deleting preexisting tokens from the codebook, wherein the updated codebook is simultaneously available to both the first and second data providers.

In an embodiment of the invention, a first data provider is provided for securely searching data in a semi-trusted environment. The first data provider may comprise one or more memories configured to store a first data element comprising secret data, a codebook of tokens to represent data elements, and a public homomorphic encryption key. The first data provider may comprise one or more processors configured to map the first data element comprising secret data to a first plurality of tokens using the token codebook, concatenate the first plurality of tokens to generate a first token signature comprising the first plurality of tokens that uniquely represents the first data element, homomorphically encrypt the first token signature using the public homomorphic encryption key to generate a homomorphically encrypted first token signature representing the first data element, transmit the homomorphically encrypted first token signature to a second data provider to compare the homomorphically encrypted first token signature representing the first data element and an unencrypted or homomorphically encrypted second token signature representing a second data element and generate a homomorphically encrypted comparison of the first and second token signatures, wherein one of the first and second data elements is a search query and the other is target data being searched, and receive the result of decrypting the homomorphically encrypted comparison at a trusted device, using a private homomorphic decryption key, to determine if the first and second token signatures match or not respectively indicating that the search query is found or not in the target data.

In an embodiment of the invention, a second data provider is provided for securely searching data in a semi-trusted environment. The second data provider may comprise one or more memories configured to store a second data element, and a codebook of tokens to represent data elements. The one or more memories may be further configured to store the public homomorphic encryption key when the second data provider generates the homomorphically encrypted second token signature. The second data provider may comprise one or more processors configured to map the second data element to a second plurality of tokens using the token codebook, concatenate the second plurality of tokens to generate a second token signature comprising the second plurality of tokens that uniquely represent the second data element, receive, from a first data provider, a homomorphically encrypted first token signature that is a homomorphically encryption of a concatenation of a first plurality of tokens uniquely representing a first data element comprising secret data according to the codebook of tokens, wherein one of the first and second data elements is a search query and the other is target data being searched, compare the homomorphically encrypted first token signature representing the first data element and an unencrypted or homomorphically encrypted second token signature to generate a homomorphically encrypted comparison of the first and second token signatures, and transmit the homomorphically encrypted comparison to a trusted device to decrypt the homomorphically encrypted comparison, using a private homomorphic decryption key, to determine if the first and second token signatures match or not respectively indicating that the search query is found or not in the target data.

BRIEF DESCRIPTION OF THE DRAWINGS

The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings in which:

FIG. 1 is a schematic illustration of a multi-party system and workflow for performing a fast and secure targeted search in a semi-trusted environment using homomorphic encryption, according to an embodiment of the invention;

FIG. 2 is a schematic illustration of a multi-party system comprising a trusted first homomorphic encryption (HE) data provider (e.g., of a HE search query), a semi-trusted or untrusted second data provider (e.g., of HE or unencrypted target data to be searched), and a trusted third party (e.g., to homomorphically decrypt the search results), according to an embodiment of the invention;

FIG. 3 is a schematic illustration of a multi-party system for securely searching data in a semi-trusted environment, according to an embodiment of the invention; and

FIG. 4 is a flowchart of a method for securely searching data in a semi-trusted environment, according to an embodiment of the invention.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the invention enable fast and efficient targeted searches, in the homomorphic encryption encrypted domain, where the search query (e.g., search keywords) and/or target data being searched (e.g., database, document, image, video, or any other type of file or data repository, or metadata thereof) are homomorphically encrypted.

By utilizing homomorphic encryption, ciphertext can be compared to ciphertext, or ciphertext can be compared to plaintext, such that, a data provider or query provider may be able to compare (1) a homomorphically encrypted search query and homomorphically encrypted target data being searched; (2) a homomorphically encrypted search query and unencrypted target data being searched; or (3) an unencrypted search query and a homomorphically encrypted target data being searched. As long as at least one of the search query or target data are homomorphically encrypted, the comparison therebetween in all three scenarios are performed under homomorphic encryption, without exposing the underlying search query or target data being searched, i.e., in the homomorphic encryption domain. This is because homomorphic encryption provides an injective or one-to-one (1:1) mapping between operations on plaintext and operations on ciphertext. Accordingly, a search that is a comparison between the query and target data, performed between a homomorphically encrypted ciphertext and a plaintext (or between two ciphertexts), generates a homomorphically encrypted comparison. It is therefore secure to search by comparing two terms where at least one is homomorphically encrypted in a semi-trusted domain because neither the underlying homomorphically encrypted term(s) or homomorphically encrypted comparison can be decrypted or exposed without the associated secret homomorphic decryption key. The secret homomorphic decryption key is only stored or accessible to a trusted party.

When used herein, the term trusted may refer for example to an entity or system which is sufficiently trusted to correctly perform computations or operations such as a search (e.g., a comparison between a search query and target data to be searched), and also trusted to keep private data secret. When used herein, the term semi-trusted may refer for example to an entity or system which is sufficiently trusted to correctly perform computations or operations such as a search (e.g., a comparison between a search query and target data to be searched), but not trusted to access or keep private data secret. When used herein, the term untrusted may refer for example to an entity or system which is not sufficiently trusted to correctly perform computations or operations such as a search (e.g., a comparison between a search query and target data to be searched), and not trusted to access or keep private data secret.

The homomorphically encrypted search result or comparison may then be transmitted to a secure environment, e.g., the query provider, the data provider, or a third party, which securely stores the private homomorphic decryption key, to decrypt and analyze the results of the comparison, e.g., to determine if the search comparison renders a match or not.

Scenarios (1)-(3) above may be applied depending on the application, for example, depending on the secrecy or security level of the data (e.g., queries and/or target data with sensitive or proprietary information are generally encrypted, while data that is less or not sensitive such as public data is generally not encrypted), whether the devices, parties or environments storing the data are trusted, semi-trusted, or untrusted (e.g., data is generally encrypted in untrusted and semi-trusted environments and unencrypted in trusted environments), whether the communication channel is trusted to be secret, and/or whether the computation is likely to be compromised in the future.

Examples of the search comparison in the aforementioned three scenarios (1)-(3) are:

In scenario (1), in which both the query and the target data being searche

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of U.S. Provisional Application Ser. No. 62/790,696, filed Jan. 10, 2019, which is hereby incorporated by reference in its entirety.

FIELD OF THE INVENTION

BACKGROUND OF THE INVENTION

To encourage collaboration, while still protecting data secrecy, cryptosystems have been developed that allow parties to operate on encrypted data (i.e., ciphertexts) in an encrypted domain:

SUMMARY OF THE INVENTION

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 3 is a schematic illustration of a multi-party system for securely searching data in a semi-trusted environment, according to an embodiment of the invention; and

FIG. 4 is a flowchart of a method for securely searching data in a semi-trusted environment, according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE INVENTION

Examples of the search comparison in the aforementioned three scenarios (1)-(3) are:

In scenario (1), in which both the query and the target data being searched are homomorphically encrypted, e.g., as shown in FIG. 1 , the homomorphically encrypted comparison may be a difference of a value of a query, value 1 , plus noise generated from homomorphically encrypting the query, noise 1 , and of a value of the target data being searched, value 2 , plus noise generated from homomorphically encrypting the target data, noise 2 , for example as:

HEC=(value 1 +noise 1 )â(value 2 +noise 2 )ââEQN. 1A

Because homomorphically encryption provides a 1:1 mapping between operations on plaintext and operations on ciphertext, the homomorphically encrypted comparison may be equivalently re-written as:

HEC=(value 1 âvalue 2 )+(noise 1 ânoise 2 )ââEQN. 1B

In scenario (2), in which the query is homomorphically encrypted, but the target data being searched is not homomorphically encrypted, the homomorphically encrypted comparison may be a difference of a value of a query, value 1 , plus noise generated from homomorphically encrypting the query, noise 1 , and of a value of the target data being searched, value 2 , for example as.

HEC=(value 1 +noise 1 )â(value 2 )ââEQN. 2A

The homomorphically encrypted comparison may be equivalently re-written as:

HEC=(value 1 âvalue 2 )+(noise 1 )ââEQN. 2B

In scenario (3), in which the query is unencrypted but the target data being searched are homomorphically encrypted, the homomorphically encrypted comparison may be a difference of a value of a query, value 1 , and of a value of the target data being searched, value 2 , plus noise generated from homomorphically encrypting the target data being searched, noise 2 .

HEC=(value 1 )â(value 2 +noise 2 )ââEQN. 3A

The homomorphically encrypted comparison may be equivalently re-written as:

HEC=(value 1 âvalue 2 )+(noise 2 )ââEQN. 3B

The homomorphically encrypted comparison in each of the above equations 1B, 2B, and 3B, is a search result that is a comparison or difference between the query and target data (value 1 âvalue 2 ) where 0 indicates a match (value 1 âvalue 2 =0, or equivalently, value 1 =value 2 ) and a nonzero difference indicates no match (value 1 âvalue 2 â 0, or equivalently, value 1 *value 2 ), as well as homomorphic encryption (noise 1 and/or noise 2 ). Because each comparison is homomorphically encrypted, the comparison appears as a ciphertext, or random string, that is impossible or impractical for an unverified observer to decipher or learn anything from the homomorphically encrypted comparison without the private homomorphic decryption key.

The homomorphically encrypted comparison may be defined by a binary indicator of whether or not the query matches the target data for any of the keywords/concatenations of keywords or not, as above, or may be defined by a more sophisticated âmatching scoreâ based on the frequency or certainty of the matching words/concatenations of key words in the document in the target data being searched. A matching score may enable the system to order the relevance of the target data being searched based on the matching score, e.g., sequentially listed in descending order form highest to lowest matching score.

Decrypting the homomorphically encrypted comparison with the private homomorphic decryption key removes the noise generated from the homomorphically encrypted comparison (e.g., noise 1 from homomorphically encrypting the query and/or noise 2 from homomorphically encrypting the target data being searched) to get an unencrypted search result, which may be a difference of a value of the search query and a value of the target data being searched:

UR=value 1 âvalue 2 ââEQN. 4

where UR is the unencrypted result of the homomorphically encrypted comparison of each of EQNs. 1-3 in scenarios (1)-(3), respectively.

The homomorphically encrypted comparison may also be defined by other equations, for example, derived from, depending on, or permuting the terms in equations 1-3. For example, instead of the difference (value 1 âvalue 2 ) where 0 indicates a match and a nonzero difference indicates no match, a ratio (value 1 /value 2 ) may be used where a 1 indicates a match and any other ratio indicates no match, or a sum (value 1 +value 2 ) where 2Ãquery (when the query is known) indicates a match and any other sum indicates no match.

Scenarios (2) and (3), where one of the data elements (e.g., the search query or the target data being searched) is unencrypted, may be executed faster and with less computations than scenario (1) where both data elements are homomorphically encrypted, while providing the same benefit of secrecy by encrypting the search result.

In all scenarios (1)-(3), further optimization may be implemented using token-based searching to speed up computations in the homomorphic encryption domain which is typically slow and cumbersome in real-world settings, especially when large amounts of data are involved. The search environment may be optimized by using a codebook to create the token-based system that allows fast and efficient searching in the homomorphic encryption domain. Embodiments of the invention may tokenize the search query and each of a plurality of data entries or units of the target data being searched to create a token-signature for each data element. In some embodiments, the token-signature may be a concatenated string of a plurality of tokens representing a plurality of respective data, properties, parameters, or characteristics of each data element. Each concatenated token-signature is a concise manner of combining all or multiple aspects of each data element to avoid redundant searches for duplicative or similar terms. This may simplify and reduce the number of independent searches that need to be performed in the homomorphic encryption domain. For example, instead of running multiple independent searches of an address for boulevard and similar terms road and street, embodiments of the invention concatenate tokens for boulevard, road, and street into a single token-signature which requires a single HE comparison.

In order to achieve the goal of fast and efficient targeted searches, in the encrypted domain, the data elements may be initially processed to generate normalized data entries or units of the target data being searched by tokenizing a data element, such as a search query or target data being searched, by splitting it into a sequence of tokens. For example, information in the data element, such as words, numbers, or pixel values, may be mapped to tokens based on a codebook of tokens. The target data being searched may be a file to be searched itself, such as documents, images, or videos, or may refer to data located within such files, such as a field, column, or row within a document, or may be metadata of any of these data.

The data elements may be transformed into a set of tokens, for example as follows. Initially, the original data elements may be used or transformed into corresponding meta-data elements representing information extracted from the data element using rule-based or machine learning classification. Data processing standardizes the data elements, e.g., removing all common separators, operators, punctuations and non-printable characters and stemming and/or lemmatization to obtain the stem of a word that is a morphological root by removing the suffixes that present grammatical or lexical information about the word. The data elements may then be divided into one or more discrete atomic data units, such as, a number, a phoneme, discrete data blocks (e.g., a row of a table, or a pixel block of an image), etc. For example, an address, 11 Allen Street, may be broken down to the atomic data units of âeleven,â âallen,â and âstreet.â The codebook of tokens may be searched for a plurality of tokens matching each instance of each atomic data unit, such as a token representing something with the same meaning or representing a synonym. An instance may be a token mapped to the same or similar meaning as the atomic data unit. For example, instances of tokens in the token book having the same meaning as the number â11â in â11 Allen Streetâ, may be mapped to the numbers â11â, the word âelevenâ, and the meaning âaddress number.â An ordered set of the plurality of tokens for the plurality of atomic units may be generated based on the predefined token numbering e.g., in the codebook. In some embodiments, one or more processors of all data providers utilizing the system may be configured to order the plurality of tokens in a set way, such that an ordered list generated by either data provider for the same atomic unit have the same order. Alternatively, the lists may not be ordered in a specific way and, instead, all permutations of the ordering of the tokens in the list may be searched.

Using the codebook of tokens to map multiple different representations of the same or substantially similar information to a single token may reduce the number of comparisons needed to search. For example, âstreetâ, âst.â, and âstr.â, which all refer to the word âstreetâ may be mapped to the same token, reducing the number of independent HE comparisons by a factor of three. Because homomorphic encryption requires multiple computations per comparison, reducing the number of HE comparisons provides a speedup that is superliner to the factor by which the number of comparisons are reduced (e.g., more than a three-fold speed-up in the above comparison).

The use of the codebook of tokens allows embodiments of the invention to incorporate new tokens as they are created, creating a dynamic codebook that evolves as new data elements are added or preexisting data elements are deleted. For example, when a new data element is incorporated to the system and the data element contains a new word that is not already mapped to a token in the codebook, a new token and/or a new mapping to preexisting tokens may be created to map that new word to multiple relevant tokens in the codebook. Similarly, when words or data elements are deleted, one or more preexisting related tokens and/or their associated mappings may be deleted. The updated codebook should be simultaneously available to both the first and second data providers, so that both generate the same token string for the same data elements. When codebooks are locally stored at the data providers, a new updated codebook or only the changes with respect to the last version may be transmitted and/or locally stored by the first and second data providers. When codebooks are remotely stored, both data providers may access the same copy or two copies may be simultaneously updated. Accordingly, each data provider may have access to the same or an identical version of the codebook so that, for example, the same data elements are mapped to the same token string. In other words, this ensures that the same data element is not mapped to a different token string by using different data providers' token codebooks.

The codebook of tokens may also or alternatively be created and updated using publicly available information outside of the database being searched, such as one of the standard dictionaries for any language (e.g., Webster dictionary for English), a list of standard names, a list of phone numbers from a phonebook, and/or a list of street names, counties, states, and/or countries, and updated as new words, names, or numeric identifiers are found in data entries. Embodiments of the invention may utilize dictionaries, lists of abbreviations, and other information to determine words that have the same meaning and that should be mapped to the same token. In some embodiments of the invention, machine learning is utilized to create and update the codebook of tokens.

Embodiments of the invention may further speed up processing by reducing the number of comparisons in the homomorphic encryption domain by generating token signatures that are a concatenated string of a plurality of tokens that uniquely represent all tokens in the codebook associated with each data element, such as a query or target data being searched. Comparison of a single concatenated string of tokens thus replaces multiple distinct individual comparisons of each individual token in the string. For example, an address, 11 Allen Street, may be mapped to a concatenated string of tokens representing âaddress,â â11,â âeleven,â ânumber,â âstreet,â âuserID,â âusername,â etc., which are all the tokens in the codebook associated with a particular user's address. Concatenating thus reduces the number of independent searches in this example by a factor of seven. As discussed, because homomorphic encryption requires multiple computations per comparison, reducing the number of HE comparisons provides a speedup that is superliner to the factor by which the number of comparisons are reduced (e.g., more than a seven-fold speed-up in the above comparison).

Concatenation may be performed based on known patterns of information, such as words, names, and numbers, that may be grouped together, such as how an address may group together a house number, street name, city name, state name, and zip code. Concatenation may reduce the amount of searches and comparisons in the homomorphic encryption domain by utilizing searching token signature rather than searching separately for each term or token. For example, a conventional query meant to search for a particular user by its name and phone number may be mapped to a single token signature for the user including a string of concatenated tokens representing all relevant token(s) in the codebook including name, phone number, address, and all other identifying information for the user. A single search may be performed for the queries' token signature rather than performing multiple conventional searches separately for the user's name and phone number.

Since the token strings are indecipherable in the encrypted domain, the tokens may be concatenate in the same order by both the query provider and the target data provider to ensure like objects are being compared. In one example, each token may have a rank, order or unique identifier (e.g., the order in which it is listed in the codebook) and may be concatenated in that order (e.g., in ascending or descending order). Additionally or alternatively, tokens may be concatenated in a logical or rules-based order. For example, tokens for an address may be concatenated to have the tokens for the house number, street name, city name, state name, and zip code in a specific order. Alternatively, the tokens for the query and target data may be concatenated in random or different orders, and the system may be configured to compare each encrypted permutation of tokens in the signatures for the query and target data to determine if there is a match.

Some embodiments of the invention may store each token signature generated from a data element in a metadata file associated with the data element. The metadata file may additionally include a frequency of each mapping to the token signature in the data element.

One application of embodiments of the invention is for a first data provider to search the data of a second semi-trusted data provider, while keeping the search query and results secret from the second data provider. In one example, the first data provider may be a law enforcement agency conducting a financial fraud investigation, where the investigation is not public, and so cannot reveal its query, e.g., the person targeted by the investigation to the second party, e.g., a bank holding the person's financial records. The second party is considered semi-trusted because it can perform the search, but cannot access the query or results without compromising the investigation. In such a situation, the second semi-trusted data provider may perform the search on a homomorphically encrypted query, and may return a homomorphically encrypted search comparison, without decrypting or exposing the query or search results.

In some embodiments, the first data provider (e.g., a query provider), may be configured to map a first data element comprising secret data (e.g., a secret query), to a first plurality of tokens using a codebook of tokens to represent data elements. The first data provider may be configured to concatenate the first plurality of tokens to generate a first token signature comprising the first plurality of tokens that uniquely represents the first data element. The first data provider may homomorphically encrypt the first token signature using a pubic homomorphic encryption key to generate a homomorphically encrypted first token signature representing a first data element, and may transmit the first token signature to a second data provider (e.g., a semi-trusted database or cloud/file management system storing target data being searched).

Similarly, the second data provider may be configured to map a second data element (e.g., the target data being searched) to a second plurality of tokens using the same token codebook, and concatenate the second plurality of tokens to generate a second token signature comprising the second plurality of tokens that uniquely represents the second data element.

The second data provider, or another device or party, may be configured to compare the homomorphically encrypted first token signature representing the first data element and an unencrypted or homomorphically encrypted second token signature to generate a homomorphically encrypted comparison of the first and second token signatures. At least the first data element is homomorphically encrypted, so its comparison with the second data element (in unencrypted plaintext or also homomorphically encrypted) is likewise homomorphically encrypted, and so cannot be decrypted by the second data provider, which is only semi-trusted and so does not have access to the secret homomorphic decryption key. The second data provider may be configured to transmit the homomorphically encrypted comparison to a trusted third party, which may be the first data provider, or to another external party or device, to decrypt the homomorphically encrypted comparison.

In some embodiments of the invention, the trusted third party receives the homomorphically encrypted comparison, and the third party decrypts the homomorphically encrypted comparison, using the private homomorphic decryption key. The decrypted comparison may indicate if the first and second token signatures match or not respectively indicating that the search query is found or not found in the target data. Additionally or alternatively, the decrypted comparison may include a matching score indicating a frequency or certainty with which the search query is found in the target data.

In some embodiments, the second data provider may also homomorphically encrypt the second token signature using a public homomorphic encryption key, e.g., when the second data element, such as the target data being searched, comprises secret data, or could be used to derive secret data, such as a hospital record or a bank record. In some embodiments of the invention, the public homomorphic encryption key used by the first and second data providers are the same. In some embodiments of the invention the public homomorphic encryption key used by the first and second data providers are different. In some embodiments, when two different encryption keys are used, the homomorphically encrypted comparison may be decrypted by two different corresponding decryption keys, e.g., both stored at one device, or each stored at a different decryption device both of which together decrypt the data. In some embodiments, the second public homomorphic encryption key may be a proxy re-encryption key, which may switch encryptions from a first encryption key to a second encryption key. In this case a single decryption key associated with the second key may decrypt the PRE HE comparison.

In some embodiments of the invention, the second data provider may not homomorphically encrypt the second token signature, e.g., when the second data element contains only publicly accessible information, such as data entries stored on a publicly accessible database, or the second data provider is trusted.

The private key for decrypting the homomorphically encrypted comparison may only be stored on or accessible to a trusted device or system, such as the first data provider, such as the query provider, or a trusted third party (and not by a semi-trusted device, such as the second data provider). Accordingly, only the trusted device can decrypt the homomorphically encrypted comparison and accessing the results to determine if the search query is found or not in the target data.

In some embodiments of the invention, the privacy of the search query may not need to be protected and, instead, only the privacy of the target data being searched needs to be protected. In such embodiments, the first data provider may be the target data provider, such as a data warehouse or cloud/file management system, providing the first data element as the target data being searched, and the second data provider may be the query provider providing the second data element as the search query.

In some embodiments of the invention, the first data provider may be both the query provider and owns the target data being search, which is stored at the second data provider, such a semi-trusted database, semi-trusted cloud service or a semi-trusted file system. In such embodiments, the first data provider may search for its own data that is stored remotely. The first data provider may request that the second data provider performs encrypted searches of the first data provider's target data, without accessing the first data provider's target data.

For example, a first data provider, such as a hospital or bank, may store a plurality of second data elements, such as such as medical records or bank records, in one or more memories of the second data provider. The first data provider may need the second data provider to perform a search for certain second data elements without the second data provider being able to access those second data elements or being able to derive that information. Therefore, in such an application, the second data elements is encrypted at the second data provider, and the decryption key may only be present on a trusted device or system, such as the first data provider. This protocol ensures that the data stored at the second data provider, such as semi-trusted database is encrypted and cannot be unlocked since the secret decryption key is not shared. This protocol also ensures that it is possible to search target data without disclosing the target data. In such an application, the first data element and the first token signature itself may not be encrypted, for example, when the search query itself does not contain sensitive information that needs to be protected. Alternatively, the first data element and token signature may be homomorphically encrypted, for example, when the search query does not contain sensitive information that needs to be protected.

In such embodiments, the first data provider may encrypt the second data element using any standard encryption, and, transmit the encrypted second data element to the second data provider for storage. Instead of the second data provider, the first data provider may map the second data element to a second plurality of tokens using the token codebook, concatenate the second plurality of tokens to generate the second token signature, homomorphically encrypt the second token signature using the public homomorphic encryption key to generate the homomorphically encrypted second token signature, and transmit the homomorphically encrypted second token signature to the second data provider to store with a correlation to the encrypted second data element.

Reference is made to FIG. 1 which is a schematic illustration of a multi-party system and workflow for providing a fast and secure targeted search in a semi-trusted environment using homomorphic encryption, according to an embodiment of the invention. The multi-party system of FIG. 1 comprises a trusted first homomorphic encryption (HE) data provider 140 , a semi-trusted or untrusted second data provider 150 , and a trusted third party 125 (e.g., to homomorphically decrypt the search results).

In scenario (1), shown in FIG. 1 , both data providers

140 and 150 homomorphically encrypt their data. In scenarios (2) and (3), only the first data provider 140 homomorphically encrypts its first data element, while the second data provider 150 leaves its second data element unencrypted in plaintext. In scenario (2), the first data provider 140 is the query provider (generating a HE query) and the second data provider 150 is the target data provider (generating unencrypted target data). In scenario (3), the first data provider 140 is the target data provider (generating HE target data) and the second data provider 150 is the query data provider (generating an unencrypted query).

The second data provider 150 may store at least one second data element 111 , such as target data being searched. The first data provider 140 , which may be, for example, a trusted query provider requesting that the second data provider 150 determine if any of the at least one second data element 111 matches the first data element 101 without exposing the first data element 101 to the second data provider 150 . In some embodiments of the invention, the first data provider 140 may be, for example, a trusted query provider storing first data element 101 , such as a search query, and the second data provider 150 may be, for example, a semi-trusted database or cloud/file management system storing second data element 111 , such as target data being searched, or vice versa.

The first data provider 140 may map the first data element 101 to a first plurality of tokens 103 using a codebook of tokens to represent first data element 101 . The first data provider 140 may concatenate the first plurality of tokens to generate a first token signature 105 comprising the first plurality of tokens that uniquely represents the first data element 101 . The first data provider 140 may homomorphically encrypt the first token signature 107 and transmit the homomorphically encrypted first token signature 107 to a device for comparison (e.g., the second data provider 150 or another external device or party).

The second data provider 150 may map the second data element 111 to at least one second plurality of tokens 113 using the token codebook. The second data provider 150 may concatenate the at least one second plurality of tokens to generate at least one second token signature 115 . In scenario (1), e.g., when the second data element 111 contains secret data, the second data provider 150 may be configured to homomorphically encrypt the second token signature 115 using a public homomorphic encryption key to generate a homomorphically encrypted second token signature 117 representing the second data element. The public homomorphic encryption key used by the first data provider 140 and second data provider 150 may be the same or different. In scenarios (2) and (3), e.g., when the second data element 111 does not contain secret data, homomorphic encryption may be skipped, and the second token signature 115 may be left unencrypted. When an external device performs the search comparison (e.g., trusted party 125 ), the second data provider 150 may transmit the unencrypted or homomorphically encrypted second token signature 117 to the external device or party. Otherwise, the second data provider 150 may keep and store the unencrypted or homomorphically encrypted second token signature 117 in memory.

The second data provider 150 or an external device (e.g., trusted party 125 ) may be configured to perform a homomorphic search by comparing the homomorphically encrypted first token signature 107 representing the first data element 101 to each of at least one unencrypted or homomorphically encrypted second token signatures 117 representing the second data element 111 to generate at least one homomorphically encrypted comparison 119 of the first and second token signatures. Examples of computations for generating the homomorphically encrypted comparison 119 are defined in equations (1)-(3). The homomorphically encrypted comparison 119 may be transmitted to (or remain in) a trusted device for d

CLAIMS

Claims ( 20 )

The invention claimed is:

1. A system for securely searching data in a semi-trusted environment, the system comprising:

a first data provider comprising one or more first processors configured to:

map a first data element comprising secret data to a first plurality of tokens by searching a codebook storing unencrypted tokens and associated mappings to represent data elements, wherein searching the codebook associates the first plurality of tokens that match the same or substantially similar information as the first data element;

concatenate the first plurality of tokens to generate a first token signature comprising the first plurality of tokens that uniquely represents the first data element, and

homomorphically encrypt the first token signature using a public homomorphic encryption key to generate a homomorphically encrypted first token signature representing the first data element;

a second data provider comprising one or more second processors configured to:

map a second data element to a second plurality of tokens by searching the token codebook, wherein searching the codebook associates the second plurality of tokens that match the same or substantially similar information as the second data element, and wherein one of the first and second data elements is a search query and the other is target data being searched,

concatenate the second plurality of tokens to generate a second token signature comprising the second plurality of tokens that uniquely represent the second data element, and compare the homomorphically encrypted first token signature representing the first data element and an unencrypted or homomorphically encrypted second token signature to generate a homomorphically encrypted comparison of the first and second token signatures;

and a trusted party comprising one or more processors configured to:

decrypt the homomorphically encrypted comparison, using a private homomorphic decryption key, to determine that the first and second token signatures match or not respectively indicating that the search query is found or not in the target data.

2. The system of claim 1 , wherein the first data element is the search query and the second data element is the target data to be searched, or the second data element is the search query and the first data element is the target data to be searched.

3. The system of claim 1 , wherein the first data provider operates in a trusted environment, the second data provider operates in a trusted or semi-trusted environment, and the trusted party operates in a trusted environment.

4. The system of claim 1 , wherein the trusted party is the first data provider, the second data provider, or a distinct third party system.

5. The system of claim 1 , wherein the one or more first and second processors of the first and second data providers are configured to map the first and second data elements, respectively, to a plurality of tokens, comprising for each data element:

divide the data element into one or more atomic data units,

search the codebook for a plurality of tokens matching each instance of each atomic data unit, and

generate an ordered set of the plurality of tokens for the plurality of atomic units.

6. The system of claim 1 , wherein the codebook of tokens is dynamically updated by adding new tokens to the codebook and deleting preexisting tokens from the codebook, wherein the updated codebook is simultaneously available to both the first and second data providers.

7. The system of claim 1 , wherein the comparison of the first and second token signatures is a binary indication of whether or not the search query is found in the target data.

8. The system of claim 1 , wherein the comparison of the first and second token signatures is a matching score indicating a frequency or certainty with which the search query is found in the target data.

9. A first data provider for securely searching data in a semi-trusted environment, the first data provider comprising:

one or more memories configured to store a first data element comprising secret data, a codebook of unencrypted tokens and associated mappings to represent data elements, and a public homomorphic encryption key;

and one or more processors configured to:

map the first data element comprising secret data to a first plurality of tokens by searching the token codebook, wherein searching the token codebook associates the first plurality of tokens that match the same or substantially similar information as the first data element;

concatenate the first plurality of tokens to generate a first token signature comprising the first plurality of tokens that uniquely represents the first data element;

homomorphically encrypt the first token signature using the public homomorphic encryption key to generate a homomorphically encrypted first token signature representing the first data element;

transmit the homomorphically encrypted first token signature to a second data provider to compare the homomorphically encrypted first token signature representing the first data element and an unencrypted or homomorphically encrypted second token signature representing a second data element and generate a homomorphically encrypted comparison of the first and second token signatures, wherein one of the first and second data elements is a search query and the other is target data being searched; and

receive the result of decrypting the homomorphically encrypted comparison at a trusted device, using a private homomorphic decryption key, to determine that the first and second token signatures match or not respectively indicating that the search query is found or not in the target data.

10. The first data provider of claim 9 , wherein the first data provider operates in a trusted environment, the second data provider operates in a trusted or semi-trusted environment, and the trusted device operates in a trusted environment.

11. A second data provider for securely searching data in a semi-trusted environment, the second data provider comprising:

one or more memories configured to store a second data element, and a codebook of unencrypted tokens and associated mappings to represent data elements; and

one or more processors configured to:

map the second data element to a second plurality of tokens by searching the token codebook, wherein searching the codebook associates the second plurality of tokens that match the same or substantially similar information as the second data element,

concatenate the second plurality of tokens to generate a second token signature comprising the second plurality of tokens that uniquely represent the second data element,

receive, from a first data provider, a homomorphically encrypted first token signature that is a homomorphically encryption of a concatenation of a first plurality of tokens uniquely representing a first data element comprising secret data according to the codebook of tokens, wherein one of the first and second data elements is a search query and the other is target data being searched,

compare the homomorphically encrypted first token signature representing the first data element and an unencrypted or homomorphically encrypted second token signature to generate a homomorphically encrypted comparison of the first and second token signatures, and

transmit the homomorphically encrypted comparison to a trusted device to decrypt the homomorphically encrypted comparison, using a private homomorphic decryption key, to determine that the first and second token signatures match or not respectively indicating that the search query is found or not in the target data.

12. The second data provider of claim 11 , wherein the one or more memories are further configured to store the public homomorphic encryption key to generate the homomorphically encrypted second token signature.

13. The second data provider of claim 11 , wherein the first data provider operates in a trusted environment, the second data provider operates in a trusted or semi-trusted environment, and the trusted device operates in a trusted environment.

14. A method for securely searching data in a semi-trusted environment, the method comprising, at a first data provider:

mapping a first data element comprising secret data to a first plurality of tokens by searching a codebook storing unencrypted tokens and associated mappings to represent data elements, wherein searching the codebook associates the first plurality of tokens that match the same or substantially similar information as the first data element;

concatenating the first plurality of tokens to generate a first token signature comprising the first plurality of tokens that uniquely represents the first data element;

homomorphically encrypting the first token signature using a public homomorphic encryption key to generate a homomorphically encrypted first token signature representing the first data element;

transmitting the homomorphically encrypted first token signature to a second data provider to compare the homomorphically encrypted first token signature representing the first data element and an unencrypted or homomorphically encrypted second token signature representing a second data element and generate a homomorphically encrypted comparison of the first and second token signatures, wherein one of the first and second data elements is a search query and the other is target data being searched;

receiving the result of decrypting the homomorphically encrypted comparison at a trusted device,

using a private homomorphic decryption key, to determine that the first and second token signatures match or not respectively indicating that the search query is found or not in the target data.

15. The method of claim 14 , wherein the first data element is the search query and the second data element is the target data to be searched, or the second data element is the search query and the first data element is the target data to be searched.

16. The method of claim 14 , wherein the first data provider operates in a trusted environment, and the second data provider operates in a trusted or semi-trusted environment.

17. The method of claim 14 , wherein mapping the first element to the first plurality of tokens comprises: dividing the data element into one or more atomic data units; searching the codebook for a plurality of tokens matching each instance of each atomic data unit; and generating an ordered set of the plurality of tokens for the plurality of atomic units.

18. The method of claim 14 , further comprising dynamically updating the codebook of tokens by adding new tokens to the codebook and deleting preexisting tokens from the codebook, wherein the updated codebook is simultaneously available to both the first and second data providers.

19. The method of claim 14 , wherein the comparison of the first and second token signatures is a binary indication of whether or not the search query is found in the target data.

20. The method of claim 14 , wherein the comparison of the first and second token signatures is a matching score indicating a frequency or certainty with which the search query is found in the target data.

US16/739,313

2019-01-10

2020-01-10

Secure search of secret data in a semi-trusted environment using homomorphic encryption

Active

2040-06-06

US11764940B2

( en )

Priority Applications (1)

Application Number

Priority Date

Filing Date

Title

US16/739,313

US11764940B2

( en )

2019-01-10

2020-01-10

Secure search of secret data in a semi-trusted environment using homomorphic encryption

Applications Claiming Priority (2)

Application Number

Priority Date

Filing Date

Title

US201962790696P

2019-01-10

US16/739,313

US11764940B2

( en )

2019-01-10

2020-01-10

Secure search of secret data in a semi-trusted environment using homomorphic encryption

Publications (2)

Publication Number

Publication Date

US20200228308A1

US20200228308A1 ( en )

2020-07-16

US11764940B2

true

US11764940B2 ( en )

2023-09-19

Family

ID=71517065

Family Applications (1)

Application Number

Title

Priority Date

Filing Date

US16/739,313

Active

2040-06-06

US11764940B2

( en )

2019-01-10

2020-01-10

Secure search of secret data in a semi-trusted environment using homomorphic encryption

Country Status (1)

Country

Link

( 1 )

US11764940B2

( en )

Cited By (1)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20240176903A1

( en )

2021-03-22

2024-05-30

Nippon Telegraph And Telephone Corporation

Secure search method, system thereof, apparatus thereof, encryption apparatus, searcher terminal, and program

Families Citing this family (16)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US11038672B2

( en )

2018-06-01

2021-06-15

Duality Technologies, Inc.

Secure and distributed management of a proxy re-encryption key ledger

WO2021087073A1

( en )

2019-10-30

2021-05-06

Via Science, Inc.

Secure outsourcing of a multiplication

US11222134B2

( en )

2020-03-04

2022-01-11

Sotero, Inc.

System and methods for data encryption and application-agnostic querying of encrypted data

US12554895B2

( en )

2020-10-27

2026-02-17

Portal26, Inc.

Encrypted analytical vault for trusted access

US20220147645A1

( en )

2020-11-12

2022-05-12

IOR Analytics, LLC

Method, apparatus, and system for discovering private data using configurable rules

CN113127536B

( en )

2021-04-14

2023-07-28

ä¸æµ·åæä¿¡æ¯ç§ææéè´£ä»»å¬å¸

An Offline Fuzzy Matching System Based on Homomorphic Configuration Encryption

US11501013B1

( en )

2021-07-09

2022-11-15

Sotero, Inc.

Autonomous machine learning methods for detecting and thwarting malicious database access

US12386785B2

( en )

2021-10-15

2025-08-12

Lognovations Holdings, Llc

Encoding / decoding system and method

CN114500006B

( en )

2022-01-05

2023-08-04

æ¯ä»å®(æå·)ä¿¡æ¯ææ¯æéå¬å¸

Query request processing method and device

CN118575174A

( en )

2022-01-20

2024-08-30

çå®¶é£å©æµ¦æéå¬å¸

Method and system for compressed fast encryption similarity search and database analysis

CN115085897B

( en )

2022-05-23

2025-01-03

æ¯ä»å®(æå·)ä¿¡æ¯ææ¯æéå¬å¸

Data processing method, device and computer equipment for protecting privacy

WO2024059676A1

( en )

2022-09-14

2024-03-21

Sotero, Inc.

Autonomous machine learning methods for detecting and thwarting ransomware attacks

CN116132012B

( en )

2022-11-07

2025-07-22

è¥¿å®çµåç§æå¤§å¦å¹¿å·ç ç©¶é¢

Trusted privacy data comparison method, storage device and intelligent terminal thereof

US12255980B2

( en )

2023-01-03

2025-03-18

International Business Machines Corporation

Homomorphic encryption key management

WO2025098294A1

( en )

2023-11-07

2025-05-15

Huawei Technologies Co., Ltd.

Task-level homomorphic encryption management method and apparatus

CN119884149B

( en )

2024-12-30

2025-12-12

åäº¬æµ·æ³°æ¹åç§æè¡ä»½æéå¬å¸

Data anonymity query method, apparatus, equipment and medium based on homomorphic encryption

Citations (294)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US3673399A

( en )

1970-05-28

1972-06-27

Ibm

Fft processor with unique addressing

US3851162A

( en )

1973-04-18

1974-11-26

Nasa

Continuous fourier transform method and apparatus

US4450525A

( en )

1981-12-07

1984-05-22

Ibm Corporation

Control unit for a functional processor

US4493048A

( en )

1982-02-26

1985-01-08

Carnegie-Mellon University

Systolic array apparatuses for matrix computations

US4689762A

( en )

1984-09-10

1987-08-25

Sanders Associates, Inc.

Dynamically configurable fast Fourier transform butterfly circuit

US4791590A

( en )

1985-11-19

1988-12-13

Cornell Research Foundation, Inc.

High performance signal processor

US4896287A

( en )

1988-05-31

1990-01-23

General Electric Company

Cordic complex multiplier

US4949294A

( en )

1987-10-30

1990-08-14

Thomson-Csf

Computation circuit using residual arithmetic

US4972358A

( en )

1989-06-08

1990-11-20

General Electric Company

Computation of discrete fourier transform using recursive techniques

US5177691A

( en )

1990-11-30

1993-01-05

General Electric Company

Measuring velocity of a target by Doppler shift, using improvements in calculating discrete Fourier transform

US5272755A

( en )

1991-06-28

1993-12-21

Matsushita Electric Industrial Co., Ltd.

Public key cryptosystem with an elliptic curve

US5317639A

( en )

1989-10-04

1994-05-31

Teledyne Industries, Inc.

Non-linear block substitution devices derived by constructive corruption

US5377207A

( en )

1992-09-03

1994-12-27

The United States Of America As Represented By The United States National Aeronautics And Space Administration

Mappings between codewords of two distinct (N,K) Reed-Solomon codes over GF (2J)

US5627863A

( en )

1994-07-15

1997-05-06

Amati Communications Corporation

Frame synchronization in multicarrier transmission systems

US5647001A

( en )

1989-10-04

1997-07-08

Litton Systems, Inc.

Nonlinear dynamic substitution devices and methods for block substitutions employing coset decompositions and direct geometric generation

US5717620A

( en )

1995-10-24

1998-02-10

Airnet Communications Corporation

Improved-accuracy fast-Fourier-transform butterfly circuit

US5831883A

( en )

1997-05-27

1998-11-03

United States Of America As Represented By The Secretary Of The Air Force

Low energy consumption, high performance fast fourier transform

US6003056A

( en )

1997-01-06

1999-12-14

Auslander; Lewis

Dimensionless fast fourier transform method and apparatus

US6073154A

( en )

1998-06-26

2000-06-06

Xilinx, Inc.

Computing multidimensional DFTs in FPGA

US6081821A

( en )

1993-08-05

2000-06-27

The Mitre Corporation

Pipelined, high-precision fast fourier transform processor

US6098088A

( en )

1995-11-17

2000-08-01

Teracom Ab

Real-time pipeline fast fourier transform processors

US6098152A

( en )

1997-10-17

2000-08-01

International Business Machines Corporation

Method and apparatus for miss sequence cache block replacement utilizing a most recently used state

US6128764A

( en )

1997-02-06

2000-10-03

California Institute Of Technology

Quantum error-correcting codes and devices

US6144740A

( en )

1998-05-20

2000-11-07

Network Security Technology Co.

Method for designing public key cryptosystems against fault-based attacks with an implementation

US6167392A

( en )

1997-10-09

2000-12-26

Telcordia Technologies, Inc.

Method and apparatus for private information retrieval from a single electronic storage device

US6240143B1

( en )

1998-08-18

2001-05-29

Qualcomm Inc.

Method and apparatus for the reflection and transmission of quasi orthogonal vectors

US6263436B1

( en )

1996-12-17

2001-07-17

At&T Corp.

Method and apparatus for simultaneous electronic exchange using a semi-trusted third party

US20010009030A1

( en )

1999-12-20

2001-07-19

Philippe Piret

Encoding method and device, decoding method and device, and systems using them

US20010019630A1

( en )

1994-07-14

2001-09-06

America Online, Inc.

Method for transferring and displaying compressed images

US6308295B1

( en )

1996-10-08

2001-10-23

Arizona Board Of Regents

Parallel spectral reed-solomon encoder and decoder

US20010034640A1

( en )

2000-01-27

2001-10-25

David Chaum

Physical and digital secret ballot systems

US20020009197A1

( en )

2000-03-31

2002-01-24

Keyes Michael P.

Cryptographic method for color images and digital cinema

US20020027986A1

( en )

1999-12-20

2002-03-07

Tonnes Brekne

Encryption of programs represented as polynomial mappings and their computations

US20020049601A1

( en )

1998-10-28

2002-04-25

Nadarajah Asokan

Optimistic fair exchange protocols

US6408368B1

( en )

1999-06-15

2002-06-18

Sun Microsystems, Inc.

Operating system page placement to maximize cache data reuse

US6438554B1

( en )

1997-10-09

2002-08-20

Telcordia Technologies, Inc.

System and method for private information retrieval from a single electronic storage device using verifiable commodities

US20020114452A1

( en )

2000-12-21

2002-08-22

Hamilton Jon W.

Method and system for digital image authentication

US6477554B1

( en )

1999-09-17

2002-11-05

Globespanvirata, Inc.

Circuit and method for computing a fast fourier transform

US20020178194A1

( en )

1998-05-18

2002-11-28

Yair Aizenberg

Method for computing a fast fourier transform and associated circuit for addressing a data memory

US20030021365A1

( en )

2001-06-08

2003-01-30

Min Jonathan S.

Robust burst detection and acquisition system and method

US20030065632A1

( en )

2001-05-30

2003-04-03

Haci-Murat Hubey

Scalable, parallelizable, fuzzy logic, boolean algebra, and multiplicative neural network based classifier, datamining, association rule finder and visualization software tool

US6549925B1

( en )

1998-05-18

2003-04-15

Globespanvirata, Inc.

Circuit for computing a fast fourier transform

US20030081785A1

( en )

2001-08-13

2003-05-01

Dan Boneh

Systems and methods for identity-based encryption and related cryptographic techniques

US20030182554A1

( en )

2002-03-21

2003-09-25

Gentry Craig B.

Authenticated ID-based cryptosystem with no key escrow

US6721349B1

( en )

1999-01-28

2004-04-13

Qualcomm Incorporated

Method and apparatus for reducing peak-to-average ratio in a CDMA communication system

US20040105546A1

( en )

2002-11-19

2004-06-03

Leon Chernyak

Geometry-Based Symmetric Cryptosystem Method

US20040151307A1

( en )

2003-02-03

2004-08-05

Lih-Chung Wang

Tractable rational map public-key system

US20040156498A1

( en )

2001-07-12

2004-08-12

Paeng Seong Hun

Public key cryptosystem using finite non abelian groups

US6792108B1

( en )

1999-06-08

2004-09-14

Universite de MontrÃ«al

Aperiodic encryption for digital data

US20040179622A1

( en )

2002-12-13

2004-09-16

Stmicroelectronics S.R.I.

Method of performing a simon's or a shor's quantum algorithm and relative quantum gate

US6801579B1

( en )

2000-03-09

2004-10-05

Lucent Technologies Inc.

Method and wireless communication using unitary space-time signal constellations

US20040205036A1

( en )

2001-04-30

2004-10-14

Nagabhushana Prabhu

Optimization on lie manifolds

US20040223616A1

( en )

2003-04-07

2004-11-11

Stmicroelectronics S.R.I.

Encryption process employing chaotic maps and digital signature process

US20050055546A1

( en )

2003-09-08

2005-03-10

Abb Research Ltd

Data encryption on the physical layer of a data transmission system

US20050094806A1

( en )

2003-11-03

2005-05-05

Microsoft Corporation

Use of isogenies for design of cryptosystems

US20050138516A1

( en )

2003-12-04

2005-06-23

Yedidia Jonathan S.

Decoding Reed-Solomon codes and related codes represented by graphs

US20050246533A1

( en )

2002-08-28

2005-11-03

Docomo Communications Laboratories Usa, Inc.

Certificate-based encryption and public key infrastructure

US20060075010A1

( en )

2004-10-05

2006-04-06

Wadleigh Kevin R

Fast fourier transform method and apparatus

US20060098814A1

( en )

2004-11-08

2006-05-11

King Fahd University Of Petroleum And Minerals

Method for communicating securely over an insecure communication channel

US20060129800A1

( en )

2004-12-14

2006-06-15

Microsoft Corporation

Cryptographically processing data based on a cassels-tate pairing

US20060140401A1

( en )

2000-12-08

2006-06-29

Johnson Harold J

System and method for protecting computer software from a white box attack

US20060177051A1

( en )

2005-02-08

2006-08-10

Microsoft Corporation

Cryptographic applications of the Cartier pairing

US20060206554A1

( en )

2005-03-14

2006-09-14

Microsoft Corporation

Computing modular polynomials modulo large primes

US20060286587A1

( en )

2005-06-15

2006-12-21

Gen-Probe Incorporated

Methods for quantitative analysis of a nucleic acid amplification reaction

US7158569B1

( en )

1999-01-19

2007-01-02

Penner Robert C

Methods of digital filtering and multi-dimensional data compression using the farey quadrature and arithmetic, fan, and modular wavelets

US20070088774A1

( en )

2003-04-17

2007-04-19

Zhizhong Li

Computer technical solution of mixed q-nary and carry line digital engineering method

US20070095909A1

( en )

2002-02-20

2007-05-03

David Chaum

Ballot integrity systems

US20070106718A1

( en )

2005-11-04

2007-05-10

Shum Hoi L

Fast fourier transform on a single-instruction-stream, multiple-data-stream processor

US20070162373A1

( en )

2002-06-18

2007-07-12

Phil Kongtcheu

Methods, systems and computer program products to facilitate the formation and trading of derivatives contracts

US20070165843A1

( en )

2006-01-13

2007-07-19

Microsoft Corporation

Trapdoor Pairings

US20070271326A1

( en )

2004-09-30

2007-11-22

Zhizhong Li

Technical Solution to Written Calculations Engineering of the Digital Engineering Method for Hybrid Numeral Carry System and Carry Line

US20070294183A1

( en )

2006-05-24

2007-12-20

Camenisch Jan L

Method for automatically validating a transaction, electronic payment system and computer program

US20080036760A1

( en )

2005-01-26

2008-02-14

International Business Machines Corporation

Method, Apparatus And Computer Program Product Enabling A Dynamic Global Parameterization Of Triangle Meshes Over Polygonal Domain Meshes

US20080063110A1

( en )

2004-01-28

2008-03-13

Amir Averbuch

Method of Transmitting Data Using Space Time Block Codes

US20080140750A1

( en )

2006-12-12

2008-06-12

Arm Limited

Apparatus and method for performing rearrangement and arithmetic operations on data

US20080201394A1

( en )

2004-11-08

2008-08-21

Zhizhong Li

Computer Technical Solution Of The Digital Engineering Method Of Hybrid Numeral Carry System And Carry Line

US20080208560A1

( en )

2007-02-23

2008-08-28

Harold Joseph Johnson

System and method of interlocking to protect software - mediated program and device behaviors

US20080263285A1

( en )

2007-04-20

2008-10-23

Siport, Inc.

Processor extensions for accelerating spectral band replication

US20080298582A1

( en )

2007-06-04

2008-12-04

Murata Kikai Kabushiki Kaisha

Broadcast Cryptosystem, Crypto-Communication Method, Decryption Device, and Decryption Program

US20090010428A1

( en )

2007-07-08

2009-01-08

Farshid Delgosha

Asymmetric cryptosystem employing paraunitary matrices

US20090106633A1

( en )

2005-03-04

2009-04-23

Tokyo Institute Of Technology

Method and apparatus for correcting and detecting multiple spotty-byte errors within a byte occurred in a limited number of bytes

US20090112955A1

( en )

2007-10-30

2009-04-30

Arm Limited

Apparatus and method for performing magnitude detection of arthimetic operations

US20090135717A1

( en )

2007-11-26

2009-05-28

Iowa State University Research Foundation, Inc.

Network protection using network coding

US20090160576A1

( en )

2007-12-24

2009-06-25

Telefonaktiebolaget Lm Ericsson (Publ)

Passive Fourier Transform Circuits and Butler Matrices

US20090249162A1

( en )

2008-03-28

2009-10-01

Cen Jung Tjhai

Error correction system using the discrete fourier transform

US20090285332A1

( en )

2004-03-31

2009-11-19

Damen Mohamed O

Method of Systematic Construction of Space-Time Constellations, System and Method of Transmitting Space-Time Constellations

US20090307218A1

( en )

2005-05-16

2009-12-10

Roger Selly

Associative memory and data searching system and method

US20090327255A1

( en )

2008-06-26

2009-12-31

Microsoft Corporation

View matching of materialized xml views

US20100002872A1

( en )

2006-09-01

2010-01-07

Kyoji Shibutani

Data transformation apparatus, data transformation method, and computer program

US20100111296A1

( en )

2008-10-30

2010-05-06

Certicom Corp.

Collision-resistant elliptic curve hash functions

US20100131807A1

( en )

2008-11-26

2010-05-27

I-Shou University

Decoding algorithm for quadratic residue codes

US20100146299A1

( en )

2008-10-29

2010-06-10

Ashwin Swaminathan

System and method for confidentiality-preserving rank-ordered search

US20100169346A1

( en )

2008-12-31

2010-07-01

Nokia Corporation

Method, apparatus, and computer program product for polynomial-based data transformation and utilization

US20100251378A1

( en )

2006-12-21

2010-09-30

Telefonaktiebolaget L M Ericsson (Publ)

Obfuscating Computer Program Code

US20100332942A1

( en )

2008-09-10

2010-12-30

Arm Limited

Memory controller for NAND memory using forward error correction

US20110013716A1

( en )

2009-07-17

2011-01-20

Mitre Corporation

Time-Frequency Space Constructions of Families of Signals

US20110107201A1

( en )

2009-10-29

2011-05-05

Microsoft Corporation

Representing complex document structure via simpler structure through isomorphism

US20110125439A1

( en )

2005-07-13

2011-05-26

Venkata Guruprasad

Distance-dependent spectra with uniform sampling spectrometry

US7966359B2

( en )

2006-03-22

2011-06-21

Qualcomm Incorporated

Wideband frequency discriminator and radiolocalization receiver

US20120030468A1

( en )

2010-07-29

2012-02-02

Charalampos Papamanthou

System and m

Secure search of secret data in a semi-trusted environment using homomorphic … — Duality Technologies, Inc. (US11764940B2)

Related documents