NDLI: (Leveled) Fully Homomorphic Encryption without Bootstrapping

Please wait, while we are loading the content...

(Leveled) Fully Homomorphic Encryption without Bootstrapping

Content Provider	ACM Digital Library
Author	Brakerski, Zvika Gentry, Craig Vaikuntanathan, Vinod
Copyright Year	2014
Abstract	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 $\textit{λ}$ security against known attacks. We construct the following. (1) A leveled FHE scheme that can evaluate $depth-\textit{L}$ arithmetic circuits (composed of fan-in 2 gates) using $\textit{O}(\textit{λ}.$ $\textit{L}3)$ per-gate computation, quasilinear in the security parameter. Security is based on RLWE for an approximation factor exponential in $\textit{L}.$ This construction does not use the bootstrapping procedure. (2) A leveled FHE scheme that can evaluate $depth-\textit{L}$ arithmetic circuits (composed of fan-in 2 gates) using $\textit{O}(\textit{λ}2)$ per-gate computation, which is independent of $\textit{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 $\textit{Ω}(\textit{λ}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 $\textit{Ω}(\textit{λ})),$ we can reduce the per-gate computation of the bootstrapped version to $\textit{O}(\textit{λ}),$ independent of $\textit{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].
Starting Page	1
Ending Page	36
Page Count	36
File Format	PDF
ISSN	19423454
e-ISSN	19423462
DOI	10.1145/2633600
Volume Number	6
Issue Number	3
Journal	ACM Transactions on Computation Theory (TOCT)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Fully homomorphic encryption Lattices Learning with errors
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

(Leveled) fully homomorphic encryption without bootstrapping

Fully Homomorphic Encryption and Bootstrapping

Efficient Fully Homomorphic Encryption from (Standard) LWE

Efficient Leveled (Multi) Identity-Based Fully Homomorphic Encryption Schemes

Leveled Certificateless Fully Homomorphic Encryption Schemes From Learning With Errors

On the exact decryption range for Gentry–Halevi's implementation of fully homomorphic encryption

Accelerating Fully Homomorphic Encryption in Hardware

Can homomorphic encryption be practical?

Exploring the Feasibility of Fully Homomorphic Encryption

(Leveled) Fully Homomorphic Encryption without Bootstrapping

Similar Documents

(Leveled) fully homomorphic encryption without bootstrapping

Fully Homomorphic Encryption and Bootstrapping

Efficient Fully Homomorphic Encryption from (Standard) LWE

Efficient Leveled (Multi) Identity-Based Fully Homomorphic Encryption Schemes

Leveled Certificateless Fully Homomorphic Encryption Schemes From Learning With Errors

On the exact decryption range for Gentry–Halevi's implementation of fully homomorphic encryption

Accelerating Fully Homomorphic Encryption in Hardware

Can homomorphic encryption be practical?

Exploring the Feasibility of Fully Homomorphic Encryption

(Leveled) Fully Homomorphic Encryption without Bootstrapping