The Experts below are selected from a list of 2790 Experts worldwide ranked by ideXlab platform
Craig Gentry - One of the best experts on this subject based on the ideXlab platform.
-
leveled Fully Homomorphic Encryption without bootstrapping
Innovations in Theoretical Computer Science, 2014Co-Authors: Zvika Brakerski, Craig Gentry, Vinod VaikuntanathanAbstract:We present a novel approach to Fully Homomorphic Encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled, Fully Homomorphic Encryption schemes (capable of evaluating arbitrary polynomial-size circuits of a-priori bounded depth), without Gentry’s bootstrapping procedure. Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or Ring LWE (RLWE) problems that have 2 λ security against known attacks. We construct the following. (1) A leveled FHE scheme that can evaluate depth-L arithmetic circuits (composed of fan-in 2 gates) using O(λ. L3) per-gate computation, quasilinear in the security parameter. Security is based on RLWE for an approximation factor exponential in L. This construction does not use the bootstrapping procedure. (2) A leveled FHE scheme that can evaluate depth-L arithmetic circuits (composed of fan-in 2 gates) using O(λ2) per-gate computation, which is independent of L. Security is based on RLWE for quasipolynomial factors. This construction uses bootstrapping as an optimization. We obtain similar results for LWE, but with worse performance. All previous (leveled) FHE schemes required a per-gate computation of Ω(λ3.5), and all of them relied on subexponential hardness assumptions. We introduce a number of further optimizations to our scheme based on the Ring LWE assumption. As an example, for circuits of large width (e.g., where a constant fraction of levels have width Ω(λ)), we can reduce the per-gate computation of the bootstrapped version to O(λ), independent of L, by batching the bootstrapping operation. At the core of our construction is a new approach for managing the noise in lattice-based ciphertexts, significantly extending the techniques of Brakerski and Vaikuntanathan [2011b].
-
better bootstrapping in Fully Homomorphic Encryption
Public Key Cryptography, 2012Co-Authors: Craig Gentry, Shai Halevi, Nigel P. SmartAbstract:Gentry's bootstrapping technique is currently the only known method of obtaining a "pure" Fully Homomorphic Encryption (FHE) schemes, and it may offers performance advantages even in cases that do not require pure FHE (e.g., when using the noise-control technique of Brakerski-Gentry-Vaikuntanathan). The main bottleneck in bootstrapping is the need to evaluate Homomorphically the reduction of one integer modulo another. This is typically done by emulating a binary modular reduction circuit, using bit operations on binary representation of integers. We present a simpler approach that bypasses the Homomorphic modular-reduction bottleneck to some extent, by working with a modulus very close to a power of two. Our method is easier to describe and implement than the generic binary circuit approach, and we expect it to be faster in practice (although we did not implement it yet). In some cases it also allows us to store the Encryption of the secret key as a single ciphertext, thus reducing the size of the public key. We also show how to combine our new method with the SIMD Homomorphic computation techniques of Smart-Vercauteren and Gentry-Halevi-Smart, to get a bootstrapping method that works in time quasi-linear in the security parameter. This last part requires extending the techniques from prior work to handle arithmetic not only over fields, but also over some rings. (Specifically, our method uses arithmetic modulo a power of two, rather than over characteristic-two fields.)
-
leveled Fully Homomorphic Encryption without bootstrapping
Conference on Innovations in Theoretical Computer Science, 2012Co-Authors: Zvika Brakerski, Craig Gentry, Vinod VaikuntanathanAbstract:We present a novel approach to Fully Homomorphic Encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled Fully Homomorphic Encryption schemes (capable of evaluating arbitrary polynomial-size circuits), without Gentry's bootstrapping procedure. Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or ring-LWE (RLWE) problems that have 2λ security against known attacks. For RLWE, we have: • A leveled FHE scheme that can evaluate L-level arithmetic circuits with O(λ · L3) per-gate computation -- i.e., computation quasi-linear in the security parameter. Security is based on RLWE for an approximation factor exponential in L. This construction does not use the bootstrapping procedure. • A leveled FHE scheme that uses bootstrapping as an optimization, where the per-gate computation (which includes the bootstrapping procedure) is O(λ2), independent of L. Security is based on the hardness of RLWE for quasi-polynomial factors (as opposed to the sub-exponential factors needed in previous schemes). We obtain similar results to the above for LWE, but with worse performance. Based on the Ring LWE assumption, we introduce a number of further optimizations to our schemes. As an example, for circuits of large width -- e.g., where a constant fraction of levels have width at least λ -- we can reduce the per-gate computation of the bootstrapped version to O(λ), independent of L, by batching the bootstrapping operation. Previous FHE schemes all required Ω(λ3.5) computation per gate. At the core of our construction is a much more effective approach for managing the noise level of lattice-based ciphertexts as Homomorphic operations are performed, using some new techniques recently introduced by Brakerski and Vaikuntanathan (FOCS 2011).
-
Fully Homomorphic Encryption with Polylog Overhead
EUROCRYPT 2012, LNCS, 2012Co-Authors: Craig Gentry, Shai Halevi, Nigel P. SmartAbstract:We show that Homomorphic evaluation of (wide enough) arithmetic circuits can be accomplished with only polylogarithmic overhead. Namely, we present a construction of Fully Homomorphic Encryption (FHE) schemes that for security parameter ¥lamba can evaluate any width-¥Omega(¥lambda) circuit with t gates in time t?polylog(¥lambda). To get low overhead, we use the recent batch Homomorphic evaluation techniques of Smart-Vercautren and Brakerski-Gentry-Vaikuntanathan, who showed that Homomorphic operations can be applied to "packed" ciphertexts that encrypt vectors of plaintext elements. In this work, we introduce permuting/routing techniques to move plaintext elements across these vectors efficiently. Hence, we are able to implement general arithmetic circuit in a batched fashion without ever needing to "unpack" the plaintext vectors. We also introduce some other optimizations that can speed up Homomorphic evaluation in certain cases. For example, we show how to use the Frobenius map to raise plaintext elements to powers of p at the "cost" of a linear operation.
-
Better Bootstrapping in Fully Homomorphic Encryption
PKC 2012, LNCS, 2012Co-Authors: Craig Gentry, Shai HaleviAbstract:Gentry’s bootstrapping technique is currently the only known method of obtaining a “pure” Fully Homomorphic Encryption (FHE) schemes, and it may offers performance advantages even in cases that do not require pure FHE (such as when using the new noise-control technique of Brakerski-Gentry-Vaikuntanathan). The main bottleneck in bootstrapping is the need to evaluate Homomorphically the reduction of one integer modulo another. This is typically done by emulating a binary modular reduction circuit, using bit operations on binary representation of integers. We present a simpler approach that bypasses the Homomorphic modular-reduction bottleneck to some extent, by working with a modulus very close to a power of two. Our method is easier to describe and implement than the generic binary circuit approach, and is likely to be faster in practice. In some cases it also allows us to store the Encryption of the secret key as a single ciphertext, thus reducing the size of the public key. We also show how to combine our new method with the SIMD Homomorphic computation techniques of Smart-Vercauteren and Gentry-Halevi-Smart, to get a bootstrapping method that works in time quasi-linear in the security parameter. This last part requires extending the techniques from prior work to handle arithmetic not only over fields, but also over some rings. (Specifically, our method uses arithmetic modulo a power of two, rather than over characteristic-two fields.)
Mehdi Tibouchi - One of the best experts on this subject based on the ideXlab platform.
-
Scale-Invariant Fully Homomorphic Encryption over the Integers ⋆
2014Co-Authors: Jeansebastien Coron, Tancrede Lepoint, Mehdi TibouchiAbstract:Abstract. At Crypto 2012, Brakerski constructed a scale-invariant Fully Homomorphic Encryption scheme based on the LWE problem, in which the same modulus is used throughout the evaluation process, instead of a ladder of moduli when doing “modulus switching”. In this paper we describe a variant of the van Dijk et al. FHE scheme over the integers with the same scale-invariant property. Our scheme has a single secret modulus whose size is linear in the multiplicative depth of the circuit to be Homomorphically evaluated, instead of exponential; we therefore construct a leveled Fully Homomorphic Encryption scheme. This scheme can be transformed into a pure Fully Homomorphic Encryption scheme using bootstrapping, and its security is still based on the Approximate-GCD problem. We also describe an implementation of the Homomorphic evaluation of the full AES Encryption circuit, and obtain significantly improved performance compared to previous implementations: about 23 seconds (resp. 3 minutes) per AES block at the 72-bit (resp. 80-bit) security level on a mid-range workstation. Finally, we prove the equivalence between the (error-free) decisional Approximate-GCD problem introduced by Cheon et al. (Eurocrypt 2013) and the classical computational Approximate-GCD problem. This equivalence allows to get rid of the additional noise in all the integer-based FHE schemes described so far, and therefore to simplify their security proof
-
Scale-Invariant Fully-Homomorphic Encryption over the Integers
17th International Conference on Practice and Theory in Public-Key Cryptography, 2014Co-Authors: Mehdi TibouchiAbstract:At Crypto 2012, Brakerski constructed a scale-invariant Fully Homomorphic Encryption scheme based on the LWE problem, in which the same modulus is used throughout the evaluation process, instead of a ladder of moduli when doing “modulus switching”. In this paper we describe a variant of the van Dijk et al. FHE scheme over the integers with the same scale-invariant property. Our scheme has a single secret modulus whose size is linear in the multiplicative depth of the circuit to be Homomorphically evaluated, instead of exponential; we therefore construct a leveled Fully Homomorphic Encryption scheme. This scheme can be transformed into a pure Fully Homomorphic Encryption scheme using bootstrapping, and its security is still based on the Approximate-GCD problem. We also describe an implementation of the Homomorphic evaluation of the full AES Encryption circuit, and obtain significantly improved performance compared to previous implementations: about 23 seconds (resp. 3 minutes) per AES block at the 72-bit (resp. 80-bit) security level on a mid-range workstation. Finally, we prove the equivalence between the (error-free) decisional Approximate-GCD problem introduced by Cheon et al. (Eurocrypt 2013) and the classical computational Approximate-GCD problem. This equivalence allows to get rid of the additional noise in all the integer-based FHE schemes described so far, and therefore to simplify their security proof.
-
batch Fully Homomorphic Encryption over the integers
Theory and Application of Cryptographic Techniques, 2013Co-Authors: Jung Hee Cheon, Mehdi Tibouchi, Jeansebastien Coron, Jinsu Kim, Moon Sung Lee, Tancrede Lepoint, Aaram YunAbstract:We extend the Fully Homomorphic Encryption scheme over the integers of van Dijk et al.(DGHV) into a batch Fully Homomorphic Encryption scheme, i.e. to a scheme that supports encrypting and Homomorphically processing a vector of plaintexts as a single ciphertext.
-
Fully Homomorphic Encryption over the Integers with Shorter Public Keys
2011Co-Authors: Jeansebastien Coron, Avradip Mandal, David Naccache, Mehdi TibouchiAbstract:At Eurocrypt 2010 van Dijk et al. described a Fully Homomorphic Encryption scheme over the integers. The main appeal of this scheme (compared to Gentry’s) is its conceptual simplicity. This simplicity comes at the expense of a public key size in O~(λ10) which is too large for any practical system. In this paper we reduce the public key size to O~(λ7) by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk et al. We also describe the first implementation of the resulting Fully Homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry’s scheme, we obtain roughly the same level of efficiency. This shows that Fully Homomorphic Encryption can be implemented using simple arithmetic operations.
Shai Halevi - One of the best experts on this subject based on the ideXlab platform.
-
better bootstrapping in Fully Homomorphic Encryption
Public Key Cryptography, 2012Co-Authors: Craig Gentry, Shai Halevi, Nigel P. SmartAbstract:Gentry's bootstrapping technique is currently the only known method of obtaining a "pure" Fully Homomorphic Encryption (FHE) schemes, and it may offers performance advantages even in cases that do not require pure FHE (e.g., when using the noise-control technique of Brakerski-Gentry-Vaikuntanathan). The main bottleneck in bootstrapping is the need to evaluate Homomorphically the reduction of one integer modulo another. This is typically done by emulating a binary modular reduction circuit, using bit operations on binary representation of integers. We present a simpler approach that bypasses the Homomorphic modular-reduction bottleneck to some extent, by working with a modulus very close to a power of two. Our method is easier to describe and implement than the generic binary circuit approach, and we expect it to be faster in practice (although we did not implement it yet). In some cases it also allows us to store the Encryption of the secret key as a single ciphertext, thus reducing the size of the public key. We also show how to combine our new method with the SIMD Homomorphic computation techniques of Smart-Vercauteren and Gentry-Halevi-Smart, to get a bootstrapping method that works in time quasi-linear in the security parameter. This last part requires extending the techniques from prior work to handle arithmetic not only over fields, but also over some rings. (Specifically, our method uses arithmetic modulo a power of two, rather than over characteristic-two fields.)
-
Fully Homomorphic Encryption with Polylog Overhead
EUROCRYPT 2012, LNCS, 2012Co-Authors: Craig Gentry, Shai Halevi, Nigel P. SmartAbstract:We show that Homomorphic evaluation of (wide enough) arithmetic circuits can be accomplished with only polylogarithmic overhead. Namely, we present a construction of Fully Homomorphic Encryption (FHE) schemes that for security parameter ¥lamba can evaluate any width-¥Omega(¥lambda) circuit with t gates in time t?polylog(¥lambda). To get low overhead, we use the recent batch Homomorphic evaluation techniques of Smart-Vercautren and Brakerski-Gentry-Vaikuntanathan, who showed that Homomorphic operations can be applied to "packed" ciphertexts that encrypt vectors of plaintext elements. In this work, we introduce permuting/routing techniques to move plaintext elements across these vectors efficiently. Hence, we are able to implement general arithmetic circuit in a batched fashion without ever needing to "unpack" the plaintext vectors. We also introduce some other optimizations that can speed up Homomorphic evaluation in certain cases. For example, we show how to use the Frobenius map to raise plaintext elements to powers of p at the "cost" of a linear operation.
-
Better Bootstrapping in Fully Homomorphic Encryption
PKC 2012, LNCS, 2012Co-Authors: Craig Gentry, Shai HaleviAbstract:Gentry’s bootstrapping technique is currently the only known method of obtaining a “pure” Fully Homomorphic Encryption (FHE) schemes, and it may offers performance advantages even in cases that do not require pure FHE (such as when using the new noise-control technique of Brakerski-Gentry-Vaikuntanathan). The main bottleneck in bootstrapping is the need to evaluate Homomorphically the reduction of one integer modulo another. This is typically done by emulating a binary modular reduction circuit, using bit operations on binary representation of integers. We present a simpler approach that bypasses the Homomorphic modular-reduction bottleneck to some extent, by working with a modulus very close to a power of two. Our method is easier to describe and implement than the generic binary circuit approach, and is likely to be faster in practice. In some cases it also allows us to store the Encryption of the secret key as a single ciphertext, thus reducing the size of the public key. We also show how to combine our new method with the SIMD Homomorphic computation techniques of Smart-Vercauteren and Gentry-Halevi-Smart, to get a bootstrapping method that works in time quasi-linear in the security parameter. This last part requires extending the techniques from prior work to handle arithmetic not only over fields, but also over some rings. (Specifically, our method uses arithmetic modulo a power of two, rather than over characteristic-two fields.)
-
Fully Homomorphic Encryption without squashing using depth 3 arithmetic circuits
Foundations of Computer Science, 2011Co-Authors: Craig Gentry, Shai HaleviAbstract:All previously known Fully Homomorphic Encryption (FHE) schemes use Gentry's blueprint:* SWHE: Construct a somewhat Homomorphic Encryption (SWHE) scheme -- roughly, an Encryption scheme that can Homomorphically evaluate polynomials up to some degree.* Squash: ``Squash" the decryption function of the SWHE scheme, so that the scheme can evaluate functions twice as complex (in terms of polynomial degree) than its own decryption function. Do this by adding a ``hint " to the SHWE public key -- namely, a large set of vectors that has a secret sparse subset that sums to the original secret key.* Bootstrap: Given a SWHE scheme that can evaluate functions twice as complex as its decryption function, apply Gentry's transformation to get a ``leveled" FHE scheme. To get ``pure" (non-leveled) FHE, one assumes circular security. Here, we describe a new blueprint for FHE. We show how to eliminate the squashing step, and thereby eliminate the need to assume that the sparse subset sum problem (SSSP) is hard, as all previous leveled FHE schemes have done. Using our new blueprint, we obtain the following results:* A ``simple" leveled FHE scheme where we replace SSSP with Decision Diffie-Hellman!* The first leveled FHE scheme based entirely on worst-case hardness}. Specifically, we give a leveled FHE scheme with security based on the shortest independent vector problem over ideal lattices (ideal-SIVP).* Some efficiency improvements for FHE.} While the new blueprint does not yet improve computational efficiency, it reduces cipher text length. As in the previous blueprint, we obtain pure FHE by assuming circular security. Our main technique is to express the decryption function of SWHE schemes as a depth-3 ($\sum \prod \sum$) arithmetic circuit. When we evaluate this decryption function Homomorphically, we temporarily switch to a multiplicatively Homomorphic Encryption (MHE) scheme, such as Elgamal, to handle the $\prod$ part, after which we translate the result from the MHE scheme back to the SWHE scheme by evaluating the MHE scheme's decryption function within the SWHE scheme. The SWHE scheme only needs to be able to evaluate the MHE scheme's decryption function (plus minor operations), and does not need to have the self-referential property of being able to evaluate its {\em own} decryption function, a property that necessitated squashing in the original blueprint.
-
Implementing Gentry's Fully-Homomorphic Encryption Scheme
Advances in Cryptology---EUROCRYPT 2011, 2011Co-Authors: Craig Gentry, Shai HaleviAbstract:We describe a working implementation of a variant of Gentry's Fully Homomorphic Encryption scheme (STOC 2009), similar to the variant used in an earlier implementation effort by Smart and Vercauteren (PKC 2010). Smart and Vercauteren implemented the underlying "somewhat Homomorphic" scheme, but were not able to implement the bootstrapping functionality that is needed to get the complete scheme to work. We show a number of optimizations that allow us to implement all aspects of the scheme, including the bootstrapping functionality. Our main optimization is a key-generation method for the underlying somewhat Homomorphic Encryption, that does not require full polynomial inversion. This reduces the asymptotic complexity from to when working with dimension- n lattices (and practically reducing the time from many hours/days to a few seconds/minutes). Other optimizations include a batching technique for Encryption, a careful analysis of the degree of the decryption polynomial, and some space/time trade-offs for the Fully-Homomorphic scheme. We tested our implementation with lattices of several dimensions, corresponding to several security levels. From a "toy" setting in dimension 512, to "small," "medium," and "large" settings in dimensions 2048, 8192, and 32768, respectively. The public-key size ranges in size from 70 Megabytes for the "small" setting to 2.3 Gigabytes for the "large" setting. The time to run one bootstrapping operation (on a 1-CPU 64-bit machine with large memory) ranges from 30 seconds for the "small" setting to 30 minutes for the "large" setting.
Vinod Vaikuntanathan - One of the best experts on this subject based on the ideXlab platform.
-
leveled Fully Homomorphic Encryption without bootstrapping
Innovations in Theoretical Computer Science, 2014Co-Authors: Zvika Brakerski, Craig Gentry, Vinod VaikuntanathanAbstract:We present a novel approach to Fully Homomorphic Encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled, Fully Homomorphic Encryption schemes (capable of evaluating arbitrary polynomial-size circuits of a-priori bounded depth), without Gentry’s bootstrapping procedure. Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or Ring LWE (RLWE) problems that have 2 λ security against known attacks. We construct the following. (1) A leveled FHE scheme that can evaluate depth-L arithmetic circuits (composed of fan-in 2 gates) using O(λ. L3) per-gate computation, quasilinear in the security parameter. Security is based on RLWE for an approximation factor exponential in L. This construction does not use the bootstrapping procedure. (2) A leveled FHE scheme that can evaluate depth-L arithmetic circuits (composed of fan-in 2 gates) using O(λ2) per-gate computation, which is independent of L. Security is based on RLWE for quasipolynomial factors. This construction uses bootstrapping as an optimization. We obtain similar results for LWE, but with worse performance. All previous (leveled) FHE schemes required a per-gate computation of Ω(λ3.5), and all of them relied on subexponential hardness assumptions. We introduce a number of further optimizations to our scheme based on the Ring LWE assumption. As an example, for circuits of large width (e.g., where a constant fraction of levels have width Ω(λ)), we can reduce the per-gate computation of the bootstrapped version to O(λ), independent of L, by batching the bootstrapping operation. At the core of our construction is a new approach for managing the noise in lattice-based ciphertexts, significantly extending the techniques of Brakerski and Vaikuntanathan [2011b].
-
efficient Fully Homomorphic Encryption from standard mathsf lwe
SIAM Journal on Computing, 2014Co-Authors: Zvika Brakerski, Vinod VaikuntanathanAbstract:A Fully Homomorphic Encryption (FHE) scheme allows anyone to transform an Encryption of a message, $m$, into an Encryption of any (efficient) function of that message, $f(m)$, without knowing the secret key. We present a leveled FHE scheme that is based solely on the (standard) learning with errors ($\mathsf{LWE}$) assumption. (Leveled FHE schemes are initialized with a bound on the maximal evaluation depth. However, this restriction can be removed by assuming “weak circular security.'') Applying known results on $\mathsf{LWE}$, the security of our scheme is based on the worst-case hardness of “short vector problems” on arbitrary lattices. Our construction improves on previous works in two aspects: 1. We show that “somewhat Homomorphic” Encryption can be based on $\mathsf{LWE}$, using a new relinearization technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. 2. We deviate from the “squashing paradigm” used in all previous works. We introduce a n...
-
on the fly multiparty computation on the cloud via multikey Fully Homomorphic Encryption
IACR Cryptology ePrint Archive, 2013Co-Authors: Adriana Lopezalt, Eran Tromer, Vinod VaikuntanathanAbstract:We propose a new notion of secure multiparty computation aided by a computationallypowerful but untrusted “cloud” server. In this notion that we call on-the-fly multiparty computation (MPC), the cloud can non-interactively perform arbitrary, dynamically chosen computations on data belonging to arbitrary sets of users chosen on-the-fly. All user’s input data and intermediate results are protected from snooping by the cloud as well as other users. This extends the standard notion of Fully Homomorphic Encryption (FHE), where users can only enlist the cloud’s help in evaluating functions on their own encrypted data. In on-the-fly MPC, each user is involved only when initially uploading his (encrypted) data to the cloud, and in a final output decryption phase when outputs are revealed; the complexity of both is independent of the function being computed and the total number of users in the system. When users upload their data, they need not decide in advance which function will be computed, nor who they will compute with; they need only retroactively approve the eventuallychosen functions and on whose data the functions were evaluated. This notion is qualitatively the best possible in minimizing interaction, since the users’ interaction in the decryption stage is inevitable: we show that removing it would imply generic program obfuscation and is thus impossible. Our contributions are two-fold: 1. We show how on-the-fly MPC can be achieved using a new type of Encryption scheme that we call multikey FHE, which is capable of operating on inputs encrypted under multiple, unrelated keys. A ciphertext resulting from a multikey evaluation can be jointly decrypted using the secret keys of all the users involved in the computation. 2. We construct a multikey FHE scheme based on NTRU, a very efficient public-key Encryption scheme proposed in the 1990s. It was previously not known how to make NTRU Fully Homomorphic even for a single party. We view the construction of (multikey) FHE from NTRU Encryption as a main contribution of independent interest. Although the transformation to a Fully Homomorphic system deteriorates the efficiency of NTRU somewhat, we believe that this system is a leading candidate for a practical FHE scheme.
-
leveled Fully Homomorphic Encryption without bootstrapping
Conference on Innovations in Theoretical Computer Science, 2012Co-Authors: Zvika Brakerski, Craig Gentry, Vinod VaikuntanathanAbstract:We present a novel approach to Fully Homomorphic Encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled Fully Homomorphic Encryption schemes (capable of evaluating arbitrary polynomial-size circuits), without Gentry's bootstrapping procedure. Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or ring-LWE (RLWE) problems that have 2λ security against known attacks. For RLWE, we have: • A leveled FHE scheme that can evaluate L-level arithmetic circuits with O(λ · L3) per-gate computation -- i.e., computation quasi-linear in the security parameter. Security is based on RLWE for an approximation factor exponential in L. This construction does not use the bootstrapping procedure. • A leveled FHE scheme that uses bootstrapping as an optimization, where the per-gate computation (which includes the bootstrapping procedure) is O(λ2), independent of L. Security is based on the hardness of RLWE for quasi-polynomial factors (as opposed to the sub-exponential factors needed in previous schemes). We obtain similar results to the above for LWE, but with worse performance. Based on the Ring LWE assumption, we introduce a number of further optimizations to our schemes. As an example, for circuits of large width -- e.g., where a constant fraction of levels have width at least λ -- we can reduce the per-gate computation of the bootstrapped version to O(λ), independent of L, by batching the bootstrapping operation. Previous FHE schemes all required Ω(λ3.5) computation per gate. At the core of our construction is a much more effective approach for managing the noise level of lattice-based ciphertexts as Homomorphic operations are performed, using some new techniques recently introduced by Brakerski and Vaikuntanathan (FOCS 2011).
-
efficient Fully Homomorphic Encryption from standard lwe
Foundations of Computer Science, 2011Co-Authors: Zvika Brakerski, Vinod VaikuntanathanAbstract:We present a Fully Homomorphic Encryption scheme that is based solely on the(standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices. Our construction improves on previous works in two aspects:\begin{enumerate}\item We show that ``somewhat Homomorphic'' Encryption can be based on LWE, using a new {\em re-linearization} technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. \item We deviate from the "squashing paradigm'' used in all previous works. We introduce a new {\em dimension-modulus reduction} technique, which shortens the cipher texts and reduces the decryption complexity of our scheme, {\em without introducing additional assumptions}. \end{enumerate}Our scheme has very short cipher texts and we therefore use it to construct an asymptotically efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is $k \cdot \polylog(k)+\log \dbs$ bits per single-bit query (here, $k$ is a security parameter).
Barry C Sanders - One of the best experts on this subject based on the ideXlab platform.
-
experimental demonstration of quantum Fully Homomorphic Encryption with application in a two party secure protocol
Physical Review X, 2020Co-Authors: Wengkian Tham, Hugo Ferretti, Kent Bonsmafisher, Aharon Brodutch, Barry C Sanders, Aephraim M Steinberg, Stacey JefferyAbstract:A Fully Homomorphic Encryption system hides data from unauthorized parties, while still allowing them to perform computations on the encrypted data. Aside from the straightforward benefit of allowing users to delegate computations to a more powerful server without revealing their inputs, a Fully Homomorphic cryptosystem can be used as a building block in the construction of a number of cryptographic functionalities. Designing such a scheme remained an open problem until 2009, decades after the idea was first conceived, and the past few years have seen the generalization of this functionality to the world of quantum machines. Quantum schemes prior to the one implemented here were able to replicate some features in particular use-cases often associated with Homomorphic Encryption but lacked other crucial properties, for example, relying on continual interaction to perform a computation or leaking information about the encrypted data. We present the first experimental realisation of a quantum Fully Homomorphic Encryption scheme. We further present a toy two-party secure computation task enabled by our scheme. Finally, as part of our implementation, we also demonstrate a post-selective two-qubit linear optical controlled-phase gate with a much higher post-selection success probability (1/2) when compared to alternate implementations, e.g. with post-selective controlled-Z or controlled-X gates (1/9).
