Conceptio › Archive › Google Patents

Google Patentsopen access

Fully homomorphic encryption — International Business Machines Corporation (US9716590B2)

International Business Machines Corporation · Google Patents

Google Patents · Patents · License: Open Access

craigb.gentry internationalbusinessmachinescorporation

patent, google patents, intellectual property, US9716590B2, International Business Machines Corporation, Craig B. Gentry, en, 2017

ABSTRACT

Abstract

In one exemplary embodiment of the invention, a method and computer program include: receiving first and second ciphertexts having first and second data encrypted per an encryption scheme, the encryption scheme has public/secret keys and encryption, decryption, operation and refresh functions, the encryption function encrypts data, the decryption decrypts ciphertext, the operation receives ciphertexts and performs operation(s) on them, the refresh operates to prevent growth of the magnitude of noise for a ciphertext while reducing the modulus of the ciphertext without using the secret key, utilizing a modulus switching technique that involves transforming a first ciphertext c modulo q into a second ciphertext câ² modulo p while preserving correctness, the technique includes scaling by p/q and rounding, p<q; using the operation function(s), performing operation(s) on them to obtain a third ciphertext; and reducing a noise level of the third ciphertext using the refresh function.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This patent application is a continuation of U.S. patent Ser. No. 13/458,518, filed on Apr. 27, 2012, the disclosure of which is hereby incorporated by reference in its entirety, which claims priority under 35 U.S.C. Â§119(e) from Provisional Patent Application No. 61/481,048, filed Apr. 29, 2011, the disclosure of which is also incorporated by reference herein in its entirety.

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

This invention was made with Government support under contract no. FA8750-11-C-0096 awarded by Defense Advanced Research Projects Agency (DARPA). The Government has certain rights to this invention.

TECHNICAL FIELD

The exemplary embodiments of this invention relate generally to encryption/decryption schemes, algorithms, techniques, methods, computer programs and apparatus and, more specifically, relate to homomorphic encryption schemes, algorithms and apparatus.

BACKGROUND

This section endeavors to supply a context or background for the various exemplary embodiments of the invention as recited in the claims. The content herein may comprise subject matter that could be utilized, but not necessarily matter that has been previously utilized, described or considered. Unless indicated otherwise, the content described herein is not considered prior art, and should not be considered as admitted prior art by inclusion in this section.

Encryption schemes that support operations on encrypted data (aka homomorphic encryption) have a very wide range of applications in cryptography. This concept was introduced by Rivest et al. shortly after the discovery of public key cryptography [21], and many known public-key cryptosystems support either addition or multiplication of encrypted data. However, supporting both at the same time seems harder, and until recently attempts at constructing so-called âfully homomorphicâ encryption turned out to be insecure.

BRIEF SUMMARY

In one exemplary embodiment of the invention, a computer-readable storage medium storing program instructions, execution of the program instructions resulting in operations comprising: receiving a first ciphertext and a second ciphertext, where the first ciphertext comprises first data encrypted in accordance with an encryption scheme and the second ciphertext comprises second data encrypted in accordance with the encryption scheme, where the encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two ciphertexts and uses the public key to perform at least one operation on the at least two ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of the magnitude of noise for a ciphertext while reducing the modulus of the ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming a first ciphertext c modulo q into a second ciphertext câ² modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme; performing at least one operation on the first ciphertext and the second ciphertext, using the at least one operation function, to obtain a third ciphertext; and reducing a noise level of the third ciphertext by using the refresh function.

In another exemplary embodiment of the invention, a method comprising: receiving a first ciphertext and a second ciphertext, where the first ciphertext comprises first data encrypted in accordance with an encryption scheme and the second ciphertext comprises second data encrypted in accordance with the encryption scheme, where the encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two ciphertexts and uses the public key to perform at least one operation on the at least two ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of the magnitude of noise for a ciphertext while reducing the modulus of the ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming a first ciphertext c modulo q into a second ciphertext câ² modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme; performing at least one operation on the first ciphertext and the second ciphertext, using the at least one operation function, to obtain a third ciphertext; and reducing a noise level of the third ciphertext by using the refresh function.

In a further exemplary embodiment of the invention, an apparatus comprising: at least one processor configured to receive a first ciphertext and a second ciphertext, where the first ciphertext comprises first data encrypted in accordance with an encryption scheme and the second ciphertext comprises second data encrypted in accordance with the encryption scheme, where the encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two ciphertexts and uses the public key to perform at least one operation on the at least two ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of the magnitude of noise for a ciphertext while reducing the modulus of the ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming a first ciphertext c modulo q into a second ciphertext câ² modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme; and at least one memory configured to store the first ciphertext and the second ciphertext, where the at least one processor is further configured to perform at least one operation on the first ciphertext and the second ciphertext, using the at least one operation function, to obtain a third ciphertext; and to reduce a noise level of the third ciphertext by using the refresh function.

In another exemplary embodiment of the invention, an apparatus comprising: means for receiving a first ciphertext and a second ciphertext, where the first ciphertext comprises first data encrypted in accordance with an encryption scheme and the second ciphertext comprises second data encrypted in accordance with the encryption scheme, where the encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two ciphertexts and uses the public key to perform at least one operation on the at least two ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of the magnitude of noise for a ciphertext while reducing the modulus of the ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming a first ciphertext c modulo q into a second ciphertext câ² modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme; means for performing at least one operation on the first ciphertext and the second ciphertext, using the at least one operation function, to obtain a third ciphertext; and means for reducing a noise level of the third ciphertext by using the refresh function.

In a further exemplary embodiment of the invention, a computer-readable storage medium storing program instructions, execution of the program instructions resulting in operations comprising: receiving a first ciphertext and a second ciphertext, where the first ciphertext comprises first data encrypted in accordance with an encryption scheme and the second ciphertext comprises second data encrypted in accordance with the encryption scheme, where the encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two ciphertexts and uses the public key to perform at least one operation on the at least two ciphertexts and obtain a resulting ciphertext, where the refresh function operates to enable slow growth of the magnitude of noise for a ciphertext while maintaining the modulus of the ciphertext constant without using the secret key, where the encryption scheme enables homomorphic operations to be performed on ciphertexts encoded, and operated on in accordance with the encryption scheme; performing at least one operation on the first ciphertext and the second ciphertext, using the at least one operation function, to obtain a third ciphertext; and reducing a noise level of the third ciphertext by using the refresh function.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

The foregoing and other aspects of embodiments of this invention are made more evident in the following Detailed Description, when read in conjunction with the attached Drawing Figures, wherein:

FIG. 1 illustrates a block diagram of an exemplary system in which various exemplary embodiments of the invention may be implemented;

FIG. 2 illustrates a simple block diagram of a requestor and a server (e.g., devices, apparatus, computer programs, systems), such as a search engine, that use the fully homomorphic encryption scheme constructed from a bootstrappable encryption scheme in accordance with the exemplary embodiments of this invention;

FIG. 3 depicts a logic flow diagram illustrative of the operation of an exemplary method, and the operation of an exemplary computer program, in accordance with the exemplary embodiments of this invention; and

FIG. 4 depicts a logic flow diagram illustrative of the operation of another exemplary method, and the operation of another exemplary computer program, in accordance with the exemplary embodiments of this invention.

DETAILED DESCRIPTION

1 Introduction

1.1 Fully Homomorphic Encryption

A fully homomorphic encryption scheme may be considered as one that allows the computation of arbitrary functions over encrypted data without requiring the use of a decryption key.

There has existed an open problem of constructing a fully homomorphic encryption scheme. This notion, originally called a privacy homomorphism, was introduced by Rivest, Adleman and Dertouzous (R. Rivest, L. Adleman, and M. Dertouzous. On data banks and privacy homomorphisms. In Foundations of Secure Computation, pages 169-180, 1978) shortly after the development of RSA by Rivest, Shamir, and Adleman (R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. In Comm. of the ACM, 21:2, pages 120-126, 1978). Basic RSA is a multiplicatively homomorphic encryption scheme, i.e., given RSA public key pk=(N,e) and ciphertexts {Ï i âÏ i e mod N}, one can efficiently compute Î i Ï i =(Î i Ï i ) e mod N, a ciphertext that encrypts the product of the original plaintexts. One may assume that it was RSA's multiplicative homomorphism, an accidental but useful property, that led Rivest et al. to ask a natural question: What can one do with an encryption scheme that is fully homomorphic: a scheme Îµ with an efficient algorithm Evaluate, that, for any valid public key pk, any circuit C (not just a circuit consisting of multiplication gates as in RSA), and any ciphertexts Ï i âEncrypt Îµ (pk,Ï i ), outputs

ÏâEvaluate Îµ (pk,C,Ï i , . . . ,Ï t ),

a valid encryption of C(Ï 1 , . . . ,Ï 1 ) under pk? Their answer: one can arbitrarily compute on encrypted data, i.e., one can process encrypted data (query it, write into it, do anything to it that can be efficiently expressed as a circuit) without the decryption key. As an application, they suggested private data banks. A user can store its data on an untrusted server in encrypted form. Later, the user can send a query on the data to the server, whereupon the server can express this query as a circuit to be applied to the data, and use the Evaluate Îµ algorithm to construct an encrypted response to the user's query, which the user then decrypts. One would obviously want the server's response here to be more concise than the trivial solution, in which the server just sends all of the encrypted data back to the user to process on its own.

It is known that one can construct additively homomorphic encryption schemes from lattices or linear codes. The lattice-based scheme and the Reed-Solomon-code-based scheme allow multiplications, though with exponential expansion in ciphertext size. Ciphertexts implicitly contain an âerrorâ that grows as ciphertexts are added together. Thus, ciphertexts output by Evaluate do not have the same distribution as ciphertexts output by Encrypt, and at some point the error may become large enough to cause incorrect decryption. For this reason, the homomorphism is sometimes referred to as a âpseudohomomorphismâ or a âbounded homomorphismâ.

There are schemes that use a singly homomorphic encryption scheme to construct a scheme that can perform more complicated homomorphic operations (T. Sander, A. Young, and M. Yung. Non-interactive cryptocomputing for NC1. In Proc. of FOCS '99, pages 554-567, 1999, and Y. Ishai and A. Paskin. Evaluating Branching Programs on Encrypted Data. In Proc. of TCC '07. Sanders, Young and Yung (SYY) show that one can use a circuit-private additively homomorphic encryption scheme to construct a circuit-private scheme that can handle arbitrary circuits, where the ciphertext size increases exponentially with the depth of the circuit. Their scheme may, therefore, feasibly evaluate NC1 circuits. Ishai and Paskin show how to evaluate branching programs, and with much smaller ciphertexts than SYY. In their scheme Evaluate outputs a ciphertext whose length is proportional to the length of the branching program. This remains true even if the size of the branching program is very large, e.g., super-polynomial. However, the computational complexity of their scheme is proportional to the size.</di

CROSS-REFERENCE TO RELATED APPLICATIONS

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

This invention was made with Government support under contract no. FA8750-11-C-0096 awarded by Defense Advanced Research Projects Agency (DARPA). The Government has certain rights to this invention.

TECHNICAL FIELD

BACKGROUND

BRIEF SUMMARY

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

The foregoing and other aspects of embodiments of this invention are made more evident in the following Detailed Description, when read in conjunction with the attached Drawing Figures, wherein:

FIG. 1 illustrates a block diagram of an exemplary system in which various exemplary embodiments of the invention may be implemented;

DETAILED DESCRIPTION

1 Introduction

1.1 Fully Homomorphic Encryption

A fully homomorphic encryption scheme may be considered as one that allows the computation of arbitrary functions over encrypted data without requiring the use of a decryption key.

ÏâEvaluate Îµ (pk,C,Ï i , . . . ,Ï t ),

In more detail, Ishai and Paskin use a âleveledâ approach to evaluate a branching program. A (deterministic) branching program (BP) P is defined by a DAG from a distinguished initial node in which each nonterminal node has two outgoing edges labeled 0 and 1, and where the terminal nodes also have labels.

Fully homomorphic encryption (FHE) [21, 8] allows a computationally powerful worker to receive encrypted data and perform arbitrarily-complex dynamically-chosen computations on that data while it remains encrypted, despite not having the secret decryption key. Until recently, all FHE schemes [8, 6, 22, 10, 5, 4] followed the same blueprint, the one laid out in Gentry's original construction[8, 7].

The first step in Gentry's blueprint is to construct a somewhat homomorphic encryption (SWHE) scheme, namely an encryption scheme capable of evaluating âlow-degreeâ polynomials homomorphically. Starting with Gentry's original construction based on ideal lattices [8], there are by now a number of such schemes in the literature [6, 22, 10, 5, 4, 14], all of which are based on lattices (either directly or implicitly). The ciphertexts in all these schemes are ânoisyâ, with a noise that grows slightly during homomorphic addition, and explosively during homomorphic multiplication, and hence, the limitation of low-degree polynomials.

To obtain FHE, Gentry provided a remarkable bootstrapping theorem which states that given a SWHE scheme that can evaluate its own decryption function (plus an additional operation), one can transform it into a âleveledâ FHE scheme. (In a âleveledâ FHE scheme, the parameters of the scheme may depend on the depth of the circuits that the scheme can evaluate (but not on their size). One can obtain a âpureâ FHE scheme (with a constant-size public key) from a leveled FHE scheme by assuming âcircular securityâânamely, that it is safe to encrypt the leveled FHE secret key under its own public key. We will often omit the term âleveledâ in this work.) Bootstrapping ârefreshesâ a ciphertext by running the decryption function on it homornorphically, using an encrypted secret key (given in the public key or obtainable therefrom), resulting in reduced noise (a reduction of noise generated by the operations).

Until recently, SWHE schemes tended to be incapable of evaluating their own decryption circuits (plus some) without significant modifications. (We discuss recent exceptions [9, 3] below.) Thus, the final step is to squash the decryption circuit of the SWHE scheme, namely transform the scheme into one with the same homomorphic capacity but a decryption circuit that is simple enough to allow bootstrapping. Gentry [8] showed how to do this by adding a âhintâânamely, a large set with a secret sparse subset that sums to the original secret keyâto the public key and relying on a âsparse subset sumâ assumption.

A bootstrappable encryption scheme is one wherein the encryption scheme can evaluate its own decryption circuit (e.g., slightly augmented versions of its own decryption circuit). Gentry showed that if the decryption circuit of a SWHE scheme is shallow enough, in particular, if it is shallow enough to be evaluated homomorphically by the somewhat homomorphic scheme itself (a self-referential property), then this somewhat homomorphic scheme becomes âbootstrappableâ, and can be used to construct a fully homomorphic scheme that can evaluate circuits of arbitrary depth.

It may be useful to provide a physical analogy as an aid in visualizing the concept of fully homomorphic encryption. Assume that the owner of a jewelry store wants her employees to assemble raw precious materials (diamonds, gold, etc.) into finished products, but is worried about theft. The owner addresses the problem by constructing glove boxes for which only the owner has the key (analogous to the secret key in an encryption scheme), and puts the raw materials inside the glove boxes (analogous to an encryption operation). Using the gloves, an employee can manipulate the items inside the box. Moreover, an employee can put things inside the box, e.g., a soldering iron to use on the raw materials, although the employee cannot take anything out. Also, the box is transparent, so that an employee can see what he is doing within the box. In this analogy, encryption means that the employee is unable to take something out of the box, not that he is unable to see it. After the employee is finished, the jewelry store owner can recover the finished product at her leisure by using her key. This analogy is inadequate in the sense that the glove box might become quite cluttered, whereas in the fully homomorphic encryption scheme only the final product need remain. In other words, to improve the analogy, imagine that the employee has some way to make any item in the glove box (of his choosing) disappear, even though he still cannot extract the item.

Now imagine that the glove boxes are defective; after an employee uses the gloves for one minute, the gloves stiffen and become unusable (analogous to the accumulation of noise). Unfortunately, even the fastest employee cannot assemble some of the more intricate designs in under a minute. To solve this problem the jewelry store owner gives to an employee that is assembling an intricate design a glove box containing the raw materials, but also several additional glove boxes. Each of these additional glove boxes holds a copy of the master key. To assemble the intricate design, the employee manipulates the materials in box # 1 until the gloves stiffen. Then, he places box # 1 inside box #

2 , where the latter box already contains a master key. Using the gloves for box #

2 , he opens box # 1 with the master key, extracts the partially assembled item, and continues the assembly within box #

2 until its gloves stiffen. He then places box #

2 inside box #

3 , and so on. The employee finally finishes his assembly inside of box # n. Of course, this procedure assumes that the employee can open box #i within box #(i+1), and have time to some progress on the assembly, all before the gloves of box #(i+1) stiffen. This is analogous to the requirement for a bootstrappable encryption scheme Îµ, that the complexity of Îµ's (augmented) decryption circuit is less than what Îµ can homomorphically evaluate.

The foregoing analogy assumes that it is safe to use a single master key that opens all boxes. However, perhaps an employee could use the gloves for box #

2 , together with master key inside that box, to open the box from the inside, extract the key, and use it to open box # 1 and remove the jewels. However, this situation can be avoided by using distinct keys for the boxes, and placing the key for box # 1 inside box #

2 , the key for box #

2 inside box #

3 , and so on. This is analogous to the question of whether the encryption scheme is KDM-secure.

One non-limiting application of fully homomorphic encryption is in a two-party setting. A simple example is making encrypted queries to search engines. Referring to FIG. 2 , to perform an encrypted search a party (requestor 1 ) generates a public key pk for the fully homomorphic encryption scheme, and generates ciphertexts Ï 1 , . . . , Ï t that encrypt the query Ï 1 , . . . , Ï t under pk. (For example, each Ï i could be a single bit of the query.) Now, let the circuit C express a search engine server 2 search function for data stored in storage 3 . The server 2 sets Ï i * âEvaluate(pk, C i , Ï 1 , . . . , Ï i ), where C i is the sub-circuit of C that computes the ith bit of the output. Note that, in practice, the evaluation of C i * and C j * may share intermediate results, in which case it may be needlessly inefficient to run independent instances of the Evaluate algorithm. The server 2 sends these ciphertexts to the requestor 1 . It is known that, by the correctness requirement, Decrypt(sk,Ï i * )=C i (Ï 1 , . . . , Ï t ). These latter values constitute precisely the answer to the query, which is recoverable through decryption.

As another non-limiting application, the exemplary embodiments of this invention enable searching over encrypted data. In this scenario, assume that the requestor 1 stores files on the server 2 (e.g., on the Internet), so that the requestor 1 can conveniently access these files without needing the requestor's computer. However, the requestor encrypts the files, otherwise the server 2 could potentially read the private data. Let bits Ï 1 , . . . , Ï t represent the files, which are encrypted in the ciphertexts Ï 1 , . . . , Ï t . Assume then that the requestor 1 later wants to download all encrypted files that satisfy a query, e.g., all files containing the word âhomomorphicâ within 5 words of âencryptionâ, but not the word âevotingâ. The requestor 1 sends the query to the server 2 , which expresses it as a circuit C. The server sets Ï i * âEvaluate(pk, C i , Ï 1 , . . . , Ï t ) and sends these ciphertexts to the requestor 1 . who decrypts the returned ciphertexts to recover C(Ï 1 , . . . ,Ï t )), the (bits of the) files that satisfy the query.

Note that in this application, as in the encrypted search application, the requestor preferably provides an upper bound on the number of bits that the response should have, and the encrypted response from the server 2 is padded or truncated to meet the upper bound.

Fully homomorphic encryption has numerous applications. For example, it enables private search engine queries where the search engine responds to a query without knowledge of the query, i.e., a search engine can provide a succinct encrypted answer to an encrypted (Boolean) query without knowing what the query was. It also enables searching on encrypted data; one can store encrypted data on a remote server and later have the server retrieve only files that (when decrypted) satisfy some Boolean constraint, even though the server cannot decrypt the files on its own. More broadly, fully homomorphic encryption improves the efficiency of secure multiparty computation.

1.2 Efficiency of FHE

The efficiency of fully homomorphic encryption has been a (perhaps, the) big question following its invention. In this paper, we are concerned with the per-gate computation overhead of the FHE scheme, defined as the ratio between the time it takes to compute a circuit homomorphically to the time it takes to compute it in the clear. (Other measures of efficiency, such ciphertext/key size and encryption/decryption time, are also important. In fact, the schemes we present in this paper are very efficient in these aspects (as are the schemes in [9, 3]).) Unfortunately, FHE schemes that follow Gentry's blueprint (some of which have actually been implemented [10, 5]) have fairly poor performanceâtheir per-gate computation overhead is p(Î»), a large polynomial in the security parameter. In fact, we would like to argue that this penalty in performance is somewhat inherent for schemes that follow this blueprint.

First, the complexity of (known approaches to) bootstrapping is inherently at least the complexity of decryption times the bit-length of the individual ciphertexts that are used to encrypt the bits of the secret key. The reason is that bootstrapping involves evaluating the decryption circuit homomorphicallyâthat is, in the decryption circuit, each secret-key bit is replaced by a (large) ciphertext that encrypts that bitâand both the complexity of decryption and the ciphertext lengths must each be Î©(Î»).

Second, the undesirable properties of known SWHE schemes conspire to ensure that the real cost of bootstrapping for FHE schemes that follow this blueprint is actually much worse than quadratic. Known FHE schemes start with a SWHE scheme that can evaluate polynomials of degree D (multiplicative depth log D) securely only if the underlying lattice problem is hard to 2 D -approximate. To achieve hardness against 2 Î» time adversaries, the lattice must have dimension Î©(DÂ·Î»). This is because we have lattice algorithms in n dimensions that compute 2 n/Î» -approximations of short vectors in time

. Moreover, the coefficients of the vectors used in the scheme have bit length Î©(D) to allow the ciphertext noise room to expand to 2 D . Therefore, the size of âfreshâ ciphertexts (e.g., those that encrypt the bits of the secret key) is {tilde over (Î©)}(D 2 Â·Î»). Since the SWHE scheme must be âbootstrappableââi.e., capable of evaluating its own decryption functionâD must exceed the degree of the decryption function. Typically, the degree of the decryption function is Î©(Î»). Thus, overall, âfreshâ ciphertexts have size {tilde over (Î©)}(Î» 3 ). So, the real cost of bootstrappingâeven if we optimistically assume that the âstaleâ ciphertext that needs to be refreshed can be decrypted in only Î(Î»)-timeâis {tilde over (Î©)}(Î» 4 ).

The analysis above ignores a nice optimization by StehlÃ© and Steinfeld [24], which so far has not been useful in practice, that uses Chernoff bounds to asymptotically reduce the decryption degree down to O(â{square root over (Î»)}). With this optimization, the per-gate computation of FHE schemes that follow the blueprint is {tilde over (Î©)}(Î» 3 ). (We note that bootstrapping lazilyâi.e., applying the refresh procedure only at a 1/L fraction of the circuit levels for L>1âcannot reduce the per-gate computation further by more than a logarithmic factor for schemes that follow this blueprint, since these SWHE schemes can evaluate only log multiplicative depth before it becomes absolutely necessary to refreshâi.e., L=O(log Î»).)

1.3 Recent Deviations from Gentry's Blueprint, and the Hope for Better Efficiency

Recently, Gentry and Halevi [9], and Brakerski and Vaikuntanathan[3], independently found very different ways to construct FHE without using the squashing step, and thus without the sparse subset sum assumption. These schemes are the first major deviations from Gentry's blueprint for FHE. Surprisingly, Brakerski and Vaikuntanathan[3] showed how to base security entirely on LWE (for sub-exponential approximation factors), avoiding reliance on ideal lattices.

From an efficiency perspective, however, these results are not a clear win over previous schemes. Both of the schemes still rely on the problematic aspects of Gentry's blueprintânamely, bootstrapping and an SWHE scheme with the undesirable properties discussed above. Thus, their per-gate computation is still more than {tilde over (Î©)}(Î» 4 ). Nevertheless, the techniques introduced in these recent constructions are very interesting and useful to us. In particular, we use the tools and techniques introduced by Brakerski and Vaikuntanathan [3] in an essential way to achieve remarkable efficiency gains.

An important, somewhat orthogonal question is the strength of assumptions underlying FHE schemes. All the schemes so far rely on the hardness of short vector problems on lattices with a subexponential approximation factor. Can we base FHE on the hardness of finding a polynomial approximation?

1.4 Our Results and Techniques

We leverage Brakerski and Vaikuntanathan's techniques [3] to achieve asymptotically very efficient FHE schemes. Also, we base security on lattice problems with quasi-polynomial approximation factors. (All previous schemes relied on the hardness of problems with sub-exponential approximation factors.) In particular, we have the following theorem (informal):

Assuming Ring LWE for an approximation factor exponential in L, we have a leveled FHE scheme that can evaluate L-level arithmetic circuits without using bootstrapping. The scheme has {tilde over (Î©)}(Î»Â·L 3 ) per-gate computation (namely, quasi-linear in the security parameter). Alternatively, assuming Ring LWE is hard for quasi-polynomial factors, we have a leveled FHE scheme that uses bootstrapping as an optimization, where the per-gate computation (which includes the bootstrapping procedure) is {tilde over (Î©)}(Î» 2 ), independent of L.

We can alternatively base security on LWE, albeit with worse performance. We now sketch our main idea for boosting efficiency.

In the BV scheme [3], like ours, a ciphertext vector cÎµR n (where R is a ring, and n is the âdimensionâ of the vector) that encrypts a message m satisfies the decryption formula m=[[

c,s

] q ] 2 , where sÎµR n is the secret key vector, q is an odd modulus, and [â¢] q denotes reduction into the range (âq/2, q/2). This is an abstract scheme that can be instantiated with either LWE or Ring LWEâin the LWE instantiation, R is the ring of integers mod q and n is a large dimension, whereas in the Ring LWE instantiation, R is the ring of polynomials over integers mod q and an irreducible f(x), and the dimension n=2

We will call [

c,s

] q the noise associated to ciphertext c under key s. Decryption succeeds as long as the magnitude of the noise stays smaller than q/2. Homomorphic addition and multiplication increase the noise in the ciphertext. Addition of two ciphertexts with noise at most B results in a ciphertext with noise at most 2B whereas multiplication results in a noise as large as B 2 . (The noise after multiplication is in fact a bit larger than B 2 due to the additional noise from the BV âre-linearizationâ process. For the purposes of this exposition, it is best to ignore this minor detail.) We will describe a noise-management technique that keeps the noise in check by reducing it after homomorphic operations, without bootstrapping.

The key technical tool we use for noise management is the âmodulus switchingâ technique developed by Brakerski and Vaikuntanathan [3]. Jumping ahead, we note that while they use modulus switching in âone shotâ to obtain a small ciphertext (to which they then apply Gentry's bootstrapping procedure), we will use it (iteratively, gradually) to keep the noise level essentially constant, while stingily sacrificing modulus size and gradually sacrificing the remaining homomorphic capacity of the scheme.

1.5 Modulus Switching

The essence of the modulus-switching technique is captured in the following lemma. In words, the lemma says that an evaluator, who does not know the secret key s but instead only knows a bound on its length, can transform a ciphertext c modulo q into a different ciphertext modulo p while preserving correctnessânamely, [

câ²,s

] p =[

c,s

] q mod 2. The transformation from c to câ² involves simply scaling by (p/q) and rounding appropriately! Most interestingly, if s is short and p is sufficiently smaller than q, the ânoiseâ in the ciphertext actually decreasesânamely, |[

câ²,s

] p |<|[

c,s

] q |.

Lemma 1 Let p and q be two odd moduli, and let c be an integer vector. Define câ² to be the integer vector closest to (p/q)Â·c such that câ²= c mod 2. Then, for any s with |[

c,s

] q |<q/2â(q/p)Â·l 1 (s), we have

[

câ²,s

] p =[

c,s

] q mod 2 and

câ²,s

] p |<( p/q )Â·|[

c,s

] q |+l 1 ( s )

where l 1 (s) is the l 1 -norm of s.

Proof. For some integer k, we have [

c,s

] q =

c,s

âkg. For the same k, let e p =

câ²,s

<img id="CUSTOM-CHARACTER-00029" he="3.22mm" wi="1.10mm" file="US09716590-20170725-P00003.TIF" alt="Figure US09716590-20170725-P00003" img-content="character" img-format="tif" orientation="portrait" inline="n

CLAIMS

Claims ( 25 )

What is claimed is:

1. A non-transitory computer-readable storage medium for secure multiparty computation and communication and storing program instructions, execution of the program instructions resulting in operations comprising:

receiving, over a network and as part of a secure multiparty computation and communication process, at a server computer system a query from a requestor computer system;

performing, as part of the secure multiparty computation and communication process, a fully homomorphic encryption scheme allowing the server computer system to perform homomorphic operations on input ciphertexts without decrypting the ciphertexts and based on the query, to produce one or more results that when decrypted are an answer to the query, wherein performing the fully homomorphic encryption scheme comprises:

accessing, at the server computer system and from a memory of the server computer system, a plurality of input ciphertexts, where each of the input ciphertexts comprises data encrypted in accordance with the fully homomorphic encryption scheme, where the fully homomorphic encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two given ciphertexts and uses the public key to perform at least one operation on the at least two given ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of a magnitude of noise for a provided ciphertext while reducing a modulus of the provided ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming the provided ciphertext c modulo q into another ciphertext câ² modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the fully homomorphic encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the fully homomorphic encryption scheme;

determining, by the server computer system, from the plurality of input ciphertexts the one or more results corresponding to and satisfying the query by performing homomorphic operations using at least the plurality of input ciphertexts at least by:

performing operations on ciphertexts according to a circuit that corresponds to the query and the evaluation of which produces the one or more results that satisfy the query, wherein the operations use the at least one operation function to obtain a ciphertext result, and wherein at least some of the operations involve the plurality of input ciphertexts;

reducing a noise level of the ciphertext result by using the refresh function; and

determining the one or more results of the evaluation of the circuit at least by evaluating the circuit and iterating the performing the operations and the reducing the noise level multiple times during the evaluation of the circuit; and

completing the secure multiparty computation and communication process at least by sending by the server computer system and over the network the one or more results of the evaluation of the circuit to the requestor computer system.

2. The non-transitory computer-readable storage medium of claim 1 , where application of the refresh function to the provided ciphertext also reduces a range of coefficients for an output of the refresh function, relative to a range of coefficients for the provided ciphertext.

3. The non-transitory computer-readable storage medium of claim 1 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being performed the refresh function is applied to an output of the multiplication.

4. The non-transitory computer-readable storage medium of claim 1 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being desired the refresh function is applied to at least one input of the multiplication.

5. The non-transitory computer-readable storage medium of claim 1 , where the fully homomorphic encryption scheme enables evaluation of a polynomial depth circuit of multiplications and wherein the circuit that corresponds to the query comprises the polynomial depth circuit of multiplications.

6. A method for secure multiparty computation and communication, comprising:

receiving, over a network and as part of a secure multiparty computation and communication process, at a server computer system a query from a requestor computer system;

accessing, at the server computer system and from a memory of the server computer system, a plurality of input ciphertexts, where each of the input ciphertexts comprises data encrypted in accordance with the fully homomorphic encryption scheme, where the encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two given ciphertexts and uses the public key to perform at least one operation on the at least two given ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of a magnitude of noise for a provided ciphertext while reducing a modulus of the provided ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming the provided ciphertext c modulo q to another ciphertext câ² modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the fully homomorphic encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the fully homomorphic encryption scheme;

reducing a noise level of the ciphertext result by using the refresh function; and

7. The method of claim 6 , where application of the refresh function to the provided ciphertext also reduces a range of coefficients for an output of the refresh function, relative to a range of coefficients for the provided for the provided ciphertext.

8. The method of claim 6 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being performed the refresh function is applied to an output of the multiplication.

9. The method of claim 6 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being desired the refresh function is applied to at least one input of the multiplication.

10. The method of claim 6 , where the encryption scheme enables evaluation of a polynomial depth circuit of multiplications and wherein the circuit that corresponds to the query comprises the polynomial depth circuit of multiplications.

11. An apparatus for secure multiparty computation and communication, comprising:

a memory configured to store a plurality of input ciphertexts and program code,

at least one processor of a server computer system configured to cause the server computer system, in response to execution of the program code, to perform the following:

receive, over a network and as part of a secure multiparty computation and communication process, at the server computer system a query from a requestor computer system;

perform, as part of the secure multiparty computation and communication process, a fully homomorphic encryption scheme allowing the server computer system to perform homomorphic operations on the input ciphertexts without decrypting the ciphertexts and based on the query, to produce one or more results that when decrypted are an answer to the query, wherein performing the fully homomorphic encryption scheme comprises:

access at the server computer system the input ciphertexts from the memory, where each of the input ciphertexts comprises data encrypted in accordance with an encryption scheme, where the encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two given ciphertexts and uses the public key to perform at least one operation on the at least two given ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of a magnitude of noise for a provided ciphertext while reducing a modulus of the provided ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming the provided ciphertext c modulo q into another ciphertext câ² modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme; and

determine from the plurality of input ciphertexts the one or more results corresponding to and satisfying the query by perform homomorphic operations using at least the plurality of input ciphertexts at least by:

reducing a noise level of the ciphertext result by using the refresh function; and

complete the secure multiparty computation and communication process at least by sending by the server computer system and over the network the one or more results of the evaluation of the circuit to the requestor computer system.

12. The apparatus of claim 11 , where application of the refresh function to the provided ciphertext also reduces a range of coefficients for an output of the refresh function, relative to a range of coefficients for the provided ciphertext.

13. The apparatus of claim 11 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being performed the refresh function is applied to an output of the multiplication.

14. The apparatus of claim 11 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being desired the refresh function is applied to at least one input of the multiplication.

15. The apparatus of claim 11 , where the fully homomorphic encryption scheme enables evaluation of a polynomial depth circuit of multiplications and wherein the circuit that corresponds to the query comprises the polynomial depth circuit of multiplications.

16. A method for secure multiparty computation and communication comprising:

receiving, over a network and as part of a secure multiparty computation and communication process, at a server computer system a query from a requestor computer system;

accessing, at the server computer system and from a memory of the server computer system, a plurality of input ciphertexts, where each of the plurality of ciphertexts comprises data encrypted in accordance with the fully homomorphic encryption scheme, where the fully homomorphic encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two given ciphertexts and uses the public key to perform at least one operation on the at least two given ciphertexts and obtain a resulting ciphertext, where the refresh function operates to enable slow growth of a magnitude of noise for a provided ciphertext while maintaining a modulus of the provided ciphertext constant without using the secret key, where the fully homomorphic encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the fully homomorphic encryption scheme;

reducing a noise level of the ciphertext result by using the refresh function; and

determining the one or more results of evaluation of the circuit at least by evaluating the circuit and iterating the performing the operations and the reducing the noise level multiple times during the evaluation of the circuit; and

17. The method of claim 16 , where the modulus of the provided ciphertext is maintained at a value of 1.

18. The method of claim 16 , where the magnitude of noise for the provided ciphertext is represented as a fractional part of coefficients for the ciphertext.

19. The method of claim 16 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being performed the refresh function is applied to an output of the multiplication.

20. The method of claim 16 , where the fully homomorphic encryption scheme enables evaluation of a polynomial depth circuit of multiplications and wherein the circuit that corresponds to the query comprises the polynomial depth circuit of multiplications.

21. An apparatus for secure multiparty computation and communication, comprising:

one or more processors;

a memory comprising a plurality of input ciphertexts and program code,

wherein the one or more processors are configured, in response to execution of the program code, to cause the computer system to perform at least the following:

receiving, over a network and as part of a secure multiparty computation and communication process, at a server computer system a query from a requestor computer system;

performing, as part of the secure multiparty computation and communication process, a fully homomorphic encryption scheme allowing the server computer system to perform homomorphic operations on the input ciphertexts without decrypting the ciphertexts and based on the query, to produce one or more results that when decrypted are an answer to the query, wherein performing the fully homomorphic encryption scheme comprises:

accessing, by the server computer system and from the memory, the input ciphertexts, where each of the plurality of ciphertexts comprises data encrypted in accordance with the fully homomorphic encryption scheme, where the fully homomorphic encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two given ciphertexts and uses the public key to perform at least one operation on the at least two given ciphertexts and obtain a resulting ciphertext, where the refresh function operates to enable slow growth of a magnitude of noise for a provided ciphertext while maintaining a modulus of the provided ciphertext constant without using the secret key, where the fully homomorphic encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the fully homomorphic encryption scheme;

reducing a noise level of the ciphertext result by using the refresh function; and

completing the secure multiparty computation and communication process by at least by sending by the server computer system and over the network the one or more results of the evaluation of the circuit to the requestor computer system.

22. The apparatus of claim 21 , where the modulus of the provided ciphertext is maintained at a value of 1.

23. The apparatus of claim 21 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being performed the refresh function is applied to an output of the multiplication.

24. The apparatus of claim 21 , where the fully homomorphic encryption scheme enables evaluation of a polynomial depth circuit of multiplications and wherein the circuit that corresponds to the query comprises the polynomial depth circuit of multiplications.

25. The apparatus of claim 21 , where the magnitude of noise for the provided ciphertext is represented as a fractional part of coefficients for the ciphertext.

US14/740,354

2011-04-29

2015-06-16

Fully homomorphic encryption

Expired - Fee Related

US9716590B2

( en )

Priority Applications (1)

Application Number

Priority Date

Filing Date

Title

US14/740,354

US9716590B2

( en )

2011-04-29

2015-06-16

Fully homomorphic encryption

Applications Claiming Priority (3)

Application Number

Priority Date

Filing Date

Title

US201161481048P

2011-04-29

US13/458,518

US9083526B2

( en )

2011-04-29

2012-04-27

Fully homomorphic encryption

US14/740,354

US9716590B2

( en )

2011-04-29

2015-06-16

Fully homomorphic encryption

Related Parent Applications (1)

Application Number

Title

Priority Date

Filing Date

US13/458,518

Continuation

US9083526B2

( en )

2011-04-29

2012-04-27

Fully homomorphic encryption

Publications (2)

Publication Number

Publication Date

US20150358153A1

US20150358153A1 ( en )

2015-12-10

US9716590B2

true

US9716590B2 ( en )

2017-07-25

Family

ID=47072788

Family Applications (2)

Application Number

Title

Priority Date

Filing Date

US13/458,518

Expired - Fee Related

US9083526B2

( en )

2011-04-29

2012-04-27

Fully homomorphic encryption

US14/740,354

Expired - Fee Related

US9716590B2

( en )

2011-04-29

2015-06-16

Fully homomorphic encryption

Family Applications Before (1)

Application Number

Title

Priority Date

Filing Date

US13/458,518

Expired - Fee Related

US9083526B2

( en )

2011-04-29

2012-04-27

Fully homomorphic encryption

Country Status (2)

Country

Link

( 2 )

US9083526B2

( en )

( 1 )

WO2012149395A1

( en )

Cited By (29)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20150365239A1

( en )

2013-01-29

2015-12-17

Nec Europe Ltd.

Method and system for providing encrypted data for searching of information therein and a method and system for searching of information on encrypted data

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

US10341086B2

( en )

2013-01-29

2019-07-02

Nec Corporation

Method and system for providing encrypted data for searching of information therein and a method and system for searching of information on encrypted data

US20190363872A1

( en )

2017-02-08

2019-11-28

Crypto Lab Inc.

Method for processing dynamic data by fully homomorphic encryption method

US10581604B2

( en )

2017-10-17

2020-03-03

Comsats Institute Of Information Technology

Post-quantum cryptographic communication protocol

US10693628B2

( en )

2018-05-04

2020-06-23

International Business Machines Corporation

Enabling distance-based operations on data encrypted using a homomorphic encryption scheme with inefficient decryption

US10728227B2

( en )

2016-08-02

2020-07-28

X-Logos, LLC

Methods and systems for enhanced data-centric encryption systems using geometric algebra

US10728017B2

( en )

2017-11-03

2020-07-28

International Business Machines Corporation

Performing vector comparison operations in fully homomorphic encryption

US11070357B2

( en )

2019-10-17

2021-07-20

Raytheon Company

Techniques for privacy-preserving data processing across multiple computing nodes

US20220006629A1

( en )

2017-01-20

2022-01-06

Enveil, Inc.

Secure Analytics Using Term Generation and Homomorphic Encryption

US11336441B2

( en )

2017-11-07

2022-05-17

Nippon Telegraph And Telephone Corporation

Communication terminal, server apparatus, and program

US11341281B2

( en )

2018-09-14

2022-05-24

International Business Machines Corporation

Providing differential privacy in an untrusted environment

US11436340B2

( en )

2019-06-24

2022-09-06

Bank Of America Corporation

Encrypted device identification stream generator for secure interaction authentication

US11483128B2

( en )

2020-05-29

2022-10-25

Samsung Electronics Co., Ltd.

Homomorphic encryption device and ciphertext arithmetic method thereof

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

US20230126672A1

( en )

2021-10-27

2023-04-27

Jpmorgan Chase Bank, N.A.

Systems and methods for mixed precision machine learning with fully homomorphic encryption

US20230188320A1

( en )

2021-12-09

2023-06-15

Electronics And Telecommunications Research Institute

Computing apparatus and method of integrating different homomorphic operations in homomorphic encryption

US11683151B2

( en )

2020-09-17

2023-06-20

Algemetric, Inc.

Methods and systems for distributed computation within a fully homomorphic encryption scheme using p-adic numbers

US20230244798A1

( en )

2018-10-25

2023-08-03

Enveil, Inc.

Systems and Methods of Performing Computation Operations Using Secure Enclaves

US11764943B2

( en )

2020-08-10

2023-09-19

Algemetric, Inc.

Methods and systems for somewhat homomorphic encryption and key updates based on geometric algebra for distributed ledger/blockchain technology

US11818243B2

( en )

2020-09-23

2023-11-14

Samsung Electronics Co., Ltd.

Scenario-based encryption device and operating method thereof

US11902413B2

( en )

2017-01-20

2024-02-13

Enveil, Inc.

Secure machine learning analytics using homomorphic encryption

US20250167976A1

( en )

2023-11-21

2025-05-22

Katholieke Universiteit Leuven

Method for accelerating bootstrapping in a cryptographic application

US12380227B2

( en )

2021-12-01

2025-08-05

Samsung Electronics Co., Ltd.

Encryption computing system and encryption method

US12542650B2

( en )

2023-10-03

2026-02-03

Bank Of America Corporation

Artificial intelligence (AI) based cloud architecture segmentation leveraging homomorphic encryption

US12609808B2

( en )

2021-10-20

2026-04-21

Axell Corporation

Encryption processing apparatus and encryption processing method

US12625977B2

( en )

2018-10-25

2026-05-12

Enveil, Inc.

Systems and methods of performing machine learning operations using secure enclaves

US12634113B2

( en )

2021-01-18

2026-05-19

Seoul National University R&Db Foundation

Method for processing dynamic data based on homomorphic encryption which carries out unlimited arithmetic operations without bootstrapping and reencryption of control data

Families Citing this family (123)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US8972742B2

( en )

2009-09-04

2015-03-03

Gradiant

System for secure image recognition

US8539220B2

( en )

2010-02-26

2013-09-17

Microsoft Corporation

Secure computation using a server module

JP5790287B2

( en )

2011-08-12

2015-10-07

ã½ãã¼æ ªå¼ä¼ç¤¾

Information processing apparatus, information processing method, program, and recording medium

WO2013038698A1

( en )

2011-09-14

2013-03-21

ç¬ç«è¡æ¿æ³äººç£æ¥æè¡ç·åç ç©¶æ

Search system, search method, and program

US9197613B2

( en )

2011-12-20

2015-11-24

Industrial Technology Research Institute

Document processing method and system

US9281941B2

( en )

2012-02-17

2016-03-08

International Business Machines Corporation

Homomorphic evaluation including key switching, modulus switching, and dynamic noise management

WO2014113132A2

( en )

2012-11-16

2014-07-24

Raytheon Bbn Technologies Corp.

Method for secure symbol comparison

WO2014109828A2

( en )

2012-11-16

2014-07-17

Raytheon Bbn Technologies Corp.

Method for secure substring search

US9306738B2

( en )

2012-12-21

2016-04-05

Microsoft Technology Licensing, Llc

Managed secure computations on encrypted data

US9229687B2

( en )

2013-09-05

2016-01-05

Xerox Corporation

Private two-party computation using partially homomorphic encryption

EP2860905A1

( en )

2013-10-09

2015-04-15

Thomson Licensing

Method for ciphering a message via a keyed homomorphic encryption function, corresponding electronic device and computer program product

US9313022B2

( en )

2013-12-27

2016-04-12

Xerox Corporation

Homomorphic cryptography modeling in support of privacy policies

US10075288B1

( en )

2014-02-28

2018-09-11

The Governing Council Of The University Of Toronto

Systems, devices, and processes for homomorphic encryption

US10171230B2

( en )

2014-02-28

2019-01-01

Empire Technology Development Llc

Homomorphic encryption scheme

JP6273951B2

( en )

2014-03-24

2018-02-07

å¯å£«éæ ªå¼ä¼ç¤¾

ENCRYPTION DEVICE, ENCRYPTION METHOD, INFORMATION PROCESSING DEVICE, AND ENCRYPTION SYSTEM

KR102251697B1

( en )

2014-04-23

2021-05-14

ì¼ì±ì ìì£¼ìíì¬

Encryption apparatus, method for encryption and computer-readable recording medium

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

US9749128B2

( en )

2014-05-15

2017-08-29

Xerox Corporation

Compact fuzzy private matching using a fully-homomorphic encryption scheme

US9819650B2

( en )

2014-07-22

2017-11-14

Nanthealth, Inc.

Homomorphic encryption in a healthcare network environment, system and methods

CN105447361B

( en )

2014-08-27

2018-08-21

åä¸ºææ¯æéå¬å¸

Method, terminal and the server of encryption and similarity measurement

WO2016112954A1

( en )

2015-01-12

2016-07-21

Nec Europe Ltd.

Method and system for providing encrypted data

US10594472B2

( en )

2015-03-09

2020-03-17

Jintai Ding

Hybrid fully homomorphic encryption (F.H.E.) systems

US10630686B2

( en )

2015-03-12

2020-04-21

Fornetix Llc

Systems and methods for organizing devices in a policy hierarchy

US9967289B2

( en )

2015-03-12

2018-05-08

Fornetix Llc

Client services for applied key management systems and processes

US10560440B2

( en )

2015-03-12

2020-02-11

Fornetix Llc

Server-client PKI for applied key management system and process

US10965459B2

( en )

2015-03-13

2021-03-30

Fornetix Llc

Server-client key escrow for applied key management system and process

WO2016173646A1

( en )

2015-04-29

2016-11-03

Nec Europe Ltd.

Method and system for providing homomorphically encrypted data on a client

US9813234B2

( en )

2015-05-11

2017-11-07

The United States of America, as represented by the Secretery of the Air Force

Transferable multiparty computation

WO2016195552A1

( en )

2015-06-02

2016-12-08

Telefonaktiebolaget Lm Ericsson (Publ)

Method and encryption node for encrypting message

US9742556B2

( en )

2015-08-25

2017-08-22

International Business Machines Corporation

Comparison and search operations of encrypted data

US9973334B2

( en )

2015-09-03

2018-05-15

Cisco Technology, Inc.

Homomorphically-created symmetric key

FR3042625B1

( en )

2015-10-14

2017-12-15

Commissariat Energie Atomique

METHOD OF CONFIDENTIAL INTERROGATION OF A DATABASED DATABASE

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

US10015007B2

( en )

2015-11-25

2018-07-03

International Business Machines Corporation

Performing efficient comparison operations on encrypted data

US10581812B2

( en )

2015-12-01

2020-03-03

Duality Technologies, Inc.

Device, system and method for fast and secure proxy re-encryption

US20170169425A1

( en )

2015-12-11

2017-06-15

Paypal, Inc.

Selective encryption of transactional information for different participants of an electronic transaction

US9900147B2

( en )

2015-12-18

2018-02-20

Microsoft Technology Licensing, Llc

Homomorphic encryption with optimized homomorphic operations

US9876636B2

( en )

2016-01-07

2018-01-23

Empire Technology Development Llc

Homomorphic public-key encryption scheme

US10348485B2

( en )

2016-02-26

2019-07-09

Fornetix Llc

Linking encryption key management with granular policy

US10860086B2

( en )

2016-02-26

2020-12-08

Fornetix Llc

Policy-enabled encryption keys having complex logical operations

US11063980B2

( en )

2016-02-26

2021-07-13

Fornetix Llc

System and method for associating encryption key management policy with device activity

US10917239B2

( en )

2016-02-26

2021-02-09

Fornetix Llc

Policy-enabled encryption keys having ephemeral policies

US10931653B2

( en )

2016-02-26

2021-02-23

Fornetix Llc

System and method for hierarchy manipulation in an encryption key management system

US10880281B2

( en )

2016-02-26

2020-12-29

Fornetix Llc

Structure of policies for evaluating key attributes of encryption keys

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

US10296709B2

( en )

2016-06-10

2019-05-21

Microsoft Technology Licensing, Llc

Privacy-preserving genomic prediction

US10833841B2

( en )

2016-07-13

2020-11-10

Sap Se

Leakage-free order-preserving encryption

US11176624B2

( en )

2016-08-29

2021-11-16

International Business Machines Corporation

Privacy-preserving smart metering

US9698986B1

( en )

2016-09-23

2017-07-04

ISARA Corporation

Generating shared secrets for lattice-based cryptographic protocols

CN106571905B

( en )

2016-11-02

2019-05-17

åäº¬é®çµå¤§å¦

A kind of numeric type data homomorphism Order Preserving Encryption Method

US10333695B2

( en )

2016-11-10

2019-06-25

Microsoft Technology Licensing, Llc

Rational number arithmetic in homomorphic encryption

US10812252B2

( en )

2017-01-09

2020-10-20

Microsoft Technology Licensing, Llc

String matching in encrypted data

US10873568B2

( en )

2017-01-20

2020-12-22

Enveil, Inc.

Secure analytics using homomorphic and injective format-preserving encryption and an encrypted analytics matrix

US10903976B2

( en )

2017-01-20

2021-01-26

Enveil, Inc.

End-to-end secure operations using a query matrix

US11507683B2

( en )

2017-01-20

2022-11-22

Enveil, Inc.

Query processing with adaptive risk decisioning

US10972251B2

( en )

2017-01-20

2021-04-06

Enveil, Inc.

Secure web browsing via homomorphic encryption

US10630655B2

( en )

2017-05-18

2020-04-21

Robert Bosch Gmbh

Post-quantum secure private stream aggregation

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

DE102017117899A1

( en )

2017-08-07

2019-02-07

Infineon Technologies Ag

Perform a cryptographic operation

DE102017219291A1

( en )

2017-10-27

2019-05-02

Robert Bosch Gmbh

Method for operating an automation system, automation system, computer system and control system therefor

IL256234A

( en )

2017-12-10

2018-01-31

Kipnis Aviad

Computation using somewhat homomorphic encryption

US10778409B2

( en )

2017-12-15

2020-09-15

Crypto Lab Inc.

Terminal device performing homomorphic encryption, server device processing ciphertext and methods thereof

EP3506547A1

( en )

2017-12-28

2019-07-03

Flytxt B.V.

Providing security against user collusion in data analytics using random group selection

US20190318118A1

( en )

2018-04-16

2019-10-17

International Business Machines Corporation

Fully homomorphic encryption — International Business Machines Corporation (US9716590B2)

Related documents