1 of 24

Obfuscation of Quantum Computation

James Bartusek

UC Berkeley

Indistinguishability Obfuscation of Null Quantum Circuits and Applications

​

with Giulio Malavolta (Bocconi University)

Obfuscation of Pseudo-Deterministic Quantum Circuits

​

with Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa (NTT)

2 of 24

Traditional encryption:

Enc

Obfuscation:

 

 

Obf

 

 

“One-way compiler”

3 of 24

The Story of (Classical) Obfuscation

  • First proposed by [Diffie, Hellman 77]

​

  • Formalizing security [Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, Yang 01], [Goldwasser, Rothblum 07]

​

  • First general-purpose candidate [Garg, Gentry, Halevi, Raykova, Sahai, Waters 13]

​

  • A “central hub” of crypto [Sahai, Waters 13],...

​

  • Firm mathematical foundations …,[Jain, Lin, Sahai 21],...

4 of 24

Quantum Obfuscation

 

 

QObf

 

 

Describes a quantum computation

5 of 24

Quantum Obfuscation

 

 

QObf

 

 

Describes a quantum computation

6 of 24

Quantum Obfuscation

QObf

 

 

 

 

 

 

Describes a quantum computation

7 of 24

Do there exist one-way compilers for quantum computations?

8 of 24

The Story of Quantum Obfuscation (so far)

Initial interest

​

  • [Aaronson 05]

​

  • [Alagic, Fefferman 16]

​

Initial results

​

  • Quantum information cannot be used to circumvent classical impossibilities [Ananth, La Placa 21], [Alagic, Brakerski, Dulek, Schaffner 21]

​

  • Perfect obfuscation for a limited set of circuit equivalences [Alagic, Jeffery, Jordan 14]

​

  • Obfuscation for circuits with logarithmic non-Clifford gates [Broadbent, Kazmi 21]

​

9 of 24

Goal: General-Purpose Feasibility Results

Which quantum programs can be obfuscated given access to an ideal classical cryptographic object:

​

Oracle that computes an (efficient) classical computation of our choice

Focus: quantum programs with (pseudo)-deterministic classical outputs

Can be heuristically instantiated with indistinguishability obfuscation

10 of 24

Results in the classical oracle model

QObf

 

 

[B, Malavolta 22]

Description of a null quantum computation

Cryptographic applications:

e.g. the only currently known NIZK and SNARG for QMA

 

 

(QObf should satisfy correctness for non-null computations)

11 of 24

Results in the classical oracle model

QObf

Description of a pseudo-deterministic quantum computation

 

 

 

 

[B, Kitagawa, Nishimaki, Yamakawa 23]

 

E.g. obfuscate a circuit that computes Shor’s algorithm

12 of 24

Results in the classical oracle model

QObf

Quantum description of a pseudo-deterministic computation

 

 

 

 

[B, Brakerski, Vaikuntanathan] (in submission)

Implies “best-possible” copy-protection [Coladangelo, Gunn 23]

 

 

13 of 24

Bird’s Eye View

 

 

 

 

 

 

Blind quantum computation

Should only allow to decrypt honestly generated encodings

Verifiable +

14 of 24

 

 

 

 

 

 

 

 

Blind Delegation

(Classically) Verifiable Delegation

 

 

 

 

 

 

 

 

 

 

 

 

[Mahadev 18a]

[Mahadev 18b]

15 of 24

 

 

 

 

 

 

 

 

 

 

 

16 of 24

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

17 of 24

Attempted fix: verify the blind evaluation algorithm

​

Still a problem: verification algorithm is learnable

​

Goal: achieve classically verifiable delegation with

reusable soundness [B, Kitagawa, Nishimaki, Yamakawa 23]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

18 of 24

 

 

 

Attack on reusability:

 

 

 

 

 

 

 

 

 

Reusable soundness of classically verifiable delegation

 

19 of 24

 

 

 

 

 

Attack on reusability:

 

 

 

 

 

 

 

 

Main idea: Commit to history state first

 

20 of 24

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Impossible due to binding of the commitment

Main idea: Commit to history state first

21 of 24

 

 

 

 

 

 

 

 

 

 

 

Publicly-decodable Pauli Functional Commitment

Committed state can be opened to either a Z or X measurement

Binding to Z measurements

Binding holds even given oracle access to receiver

Main idea: Commit to history state first

22 of 24

 

 

 

 

 

 

 

 

 

 

 

Publicly-decodable Pauli Functional Commitment

Construction: Generalize template from [Brakerski, Christiano, Mahadev, Vazirani, Vidick 18] to support high-dimensional coset states

Main idea: Commit to history state first

23 of 24

Summary

  • We want to understand if quantum computation can be obfuscated

​

  • First step: what is possible in the classical oracle model?

​

  • Progress so far: quantum programs with classical inputs and (pseudo)-deterministic classical outputs (e.g. Shor’s algorithm)

​

  • Fundamental connections with the notions of blind and (classically) verifiable quantum computation

​

​

24 of 24

Future Directions

  • Proving security under (quantum-secure) indistinguishability obfuscation

​

  • Obfuscating quantum states (ongoing work)

​

  • Obfuscating programs with non-deterministic (classical) output

​

  • Obfuscating programs with quantum inputs / outputs

​

  • Complexity theoretic implications?

Thanks for listening!