PaperlayerView exact revision on arXiv

Source-linked AI summary

Obfuscation of Pseudo-Deterministic Quantum Circuits

James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

arXiv:2302.11083v3quant-phcs.CR

TL;DR

The authors do not know how to obfuscate the quantum FHE evaluation circuit. Assuming QLWE, they construct a VBB obfuscator for pseudo-deterministic quantum circuits in the classical oracle model and show that a BQP oracle for language decisions can be simulated with a P oracle.

  • Problem

    The quantum FHE evaluation circuit cannot be obfuscated by the approach described, leaving this step unresolved.

    Source: §2.1 · p. 7

  • Method

    They construct a classical-oracle-model VBB obfuscator for pseudo-deterministic quantum circuits, with a quantum state as the obfuscated program.

    Source: §1 · p. 3

  • Results

    Assuming QLWE, a BQP oracle for deciding BQP languages can be simulated using a P oracle.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Publicly-decodable Pauli functional commitments are an intermediate primitive that may be of independent interest.

    Source: §1 · p. 4

    The authors leave open whether the quantum states can be removed to obtain a classical obfuscated program and whether the heuristic security proof can be improved.

    Source: §1 · p. 6

Abstract

from arXiv · show

We show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, assuming the quantum hardness of learning with errors. Given the classical description of a quantum circuit $Q$, our obfuscator outputs a quantum state $\ket{\widetilde{Q}}$ that can be used to evaluate $Q$ repeatedly on arbitrary inputs. Instantiating the classical oracle using any candidate post-quantum indistinguishability obfuscator gives us the first candidate construction of indistinguishability obfuscation for all polynomial-size pseudo-deterministic quantum circuits. In particular, our scheme is the first candidate obfuscator for a class of circuits that is powerful enough to implement Shor's algorithm (SICOMP 1997). Our approach follows Bartusek and Malavolta (ITCS 2022), who obfuscate \emph{null} quantum circuits by obfuscating the verifier of an appropriate classical verification of quantum computation (CVQC) scheme. We go beyond null circuits by constructing a publicly-verifiable CVQC scheme for quantum \emph{partitioning} circuits, which can be used to verify the evaluation procedure of Mahadev's quantum fully-homomorphic encryption scheme (FOCS 2018). We achieve this by upgrading the one-time secure scheme of Bartusek (TCC 2021) to a fully reusable scheme, via a publicly-decodable \emph{Pauli functional commitment}, which we formally define and construct in this work. This commitment scheme, which satisfies a notion of binding against committers that can access the receiver's standard and Hadamard basis decoding functionalities, is constructed by building on techniques of Amos, Georgiou, Kiayias, and Zhandry (STOC 2020) introduced in the context of equivocal but collision-resistant hash functions.

1 Introduction

Quantum obfuscation remained open beyond narrow circuit classes; this work constructs a classical-oracle VBB obfuscator for pseudo-deterministic quantum circuits under QLWE. The introduction also presents publicly verifiable quantum computation and publicly decodable Pauli functional commitments as supporting contributions.

Results

  • Pseudo-deterministic circuits output a fixed classical result for each input with overwhelming probability, and this class captures Shor’s algorithm [Sho97a].The class can decide any language in non-promise BQP.Source: §1 · p. 3

Main result

  • Assuming QLWE, a quantum state is a VBB obfuscator for any polynomial-size pseudo-deterministic quantum circuit in the classical oracle model.The evaluator and adversary receive oracle access to an efficiently computable classical functionality prepared by the obfuscator.Source: §1 · p. 3

Results

  • Instantiating the classical obfuscator with candidate post-quantum indistinguishability obfuscation gives heuristic evidence for indistinguishability obfuscation of pseudo-deterministic quantum circuits.Indistinguishability obfuscation requires computational indistinguishability for obfuscations of functionally equivalent programs.Source: §1 · p. 4
  • In the classical oracle model, the result can be viewed as simulating a BQP oracle using a P oracle for languages, not general promise problems.The claim assumes QLWE.Source: §1 · p. 4

Building blocks

  • The authors construct Pauli functional commitments that remain secure when the committer accesses both standard- and Hadamard-basis decoding functionalities.Such commitments support opening a qubit committed in superposition for measurement in either basis; prior constructions were compromised by access to Hadamard-basis decoding.Source: §1 · p. 4

Publicly-verifiable quantum fully-homomorphic encryption

  • The work gives the first feasibility result for publicly verifiable quantum fully homomorphic encryption, with classical verification of pseudo-deterministic quantum computation over the plaintexts.The scheme's public parameters are quantum, although verification is classical.Source: §1 · p. 5

Applications

  • The introduction points to quantum copy protection for unlearnable quantum programs and functional encryption for quantum functionalities as applications of the construction.The authors describe these applications as sketches and leave deeper exploration for future work.Source: §1 · p. 5

Open problems

  • Extending obfuscation to all quantum circuits with classical input and output remains open; the authors identify classical verification of general quantum sampling with negligible soundness as a barrier.They also leave open obfuscating general quantum operations and improving the heuristic security proof, including deriving quantum-circuit iO from classical-circuit iO.Source: §1 · pp. 5–6

2 Technical Overview

The technical overview develops a route to obfuscation via classical verification of quantum partitioning circuits, moving from prior one-time soundness to reusable and publicly verifiable soundness. It outlines binding for committed quantum histories and a publicly decodable Pauli functional commitment, including a binding argument based on parameter bounds and the Welch bound.

2.1 Our approach: Verifying quantum partitioning circuits

  • The approach needs publicly verifiable soundness for randomized QFHE evaluation: supports only pseudo-deterministic circuits and is privately verifiable, while Eval[Enc(Q)] is quantum.A verifier can be queried repeatedly through the obfuscated program, so private verifiability is insufficient; directly obfuscating the quantum evaluation circuit is not known.Source: §2.1 · p. 7
  • Partitioning circuits let a classical predicate of randomized QFHE evaluation outputs remain pseudo-deterministic, while the prover must not depend on the predicate containing the secret key.This avoids requiring verification of the full sampling distribution of Eval[Enc(Q)]; the proposed obfuscation route verifies before decrypting.Source: §2.1 · pp. 7–8

2.2 Prior work: One-time soundness

  • Prior work gives a privately verifiable partitioning-circuit protocol with one-time soundness, and this overview introduces Pauli functional commitments as an abstraction for upgrading it.A Pauli functional commitment lets a committed qubit be opened for standard- or Hadamard-basis measurement; prior PFC-I constructions derive dual-mode and uncertainty binding from QLWE.Source: §2.2 · pp. 8–10
  • Repeated superposition queries to the verification oracle can reveal the secret measurement bases and break soundness; signature tokens do not prevent the attack because the prover can project back onto the signing key.The verifier treats Hadamard-round openings differently depending on the hidden basis bits, enabling the information leak.Source: §2.2 · pp. 12–13

2.3 Reusable soundness for a single instance

  • A standard per-instance route to reusable soundness fails here: every input has a valid output, and a sampled ciphertext may have negligible probability, which the one-time scheme cannot establish as in-support.The usual approach associates each instance with its own public and secret parameters, but these quantum sampling inputs do not yield a suitable yes/no instance.Source: §2.3 · p. 13
  • Binding of PFC-II openings lets a prover use committed history states for standard- and Hadamard-basis measurements while preventing mixtures of honest and dishonest openings across repeated verification queries.The soundness argument replaces verification-oracle answers on accepting proofs with ⊥, relying on binding to show this negligibly affects an adversary’s distinct, dishonest proof; the result reduces to one-time soundness.Source: §2.3 · pp. 13, 15, 16

2.4 Public verifiability in the oracle model

  • Naively publishing parameters lets queries on other instances expose arbitrary DecX oracles; signature tokens restrict access to one signed instance, and measure-and-reprogram reduces security to the fixed-instance setting.Strong unforgeability prevents alternate signatures from generating fresh parameter sets with different index patterns.Source: §2.4 · pp. 17–18
  • Public verification requires PFC binding when the committer accesses both DecZ and DecX but the opener accesses only DecZ; the known construction lacks this property.The overview presents a new publicly decodable commitment as completing non-interactive public verification for quantum partitioning circuits and the obfuscation construction.Source: §2.4 · p. 18

2.5 Pauli functional commitments with public decodability

  • The construction enlarges the hidden subspace to dimension n/2 so DecX can use membership in S⊥ without readily revealing S, then gates that oracle with a signature token so access ends after commitment.Its key includes a uniform superposition over a random affine subspace and a membership oracle for S⊥; the commitment is a signature on 1, while the oracle responds only to a valid signature on 0.Source: §2.5 · pp. 19–20
  • Binding is proved through oracle-query reductions and an inner-product adversary argument [AC12], with the key challenge being overlaps between projectors defined by an arbitrary rotation.The proof outline samples from a public ambient space, applies a worst-case-to-average-case reduction and amplitude amplification, then bounds how much queries can decrease expected inner products; the overlap condition differs from those in [AC12] [BS16].Source: §2.5 · pp. 20–21
  • Appendix B shows δ > ε^13 for R, sufficient for contradiction, and reduces the proof to the Welch bound, completing binding with public decodability.The Welch bound limits how many vectors with a given minimum distance can be packed into a low-dimensional Hilbert space.Source: §2.5 · p. 21

3 Preliminaries

This section establishes the quantum, cryptographic, and oracle-model foundations used in the paper, including security notions and tools for its obfuscation and verification constructions. It also presents strong unforgeability for an oracle-model signature-token scheme and notes its extension from single-bit to polynomial-size messages.

3 Preliminaries

  • The preliminaries use λ for the security parameter and define negligible, non-negligible, and polynomial functions, uniform sampling, and randomized-algorithm notation.Source: §3 · p. 21

3.1 Quantum information

  • Pseudo-deterministic circuits output a bit that is fixed with probability 1 − negl(λ) on each classical input, and trace distance bounds distinguishability of quantum states.The section also defines quantum states, operations, circuits, and oracle access.Source: §3.1 · p. 22

3.2 Obfuscation

  • Indistinguishability obfuscation requires correctness and indistinguishable obfuscations of functionally equivalent circuit families; virtual black-box obfuscation instead compares an adversary with an oracle simulator.Both definitions cover pseudo-deterministic quantum circuits as well as classical circuits.Source: §3.2 · p. 23

3.3 Dual-mode randomized trapdoor claw-free hash functions

  • Under QLWE, show existence of a dual-mode randomized trapdoor claw-free hash function, whose key-generation bit selects injective (0) or 2-to-1 (1) mode.Its supplied syntax specifies deterministic inversion and checking algorithms.Source: §3.3 · pp. 23–24

3.4 Quantum fully-homomorphic encryption

  • The defined QFHE encrypts classical messages with classical keys, evaluates quantum circuits on ciphertexts, and requires semantic security and evaluation correctness for pseudo-deterministic circuits.Such a scheme can be constructed from QLWE, as shown by Mahadev [Mah18] and Brakerski.Source: §3.4 · p. 25

3.5 Measure and re-program

  • The measure-and-reprogram simulator samples a 2q-wise independent oracle, measures a query, receives its replacement value, and may reprogram the oracle at that input.It then answers subsequent queries using the reprogrammed function; its runtime is at most poly(q, log |A|, log |B|) times the adversary’s runtime.Source: §3.5 · p. 26

3.6 Signature tokens

  • Signature tokens use a quantum signing key and classical verification key; oracle-model unforgeability forbids producing valid signatures for both bits, and strong unforgeability forbids distinct valid message-signature pairs.An oracle-model unforgeable scheme exists [BS16].Source: §3.6 · pp. 26–27
  • An oracle-model signature-token scheme achieves strong unforgeability via a proof tweak to [BS16], with duplicate-signature cases using target sets of distinct nonzero vectors in A or A⊥.The proof reduces failure to three cases; [BS16] already handles signatures valid for both 0 and 1.Source: §3.6 · p. 27
  • A single-bit signature-token scheme extends to polynomial-size messages by signing each bit with a separate invocation.Source: §3.6 · p. 28

4 Pauli Functional Commitments

Section 4 defines and constructs Pauli functional commitments supporting standard- and Hadamard-basis openings, and establishes their binding guarantees for bits and strings under the stated assumptions. Its proof rules out low-query commit/open strategies by reducing a binding violation to a query lower bound.

4.1 Definition

  • The definition specifies commitment and opening procedures with separate classical decoders for standard- and Hadamard-basis openings.Public decodability permits the committer to query both receiver decoding functionalities, but not the adversarial opener to query DecX.Source: §4.1 · pp. 28–29
  • Any Pauli functional commitment with single-bit binding with public decodability also has string binding with public decodability.The commitment supports openings corresponding to standard- or Hadamard-basis measurements of a committed qubit.Source: §4.1 · pp. 28, 30

4.2 Construction

  • The Fig. 3 Pauli functional commitment satisfies correctness, preserving the measurement distributions for standard- and Hadamard-basis openings.The scheme is described in the oracle model with a classical oracle CK and quantum commitment key state; post-quantum indistinguishability obfuscation can heuristically instantiate the oracle in the plain model.Source: §4.1 · p. 28, §4.2 · pp. 30, 32, 33

4.3 Binding

  • For n ≥ 130λ, the construction satisfies single-bit binding with public decodability, assuming Tok is unforgeable.The committer may access the receiver’s DecZ and DecX functionalities, but the adversarial opener is not given access to DecX.Source: §4.1 · p. 29, §4.3 · p. 33
  • The proof rules out commit/open unitaries making at most the stated query limit, establishing Claim 4.16 and completing the binding argument.Claim 4.16 suffices for Theorem 4.7.Source: §4.3 · pp. 37, 38, 40
  • Fixed-point amplitude amplification turns a violation of Claim 4.14 into a violation of Claim 4.16 while keeping the amplified strategy within the query limit.The proof implements the amplified commitment using oracle access to O[A] and O[A⊥].Source: §4.3 · pp. 37–38
  • An oracle-query lower bound from [AC12], combined with Theorem 4.20’s overlap bound for related affine-subspace states, contradicts the assumed query limit.The proof applies the bound to functionalities for balanced affine subspaces and their related pairs.Source: §4.3 · pp. 38–40

5 Verification of Quantum Partitioning Circuits

Section 5 develops verification of quantum partitioning circuits into classical and publicly verifiable protocols, proves public verification via a hybrid argument, and combines this framework with QFHE to construct publicly verifiable QFHE for pseudo-deterministic circuits in an oracle model.

5.1 Definition

  • The definition specifies a non-interactive public-verification protocol with a quantum proving key and classical functionality; its verifier returns samples or rejects, and Combine determines the output bit.Completeness and soundness are defined for pseudo-deterministic predicate-composed circuits.Source: §5.1 · pp. 40–41

5.2 QPIP1 verification

  • The QPIP1 protocol is a λ-wise parallel repetition of the quantum sampling verification protocol, verifying quantum partitioning circuits using only single-qubit standard- and Hadamard-basis measurements.Measuring certain registers of the history state in the standard basis yields an approximate sample from the output distribution; the state is the unique Hamiltonian ground state, enabling validity tests through its energy.Source: §5.2 · p. 41

5.3 Classical verification

  • Mahadev’s measurement protocol, parallel repetition, and Fiat–Shamir compile the information-theoretic protocol into a two-message, negligibly sound classical-verifier protocol in the quantum random oracle model.With r(λ)=λ^2 and k(λ)=λ, ΠCV also satisfies completeness and soundness, plus Din-if-accept and Dout-if-accepted-wrong-output properties.Source: §5.3 · pp. 42, 45

5.4 Public verification

  • Theorem 5.12 establishes that ΠPV is complete and sound, using a Pauli functional commitment, a strongly unforgeable signature-token scheme, and a superposition-secure pseudorandom function.The soundness proof uses hybrids and the commitment’s public string binding to separate Din and Dout cases, reducing the final case to ΠCV soundness.Source: §5.4 · pp. 45, 46, 48
  • Claim 5.14 states Pr[H0 = 1] = non-negl(λ), while Claim 5.15 states Pr[Hp = 1] = negl(λ); since p = poly(λ), the text says this contradicts both claims and completes the proof.Source: §5.4 · p. 51
  • The hybrid transition bound reduces to PFC string binding with public decodability, using the disjointness of the Din[P, b] and Dout[P, b] string sets.The proof defines the index subset S from the secret verification parameters and uses it to define these predicates.Source: §5.4 · pp. 52, 56

5.5 Application: Publicly-Verifiable QFHE

  • The application defines publicly-verifiable QFHE for pseudo-deterministic circuits in the oracle model, with evaluation and verification using a classical polynomial-time oracle PP.A heuristic plain-model instantiation obfuscates PP using post-quantum indistinguishability obfuscation.Source: §5.5 · pp. 56–57
  • The construction combines a QFHE scheme with publicly verifiable non-interactive classical verification for quantum partitioning circuits.Source: §5.5 · p. 57
  • For a ciphertext ct, it defines E[ct] to evaluate Q(·, y) homomorphically, then generates public verification keys and a public key for E[ct].Source: §5.5 · pp. 57–58
  • Public evaluation proves E[ct] on input y, then uses the verification functionality to combine the resulting ciphertexts and outputs (ect, π).Source: §5.5 · p. 58
  • Theorem 5.20 establishes that the construction satisfies Definition 5.19, with correctness, security, and soundness following from QFHE and PV guarantees.The proof derives correctness from QFHE evaluation correctness and PV completeness, security from QFHE semantic security, and soundness from QFHE correctness and PV soundness.Source: §5.5 · p. 58

6 Quantum Obfuscation

The construction combines a classical-circuit VBB obfuscator with publicly verifiable QFHE to obtain VBB obfuscation for pseudo-deterministic quantum circuits. It also applies the obfuscator to copy protection and functional encryption.

6.1 Construction

  • A classical-circuit VBB obfuscator and publicly-verifiable QFHE for pseudo-deterministic circuits are the construction’s two ingredients.Theorem 6.1 establishes that the resulting scheme is a VBB obfuscator; coherent evaluation and reversing allow reuse on polynomially many inputs.Source: §6.1 · p. 58

6.2 Application: Copy-protection

  • For γ-quantum-unlearnable circuit families, Protocol 9 gives copy protection with (γ(λ)−1/poly(λ))-anti-piracy security.The application generalizes the construction of [ALL+21] to pseudo-deterministic quantum circuits.Source: §6.2 · p. 60

6.3 Application: Functional encryption

  • The proposed construction is functionally encryption with indistinguishability security for polynomial-size pseudo-deterministic quantum functionalities.The construction uses public-key encryption, a statistically simulation sound NIZK proof system, and the obfuscated program as the decryption key’s evaluation procedure.Source: §6.3 · pp. 60, 62

A Remaining Proofs from Section 4.1

This appendix shows how binding properties of Pauli functional commitments relate: single-bit binding with public decodability implies string binding with public decodability. The proof proceeds through collapse binding and unique message binding.

A Remaining Proofs from Section 4.1

  • Single-bit binding with public decodability implies string binding with public decodability for Pauli functional commitments.The proof first derives collapse binding, then unique message binding, and uses both to establish string binding.Source: A Remaining Proofs from Section 4.1 · pp. 67, 69
  • Collapse binding compares whether decoding changes after a randomly selected measurement of the commitment’s state.The experiment measures with the projectors for bit 0 or bit 1, then checks whether the decoder outputs the sampled bit.Source: A Remaining Proofs from Section 4.1 · p. 68
  • Unique message binding requires that the commitment experiment output 1 only with negligible probability.Its adversary has access to the commitment’s decoding functionalities.Source: A Remaining Proofs from Section 4.1 · p. 68

B Remaining Proofs from Section 4.3

The proof reduces the higher-dimensional affine-subspace claim to a two-dimensional case by conditioning on a shared subspace. The reduction uses the stated dimension condition and the theorem’s state-support and overlap assumptions.

B Remaining Proofs from Section 4.3

  • The reduction’s dimension condition is n−d+1 > 10 log(1/ǫ)+6.The theorem considers states in Im(Π_A0) with overlap at least ǫ under Π_A1.Source: B Remaining Proofs from Section 4.3 · p. 69
  • The proof partitions pairs of affine subspaces by their shared (d−2)-dimensional subspace, then treats the induced spaces of cosets as a two-dimensional case.Each pair consists of six cosets of the shared subspace.Source: B Remaining Proofs from Section 4.3 · p. 69
  • For each fixed shared subspace, the proof represents the relevant affine spaces as unions of cosets whose vectors satisfy paired sum equalities.This representation supplies the structure used to identify the induced two-dimensional instance.Source: B Remaining Proofs from Section 4.3 · p. 70

B.1 Two-dimensional case

The two-dimensional proof shows that the assumed states cannot satisfy both the required support and overlap conditions when n exceeds the stated logarithmic threshold. Its strategy derives many separated states in a common low-dimensional subspace and contradicts a Welch-bound packing limit.

B.1 Two-dimensional case

  • The proof’s initial reduction assumes states lie in Im(Π_A0) while retaining at least ǫ overlap with Π_A1.The proof overview notes that imposing the overlap condition further restricts the expected inner product.Source: §B.1 · p. 71
  • The proof’s overview derives exponentially many states close to a common two-dimensional subspace, each with ǫ overlap with a different orthogonal subspace.A Welch bound limits how many sufficiently separated vectors can fit in a low-dimensional subspace.Source: §B.1 · p. 72
  • The construction bounds |A*₁| by 16/ε^10: each invocation selects at most 16/ε^2 vectors, while termination yields pairwise-overlap-separated states in a two-dimensional subspace, contradicting n > 10 log(1/ε) + 6.Source: §B.1 · p. 78

B.2 Useful facts

The appendix collects auxiliary vector facts, including bounds that transfer overlap and projector-norm information between nearby quantum states. It also uses three-vector dot-product bounds in an algebraic proof.

B.2 Useful facts

  • When two complex unit vectors have overlap at least 1 − α, Fact B.7 gives lower bounds on another vector’s overlap and on its projected norm.The displayed bound expressions are incomplete in the passage.Source: §B.2 · p. 79
  • The projector-norm argument selects a vector in the projector image and applies the preceding overlap bound.The passage says the first inequality follows from membership in the image, and the second from Fact B.7’s first part.Source: §B.2 · p. 79
  • For three unit vectors in R3, the appendix states upper and lower bounds on the sum of their pairwise dot products.The supplied passages state the bounds as ≤ 3 and ≥ 3, respectively.Source: §B.2 · p. 79

C Remaining Proofs from Section 5.3

The appendix derives the remaining proof claims by compiling a quantum verification protocol, applying parallel repetition, and then applying Fiat–Shamir. It carries the relevant lemmas through these steps, using the repetition theorem and Measure-and-Reprogram.

C Remaining Proofs from Section 5.3

  • The protocol ΠCCR compiles ΠQV into a four-message quantum commit-challenge-response protocol with a classical verifier, using Mahadev’s measurement protocol.The compilation is described as satisfying computationally orthogonal projectors, a property described in [ACGH20] and argued for in.Source: C Remaining Proofs from Section 5.3 · p. 81
  • Parallel repetition yields analogues of Lemmas 5.9–5.11, and Fiat–Shamir carries those claims to ΠCV.The final transfer uses Measure-and-Reprogram; the passage also notes the resulting argument is statistical, even when the adversary has secret parameters.Source: C Remaining Proofs from Section 5.3 · pp. 81, 85
  • The proof defines a commit-challenge-response protocol with a commitment, a random-bit challenge, a response, and verifier acceptance or rejection.The verifier receives z and outputs ⊤ on acceptance or ⊥ on rejection.Source: C Remaining Proofs from Section 5.3 · p. 81
  • The parallel-repetition theorem makes it negligible for a prover to pass all zero-challenge rounds and at least δλ one-challenge rounds.The theorem applies to a protocol with computationally orthogonal projectors and a publicly computable zero-challenge acceptance predicate.Source: C Remaining Proofs from Section 5.3 · p. 83
  • The Fiat–Shamir protocol computes the challenge T by hashing the prover’s first message y, and Measure-and-Reprogram transfers the parallel-protocol lemmas.The passage identifies ΠCV as Fiat–Shamir applied to Πparl.Source: C Remaining Proofs from Section 5.3 · pp. 81, 85
Loading 2302.11083v3…