Paper 2018/338

Quantum FHE (Almost) As Secure As Classical

Zvika Brakerski

Abstract

Fully homomorphic encryption schemes (FHE) allow to apply arbitrary efficient computation to encrypted data without decrypting it first. In Quantum FHE (QFHE) we may want to apply an arbitrary quantumly efficient computation to (classical or quantum) encrypted data. We present a QFHE scheme with classical key generation (and classical encryption and decryption if the encrypted message is itself classical) with comparable properties to classical FHE. Security relies on the hardness of the learning with errors (LWE) problem with polynomial modulus, which translates to the worst case hardness of approximating short vector problems in lattices to within a polynomial factor. Up to polynomial factors, this matches the best known assumption for classical FHE. Similarly to the classical setting, relying on LWE alone only implies leveled QFHE (where the public key length depends linearly on the maximal allowed evaluation depth). An additional circular security assumption is required to support completely unbounded depth. Interestingly, our circular security assumption is the same assumption that is made to achieve unbounded depth multi-key classical FHE. Technically, we rely on the outline of Mahadev (arXiv 2017) which achieves this functionality by relying on super-polynomial LWE modulus and on a new circular security assumption. We observe a connection between the functionality of evaluating quantum gates and the circuit privacy property of classical homomorphic encryption. While this connection is not sufficient to imply QFHE by itself, it leads us to a path that ultimately allows using classical FHE schemes with polynomial modulus towards constructing QFHE with the same modulus.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2018
Keywords
fully homomorphic encryptionlearning with errorsquantum computation
Contact author(s)
zvika brakerski @ weizmann ac il
History
2019-04-22: revised
2018-04-11: received
See all versions
Short URL
https://ia.cr/2018/338
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/338,
      author = {Zvika Brakerski},
      title = {Quantum {FHE} (Almost) As Secure As Classical},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/338},
      year = {2018},
      url = {https://eprint.iacr.org/2018/338}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.