1 of 38

On the Power of Oblivious State Preparation

James Bartusek Dakshita Khurana

NYU UIUC and NTT Research

2 of 38

Quantum Background

Single-qubit Observables

 

 

 

 

 

 

Bloch sphere:

Single-qubit Rotations

 

 

 

3 of 38

Oblivious State Preparation (OSP)

 

Quantum Receiver

 

 

 

 

4 of 38

Standard OSP

 

Quantum Receiver

 

 

 

 

5 of 38

Standard OSP

 

Quantum Receiver

 

 

 

[CCKW19]: Malicious 4-states QFactory with basis-blindness

Note: We don’t require any verifiability property (see [GV19, GMP22])

 

6 of 38

Standard Two-Round OSP

 

Quantum Receiver

 

 

 

 

This is round-optimal

 

 

7 of 38

Results

OSP

Proofs of quantumness (and test of a qubit)

Blind classical delegation of quantum computation

Classical verification of quantum computation

1-of-2 puzzles

Quantum money with classical communication

Classically-verifiable position verification

Plain TCFs

Dual-mode TCFs

QFHE

Oblivious transfer between one classical and one quantum party

PKE with classical keys and ciphertexts

Two-round

(+ classical FHE)

Two-round

Two-round

[RS19]

[LLQ22]

 

LWE

Extended LHS on group actions

[BCMVV18]

[AMR22, GV24]

Two-round

8 of 38

Takeaways

  • OSP a simple primitive that unifies several constructions in the classical-client quantum-server setting

​

  • In some cases, going through OSP gives new implications
    • Dual-mode TCFs -> quantum money with classical communication
    • Plain TCFs -> blind classical delegation of quantum computation
    • Plain TCFs -> classical verification of quantum computation (concurrent with [BKMSW24])

​

9 of 38

Takeaways

  • OSP a simple primitive that unifies several constructions in the classical-client quantum-server setting

​

  • In some cases, going through OSP gives new implications
    • Group actions -> quantum money with classical communication
    • Group actions-> blind classical delegation of quantum computation
    • Group actions -> classical verification of quantum computation (concurrent with [BKMSW24])

​

    • The constructions of OT and PKE help to “explain” the use of public-key crypto in classical-client quantum-server protocols [BKMVV18,…]
      • Corollary [ACCFLM22]: perfectly-correct OSP does not exist in the QROM
      • In classical setting, we have a separation between OT and TDFs [GKMOV00]

10 of 38

Outline

  • Construction of OSP (via [BGKPV23])

​

  • A computational Bell test from OSP and applications (via [KCVY21, ABCC24])

​

  • Blind classical delegation of quantum computation from OSP (via [Bro15])

​

  • Verifiable classical delegation of quantum computation from OSP (via [KLVY23, NZ23])

​

  • OSP implies PKE and OT (via encrypted CNOT [Mah18])

​

  • Open directions

11 of 38

Outline

  • Construction of OSP (via [BGKPV23])

​

  • A computational Bell test from OSP and applications (via [KCVY21, ABCC24])

​

  • Blind classical delegation of quantum computation from OSP (via [Bro15])

​

  • Verifiable classical delegation of quantum computation from OSP (via [KLVY23, NZ23])

​

  • OSP implies PKE and OT (via encrypted CNOT [Mah18])

​

  • Open directions

12 of 38

(Plain) TCF

  •  

 

Can generalize to any “QPT preparable” distribution

 

13 of 38

OSP from plain TCFs

Classical Sender

Quantum Receiver

 

 

 

 

 

 

 

(via [BGKPV23])

 

14 of 38

OSP from plain TCFs

Classical Sender

Quantum Receiver

 

 

 

 

 

 

 

 

 

 

 

 

 

(via [BGKPV23])

 

 

 

15 of 38

Outline

  • Construction of OSP (via [BGKPV23])

​

  • A computational Bell test from OSP and applications (via [KCVY21, ABCC24])

​

  • Blind classical delegation of quantum computation from OSP (via [Bro15])

​

  • Verifiable classical delegation of quantum computation from OSP (via [KLVY23, NZ23])

​

  • OSP implies PKE and OT (via encrypted CNOT [Mah18])

​

  • Open directions

16 of 38

Proof of quantumness from OSP

Prover

Verifier

 

OSP

 

 

 

 

 

 

 

 

 

 

 

 

[KCVY21, BGKPV23, ABCC24]

17 of 38

Proof of quantumness from OSP

Prover

Verifier

 

OSP

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Soundness argument:

 

 

18 of 38

Proof of quantumness from OSP

Prover

Verifier

 

OSP

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

19 of 38

Unclonable states from OSP

Prover

Verifier

 

OSP

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Observation:

20 of 38

Outline

  • Construction of OSP (via [BGKPV23])

​

  • A computational Bell test from OSP and applications (via [KCVY21, ABCC24])

​

  • Blind classical delegation of quantum computation from OSP (via [Bro15])

​

  • Verifiable classical delegation of quantum computation from OSP (via [KLVY23, NZ23])

​

  • OSP impies PKE and OT (via encrypted CNOT [Mah18])

​

  • Open directions

21 of 38

Quantum server

 

 

 

 

22 of 38

Quantum server

Classical client

 

 

 

 

 

 

 

 

OSP

 

 

 

23 of 38

Quantum server

Classical client

 

 

 

 

 

 

 

 

OSP

 

 

 

 

24 of 38

Quantum server

Classical client

 

 

 

 

 

 

 

 

OSP

 

 

 

CNOT

 

 

 

 

 

 

 

 

OSP

 

 

 

CNOT

 

 

 

 

 

 

 

 

 

 

25 of 38

Outline

  • Construction of OSP (via [BGKPV23])

​

  • A computational Bell test from OSP and applications (via [KCVY21, ABCC24])

​

  • Blind classical delegation of quantum computation from OSP (via [Bro15])

​

  • Verifiable classical delegation of quantum computation from OSP (via [KLVY23, NZ23])

​

  • OSP implies PKE and OT (via encrypted CNOT [Mah18])

​

  • Open directions

26 of 38

[KLVY23] Compiler

 

Alice

Bob

 

 

 

 

 

 

No communication

QFHE

QPT prover

Classical verifier

 

 

 

 

 

 

27 of 38

Generalized KLVY Compiler

 

Alice

Bob

 

 

 

 

 

 

No communication

Blind delegation of Alice’s strategy

Classical verifier

 

 

 

 

 

 

So, under what conditions does this compiler maintain soundness?

QPT prover

28 of 38

Computationally Non-Local Strategies

 

 

 

Alice Operation

Bob Operation

 

 

 

 

29 of 38

Computationally Non-Local Strategies

 

 

 

QPT Alice Operation

QPT Bob Operation

 

 

 

 

 

From OSP

Observation: [NZ23] upper bounds the CNL value of a family of non-local games for delegating arbitrary BQP computation

 

30 of 38

Outline

  • Construction of OSP (via [BGKPV23])

​

  • A computational Bell test from OSP and applications (via [KCVY21, ABCC24])

​

  • Blind classical delegation of quantum computation from OSP (via [Bro15])

​

  • Verifiable classical delegation of quantum computation from OSP (via [KLVY23, NZ23])

​

  • OSP implies PKE and OT (via encrypted CNOT [Mah18])

​

  • Open directions

31 of 38

Encrypted CNOT

 

 

 

 

 

 

Introduced in [Mah18] as a building block for QFHE

32 of 38

Two-round Encrypted CNOT

 

 

 

 

 

 

Introduced in [Mah18] as a building block for QFHE

 

 

 

33 of 38

(Two-round) Encrypted CNOT from (two-round) OSP

OSP

34 of 38

Public-key encryption from two-round ECNOT

KeyGen

 

 

 

 

 

35 of 38

Public-key encryption from two-round ECNOT

KeyGen

 

 

 

 

 

 

 

Dec

 

Security:

 

 

 

36 of 38

Oblivious transfer from ECNOT

Basic idea:

 

 

 

 

 

 

 

 

To obtain security against a malicious receiver, repeat and use a cut-and-choose to allow the sender to check that (most of) their states are honestly prepared

37 of 38

Outline

  • Construction of OSP (via [BGKPV23])

​

  • A computational Bell test from OSP and applications (via [KCVY21, ABCC24])

​

  • Blind classical delegation of quantum computation from OSP (via [Bro15])

​

  • Verifiable classical delegation of quantum computation from OSP (via [KLVY23, NZ23])

​

  • Implications to PKE and OT (via encrypted CNOT [Mah18])

​

  • Open directions

38 of 38

Open directions

    • Other applications of OSP
      • Certified deletion / revocable crypto with classical communication?
      • More direct construction of classical verification of quantum computation?
      • Verifiable state preparation (see [GV19])?

​

    • What else implies OSP
      • Coding-based assumptions?
      • Test of a qubit?
      • OT? Or is there a separation?

​

    • Exploring OSP as a basic cryptographic primitive
      • OSP extension (see [Zha21])?
      • OSP for several binary observables? Or multi-output observables?
      • Amplification? Combiners?