NDLI: Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$

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

Volume 47

Volume 46

Volume 43 Issue 2 (Special Section on the Fifty-Second IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011))

Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

How to Garble Arithmetic Circuits

Min-Max Graph Partitioning and Small Set Expansion

Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$

Privacy Amplification and Nonmalleable Extractors Via Character Sums

A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths

Quadratic Goldreich--Levin Theorems

3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General

Near-Optimal Column-Based Matrix Reconstruction

On Range Searching in the Group Model and Combinatorial Discrepancy

Extractors for Circuit Sources

Special Section on the Fifty-Second IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011)

Self-Improving Algorithms for Coordinatewise Maxima and Convex Hulls

Constraint Satisfaction Parameterized by Solution Size

Improved Bounds for the Union of Locally Fat Objects in the Plane

Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

Expanders via Random Spanning Trees

Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of Bits

Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification

Computing the Discrete Fréchet Distance in Subquadratic Time

Approximate Shortest Descending Paths

Coin Flipping with Constant Bias Implies One-Way Functions

Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset

Volume 43 Issue 1 (Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010))

Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Brakerski, Zvika Vaikuntanathan, Vinod
Copyright Year	2014
Abstract	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 new dimension-modulus reduction technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, without introducing additional assumptions. Our scheme has very short ciphertexts, and we therefore use it to construct an asymptotically efficient $\mathsf{LWE}$-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is $k\cdot\mathrm{polylog}(k)+\log\|\mathtt{DB}\|$ bits per single-bit query, in order to achieve security against $2^k$-time adversaries (based on the best known attacks against our underlying assumptions).
Starting Page	831
Ending Page	871
Page Count	41
File Format	PDF
ISSN	00975397
DOI	10.1137/120868669
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2 (Special Section on the Fifty-Second IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011))
Volume Number	43
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2014-04-29
Access Restriction	Subscribed
Subject Keyword	fully homomorphic encryption learning with errors private information retrieval Data encryption Cryptography cryptology public-key encryption
Content Type	Text
Resource Type	Article
Subject	Mathematics 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

Efficient Fully Homomorphic Encryption from (Standard) LWE

Single-Database Private Information Retrieval from Fully Homomorphic Encryption

Efficient Batch Fully Homomorphic Encryption with a Shorter Key from Ring-LWE

CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes

1 A Multi-Bit Fully Homomorphic Encryption with Shorter Public Key from LWE

Homomorphic AES evaluation using the modified LTV scheme

A novel fully homomorphic encryption scheme bsed on LWE

A Multi-Bit Fully Homomorphic Encryption With Shorter Public Key From LWE

Efficient batch identity-based fully homomorphic encryption scheme in the standard model

Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$

Similar Documents

Efficient Fully Homomorphic Encryption from (Standard) LWE

Single-Database Private Information Retrieval from Fully Homomorphic Encryption

Efficient Batch Fully Homomorphic Encryption with a Shorter Key from Ring-LWE

CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes

1 A Multi-Bit Fully Homomorphic Encryption with Shorter Public Key from LWE

Homomorphic AES evaluation using the modified LTV scheme

A novel fully homomorphic encryption scheme bsed on LWE

A Multi-Bit Fully Homomorphic Encryption With Shorter Public Key From LWE

Efficient batch identity-based fully homomorphic encryption scheme in the standard model

Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$