ABSTRACT
Abstract
In aspects of high-precision rational number arithmetic in homomorphic encryption, a computing device stores homomorphic encrypted data as a dataset, and implements an encryption application that can encode integers into plaintext polynomials, where the integers are representative of initial data received for encryption. The encryption application can encrypt the plaintext polynomials into ciphertexts of the homomorphic encrypted data, and perform homomorphic operations as rational number arithmetic on the ciphertexts, generating updated ciphertexts while the homomorphic encrypted data remains encrypted. The encryption application can then decrypt the updated ciphertexts to modified plaintext polynomials that can be resolved back to the plaintext polynomials effective to recover the integers that represent the initial data. The encryption application can also decode the modified plaintext polynomials back to the integers effective to recover the initial data in an unencrypted form.
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 encrypted 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 high-precision rational number arithmetic 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.
High-precision rational number arithmetic in homomorphic encryption is described. In aspects, a computing device stores homomorphic encrypted data as a dataset, and implements an encryption application that can encode integers into plaintext polynomials, where the integers are representative of initial data received for encryption. The encryption application can also encrypt the plaintext polynomials into ciphertexts of the homomorphic encrypted data. In aspects of the encryption, the encryption application encodes the integers into the plaintext polynomials and encrypts the plaintext polynomials into the ciphertexts as a combined process to generate the ciphertexts of the homomorphic encrypted data.
The encryption application can perform homomorphic operations as rational number arithmetic on the ciphertexts, such as multiplication operations, generating updated ciphertexts while the homomorphic encrypted data remains encrypted. The encryption application can then decrypt the updated ciphertexts to modified plaintext polynomials that can be resolved back to the plaintext polynomials effective to recover the integers that represent the initial data. The encryption application can also decode the modified plaintext polynomials back to the integers effective to recover the initial data in an unencrypted form. In aspects of the decryption, the encryption application decrypts the updated ciphertexts to the modified plaintext polynomials and decodes the modified plaintext polynomials as a combined process to recover the initial data in the unencrypted form.
In other aspects of high-precision rational number arithmetic in homomorphic encryption, the encryption application is implemented to encode the integers as the plaintext polynomials and encrypt the plaintext polynomials into the ciphertexts effective to allow homomorphic evaluation of large ciphertext polynomials on rational numbers. The encryption application is implemented to maximize a multiplicative depth of a homomorphic computation performed on the encrypted rational numbers. The homomorphic encrypted data is encrypted based on a Fan-Vercauteren (FV) homomorphic encryption scheme with the plaintext polynomials defined as
/(b n +1)
in an FVb encryption scheme, including having replaced coefficients reduced integer modulo t of the plaintext polynomials
t [x]/(x n +1) in the FV plaintext space with (xâb).
The polynomials of the ciphertexts of the homomorphic encrypted data can be encrypted in log base two (log 2 ) with coefficients of the encrypted polynomials being less than or equal to one. The encryption application replaces the t modulus of the plaintext polynomials
t [x]/(x n +1) in the FV plaintext space with (xâb) effective to minimize t and allow homomorphic evaluation of large ciphertext polynomials on encrypted rational numbers. The encryption application is also implemented to perform multiplication operations on the ciphertexts as the homomorphic operations, where the ciphertexts of the homomorphic encrypted data are susceptible to a noise increase contributed by the multiplication operations on the ciphertexts. The encryption application can then optimize the noise increase in the ciphertexts contributed by the multiplication operations, effective to maximize a multiplicative depth of the homomorphic operations performed on the encrypted rational numbers. Replacing the t modulus of the plaintext polynomials with (xâb) allows for the optimization of the noise increase in the ciphertexts utilizing a large b value.
BRIEF DESCRIPTION OF THE DRAWINGS
Aspects of high-precision rational number arithmetic 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 high-precision rational number arithmetic in homomorphic encryption can be implemented as described herein.
FIG. 2 illustrates an example system in which aspects of high-precision rational number arithmetic in homomorphic encryption can be implemented as described herein.
FIG. 3 illustrates an example method of high-precision rational number arithmetic in homomorphic encryption in accordance with techniques described herein.
FIG. 4 illustrates an example method of high-precision rational number arithmetic in homomorphic encryption in accordance with techniques described herein.
FIG. 5 illustrates an example system with an example device that can implement high-precision rational number arithmetic in homomorphic encryption as described herein.
DETAILED DESCRIPTION
Aspects of high-precision rational number arithmetic in homomorphic encryption are described, such as to implement techniques for homomorphic operations, including multiplication operations and rational number arithmetic on homomorphic encrypted data. 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. The techniques implement a variant of the Fan Vercauteren (FV) homomorphic encryption scheme, described herein as the FVb encryption scheme, which provides that significantly more efficient homomorphic operations, including rational number arithmetic, can be performed on encrypted rational numbers, which include input integers, of homomorphic encrypted data than allowable by the FV encryption scheme. Rational numbers can be encoded as elements in plaintext space, enabling homomorphic evaluation of deep circuits with high-precision rational number inputs. The FVb encryption scheme described herein allows an implemented encryption application to evaluate homomorphically very high polynomials on encrypted rational numbers.
The techniques for high-precision rational number arithmetic in homomorphic encryption can be implemented as optimizations to improve processing speed, such as for decrypting homomorphic encrypted data. The described techniques are implemented to perform homomorphic computations in
[x] (integer coefficient polynomials) rather than in
[x]/(x n +1). A decryption result is an integer modulo (B n +1) where B is some small number. The modulo operation finds the remainder after division of one number by another. For example, given two positive numbers a and n, a modulo n is the remainder of the Euclidean division of a by n. When the computation is performed over
[x], this number B is already reduced modulo (B n +1), and a small integer result is obtained. This provides for faster homomorphic operations, including rational number arithmetic, on homomorphic encrypted data, without needing to perform processing intensive reduction modulo the large number (B n +1).
While features and concepts of high-precision rational number arithmetic in homomorphic encryption can be implemented in any number of different devices, systems, networks, environments, and/or configurations, aspects of high-precision rational number arithmetic 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 high-precision rational number arithmetic 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 encrypted bit strings of some length in rows and columns, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time. Homomorphic encryption is a powerful cryptographic technique that allows computation on the encrypted data 106 without first decrypting the encrypted data. Even though homomorphic operations can be performed on the encrypted data, the results of the operations remain encrypted, and no information about the underlying plaintext is accessible.
The computing device 100 implements an encryption application 110 that can include various algorithms to implement the tech
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 encrypted 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 high-precision rational number arithmetic 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.
High-precision rational number arithmetic in homomorphic encryption is described. In aspects, a computing device stores homomorphic encrypted data as a dataset, and implements an encryption application that can encode integers into plaintext polynomials, where the integers are representative of initial data received for encryption. The encryption application can also encrypt the plaintext polynomials into ciphertexts of the homomorphic encrypted data. In aspects of the encryption, the encryption application encodes the integers into the plaintext polynomials and encrypts the plaintext polynomials into the ciphertexts as a combined process to generate the ciphertexts of the homomorphic encrypted data.
The encryption application can perform homomorphic operations as rational number arithmetic on the ciphertexts, such as multiplication operations, generating updated ciphertexts while the homomorphic encrypted data remains encrypted. The encryption application can then decrypt the updated ciphertexts to modified plaintext polynomials that can be resolved back to the plaintext polynomials effective to recover the integers that represent the initial data. The encryption application can also decode the modified plaintext polynomials back to the integers effective to recover the initial data in an unencrypted form. In aspects of the decryption, the encryption application decrypts the updated ciphertexts to the modified plaintext polynomials and decodes the modified plaintext polynomials as a combined process to recover the initial data in the unencrypted form.
In other aspects of high-precision rational number arithmetic in homomorphic encryption, the encryption application is implemented to encode the integers as the plaintext polynomials and encrypt the plaintext polynomials into the ciphertexts effective to allow homomorphic evaluation of large ciphertext polynomials on rational numbers. The encryption application is implemented to maximize a multiplicative depth of a homomorphic computation performed on the encrypted rational numbers. The homomorphic encrypted data is encrypted based on a Fan-Vercauteren (FV) homomorphic encryption scheme with the plaintext polynomials defined as
/(b n +1)
in an FVb encryption scheme, including having replaced coefficients reduced integer modulo t of the plaintext polynomials
t [x]/(x n +1) in the FV plaintext space with (xâb).
The polynomials of the ciphertexts of the homomorphic encrypted data can be encrypted in log base two (log 2 ) with coefficients of the encrypted polynomials being less than or equal to one. The encryption application replaces the t modulus of the plaintext polynomials
t [x]/(x n +1) in the FV plaintext space with (xâb) effective to minimize t and allow homomorphic evaluation of large ciphertext polynomials on encrypted rational numbers. The encryption application is also implemented to perform multiplication operations on the ciphertexts as the homomorphic operations, where the ciphertexts of the homomorphic encrypted data are susceptible to a noise increase contributed by the multiplication operations on the ciphertexts. The encryption application can then optimize the noise increase in the ciphertexts contributed by the multiplication operations, effective to maximize a multiplicative depth of the homomorphic operations performed on the encrypted rational numbers. Replacing the t modulus of the plaintext polynomials with (xâb) allows for the optimization of the noise increase in the ciphertexts utilizing a large b value.
BRIEF DESCRIPTION OF THE DRAWINGS
Aspects of high-precision rational number arithmetic 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 high-precision rational number arithmetic in homomorphic encryption can be implemented as described herein.
FIG. 2 illustrates an example system in which aspects of high-precision rational number arithmetic in homomorphic encryption can be implemented as described herein.
FIG. 3 illustrates an example method of high-precision rational number arithmetic in homomorphic encryption in accordance with techniques described herein.
FIG. 4 illustrates an example method of high-precision rational number arithmetic in homomorphic encryption in accordance with techniques described herein.
FIG. 5 illustrates an example system with an example device that can implement high-precision rational number arithmetic in homomorphic encryption as described herein.
DETAILED DESCRIPTION
Aspects of high-precision rational number arithmetic in homomorphic encryption are described, such as to implement techniques for homomorphic operations, including multiplication operations and rational number arithmetic on homomorphic encrypted data. 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. The techniques implement a variant of the Fan Vercauteren (FV) homomorphic encryption scheme, described herein as the FVb encryption scheme, which provides that significantly more efficient homomorphic operations, including rational number arithmetic, can be performed on encrypted rational numbers, which include input integers, of homomorphic encrypted data than allowable by the FV encryption scheme. Rational numbers can be encoded as elements in plaintext space, enabling homomorphic evaluation of deep circuits with high-precision rational number inputs. The FVb encryption scheme described herein allows an implemented encryption application to evaluate homomorphically very high polynomials on encrypted rational numbers.
The techniques for high-precision rational number arithmetic in homomorphic encryption can be implemented as optimizations to improve processing speed, such as for decrypting homomorphic encrypted data. The described techniques are implemented to perform homomorphic computations in
[x] (integer coefficient polynomials) rather than in
[x]/(x n +1). A decryption result is an integer modulo (B n +1) where B is some small number. The modulo operation finds the remainder after division of one number by another. For example, given two positive numbers a and n, a modulo n is the remainder of the Euclidean division of a by n. When the computation is performed over
[x], this number B is already reduced modulo (B n +1), and a small integer result is obtained. This provides for faster homomorphic operations, including rational number arithmetic, on homomorphic encrypted data, without needing to perform processing intensive reduction modulo the large number (B n +1).
While features and concepts of high-precision rational number arithmetic in homomorphic encryption can be implemented in any number of different devices, systems, networks, environments, and/or configurations, aspects of high-precision rational number arithmetic 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 high-precision rational number arithmetic 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 encrypted bit strings of some length in rows and columns, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time. Homomorphic encryption is a powerful cryptographic technique that allows computation on the encrypted data 106 without first decrypting the encrypted data. Even though homomorphic operations can be performed on the encrypted data, the results of the operations remain encrypted, and no information about the underlying plaintext is accessible.
The computing device 100 implements an encryption application 110 that can include various algorithms to implement the techniques of high-precision rational number arithmetic 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 110 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 110 , 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 110 and the various algorithms is described following, with additional implementation detail described with reference to FIG. 2 .
Generally, the techniques and algorithms of high-precision rational number arithmetic in homomorphic encryption as described herein are agnostic to the homomorphic encryption scheme that is being used. However for simplicity, the discussion centers on Ring-LWE (Learning With Errors)-based cryptosystems. Fully homomorphic encryption refers to an encryption scheme which enables Boolean or arithmetic circuits to be evaluated on the encrypted data 106 , without requiring access to the secret key used to encrypt the data. In RLWE-based homomorphic encryption schemes, the native plaintext elements are polynomials in a ring
t [x]/(x n +1), where n is a power of two (2) and t is an integer modulus.
For performing rational number arithmetic, an encoding scheme is used, which converts the inputs to polynomials and allows the result of the homomorphic computation to be decoded to recover the result as a rational number. A problem is that the modulus t often needs to be extremely large to prevent the plaintext polynomial coefficients from being reduced modulo t during the computation, which is a requirement for the decoding operation to work correctly. This results in larger noise growth, and prevents the evaluation of deep circuits, unless the encryption parameters are significantly increased.
In aspects of high-precision rational number arithmetic in homomorphic encryption as implemented by the encryption application 110 described herein, the modulus t is replaced by a polynomial (xâb) in the Fan-Vercauteren (FV) encryption scheme. This yields a new encryption scheme, referred to herein as âFVbâ with a convenient plaintext space
/(b n +1)
. Rational numbers can be encoded as elements of this plaintext space, enabling homomorphic evaluation of deep circuits with high-precision rational number inputs. For example, the new FVb scheme allows the encryption application 110 to evaluate circuits of depth nine (9) with 32-bit integer inputs, whereas in the same parameter setting, the Fan-Vercauteren scheme only allows up to depth two (2).
Generally, the encryption schemes that are used for homomorphic encryption have several features in common. For example, security is based on the hardness of either the Learning With Errors (LWE) or the Ring Learning With Errors (RLWE) problem, which makes the plaintext and ciphertext spaces very similar in the different schemes. Another commonality is that in each homomorphic encryption scheme, every ciphertext 108 has an inherent attribute called noise, which accumulates in homomorphic operations 112 , particularly when homomorphic multiplication operations are performed on the ciphertexts, and the accumulating noise corrupts the ciphertext once it reaches a certain maximum value. Once a ciphertext 108 is corrupted, it can no longer be decrypted, even with the correct secret key. Thus, an efficient solution is to increase the parameters of the encryption scheme, allowing deep enough circuits to be evaluated before the noise ceiling is reached. This approach is called a âleveled fullyâ homomorphic encryption scheme, as implemented by the encryption application 110 .
In most homomorphic encryption schemes based on the Ring Learning With Errors (RLWE) assumption, the natural plaintext elements are polynomials in a ring R t =
t [x]/Φ m (x), where Φ m denotes the m-th cyclotomic polynomial. For security and performance, it is common to restrict m to be a power of two (2), in which case Φ 2n (x) is of the form x n +1. Thus, homomorphic operations 112 performed on the ciphertexts 108 reflect on the plaintext side as additions and multiplications in the ring R t . However, this is unnatural for nearly all naturally occurring applications, as in practice, operations are performed on encrypted integers and rational numbers. For this reason, an encoding of elements of
or
into polynomials in R t is utilized, which respects both additions and multiplications, and is also injective in a large domain (subset of
or
), so that the results of a computation can be decoded after decryption.
Several different encoding methods for integers and rational numbers can be used, but all have a common limitation of the decoding operation will perform correctly only as long as the homomorphic operations 112 do not cause the underlying plaintext polynomial coefficients to be reduced modulo the integer t. In order for the result to be correct as an integer or as a rational number, t needs to be set sufficiently large. Therefore, when selecting encryption parameters for applications, considerations include making sure that the noise does not overflow, and also that the plaintext polynomial coefficients do not grow too large. This results in a subtle optimization problem, that in order to have no plaintext coefficient wrap-around, a large t is chosen, which unfortunately implies faster noise growth, and therefore larger parameters overall are chose for the encryption scheme to increase the noise ceiling and to preserve the security level. The consequence of this can be worse computational performance on the homomorphic encrypted data 106 .
In aspects of high-precision rational number arithmetic in homomorphic encryption, the encryption application 110 is implemented to manage the plaintext polynomial coefficient growth by replacing the modulus t with a small polynomial (xâb), for some positive integer b (e.g., b=2), turning the plaintext space into the integer quotient ring
/(b n +1)
. In typical parameter settings suitable for homomorphic encryption, n has size several thousands, yielding a plaintext space large enough to contain the results of many naturally occurring computations, without modular reduction ever taking place. The encryption application 110 is implemented to combine this method with the Fan-Vercauteren (FV) encryption scheme, which is also detailed in the Simple Encrypted Arithmetic Library (SEAL version of the library v2.1), which implements the Fan-Vercauteren scheme.
The techniques of high-precision rational number arithmetic in homomorphic encryption are described in the general context of encrypting, evaluating, and decrypting the homomorphic encrypted data 106 . The encryption application 110 can receive initial data 114 , and utilize an integer encoder 116 to encode integers that are representative of initial data 114 into plaintext polynomials 118 . The encryption application 110 also implements an encryption algorithm 120 to encrypt the plaintext polynomials 118 into the ciphertexts 108 of the homomorphic encrypted data 106 . In aspects of the encryption, the encryption application 110 encodes the integers of the initial data 114 into the plaintext polynomials 118 and encrypts the plaintext polynomials into the ciphertexts 108 as a combined process of the integer encoder 116 and the encryption algorithm 120 to generate the ciphertexts 108 of the homomorphic encrypted data.
The encryption application 110 is implemented to initiate the integer encoder 116 to encode the integers as the plaintext polynomials 118 defined as
t [x]/(x n +1) with coefficients reduced integer modulo t. The encryption application 110 can also initiate the encryption algorithm 120 to encrypt the plaintext polynomials 118 into the ciphertexts 108 , replacing the t modulus of the plaintext polynomials with (xâb) in the ciphertexts, and allowing homomorphic evaluation of large ciphertext polynomials on rational numbers. The homomorphic encrypted data 106 is encrypted based on the Fan-Vercauteren (FV) homomorphic encryption scheme with the plaintext polynomials defined as
/(b n +1)
in the FVb encryption scheme, including having replaced coefficients reduced integer modulo t of the plaintext polynomials
t [x]/(x n +1) in the FV plaintext space with (xâb). Further, the polynomials of the ciphertexts 108 of the homomorphic encrypted data 106 can be encrypted in log base two (log 2 ) with the coefficients 122 of the encrypted polynomials being less than or equal to one. The encryption application 110 replaces the t modulus of the plaintext polynomials
t [x]/(x n +1) in the FV plaintext space with (xâb) effective to minimize t and allow homomorphic evaluation of large ciphertext polynomials on encrypted rational numbers (to include the input integers), as well as increase processing efficiency of the homomorphic encryption scheme.
The encryption application 110 can utilize or apply one or more of various homomorphic encryption algorithms 124 to perform the homomorphic operations 112 , such as multiplication operations on the ciphertexts 108 of the homomorphic encrypted data 106 , as well as rational number arithmetic on the ciphertexts. The homomorphic operations 112 generate updated ciphertexts 126 while the homomorphic encrypted data remains encrypted. As described herein, the ciphertexts 108 of the homomorphic encrypted data 106 are susceptible to a noise increase contributed by the multiplication operations on the ciphertexts. However, the noise increase in the FVb encryption scheme is optimized in the ciphertexts, effective to maximize a multiplicative depth of the homomorphic operations performed on encrypted rational numbers. The t modulus of the plaintext polynomials in the FV encryption scheme being replaced with (xâb) allows optimization of the noise increase in the ciphertexts utilizing a large b value.
The encryption application 110 can utilize a decryption algorithm 128 to then decrypt the updated ciphertexts 126 to modified plaintext polynomials 130 that can be resolved back to the plaintext polynomials 118 effective to recover the integers that represent the initial data 114 . The decryption algorithm 128 can decode the modified plaintext polynomials 130 back to the integers effective to recover the initial data in an unencrypted form. In aspects of the decryption, the encryption application 110 decrypts the updated ciphertexts 126 to the modified plaintext polynomials 130 and decodes the modified plaintext polynomials as a combined process of the decryption algorithm 128 to recover the initial data 114 in the unencrypted form.
In aspects of high-precision rational number arithmetic in homomorphic encryption, the decryption algorithm 128 is implemented to perform the homomorphic computations in
[x] (integer coefficient polynomials) rather than in
[x]/(x n +1). A decryption result is an integer modulo (B n +1) where B is some small number. The modulo operation finds the remainder after division of one number by another. For example, given two positive numbers a and n, a modulo n is the remainder of the Euclidean division of a by n. When the computation is performed over
[x], this number B is already reduced modulo (B n +1), and a small integer result is obtained. This provides for faster decryption of the homomorphic encrypted data 106 , without needing to perform processing intensive reduction modulo the large number (B n +1).
With reference to notation used herein, for n is a power of two (2), denote R=
[x]/(x n +1) as the 2n-th cyclotomic ring of integers. For an integer a, denote R a =R/aR=
a [x]/(x n +1) and
=Râ
=
[x]/(x n +1). Additionally, pâ
[x] and the infinity norm of p is denoted â¥pâ¥. For pâR (or R a ,
), consider the representative with the lowest possible degree, encounter the infinity norm in the canonical embedding, and for pâR (or pâ
), denote it by â¥p⥠can . For integers modulo a, use representatives in the symmetric interval [ââ(aâ1)/2â, â(aâ1)/2â]. For a polynomial pâ
[x],[p] a denotes the coefficient-wise reduction modulo a. For pâ
[x] denote rounding of the coefficients to the nearest integer by âpâ. For a polynomial p and an integer base w, denote the polynomials in its coefficient-wise base-w decomposition by p (i) , where i=0, . . . , âlog w â¥pâ¥â. Then denote by Ï a discrete Gaussian distribution having standard deviation Ï, truncated as some large bound B (e.g., Bâ6Ï). The computational security parameter is denoted λ, and âlogâ represents log 2 .
Fan-Vercauteren Scheme
With reference to the previous FV scheme, the plaintext space is the R t , and the ciphertext space is the product ring R q ÃR q , and assume t<<q, which is the case for nearly all useful parameter choices. The degree n in the polynomial modulus x n +1 is a power of two (2) (e.g., typically at least 1024). The standard deviation Ï of Ï is often in practice chosen rather small, such as Ï
CLAIMS
Claims ( 18 )
The invention claimed is:
1. A computing device implemented for high-precision rational number arithmetic 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:
encode integers into plaintext polynomials, the integers representative of initial data received for encryption, wherein the plaintext polynomials comprise coefficients reduced integer modulo t;
encrypt the plaintext polynomials into ciphertexts of the homomorphic encrypted data, wherein encrypting the plaintext polynomials into the ciphertexts comprises replacing each coefficient reduced integer modulo t with a polynomial;
perform homomorphic operations as rational number arithmetic on the ciphertexts, generating updated ciphertexts while the homomorphic encrypted data remains encrypted;
decrypt the updated ciphertexts to modified plaintext polynomials encoding the plaintext polynomials; and
decode the modified plaintext polynomials back to the integers to recover the initial data in an unencrypted form, wherein the encryption application is implemented to encode the integers as the plaintext polynomials and encrypt the plaintext polynomials into the ciphertexts to allow homomorphic evaluation of ciphertext polynomials on rational numbers.
2. The computing device as recited in claim 1 , wherein the encryption application is implemented to encode the integers into the plaintext polynomials and encrypt the plaintext polynomials into the ciphertexts as a combined process to generate the ciphertexts of the homomorphic encrypted data.
3. The computing device as recited in claim 1 , wherein the encryption application is implemented to decrypt the updated ciphertexts to the modified plaintext polynomials and decode the modified plaintext polynomials as a combined process to recover the initial data in the unencrypted form.
4. The computing device as recited in claim 1 , wherein the encryption application is implemented to maximize a multiplicative depth of a homomorphic computation performed on the rational numbers.
5. The computing device as recited in claim 1 , wherein the homomorphic encrypted data is encrypted based on a Fan-Vercauteren (FV) homomorphic encryption scheme with the plaintext polynomials defined as
/(b n +1)
in an FVb encryption scheme, and wherein replacing each coefficient reduced integer modulo t comprises replacing each coefficient reduced integer modulo t with (xâb).
6. The computing device as recited in claim 5 , wherein polynomials of the ciphertexts of the homomorphic encrypted data are encrypted in log base two (log 2) with coefficients of the encrypted polynomials being less than or equal to one.
7. The computing device as recited in claim 5 , wherein the encryption application is implemented to replace the t modulus of the plaintext polynomials
t [x]/(x n +1) in the FV plaintext space with (xâb) to minimize t and allow homomorphic evaluation of ciphertext polynomials on encrypted rational numbers.
8. The computing device as recited in claim 5 , wherein the encryption application is implemented to:
perform multiplication operations on the ciphertexts as the homomorphic operations, the ciphertexts of the homomorphic encrypted data being susceptible to a noise increase contributed by the multiplication operations on the ciphertexts; and
optimize the noise increase in the ciphertexts contributed by the multiplication operations to maximize a multiplicative depth of the homomorphic operations performed on encrypted rational numbers.
9. The computing device as recited in claim 8 , wherein the t modulus of the plaintext polynomials being replaced with (xâb) allows optimization of the noise increase in the ciphertexts.
10. A method of high-precision rational number arithmetic in homomorphic encryption, the method comprising:
accessing an encryption application at a computing device;
encoding integers into plaintext polynomials by the encryption application, the integers representative of initial data received for encryption, and wherein the plaintext polynomials comprise coefficients reduced integer modulo t;
encrypting the plaintext polynomials into ciphertexts of homomorphic encrypted data, wherein encrypting the plaintext polynomials into the ciphertexts comprises replacing each coefficient reduced integer modulo t with a polynomial;
performing homomorphic operations as rational number arithmetic on the ciphertexts, the homomorphic operations generating updated ciphertexts while the homomorphic encrypted data remains encrypted;
decrypting the updated ciphertexts to modified plaintext polynomials encoding the plaintext polynomials; and
decoding the modified plaintext polynomials back to the integers to recover the initial data in an unencrypted form, wherein encoding the integers as the plaintext polynomials and encrypting the plaintext polynomials into the ciphertexts allows homomorphic evaluation of ciphertext polynomials on rational numbers.
11. The method as recited in claim 10 , wherein the homomorphic encrypted data is encrypted based on a Fan-Vercauteren (FV) homomorphic encryption scheme with the plaintext polynomials defined as
/(b n +1)
in an FVb encryption scheme, and wherein replacing each coefficient reduced integer modulo t comprises replacing each coefficient reduced integer modulo t with (xâb).
12. The method as recited in claim 11 , wherein polynomials of the ciphertexts of the homomorphic encrypted data are encrypted in log base two (log 2) with coefficients of the encrypted polynomials being less than or equal to one.
13. The method as recited in claim 11 , further comprising:
replacing the t modulus of the plaintext polynomials
t [x]/(x n +1) with (xâb) in the FVb encryption scheme to minimize t and allow homomorphic evaluation of ciphertext polynomials on encrypted rational numbers.
14. The method as recited in claim 11 , further comprising:
performing multiplication operations on the ciphertexts as the homomorphic operations, the ciphertexts of the homomorphic encrypted data being susceptible to a noise increase contributed by the multiplication operations on the ciphertexts; and
optimizing the noise increase in the ciphertexts contributed by the multiplication operations to maximize a multiplicative depth of the homomorphic operations performed on encrypted rational numbers.
15. The method as recited in claim 14 , wherein the t modulus of the plaintext polynomials being replaced with (xâb) allows optimization of the noise increase in the ciphertexts.
16. A method of high-precision rational number arithmetic in homomorphic encryption, the method comprising:
accessing an encryption application at a computing device;
generating, by the encryption application, ciphertexts of homomorphic encrypted data to encode integers representative of initial data received for encryption into plaintext polynomials comprising coefficients reduced integer modulo t, combined with encrypting the plaintext polynomials into the ciphertexts;
wherein encrypting the plaintext polynomials into the ciphertexts comprises replacing the t modulus with a polynomial;
performing homomorphic operations as rational number arithmetic on the ciphertexts, generating updated ciphertexts while the homomorphic encrypted data remains encrypted; and
recovering the initial data in an unencrypted form by a decryption process of decrypting the updated ciphertexts to modified plaintext polynomials combined with decoding the modified plaintext polynomials that resolve back to the plaintext polynomials and the integers that represent the initial data, wherein encoding the integers as the plaintext polynomials and encrypting the plaintext polynomials into the ciphertexts allows homomorphic evaluation of ciphertext polynomials on rational numbers.
17. The method as recited in claim 16 , wherein the generating the ciphertexts encrypts the homomorphic encrypted data based on a Fan-Vercauteren (FV) homomorphic encryption scheme with the plaintext polynomials defined as
/(b n +1)
in an FVb encryption scheme, and wherein replacing each coefficient reduced integer modulo t comprises replacing each coefficient reduced integer modulo t with (xâb).
18. The method as recited in claim 17 , wherein:
the homomorphic operations are multiplication operations performed on the ciphertexts of the homomorphic encrypted data, the ciphertexts of the homomorphic encrypted data being susceptible to a noise increase contributed by the multiplication operations on the ciphertexts; and
optimizing the noise increase in the ciphertexts contributed by the multiplication operations to maximize a multiplicative depth of the homomorphic operations performed on encrypted rational numbers.
US15/638,181
2017-06-29
2017-06-29
High-precision rational number arithmetic in homomorphic encryption
Active
2037-09-21
US10749665B2
( en )
Priority Applications (3)
Application Number
Priority Date
Filing Date
Title
US15/638,181
US10749665B2
( en )
2017-06-29
2017-06-29
High-precision rational number arithmetic in homomorphic encryption
EP18743205.9A
EP3646524B1
( en )
2017-06-29
2018-06-27
High-precision rational number arithmetic in homomorphic encryption
PCT/US2018/039634
WO2019005891A1
( en )
2017-06-29
2018-06-27
High-precision rational number arithmetic in homomorphic encryption
Applications Claiming Priority (1)
Application Number
Priority Date
Filing Date
Title
US15/638,181
US10749665B2
( en )
2017-06-29
2017-06-29
High-precision rational number arithmetic in homomorphic encryption
Publications (2)
Publication Number
Publication Date
US20190007197A1
US20190007197A1 ( en )
2019-01-03
US10749665B2
true
US10749665B2 ( en )
2020-08-18
Family
ID=62976209
Family Applications (1)
Application Number
Title
Priority Date
Filing Date
US15/638,181
Active
2037-09-21
US10749665B2
( en )
2017-06-29
2017-06-29
High-precision rational number arithmetic in homomorphic encryption
Country Status (3)
Country
Link
US
( 1 )
US10749665B2
( en )
EP
( 1 )
EP3646524B1
( en )
WO
( 1 )
WO2019005891A1
( en )
Cited By (6)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20220140997A1
( en )
*
2020-11-01
2022-05-05
The Toronto-Dominion Bank
Validating confidential data using homomorphic computations
US11374736B2
( en )
*
2018-06-20
2022-06-28
Clemson University
System and method for homomorphic encryption
US11907380B2
( en )
2021-05-17
2024-02-20
International Business Machines Corporation
In-memory computation in homomorphic encryption systems
US20240104224A1
( en )
*
2022-09-27
2024-03-28
Intel Corporation
Privacy-preserving search using homomorphic encryption
US20240160423A1
( en )
*
2022-11-11
2024-05-16
Electronics And Telecommunications Research Institute
Program conversion apparatus and method
US20240214201A1
( en )
*
2022-12-20
2024-06-27
Axell Corporation
Encryption processing apparatus and encryption processing method
Families Citing this family (29)
* 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
US10541805B2
( en )
2017-06-26
2020-01-21
Microsoft Technology Licensing, Llc
Variable relinearization 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
US11799628B2
( en )
*
2018-12-07
2023-10-24
Crypto Lab Inc.
Apparatus and method for processing non-polynomial operation on encrypted messages
US11764940B2
( en )
2019-01-10
2023-09-19
Duality Technologies, Inc.
Secure search of secret data in a semi-trusted environment using homomorphic encryption
US11436340B2
( en )
2019-06-24
2022-09-06
Bank Of America Corporation
Encrypted device identification stream generator for secure interaction authentication
CN110765147B
( en )
*
2019-10-22
2022-09-06
å ¨é¾éæéå ¬å¸
Content updating method based on block chain encrypted storage, user node and medium
BR112022008988A2
( en )
*
2019-11-14
2022-08-09
Senecio Ltd
SYSTEM AND METHOD FOR GROUPING AND COUNTING OF AUTOMATED AND SEMI-AUTOMATED MOSQUITO SEPARATION IDENTIFICATION
CN110969261B
( en )
*
2019-11-29
2023-11-28
ä¸å½é¶è¡è¡ä»½æéå ¬å¸
Encryption algorithm-based model construction method and related equipment
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
KR102926830B1
( en )
*
2020-04-28
2026-02-11
ì¼ì±ì ì주ìíì¬
Operating method of memory controller, cloud computing device and edge computer
FR3110311B1
( en )
*
2020-05-14
2022-07-01
Zama
evaluation of real-valued functions on encrypted data
KR20220048225A
( en )
*
2020-10-12
2022-04-19
ì¼ì±ì ì주ìíì¬
Homomorphic encryption accelerator and homomorphic operation performing device including the same
US12250291B2
( en )
*
2020-11-10
2025-03-11
Evernorth Strategic Development, Inc.
Encrypted database systems including homomorphic encryption
CN113421096A
( en )
*
2021-08-17
2021-09-21
æ¯ä»å®(æå·)ä¿¡æ¯ææ¯æéå ¬å¸
Block chain-based goods transaction method and device
JP7187074B1
( en )
*
2021-10-26
2022-12-12
æ ªå¼ä¼ç¤¾ã¢ã¯ã»ã«
Cryptographic processing device, cryptographic processing method, and cryptographic processing program
US12381710B2
( en )
*
2021-11-04
2025-08-05
Samsung Electronics Co., Ltd.
Crypto processor and electronic device including the same
US12362905B2
( en )
*
2021-12-09
2025-07-15
Electronics And Telecommunications Research Institute
Computing apparatus and method of integrating different homomorphic operations in homomorphic encryption
US11856083B2
( en )
*
2022-01-06
2023-12-26
International Business Machines Corporation
Analysis and debugging of fully-homomorphic encryption
KR20230161779A
( en )
*
2022-05-19
2023-11-28
ìì¸ëíêµì°ííë ¥ë¨
Device and Method for Homomorphic Permutation
CN115174035B
( en )
*
2022-06-30
2024-12-17
èèåºåé¾ç§æ(ä¸æµ·)æéå ¬å¸
Data processing method and device
US20240171371A1
( en )
*
2022-11-23
2024-05-23
Intel Corporation
Homomorphic encryption encode/encrypt and decrypt/decode device
CN116226471B
( en )
*
2023-05-10
2023-07-25
æµå®èç软件ç§ææéå ¬å¸
Data storage method for homeland resource planning
CN116886447B
( en )
*
2023-09-07
2024-02-13
ä¸å½çµåç§æéå¢å ¬å¸ç¬¬åäºç 究æ
Encryption transmission method and device for simplified encoding and decoding
CN118312486B
( en )
*
2024-06-11
2024-09-06
æµæ±å¤©æ£ä¿¡æ¯ç§ææéå ¬å¸
Data security circulation method based on cross-domain data communication sharing platform
CN119051837B
( en )
*
2024-10-30
2025-01-10
ä¸æµ·ç±å¯çä¿¡æ¯ææ¯è¡ä»½æéå ¬å¸
Homomorphic encryption processing method, homomorphic encryption processing system, electronic device, storage medium and program product
Citations (45)
* 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
US6772339B1
( en )
2000-03-13
2004-08-03
Lucent Technologies Inc.
Mix and match: a new approach to secure multiparty computation
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
US20120039463A1
( en )
2010-08-16
2012-02-16
International Business Machines Corporation
Fast Evaluation Of Many Polynomials With Small Coefficients On The Same Point
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
US20180011996A1
( en )
2015-01-15
2018-01-11
Secretskydb Ltd
Secret shared random access machine
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
US20180375640A1
( en )
2017-06-26
2018-12-27
Microsoft Technology Licensing, Llc
Variable Relinearization in Homomorphic Encryption
US20190220734A1
( en )
2016-10-11
2019-07-18
The Research Foundation For The State University Of New York
System, Method, and Accelerator to Process Convolutional Neural Network Layers
2017
2017-06-29
US
US15/638,181
patent/US10749665B2/en
active
Active
2018
2018-06-27
EP
EP18743205.9A
patent/EP3646524B1/en
not_active
Not-in-force
2018-06-27
WO
PCT/US2018/039634
patent/WO2019005891A1/en
not_active
Ceased
Patent Citations (49)
* 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
US6772339B1
( en )
2000-03-13
2004-08-03
Lucent Technologies Inc.
Mix and match: a new approach to secure multiparty computation
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
US20150358153A1
( en )
2011-04-29
2015-12-10
International Business Machines Corporation
Fully Homomorphic Encryption
US20130170640A1
( en )
2011-04-29
2013-07-04
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
US20160191233A1
( en )
2012-12-21
2016-06-30
Microsoft Technology Licensing, Llc
Managed secure computations on encrypted data
US20140177828A1
( en )
2012-12-21
2014-06-26
Microsoft Corporation
Managed secure computations on encrypted data