In this paper we show how to convert a statistically binding but computationally concealing quantum bit commitment scheme into a computationally binding but statistically concealing scheme. For a security parameter n, the construction of the statistically concealing scheme requires O(n^2) executions of the statistically binding scheme. As a consequence, statistically concealing but computationally binding quantum bit commitments can be based upon any family of quantum one-way functions. Such a construction is not known to exist in the classical world.
In this paper we show how to convert a statistically binding but computationally concealing quantum bit commitment scheme into a computationally binding but statistically concealing scheme. For a security parameter n, the construction of the statistically concealing scheme requires O(n^2) executions of the statistically binding scheme. As a consequence, statistically concealing but computationally binding quantum bit commitments can be based upon any family of quantum one-way functions. Such a construction is not known to exist in the classical world.
We provide a non-interactive quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any quantum one-way function. Our protocol is basically a parallel composition of the previous non-interactive quantum bit commitment schemes (based on quantum one-way permutations, due to Dumais, Mayers and Salvail (EUROCRYPT 2000)) with pairwise independent hash functions. To construct our non-interactive quantum bit commitment scheme from any quantum one-way function, we follow the procedure below: (i) from Dumais-Mayers-Salvail scheme to a weakly-hiding and 1-out-of-2 binding commitment (of a parallel variant); (ii) from the weakly-hiding and 1-out-of-2 binding commitment to a strongly-hiding and 1-out-of-2 binding commitment; (iii) from the strongly-hiding and 1-out-of-2 binding commitment to a normal statistically-hiding commitment. In the classical case, statistically-hiding bit commitment scheme (by Haitner, Nguyen, Ong, Reingold and Vadhan (SIAM J. Comput., Vol.39, 2009)) is also constructible from any one-way function. While the classical statistically-hiding bit commitment has large round complexity, our quantum scheme is non-interactive, which is advantageous over the classical schemes. A main technical contribution is to provide a quantum analogue of the new interactive hashing theorem, due to Haitner and Reingold (CCC 2007). Moreover, the parallel composition enables us to simplify the security analysis drastically.
We propose an efficient quantum protocol performing quantum bit commitment, which is a simple cryptographic primitive involved with two parties, called a committer and a verifier. Our protocol is non-interactive, uses no supplemental shared information, and achieves computational concealing and statistical binding under a natural complexity-theoretical assumption. An earlier protocol in the literature relies on the existence of an efficient quantum one-way function. Our protocol, on the contrary, exploits a seemingly weaker assumption on computational difficulty of distinguishing two specific ensembles of reduced quantum states. This assumption is guaranteed by, for example, computational hardness of solving the graph automorphism problem efficiently on a quantum computer.
Bit commitment is one of the cornerstones of both classical and quantum cryptography. In the classical world, security analysis is straightforward because both hiding and binding each admit a single natural interpretation. In the quantum world, however, security notions can be defined in different ways that are not necessarily equivalent. Over three decades, several works have introduced numerous binding notions whose precise statements and mu- tual implications remain scattered across the literature. This thesis clarifies that ambiguity. We study quantum binding notions within the framework of canonical purified quantum bit commitment (QBC) schemes, a class that captures both the theoretical generality and the practical mechanisms of recent constructions. In the statistical setting, we examine six binding notions: strong-binding, honest-binding, sum-binding, collapse-binding, extractor- binding, and arbitrary-binding. We prove that all these definitions except strong-binding are equivalent for the class of canonical purified schemes. In the computational setting, we establish that honest-binding, sum-binding, and collapse-binding are equivalent for the same class of schemes. Moreover, we introduce a quantitative framework based on the work of Ref. [26] to quantify the tradeoff between hiding and binding properties, and we use it to provide a geometric proof of the impossibility theorem of Mayers [21] and Lo & Chau [20], for canonical purified schemes. We next revisit the quantum notion of hiding, which is far less ambiguous than binding. Finally, we survey some technical tools that can be used to construct secure QBC schemes.
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction -- between quantum one-way functions and quantum hard-predicates -- is quantitatively more efficient than the known classical version. Roughly speaking, if the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n/epsilon^2) in the classical case but only by a factor of O(1/epsilon) in the quantum case, where 1/2 + epsilon is the probability of predicting the hard-predicate. Moreover, we prove via a lower bound that, in a black-box framework, the classical version of the reduction cannot have overhead less than order n/epsilon^2. We also show that, using this reduction, a quantum bit commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation. This complements a recent result by Dumais, Mayers and Salvail, where the bit commitment scheme is perfectly concealing and computationally binding. We also show how to perform qubit commitment by a similar approach.
Randomness certification aims to guarantee that the output of an untrusted quantum device contains genuine randomness that remains unpredictable even given quantum side information held by an adversary. For a classical verifier interacting with a single quantum device, such a guarantee cannot rely on the physical separation underlying standard Bell tests and must instead follow from computational restrictions on the prover. Building on the framework of Computational Bell Inequalities, we distinguish classical and quantum virtual-input hiding, showing that the former suffices for proofs of quantumness, whereas the latter enables randomness certification against quantum side information.
Our main technical contribution is to establish quantum virtual-input hiding for a commitment-based protocol derived from the proof of quantumness from one-way-functions by Morimae and Yamakawa. We show that statistical hiding together with ordinary computational binding against quantum polynomial-time senders suffices, without requiring stronger quantum binding notions such as sum-binding or collapse-binding. This yields a randomness-certification protocol from post-quantum statistically hiding bit commitments. In particular, existing constructions of such commitments from post-quantum one-way permutations imply that post-quantum one-way permutations suffice for randomness certification.
We further instantiate our construction using quantum-secure trapdoor claw-free functions, obtaining an efficient classical verifier, and in the quantum random oracle model, obtaining randomness certification without additional computational assumptions but with an inefficient verifier. These instantiations separate the cryptographic properties sufficient for randomness certification from the additional structure required for efficient verification within our commitment-based framework.
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction is quantitatively more ecient than the known classical version. If the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n=" ) in the classical case but only by a factor of O(1=") in the quantum case, where 2 + " is the probability of predicting the hard-predicate. We also show that, using the GoldreichLevin Theorem, a quantum bit (or qubit) commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation.