Impossibility of quantum virtual black-box obfuscation of classical circuits

DOI10.1007/978-3-030-84242-0_18MaRDI QIDQ2120091zbMATH OpenOpenAlexFDO

Authors Gorjan Alagic, Zvika Brakerski, Yfke Dulek, Christian Schaffner

Publication date 31 March 2022

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

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Quantum computation (81P68) Quantum coding (general) (81P70) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Abstract: Virtual black-box obfuscation is a strong cryptographic primitive: it encrypts a circuit while maintaining its full input/output functionality. A remarkable result by Barak et al. (Crypto 2001) shows that a general obfuscator that obfuscates classical circuits into classical circuits cannot exist. A promising direction that circumvents this impossibility result is to obfuscate classical circuits into quantum states, which would potentially be better capable of hiding information about the obfuscated circuit. We show that, under the assumption that learning-with-errors (LWE) is hard for quantum computers, this quantum variant of virtual black-box obfuscation of classical circuits is generally impossible. On the way, we show that under the presence of dependent classical auxiliary input, even the small class of classical point functions cannot be quantum virtual black-box obfuscated.

Recommendations

• The impossibility of obfuscation with auxiliary input or a universal simulator
• On the obfuscatability of quantum point functions
• Instantiation of quantum point obfuscation
• Constructions for quantum indistinguishability obfuscation
• On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models

Cites work

• Fully homomorphic encryption using ideal lattices
• Garbled circuits as randomized encodings of functions: a primer
• scientific article; zbMATH DE number 1842483 (Why is no real title available?)
• Obfuscating Point Functions with Multibit Output
• Obfuscation of probabilistic circuits and applications
• On lattices, learning with errors, random linear codes, and cryptography
• On obfuscating point functions
• On perfect correctness in (lockable) obfuscation
• On quantum advantage in information theoretic single-server PIR
• Post-quantum zero knowledge in constant rounds
• Pseudorandomness of ring-LWE for any ring and modulus
• Quantum FHE (almost) as secure as classical
• Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity
• Quantum security proofs using semi-classical oracles
• Secure quantum extraction protocols
• Secure software leasing

Cited in

(9)

• Instantiation of quantum point obfuscation
• Constructions for quantum indistinguishability obfuscation
• Post-quantum resettably-sound zero knowledge
• On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models
• The impossibility of obfuscation with auxiliary input or a universal simulator
• A note on the post-quantum security of (ring) signatures
• Obfuscation of pseudo-deterministic quantum circuits
• One-out-of-many unclonable cryptography: definitions, constructions, and more
• On the obfuscatability of quantum point functions

This page was built for publication: Impossibility of quantum virtual black-box obfuscation of classical circuits

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