BRICS RS-00-52 Crépeau et al.: How to Convert a Flavor of Quantum Bit Commitment BRICS

Basic Research in Computer Science

How to Convert a Flavor of Quantum Bit Commitment

Claude Crépeau Frédéric Légaré Louis Salvail BRICS Report Series RS-00-52 ISSN 0909-0878 December 2000 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2000, Claude Crépeau & Frédéric Légaré & Louis

Salvail. BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/00/52/

How to Convert a Flavor of Quantum Bit Commitment

Claude Crépeau^{1}, Frédéric Légaré^{1}, and Louis Salvail^{2}

1 School of Computer Science, McGill University, {crepeau,legare}@cs.mcgill.ca 2 BRICS^{⋆ ⋆ ⋆}, Dept. of Computer Science,University of Århus, salvail@brics.dk

Abstract. 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.

1 Introduction

Finding the weakest computational assumptions from which the basic cryptographic primitives can be based upon is important for the theoretical foundations of cryptography. Protocols for secure 2-party computation are usually built from two basic and fundamental cryptographic primitives: Bit commitment and oblivious transfer. Classically, one-way functions are necessary and sufficient for secure bit commitment but not for oblivious transfer unless a major breakthrough in complexity theory[11, 13]. This suggests that in classical cryptography, bit commitment is a weaker primitive than oblivious transfer. Bit commitments come in two main flavors: binding but computationally concealing and concealing but computationally binding. Informally, binding means that whatever the committer does, it is impossible to open both 0 and 1 with non-negligible probability of success (this is sometimes called statistically binding). Concealing means that the receiver cannot obtain more than a negligible amount of information about the committed bit (i.e. statistically concealing). The weakest known computational assumption from

⋆ ⋆ ⋆ Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation.

which bit commitment can be based upon depends on its flavor. Binding but computationally concealing bit commitments can be based upon any one-way function [17, 12, 8]. On the other hand, the weakest known assumption for concealing but computationally binding commitments is the existence of one-way permutations [18]. It seems that in the classical world, unconditionally concealing commitments are more demanding than unconditionally binding ones. The two flavors allow for different cryptographic applications. For example, zero-knowledge proofs [9, 10] can be constructed from unconditionally binding commitments whereas perfect zero-knowledge arguments [3] require unconditionally concealing commitments. Arguments can be used whenever the verifier is not restricted in computing power and proofs can be used whenever the prover has unlimited computing power. Arguments are preferable in some settings, since a dishonest prover for an argument must break the complexity assumption on-line in order to prove a false theorem whereas a dishonest verifier involved in a computational zero-knowledge proof can spend unlimited time in order to extract additional knowledge.

In quantum cryptography, computational assumptions are also required for bit commitment and oblivious transfer [15, 16, 14]. The standard computational assumptions for the quantum case are defined as in the classical case except that they must resist quantum inverters. A quantum one-way function is simply a classical function f : {0, 1}^{n} → {0, 1}^{l(n)} for which given any x ∈ {0, 1}^{n}, f(x) can be efficiently computed by the quantum computer but finding x given f(x), (when x ∈_{R} {0, 1}^{n}) is hard. In [7], an unconditionally concealing quantum bit commitment scheme is built from any quantum one-way permutation. The resulting scheme although improving the communication complexity of the known classical protocols, requires the same kind of assumption than in the classical case. In this paper, we show that the computational assumption for concealing quantum bit commitment schemes can be weakened compared to its classical counterpart. Our result relies heavily upon the bbcs protocol for quantum 1-out-of-2 oblivious transfer of Bennett, Brassard, Crépeau, and Skubiszewska [2]. The bbcs protocol can be seen as a construction of quantum oblivious transfer from a black-box for bit commitment [5, 20]. Therefore and unlike the classical case, there exists a black-box reduction of quantum oblivious transfer to bit commitment.

Our main contribution consists in showing how any statistically binding quantum bit commitment scheme can be transformed into a statistically concealing one. The construction is obtained by using the bbcs protocol together with statistically binding but otherwise computationally concealing commitments (these commitments will be called initial commitments in the following). Using the bbcs protocol that way, we construct a simple quantum commitment scheme that we show statistically concealing and computationally binding. The construction converts the flavor of the initial commitments after calling them O(n^{2}) times for n a security parameter. As a byproduct, we show that the bbcs protocol is an oblivious transfer that statistically hides one out of the two bits sent and computationally conceals the receiver’s selection bit whenever it is used together with statistically binding but computationally concealing commitments instead of perfect commitments given as black-boxes. This extends the security result for the bbcs protocol of [2, 5, 20] to this case. Our reduction of an adversary for the concealing condition of the initial commitment scheme to an adversary for the binding condition of the resulting commitment scheme is is an expected polynomial-time black-box reduction. Although quantum information has peculiar behaviors adding complexity to the security proofs of cryptographic protocols, we shall see that using quantum oblivious transfer as a primitive allows to return to an essentially classical situation. This might be of independent interest for the construction and analysis of complex quantum protocols.

One consequence of our result is that statistically concealing but computationally binding quantum commitment scheme can be based upon any quantum one-way function using Naor’s construction [17] from pseudo-random generators. Only the ability to send and receive BB84 qubits is required in order to get the new flavor. The scheme can therefore be implemented using current technology. Our result gives more evidences that computational security in 2-party quantum cryptography enjoys different properties than its classical counterpart.

Paper’s Organization. We introduce tools and definitions in Sect. 2. The protocol by which the flavor of an originally binding but computationally concealing commitment is transformed into a concealing but computationally binding commitment is described in Sect. 3. The security proof of our construction is given in Sects. 4 and 5. In Sect. 4, we show that the resulting commitment is computationally binding if the original one was computationally concealing. We then prove in Sect. 5 that if the initial commitment scheme is binding then the resulting one is concealing. We finally conclude in Sect. 6.

2 Preliminaries

2.1 Tools

Let X ∼ B(p) be a Bernoulli random variable with probability of success p (when X = 1). The following simple argument will be useful:

Hybrid Argument. Let X = {X_{1}, X_{2}, …, X_{n}} be a set of independent random variables X_{i} ∼ B(p_{i}) for 1 ≤ i ≤ n. Then, there exist 1 ≤ k < n such that,

|p_{k+1} − p_{k}| ≥ \frac{|p_{n} − p_{1}|}{n}.  (1)

The result also holds without the absolute values. Later, we shall be given X without the values of the p_{i}’s but only a way of sampling in each X_{i} ∈ X and a guarantee that (1) holds for some k. The algorithms of Appendices B and C can then be used to estimate the p_{i}’s and find k′ satisfying a drop similar to (1).

2.2 Notations and Model of Computation

For simplicity, we shall often drop the security parameters associated with protocol executions. When protocols and adversaries are modeled as circuits they should be understood as infinite families of circuits, one circuit for each possible values of the security parameters. We write poly(n) for an arbitrary positive polynomial.

The basis {|0⟩, |1⟩} denotes the computational or rectilinear or “+” basis for H_{2}. When the context requires, we write |b⟩_{+} to denote the bit b in the rectilinear basis. The diagonal basis, denoted “×”, is defined as \{|0⟩_{×}, |1⟩_{×}\} where |0⟩_{×} = \frac{1}{\sqrt{2}}(|0⟩ + |1⟩) and |1⟩_{×} = \frac{1}{\sqrt{2}}(|0⟩ − |1⟩). The states |0⟩, |1⟩, |0⟩_{×} and |1⟩_{×} are the four BB84 states. For any x ∈ {0, 1}^{n} and θ ∈ {+, ×}^{n}, the state |x⟩_{θ} is defined as ⊗_{i=1}^{n}|x_{i}⟩_{θ_{i}}. An orthogonal (or Von Neumann) measurement of a quantum state in H_{m} is described by a set of m orthogonal projections M = {ℙ_{i}}_{i=1}^{m} acting in H_{m} thus satisfying ∑_{i} ℙ_{i} = 11_{m} for 11_{m} denoting the identity operator in H_{m}. Each projection or equivalently each index i ∈ {1, …, m} is a possible classical outcome for M.

We modeled quantum algorithms by quantum circuits built out of an universal set of quantum gates UG = {CNot, H, R_{ℚ}}, where CNot denotes the controlled-not, H the one qubit Hadamard gate, and R_{ℚ} is an arbitrary one qubit non-trivial rotation specified by a matrix containing only rational numbers [1]. The time-complexity of a quantum circuit C is the number of elementary gates ∥C∥_{UG} in C. In addition to the set of gates UG, a quantum circuit is allowed to perform one kind of Von Neumann measurement: M_{+} = {ℙ_{0}^{+}, ℙ_{1}^{+}} where ℙ_{0}^{+} = |0⟩⟨0| and ℙ_{1}^{+} = |1⟩⟨1| are the two orthogonal projections of the computational basis. M_{+} is sometimes called the measurement in the rectilinear or computational basis. Another Von Neumann measurement that is used by the receiver in the BB84 quantum coding scheme is the measurement in the diagonal basis M_{×} = {ℙ_{0}^{×}, ℙ_{1}^{×}} where ℙ_{0}^{×} = \frac{1}{2}(|0⟩ + |1⟩)^{†}(|0⟩ + |1⟩) and ℙ_{0}^{×} = \frac{1}{2}(|0⟩ − |1⟩)^{†}(|0⟩ − |1⟩). The Hadamard gate H is sufficient to build measurement M_{×} ∈ UG from M_{+} since M_{×} = {H^{†}ℙ_{0}^{+}H, H^{†}ℙ_{1}^{+}H}. If |Ψ⟩ ∈ H_{A} ⊗ H_{B} is a composite quantum state, we write ℙ_{x}^{A}|Ψ⟩ for the projector applied to the registers in H_{A} along the state |x⟩ for x ∈ {0, 1}^{Dim(H_{A})}. The classical output L(|Ψ⟩) of circuit L is the classical outcomes of all Von Neumann measurements M_{+} taking place during the computation L|Ψ⟩. If the circuit L accepts two input states of the form |Ψ_{0}⟩ ⊗ |Ψ_{1}⟩ we may write similarly L(|Ψ_{0}⟩, |Ψ_{1}⟩) for the classical output.

A 2-party quantum protocol is a pair of interactive quantum circuits (A, B) applied to some initial product state |x_{A}⟩^{A} ⊗ |x_{B}⟩^{B} representing A’s and B’s inputs to the protocol neglecting to write explicitly the states of A’s and B’s registers that do not encode their respective input to the protocol (thus all in initial states |0⟩). Since communication takes place between A and B, the complete circuit representing one protocol execution may have quantum gates in A and B acting upon the same quantum registers. We write A ⊙ B the complete quantum circuit when A is interacting with B. The final composite state |Ψ_{final}⟩ obtained after the execution is written |Ψ_{final}⟩ = (A ⊙ B)|x_{A}⟩^{A}|x_{B}⟩^{B}. Protocols are to be understood, although not explicitly stated, as specified by families of circuits, one for each possible value of the security parameter n. If for a participant (adversary) P given 1^{n} as input there exists a classical Turing machine that efficiently computes the description of the circuit P_{n} to be run for security parameter n then P is said to be a uniform participant (adversary); that is P is modeled by a uniform family of quantum circuits. Otherwise, P is said to be non-uniform.

2.3 Cryptographic Primitives

The two relevant quantum primitives we shall use heavily in the following are quantum bit commitment and quantum oblivious transfer. They are defined as straightforward quantum generalizations of their classical counterparts.

Quantum Bit Commitment. A quantum bit commitment scheme is defined by two quantum protocols ((C^{A}, C^{B}), (O^{A}, O^{B})) where (C^{A}, C^{B}) is a pair of interactive quantum circuits for the committing stage and (O^{A}, O^{B}) is a pair of interactive quantum circuits for the opening stage (i.e. A being the committer and B the receiver). The committing stage generates the state |Ψ_{b}⟩ = (C^{A} ⊙ C^{B})|b⟩^{A}|0⟩^{B} upon which the opening stage is executed: |Ψ_{final}⟩ = (O^{A} ⊙ O^{B})|Ψ_{b}⟩. The binding condition of a quantum bit commitment is slightly more general than the usual classical definition. An adversary Ã = (CÃ, OÃ) is such that |Ψ̃⟩ = (CÃ ⊙C^{B})|0⟩Ã is generated during the committing stage. The dishonest opening circuit OÃ tries to open b ∈_{R} {0, 1} given as an extra input bit |b⟩Ã. Given the final state |Ψ̃_{final}⟩ = (OÃ ⊙ O^{B})|b⟩^{A}|Ψ̃⟩ we define s_{b}(n) as the probability to open b with success. More precisely, s_{b}(n) = ∥ℙ_{OK,b}^{B}|Ψ̃_{final}⟩∥^{2} where ℙ_{OK,b}^{B} is Bob’s projection operator on the subspace leading to accept the opening of b. An adversary Ã of the binding condition who can open b = 0 with probability at least s_{0}(n) and open b = 1 with probability at least s_{1}(n) will be called a (s_{0}(n), s_{1}(n))–adversary against the binding condition. We define the concealing and binding criteria similarly to [7]:

(computationally) binding: There exists no quantum (s_{0}(n), s_{1}(n))– adversary Ã where for some positive polynomial p(n), and sufficiently large n’s, s_{0}(n) + s_{1}(n) ≥ 1 + \frac{1}{p(n)}. The scheme is computationally binding if we add the restriction that ∥Ã∥_{UG} ∈ O(poly(n)).

(computationally) concealing: For every interactive quantum circuit C̃^{B} for the committing stage, all quantum circuits LB̃ acting only upon B̃’s registers, all positive polynomials p(n) and sufficiently large n’s, P (LB̃((C^{A} ⊙ CB̃)|b⟩^{A}|0⟩B̃) = b) < \frac{1}{2} + \frac{1}{p(n)} where the probabilities are taken over b ∈_{R} {0, 1}. The scheme is computationally concealing if we add the restriction ∥CB̃∥_{UG} + ∥LB̃∥_{UG} ∈ O(poly(n)).

What we call concealing and binding is in fact statistically concealing and statistically binding respectively and not perfectly concealing and perfectly binding.

Quantum Oblivious Transfer. In the following, we shall restrict our attention to 1–2 quantum oblivious transfer (i.e. one-out-of-two oblivious transfer)[2, 6]. A 1–2 quantum oblivious transfer protocol involves a sender Alice holding input bits (b_{0}, b_{1}) and a receiver Bob holding input c ∈ {0, 1}. Alice sends (b_{0}, b_{1}) to Bob in such a way that Bob receives only b_{c} and Alice does not get to know c. The receiver must not be able to find b\overline{c} for at at least one \overline{c} ∈ \{0, 1\} and even given b_{c}. More precisely, a protocol (A, B) for 1–2 quantum oblivious is such that |Ψ(b_{0}, b_{1}, c)⟩ = (A ⊙ B)|b_{0}; b_{1}⟩^{A}|c⟩^{B} allows Bob to recover b_{c} from applying M_{+} upon one of his registers. A protocol for 1–2 quantum oblivious transfer is (computationally) secure if it is both

(computationally) secure against the sender: For every quantum sender Ã, all quantum circuit LÃ acting only on Ã’s registers, all positive polynomials p(n) and sufficiently large n’s, P (LÃ((Ã ⊙ B)|0; 0⟩Ã|c⟩^{B}) = c) < \frac{1}{2} + \frac{1}{p(n)} where the probabilities are taken over c ∈_{R} {0, 1}. The protocol is computationally if we add the restriction ∥LÃ∥_{UG} + ∥Ã∥_{UG} ∈ O(poly(n)).

(computationally) secure against the receiver: For every quantum receiver B̃, all quantum circuits LB̃ acting only on B̃’s registers, all positive polynomials p(n) and sufficiently large n’s, there exists c ∈ \{0, 1\}, P (LB̃((A ⊙ B̃)|b_{0}; b_{1}⟩^{A}|0⟩B̃, |b_{c}; c⟩B̃) = bc̄) < \frac{1}{2} + \frac{1}{p(n)} where the probabilities are taken over b_{0}, b_{1} ∈_{R} {0, 1}. The security is computational if we add the restriction ∥B̃∥_{UG}+∥LB̃∥_{UG} ∈ O(poly(n)).

As for bit commitment, the security against the sender and the security against the receiver is not perfect but statistical.

3 The protocols

In this section, we first describe the bbcs protocol for 1-2 oblivious transfer [2] which is the basis of our result. Then, we describe our quantum bit commitment scheme qbc, using bbcs as a sub-protocol, that transforms any (statistically) binding bit commitment scheme into a (statistically) concealing one. Throughout this paper, we assume for simplicity that quantum transmission is error-free.

3.1 The bbcs Protocol For 1 − 2 Quantum Oblivious Transfer

The bbcs protocol [2] is based upon the BB84 quantum coding scheme. If the receiver (Bob) of a random BB84 qubit |s⟩_{β}, s ∈_{R} {0, 1}, β ∈_{R} {+, ×} is forced to measure it in basis β̂ ∈_{R} {+, ×} upon reception, then a noisy classical communication of bit s from Alice to Bob is implemented. Moreover, if later on Alice announces β, then Bob knows that he received s whenever β = β̂ and an uncorrelated bit whenever β ≠ β̂. The bbcs protocol amplifies this process in order to get a secure 1–2 oblivious transfer. In order to ensure that Bob measures the BB84 qubits upon reception, bit commitments are required. Bob commits upon each measurement and outcome right after the quantum transmission. Alice then verifies in random positions that Bob has really measured the transmitted qubits by testing that whenever β = β̂ then Bob’s classical outcome r ∈ {0, 1} is such that r = s.

In the following, we assume that Alice and Bob have access to some bit commitment scheme BBC in order for Bob to commit upon the measurements of the received qubits together with their outcomes. Since the two commitments are made together, we write BBC(x, y), x, y ∈ {0, 1} for the commitments of both the measurement and the outcome. This simply means 2 sequential executions of BBC, one for the commitment of x and the other the commitment of y. BBC may be given as a black-box for bit commitment or may be provided from some computational assumption. We denote by the Open-BBC(x, y) the opening stage of BBC(x, y). Protocol bbcs(b_{0}, b_{1})(c) achieves the oblivious transfer of bit b_{c}:

Protocol 1 ( bbcs(b_{0}, b_{1})(c) )

1: For 1 ≤ i ≤ 2n

– Alice picks s_{i} ∈_{R} {0, 1}, β_{i} ∈_{R} {+, ×}

– Alice sends to Bob a qubit π_{i} in state |s_{i}⟩_{β_{i}}

– Bob picks a basis β̂_{i} ∈_{R} {+, ×}, measures π_{i} in basis β̂_{i}, and obtains the outcome r_{i} ∈ {0, 1}

2: For 1 ≤ i ≤ n

– Bob runs BBC(r_{i}, β̂_{i}) and BBC(r_{n+i}, β̂_{n+i}) with Alice

– Alice picks f_{i} ∈_{R} {0, 1} and announces it to Bob

– Bob runs Open-BBC(r′_{nf_{i}+i}, β̂_{nf_{i}+i})

– Alice verifies that β_{nf_{i}+i} = β̂_{nf_{i}+i} ⇒ s_{nf_{i}+i} = r_{nf_{i}+i}, otherwise she rejects the current execution

– if f_{i} = 0 then Alice sets β_{i} ← β_{n+i} and s_{i} ← s_{n+i} and Bob sets β̂_{i} ← β̂_{n+i} and r_{i} ← r_{n+i}

3: Alice announces her choices of bases β_{1}, β_{2}, …, β_{n} to Bob

4: Bob announces two subsets of positions J_{0}, J_{1} ⊂ {1, 2, …, n}, |J_{0}| = |J_{1}| =

\frac{n}{3} , J_{0} ∩ J_{1} = ∅, and ∀i ∈ J_{c}, β_{i} = β̂_{i}.
5: Alice computes and announces b̂_{0} = ⨁_{j∈J_{0}} s_{j} ⊕ b_{0} and b̂_{1} = ⨁_{j∈J_{1}} s_{j} ⊕ b_{1}
6: Bob receives ⟨b̂_{0}, b̂_{1}⟩ then computes b_{c} = ⨁_{i∈J_{c}} r_{i} ⊕ b̂_{c}

Known Security Results. The correctness and the security of the bbcs protocol against the sender (Alice) has been reduced to the security of BBC in [2, 5]. The security against the receiver (Bob) has been provided by Yao in [20] given the security of the commitment scheme BBC. That is, given BBC is a perfect black-box for bit commitment then bbcs is secure against any dishonest Bob irrespectively of his computing power.

3.2 Quantum Bit Commitment Using bbcs

Given a binding but computationally concealing bit commitment scheme BBC in bbcs the following commitment scheme will be shown concealing and computationally binding.

Protocol 2 ( qbc(b) )

1: qbc-commit(b)

– For 1 ≤ j ≤ n • Alice prepares a_{0j} ∈_{R} {0, 1} and a_{1j} = a_{0j} ⊕ b

• Bob prepares c_{j} ∈_{R} {0, 1}

• Alice and Bob execute bbcs(a_{0j}, a_{1j})(c_{j}) and Bob receives the result d_{j} 2: qbc-open(b)

• Alice announces b

• For 1 ≤ j ≤ n • Alice announces a_{0j} and a_{1j}

• Bob verifies that b = a_{0j} ⊕ a_{1j} and d_{j} = a_{c_{j} j}

A commitment to bit b is done by sending through 1–2 oblivious transfer n pairs if bits {(a_{0j}, a_{1j})}_{j=1}^{n} such that a_{0j} ⊕ a_{1j} = b. The concealing condition is guaranteed by the security of oblivious transfer against the receiver and the binding condition is guaranteed by the security against the sender. Proving the security of qbc reduces to showing that the bbcs protocol remains secure whenever computationally concealing but binding commitments are used instead of classical black-boxes [5, 20].

More Notations. In the following we shall have to identify the variables generated during all calls to bbcs in qbc. For that purpose, we use the following notation:

– π_{i}^{j} is the i-th qubit sent in the j-th call to bbcs in qbc.

– β_{i}^{j} ∈ {+, ×} is the basis β_{i} announced by Alice during the j-th execution of bbcs in qbc.

– β̂_{i}^{j} ∈ {+, ×} is the basis used by Bob to measure π_{i}^{j} in the j-th call to bbcs.

– r_{i}^{j} ∈ {0, 1} is the outcome of Bob’s measurement of π_{i}^{j} in basis β̂_{i}^{j}.

– r̂_{i}^{j} ∈ {0, 1} is Carl’s outcome for measurement of π_{i}^{j} in basis β_{i}^{j}.

– J^{j} = (J_{0}^{j}, J_{1}^{j}) is the two sets of positions announced by Bob in the j-th execution of bbcs.

We denote by bold lowercases the values for all executions at one glance: β = {β_{i}^{j}}_{i,j}, β̂ = {β̂_{i}^{j}}_{i,j}, r = {r_{i}^{j}}_{i,j}, and r̂ = {r̂_{i}^{j}}_{i,j}. We denote by b̂_{0} = b̂_{0}^{1}, …, b̂_{0}^{n} and b̂_{1} = b̂_{1}^{1}, …, b̂_{1}^{n} the bits announced by Alice at step 5 of each call to bbcs. Similarly, we denote by a = (a_{0}, a_{1}) = (a_{01}, a_{11}), (a_{02}, a_{12}), …, (a_{0n}, a_{1n}) ∈ {0, 1}^{2n} Alice’s announcements during the opening stage. We also denote J_{0} = J_{0}^{1}, …, J_{0}^{n} and J_{1} = J_{1}^{1}, …, J_{1}^{n} all sets announced by Bob and we write J = (J_{0}, J_{1}). Let c = c_{1}, …, c_{n} be all selection bits used by Bob and let d = d_{1}, …, d_{n} be all bits received by bbcs. We write J_{c} = J_{c_{1}}^{1}, J_{c_{2}}^{2}, …, J_{c_{n}}^{n} for all set of positions corresponding to qubits measured by Bob in bases announced by Alice.

4 The Binding Condition

In the following sections, we show that qbc is secure against any Alice (the sender) who cannot break the concealing condition of the inner commitment scheme BBC used in the calls to bbcs in order for Bob to commit on his measurements and measurement outcomes.

Simplified Version of bbcs. In our analysis of the binding condition of qbc, we shall assume that the opening of half of the commitments in step 2 of bbcs doesn’t occur. The opening of the commitments allows Alice to make sure that Bob measured the qubits received in bbcs upon reception. This test is not relevant to the binding condition of qbc.

Protocol 3 ( bbcs^{∗}(b_{0}, b_{1})(c) )

1: ...step 1 of protocol 3.1

2: For 1 ≤ i ≤ n

– Bob runs BBC(r_{i}, β̂_{i}) and BBC(r_{n+i}, β̂_{n+i}) with Alice

– Alice picks f_{i} ∈_{R} {0, 1} and announces it to Bob

– if f_{i} = 0 then Alice sets β_{i} ← β_{n+i} and s_{i} ← s_{n+i} and Bob sets β̂_{i} ← β̂_{n+i} and r_{i} ← r_{n+i}

3–6: ...as steps 3 to 6 in protocol 3.1

We omit the proof of the following simple lemma:

Lemma 1. If bbcs^{∗} is secure against the sender then bbcs is secure against the sender.

Throughout Sect. 4, we shall assume tacitly calls to bbcs^{∗} in qbc instead of calls to bbcs. This simplifies the analysis and according to lemma 1, it can be done without lost of generality.

4.1 How to Prove the Binding Condition

In order to show that qbc is computationally binding, we introduce intermediary protocols that will allow us to bridge the security of the qbc protocol with the known security of bbcs given black-boxes for bit commitments. Let’s consider the following four modified protocols:

u-bbcs: Protocol bbcs except that in step 2, Bob commits to random values. In other words, for 1 ≤ i ≤ n, Bob runs BBC(u_{0i}, u_{1i}) and BBC(u_{2i}, u_{3i}) with u_{0i}, u_{1i}, u_{2i}, u_{3i} ∈_{R} {0, 1}.

m-bbcs: The same as u-bbcs but a third party, for 1 ≤ i ≤ n, intercepts the ith qubit π_{i} sent by Alice in step 1, measures in basis β_{i} and sends the resulting state to Bob.

u-qbc: Protocol qbc using u-bbcs. m-qbc: Protocol qbc using m-bbcs.

The security against any dishonest sender in u-bbcs and m-bbcs is a direct consequence of the analysis provided in [5]. Since the commitments upon measurements do not carry any information about Bob’s measurement, Alice cannot obtain any information about his selection bit c. The security is information-theoretic, no complexity assumption on Alice’s computing power is required.

We reduce the security of the binding condition of qbc to the security of the concealing condition of BBC in two steps:

1. Using Lemmas 2 and 3, we conclude in Lemma 4 that u-qbc is binding. The modified protocol m-qbc is used for reducing the security of u-qbc to the security of u-bbcs. Carl’s presence allows to classicize the analysis which becomes simpler than working from u-qbc directly.

2. Theorem 1 establishes the desired result using the fact that an adversary for the binding condition of qbc cannot be an adversary of u-qbc (Lemma 4). It is shown how to construct an adversary for the concealing condition of BBC given an adversary for the binding condition of qbc.

4.2 Part 1

In this section, we show that u-qbc is binding (Lemma 4) using Lemmas 2 and 3 as intermediary steps.

First, we show that an adversary against the binding condition of uqbc can be transformed into an adversary against the binding condition of m-qbc.

Lemma 2. If there exist a (s_{0}(n), s_{1}(n))-adversary Ã against the binding condition of u-qbc there also exists a (s_{0}(n), s_{1}(n))-adversary A^{∗} against the binding condition of m-qbc.

Proof. We observe first that Ã’s announcement of β at step 3 of u-bbcs commutes with step 2. That is, since only commitments to random values are received by Ã, the measurement producing β can be performed without Bob’s commitments. Ã could simulate the commitments on her own and then execute the measurement producing β before the qubits are sent to Bob at step 1. Let A^{∗} be the quantum adversary that does that. If Ã provides a (s_{0}(n), s_{1}(n))–advantage in u-qbc then so it is for A^{∗}. We now show that A^{∗} is also an adversary for the binding condition of m-qbc.

Now assume for simplicity and without loss of generality that, Bob in u-qbc or Bob and Carl in m-qbc wait until after Alice announces a = (a_{0}, a_{1}) before measuring all qubits received. It is easy to verify that this can always be done since nothing in the committing stage of u-qbc or mqbc relies on those measurements’ outcomes (i.e. since the commitments are made to random values). Clearly, postponing measurements do not influence Alice’s probability of success at the opening stage. Let V = (β, J, b̂_{0}, b̂_{1}, c, a) be the partial view in u-qbc or in m-qbc up to Alice’s announcement of a (and b since for all 1 ≤ j ≤ n, a_{j0} ⊕ a_{j1} = b) in the opening stage. Let V_{U} and V_{M} be the random variable for the partial view in u-qbc and m-qbc respectively. By construction we have that for all V = (β, J, b̂_{0}, b̂_{1}, c, a), P (V_{U} = V) = P (V_{M} = V). Moreover, we have that for all partial views V, the joint states |Ψ_{U}(V)⟩ for u-qbc and |Ψ_{M}(V)⟩ for m-qbc satisfy |Ψ_{U}(V)⟩ = |Ψ_{M}(V)⟩. Let V_{b} = {(β, J, b̂_{0}, b̂_{1}, c, a)|(∀1 ≤ j ≤ n)[a_{j0} ⊕ a_{j1} = b]} be the set of partial views corresponding for Alice to open bit b. Given V, Bob’s test will succeed if he gets d = a_{c} = a_{1c_{1}}, a_{2c_{2}}, …, a_{nc_{n}} after measuring the qubits in positions in J_{c} using Alice’s bases β_{i}^{j} for all i ∈ J_{c_{j}}^{j}. Let M_{test}(V) = {ℚ_{ok}^{V}, 11 − ℚ_{ok}^{V}} be the measurement allowing Bob to test Alice’s announcement when she unveils b given partial view V ∈ V_{b}. ℚ_{ok}^{V} is the projection for the state of all qubits received in positions in J_{c} into the subspace corresponding to parity d_{j} = a_{jc_{j}} for all j ∈ {1, …, n}. More precisely, ℚ_{ok}^{V} = ⨂_{j=1}^{n} ∑_{x∈T (V,j)} ℙ_{x}^{β(V, j)}

where T (V, j) = {x ∈ {0, 1}^{#J_{c_{j}}^{j}} | ⊕_{i} x_{i} = a_{jc_{j}} ⊕ b̂_{c_{j}}^{j}} and β(V, j) = {β_{i}^{j}|i ∈ J_{c_{j}}^{j}} for all j ∈ {1, …, n}. Let s′_{b}(b) be the probability of success when A^{∗} opens b in m-qbc. We get that

s_{b}(n) = ∑_{V ∈V_{b}} P (V_{U} = V) ∥ℚ_{ok}^{V}|Ψ_{U}(V)⟩∥^{2}
= ∑_{V ∈V_{b}} P (V_{M} = V) ∥ℚ_{ok}^{V}ℚ_{ok}^{V}|Ψ_{M}(V)⟩∥^{2} = s′_{b}(n)  (2)

since the only difference between u-qbc and m-qbc is that in the former case both Carl and Alice measure the qubits in positions in J_{c} with the same measurement M_{test} (this why we have ℚ_{ok}^{V}ℚ_{ok}^{V} = ℚ_{ok}^{V} in (2)). Carl’s measurements for positions in J\overline{c} are irrelevant to the success probability. The result follows. ⊓ ⊔

Next, we reduce the binding condition of m-qbc to the security against the sender in m-bbcs. We show that from any successful adversary against the binding condition of m-qbc one can construct an adversary able to extract non-negligible information about Bob’s selection bit in m-bbcs. Carl’s measurements in m-qbc allows to classicize most part of the reduction thus simplifying the proof that u-qbc is binding.

Lemma 3. If there exists a (s_{0}(n), s_{1}(n))-adversary Ã = (CÃ, OÃ) against the binding condition of m-qbc with s_{0}(n) + s_{1}(n) ≥ 1 + \frac{1}{p(n)} for some positive polynomial p(n), then there also exists a cheating sender A^{∗} for m-bbcs.

Proof. Let a′_{j0} and a′_{j1} be the two input bits for the j-th call to m-bbcs computed according to Carl’s outcomes r̂. Let V be the random variable for the joint view (a, a′, d, c) for an execution of the committing and the opening stages of m-qbc between Ã and an honest receiver B and where Ã is opening a random bit b ∈_{R} {0, 1}. Without loss of generality, we assume the announcements made by Ã to be consistent, that is a_{0i} ⊕ a_{1i} = b for 1 ≤ i ≤ n when she opens bit b. Given V = (a, a′, d, c), we define the ordered set S(V) = {j|a′_{j0} ⊕ a′_{j1} ≠ a_{j0} ⊕ a_{j1}} ⊆ {1, …, n} of calls to m-bbcs for which given view V Alice’s announcement of a disagree with Carl’s outcomes a′. Given the ordered set S(V) = {σ_{1}, σ_{2}, …, σ_{s}}, let X_{j}(V) ∈ {0, 1} for 1 ≤ j ≤ s be defined as

X_{j}(V) = \begin{cases}0 & if d_{σ_{j}} ≠ a_{σ_{j}c_{σ_{j}}} \\ 1 & if d_{σ_{j}} = a_{σ_{j}c_{σ_{j}}} . \end{cases}

We let X(V) = X_{1}(V), …, X_{l(V)}(V) for l(V) = min (|S(V)|, ⌈\frac{n}{2}⌉). Clearly, for Ã to open with success given V, we must have X(V) = 1^{l(V)}. Note that P (|S(V )| ≥ \frac{n}{2}) ≥ \frac{1}{2} since for at least one choice of b, |S(V )| ≥ \frac{n}{2} given that V always describes a consistent opening. We easily get that

P (X(V ) = 1^{⌈ \frac{n}{2} ⌉}) = P (X(V ) = 1^{l(V)}) − P (X(V ) = 1^{l(V)} ∧ l(V ) < \frac{n}{2})
≥ \frac{1}{2}(s_{0}(n) + s_{1}(n)) − \frac{1}{2}P (X(V ) = 1^{l(V)} | l(V ) < \frac{n}{2})
≥ \frac{1}{2p(n)}.  (3)

Since ∑_{x∈\{0,1\}^{⌈ \frac{n}{2} ⌉}} P (X(V ) = x) = 1, for n sufficiently large there

exists a string ŷ^{0} ∈ \{0, 1\}^{⌈ \frac{n}{2} ⌉} such that P (X(V ) = ŷ^{0}) ≤ \frac{1}{4p(n)}. Let ρ be the number of zeros in ŷ^{0} and R(ŷ^{0}) = \{r_{1}, r_{2}, …, r_{ρ}\} ⊆ \{1, …, ⌈\frac{n}{2}⌉\} be the ordered set of positions 1 ≤ r ≤ ⌈\frac{n}{2}⌉ where ŷ_{r}^{0} = 0. We now define for 1 ≤ j ≤ ρ the hybrid strings ŷ^{j} = ŷ_{1}^{j}ŷ_{2}^{j} … ŷ_{⌈ \frac{n}{2} ⌉}^{j} between ŷ^{0} and 1^{⌈ \frac{n}{2} ⌉}:

ŷ_{i}^{j} = \begin{cases}1 & if i = r_{k} for k ≤ j \\ ŷ_{i}^{0} & Otherwise. \end{cases}

Hence, P (X(V ) = ŷ^{ρ} = 1^{n}) − P (X(V ) = ŷ^{0}) ≥ \frac{1}{4p(n)} and we conclude by a hybrid argument that there exist 1 ≤ k^{∗} ≤ ρ such that

P (X(V ) = ŷ^{k^{∗}}) − P (X(V ) = ŷ^{k^{∗}−1}) ≥ \frac{1}{ρ4p(n)} ≥ \frac{1}{2(n + 1)p(n)} (4)

Note that ŷ^{k^{∗}} and ŷ^{k^{∗}−1} differs only by the bit in position r_{k^{∗}} where they respectively have a 1 and a 0.

A^{∗} uses Ã and B = (C^{B}, O^{B}) the following way: after choosing h ∈_{R} {1, …, n}, it lets Ã interact with a simulated honest receiver B for m-qbc except for the h-th execution of m-bbcs for which Ã interacts with the targeted receiver for m-bbcs. Let V = (a, a′, d, c) be the view generated during the execution. Given A^{∗}’s view, algorithm L^{A^{∗}} produces a guess c̃ for Bob’s selection bit c = c_{h} in m-bbcs as follows:

– If |S(V)| ≥ ⌈\frac{n}{2}⌉, h = σ_{r_{k^{∗}}} and ∀i ∈ \{1, …, ⌈\frac{n}{2}⌉\} \ \{r_{k^{∗}}\}, X_{i}(V) = ŷ_{i}^{k^{∗}}, then c̃ ∈ {0, 1} is defined such that a_{hc̃} = a′_{hc̃} (which necessarily exists since h ∈ S(V)),

– Otherwise, c̃ ∈_{R} {0, 1}.

Let T (V) be the event of a successful test in the previous computation. We have that P (T (V )) ≥ (P (X(V ) = ŷ^{k^{∗}}) + P (X(V ) = ŷ^{k^{∗}−1})) /2n since independently |S(V)| ≥ n/2 with probability at least 1/2, h = σ_{r_{k}^{∗}} with probability 1/n, and ∀i ∈ \{1, …, ⌈\frac{n}{2}⌉\} \ \{r_{k^{∗}}\}, X_{i}(V) = ŷ_{i}^{k^{∗}} with probability P (X(V ) = ŷ^{k^{∗}}) + P (X(V ) = ŷ^{k^{∗}−1}). Given T (V), the guess c̃ is the only value for Bob’s selection bit c that would lead to X(V) = ŷ^{k^{∗}} instead of X(V) = ŷ^{k^{∗}−1} (the two strings are the only possible given T (V)). We get P (c̃ = c|T (V )) = P (X(V ) = ŷ^{k^{∗}}) / (P (X(V ) = ŷ^{k^{∗}}) + P (X(V ) = ŷ^{k^{∗}−1})). (A^{∗}, L^{A^{∗}}) is a cheating sender for m-bbcs since P (c̃ = c) = \frac{1}{2}(1 − P (T (V ))) + P (T (V )) P (c̃ = c|T (V )) ≥ \frac{1}{2} + \frac{1}{8n(n+1)p(n)}. ⊓ ⊔

Using Lemmas 1, 2 and 3 together with the fact that m-bbcs is unconditionally secure against the sender [5], we get the desired result:

Lemma 4. Protocol u-qbc is binding.

As we shall see next, Lemma 4 helps a great deal in proving that qbc is computationally binding.

4.3 qbc is Binding When BBC is Concealing

In the following, we conclude that qbc is computationally binding whenever BBC is computationally concealing. We use the fact that u-qbc is statistically binding (Lemma 4) in order to use any adversary against the binding condition of qbc as a distinguisher between random (u-qbc) and real (qbc) commitments for some hybrids between u-qbc and qbc.

Theorem 1. If there exists a (s_{0}(n), s_{1}(n))-adversary Ã = (CÃ, OÃ) against the binding condition of qbc with s_{0}(n) + s_{1}(n) ≥ 1 + \frac{1}{p(n)} for positive positive polynomial p(n), then there exists a quan-

tum receiver CB̃ in BBC and a quantum algorithm LB̃ such that P (LB̃((C^{A} ⊙ CB̃)|b⟩^{A}|0⟩B̃) = b) ≥ \frac{1}{2} + Ω(\frac{1}{n^{4}p(n)}) whenever b ∈_{R} \{0, 1\}

and where CB̃ calls Ã an expected O(n^{5}p(n)^{2}) times.

Proof. Let B = (C^{B}, O^{B}) be the circuits for the honest receiver in qbc and let A be an honest committer in BBC. Given Ã, we construct a receiver CB̃ in BBC from which a bias for A’s committed bit can be extracted. Remember that the only difference between u-qbc and qbc is that a honest receiver commits to random bits instead of his measurements and outcomes. There are 4n calls to Commit-BBC per bbcs (u-bbcs) for a total of 4n^{2} during the committing stage of qbc (u-qbc). Let’s note as significant the committed bits specified by the protocol bbcs (to measurements and outcomes) and as random the ones specified by the protocol u-bbcs (to random bits). We describe hybrids in between qbc and u-qbc by letting the number of significant and random commitments vary. Let qbc^{k} be protocol qbc but where the first k commitments out of 4n^{2} are made to random values. We have that u-qbc ≡ qbc^{4n^{2}} is binding whereas Ã is a (s_{0}(n), s_{1}(n))–adversary for the binding condition of qbc^{0} ≡ qbc. Let s_{b}^{k}(n) be the probability that Ã succeeds when opening b ∈ {0, 1} in qbc^{k} for 0 ≤ k ≤ 4n^{2}. Defining ŝ^{k}(n) = (s_{0}^{k}(n) + s_{1}^{k}(n))/2, we get that ŝ^{0}(n) ≥ \frac{1}{2} + \frac{1}{2p(n)} and ŝ^{4n^{2}}(n) < \frac{1}{2} + \frac{1}{poly(n)} (from Lemma 4), given n sufficiently large. By the hybrid argument, there exists 0 ≤ k^{∗} ≤ 4n^{2} − 1 such that for n sufficiently large,

ŝ^{k^{∗}}(n) − ŝ^{k^{∗}+1}(n) ≥ \frac{1}{9n^{2}p(n)}.  (5)

Hence, D_{4n^{2}}(\frac{1}{9n^{2}p(n)}) = \{ŝ^{i}(n)\}_{i=0}^{4n^{2}} is a family of Bernoulli distributions that satisfies the condition of Lemma 7. The sampling circuit S is easy to construct given Ã and B. Upon classical input |l⟩ for 0 ≤ l ≤ 4n^{2}, S runs Ã and B except that the first l commitments sent from B to Ã (using BBC) are made to random values instead of the measurements β̂ and the outcomes r. Ã then opens a random bit b ∈_{R} {0, 1}. If B accepts the opening of b then S(|l⟩) = 1 otherwise it returns S(|l⟩) = 0. Circuit S is therefore a sampling circuit for D_{4n^{2}}(\frac{1}{9n^{2}p(n)}) such that ∥S∥_{UG} ∈ O(∥Ã∥_{UG}) assuming without loss of generality that ∥B∥_{UG} ∈ O(∥Ã∥_{UG}).

We now construct the adversary CB̃ for the concealing condition of BBC given Ã. In order to use algorithm FindDrop presented in Appendix C, CB̃ must first determine a lower bound \frac{1}{p′(n)} for the drop \frac{1}{9n^{2}p(n)}. This is done by finding a lower bound p̃(n) for \frac{1}{2p(n)} and then setting p′(n) =

5n^{2}/p̃(n). CB̃ computes p̃(n) = LowBound(S_{0}, \frac{1}{2}, n) where LowBound is the procedure described in Appendix B and S_{0} is the circuit S with the input bits fixed to |0⟩. According to Lemma 6, when n is sufficiently large LowBound returns p̃(n) such that \frac{1}{2n^{2}p(n)} ≤ p̃(n) ≤ \frac{1}{2p(n)} except with negligible probability and after an expected O(n^{5}p(n)^{2}) calls to S_{0}.

Now CB̃ can use FindDrop(S, \frac{1}{p′(n)}, n) with the family of distributions

D_{4n^{2}}(\frac{1}{p′(n)}) = \{ŝ^{i}(n)\}_{i=0}^{4n^{2}} which exhibits a drop \frac{1}{p′(n)} except with negligible probability. From Lemma 7, CB̃ gets 0 ≤ κ ≤ 4n^{2} − 1 such that

ŝ^{κ}(n) − ŝ^{κ+1}(n) ≥ \frac{1}{2p′(n)}  (6)

except with negligible probability. The value of κ is obtained after calling S (including the calls to S_{0} in LowBound) an expected O(n^{5}p(n)^{2}) times.

CB̃ then uses κ for attacking the concealing condition of BBC the following way: It lets Ã and B interact (where Ã opens b ∈_{R} {0, 1}) as in qbc^{κ+1} except that the (κ + 1)-th random commitment is provided by the committer A in BBC. Let b ∈ {0, 1} be the bit committed by A. Let V be the random variable for the view generated during the interaction between Ã and B when Ã opens the random bit. Let c_{κ+1}(V) ∈ {0, 1} be the bit that B would have committed if the (κ + 1)-th commitment was significant. The distinguisher LB̃ (which is classical given the view V) returns the guess b̃ for b the following way:

– If V is a successful opening then b̃ = c_{κ+1}(V),

– Otherwise, b̃ ∈_{R} {0, 1}.

Let V_{ok}^{κ+1} be the set of views for qbc^{κ+1} resulting in a successful opening and let G be the set of values κ for which (6) holds. We have ŝ^{κ}(n) = P (V ∈ V_{ok}^{κ+1}|c_{κ+1}(V ) = b) and ŝ^{κ+1}(n) = \frac{1}{2} (P (V ∈ V_{ok}^{κ+1}|c_{κ+1}(V ) ≠ b) + P (V ∈ V_{ok}^{κ+1}|c_{κ+1}(V ) = b)) which, using (6), leads to P (V ∈ V_{ok}^{κ+1} ∧ c_{κ+1}(V ) ≠ b) ≤ P (V ∈ V_{ok}^{κ+1} ∧ c_{κ+1}(V ) = b) − \frac{1}{2p′(n)}. Since we have in addition that P (V ∈ V_{ok}^{κ+1}) = P (V ∈ V_{ok}^{κ+1} ∧ c_{κ+1}(V ) ≠ b) + P (V ∈ V_{ok}^{κ+1} ∧ c_{κ+1}(V ) = b), we get

P (b̃ = b|κ ∈ G) = P (V ∈ V_{ok}^{κ+1} ∧ c_{κ+1}(V ) = b) + \frac{1}{2} (1 − P (V ∈ V_{ok}^{κ+1}))
≥ \frac{1}{2} (1 + \frac{1}{2p′(n)}) .

Since P (b̃ = b) ≥ P (κ ∈ G) P (b̃ = b|κ ∈ G) and P (κ ∈ G) ≥ 1 −

2^{−αn}, α > 0 (Lemma 6) we finally get that (CB̃, LB̃) is an adversary for the concealing condition of BBC providing a bias in Ω(\frac{1}{p′(n)}) = Ω(\frac{1}{n^{4}p(n)}) after calling Ã an expected O(n^{5}p(n)^{2}) times. ⊓ ⊔

5 The Concealing Condition

We now reduce the concealing condition of qbc to the security of bbcs against the receiver [20].

Lemma 5. If there exists a quantum interacting circuit CB̃ for Commit-qbc and a quantum algorithm LB̃ acting only on B̃’s registers such that P (LB̃((C^{A} ⊙ CB̃)|b⟩^{A}|0⟩B̃) = b) ≥ \frac{1}{2} + \frac{1}{p(n)} for some positive

polynomial p(n) and an honest committing circuit C^{A} for b ∈_{R} {0, 1}, then there also exists a cheating receiver (B^{∗}, L^{B^{∗}}) for bbcs.

Proof. For the receiver CB̃ and C^{A} described in the statement, we have

P (LB̃((C^{A} ⊙ CB̃)|1⟩^{A}|0⟩B̃) = 1) −

P (LB̃((C^{A} ⊙ CB̃)|0⟩^{A}|0⟩B̃) = 1) ≥ \frac{2}{p(n)}.

Let’s define a modification of an honest committing circuit for qbc, noted CÃ, which is the same as C^{A} but takes a string f̂ ∈ {0, 1}^{n} instead of a bit b and sends in the i-th call to bbcs the bits a_{0i} ∈_{R} {0, 1} and a_{1i} = a_{0i}⊕f̂_{i} for 1 ≤ i ≤ n. The circuit C^{A} with input b is equivalent to CÃ with input b^{n}. Once again, by an hybrid argument, there exist 1 ≤ k^{∗} ≤ n such that

P (LB̃((CÃ ⊙ CB̃)|1^{k^{∗}}0^{n−k^{∗}}⟩Ã|0⟩B̃) = 1) −
P (LB̃((CÃ ⊙ CB̃)|1^{k^{∗}−1}0^{n−k^{∗}+1}⟩Ã|0⟩B̃) = 1)

≥ \frac{2}{np(n)}

With such value k^{∗}, B^{∗} runs bbcs(e_{0}, e_{1})(?) with an honest sender A′ the following way: it lets CB̃ interact with CÃ with input (1^{k^{∗}−1}?0^{n−k^{∗}}) for Commit-qbc except for the k^{∗}-th call to bbcs where it makes CB̃ interact with the targeted sender.

Then, knowing e_{c} for c ∈ {0, 1}, we take the output of LB̃, b′ say, and compute a guess e_{c} ⊕ b′ for e\overline{c}. For this algorithm L^{B^{∗}} we have

P (L^{B^{∗}}((A′ ⊙ B^{∗})|e_{0}; e_{1}⟩^{A}|0⟩^{B^{∗}}, |e_{c}; c⟩^{B^{∗}}) = ec̄) = P (b′ = e_{0} ⊕ e_{1})
≥ \frac{1}{2} + \frac{1}{np(n)}

where the probabilities are taken over e_{0}, e_{1} ∈_{R} {0, 1}. ⊓ ⊔

From Yao’s result [20] and Lemma 5 it is straightforward to conclude that qbc is concealing.

6 Conclusion and Open Questions

Having shown in Theorem 1, that a computationally concealing BBC results in a computationally binding qbc and, from Lemma 5 together with Yao’s result [20], that no adversary against the concealing condition of qbc exists, we conclude with our main result:

Theorem 2. If BBC is binding and computationally concealing then qbc is concealing and computationally binding.

For security parameter n, the reduction of an adversary (CB̃ ; n, LB̃ ; n) for the concealing condition of BBC to an adversary Ã_{n} for the binding condition of qbc is expected polynomial-time black-box. If Ã_{n} breaks the binding condition of qbc with s_{0}(n) + s_{1}(n) ≥ 1 + \frac{1}{p(n)} then the circuit CB̃ ; n is specified by a classical Turing machine calling Ã_{n} at most n^{5}p(n)^{2} times except with negligible probability. LB̃ ; n then provides a polynomial bias on the committed bit through an almost trivial classical computation given as input CB̃’s view. This guarantees that (CB̃ ; n, LB̃ ; n) satisfies ∥CB̃ ; n∥_{UG} + ∥LB̃ ; n∥_{UG} ∈ O(n^{5}p(n)∥Ã∥_{UG}) (using standard simulation techniques) thus breaking the concealing condition of BBC as defined in Sect. 2.3. The adversary {(CB̃ ; n, LB̃ ; n)}_{n>0} is specified by a uniform family of quantum circuits whenever {Ã_{n}}_{n>0} is a uniform family^{1}. Our reduction is therefore uniformity preserving [18]. It is an interesting open problem to find an exact polynomial-time black-box reduction.

One consequence of Theorem 2 is that concealing commitment schemes can be built from any quantum one-way function. We first observe that Naor’s commitment scheme [17] is also secure against the quantum computer if the pseudo-random generator (PRG) it is based upon is secure against the quantum computer. This follows from the fact that any quantum circuit able to distinguish between commitments to 0 and 1 is also able to distinguish a truly random sequence from a pseudo-random one. To complete the argument, we must make sure that given a quantum one-way function one can construct a PRG resistant to quantum distinguishers. A tedious but not difficult exercise allows to verify that the classical construction of [19] results in a PRG secure against quantum distinguishers given it is built from quantum one-way functions. We get the following corollary which is not known to hold in the classical case:

1 Given 1^{n}, there exists a poly-time Turing machine that outputs the description of (CB̃ ; n, LB̃ ; n), namely one knowing p(n).

Corollary 1. Both binding but computationally concealing and concealing but computationally biding quantum bit commitments can be constructed from quantum one-way functions.

It would be interesting to find a concealing quantum bit commitment scheme directly constructed from one-way functions which improves the complexity of our construction. Is it possible to find a non-interactive concealing commitment scheme from the same complexity assumption or are such constructions inherently interactive? It is also unclear whether or not perfectly concealing schemes can be based upon any quantum oneway function?

Although we assumed in this paper a perfect quantum channel, our construction should also work with noisy quantum transmission. It would be nice to provide the analysis for this general case.

References

1. Barenco, A., C.H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin and H. Weinfurter, “Elementary Gates for Quantum Computation”, Physical Review A, vol. 52, no 5, November 1995, pp. 3457 – 3467.

2. Bennett, C. H., G. Brassard, C. Crépeau and M.-H. Skubiszewska, “Practical Quantum Oblivious Transfer”, Advances in Cryptology : CRYPTO ’91 : Proceedings, Lecture Notes in Computer Science, vol. 576, Springer–Verlag, August 1992, pp. 362 – 371.

3. Brassard, G., D. Chaum and C. Crépeau, “Minimum Disclosure Proofs of Knowledge”, Journal of Computing and System Science, vol.37 , 1988, pp. 156 – 189.

4. R., Cleve,personnal communication, March 2000.

5. Crépeau, C., “Quantum Oblivious Transfer”, Journal of Modern Optics, vol. 41, no. 12, December 1994, pp. 2445 – 2454.

6. Crépeau, C., “An Equivalence Between Two flavors of Oblivious Transfer”, Advances in Cryptology :CRYPTO 87:Proceedings, Lecture Notes in Computer Science, vol.293, Springer-Verlag, 1987,pp. 350 – 354.

7. Dumais, P., D. Mayers, and L. Salvail, “Perfectly Concealing Quantum Bit Commitment From Any Quantum One-Way Permutation”, Advances in Cryptology :EUROCRYPT ’00 : Proceedings, Lecture Notes in Computer Science, vol. 1807, Springer–Verlag, 2000, pp. 300 – 315.

8. Goldreich, O., and L. Levin,“A Hard-Core Predicate for Any One-Way Function”, Proc. 21st ACM Symp. on Theory of Computing, 1989, pp. 25 – 32.

9. Goldwasser, S., S. Micali,and C. Rackoff, “The Knowledge Complexity of Interactive Proof Systems”, SIAM Journal on Computing, vol.18, pp. 186 – 208.

10. Goldreich, O., S. Micali, and A. Wigderson,“Proofs that Yield Nothing but their Validity or All Language in NP Have Zero-Knowledge Proof Systems”, Journal of the ACM, vol.38, No.1, pp.691–729,1991.

11. Goldreich, O, S. Micali, and A. Wigderson, “ ”How to play any mental game or a completeness theorem for protocols with honest majority”, Proc. 19th Symposium on Theory of Computing, 1987, pp. 218 – 229.

12. Impagliazzo, I., L. Levin, and L. Luby,“Pseudo-Random Generation from One-Way Functions”,Proc. 21st Symposium on Theory of Computing, 1989, pp. 12 – 24.

13. Impagliazzo, R and S. Rudich, “Limits on Provable Consequences of One-Way Permutations”, in the 24th ACM Symposium on Theory of Computing, 1989.

14. Lo, H.–K. and H. F. Chau, “Is quantum Bit Commitment Really Possible?”, Physical Review Letters, vol. 78, no 17, April 1997, pp. 3410 – 3413.

15. Mayers, D., “The Trouble With Quantum Bit Commitment

http://xxx.lanl.gov/abs/quant-ph/9603015, March 1996.

16. Mayers, D., “Unconditionally Secure Quantum Bit Commitment is Impossible”, Physical Review Letters, vol. 78, no 17, April 1997, pp. 3414 – 3417.

17. Naor, M., “Bit Commitment Using Pseudo-Randomness”, Journal of Cryptology, vol. 4, 1991, pp. 151 – 158.

18. Naor, M., R. Ostrovsky, R. Ventkatesan, and M. Young, “Perfect Zero-Knowledge Arguments For NP Using Any One-Way Permutation”, Journal of Cryptology, vol. 11, no 2, 1998, pp. 87 – 108.

19. Håstad, J., R. Impagliazzo, L. A. Levin, and M. Luby “A pseudo-random generator from any one-way function”, In SIAM Journal on Computing, vol. 28, no 4, pp. 1364-1396, 1999.

20. Yao, A. C.–C., “Security of Quantum Protocols Against Coherent Measurements”, Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, May 1995, pp. 67 – 75.

A Bernshtein’s Law of Large Numbers

Theorem 3 (Bernshtein). Let X_{1}, X_{2}, …, X_{n} ∼ B(p) be independent random variables following a Bernoulli distribution with p as the probability parameter. Then for any 0 < ϵ ≤ p(1 − p),

P (|\frac{∑_{i=1}^{n} X_{i}}{n} − p| ≥ ϵ) ≤ 2e^{−nϵ^{2}}

In particular, Bernshtein’s law of large numbers ensures us that we can estimate the probability of an event with an error bounded by any polynomial except with negligible probability using a polynomial number of random variables. For example, if we want an error bounded by \frac{1}{p(m)} then with ⌈mp(m)^{2}⌉ random variables we obtain a correctly bounded estimate with probability at least 1 − 2e^{−m}.

B Estimating Polynomial Variation of Bernoulli’s Parameter

Suppose we have a quantum circuit R_{n} allowing to sample from a Bernoulli distribution with unknown parameter p_{n} = q + \frac{1}{p(n)} where 0 ≤ q < 1 is a known constant and p(n) is some positive polynomial. That is P (R_{n} = 1) = p_{n} and P (R_{n} = 0) = 1 − p_{n} independently for each execution of R_{n}. The following classical procedure uses the quantum sampling circuit R_{n} as a black-box to provide a lower bound \frac{1}{g_{n}} for \frac{1}{p(n)}:

LowBound(R_{n}, q, n)

1. p̃_{n} = 0; g_{n} = 1;

2. While p̃_{n} ≤ q + \frac{2}{g_{n}} Do (a) g_{n} = g_{n}n;

(b) #sampling = ng_{n}^{2};

(c) success = 0;

(d) For 1 ≤ i ≤ #sampling Do success = success + R_{n};

(e) p̃_{n} = \frac{success}{#sampling};

 3. Return: \frac{1}{g_{n}}.

Lemma 6. For n sufficiently large, LowBound(R_{n}, q, n) returns \frac{1}{g_{n}} such that \frac{1}{n^{2}p(n)} < \frac{1}{g_{n}} ≤ \frac{1}{p(n)} except with probability 2^{−αn}, α > 0 and after calling R_{n} an expected O(n^{5}p(n)^{2}) times.

Proof. For n sufficiently large, there exist a constant k such that

\frac{1}{n^{k+1}} < \frac{1}{p(n)} ≤ \frac{1}{n^{k}} .  (7)

Since by (7) there exists at least one, let k′ be the smallest constant such that for all i ≥ k′ + 2 and j ≤ k′

\frac{3}{n^{i}} < \frac{1}{p(n)} ≤ \frac{1}{n^{j}} .  (8)

By Bernshtein’s law of large numbers, the obtained estimate p̃_{n}(t) in the t-th repetition of step 2 as a bounded error \frac{1}{n^{t}} with probability at least 1 − 2e^{−n}. So, for j ≤ k′ we have with probability at least 1 − 2e^{−n}

p̃_{n}(j) ≤ q + \frac{1}{p(n)} + \frac{1}{n^{j}} ≤ q + \frac{2}{n^{j}}  (9)

and the number of repetition of step 2 is greater than k′ with probability at least (1 − 2e^{−n})^{k′}. Moreover, for i ≥ k′ + 2 we have again with probability at least 1 − 2e^{−n}

p̃_{n}(i) ≥ q + \frac{1}{p(n)} − \frac{1}{n^{i}} > q + \frac{2}{n^{i}}  (10)

and so the probability of executing more than k′ + 2 repetitions of step 2 is lower then 2e^{−n}. Hence the procedure will repeat step 2 either k′ + 1 or k′ + 2 and respectively output \frac{1}{n^{k′+1}} or \frac{1}{n^{k′+2}} except with negligible probability smaller than 2^{−αn} for some α > 0. By definition of k′ we have that

\frac{1}{n^{2}p(n)} ≤ \frac{1}{n^{k′+1}} , \frac{1}{n^{k′+2}} < \frac{1}{p(n)}.  (11)

Furthermore, since equation 10 the expected number of calls to R_{n} is in O(n^{5}p(n)^{2}). ⊓ ⊔

C Finding a Polynomial Drop Between Neighbors

Let D_{m}(\frac{1}{p(n)}) = \{p_{i}\}_{i=0}^{m} be a family of Bernoulli distributions with unknown parameters 0 ≤ p_{i} ≤ 1 for every 0 ≤ i ≤ m and such that p_{k^{∗}} − p_{k^{∗}+1} ≥ \frac{1}{p(n)} for some 0 ≤ k^{∗} < m. Let S be a quantum circuit such that P (S|l⟩ = 1) = p_{l} and P (S|l⟩ = 0) = 1 − p_{l} for all 0 ≤ l ≤ m. That is, S is a quantum circuit allowing to sample from the Bernoulli distribution B(p_{l}) given classical input |l⟩. We would like to find κ that exhibits a polynomial drop p_{κ} − p_{κ+1} similar to p_{k^{∗}} − p_{k^{∗}}. Algorithm FindDrop finds κ using the sampling circuit S as a black-box but is otherwise classical: FindDrop(S, \frac{1}{p(n)}, n)

1. p̃_{−1} = 0; k = −1;

 2. Loop:

(a) k = k + 1; success = 0;

(b) For i = 1 to ⌈64mnp(n)^{2}⌉ Do success = success + S|k⟩;

(c) p̃_{k} = success/⌈64mnp(n)^{2}⌉;

3. Until (p̃_{k−1} − p̃_{k} ≥ \frac{3}{4p(n)}) or (k = m)

4. Return κ=k − 1.

The returned value κ can now be shown to satisfy p_{κ} − p_{κ+1} ≥ \frac{1}{2}(p_{k^{∗}} − p_{k^{∗}+1}) except with negligible probability. The algorithm is efficient in terms of ∥S∥_{UG}, and parameters m and n.

Lemma 7. Given a family of Bernoulli distributions D_{m}(\frac{1}{p(n)}) = \{p_{i}\}_{i=1}^{m} with sampling circuit S such that p_{k^{∗}} − p_{k^{∗}+1} ≥ \frac{1}{p(n)} for some 0 ≤ k^{∗} ≤ m−1, algorithm FindDrop(S, \frac{1}{p(n)}, n) returns κ such that p_{κ}−p_{κ+1} ≥ \frac{1}{2p(n)} except with negligible probability 2^{−αn}, α > 0 and after calling S at most (m + 1)⌈64mnp(n)^{2}⌉ ∈ O(m^{2}np(n)^{2}) times.

Proof. By Bernshtein’s law of large numbers, p̃_{k} as a bounded error \frac{1}{8p(n)} with probability at least 1 − 2e^{−mn}. So, with probability at least (1 − 2e^{−mn})^{m+1} the estimate p̃_{k} is within bounded errors \frac{1}{8p(n)} of p_{k} for all 0 ≤ k ≤ m. In that case, we have for 0 ≤ i ≤ m − 1 such that p_{i} − p_{i+1} <

\frac{1}{2p(n)}

p̃_{i} − p̃_{i+1} ≤ p_{i} − p_{i+1} + \frac{2}{8p(n)} < \frac{3}{4p(n)}  (12)

and also for 0 ≤ j ≤ m − 1 such that p_{j} − p_{j+1} ≥ \frac{1}{p(n)}

p̃_{j} − p̃_{j+1} ≥ p_{j} − p_{j+1} − \frac{2}{8p(n)} ≥ \frac{3}{4p(n)}.  (13)

The algorithm FindDrop returns a bad κ whenever p_{κ} − p_{κ+1} < \frac{1}{2p(n)} but p̃_{k}−p̃_{κ+1} ≥ \frac{3}{4p(n)} or whenever k^{∗} could not be recognized. By equations 12 and 13, the probability p_{e} that FindDrop makes a mistake in the output satisfies p_{e} ≤ 1 − (1 − 2e^{−mn})^{m+1} ≤ 2^{−αn} for some α > 0.

⊓ ⊔

Recent BRICS Report Series Publications

RS-00-52 Claude Crépeau, Frédéric Légaré, and Louis Salvail. How to Convert a Flavor of Quantum Bit Commitment. December 2000. 24 pp. To appear in Advances in Cryptology: International Conference on the Theory and Application of Cryptographic Techniques, EUROCRYPT ’01 Proceedings, LNCS, 2001.

RS-00-51 Peter D. Mosses. CASL for CafeOBJ Users. December 2000. 24 pp. Appears in Futatsugi, Nakagawa and Tamai, editors, CAFE: An Industrial-Strength Algebraic Formal Method, 2000, chapter 6, pages 121–144.

RS-00-50 Peter D. Mosses. Modularity in Meta-Languages. December 2000. 18 pp. Appears in 2nd Workshop on Logical Frameworks and Meta-Languages, LFM ’00 Proceedings, 2000.

RS-00-49 Ulrich Kohlenbach. Higher Order Reverse Mathematics. December 2000. 18 pp.

RS-00-48 Marcin Jurdziński and Jens Vöge. A Discrete Stratety Improvement Algorithm for Solving Parity Games. December 2000.

RS-00-47 Lasse R. Nielsen. A Denotational Investigation of Defunctionalization. December 2000. Presented at 16th Workshop on the Mathematical Foundations of Programming Semantics, MFPS ’00 (Hoboken, New Jersey, USA, April 13–16, 2000).

RS-00-46 Zhe Yang. Reasoning About Code-Generation in Two-Level Languages. December 2000.

RS-00-45 Ivan B. Damgård and Mads J. Jurik. A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System. December 2000. 18 pp. To appear in Fourth International Workshop on Practice and Theory in Public Key Cryptography, PKC ’01 Proceedings, LNCS, 2001. This revised and extended report supersedes the earlier BRICS report RS-00-5.