ABSTRACT
Abstract
In aspects of variable relinearization in homomorphic encryption, a computing device stores homomorphic encrypted data as a dataset, and implements an encryption application that can perform a multiplication operation on a ciphertext in the homomorphic encrypted data, where the multiplication operation contributes to increase a noise component in the ciphertext. The encryption application can determine a relinearization amount by which to relinearize the ciphertext after the multiplication operation, where the determination is effective to optimize a noise increase in the ciphertext based at least in part on projected subsequent multiplication operations on the ciphertext. The encryption application can then relinearize the ciphertext utilizing the determined relinearization amount that optimizes the noise increase in the ciphertext for optimal relinearization performance.
Description
BACKGROUND
Cloud-based storage and on-line services are readily available and continue to develop rapidly. Enterprise customers, such as in the medical and financial sectors, save money and streamline business processes by outsourcing the storage and computation of their data to public storage, such as provided by cloud-based services. Instead of storing and managing a large amount of data locally, a medical service provider, for example, can utilize cloud storage for electronic medical records of patient data, and a financial service provider can utilize the cloud storage for financial data and customer records. However, using public cloud-based storage can potentially expose data, compromising the privacy and security of the personal medical, financial, and other sensitive data.
One effective technique is to store private and sensitive data in an encrypted form in the public cloud-based storage, and perform computations on the encrypted data directly. However, typical block ciphers do not allow encrypted data to be used in encrypted form, and meaningful computation on the encrypted data would either require it to be returned to the owner of the data for decryption, or alternatively, for the cloud-based storage service to have access to the decryption key. Homomorphic encryption refers to encryption schemes used to encrypt data in a way that allows evaluating Boolean or arithmetic circuits on the data while it remains encrypted. Homomorphic encryption may also refer to encryption schemes with less capabilities, such as for performing only additions or only multiplications on the encrypted data. However, the conventional techniques used to evaluate homomorphic encrypted data are significantly less efficient than operating on unencrypted data, such as if the data is returned to the owner of the data for decryption.
SUMMARY
This Summary introduces features and concepts of variable relinearization in homomorphic encryption, which is further described below in the Detailed Description and/or shown in the Figures. This Summary should not be considered to describe essential features of the claimed subject matter, nor used to determine or limit the scope of the claimed subject matter.
Variable relinearization in homomorphic encryption is described. In aspects, a computing device stores homomorphic encrypted data as a dataset, and implements an encryption application that can perform a multiplication operation on a ciphertext in the homomorphic encrypted data of the dataset, where the multiplication operation contributes to increase a noise component in the ciphertext. The encryption application can determine a relinearization amount by which to relinearize the ciphertext after the multiplication operation. The relinearization amount is determined effective to optimize a noise increase in the ciphertext attributable to relinearizing the ciphertext and based in part on projected subsequent multiplication operation on the ciphertext. The encryption application can then relinearize the ciphertext utilizing the determined relinearization amount that optimizes the noise increase in the ciphertext, such as for optimal relinearization performance.
In other aspects of variable relinearization in homomorphic encryption, the encryption application is implemented to estimate a noise level in the ciphertext based on an initial noise component in the ciphertext and based on the noise increase to the noise component from the multiplication operation. The encryption application can then determine the relinearization amount by which to relinearize the ciphertext based on the estimated noise level in the ciphertext. The relinearization amount can be determined to be not greater than a current noise level in the ciphertext. The current noise level in the ciphertext is based on the initial noise component in the ciphertext and the noise increase to the noise component from the multiplication operation. The encryption application is implemented to estimate the noise increase of the noise component based on a type of the ciphertext multiplication operation and input parameters of the multiplication operation. In an implementation, the encryption application can determine the relinearization amount as a size of evaluation keys of an encryption scheme used to generate the homomorphic encrypted data. The determination of the size of the evaluation keys is effective to optimize the noise increase in the ciphertext resulting from the relinearization.
BRIEF DESCRIPTION OF THE DRAWINGS
Aspects of variable relinearization in homomorphic encryption are described with reference to the following Figures. The same numbers may be used throughout to reference like features and components that are shown in the Figures:
FIG. 1 illustrates an example computing device in which aspects of variable relinearization in homomorphic encryption can be implemented as described herein.
FIG. 2 illustrates an example system in which aspects of variable relinearization in homomorphic encryption can be implemented as described herein.
FIG. 3 illustrates an example method of variable relinearization in homomorphic encryption in accordance with techniques described herein.
FIG. 4 illustrates an example method of variable relinearization in homomorphic encryption in accordance with techniques described herein.
FIG. 5 illustrates an example system with an example device that can implement variable relinearization in homomorphic encryption as described herein.
DETAILED DESCRIPTION
Aspects of variable relinearization in homomorphic encryption are described, such as to implement techniques for relinearizing ciphertexts in homomorphic encrypted data after multiplication operations. Generally, homomorphic encryption can be used to encrypt data in a way that allows computations to be performed on the encrypted data without decrypting it, such as evaluating Boolean or arithmetic circuits on the encrypted data while it remains encrypted. Utilizing homomorphic encryption has applications in privacy-preserving data analysis. However, in homomorphic encrypted data, the ciphertexts contain a noise component, which increases when computations, such as multiplication operations, are performed on the ciphertexts. Once the noise component in a ciphertext reaches a certain bound, the ciphertext can become corrupted to the point that it cannot be decrypted accurately, and the data is lost. Thus, the noise growth in a ciphertexts is a limiting factor in the number of computations that can be performed on a ciphertext.
A technique that is used to control the noise increase, also referred to as the noise growth in ciphertexts, is relinearization. However, relinearization itself also adds noise to a ciphertext that is being relinearized, while at the same time optimizing the noise increase in further operations. As described herein, the relinearization of a ciphertext can be variable to approximate or match the noise component in the ciphertext, and the variable relinearization amount is based on the current noise component of the ciphertext. The relinearization by variable amounts results in noise growth that minimizes a change in the quality of the ciphertext at the time when relinearization is performed. The variable relinearization controls how much noise is added in relinearization of a ciphertext, thus resulting in a smaller overall noise, allowing additional homomorphic operations to be performed on the ciphertext. In aspects of variable relinearization in homomorphic encryption, the relinearization of a ciphertext by variable amounts can be based on the past and the future of the computation that is to be performed on the ciphertext to optimize the overall noise increase.
Aspects of variable relinearization are implemented to optimize the noise component in ciphertexts, and can include not only minimizing noise increase in a ciphertext, but also by determining to add noise to the noise component of the ciphertext. The variable relinearization can be performed in a way that adds almost no noise to a ciphertext, but this lends to slow processing. A trade-off of performing relinearization faster is that more noise may be added to the noise component of the ciphertext. However, based on a determination of the amount of relinearization effective to optimize the noise component in the ciphertext, an optimally larger amount of noise increase may be determined for optimal relinearization performance. In some instances where relinearization performance is a critical aspect, and if there is available space for noise increase at the end of a computation, the relinearization can be performed to add as much noise as possible to the noise component of a ciphertext, which will be the fastest performance. It should also be noted that relinearization performance can be determined across multiple executions of relinearization, taking into account the overall performance of a computation, and not necessarily just evaluating each individual relinearization.
While features and concepts of variable relinearization in homomorphic encryption can be implemented in any number of different devices, systems, networks, environments, and/or configurations, aspects of variable relinearization in homomorphic encryption are described in the context of the following example devices, systems, and methods.
FIG. 1 illustrates an example computing device 100 in which aspects of variable relinearization in homomorphic encryption can be implemented. The computing device 100 can be implemented with various components, such as a processing system 102 and memory 104 (e.g., non-volatile, physical memory), and with any number and combination of different components as further described with reference to the example device shown in FIG. 5 . In implementations, the processing system 102 may include multiple and/or different processors, such as a microprocessor, a separate graphics processor, and/or a separate high-speed, dedicated processor.
In this example, homomorphic encrypted data 106 is stored in the memory 104 , such as a dataset of homomorphic encrypted data of ciphertexts 108 . The homomorphic encrypted data 106 can include N (bit) strings of some length L, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time. The encrypted bits in the dataset of homomorphic encrypted data 106 can be denoted as R {1,1} , . . . R {N,L} , in rows and columns of the encrypted bits.
The techniques of variable relinearization in homomorphic encryption are described in the general context of evaluating the homomorphic encrypted data 106 , and homomorphic encryption algorithms 110 are applied to evaluate the homomorphic encrypted data in the dataset while the data remains encrypted. In this example, the homomorphic encryption algorithms 110 apply multiplication operations 112 on the ciphertexts 108 of the homomorphic encrypted data. The multiplication operations 112 on the ciphertexts 108 initiate the need for relinearization, and as described herein, can be implemented as variable relinearization in homomorphic encryption.
The computing device 100 implements the encryption application 114 that can include various algorithms to implement the techniques of variable relinearization in homomorphic encryption, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102 . The encryption application 114 can be stored in computer-readable storage memory (e.g., the memory 104 ), such as any suitable memory device or electronic data storage implemented in the computing device. Further, although the various algorithms are shown and described as modules of the encryption application 114 , any one or combination of the algorithms may be implemented separately or together, and may be independent of the encryption application. An overview of the encryption application 114 and the various algorithms is described following, with additional implementation details described with reference to FIG. 2 .
In aspects of variable relinearization in homomorphic encryption, the encryption application 114 can apply one or more of the various algorithms 110 to perform homomorphic operations, such as the multiplication operations 112 , on the ciphertexts 108 of the homomorphic encrypted data 106 . As noted above, generally the <figure-callout id="112" label="multiplication operatio
BACKGROUND
Cloud-based storage and on-line services are readily available and continue to develop rapidly. Enterprise customers, such as in the medical and financial sectors, save money and streamline business processes by outsourcing the storage and computation of their data to public storage, such as provided by cloud-based services. Instead of storing and managing a large amount of data locally, a medical service provider, for example, can utilize cloud storage for electronic medical records of patient data, and a financial service provider can utilize the cloud storage for financial data and customer records. However, using public cloud-based storage can potentially expose data, compromising the privacy and security of the personal medical, financial, and other sensitive data.
One effective technique is to store private and sensitive data in an encrypted form in the public cloud-based storage, and perform computations on the encrypted data directly. However, typical block ciphers do not allow encrypted data to be used in encrypted form, and meaningful computation on the encrypted data would either require it to be returned to the owner of the data for decryption, or alternatively, for the cloud-based storage service to have access to the decryption key. Homomorphic encryption refers to encryption schemes used to encrypt data in a way that allows evaluating Boolean or arithmetic circuits on the data while it remains encrypted. Homomorphic encryption may also refer to encryption schemes with less capabilities, such as for performing only additions or only multiplications on the encrypted data. However, the conventional techniques used to evaluate homomorphic encrypted data are significantly less efficient than operating on unencrypted data, such as if the data is returned to the owner of the data for decryption.
SUMMARY
This Summary introduces features and concepts of variable relinearization in homomorphic encryption, which is further described below in the Detailed Description and/or shown in the Figures. This Summary should not be considered to describe essential features of the claimed subject matter, nor used to determine or limit the scope of the claimed subject matter.
Variable relinearization in homomorphic encryption is described. In aspects, a computing device stores homomorphic encrypted data as a dataset, and implements an encryption application that can perform a multiplication operation on a ciphertext in the homomorphic encrypted data of the dataset, where the multiplication operation contributes to increase a noise component in the ciphertext. The encryption application can determine a relinearization amount by which to relinearize the ciphertext after the multiplication operation. The relinearization amount is determined effective to optimize a noise increase in the ciphertext attributable to relinearizing the ciphertext and based in part on projected subsequent multiplication operation on the ciphertext. The encryption application can then relinearize the ciphertext utilizing the determined relinearization amount that optimizes the noise increase in the ciphertext, such as for optimal relinearization performance.
In other aspects of variable relinearization in homomorphic encryption, the encryption application is implemented to estimate a noise level in the ciphertext based on an initial noise component in the ciphertext and based on the noise increase to the noise component from the multiplication operation. The encryption application can then determine the relinearization amount by which to relinearize the ciphertext based on the estimated noise level in the ciphertext. The relinearization amount can be determined to be not greater than a current noise level in the ciphertext. The current noise level in the ciphertext is based on the initial noise component in the ciphertext and the noise increase to the noise component from the multiplication operation. The encryption application is implemented to estimate the noise increase of the noise component based on a type of the ciphertext multiplication operation and input parameters of the multiplication operation. In an implementation, the encryption application can determine the relinearization amount as a size of evaluation keys of an encryption scheme used to generate the homomorphic encrypted data. The determination of the size of the evaluation keys is effective to optimize the noise increase in the ciphertext resulting from the relinearization.
BRIEF DESCRIPTION OF THE DRAWINGS
Aspects of variable relinearization in homomorphic encryption are described with reference to the following Figures. The same numbers may be used throughout to reference like features and components that are shown in the Figures:
FIG. 1 illustrates an example computing device in which aspects of variable relinearization in homomorphic encryption can be implemented as described herein.
FIG. 2 illustrates an example system in which aspects of variable relinearization in homomorphic encryption can be implemented as described herein.
FIG. 3 illustrates an example method of variable relinearization in homomorphic encryption in accordance with techniques described herein.
FIG. 4 illustrates an example method of variable relinearization in homomorphic encryption in accordance with techniques described herein.
FIG. 5 illustrates an example system with an example device that can implement variable relinearization in homomorphic encryption as described herein.
DETAILED DESCRIPTION
Aspects of variable relinearization in homomorphic encryption are described, such as to implement techniques for relinearizing ciphertexts in homomorphic encrypted data after multiplication operations. Generally, homomorphic encryption can be used to encrypt data in a way that allows computations to be performed on the encrypted data without decrypting it, such as evaluating Boolean or arithmetic circuits on the encrypted data while it remains encrypted. Utilizing homomorphic encryption has applications in privacy-preserving data analysis. However, in homomorphic encrypted data, the ciphertexts contain a noise component, which increases when computations, such as multiplication operations, are performed on the ciphertexts. Once the noise component in a ciphertext reaches a certain bound, the ciphertext can become corrupted to the point that it cannot be decrypted accurately, and the data is lost. Thus, the noise growth in a ciphertexts is a limiting factor in the number of computations that can be performed on a ciphertext.
A technique that is used to control the noise increase, also referred to as the noise growth in ciphertexts, is relinearization. However, relinearization itself also adds noise to a ciphertext that is being relinearized, while at the same time optimizing the noise increase in further operations. As described herein, the relinearization of a ciphertext can be variable to approximate or match the noise component in the ciphertext, and the variable relinearization amount is based on the current noise component of the ciphertext. The relinearization by variable amounts results in noise growth that minimizes a change in the quality of the ciphertext at the time when relinearization is performed. The variable relinearization controls how much noise is added in relinearization of a ciphertext, thus resulting in a smaller overall noise, allowing additional homomorphic operations to be performed on the ciphertext. In aspects of variable relinearization in homomorphic encryption, the relinearization of a ciphertext by variable amounts can be based on the past and the future of the computation that is to be performed on the ciphertext to optimize the overall noise increase.
Aspects of variable relinearization are implemented to optimize the noise component in ciphertexts, and can include not only minimizing noise increase in a ciphertext, but also by determining to add noise to the noise component of the ciphertext. The variable relinearization can be performed in a way that adds almost no noise to a ciphertext, but this lends to slow processing. A trade-off of performing relinearization faster is that more noise may be added to the noise component of the ciphertext. However, based on a determination of the amount of relinearization effective to optimize the noise component in the ciphertext, an optimally larger amount of noise increase may be determined for optimal relinearization performance. In some instances where relinearization performance is a critical aspect, and if there is available space for noise increase at the end of a computation, the relinearization can be performed to add as much noise as possible to the noise component of a ciphertext, which will be the fastest performance. It should also be noted that relinearization performance can be determined across multiple executions of relinearization, taking into account the overall performance of a computation, and not necessarily just evaluating each individual relinearization.
While features and concepts of variable relinearization in homomorphic encryption can be implemented in any number of different devices, systems, networks, environments, and/or configurations, aspects of variable relinearization in homomorphic encryption are described in the context of the following example devices, systems, and methods.
FIG. 1 illustrates an example computing device 100 in which aspects of variable relinearization in homomorphic encryption can be implemented. The computing device 100 can be implemented with various components, such as a processing system 102 and memory 104 (e.g., non-volatile, physical memory), and with any number and combination of different components as further described with reference to the example device shown in FIG. 5 . In implementations, the processing system 102 may include multiple and/or different processors, such as a microprocessor, a separate graphics processor, and/or a separate high-speed, dedicated processor.
In this example, homomorphic encrypted data 106 is stored in the memory 104 , such as a dataset of homomorphic encrypted data of ciphertexts 108 . The homomorphic encrypted data 106 can include N (bit) strings of some length L, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time. The encrypted bits in the dataset of homomorphic encrypted data 106 can be denoted as R {1,1} , . . . R {N,L} , in rows and columns of the encrypted bits.
The techniques of variable relinearization in homomorphic encryption are described in the general context of evaluating the homomorphic encrypted data 106 , and homomorphic encryption algorithms 110 are applied to evaluate the homomorphic encrypted data in the dataset while the data remains encrypted. In this example, the homomorphic encryption algorithms 110 apply multiplication operations 112 on the ciphertexts 108 of the homomorphic encrypted data. The multiplication operations 112 on the ciphertexts 108 initiate the need for relinearization, and as described herein, can be implemented as variable relinearization in homomorphic encryption.
The computing device 100 implements the encryption application 114 that can include various algorithms to implement the techniques of variable relinearization in homomorphic encryption, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102 . The encryption application 114 can be stored in computer-readable storage memory (e.g., the memory 104 ), such as any suitable memory device or electronic data storage implemented in the computing device. Further, although the various algorithms are shown and described as modules of the encryption application 114 , any one or combination of the algorithms may be implemented separately or together, and may be independent of the encryption application. An overview of the encryption application 114 and the various algorithms is described following, with additional implementation details described with reference to FIG. 2 .
In aspects of variable relinearization in homomorphic encryption, the encryption application 114 can apply one or more of the various algorithms 110 to perform homomorphic operations, such as the multiplication operations 112 , on the ciphertexts 108 of the homomorphic encrypted data 106 . As noted above, generally the multiplication operations 112 that are performed by the homomorphic encryption algorithms 110 , or by other multiplication operations on the ciphertexts 108 , increase the noise component in a ciphertext. As the noise component of a ciphertext increases, computation processing becomes slow, and further, once the noise component in a ciphertext reaches a certain bound, the ciphertext can become corrupted to the point that it cannot be decrypted accurately, and the data is lost. Aspects of variable relinearization in homomorphic encryption can be implemented to relinearize the ciphertexts 108 , and doing so in a manner effective to minimize or optimize the noise increase in the ciphertexts that is attributable to the multiplication operations 112 and/or relinearizing the ciphertexts.
For example, in many encryption schemes that utilize homomorphic encryption, such as the Fan-Vercauteren (FV) scheme described herein, newly encrypted ciphertexts 108 consist of two polynomials in R q . When multiplication on ciphertexts of size M and size N is performed, the resulting ciphertext has size M+Nâ1 (e.g., two newly encrypted ciphertexts multiply to a ciphertext of size three (3)). With consecutive multiplication operations 112 , the ciphertext 108 grows in size very quickly, which makes operating on the ciphertext very slow. Additionally, noise growth gets worse as the size of the ciphertexts increases, so multiplying ciphertexts of a size five (5) for instance becomes nonsensical. Relinearization brings down the size of a ciphertext to the lower bound of two (2). Thus, relinearization controls the size of the ciphertexts, and smaller size ciphertexts incur less noise due to multiplication operations and are faster to process.
The encryption application 114 can perform a multiplication operation 112 on a ciphertext 116 in the homomorphic encrypted data 106 of the dataset, and the multiplication operation 112 contributes to increase a noise component 118 in the ciphertext. In this example, the encryption application 114 includes a variable relinearization algorithm 120 that is implemented to determine a variable relinearization amount 122 by which to relinearize the ciphertext 116 after the multiplication operation 112 . The relinearization amount 122 is determined to optimize a noise increase in the ciphertext 116 that is attributable to relinearizing the ciphertext, and the optimization can be based in part on projected subsequent multiplication operations 112 on the ciphertext 116 . The encryption application 114 can then relinearize the ciphertext 116 utilizing the determined variable relinearization amount 122 that optimizes the noise increase in the ciphertext for optimal relinearization performance.
Additionally relinearization performance can be determined across multiple executions of relinearization, taking into account the overall performance of a computation, and not necessarily just evaluating each individual relinearization. For example, a computation may be homomorphic multiplication of two-component ciphertexts in the form d 1 * c1 +d 2 * c2 + . . . +d 10 * c10 , where each term in the sum will be a three-component ciphertext. Rather than relinearizing the ten (10) individual multiplication results, computing instead the sums of the three-component ciphertexts is very fast. Once the sum has been computed, which still results in a three-component ciphertext, it can be relinearized. In this example, the computational cost goes down by nine (9) relinearizations, but the additions become slightly slower, which is irrelevant as they are very fast compared to the relinearizations.
In other aspects of variable relinearization in homomorphic encryption, the variable relinearization algorithm 120 of the encryption application 114 is implemented to estimate a noise level in the ciphertext 116 as the ciphertext noise level estimate 124 based on an initial noise component 126 in the ciphertext 116 and based on the noise increase to the noise component 118 contributed by the multiplication operation 112 . The variable relinearization algorithm 120 of the encryption application 114 can then determine the variable relinearization amount 122 by which to relinearize the ciphertext 116 based on the ciphertext noise level estimate 124 . In an implementation, the variable relinearization amount 122 can be determined to be not greater than the current noise level in the ciphertext 116 .
In an illustrative example, a newly encrypted ciphertext 108 has some noise component, such as represented by some ten (10) bit number, and may have a noise ceiling of two-hundred (200) bits. For simplicity, assume that every multiplication operation 112 adds thirty (30) bits of noise (e.g., a multiplicative increase by some factor Ë2 30 ). Accordingly, after one multiplication operation, the noise is a forty (40) bit number. A relinearization incurs an additive term, which generally can be of any size depending on the performance target. At its smallest, the noise increase could be some eight (8) bit number, which adding a number 2 8 to a number 2 40 , this noise increase is completely irrelevant (particularly given that the ceiling is 2 200 in this example). Even if the additive term is Ë2 40 , the change is nearly irrelevant compared to the two-hundred (200) bit ceiling. The new level of the noise component may be at most Ë2 41 for a mere one (1) bit increase.
However, to achieve better performance, the encryption application 114 can be implemented to relinearize by some much larger amount, so that the additive term is 2 80 , resulting in approximately 2 80 +2 40 =2 80 . Another multiplication operation 112 can be performed and the noise is then approximately one-hundred ten (110) bits. At this point, there will be no change in the noise component if the ciphertext is relinearized, and there is no change in the noise, as approximately 2 80 +2 110 â2 110 . A subsequent multiplication can be performed, followed by a relinearization using much faster evaluation keys 128 . For example, a relinearization may add one-hundred sixty (160) bits of noise, which is going to be much faster than the eighty (80) bit relinearization, and at the one-hundred sixty (160) bits, another multiplication operation 112 can be performed, which increases the noise component of the ciphertext to one-hundred ninety (190) bits. The ciphertext will still decrypt correctly, and the result is a three-component ciphertext.
A determination can then be made not to relinearize if no subsequent multiplication operations 112 are to be performed (but relinearization could be performed and it would be very fast processing because a very large amount of noise can be added at this point without change). In implementations, the size of the homomorphic encryption evaluation keys 128 do not change, which in practice is a vector of polynomials with coefficients of a certain size. If the coefficients are large, then the vector of polynomials is shorter (length two (2) is the minimum), and this is the case where a lot of noise is added but the computation is fast. On the other end, the coefficients can be very small (0 or 1), and the vector of polynomials can be very long, which adds very little noise, but results in very slow performance. In any case, the total size of the homomorphic encryption evaluation keys 128 is approximately always the same, and it is efficient to store fewer polynomials with larger coefficients.
The current noise level in the ciphertext 116 is based on the initial noise component 126 in the ciphertext and the noise increase to the noise component 118 from a multiplication operation 112 . The encryption application 114 can be implemented to estimate the noise increase of the noise component 118 based on a type of the ciphertext multiplication operation and input parameters of the multiplication operation. For example, a Table 2 is included in details below, and the table includes homomorphic operations, and an input description for each, from which noise estimates for the homomorphic operations can be determined as an associated output noise.
In an implementation, the variable relinearization algorithm 120 of the encryption application 114 can determine the variable relinearization amount 122 as a size of the homomorphic encryption evaluation keys 128 of the encryption scheme used to generate the homomorphic encrypted data 106 . The determination of the size of the homomorphic encryption evaluation keys 128 is effective to optimize the noise increase from the noise increase in the ciphertext 116 resulting from the relinearization. The technique of variable relinearization reduces the size of the ciphertexts down to (at least) two (2) polynomials, and utilizes the homomorphic encryption evaluation keys 128 . The relinearization itself increases the noise in the ciphertext 116 by an amount that depends on the size of the evaluation keys 128 . This size can be a user-selectable variable, and the smaller the evaluation keys 128 (for a larger noise increase), the faster the relinearization will be performed.
Initially, when the initial noise component 126 of the ciphertext 116 is still small, the encryption application 114 can initiate to relinearize the ciphertext 116 by large size evaluation keys 128 , which results in relatively slow processing, but adds little noise to the ciphertext 116 . When the noise level of the noise component in the ciphertext 116 increases, the encryption application 114 can initiate to relinearize by larger size evaluation keys 128 , which results in relatively faster processing, and the added noise drowns into the already large noise in the ciphertext. This provides for a better performing encryption scheme and allows more homomorphic operations to be performed on the homomorphic encrypted data 106 .
Therefore, the size of the evaluation keys 128 can be selected or chosen to be as small as possible, without making the noise growth (e.g., the noise increase of the noise component 118 ) from the relinearization too large. Since relinearization increases the noise in the ciphertexts 108 by an additive factor, if the ciphertext 116 already contains a larger or equal size noise, the additional noise will drown into the existing noise and will not cause the ciphertext 116 to degrade in quality by any noticeable amount, as described above. Therefore, in aspects of variable relinearization in homomorphic encryption, one technique can be to relinearize by variable size evaluation keys 128 , depending on what the current noise level is estimated to be in the ciphertext 116 .
FIG. 2 illustrates an example system 200 in which aspects of variable relinearization in homomorphic encryption can be implemented as described herein. The example system 200 includes the computing device 100 that is shown and described with reference to FIG. 1 . The example system also includes a cloud-based service 202 that is accessible by computing devices, to include the computing device 100 . The cloud-based service 202 includes data storage 204 that may be implemented as any suitable memory, memory device, or electronic data storage for network-based storage. The data storage 204 can store the homomorphic encrypted data 106 . The cloud-based service 202 can also implement an instance of the encryption application 114 , as shown and described with reference to FIG. 1 .
In this instance, the encryption application 114 can receive a data request 206 from the computing device 100 , such as a query of the homomorphic encrypted data 106 in the dataset. The encryption application 114 can then apply one or more of the various homomorphic encryption algorithms 110 shown and described with reference to FIG. 1 , performing the multiplication operations 112 . The encryption application 114 can also apply the described efficiencies and techniques of variable relinearization in homomorphic encryption. The encryption application 114 can process and determine the requested data 206 from the homomorphic encrypted data 106 , and the requested data can then be returned to the computing device 100 as the returned data 208 .
The cloud-based service 202 can also be implemented with server devices that are representative of one or multiple hardware server devices of the service. Further, the cloud-based service 202 can be implemented with various components, such as a processing system and memory, as well as with any number and combination of different components as further described with reference to the example device shown in FIG. 5 to implement the services, applications, servers, and other features of variable relinearization in homomorphic encryption. Other aspects of variable relinearization in homomorphic encryption as described herein can be implemented by the encryption application 114 at the cloud-base service and/or may be implemented in conjunction with the encryption application 114 that is implemented by the computing device 100 , as shown and described with reference to FIG. 1 .
The example system 200 also includes a network 210 , and any of the devices, servers, and/or services described herein can communicate via the network, such as for data communication between the computing device 100 and the cloud-based service 202 . The network 210 can be implemented to include a wired and/or a wireless network. The network can also be implemented using any type of network topology and/or communication protocol, and can be represented or otherwise implemented as a combination of two or more networks, to include IP-based networks and/or the Internet. The network may also include mobile operator networks that are managed by a mobile network operator and/or other network operators, such as a communication service provider, mobile phone provider, and/or Internet service provider.
Homomorphic Encryption
Homomorphic encryption is a powerful cryptographic technique that allows computation on encrypted data without first decrypting it. Even though anyone can operate on the encrypted data, the results of the operations remain encrypted, and no information about the underlying plaintext is leaked, except perhaps its size. In examples, a medical service provider may want to outsource the storage of encrypted medical data files for public cloud-based storage, such as at the cloud-based service 202 with the data storage 204 . Similarly, a financial service provider may want to outsource the storage of encrypted financial data files for public cloud-based storage.
In order to protect the privacy of the patients of the medical service provider, and protect the privacy of the customers of the financial service provider, the respective medical data files and the financial data files are uploaded to the cloud-based service 202 for storage in encrypted form, such as the homomorphic encrypted data 106 in a dataset. At a later date, the medical service provider or the financial service provider may want to request and/or update the encrypted data that has been uploaded to the cloud-based storage. The computing device 100 is representative of an entity accessing or initiating a request of the homomorphic encrypted data 106 that has been stored as a dataset in the data storage 204 at the cloud-based service 202 . A data request 206 or data update can be communicated from the medical service provider or the financial service provider in an encrypted form to protect the privacy of the respective patients and customers.
Generally, the techniques and algorithms of variable relinearization in homomorphic encryption as described herein are agnostic to the encryption scheme that is being used for homomorphic encryption. However for simplicity, the discussion centers on Ring-LWE (learning with error)-based cryptosystems using power-of-2 cyclotomic rings of integers. This is described in a document âOn ideal lattices and learning with errors over ringsâ by Lyubashevsky et al. (Advances in CryptologyâEUROCRYPT 2010, 29 th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-Jun. 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 1-23. Springer, 2010). In such cryptosystems, the plaintext space is typically the polynomial quotient ring Z t [x]/(x n +1), and the ciphertext space is the polynomial quotient ring Z q [x]/(x n +1), where n is a power of 2, and t«q are integers. Here Z t and Z q denote integers modulo t and q, respectively. Thus, it is customary to denote R=Z[x]/(x n +1), so that the plaintext and ciphertext spaces become R t =R/tR, and R q =R/qR, respectively. In implementations, the techniques described herein can utilize the Simple Encrypted Arithmetic Library (SEAL version of the library v2.1), which implements the Fan-Vercauteren scheme. Thus, the techniques also may apply trivially to many other encryption schemes that are used for homomorphic encryption.
As a distinction, fully homomorphic encryption refers to an encryption scheme which can evaluate any arithmetic circuit on encrypted inputs, but in practice, is extensive to implement. Rather, by restricting the multiplicative depth of the circuits to some bound L, the parameters of the encryption scheme can be set to support only circuits up to depth L, and significantly better performance is obtained with this âleveled fullyâ homomorphic encryption scheme, rather than the result of using a true fully homomorphic encryption scheme. The leveled fully homomorphic encryption scheme can be described by randomized algorithms, which include Setup, KeyGen, Encrypt, Decrypt, and Evaluate algorithms.
Given a security parameter K and a parameter LâZ + (level), the Setup(1 κ , 1 L ) outputs a set of encryption parameters parms. The KeyGen(parms) outputs a secret key sk and a public key pk, and optionally, outputs one or more evaluation keys evk. Given a message mâR t , the Encrypt(m, pk) outputs ciphertext câR q . Given the ciphertext câR q , the Decrypt(c, sk) outputs a message mâR t . For the Evaluate(C, (c1, . . . , c k ), evk): Given a circuit f of depth at most L with k input wires, and inputs c1, . . . , c k , with c i âEncrypt(m i , pk), outputs a ciphertext c such that Pr [Decrypt(c, sk)â f (m 1 , . . . , m k )]=negl(κ). Additionally, the size of the output of Evaluate is not more than a polynomial in κ independent of f (compactness), and independent of L. The leveled fully homomorphic encryption scheme is secure if its IND-CPA secure.
With reference to encoding, the techniques described herein restrict to encryption schemes for homomorphic encryption where the plaintext space is the polynomial quotient ring R t . Thus, when integers are to be encrypted, and integer arithmetic performed on them in encrypted form, an encoding scheme is used to convert integers into elements of R t . There are many ways to do this, however the simplest and easiest method can be utilized for variable relinearization in homomorphic encryption. Given an integer mâZ, it is encoded as the constant polynomial mâR t , allowing for only encoding integers between zero (0) and tâ1, which provides a strict lower bound on the size of t that can be used. Because Z t is a subring of R t , as long as the coefficients of the underlying plaintext polynomials that are encountered during the homomorphic evaluation never get reduced modulo t, the homomorphic encryption scheme can be used to perform integer arithmetic. This can place a strong lower bound on the size of t, which subsequently necessitates the use of larger n and q, meaning that t should be chosen to be as small as possible.
Relinearization Overview
As described herein, relinearization pertains not only to the FV scheme, but also to the particular implementation of SEAL as described below. With reference to relinearization, to obtain and maintain cryptographic properties (e.g., compactness and circuit privacy) of the homomorphic encrypted data 106 , a relinearization operation can be performed by the encryption application 114 after every homomorphic multiplication operation 112 . The result of multiplying two ciphertexts of sizes M and N results in a ciphertext of size M+Nâ1. Relinearization can then be initiated to reduce the size down from three (3) to two (2) after each multiplication operation, preventing the ciphertext size from leaking information about the evaluated arithmetic circuit.
However, the encryption application 114 does not perform relinearization by default after
CLAIMS
Claims ( 19 )
The invention claimed is:
1. A computing device implemented for variable relinearization in homomorphic encryption, the computing device comprising:
a memory configured to store homomorphic encrypted data as a dataset;
a processor system configured to execute an encryption application that is implemented to:
receive a request containing a query of the homomorphic encrypted data of the dataset from another computing device via a communications network; and
evaluate the homomorphic encrypted data of the dataset based on the query to determine requested data by which the processor system:
performs a multiplication operation on a ciphertext in the homomorphic encrypted data of the dataset responsive to the query, the multiplication operation contributing to increase a noise component in the ciphertext;
determines one or more projected subsequent multiplication operations on the ciphertext;
determines a relinearization amount that sets a noise increase in the ciphertext to a size that satisfies a noise increase performance target based at least in part on the one or more projected subsequent multiplication operations on the ciphertext, wherein the relinearization amount is determined based at least in part on a number of the one or more projected subsequent multiplication operations;
relinearizes the ciphertext utilizing the determined relinearization amount; and
returns the requested data to the other computing device via the communications network.
2. The computing device as recited in claim 1 , wherein the encryption application is implemented to set the noise increase attributable to relinearizing the ciphertext to the size that satisfies the noise increase performance target.
3. The computing device as recited in claim 1 , wherein the encryption application is implemented to:
estimate a noise level in the ciphertext, the noise level estimated based on an initial noise component in the ciphertext and the noise increase to the noise component; and
determine the relinearization amount based on the estimated noise level in the ciphertext.
4. The computing device as recited in claim 2 , wherein the encryption application is implemented to estimate the noise increase of the noise component based on a type of the ciphertext multiplication operation and input parameters of the multiplication operation.
5. The computing device as recited in claim 1 , wherein the encryption application is implemented to determine the relinearization amount not greater than a current noise level in the ciphertext.
6. The computing device as recited in claim 4 , wherein the current noise level in the ciphertext is based on an initial noise component in the ciphertext and the noise increase to the noise component from the multiplication operation.
7. The computing device as recited in claim 1 , wherein the encryption application is implemented to determine the relinearization amount as a size of evaluation keys of an encryption scheme used to generate the homomorphic encrypted data, the size of the evaluation keys determined effective to optimize the noise increase in the ciphertext resulting from the relinearization.
8. A method for variable relinearization in homomorphic encryption, the method comprising:
storing homomorphic encrypted data as a dataset in a memory device; and
at a processor system:
receiving a request containing a query of the homomorphic encrypted data of the dataset from another computing device via a communications network; and
evaluating the homomorphic encrypted data of the dataset based on the query to determine requested data at least in part by:
performing a multiplication operation on a ciphertext in the homomorphic encrypted data of the dataset responsive to the query, the multiplication operation contributing to increase a noise component in the ciphertext;
determining one or more projected subsequent multiplication operations on the ciphertext;
determining a relinearization amount that sets a noise increase in the ciphertext to a size that satisfies a noise increase performance target based at least in part on the one or more projected subsequent multiplication operations on the ciphertext, wherein the relinearization amount is determined based at least in part on a number of the one or more projected subsequent multiplication operations;
relinearizing the ciphertext utilizing the determined relinearization amount; and
returning the requested data to the other computing device via the communications network.
9. The method as recited in claim 8 , further comprising:
setting the noise increase attributable to the relinearizing the ciphertext to the size that satisfies the noise increase performance target.
10. The method as recited in claim 8 , further comprising:
estimating a noise level in the ciphertext, the noise level estimated based on an initial noise component in the ciphertext and the noise increase to the noise component; and
said determining the relinearization amount based on the estimated noise level in the ciphertext.
11. The method as recited in claim 10 , further comprising:
estimating the noise increase of the noise component based on a type of the ciphertext multiplication operation and input parameters of the multiplication operation.
12. The method as recited in claim 8 , wherein the relinearization amount is not greater than a current noise level in the ciphertext.
13. The method as recited in claim 12 , wherein the current noise level in the ciphertext is based on an initial noise component in the ciphertext and the noise increase to the noise component from the multiplication operation.
14. The method as recited in claim 8 , wherein the relinearization amount is determined to be a size of evaluation keys of an encryption scheme used to generate the homomorphic encrypted data.
15. The method as recited in claim 14 , further comprising:
determining the size of the evaluation keys effective to set the noise increase in the ciphertext resulting from the relinearization to the size that satisfies the noise increase performance target.
16. A method for variable relinearization in homomorphic encryption, the method comprising:
storing homomorphic encrypted data as a dataset in a memory device; and
at a processor system:
receiving a request containing a query of the homomorphic encrypted data of the dataset from another computing device via a communications network; and
evaluating the homomorphic encrypted data of the dataset based on the query to determine requested data at least in part by:
performing multiplication operations on a ciphertext in the homomorphic encrypted data of the dataset responsive to the query, the multiplication operations each contributing to increase a noise component in the ciphertext;
estimating a noise level in the ciphertext after each of the multiplication operations, the noise level being estimated based on an initial noise component in the ciphertext and the noise increase to the noise component;
determining a variable relinearization amount that sets a noise increase in the ciphertext to a size that satisfies a noise increase performance target based at least in part on one or more subsequent multiplication operations performed on the ciphertext, wherein the relinearization amount is determined based at least in part on a number of the one or more projected subsequent multiplication operations;
relinearizing the ciphertext utilizing the determined variable relinearization amount; and
returning the requested data to the other computing device via the communications network.
17. The method as recited in claim 16 , further comprising:
setting the noise increase attributable to the relinearizing the ciphertext after one or more of the multiplication operations to the size that satisfies the noise increase performance target.
18. The method as recited in claim 16 , wherein the variable relinearization amount is not greater than a current noise level in the ciphertext.
19. The method as recited in claim 16 , wherein the variable relinearization amount is determined to be a size of evaluation keys of an encryption scheme used to generate the homomorphic encrypted data.
US15/633,284
2017-06-26
2017-06-26
Variable relinearization in homomorphic encryption
Active
2037-09-09
US10541805B2
( en )
Priority Applications (3)
Application Number
Priority Date
Filing Date
Title
US15/633,284
US10541805B2
( en )
2017-06-26
2017-06-26
Variable relinearization in homomorphic encryption
PCT/US2018/039571
WO2019005845A1
( en )
2017-06-26
2018-06-26
Variable relinearization in homomorphic encryption
EP18743189.5A
EP3646523A1
( en )
2017-06-26
2018-06-26
Variable relinearization in homomorphic encryption
Applications Claiming Priority (1)
Application Number
Priority Date
Filing Date
Title
US15/633,284
US10541805B2
( en )
2017-06-26
2017-06-26
Variable relinearization in homomorphic encryption
Publications (2)
Publication Number
Publication Date
US20180375640A1
US20180375640A1 ( en )
2018-12-27
US10541805B2
true
US10541805B2 ( en )
2020-01-21
Family
ID=62976193
Family Applications (1)
Application Number
Title
Priority Date
Filing Date
US15/633,284
Active
2037-09-09
US10541805B2
( en )
2017-06-26
2017-06-26
Variable relinearization in homomorphic encryption
Country Status (3)
Country
Link
US
( 1 )
US10541805B2
( en )
EP
( 1 )
EP3646523A1
( en )
WO
( 1 )
WO2019005845A1
( en )
Cited By (14)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US11038683B1
( en )
*
2020-01-24
2021-06-15
Via Science, Inc.
Secure data processing
US20210376997A1
( en )
*
2020-05-27
2021-12-02
Samsung Electronics Co., Ltd.
Artificial intelligence calculation semiconductor device and storage device comprising the same
US11343070B2
( en )
*
2018-05-23
2022-05-24
Hrishikesh DEWAN
System and method for performing a fully homomorphic encryption on a plain text
US11483128B2
( en )
2020-05-29
2022-10-25
Samsung Electronics Co., Ltd.
Homomorphic encryption device and ciphertext arithmetic method thereof
US20230035988A1
( en )
*
2021-07-27
2023-02-02
Samsung Electronics Co., Ltd.
Storage device, storage system operating method, and computing system
US20230188320A1
( en )
*
2021-12-09
2023-06-15
Electronics And Telecommunications Research Institute
Computing apparatus and method of integrating different homomorphic operations in homomorphic encryption
US20230216656A1
( en )
*
2021-12-31
2023-07-06
Huawei Technologies Co., Ltd.
Low-latency pipeline and method for use of a low latency pipline in homomorphic encryption
US11764940B2
( en )
2019-01-10
2023-09-19
Duality Technologies, Inc.
Secure search of secret data in a semi-trusted environment using homomorphic encryption
US20240160423A1
( en )
*
2022-11-11
2024-05-16
Electronics And Telecommunications Research Institute
Program conversion apparatus and method
US20240313946A1
( en )
*
2023-03-16
2024-09-19
Crypto Lab Inc.
Electronic apparatus for bootstrap processing homomorphic encrypted messages and methods thereof
US12380227B2
( en )
*
2021-12-01
2025-08-05
Samsung Electronics Co., Ltd.
Encryption computing system and encryption method
US12587360B1
( en )
2025-08-08
2026-03-24
Chain Reaction, Ltd.
Multi-chip accelerator architecture for fully homomorphic encryption inference
US20260095300A1
( en )
*
2024-10-01
2026-04-02
International Business Machines Corporation
Compression and decompression of sparse vectors under homomorphic encryption
WO2026073863A1
( en )
*
2024-10-03
2026-04-09
Katholieke Universiteit Leuven
Method for homomorphic encryption with low noise growth
Families Citing this family (23)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US10812252B2
( en )
2017-01-09
2020-10-20
Microsoft Technology Licensing, Llc
String matching in encrypted data
US11196539B2
( en )
2017-06-22
2021-12-07
Microsoft Technology Licensing, Llc
Multiplication operations on homomorphic encrypted data
US10749665B2
( en )
2017-06-29
2020-08-18
Microsoft Technology Licensing, Llc
High-precision rational number arithmetic in homomorphic encryption
US10797856B2
( en )
*
2018-04-18
2020-10-06
Fujitsu Limited
Outsourcing processing operations with homomorphic encryption
US11032061B2
( en )
*
2018-04-27
2021-06-08
Microsoft Technology Licensing, Llc
Enabling constant plaintext space in bootstrapping in fully homomorphic encryption
CN109962778A
( en )
*
2019-03-21
2019-07-02
西åå·¥ä¸å¤§å¦
Integer-Based Multiparty Homomorphic Encryption
US11431470B2
( en )
*
2019-08-19
2022-08-30
The Board Of Regents Of The University Of Texas System
Performing computations on sensitive data while guaranteeing privacy
KR102925508B1
( en )
2019-12-23
2026-02-11
ì¼ì±ì ì주ìíì¬
Non-transitory computer-readable medium storing program code, decryption device, and communication system including encryption device and decryption device
US12099997B1
( en )
2020-01-31
2024-09-24
Steven Mark Hoffberg
Tokenized fungible liabilities
KR20210135075A
( en )
*
2020-05-04
2021-11-12
ì¼ì±ì ì주ìíì¬
Device of performing homomorphic encryption and decryption, system including the same, method of performing homomorphic encryption and decryption
US11962679B2
( en )
*
2020-06-19
2024-04-16
Duality Technologies, Inc.
Secure distributed key generation for multiparty homomorphic encryption
EP3993308A1
( en )
*
2020-10-29
2022-05-04
Zama SAS
Fully homomorphic cryptography with improved data item representation
US12250291B2
( en )
*
2020-11-10
2025-03-11
Evernorth Strategic Development, Inc.
Encrypted database systems including homomorphic encryption
US11522672B2
( en )
*
2021-02-01
2022-12-06
Seagate Technology Llc
Fully homomorphic encryption from error canceling set systems
CN113055153B
( en )
*
2021-03-10
2022-12-23
ä¸å½äººæ°å¤§å¦
Data encryption method, system and medium based on fully homomorphic encryption algorithm
KR102430495B1
( en )
*
2021-08-04
2022-08-09
ì¼ì±ì ì주ìíì¬
Storage device, host device and data tranfering method thereof
US12381710B2
( en )
*
2021-11-04
2025-08-05
Samsung Electronics Co., Ltd.
Crypto processor and electronic device including the same
US11764944B2
( en )
*
2021-12-30
2023-09-19
Huawei Technologies Co., Ltd.
Field-programmable gate array (FPGA) clusters and methods of using an FPGA cluster for homomorphic encryption acceleration
EP4228198B1
( en )
*
2022-02-10
2025-03-05
Seoul National University R & DB Foundation
Electronic device for delegating generation of homomorphic rotation key to server and method of operating the same
EP4280529B1
( en )
*
2022-05-19
2025-09-24
Zama SAS
Optimizing encrypted computation parameters
KR102830741B1
( en )
*
2022-11-30
2025-07-08
ìì¸ëíêµì°ííë ¥ë¨
Elctronic apparatus and method for verifying encrypted data
US20240340158A1
( en )
*
2023-04-10
2024-10-10
Samsung Electronics Co., Ltd.
Apparatus and method with homomorphic encryption operation
CN119834955B
( en )
*
2025-02-12
2026-04-07
ä¸å½ç§å¦é¢ä¿¡æ¯å·¥ç¨ç 究æ
Finite-order homomorphic encryption method and system based on multiple secret keys NTRU
Citations (42)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20020027986A1
( en )
1999-12-20
2002-03-07
Tonnes Brekne
Encryption of programs represented as polynomial mappings and their computations
US20040078414A1
( en )
2000-06-01
2004-04-22
Geiringer Felix Egmont
Decryption of cipher polynomials
US20070116283A1
( en )
*
2003-11-03
2007-05-24
Koninklijke Philips Electronics N.V.
Method and device for efficient multiparty multiplication
US20080294909A1
( en )
2005-03-01
2008-11-27
The Regents Of The University Of California
Method for Private Keyword Search on Streaming Data
US20090327748A1
( en )
2004-01-05
2009-12-31
International Business Machines Corp.
System and method for fast querying of encrypted databases
US20100020965A1
( en )
2007-12-28
2010-01-28
Shay Gueron
Method for speeding up the computations for characteristic 2 elliptic curve cryptographic systems
US20110110525A1
( en )
*
2009-11-10
2011-05-12
International Business Machines Corporation
Fully homomorphic encryption method based on a bootstrappable encryption scheme, computer program and apparatus
US20120039473A1
( en )
*
2010-08-16
2012-02-16
International Business Machines Corporation
Efficient Implementation Of Fully Homomorphic Encryption
US20130014270A1
( en )
*
2011-07-08
2013-01-10
Sy Bon K
Method of comparing private data without revealing the data
US20130024653A1
( en )
2011-07-18
2013-01-24
Gove Darryl J
Acceleration of string comparisons using vector instructions
US8429421B2
( en )
2010-12-17
2013-04-23
Microsoft Corporation
Server-side encrypted pattern matching
US20130170640A1
( en )
*
2011-04-29
2013-07-04
International Business Machines Corporation
Fully Homomorphic Encryption
US8515058B1
( en )
2009-11-10
2013-08-20
The Board Of Trustees Of The Leland Stanford Junior University
Bootstrappable homomorphic encryption method, computer program and apparatus
US20130216044A1
( en )
*
2012-02-17
2013-08-22
International Business Machines Corporation
Homomorphic evaluation including key switching, modulus switching, and dynamic noise management
US20130329883A1
( en )
*
2012-06-12
2013-12-12
Kryptnostic
Method for fully homomorphic encryption using multivariate cryptography
US20140177828A1
( en )
*
2012-12-21
2014-06-26
Microsoft Corporation
Managed secure computations on encrypted data
US20140215222A1
( en )
*
2011-08-29
2014-07-31
Sony Corporation
Information processing apparatus, information processing method, and program
US20140233727A1
( en )
2012-11-16
2014-08-21
Raytheon Bbn Technologies Corp.
Method for secure substring search
US20140325230A1
( en )
*
2011-07-08
2014-10-30
Research Foundation Of The City University Of New York
Method of comparing private data without revealing the data
US20150033018A1
( en )
2012-01-19
2015-01-29
International Business Machines Corporation
System for determining whether character string has been accepted by automaton
US20150039912A1
( en )
2013-08-01
2015-02-05
Visa International Service Association
Homomorphic Database Operations Apparatuses, Methods and Systems
US20150046708A1
( en )
2013-08-07
2015-02-12
Fujitsu Limited
Information processing technique for secure pattern matching
US20150046450A1
( en )
2013-08-08
2015-02-12
Hitachi Solutions, Ltd.
Searchable code processing system and method
EP2924911A1
( en )
2014-03-24
2015-09-30
Fujitsu Limited
Secure Pattern Matching using Somewhat Homomorphic Encryption
US20150280914A1
( en )
2014-03-25
2015-10-01
Fujitsu Limited
Ciphertext processing device, ciphertext processing method, computer-readable recording medium, and information processing device
US20150288665A1
( en )
2014-04-04
2015-10-08
University Of Ottawa
Secure Linkage Of Databases
US20150295716A1
( en )
2012-06-22
2015-10-15
Commonwealth Scientific And Industrial Research Organisation
Homomorphic encryption for database querying
US20150312031A1
( en )
*
2014-04-23
2015-10-29
Samsung Electronics Co., Ltd.
Encryption apparatus, method for encryption and computer-readable recording medium
US9202079B2
( en )
2012-10-25
2015-12-01
Verisign, Inc.
Privacy preserving data querying
US20150365229A1
( en )
*
2013-02-01
2015-12-17
Morpho
Method of xor homomorphic encryption and secure calculation of a hamming distance
US20160105402A1
( en )
*
2014-07-22
2016-04-14
Harsh Kupwade-Patil
Homomorphic encryption in a healthcare network environment, system and methods
US20160119119A1
( en )
*
2014-05-15
2016-04-28
Xeror Corporation
Compact fuzzy private matching using a fully-homomorphic encryption scheme
US9436835B1
( en )
*
2012-01-05
2016-09-06
Gokay Saldamli
Homomorphic encryption in computing systems and environments
US20170134157A1
( en )
2015-11-05
2017-05-11
Microsoft Technology Licensing, Llc
Homomorphic Encryption with Optimized Encoding
US20170134158A1
( en )
*
2015-11-09
2017-05-11
CertSIGN S.A.
Fully Homomorphic Encryption from Monoid Algebras
US20170293913A1
( en )
2016-04-12
2017-10-12
The Governing Council Of The University Of Toronto
System and methods for validating and performing operations on homomorphically encrypted data
US20180198601A1
( en )
2017-01-09
2018-07-12
Microsoft Technology Licensing, Llc
String Matching in Encrypted Data
US10075288B1
( en )
2014-02-28
2018-09-11
The Governing Council Of The University Of Toronto
Systems, devices, and processes for homomorphic encryption
US20180278410A1
( en )
2015-10-09
2018-09-27
Mitsubishi Electric Corporation
Secret search system, management device, secret search method and computer readable medium
US10116437B1
( en )
*
2015-12-14
2018-10-30
Ingram Micro, Inc.
Method for protecting data used in cloud computing with homomorphic encryption
US20180375639A1
( en )
2017-06-22
2018-12-27
Microsoft Technology Licensing, Llc
Multiplication Operations on Homomorphic Encrypted Data
US20190007197A1
( en )
2017-06-29
2019-01-03
Microsoft Technology Licensing, Llc
High-Precision Rational Number Arithmetic in Homomorphic Encryption
2017
2017-06-26
US
US15/633,284
patent/US10541805B2/en
active
Active
2018
2018-06-26
EP
EP18743189.5A
patent/EP3646523A1/en
not_active
Withdrawn
2018-06-26
WO
PCT/US2018/039571
patent/WO2019005845A1/en
not_active
Ceased
Patent Citations (46)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20020027986A1
( en )
1999-12-20
2002-03-07
Tonnes Brekne
Encryption of programs represented as polynomial mappings and their computations
US20040078414A1
( en )
2000-06-01
2004-04-22
Geiringer Felix Egmont
Decryption of cipher polynomials
US20070116283A1
( en )
*
2003-11-03
2007-05-24
Koninklijke Philips Electronics N.V.
Method and device for efficient multiparty multiplication
US20090327748A1
( en )
2004-01-05
2009-12-31
International Business Machines Corp.
System and method for fast querying of encrypted databases
US20080294909A1
( en )
2005-03-01
2008-11-27
The Regents Of The University Of California
Method for Private Keyword Search on Streaming Data
US20100020965A1
( en )
2007-12-28
2010-01-28
Shay Gueron
Method for speeding up the computations for characteristic 2 elliptic curve cryptographic systems
US8515058B1
( en )
2009-11-10
2013-08-20
The Board Of Trustees Of The Leland Stanford Junior University
Bootstrappable homomorphic encryption method, computer program and apparatus
US20110110525A1
( en )
*
2009-11-10
2011-05-12
International Business Machines Corporation
Fully homomorphic encryption method based on a bootstrappable encryption scheme, computer program and apparatus
US20120039463A1
( en )
2010-08-16
2012-02-16
International Business Machines Corporation
Fast Evaluation Of Many Polynomials With Small Coefficients On The Same Point
US20120039473A1
( en )
*
2010-08-16
2012-02-16
International Business Machines Corporation
Efficient Implementation Of Fully Homomorphic Encryption
US8903083B2
( en )
2010-08-16
2014-12-02
International Business Machines Corporation
Fast evaluation of many polynomials with small coefficients on the same point
US8429421B2
( en )
2010-12-17
2013-04-23
Microsoft Corporation
Server-side encrypted pattern matching
US20130170640A1
( en )
*
2011-04-29
2013-07-04
International Business Machines Corporation
Fully Homomorphic Encryption
US20150358153A1
( en )
*
2011-04-29
2015-12-10
International Business Machines Corporation
Fully Homomorphic Encryption
US20130014270A1
( en )
*
2011-07-08
2013-01-10
Sy Bon K
Method of comparing private data without revealing the data
US20140325230A1
( en )
*
2011-07-08
2014-10-30
Research Foundation Of The City University Of New York
Method of comparing private data without revealing the data
US20130024653A1
( en )
2011-07-18
2013-01-24
Gove Darryl J
Acceleration of string comparisons using vector instructions
US20140215222A1
( en )
*
2011-08-29
2014-07-31
Sony Corporation
Information processing apparatus, information processing method, and program
US9436835B1
( en )
*
2012-01-05
2016-09-06
Gokay Saldamli
Homomorphic encryption in computing systems and environments
US20150033018A1
( en )
2012-01-19
2015-01-29
International Business Machines Corporation
System for determining whether character string has been accepted by automaton
US20130216044A1
( en )
*
2012-02-17
2013-08-22
International Business Machines Corporation
Homomorphic evaluation including key switching, modulus switching, and dynamic noise management
US20130329883A1
( en )
*
2012-06-12
2013-12-12
Kryptnostic
Method for fully homomorphic encryption using multivariate cryptography
US20150295716A1
( en )
2012-06-22
2015-10-15
Commonwealth Scientific And Industrial Research Organisation
Homomorphic encryption for database querying
US9202079B2
( en )
2012-10-25
2015-12-01
Verisign, Inc.
Privacy preserving data querying
US20140233727A1
( en )
2012-11-16
2014-08-21
Raytheon Bbn Technologies Corp.
Method for secure substring search
US20140177828A1
( en )
*
2012-12-21
2014-06-26
Microsoft Corporation
Managed secure computations on encrypted data
US20160191233A1
( en )
*
2012-12-21
2016-06-30
Microsoft Technology Licensing, Llc
Managed secure computations on encrypted data
US20150365229A1
( en )
*
2013-02-01
2015-12-17
Morpho
Method of xor homomorphic encryption and secure calculation of a hamming distance
US20150039912A1
( en )
2013-08-01
2015-02-05
Visa International Service Association
Homomorphic Database Operations Apparatuses, Methods and Systems
US20150046708A1
( en )
2013-08-07
2015-02-12
Fujitsu Limited
Information processing technique for secure pattern matching
US20150046450A1
( en )
2013-08-08
2015-02-12
Hitachi Solutions, Ltd.
Searchable code processing system and method
US10075288B1
( en )
2014-02-28
2018-09-11
The Governing Council Of The University Of Toronto
Systems, devices, and processes for homomorphic encryption
EP2924911A1
( en )
2014-03-24
2015-09-30
Fujitsu Limited
Secure Pattern Matching using Somewhat Homomorphic Encryption
US20150280914A1
( en )
2014-03-25
2015-10-01
Fujitsu Limited
Ciphertext processing device, ciphertext processing method, computer-readable recording medium, and information processing device
US20150288665A1
( en )
2014-04-04
2015-10-08
University Of Ottawa
Secure Linkage Of Databases
US20150312031A1