Quantum homomorphic encryption for polynomial-sized circuits

DOI10.1007/978-3-662-53015-3_1zbMATH Open1406.94047arXiv1603.09717OpenAlexW3103263362MaRDI QIDQ2829941FDOQ2829941

Authors: Yfke Dulek, Christian Schaffner, Florian Speelman 

Publication date: 9 November 2016

Published in: Theory of Computing, Advances in Cryptology – CRYPTO 2016 (Search for Journal in Brave)

Abstract: We present a new scheme for quantum homomorphic encryption which is compact and allows for efficient evaluation of arbitrary polynomial-sized quantum circuits. Building on the framework of Broadbent and Jeffery and recent results in the area of instantaneous non-local quantum computation, we show how to construct quantum gadgets that allow perfect correction of the errors which occur during the homomorphic evaluation of T gates on encrypted quantum data. Our scheme can be based on any classical (leveled) fully homomorphic encryption (FHE) scheme and requires no computational assumptions besides those already used by the classical scheme. The size of our quantum gadget depends on the space complexity of the classical decryption function -- which aligns well with the current efforts to minimize the complexity of the decryption function. Our scheme (or slight variants of it) offers a number of additional advantages such as ideal compactness, the ability to supply gadgets "on demand", circuit privacy for the evaluator against passive adversaries, and a three-round scheme for blind delegated quantum computation which puts only very limited demands on the quantum abilities of the client.

Full work available at URL: https://arxiv.org/abs/1603.09717

Recommendations

• Quantum homomorphic encryption for polynomial-sized circuits
• Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity
• Classical homomorphic encryption for quantum circuits
• Teleportation-based quantum homomorphic encryption scheme with quasi-compactness and perfect security
• Quantum FHE (almost) as secure as classical

zbMATH Keywords

quantum computingquantum cryptographyquantum teleportationhomomorphic encryptiongarden-hose modelGarden-Hose model

Mathematics Subject Classification ID

Cryptography (94A60) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94)

Cites Work

• Probabilistic encryption
• Fully homomorphic encryption over the integers
• Evaluating Branching Programs on Encrypted Data
• Fully homomorphic encryption using ideal lattices
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Theory of Cryptography
• (Leveled) fully homomorphic encryption without bootstrapping
• Title not available (Why is that?)
• A method for obtaining digital signatures and public-key cryptosystems
• Universal Blind Quantum Computation
• Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
• (Leveled) fully homomorphic encryption without bootstrapping
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Attribute-based encryption for circuits
• Multiparty computation with low communication, computation and interaction via threshold FHE
• Title not available (Why is that?)
• BLIND QUANTUM COMPUTATION
• Secure assisted quantum computation
• Candidate indistinguishability obfuscation and functional encryption for all circuits
• How to use indistinguishability obfuscation
• Secure Two-Party Quantum Evaluation of Unitaries against Specious Adversaries
• Symmetric quantum fully homomorphic encryption with perfect security
• Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity
• Quantum fully homomorphic encryption scheme based on universal quantum circuit
• How to run Turing machines on encrypted data
• Private information retrieval
• Reusable garbled circuits and succinct functional encryption
• A simple BGN-type cryptosystem from LWE
• Composable security of delegated quantum computation
• Efficient fully homomorphic encryption from (standard) LWE
• Computing Blindfolded: New Developments in Fully Homomorphic Encryption
• New bounds for the garden-hose model
• The garden-hose model
• The garden hose complexity for the equality function
• Computational Security of Quantum Encryption
• Temporally unstructured quantum computation
• Quantum homomorphic encryption for polynomial-sized circuits
• Attribute-based encryption for circuits
• Quantum private information retrieval has linear communication complexity
• Semantic security and indistinguishability in the quantum world
• Instantaneous non-local computation of low T-depth quantum circuits

Cited In (28)

• Quantum fully homomorphic encryption with verification
• Efficient quantum homomorphic encryption scheme with flexible evaluators and its simulation
• Quantum homomorphic encryption scheme with flexible number of evaluator based on \((k, n)\)-threshold quantum state sharing
• Post-quantum multi-party computation
• Improved multiparty quantum private comparison based on quantum homomorphic encryption
• The quantum internet: a hardware review
• Multi-server blind quantum computation over collective-noise channels
• An efficient quantum somewhat homomorphic symmetric searchable encryption
• Verification of quantum computation: an overview of existing approaches
• Arbitrable blind quantum computation
• Secure delegated quantum algorithms for solving Mahalanobis distance
• Teleportation-based quantum homomorphic encryption scheme with quasi-compactness and perfect security
• General impossibility of group homomorphic encryption in the quantum world
• Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity
• Classical Homomorphic Encryption for Quantum Circuits
• Quantum multiparty cryptosystems based on a homomorphic random basis encryption
• Delegating quantum computation in the quantum random oracle model
• Constructions for quantum indistinguishability obfuscation
• Title not available (Why is that?)
• Invited Paper: Homomorphic Operations Techniques Yielding Communication Efficiency
• Rate-1 quantum fully homomorphic encryption
• Quantum fully homomorphic encryption scheme based on universal quantum circuit
• How to construct quantum FHE, generically
• Quantum one-time pad-based quantum homomorphic encryption schemes for circuits of the non-Clifford gates
• Security limitations of classical-client delegated quantum computing
• Practical multi-party quantum homomorphic encryption
• Classical Homomorphic Encryption for Quantum Circuits
• Quantum homomorphic encryption for polynomial-sized circuits

This page was built for publication: Quantum homomorphic encryption for polynomial-sized circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829941)