Unconditionally Secure Commitments with Quantum Auxiliary Inputs

We show the following unconditional results on quantum commitments in two related yet different models:

1. We revisit the notion of quantum auxiliary-input commitments introduced by Chailloux, Kerenidis, and Rosgen (Comput. Complex. 2016) where both the committer and receiver take the same quantum state, which is determined by the security parameter, as quantum auxiliary inputs. We show that computationally-hiding and statistically-binding quantum auxiliary-input commitments exist unconditionally, i.e., without relying on any unproven assumption, while Chailloux et al. assumed a complexity-theoretic assumption, QIP ⊆ QMA. On the other hand, we observe that achieving both statistical hiding and statistical binding at the same time is impossible even in the quantum auxiliary-input setting. To the best of our knowledge, this is the first example of unconditionally proving computational security of any form of (classical or quantum) commitments for which statistical security is impossible. As intermediate steps toward our construction, we introduce and unconditionally construct post-quantum sparse pseudorandom distributions and quantum auxiliaryinput EFI pairs which may be of independent interest.

2. We introduce a new model which we call the common reference quantum state (CRQS) model where both the committer and receiver take the same quantum state that is randomly sampled by an efficient setup algorithm. We unconditionally prove that there exist statistically hiding and statistically binding commitments in the CRQS model, circumventing the impossibility in the plain model.

We also discuss their applications to zero-knowledge proofs, oblivious transfers, and multi-party computations.

As an application of our quantum auxiliary-input commitments, we plug them into Blum's Hamiltonicity protocol [Blu87] to obtain the following theorem.

Theorem 1.3. There exist zero-knowledge proofs for NP in the quantum auxiliary-input setting with nonuniform simulation (with quantum advice) and soundness error 1/2.

We can also use our quantum auxiliary-input commitments to instantiate the 3-coloring protocol of [GMR89] and the quantum Σ-protocol for QMA of [BG22]. On the other hand, unfortunately, we do not know how to instantiate the construction of OTs of [BCKM21] using our quantum auxiliary-input commitments. This is due to the fact that there may not be an efficient way to generate the quantum auxiliaryinput, which prevents us from applying Watrous' rewinding lemma [Wat09] that is used in the security proof in [BCKM21].

Commitments in the CRQS model. Our result on quantum auxiliary-input commitments is theoretically interesting. However, the fact that there is no efficient way to generate the quantum auxiliary input makes it unlikely to have uses in real-world applications. We therefore consider an alternative model that involves only efficiently generatable states. Specifically, we introduce a new notion that we call the common reference quantum state (CRQS) model, where an efficient setup algorithm randomly samples a classical key k and then distributes many copies of a (pure) quantum state |ψ k associated with the key k. It is a natural quantum analog of the common reference string model in classical cryptography.

At first glance, the CRQS model may look similar to the quantum auxiliary-input setting since in both settings, the committer and receiver receive some quantum state as a resource for executing the protocol. However, the crucial differences are that: