NDLI: (Leveled) fully homomorphic encryption without bootstrapping

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

High-confidence predictions under adversarial uncertainty

Learning hurdles for sleeping experts

Restriction access

Mechanism design with approximate valuations

Quantum strategic game theory

The curse of simultaneity

No justified complaints: on fair sharing of multiple resources

From randomizing polynomials to parallel algorithms

Practical verified computation with streaming interactive proofs

Paging for multi-core shared caches

Noise vs computational intractability in dynamics

Distribution free evolvability of polynomial functions over all convex loss functions

Algorithms on evolving graphs

Towards deterministic tree code constructions

Linear time decoding of regular expander codes

List decoding subspace codes from insertions and deletions

Bounds on locally testable codes with unique tests

Approximately optimal mechanism design via differential privacy

Fairness through awareness

Dynamics of prisoner's dilemma and the evolution of cooperation on networks

Crowdsourced Bayesian auctions

Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure

Quantum interactive proofs with weak error bounds

Quantum money from knots

Quantum rejection sampling

(Leveled) fully homomorphic encryption without bootstrapping

From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again

Targeted malleability: homomorphic encryption for restricted computations

Sherali-Adams relaxations and indistinguishability in counting logics

Graph densification

Spectral sparsification via random spanners

Multicommodity flows and cuts in polymatroidal networks

On the degree of univariate polynomials over the integers

On persistent homotopy, knotted complexes and the Alexander module

Compressed matrix multiplication

Gadgets and anti-gadgets leading to a complexity dichotomy

On beating the hybrid argument

Linear programming, width-1 CSPs, and robust satisfaction

Marginal hitting sets imply super-polynomial lower bounds for permanent

(Leveled) fully homomorphic encryption without bootstrapping

Content Provider	ACM Digital Library
Author	Gentry, Craig Brakerski, Zvika Vaikuntanathan, Vinod
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), 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 Õ(λ · $L^{3})$ 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 $Õ(λ^{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 Õ(λ), 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).
Starting Page	309
Ending Page	325
Page Count	17
File Format	PDF
ISBN	9781450311151
DOI	10.1145/2090236.2090262
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-01-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Bootstrapping Modulus reduction Fully homomorphic encryption Learning with errors
Content Type	Text
Resource Type	Article

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

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

Leveled Certificateless Fully Homomorphic Encryption Schemes From Learning With Errors

Fully Homomorphic Encryption and Bootstrapping

(Leveled) Fully Homomorphic Encryption without Bootstrapping

1 FULLY HOMOMORPHIC ENCRYPTION WITHOUT BOOTSTRAPPING

Efficient Fully Homomorphic Encryption from (Standard) LWE

Can homomorphic encryption be practical?

A novel fully homomorphic encryption scheme bsed on LWE

(Leveled) fully homomorphic encryption without bootstrapping

Similar Documents

(Leveled) Fully Homomorphic Encryption without Bootstrapping

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

Leveled Certificateless Fully Homomorphic Encryption Schemes From Learning With Errors

Fully Homomorphic Encryption and Bootstrapping

(Leveled) Fully Homomorphic Encryption without Bootstrapping

1 FULLY HOMOMORPHIC ENCRYPTION WITHOUT BOOTSTRAPPING

Efficient Fully Homomorphic Encryption from (Standard) LWE

Can homomorphic encryption be practical?

A novel fully homomorphic encryption scheme bsed on LWE

(Leveled) fully homomorphic encryption without bootstrapping