ABSTRACT
Abstract
Embodiments are described for a method of performing fully homomorphic encryption on a data set by providing a multivariate encryption polynomial to produce an encrypted data set and a multivariate decryption polynomial to decrypt the encrypted data set, providing a multivariate function polynomial that represents an operation to be performed on the encrypted data set, and recomposing the function polynomial with encryption polynomial. Also described are a method comprising providing a private key comprising a multivariate polynomial polynomial function to encrypt plaintext data to produce ciphertext, and providing a public key comprising a multivariate set of equations derived from the private key and a randomly selected injective vectorial multivariate function to decrypt the ciphertext.
Description
CROSS-REFERENCE TO RELATED APPLICATIONS
The present application claims the benefit of the U.S. Provisional Application No. 61/658,502 entitled âEfficient Fully Homomorphic Encryption on Arbitrary Boolean Circuits,â and filed on Jun. 12, 2012.
BACKGROUND
Homomorphic encryption has long been a subject of great interest in the field of cryptography due to its potential applications in cloud computing for outsourcing analysis and hosting of private data. Homomorphic encryption generally refers to encryption that allows functions to be performed on ciphertext to obtain an encrypted result. When decrypted, the result matches the result of the same functions performed on the plaintext. This allows a person to encrypt data and have functions (e.g., data mining operations) performed on the data by a third party, without that third party being able to perceive the data. Fully homomorphic encryption supports both addition and multiplication operations, and thus preserves the ring structure of the plaintext. Under this scheme, any circuit can be homomorphically evaluated, allowing the construction of programs that may be run on encryptions of their inputs to produce an encryption of their output. Since such a program never decrypts its input, the inputs and the internal state of the data is never exposed, and cannot be perceived by a third party.
The first fully homomorphic encryption scheme using lattice-based cryptography was shown by Craig Gentry of IBM in mid-2009. Gentry's method was based on the accumulation of an error vector, which is corrected for by âhomomorphicallyâ decrypting the data and squashing the error. This method thus requires and introduces ciphertext expansion and error squashing operations. At present, deployment of the Gentry homomorphic encryption system is not practical because of the excessive time and processor resources required. For example, using non-homomorphic analysis on a 256-bit AES (Advanced Encryption Standard) block takes on the order of milliseconds using present computer systems, but upwards of 36 hours when performed using the Gentry homomorphic encryption method. This is clearly an unacceptable amount of time and processing overhead for most, if not all practical applications at present.
The subject matter discussed in the background section should not be assumed to be prior art merely as a result of its mention in the background section. Similarly, a problem mentioned in the background section or associated with the subject matter of the background section should not be assumed to have been previously recognized in the prior art. The subject matter in the background section merely represents different approaches, which in and of themselves may also be inventions.
BRIEF SUMMARY OF EMBODIMENTS
Embodiments include a method of performing fully homomorphic encryption on a data set by providing a multivariate encryption polynomial to produce an encrypted data set and a multivariate decryption polynomial to decrypt the encrypted data set, providing a multivariate function polynomial that represents an operation to be performed on the encrypted data set, and recomposing the function polynomial with encryption polynomial. The function polynomial comprises a ciphertext representation of the data set. The method further comprises distributing the encryption polynomial and the function polynomial to a user publicly, and distributing the decryption polynomial to the user privately. At least one of the encryption polynomial and the decryption polynomial is an algebraic normal form equation, and the algebraic normal form comprises a non-linear Boolean circuit consisting of a set of Boolean functions. The Boolean circuit comprises a left inverse function.
In an embodiment, the multivariate decryption polynomial comprises a private key consisting of a plurality of matrices and a vectorial multivariate polynomial function, and wherein the multivariate encryption polynomial comprises a public key derived from the private key and a randomly selected injective vectorial multivariate function. The method may further comprise orthogonally embedding information required for decryption in the ciphertext and the multivariate encryption polynomial. The injective vectorial multivariate equation comprises a randomly chosen multivariate quadratic function, and wherein a nullspace of the quadratic function is trivial. The ciphertext may comprise a noised ciphertext space, and the method may further comprise adding noise to the data set, the noise comprising randomly selected plaintext noise and ciphertext noise, and removing the noise from the data set by mapping data set values to a lower dimensional space. The method may provide an obfuscation function that hides parameters of an encryption function generating the encrypted data, the obfuscation function selecting random bits of an output set comprising the encrypted data set, and wherein the random bits are ignored by a decryption function decrypting the encrypted data.
Embodiments are also directed to a method of performing fully homomorphic encryption on a data set, comprising providing an algebraic representation of a public encryption key that encrypts the data set, providing an algebraic representation of a private decryption key that decrypts the data set, providing an algebraic representation of a function to be executed on the data, and orthogonally embedding information required for decryption of the data set encryption key. The private decryption key comprises a plurality of matrices and a vectorial multivariate polynomial function, and the public encryption key is derived from the private decryption key and a randomly selected injective vectorial multivariate function. The selected injective vectorial multivariate function comprises orthogonally embedding information required for decryption of the data set, and the injective vectorial multivariate equation comprises a randomly chosen multivariate quadratic function, and wherein a nullspace of the quadratic function is trivial.
Embodiments are further directed to a method of performing fully homomorphic encryption on a data set by providing a private key comprising a multivariate polynomial polynomial function to encrypt plaintext data to produce ciphertext, and providing a public key comprising a multivariate set of equations derived from the private key and a randomly selected injective vectorial multivariate function to decrypt the ciphertext. This method may further comprise encrypting a first plaintext data set to generate a first ciphertext, encrypting a second plaintext data set to generate a second ciphertext, and comparing the first and second ciphertexts to determine equivalence. Such a method enables the determination of whether a numerical representation of the first ciphertext is greater than or less than the second ciphertext. Such a method also enables a function such as binary search, sorting, and hashtable generation over multiple ciphertext blocks of at least one of the first ciphertext and the second ciphertext. Such a method also enables representing null terminated string and common string operations.
Embodiments are further directed to circuits and systems that implement the above-described methods, as well as computer-readable media that store instructions implementing the above-described methods.
BRIEF DESCRIPTION OF THE DRAWINGS
In the following drawings like reference numbers are used to refer to like elements. Although the following figures depict various examples, the one or more implementations are not limited to the examples depicted in the figures.
FIG. 1 is a block diagram of an embodiment of a homomorphic encryption process that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 2 is a functional diagram of a key generation process in a homomorphic encryption system that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 3 is a functional diagram of a private key encryption process in a homomorphic encryption system that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 4 is a functional diagram of a public key encryption process in a homomorphic encryption system that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 5 is a functional diagram of a homomorphic circuit generation process in a homomorphic encryption system that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 6 is a functional diagram of homomorphic circuit evaluation on provided data, under an embodiment.
FIG. 7 is a functional diagram of homomorphic circuit evaluation on cloud data, under an embodiment.
DETAILED DESCRIPTION
Embodiments are described for a fully homomorphic encryption method that directly constructs an algebraic representation of the homomorphic circuit in terms of the ciphertext. Such a method includes a process for building left invertible circuits and their generalized left inverse over polynomial rings. Embodiments are further described for a multivariate cryptographic scheme that enables fully homomorphic evaluations of arbitrary Boolean circuits through their algebraic normal form representation as systems of multivariate polynomial equations. Such methods are used in a private key/public key encryption system that supports symmetric and asymmetric modes of data encryption to implement cryptosystems to enable scenarios such as sending encrypted e-mail messages that are searchable while still in the cloud, data mining of private databases, or outsourcing of sensitive operations without sacrificing security. Embodiments take advantage of the fact that Boolean functions and boolean circuits in the form of systems of algebraic normal functions can be efficiently evaluated on modern processors by a generalization of certain algorithms and even more efficiently evaluated with highly parallelized GPU (graphic processing unit) algorithms.
Aspects of the one or more embodiments described herein may be implemented in a computer system that processes data. Any of the described embodiments may be used alone or together with one another in any combination. Although various embodiments may have been motivated by various deficiencies with the prior art, which may be discussed or alluded to in one or more places in the specification, the embodiments do not necessarily address any of these deficiencies. In other words, different embodiments may address different deficiencies that may be discussed in the specification. Some embodiments may only partially address some deficiencies or just one deficiency that may be discussed in the specification, and some embodiments may not address any of these deficiencies.
DEFINITIONS AND NOTATIONS
For purposes of description, certain definitions and nomenclature are adopted as described herein to facilitate discussion. The set {0,1} is denoted as Z 2 . By definition B is just the equivalence classes of Z 2 , but the latter is preferred because representation of Boolean circuits is more natural in Z 2 . The powerset of a set S is the set of all subsets including the emptyset is denoted P(S).
Vectors are denoted by lowercase bold letters such as a, m, or x. Matrices are identified by uppercase bold letters such as C or D. The description uses a variant of the conventional indexing x i =(x i,j ), where x i,j is the jth element of x i . Similarly, for matrices C=(C i,j ), where C i is the ith row vector of C and C i,j is the jth entry of the ith row vector of C. The capitalization serves to distinguish between indexing into a set of vectors or indexing into a matrix. If C=[x 1 x 2 . . . x n ] then x i are understood to be the column vectors of C. row vectors are represented by C=[x 1 x 2 . . . x n ] T , where T denotes the transpose. An n dimensional vector x, with entries in
2 , is noted by xε
2 n . An nÃm matrix C, with entries in
2 , is noted by
2 nÃm . Indexing individual elements is done by using commas to make clear the separation between indexes. This notation is more verbose, but clearer in cases where index variables and numbers are mixed. Examples of indexing into vectors is given below.
a
=
[
a
1
a
2
â®
a
n
]
â¢
â¢
m
i
=
CROSS-REFERENCE TO RELATED APPLICATIONS
The present application claims the benefit of the U.S. Provisional Application No. 61/658,502 entitled âEfficient Fully Homomorphic Encryption on Arbitrary Boolean Circuits,â and filed on Jun. 12, 2012.
BACKGROUND
Homomorphic encryption has long been a subject of great interest in the field of cryptography due to its potential applications in cloud computing for outsourcing analysis and hosting of private data. Homomorphic encryption generally refers to encryption that allows functions to be performed on ciphertext to obtain an encrypted result. When decrypted, the result matches the result of the same functions performed on the plaintext. This allows a person to encrypt data and have functions (e.g., data mining operations) performed on the data by a third party, without that third party being able to perceive the data. Fully homomorphic encryption supports both addition and multiplication operations, and thus preserves the ring structure of the plaintext. Under this scheme, any circuit can be homomorphically evaluated, allowing the construction of programs that may be run on encryptions of their inputs to produce an encryption of their output. Since such a program never decrypts its input, the inputs and the internal state of the data is never exposed, and cannot be perceived by a third party.
The first fully homomorphic encryption scheme using lattice-based cryptography was shown by Craig Gentry of IBM in mid-2009. Gentry's method was based on the accumulation of an error vector, which is corrected for by âhomomorphicallyâ decrypting the data and squashing the error. This method thus requires and introduces ciphertext expansion and error squashing operations. At present, deployment of the Gentry homomorphic encryption system is not practical because of the excessive time and processor resources required. For example, using non-homomorphic analysis on a 256-bit AES (Advanced Encryption Standard) block takes on the order of milliseconds using present computer systems, but upwards of 36 hours when performed using the Gentry homomorphic encryption method. This is clearly an unacceptable amount of time and processing overhead for most, if not all practical applications at present.
The subject matter discussed in the background section should not be assumed to be prior art merely as a result of its mention in the background section. Similarly, a problem mentioned in the background section or associated with the subject matter of the background section should not be assumed to have been previously recognized in the prior art. The subject matter in the background section merely represents different approaches, which in and of themselves may also be inventions.
BRIEF SUMMARY OF EMBODIMENTS
Embodiments include a method of performing fully homomorphic encryption on a data set by providing a multivariate encryption polynomial to produce an encrypted data set and a multivariate decryption polynomial to decrypt the encrypted data set, providing a multivariate function polynomial that represents an operation to be performed on the encrypted data set, and recomposing the function polynomial with encryption polynomial. The function polynomial comprises a ciphertext representation of the data set. The method further comprises distributing the encryption polynomial and the function polynomial to a user publicly, and distributing the decryption polynomial to the user privately. At least one of the encryption polynomial and the decryption polynomial is an algebraic normal form equation, and the algebraic normal form comprises a non-linear Boolean circuit consisting of a set of Boolean functions. The Boolean circuit comprises a left inverse function.
In an embodiment, the multivariate decryption polynomial comprises a private key consisting of a plurality of matrices and a vectorial multivariate polynomial function, and wherein the multivariate encryption polynomial comprises a public key derived from the private key and a randomly selected injective vectorial multivariate function. The method may further comprise orthogonally embedding information required for decryption in the ciphertext and the multivariate encryption polynomial. The injective vectorial multivariate equation comprises a randomly chosen multivariate quadratic function, and wherein a nullspace of the quadratic function is trivial. The ciphertext may comprise a noised ciphertext space, and the method may further comprise adding noise to the data set, the noise comprising randomly selected plaintext noise and ciphertext noise, and removing the noise from the data set by mapping data set values to a lower dimensional space. The method may provide an obfuscation function that hides parameters of an encryption function generating the encrypted data, the obfuscation function selecting random bits of an output set comprising the encrypted data set, and wherein the random bits are ignored by a decryption function decrypting the encrypted data.
Embodiments are also directed to a method of performing fully homomorphic encryption on a data set, comprising providing an algebraic representation of a public encryption key that encrypts the data set, providing an algebraic representation of a private decryption key that decrypts the data set, providing an algebraic representation of a function to be executed on the data, and orthogonally embedding information required for decryption of the data set encryption key. The private decryption key comprises a plurality of matrices and a vectorial multivariate polynomial function, and the public encryption key is derived from the private decryption key and a randomly selected injective vectorial multivariate function. The selected injective vectorial multivariate function comprises orthogonally embedding information required for decryption of the data set, and the injective vectorial multivariate equation comprises a randomly chosen multivariate quadratic function, and wherein a nullspace of the quadratic function is trivial.
Embodiments are further directed to a method of performing fully homomorphic encryption on a data set by providing a private key comprising a multivariate polynomial polynomial function to encrypt plaintext data to produce ciphertext, and providing a public key comprising a multivariate set of equations derived from the private key and a randomly selected injective vectorial multivariate function to decrypt the ciphertext. This method may further comprise encrypting a first plaintext data set to generate a first ciphertext, encrypting a second plaintext data set to generate a second ciphertext, and comparing the first and second ciphertexts to determine equivalence. Such a method enables the determination of whether a numerical representation of the first ciphertext is greater than or less than the second ciphertext. Such a method also enables a function such as binary search, sorting, and hashtable generation over multiple ciphertext blocks of at least one of the first ciphertext and the second ciphertext. Such a method also enables representing null terminated string and common string operations.
Embodiments are further directed to circuits and systems that implement the above-described methods, as well as computer-readable media that store instructions implementing the above-described methods.
BRIEF DESCRIPTION OF THE DRAWINGS
In the following drawings like reference numbers are used to refer to like elements. Although the following figures depict various examples, the one or more implementations are not limited to the examples depicted in the figures.
FIG. 1 is a block diagram of an embodiment of a homomorphic encryption process that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 2 is a functional diagram of a key generation process in a homomorphic encryption system that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 3 is a functional diagram of a private key encryption process in a homomorphic encryption system that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 4 is a functional diagram of a public key encryption process in a homomorphic encryption system that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 5 is a functional diagram of a homomorphic circuit generation process in a homomorphic encryption system that utilizes multivariate encryption polynomials, under an embodiment.
FIG. 6 is a functional diagram of homomorphic circuit evaluation on provided data, under an embodiment.
FIG. 7 is a functional diagram of homomorphic circuit evaluation on cloud data, under an embodiment.
DETAILED DESCRIPTION
Embodiments are described for a fully homomorphic encryption method that directly constructs an algebraic representation of the homomorphic circuit in terms of the ciphertext. Such a method includes a process for building left invertible circuits and their generalized left inverse over polynomial rings. Embodiments are further described for a multivariate cryptographic scheme that enables fully homomorphic evaluations of arbitrary Boolean circuits through their algebraic normal form representation as systems of multivariate polynomial equations. Such methods are used in a private key/public key encryption system that supports symmetric and asymmetric modes of data encryption to implement cryptosystems to enable scenarios such as sending encrypted e-mail messages that are searchable while still in the cloud, data mining of private databases, or outsourcing of sensitive operations without sacrificing security. Embodiments take advantage of the fact that Boolean functions and boolean circuits in the form of systems of algebraic normal functions can be efficiently evaluated on modern processors by a generalization of certain algorithms and even more efficiently evaluated with highly parallelized GPU (graphic processing unit) algorithms.
Aspects of the one or more embodiments described herein may be implemented in a computer system that processes data. Any of the described embodiments may be used alone or together with one another in any combination. Although various embodiments may have been motivated by various deficiencies with the prior art, which may be discussed or alluded to in one or more places in the specification, the embodiments do not necessarily address any of these deficiencies. In other words, different embodiments may address different deficiencies that may be discussed in the specification. Some embodiments may only partially address some deficiencies or just one deficiency that may be discussed in the specification, and some embodiments may not address any of these deficiencies.
DEFINITIONS AND NOTATIONS
For purposes of description, certain definitions and nomenclature are adopted as described herein to facilitate discussion. The set {0,1} is denoted as Z 2 . By definition B is just the equivalence classes of Z 2 , but the latter is preferred because representation of Boolean circuits is more natural in Z 2 . The powerset of a set S is the set of all subsets including the emptyset is denoted P(S).
Vectors are denoted by lowercase bold letters such as a, m, or x. Matrices are identified by uppercase bold letters such as C or D. The description uses a variant of the conventional indexing x i =(x i,j ), where x i,j is the jth element of x i . Similarly, for matrices C=(C i,j ), where C i is the ith row vector of C and C i,j is the jth entry of the ith row vector of C. The capitalization serves to distinguish between indexing into a set of vectors or indexing into a matrix. If C=[x 1 x 2 . . . x n ] then x i are understood to be the column vectors of C. row vectors are represented by C=[x 1 x 2 . . . x n ] T , where T denotes the transpose. An n dimensional vector x, with entries in
2 , is noted by xε
2 n . An nÃm matrix C, with entries in
2 , is noted by
2 nÃm . Indexing individual elements is done by using commas to make clear the separation between indexes. This notation is more verbose, but clearer in cases where index variables and numbers are mixed. Examples of indexing into vectors is given below.
a
=
[
a
1
a
2
â®
a
n
]
â¢
â¢
m
i
=
[
m
i
,
1
m
i
,
2
â®
m
i
,
k
]
â¢
â¢
x
i
=
[
x
i
,
1
x
i
,
2
â®
x
i
,
k
]
(
1
)
The nÃn identity matrix is denoted by I[n]. The truncated nÃn identity matrix is denoted by I[n; a, b]ε
2 (bâa+1)Ãn , with a<b and rows a through b preserved and the rest discarded.
I
â¡
[
n
;
2
,
3
]
=
[
0
1
0
0
0
0
1
0
]
(
2
)
The zero vector is denoted in
2 n as 0 n and the zero matrix in
2 nÃm as 0 nÃm . Polynomial vectors of order one monomials in lexicographical order are often used for convenience in describing multivariate functions. Let
(x 1 , x 2 , . . . , x n )ε
2 [x 1 , X 2 , . . . , X n ] m be a multivariate polynomial expression representing a function
:
2 n â
2 m with n inputs and m outputs and let xε
2 [X 1 , X 2 , dots, X n ] n be polynomial vector of order one monomials in lexicographical order. With x i =x i , the expression
(x) is equivalent to writing
(x 1 , x 2 , . . . , x n ).
A generalized inverse or g-inverse of a matrix A, is a matrix A + that has some of the properties of to the inverse matrix A â1 . There are many kinds of generalized inverses, but for purposes of description only two specific types of one-sided generalized inverses are relevant. The definitions below are restricted to matrices over fields, but the definitions extend to arbitrary commutative rings. The left generalized inverse of Aε
q rÃc , A + satisfies the following properties: 1. c>r and 2. A + A=I c . The right generalized inverse of Aε
q rÃc , A + satisfies the following properties: 1. r>c and 2. AA + =I r . When c=r, this gives the standard definition of a matrix inverse. An important distinction between the inverse and generalized inverses is that the generalized inverse of a matrix is not necessarily unique.
The algebraic normal form (ANF) is a canonical way of representing boolean functions. A boolean function Æ is considered to be expressed in ANF, if and only if (iÆÆ) it is expressed entirely as the sum (XOR) of a constant and products (AND) of function arguments. Furthermore, each boolean function has a unique representation in ANF. The general form of the ANF for a boolean function can be succinctly expressed as
Æ( x )=Æ( x 1 ,x 2 , . . . ,x n )=
a i Î jεi x j ââ(3)
In other words ANF form is canonical form for representing boolean functions in terms of elements from the ring of polynomials
2 [x 1 , x 2 , . . . x n ] n . The general ANF for a function Æ of four boolean variables better elucidates the structure of an ANF representation:
Æ( x 1 ,x 2 ,x 3 ,x 4 )=
a à +
a 1 x 1 +a 2 x 2 +a 3 x 3 +a 4 x 4 +
a 1,2 x 1 x 2 +a 1,3 x 1 x 3 +a 1,4 x 1 x 4 +
a 2,3 x 2 x 3 +a 2,4 x 2 x 4 +a 3,4 x 3 x 4 +
a 1,2,3 X 1 x 2 x 3 +a 1,2,4 x 1 x 2 x 4 +a 1,3,4 x 1 x 3 x 4 +
a 2,3,4 x 2 x 3 x 4 +
a 1,2,3,4 x 1 x 2 x 3 x 4 ââ(4)
Thus the representation of a Boolean function is a polynomial of n variables in the ring
2 [x 1 , x 2 , . . . , x n ]. All possible monomials on n function arguments form a set of linearly independent basis functions for all boolean functions of n variables.
Some monomial within a Boolean function is referred to as follows: Æ:
2 n â
2 , as mεÆ. This means a term in the ANF representation of Æ, and not necessarily any specific term. Similarly, mεÆ(x) is meant to be a term in the ANF representation of Æ expressed on the vector x of order one monomials with xε
2 [x 1 , x 2 , . . . , x n ] n . The entries of vector x should be understood in terms of default lexicographic ordering of order one monomials, x i =x i , with x i ε
2 [x 1 , x 2 , . . . , x n ]. Order one monomials may also be referred to as variables. Similarly, if some individual variable x i appears in some monomial term tεÆ, the notation x i εm뵮 is used. The existence of an individual variable is denoted within a monomial by âx i εmεÆ. Finally, a variable x i that does not occur in any monomial in a function is notated as x i âm, âtεÆ(x). It may occasionally be difficult to tell whether a vector is representing an element in
2 n â
2 [x 1 , x 2 , . . . , x n ] n or the full ring itself. In general, when an argument is provided during function compositions and function definitions it is intended to illustrate the polynomial description of that function. When it is ambiguous as to whether a vector is intended as a vector of order one polynomials or as vector constants (order zero polynomials) it will be explicitly noted.
Additional notation conventions are as follows. Let
:
2 n â
2 m ε
2 [x 1 , x 2 , . . . , x n ] m be a multivariate polynomial vector function, the following definitions apply for commonly defined operations and objects. The ordered set of monomials of a multivariate vector function
is the set of all monomials of
, sorted by reverse lexicographical order. It will be frequently used as an index set. The coefficient matrix of
ε
of multivariate vector function
is the matrix of coefficients corresponding to all of its monomials. The linear and non-linear contributions to
are denoted by L[
] and L [
], respectively. They satisfy the following constraints.
â t ε L [
],deg t⦠1
â t ε L [
],deg t> 1
L [
]+ L [
]=Fââ(5)
The nullspace of
is the set of all vectors in nε
2 m such that n T
={right arrow over (0)} and is denoted
. The Gröbner basis of
is denoted
(
). The ideal generated by
and its Gröbner basis <a href="https://patentimages.storage.googlea
CLAIMS
Claims ( 19 )
What is claimed is:
1. A method of performing fully homomorphic encryption on a data set, comprising:
providing a multivariate encryption polynomial to encrypt the data set and produce an encrypted data set;
providing a multivariate decryption polynomial to decrypt the encrypted data set;
providing a vectorial multivariate function polynomial that represents an operation to be performed on the encrypted data set; and
distributing the multivariate function polynomial and the multivariate encryption polynomial to a user, wherein the fully homomorphic encryption is performed based on orthogonal embeddings and based on a nondeterministic polynomial time complete (NP-complete) problem, and wherein the multivariate function polynomial and the multivariate encryption polynomial are algebraic equations and the multivariate function polynomial represents a Boolean circuit.
2. The method of claim 1 wherein the fully homomorphic encryption is performed in a public-key/private-key encryption system, and wherein the multivariate function polynomial comprises a ciphertext representation of the data set.
3. The method of claim 1 further comprising:
distributing the multivariate decryption polynomial to the user privately.
4. The method of claim 1 wherein the Boolean circuit comprises a left inverse function.
5. The method of claim 2 wherein the multivariate decryption polynomial comprises a private key consisting of a plurality of matrices and a vectorial multivariate polynomial function, and wherein the multivariate encryption polynomial comprises a public key derived from the private key and a randomly selected injective vectorial multivariate function.
6. The method of claim 5 further comprising orthogonally embedding information required for decryption in the ciphertext and the multivariate encryption polynomial.
7. The method of claim 6 wherein the injective vectorial multivariate equation comprises a randomly chosen multivariate quadratic function, and wherein a nullspace of the quadratic function is trivial.
8. The method of claim 2 wherein the ciphertext comprises noised ciphertext space, the method further comprising:
adding noise to the data set, the noise comprising randomly selected plaintext noise and ciphertext noise; and
removing the noise from the data set by mapping data set values to a lower dimensional space.
9. The method of claim 3 further comprising providing an obfuscation function that hides parameters of an encryption function generating the encrypted data, the obfuscation function selecting random bits of an output set comprising the encrypted data set, and wherein the random bits are ignored by a decryption function decrypting the encrypted data.
10. A method of performing fully homomorphic encryption on a data set, comprising:
providing a public multivariate encryption polynomial to encrypt the data set and produce an encrypted data set;
providing a private multivariate decryption polynomial to decrypt the encrypted data set;
providing a vectorial multivariate function polynomial that represents an operation to be performed on the encrypted data set; and
distributing the multivariate function polynomial to a user publicly, wherein the fully homomorphic encryption is performed based on orthogonal embeddings and based on a nondeterministic polynomial time complete (NP-complete) problem, and wherein the multivariate function polynomial and the multivariate encryption polynomial are algebraic equations and the multivariate function polynomial represents a Boolean circuit.
11. The method of claim 10 wherein the private decryption key comprises a plurality of matrices and a vectorial multivariate polynomial function.
12. The method of claim 11 wherein the public encryption key is derived from the private decryption key and a randomly selected injective vectorial multivariate function.
13. The method of claim 12 wherein the selected injective vectorial multivariate function comprises orthogonally embedding information required for decryption of the data set.
14. The method of claim 13 wherein the injective vectorial multivariate equation comprises a randomly chosen multivariate quadratic function, and wherein a nullspace of the quadratic function is trivial.
15. A method of performing fully homomorphic encryption on a data set, comprising:
providing a public multivariate encryption polynomial to encrypt the data set and produce an encrypted data set;
providing a private multivariate decryption polynomial to decrypt the encrypted data set; and
providing multiple vectorial function polynomials that represent a functionally complete set of operations to be performed on the encrypted data set; and
distributing the multiple vectorial function polynomials to a user publicly, wherein the fully homomorphic encryption is performed based on orthogonal embeddings and based on a nondeterministic polynomial time complete (NP-complete) problem, and wherein the public multivariate encryption polynomial and the private multivariate decryption polynomial are algebraic equations and the multiple vectorial multivariate function polynomials represent a functionally complete set of operators that are chained together to create a Boolean circuit.
16. The method of claim 15 further comprising representing null terminated string and common string operations.
17. The method of claim 15 further comprising:
encrypting a first plaintext data set to generate a first ciphertext;
encrypting a second plaintext data set to generate a second ciphertext; and comparing the first and second ciphertexts to determine equivalence.
18. The method of claim 15 further comprising determining whether a numerical representation of the first ciphertext is greater than or less than the second ciphertext.
19. The method of claim 18 further comprising performing at least one of binary search, sorting, and hashtable generation over multiple ciphertext blocks of at least one of the first ciphertext and the second ciphertext.
US13/915,500
2012-06-12
2013-06-11
Method for fully homomorphic encryption using multivariate cryptography
Expired - Fee Related
US9313028B2
( en )
Priority Applications (1)
Application Number
Priority Date
Filing Date
Title
US13/915,500
US9313028B2
( en )
2012-06-12
2013-06-11
Method for fully homomorphic encryption using multivariate cryptography
Applications Claiming Priority (2)
Application Number
Priority Date
Filing Date
Title
US201261658502P
2012-06-12
2012-06-12
US13/915,500
US9313028B2
( en )
2012-06-12
2013-06-11
Method for fully homomorphic encryption using multivariate cryptography
Publications (2)
Publication Number
Publication Date
US20130329883A1
US20130329883A1 ( en )
2013-12-12
US9313028B2
true
US9313028B2 ( en )
2016-04-12
Family
ID=49715321
Family Applications (1)
Application Number
Title
Priority Date
Filing Date
US13/915,500
Expired - Fee Related
US9313028B2
( en )
2012-06-12
2013-06-11
Method for fully homomorphic encryption using multivariate cryptography
Country Status (1)
Country
Link
US
( 1 )
US9313028B2
( en )
Cited By (9)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US10320559B2
( en )
2017-03-30
2019-06-11
Bank Of America Corporation
Network communication encoder using key pattern encryption
US10333906B2
( en )
2017-03-30
2019-06-25
Bank Of America Corporation
Network communication decoder using key pattern encryption
US10728017B2
( en )
2017-11-03
2020-07-28
International Business Machines Corporation
Performing vector comparison operations in fully homomorphic encryption
US20220255722A1
( en )
*
2019-06-05
2022-08-11
Crypto Lab Inc.
Practical sorting on large-scale encrypted data
US11461435B2
( en )
2017-12-18
2022-10-04
University Of Central Florida Research Foundation, Inc.
Techniques for securely executing code that operates on encrypted data on a public computer
US11515996B2
( en )
2021-02-01
2022-11-29
Seagate Technology Llc
Enforcing access structures in fully homomorphic encryption
US11522672B2
( en )
2021-02-01
2022-12-06
Seagate Technology Llc
Fully homomorphic encryption from error canceling set systems
US20240022395A1
( en )
*
2021-03-26
2024-01-18
Axell Corporation
Encryption processing device and encryption processing method
US12039079B2
( en )
2022-04-08
2024-07-16
Bank Of America Corporation
System and method to secure data pipelines using asymmetric encryption
Families Citing this family (65)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
JP2014068140A
( en )
*
2012-09-25
2014-04-17
Sony Corp
Information processor, information processing method and program
KR101795771B1
( en )
*
2013-03-18
2017-11-09
íêµì ìíµì ì°êµ¬ì
System and method for providing compressed encryption and decryption in homomorphic cryptography based on intergers
JP6173904B2
( en )
*
2013-12-13
2017-08-02
æ ªå¼ä¼ç¤¾æ±è
Common key encryption device and program, and common key decryption device and program
US10719828B2
( en )
*
2014-02-11
2020-07-21
Square, Inc.
Homomorphic passcode encryption
US10171230B2
( en )
2014-02-28
2019-01-01
Empire Technology Development Llc
Homomorphic encryption scheme
US10075288B1
( en )
*
2014-02-28
2018-09-11
The Governing Council Of The University Of Toronto
Systems, devices, and processes for homomorphic encryption
CN103916248A
( en )
*
2014-04-10
2014-07-09
ä¸å大å¦
Fully homomorphic encryption public key space compression method
US10693626B2
( en )
*
2014-04-23
2020-06-23
Agency For Science, Technology And Research
Method and system for generating/decrypting ciphertext, and method and system for searching ciphertexts in a database
CN104009848B
( en )
*
2014-05-26
2017-09-29
ååç工大å¦
A kind of multivariate digital signature system and method for mixed type
JP2016012111A
( en )
*
2014-06-30
2016-01-21
å¯å£«éæ ªå¼ä¼ç¤¾
Encryption processing method, encryption processing device, and encryption processing program
WO2016050884A1
( en )
2014-09-30
2016-04-07
Koninklijke Philips N.V.
Electronic calculating device for performing obfuscated arithmetic
CN107004072A
( en )
*
2014-12-12
2017-08-01
ç家é£å©æµ¦æéå ¬å¸
electronic generation equipment
WO2016102445A1
( en )
2014-12-22
2016-06-30
Koninklijke Philips N.V.
Electronic calculating device
US10333696B2
( en )
2015-01-12
2019-06-25
X-Prime, Inc.
Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency
US9965628B2
( en )
2015-03-02
2018-05-08
Dell Products Lp
Device reporting and protection systems and methods using a secure distributed transactional ledger
US9967334B2
( en )
2015-03-02
2018-05-08
Dell Products Lp
Computing device configuration and management using a secure decentralized transaction ledger
US10484168B2
( en )
*
2015-03-02
2019-11-19
Dell Products L.P.
Methods and systems for obfuscating data and computations defined in a secure distributed transaction ledger
US9967333B2
( en )
2015-03-02
2018-05-08
Dell Products Lp
Deferred configuration or instruction execution using a secure distributed transaction ledger
US10592985B2
( en )
2015-03-02
2020-03-17
Dell Products L.P.
Systems and methods for a commodity contracts market using a secure distributed transaction ledger
US9742556B2
( en )
*
2015-08-25
2017-08-22
International Business Machines Corporation
Comparison and search operations of encrypted data
US9948460B2
( en )
*
2015-08-28
2018-04-17
City University Of Hong Kong
Multivariate cryptography based on clipped hopfield neural network
US10075289B2
( en )
*
2015-11-05
2018-09-11
Microsoft Technology Licensing, Llc
Homomorphic encryption with optimized parameter selection
US10153894B2
( en )
2015-11-05
2018-12-11
Microsoft Technology Licensing, Llc
Homomorphic encryption with optimized encoding
US9846785B2
( en )
2015-11-25
2017-12-19
International Business Machines Corporation
Efficient two party oblivious transfer using a leveled fully homomorphic encryption
US9876636B2
( en )
2016-01-07
2018-01-23
Empire Technology Development Llc
Homomorphic public-key encryption scheme
US10296709B2
( en )
2016-06-10
2019-05-21
Microsoft Technology Licensing, Llc
Privacy-preserving genomic prediction
EP3270321B1
( en )
*
2016-07-14
2020-02-19
Kontron Modular Computers SAS
Technique for securely performing an operation in an iot environment
US10095880B2
( en )
2016-09-01
2018-10-09
International Business Machines Corporation
Performing secure queries from a higher security domain of information in a lower security domain
CN106330463B
( en )
*
2016-09-09
2019-08-20
ååç工大å¦
A kind of signature system and method for multivariable public key
US10812252B2
( en )
2017-01-09
2020-10-20
Microsoft Technology Licensing, Llc
String matching in encrypted data
US10608811B2
( en )
*
2017-06-15
2020-03-31
Microsoft Technology Licensing, Llc
Private set intersection encryption techniques
EP3642999B1
( en )
*
2017-06-20
2024-08-07
Nokia Technologies Oy
Secured computing
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
US10749665B2
( en )
2017-06-29
2020-08-18
Microsoft Technology Licensing, Llc
High-precision rational number arithmetic in homomorphic encryption
EP3493460A1
( en )
*
2017-12-01
2019-06-05
Gemalto Sa
Cryptography device having secure provision of random number sequences
IL256234A
( en )
2017-12-10
2018-01-31
Kipnis Aviad
Computation using somewhat 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
US11637694B2
( en )
*
2018-07-16
2023-04-25
Winkk, Inc.
Secret material exchange and authentication cryptography operations
US11764940B2
( en )
2019-01-10
2023-09-19
Duality Technologies, Inc.
Secure search of secret data in a semi-trusted environment using homomorphic encryption
CN112668015B
( en )
*
2019-12-12
2022-02-01
åæ§æ¸ 交信æ¯ç§æ(å京)æéå ¬å¸
Data processing method and device and data processing device
US12099997B1
( en )
2020-01-31
2024-09-24
Steven Mark Hoffberg
Tokenized fungible liabilities
CN111565101A
( en )
*
2020-04-28
2020-08-21
ä¸æµ·ç©èæºè½ç§ææéå ¬å¸
Processing method and device for computing task
DE102020207980B3
( en )
2020-06-26
2021-09-30
Siemens Healthcare Gmbh
Anonymized generation and verification of processed data
KR20220040309A
( en )
*
2020-09-23
2022-03-30
ì¼ì±ì ì주ìíì¬
Homomorphic encryption device and operating method thereof
US11989113B2
( en )
*
2020-10-19
2024-05-21
Duality Technologies, Inc.
Efficiently debugging a program in homomorphically encrypted space
US11582020B2
( en )
*
2020-12-02
2023-02-14
Verizon Patent And Licensing Inc.
Homomorphic encryption offload for lightweight devices
KR20220078155A
( en )
*
2020-12-03
2022-06-10
ì¼ì±ì ì주ìíì¬
Crypto processor and method for operating the same, and electronic device including the same
CN113888163B
( en )
*
2021-09-24
2024-07-16
å½ç½ä¸æµ·å¸çµåå ¬å¸
Smart contract bill recording and processing method based on fully homomorphic encryption
US12170718B2
( en )
*
2021-10-01
2024-12-17
Duality Technologies, Inc.
Large-precision homomorphic comparison using bootstrapping
CN114239088B
( en )
*
2021-12-13
2025-06-10
è¨ææ°åç§æ(å京)æéå ¬å¸
Boolean circuit continuous execution method and device based on garbled circuit
US20230207128A1
( en )
*
2021-12-29
2023-06-29
AiOnco, Inc.
Processing encrypted data for artificial intelligence-based analysis
CN114844621B
( en )
*
2022-04-08
2023-04-07
åå°æ»¨å·¥ä¸å¤§å¦ï¼æ·±å³ï¼
Multi-user privacy protection machine learning method and device based on multi-key full homomorphic encryption
KR20230161779A
( en )
*
2022-05-19
2023-11-28
ìì¸ëíêµì°ííë ¥ë¨
Device and Method for Homomorphic Permutation
CN114978512B
( en )
*
2022-07-18
2022-09-27
åæ§æ¸ 交信æ¯ç§æ(å京)æéå ¬å¸
Privacy intersection method and device and readable storage medium
CN115982768A
( en )
*
2022-12-31
2023-04-18
èèåºåé¾ç§æ(ä¸æµ·)æéå ¬å¸
A method and device for seeking privacy
CN116455575B
( en )
*
2023-06-16
2023-10-10
å京天润åºä¸ç§æåå±è¡ä»½æéå ¬å¸
A key generation, encryption and decryption method, electronic device and storage medium
US12562905B2
( en )
*
2024-01-22
2026-02-24
Bank Of America Corporation
System and method for encrypting user device resource transactions
CN118041509B
( en )
*
2024-02-23
2025-02-11
å京ç«å±±å¼æç§ææéå ¬å¸
Two-party secure computing method, device, electronic device, storage medium and product
US12219043B1
( en )
*
2024-06-28
2025-02-04
Semen Konstantinovich Rososhek
Method and system for homomorphic encryption
US12567947B1
( en )
*
2024-06-28
2026-03-03
Semen Konstantinovich Rososhek
Method and system for public key matrix-based homomorphic encryption
CN118568787B
( en )
*
2024-07-31
2024-12-24
èèç§æéå¢è¡ä»½æéå ¬å¸
Hardware module and its application method
CN119577800B
( en )
*
2024-11-15
2025-09-16
å京çµåç§æå¦é¢
A data sorting method based on homomorphic encryption
CN120030064B
( en )
*
2025-04-22
2025-08-08
æ¯ä»å®(æå·)ä¿¡æ¯ææ¯æéå ¬å¸
Vector retrieval method and device for protecting data privacy
Citations (7)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US6385329B1
( en )
*
2000-02-14
2002-05-07
Digimarc Corporation
Wavelet domain watermarks
US20100218037A1
( en )
*
2008-09-16
2010-08-26
File System Labs Llc
Matrix-based Error Correction and Erasure Code Methods and Apparatus and Applications Thereof
US20110243320A1
( en )
*
2010-03-30
2011-10-06
International Business Machines Corporation
Efficient Homomorphic Encryption Scheme For Bilinear Forms
US20120039463A1
( en )
*
2010-08-16
2012-02-16
International Business Machines Corporation
Fast Evaluation Of Many Polynomials With Small Coefficients On The Same Point
US20130097431A1
( en )
*
2011-10-18
2013-04-18
Paul Marion Hriljac
Systems and methods of source software code modification
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
US8762736B1
( en )
*
2008-04-04
2014-06-24
Massachusetts Institute Of Technology
One-time programs
2013
2013-06-11
US
US13/915,500
patent/US9313028B2/en
not_active
Expired - Fee Related
Patent Citations (7)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US6385329B1
( en )
*
2000-02-14
2002-05-07
Digimarc Corporation
Wavelet domain watermarks
US8762736B1
( en )
*
2008-04-04
2014-06-24
Massachusetts Institute Of Technology
One-time programs
US20100218037A1
( en )
*
2008-09-16
2010-08-26
File System Labs Llc
Matrix-based Error Correction and Erasure Code Methods and Apparatus and Applications Thereof
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
US20110243320A1
( en )
*
2010-03-30
2011-10-06
International Business Machines Corporation
Efficient Homomorphic Encryption Scheme For Bilinear Forms
US20120039463A1
( en )
*
2010-08-16
2012-02-16
International Business Machines Corporation
Fast Evaluation Of Many Polynomials With Small Coefficients On The Same Point
US20130097431A1
( en )
*
2011-10-18
2013-04-18
Paul Marion Hriljac
Systems and methods of source software code modification
Cited By (12)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US10320559B2
( en )
2017-03-30
2019-06-11
Bank Of America Corporation
Network communication encoder using key pattern encryption
US10333906B2
( en )
2017-03-30
2019-06-25
Bank Of America Corporation
Network communication decoder using key pattern encryption
US10728017B2
( en )
2017-11-03
2020-07-28
International Business Machines Corporation
Performing vector comparison operations in fully homomorphic encryption
US10735181B2
( en )
2017-11-03
2020-08-04
International Business Machines Corporation
Performing vector comparison operations in fully homomorphic encryption
US11461435B2
( en )
2017-12-18
2022-10-04
University Of Central Florida Research Foundation, Inc.
Techniques for securely executing code that operates on encrypted data on a public computer
US20220255722A1
( en )
*
2019-06-05
2022-08-11
Crypto Lab Inc.
Practical sorting on large-scale encrypted data
US12149604B2
( en )
*
2019-06-05
2024-11-19
Crypto Lab Inc.
Practical sorting on large-scale encrypted data
US11515996B2
( en )
2021-02-01
2022-11-29
Seagate Technology Llc
Enforcing access structures in fully homomorphic encryption
US11522672B2
( en )
2021-02-01
2022-12-06
Seagate Technology Llc
Fully homomorphic encryption from error canceling set systems
US20240022395A1
( en )
*
2021-03-26
2024-01-18
Axell Corporation
Encryption processing device and encryption processing method
US12621120B2
( en )
*
2021-03-26
2026-05-05
Axell Corporation
Encryption processing device and encryption processing method
US12039079B2
( en )
2022-04-08
2024-07-16
Bank Of America Corporation
System and method to secure data pipelines using asymmetric encryption
Also Published As
Publication number
Publication date
US20130329883A1
( en )
2013-12-12
Similar Documents
Publication
Publication Date
Title
US20130329883A1
( en )
2013-12-12
Method for fully homomorphic encryption using multivariate cryptography
Bourse et al.
2020
Improved secure integer comparison via homomorphic encryption
Benhamouda et al.
2017
CCA-secure inner-product functional encryption from projective hash functions
Agrawal et al.
2011
Functional encryption for inner product predicates from learning with errors
Roetteler et al.
2015
A note on quantum related-key attacks
Priyadarsini
2015
A survey on some applications of graph theory in cryptography
US10630472B2
( en )
2020-04-21
Method and system for providing encrypted data on a client
Chatterjee et al.
2013
Accelerating sorting of fully homomorphic encrypted data
Damgård et al.
2010
Secure Multiparty AES: (Short Paper)
Dufour-Sans et al.
2019
Unbounded inner-product functional encryption with succinct keys
Liu et al.
2021
Algebraic attacks on rasta and dasta using low-degree equations
JPWO2010123112A1
( en )
2012-10-25
ENCRYPTION DEVICE, DECRYPTION DEVICE, ENCRYPTION METHOD, DECRYPTION METHOD, SECURITY METHOD, PROGRAM, AND RECORDING MEDIUM
Singh et al.
2013
Lattice Based Identity Based Proxy Re-Encryption Scheme.
Ustimenko et al.
2019
On the constructions of new symmetric ciphers based on nonbijective multivariate maps of prescribed degree
Yasuda et al.
2015
Secure statistical analysis using RLWE-based homomorphic encryption
Vizár et al.
2015
Cryptanalysis of chosen symmetric homomorphic schemes
Singh et al.
2014
Lattice based identity based unidirectional proxy re-encryption scheme
Sahu et al.
2016
Cryptanalytic Attacks on IDEA Block Cipher
Jain et al.
2023
Revisiting fully homomorphic encryption schemes
Liu et al.
2016
A linear algebra attack on the non-commuting cryptography class based on matrix power function
Boyle et al.
2025
Non-interactive distributed point functions
Ogura
2012
On Multivariate Public-key Cryptosystems
Huang et al.
2022
Anonymous public key encryption under corruptions
Chen et al.
2014
An encryption depth optimization scheme for fully homomorphic encryption