1 of 29

Quantum State Obfuscation from Classical Oracles

James Bartusek Zvika Brakerski Vinod Vaikuntanathan

NYU Weizmann Institute MIT

2 of 29

Assuming one-way functions, there exists ideal obfuscation for any pseudo-deterministic quantum program in the classical oracle model

Main result: “Quantum State Obfuscation”

3 of 29

Assuming one-way functions, there exists ideal obfuscation for any pseudo-deterministic quantum program in the classical oracle model

Main result: “Quantum State Obfuscation”

4 of 29

Assuming one-way functions, there exists ideal obfuscation for any pseudo-deterministic quantum program in the classical oracle model

Main result: “Quantum State Obfuscation”

5 of 29

Assuming one-way functions, there exists ideal obfuscation for any pseudo-deterministic quantum program in the classical oracle model

[AC12, BS16, ACKZ20, ALLZZ21, …]

Oracle may be instantiated with any quantum-secure classical obfuscator [e.g. BGMZ18, CVW18, AP20, BDGM22, GP21, WW21], yielding a candidate quantum state indistinguishability obfuscator

Main result: “Quantum State Obfuscation”

6 of 29

Quantum obfuscation results

Work	Obfuscator	Program class	Assumption / model	Result
[BK21]	Classical -> Quantum	Unitaries with log-many non-Clifford gates (quantum -> quantum)	iO for classical circuits	iO
[BM22]	Classical -> Classical	Null (quantum -> classical)	Classical oracle model + LWE	iO
[BKNY23]	Classical -> Quantum	Pseudo-deterministic (classical -> classical)	Classical oracle model + LWE	Ideal
[CG24]	Quantum -> Quantum	Pseudo-deterministic (classical -> classical)	Quantum oracle model	iO
This work	Quantum -> Quantum	Pseudo-deterministic (classical -> classical)	Classical oracle model + OWF	Ideal

7 of 29

Quantum obfuscation results

Work	Obfuscator	Program class	Assumption / model	Result
[BK21]	Classical -> Quantum	Unitaries with log-many non-Clifford gates (quantum -> quantum)	iO for classical circuits	iO
[BM22]	Classical -> Classical	Null (quantum -> classical)	Classical oracle model + LWE	iO
[BKNY23]	Classical -> Quantum	Pseudo-deterministic (classical -> classical)	Classical oracle model + LWE	Ideal
[CG24]	Quantum -> Quantum	Pseudo-deterministic (classical -> classical)	Quantum oracle model	iO
This work	Quantum -> Quantum	Pseudo-deterministic (classical -> classical)	Classical oracle model + OWF	Ideal
…	…	…
??	Classical -> Classical	CPTP map (quantum -> quantum)
??	Quantum -> Quantum	CPTP map (quantum -> quantum)

8 of 29

Application: Best-possible copy-protection [CG24]

[Aar09] software copy-protection:

9 of 29

Construction: Bird’s eye view

10 of 29

Homomorphic quantum computation

Construction: Bird’s eye view

11 of 29

Oracle should act as a “constrained” secret key

Construction: Bird’s eye view

Homomorphic quantum computation

12 of 29

Prior approach [BM22, BKNY23]

Classical argument for (samp) BQP [Mah18,…]

Construction: Bird’s eye view

Homomorphic quantum computation

13 of 29

Prior approach [BM22, BKNY23]

Classical argument for (samp) BQP [Mah18,…]

This approach fails in our setting because the statement to be proven is quantum!

Construction: Bird’s eye view

Homomorphic quantum computation

14 of 29

Quantum authentication scheme

Idea: Oracle will detect if the adversary is deviating from the honest computation

How do we authenticate quantum information?

2. How do we perform computation

on authenticated information?

Our approach

15 of 29

Tampering adversary

or

Quantum Authentication

16 of 29

Publicly-Verifiable Quantum Authentication

Tampering adversary

or

Verification oracle

Verification oracle can be used to test whether any state is a valid authenticated state

Why does this not violate the impossibility of signing quantum states [BCGST02]?

17 of 29

=

Intuition for security:

Encode-Encrypt Authentication

:

where

Generic template [BGS13]:

Any successful tampering attack must stay inside the codespace

18 of 29

=

Intuition for security:

Encode-Encrypt Authentication

:

where

Our instantiation

Any successful tampering attack must stay inside the codespace

(“quantum linear codes”)

Public-verification security relies on the uniform randomness of the choice of code

19 of 29

Authentication scheme: Details

Require security against adversaries with the ability to perform these projective measurements

Bonus property: linear-homomorphism

20 of 29

Initial experiment:

Authentication scheme: Proof sketch

21 of 29

Initial experiment:

Authentication scheme: Proof sketch

22 of 29

Initial experiment:

Authentication scheme: Proof sketch

23 of 29

How do we authenticate quantum information?

2. How do we perform computation

on authenticated information?

Construction: Bird’s eye view

24 of 29

To go beyond Cliffords, we need some magic

Quantum FHE

=

“Oblivious measurement”:

[Mah18]

25 of 29

From Quantum FHE to Obfuscation

“Oblivious measurement”:

=

To go beyond Cliffords, we need some magic

Issue: Our Auth scheme is not Clifford-homomorphic

26 of 29

“Oblivious measurement”:

=

To implement everything else…

Solution: “Linear + Measurement Circuits”

Disclaimer: this oblivious measurement becomes more complicated

27 of 29

Oracle-enabled oblivious measurement

Setting: evaluator has authenticated quantum states

28 of 29

How do we authenticate quantum information?

2. How do we perform computation

on authenticated information?

See paper for further details, including how we prevent “mixed-input” attacks

Construction: Bird’s eye view

29 of 29

Open problems

Can we prove security assuming post-quantum indistinguishability obfuscation for classical circuits?

Can we obfuscate more general classes of circuits?

Sampling circuits (this scheme is a candidate!)

Quantum input / output

Thanks for listening!