Efficient Fully Homomorphic Encryption from (Standard) LWE
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 (LWE...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115488 https://orcid.org/0000-0002-2666-0045 |
| _version_ | 1811072759430643712 |
|---|---|
| author | Brakerski, Zvika Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Brakerski, Zvika Vaikuntanathan, Vinod |
| author_sort | Brakerski, Zvika |
| collection | MIT |
| description | 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 (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 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 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 LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is k·polylog(k)+log |DB| bits per
single-bit query, in order to achieve security against 2k-time adversaries (based on the best known attacks against our underlying assumptions). Key words. cryptology, public-key encryption, fully homomorphic encryption, learning with errors, private information retrieval |
| first_indexed | 2024-09-23T09:12:02Z |
| format | Article |
| id | mit-1721.1/115488 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:12:02Z |
| publishDate | 2018 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1154882022-09-30T14:02:24Z Efficient Fully Homomorphic Encryption from (Standard) LWE Brakerski, Zvika Vaikuntanathan, Vinod Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Vaikuntanathan, Vinod 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 (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 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 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 LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is k·polylog(k)+log |DB| bits per single-bit query, in order to achieve security against 2k-time adversaries (based on the best known attacks against our underlying assumptions). Key words. cryptology, public-key encryption, fully homomorphic encryption, learning with errors, private information retrieval 2018-05-18T13:31:11Z 2018-05-18T13:31:11Z 2014-04 2012-03 2018-05-10T16:45:09Z Article http://purl.org/eprint/type/JournalArticle 0097-5397 1095-7111 http://hdl.handle.net/1721.1/115488 Brakerski, Zvika, and Vinod Vaikuntanathan. “Efficient Fully Homomorphic Encryption from (Standard) LWE.” SIAM Journal on Computing, vol. 43, no. 2, Jan. 2014, pp. 831–71. © The Authors https://orcid.org/0000-0002-2666-0045 http://dx.doi.org/10.1137/120868669 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Brakerski, Zvika Vaikuntanathan, Vinod Efficient Fully Homomorphic Encryption from (Standard) LWE |
| title | Efficient Fully Homomorphic Encryption from (Standard) LWE |
| title_full | Efficient Fully Homomorphic Encryption from (Standard) LWE |
| title_fullStr | Efficient Fully Homomorphic Encryption from (Standard) LWE |
| title_full_unstemmed | Efficient Fully Homomorphic Encryption from (Standard) LWE |
| title_short | Efficient Fully Homomorphic Encryption from (Standard) LWE |
| title_sort | efficient fully homomorphic encryption from standard lwe |
| url | http://hdl.handle.net/1721.1/115488 https://orcid.org/0000-0002-2666-0045 |
| work_keys_str_mv | AT brakerskizvika efficientfullyhomomorphicencryptionfromstandardlwe AT vaikuntanathanvinod efficientfullyhomomorphicencryptionfromstandardlwe |