Apparent Collapse of Quantum State and Computational Quantum Oblivious Transfer

Abstract. We analyze the situation where computationally binding string commitment schemes are used to force the receiver of a BB84 encoding of a classical bitstring to measure upon reception. Since measuring induces an irreversible collapse to the received quantum state, even given extra information after the measurement does not allow the receiver to evaluate reliably some predicates applied to the classical bits encoded in the state. This fundamental quantum primitive is called quantum measurement commitment (QMC) and allows for secure two-party computation of classical functions. An adversary to QMC is one that can both provide valid proof of having measured the received states while still being able to evaluate a predicate applied to the classical content of the encoding. We give the first quantum black-box reduction for the security of QMC to the binding property of the string commitment. We characterize a class of quantum adversaries against QMC that can be transformed into adversaries against a weak form for the binding property of the string commitment. Our result provides a construction for 1 − 2-oblivious transfer that is computationally secure against the receiver and unconditionally secure against the sender given any unconditionally concealing string commitment satisfying a weak computational binding property.

keywords: quantum bit commitment, oblivious transfer, quantum measurement, computational assumptions.

1 Introduction

As for the classical case, secure quantum 2-party cryptography must rely upon some kind of assumption[14, 15, 13]. However, the two models of computation do not share the same capabilities and limits[11, 6, 20]. In particular, given a classical black-box for bit commitment, there exists a quantum protocol, called the CK protocol [6, 5, 4], achieving 1 − 2 oblivious transfer (one-out-of-two oblivious transfer). This is in sharp contrast with the classical case where such a reduction is not only unknown but unlikely to exist [11]. The difference between the two models can intuitively be appreciated by observing that a classical black-box for bit commitment allows to transform the quantum channel into a noisy classical channel powerful enough to provide OT. To see this, consider the BB84 coding scheme [2, 6] for classical bit b into a random state in { b⟩_{+} , b⟩_{×} }.The random θ ∈ {+, ×} used to encode b into the quantum state b⟩_{θ}, is called the transmission basis.Since only orthogonal quantum states can be distinguished with certainty, the transmitted bit b is not received perfectly by the receiver, Alice, who does not know the transmission basis. The coding scheme also specifies what an honest Alice should be doing with the received state b⟩_{θ}. She picks θ̂ ∈_{R} {+, ×} and measures b⟩_{θ} with measurement 𝕄θ̂ that distinguishes perfectly orthogonal states 0⟩θ̂ and 1⟩θ̂ by providing the classical outcome b̂ ∈ {0, 1}. If Bob and Alice follow honestly the BB84 coding scheme then b is received with probability 1 when θ̂ = θ whereas a random bit is received when θ̂ ≠ θ. The error-rate of such a transmission is therefore \frac{1}{4} when θ is not revealed to Alice. Dishonest Bob however, could send different states in order to temper with the error-rate of the channel so it becomes an unfair noisy channel (i.e. UNC) [8]. Bob could instead send cos \frac{π}{8} b⟩+ (−1)^{b}sin \frac{π}{8} 1 − b⟩ for the encoding of b. In this case, the error-rate falls to sin^{2} \frac{π}{8}. According to [8], the resulting (sin^{2} \frac{π}{8}, \frac{1}{4})-UNC has no cryptographic capability since 2 sin^{2} \frac{π}{8}(1 − sin^{2} \frac{π}{8}) ≤ \frac{1}{4}. In order to prevent Bob from behaving in such a way, a slightly different strategy is used. Bob is now asked to announce θ allowing Alice to determine whether b has been received. The result is an oblivious transfer of bit b from Bob to Alice assuming Alice is honest. Dishonest Alice can easily learn b all the time by waiting for θ before applying measurement 𝕄_{θ}. Bob must make sure that Alice has measured before the announcement of θ so the initial state has collapsed irreversibly. An oblivious transfer is possible only given such a primitive implemented the natural way using commitments.

We call Quantum Measurement Commitment (or QMC) the primitive that allows Alice to provide Bob with evidences of a measurement she claims having performed on the qubits received before the announcement of θ. Implementing a QMC is simply done by sending a commitment containing (θ̂,b̂) to Bob where θ̂ is the measurement Alice claims having performed and b̂ is the outcome. An apparent collapse occurred if given the transmission basis θ, the encoded bit b cannot be determined perfectly. However, verifying the collapse of a single qubit cannot be done perfectly since Alice could always provide a commitment to random (θ̂,b̂) while keeping b⟩_{θ} untouched until θ is announced. The probability of opening with success would then be \frac{3}{4} while b can always be received perfectly from θ. To avoid lucky Alice from learning too much about b, we consider QMC made to n random BB84 qubits b⟩_{θ} = b_{1}⟩_{θ_{1}}, b_{2}⟩_{θ_{2}}, …, b_{n}⟩_{θ_{n}}.The QMC is simply implemented using a string commitment containing the measurements θ̂ ∈ {+, ×}^{n} and the outcomes b̂∈ {0, 1}^{n}. The classical transmission is defined by some predicate f(b_{1}, …, b_{n}). Alice should be unable to evaluate f(b_{1}, …, b_{n}) even given the knowledge of θ once the QMC has been performed. The CK protocol can be seen as a reduction of oblivious transfer to such a QMC with f(b_{1}, …, b_{n}) ≡ ⊕_{i=1}^{n} b_{i}. A QMC is therefore an universal primitive for secure quantum 2-party computation of classical functions. A successful adversary to QMC is one that can unveil valid measurement outcomes with good probability while being able to get a bias on f(b_{1}, …, b_{n}) given θ ∈ {+, ×}^{n}.

Our contributions

In this paper, we address the question of determining how the binding property of the string commitment scheme used for implementing a QMC enforces its security. As already pointed out in [9, 7], quantum bit commitment schemes satisfy different binding properties than classical ones. The difference becomes more obvious when string commitments are taken into account. We generalize the computational binding criteria of [9] to the case where commitments are made to strings of size l ∈ Ω(n) for n the security parameter, and l some value depending on n. Intuitively, for a class of functions F ⊆ {f : {0, 1}^{l} → {0, 1}^{m}}, with m < l both depending on n, we say that a string commitment scheme is F –binding if for all f ∈ F and a random y ∈_{R} {0, 1}^{m}, the committer cannot open any s ∈ {0, 1}^{l} such that f(s) = y with success probability significantly better than 1/2^{m}. The smaller m is compared to l, the weaker is the F –binding criteria. We relate the security of a QMC to a weak form of the F –binding property. We assume that QMC’s are made using some computationally binding and unconditionally concealing string commitments containing the bases θ̂ ∈ {+, ×}^{n} and the results b̂ ∈ {0, 1}^{n} obtained by Alice after Bob’s transmission of b⟩_{θ}. At this point, Bob selects a challenge c ∈_{R} {0, 1}. If c = 0, Alice unveils all measurements and outcomes that Bob verifies. If c = 1, Bob announces the transmission basis θ ∈_{R} {+, ×}^{n} and Alice tries to maximize her bias on the parity of b. Let p̃_{s} be Alice’s probability of success when c = 0 and let ϵ̃ be Alice’s expected bias when c = 1. First notice that if p̃_{s} + 2ϵ̃ = 2 then the QMC is not accomplishing anything since Alice can always unveil perfectly (p̃_{s} = 1) and bias the parity of b as she likes (ϵ̃ = 1/2). In this case it is impossible to build a secure OT from that QMC. However, as we will see in Section 3.2 an honest Alice can always achieve p̃_{s} + 2ϵ̃ = 1 and thus all adversaries such that p̃_{s} + 2ϵ̃ ≤ 1 are considered trivial. Our main contribution describes how p̃_{s} and ϵ̃ relates to the F_{m}^{n}–binding criteria of the string commitment where F_{m}^{n} is a class of functions with m ∈ O(polylog(n)). We give a black-box reduction of any good quantum adversary against QMC into one against the F_{m}^{n}–binding property of the string commitment. We show that if p̃_{s} + 4ϵ̃^{2} ≥ 1 + δ(n) for nonnegligible δ(n), then the string commitment is not F_{m}^{n}–binding. We also show that the converse condition ϵ̃ ≤ \sqrt{1 + δ(n) − p̃_{s}} /2 (for negligible δ(n)) is sufficient to build a secure OT. If p̃_{s} is sufficiently close to 1 on a large number of QMCs then a correct and private OT is implemented. The opposite case “many p̃_{s} are not close to 1” is easy to detect and reject.

Our reduction shows that using computationally binding commitments one can enforce a computational or apparent collapse of quantum information. This is the first quantum black-box reduction linking the security of those two primitives. Previously, Yao [20] has shown that if the string commitment is modeled by a classical black-box then the CK protocol is secure. Our result can be used for proving the security of OT in the computational setting using a completely different approach. Our 1 − 2 oblivious transfer is unconditionally secure against the sender but computationally secure against the receiver and is very similar to the CK protocol. As for the Quantum Goldreich-Levin theorem of [1] and the computationally binding commitments of [9] and [7], our result clearly indicates that 2-party quantum cryptography in the computational setting can be based upon different if not weaker assumptions than its classical counterpart.

2 Preliminaries

Notations and Tools. In the following, poly(n) stands for any polynomial in n. We write A(n) < poly(n) for “A(n) is smaller than any polynomial provided n is sufficiently large” and A(n) ≤ poly(n) (resp. A(n) ≥ poly(n)) means that A(n) is upper bounded by some polynomial (resp. lower bounded by some polynomial). For w ∈ {0, 1}^{n}, x ⪯ w means that x_{i} = 0 for all 1 ≤ i ≤ n such that w_{i} = 0 (x belongs to the support of w). We denote by “♦” the string concatenation operator. For w ∈ {0, 1}^{n}, we write [w] ≡ ⊕_{i=1}^{n} w_{i}. For w, z ∈ {0, 1}^{n}, we write |w| for the Hamming weight of w, Δ(w, z) = |w ⊕ z| for the Hamming distance, and w ⊙ z ≡ ⊕_{i=1}^{n} w_{i} · z_{i} is the boolean inner product. Notation ∥u⃗∥ denotes the Euclidean norm of u⃗ and u^{†} denotes its complex conjugate transposed. The following well-known identity will be useful,

(∀y ∈ {0, 1}^{n})[y ≠ 0^{n} ⇒ ∑_{x∈{0,1}^{n}} (−1)^{x⊙y} = 0].  (1)

Next lemma, proved in Appendix A, provides a useful generalization of the parallelogram identity:

Lemma 1. Let A ⊆ {0, 1}^{n} be a set of bitstrings. Let {v⃗_{w,z}}_{w,z} be any family of vectors indexed by w ∈ {0, 1}^{n} and z ∈ A that satisfies,

(∀s, t ∈ {0, 1}^{n}, s ≠ t)[∑_{w} ∑_{z_{1}∈A:w⊕z_{1}=s} ∑_{z_{2}∈A:w⊕z_{2}=t} (−1)^{w⊙(z_{1}⊕z_{2})} ⟨v⃗_{w,z_{1}} , v⃗_{w,z_{2}} ⟩ = 0]  (2)

Then, ∑_{w} ∥ ∑_{z∈A} (−1)^{w⊙z} v⃗_{w,z}∥^{2} = ∑_{w∈{0,1}^{n}} ∑_{z∈A} ∥v⃗_{w,z}∥^{2}.  (3)

Finally, for θ, b ∈ {0, 1}^{n}, we define Δ_{⪯} (θ, b) = {(θ̂,b̂) ∈ {0, 1}^{n} × {0, 1}^{n}|(∀i, 1 ≤ i ≤ n)[θ̂_{i} = θ_{i} ⇒ b̂_{i} = b_{i}]}. It is easy to verify that #Δ_{⪯} (θ, b) = 3^{n} and that (θ ⊕ τ, b ⊕ β) ∈ Δ_{⪯} (θ, b) iff β ⪯ τ.

Quantum Operators and Encoding. In the following, we denote the m-dimensional Hilbert space by H_{m}. 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 𝕄 = {ℙ_{i}}_{i=1}^{m} acting in H_{m} thus satisfying ∑ _{i} ℙ_{i} = 1_{m} for 1_{m} denoting the identity operator in H_{m}. Each projection or equivalently each index i ∈ {1, …, m} is a possible classical outcome for 𝕄. In the following, we write ℙ_{+,0} ≡ ℙ_{0} = 0⟩⟨0 , ℙ_{+,1} ≡ ℙ_{1} = 1⟩⟨1 , ℙ_{×,0} = 0⟩_{×} ⟨0 and ℙ_{×,1} = 1⟩_{×} ⟨1 for the projections along the four BB84 states. The two possible measurements applied by the receiver of BB84 qubits are 𝕄_{+} = {ℙ_{0}, ℙ_{1}} and 𝕄_{×} = {ℙ_{×,0} , ℙ_{×,1} }. For θ ∈ {+, ×}^{n}, measurement 𝕄_{θ} is the composition of measurements 𝕄_{θ_{i}} for 1 ≤ i ≤ n. In order to simplify the notation, we sometimes associate the rectilinear basis “+” with bit 0 and the diagonal basis with bit 1. We map sequences of rectilinear and diagonal bases into bitstrings the obvious way. In order to indicate that ϕ⟩ ∈ H_{2^{r}} is the state of a quantum register H_{R} ≃ H_{2^{r}} we write ϕ⟩^{R}. If H_{R} ≃ H_{2^{r}} and H_{S} ≃ H_{2^{s}} are two quantum registers and ϕ⟩ = ∑ _{x∈{0,1}^{r}} ∑ _{y∈{0,1}^{s}} γ_{x,y} x⟩⊗ y⟩ ∈ H_{2^{r}} ⊗ H_{2^{s}} then we write ϕ⟩^{RS} = ∑ _{x∈{0,1}^{r}} ∑ _{y∈{0,1}^{s}} γ_{x,y} x⟩^{R} ⊗ y⟩^{S} to denote the state of both registers H_{R} and H_{S}. Given any transformation U^{R} acting on a register H_{R} and any state ϕ⟩ ∈ H_{R} ⊗ H_{Others} ,we write U^{R} ϕ⟩ =^{def} (U^{R} ⊗ 1_{Others} ) ϕ⟩. We use the same notation when U^{R} denotes a projection operator.

Model of Computation In this paper, we model protocols and algorithms by quantum circuits built out of the universal set of quantum gates UG= {CNot, H, P, T}, where CNot denotes the controlled-not, H the one qubit Hadamard gate, P the phase gate, and T is a one qubit gate sometimes refer to as the π/8 gate [16].In addition to the set of gates UG, a quantum circuit is allowed to perform von Neumann measurements in the computational basis 𝕄_{+} . A circuit C executed in the reverse direction is denoted C^{†}. The complexity of the circuit C is simply the number ∥C∥_{UG} of elementary gates in C.

In the following, we use the two Pauli (unitary) transformations σ_{X} (bit flip) and σ_{Z} (conditional phase shift) defined for b ∈ {0, 1} as, σ_{X} : b⟩ ↦ 1 − b⟩ and σ_{Z} : b⟩ ↦ (−1)^{b} b⟩. Assuming U is a one qubit operation and s ∈ {0, 1}^{n}, we write U^{⊗s} = ⊗_{i=1}^{n} U_{i} where U_{i} = 1_{2} if s_{i} = 0 and U_{i} = U if s_{i} = 1. U^{⊗s} is therefore a conditional application of U on each of n registers depending upon the value of s. The maximally entangled state Φ_{n}^{+} ⟩ = 2^{−n/2} ∑ _{x∈{0,1}^{n}} x⟩⊗ x⟩ will be useful in our reduction. This state can easily be constructed from 0^{n}⟩^{L} ⊗ 0^{n}⟩^{R} after applying n H and CNOT gates. A 2-party quantum protocol taking place between A and B is a pair of interactive quantum circuits (P^{A}, P^{B}) applied to some initial product state x_{A}⟩^{A} ⊗ x_{B}⟩^{B} representing A’s and B’s (maybe secret) 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 a protocol execution may have quantum gates in P^{A} and P^{B} acting upon the same quantum registers. We write P^{A} ⊙ P^{B} for the complete quantum circuit when A is interacting with B. The final composite state Ψ_{final} ⟩ obtained after the execution is then written as Ψ_{final} ⟩ = (P^{A} ⊙ P^{B}) x_{A}⟩^{A} x_{B}⟩^{B}. Protocols are to be understood, although not always explicitly stated, as specified by families of interactive quantum circuits, one for each possible value of the security parameter n. We denote by P^{AB} = {(P_{n}^{A}, P_{n}^{B})}_{n>0} such a family of protocols.

3 Definitions

3.1 Computationally Binding Quantum String Commitment

In the following we shall always refer to A as the sender and B as the receiver of some commitment. Such a scheme can be specified by two families of protocols C^{AB} = {(C_{n}^{A}, C_{n}^{B})}_{n>0} , and O^{AB} = {(O_{n}^{A}, O_{n}^{B})}_{n>0} where each pair defined A’s and B’s circuits for the committing and the opening phase respectively. A lstring commitment allows to commit upon strings of length l for n a security parameter. The committing stage generates the state ψ_{s}⟩ = (C_{n}^{A} ⊙ C_{n}^{B}) s⟩^{A} 0⟩^{B} when A commits to s ∈ {0, 1}^{l}. The opening stage is executed from the shared state ψ_{s}⟩ and produces ψ_{final} ⟩ = (O_{n}^{A} ⊙ O_{n}^{B}) ψ_{s}⟩. In [9], the security criteria for computationally binding but otherwise concealing quantum bit commitment schemes were introduced. Here, we follow a similar approach for string commitment schemes.

An adversary Ã = {(C̃_{n}^{A}, Õ_{n}^{A})}_{n>0} for the binding condition is such that ψ̃⟩ = (C̃_{n}^{A} ⊙ C_{n}^{B}) 0⟩^{A} 0⟩^{B} is generated during the committing stage. The dishonest opening circuit Õ_{n}^{A} tries to open s ∈ {0, 1}^{l} given as an extra input in state s⟩^{A}. Given the final state ψ̃_{final} ⟩ = (Õ_{n}^{A} ⊙ O_{n}^{B}) s⟩^{A} ψ̃⟩ we define p̃_{s}(n) as the probability to open s ∈ {0, 1}^{l} with success. More precisely, p̃_{s}(n) = ∥ℚ_{s}^{B} ψ̃_{final} ⟩∥^{2} where ℚ_{s}^{B} is B’s projection operator on the subspace leading to accept the opening of s. The main difference between quantum and classical commitments is the impossibility in the quantum case to determine the committed string s after the committing phase of the protocol. Classically, this can be done by fixing the committer’s random tape so s becomes uniquely determined. In addition, proof techniques like rewinding have no quantum counterpart [17, 18]. A committer (to a concealing commitment) can always commit upon any superposition of values for s that will remain such until the opening phase. A honest committer does not necessarily know a single string that can be unveiled with non-negligible probability of success. Suppose a quantum l–string commitment scheme has committing circuit C_{n}^{A} ⊙ C_{n}^{B} and let ψ(s)⟩^{AB} = (C_{n}^{A} ⊙ C_{n}^{B}) s⟩^{A}. If the committer starts with superposition ∑ _{s} \sqrt{p̃_{s}(n)} s⟩, for any probability distribution \{(p̃_{s}(n), s)\}_{s∈\{0,1\}^{l}} , then the state obtained after the committing phase would be:

∑_{s∈\{0,1\}^{l}} \sqrt{p̃_{s}(n)} ψ(s)⟩^{AB} = C_{n}^{A} ⊙ C_{n}^{B} ( ( ∑_{s∈\{0,1\}^{l}} \sqrt{p̃_{s}(n)} s⟩^{A}) ⊗ 0⟩^{A} ⊗ 0⟩^{B} ) .  (4)

Equation (4) is a valid commitment to a superposition of strings that will always allow the sender to open s with probability p̃_{s}(n). The honest strategy described in (4) achieves ∑ _{s} p̃_{s}(n) = 1. In [9], the binding condition is satisfied if no adversary can do significantly better than what is achievable by (4) in the special case where l = 1. More precisely, a bit commitment scheme is binding if for all adversaries Ã:

p̃_{0}(n) + p̃_{1}(n) < 1 + 1/poly(n)  (5)

where p̃_{b}(n) is the probability to open bit b with success. Extending this definition to the case where l ∈ Ω(n) must be done with care however. The obvious generalization of (5) to the requirement ∑ _{s∈{0,1}^{l}} p̃_{s}(n) < 1 + 1/poly(n) is too strong whenever l ∈ Ω(n). For example, if l = n and p̃_{s}(n) = 2^{−n} (1 + \frac{1}{p(n)} ) for all strings s ∈ {0, 1}^{n} then Ã’s behaviour is indistinguishable in polynomial time from what is achievable with the honest state (4) resulting from distribution {(2^{−n} , s)}_{s}. Any such attack that cannot be distinguished from the honest behavior should hardly be considered successful. On the other hand, defining a successful adversary Ã as one who can open s and s′ (s ≠ s′) such that p̃_{s}(n) + p̃_{s′}(n) ≥ 1 + 1/p(n) is in general too weak when one tries to reduce the security of a protocol to the security of the string commitment used by that protocol (as we shall see for QMCs). Breaking a protocol could be reduced to breaking the string commitment scheme in a more subtle way. In general, the possibility to commit upon several strings in superposition can be used by the adversary to make his attack against the binding condition even more peculiar. Instead of trying to open a particular string s ∈ {0, 1}^{l}, an attacker could be interested in opening any s ∈ {0, 1}^{l} such that f(s) = y for some function f : {0, 1}^{l} → {0, 1}^{m} with m ≤ l. We shall see in the following that the security of QMC is guaranteed provided the string commitment does not allow the committer to mount such an attack for a special class of functions. Such an adversary is defined by a family of interactive quantum circuits Ã^{f} = {(C̃_{n}^{A}, Õ_{n}^{A})}_{n>0} such that ψ̃⟩ = (C̃_{n}^{A} ⊙ C_{n}^{B}) 0⟩^{A} 0⟩^{B} is the state generated during the committing phase of the protocol and ψ̃(y)⟩ = (Õ_{n}^{A} ⊙ O_{n}^{B}) y⟩^{A} ψ̃⟩^{AB} is the state (hopefully) allowing to open s ∈ {0, 1}^{l} such that f(s) = y. The probability to succeed during the opening stage is,

p̃_{y}^{f}(n) = ∥ ∑_{s∈{0,1}^{l}:f(s)=y} ℚ_{s}^{B} ψ̃(y)⟩∥^{2},  (6)

where ℚ_{s}^{B} is B’s projector operator leading to accept the opening of s ∈ {0, 1}^{l}. The following binding criteria takes into account such attacks:

Definition 1. Let F ⊆ {f : {0, 1}^{l} → {0, 1}^{m}} be a set of functions where m ≤ l. A l-string commitment scheme is computationally F -binding if for any f ∈ F and any adversary Ã^{f} such that ∥Ã^{f} ∥_{UG} ≤ poly(n), we have

∑_{y∈{0,1}^{m}} p̃_{y}^{f}(n) < 1 + 1/poly(n) where p̃_{y}^{f}(n) is defined as in (6).  (7)

Note that any standard attack can be expressed in terms of an appropriate class of functions F. In general, the smaller m is with respect to l, the weaker is the F –binding criteria. A class of functions of particular interest is built out of s_{1}(x, y) = x, s_{2}(x, y) = y, and s_{3}(x, y) = x ⊕ y for all x, y ∈ {0, 1}. Let I_{m}^{n} be the set of subsets of {1, …, n} having size exactly m, we define the class of functions F_{m}^{n} as,

F_{m}^{n} = { f_{I} : {0, 1}^{2n} → {0, 1}^{m}|I ∈ I_{m}^{n}, f_{I}(x, y) = ♦_{h∈I} s_{j_{h}} (x_{h}, y_{h}), where j_{h} ∈ {1, 2, 3} for h ∈ I }  .  (8)

In other words, F_{m}^{n} contains the set of functions f such that each output bit of f(x, y) is a bit in x or y or x⊕y. Notice that no quantum string commitment has been formally shown F -binding even for F with small range. We believe however that the commitment of [7] can be turned into a F_{m}^{n}-binding string commitment but this analysis is beyond the scope of this paper.

3.2 Commitment to Quantum Measurement

Quantum Measurement Commitment (QMC) is a primitive allowing the receiver of random qubits to show the sender that they have been measured without disclosing any further information about the measurement and the outcome. In this paper we restrict our attention to quantum transmission of random BB84 qubits. The measurements performed by the receiver are, for each transmission, independently chosen in {𝕄_{+} , 𝕄_{×} }. We model QMCs by the following game between players A and B:

1. B sends n random BB84 qubits in state b⟩_{θ} for b ∈_{R} {0, 1}^{n} and θ ∈_{R} {+, ×}^{n},

2. A applies measurement 𝕄θ̂ for θ̂ ∈_{R} {+, ×}^{n} producing classical outcome b̂∈ {0, 1}^{n},

3. A uses a 2n-string commitment in order to commit to (θ̂,b̂) toward B,

4. B picks and announces a random challenge c ∈_{R} {0, 1}, – If c = 0 then A opens (θ̂,b̂) and B verifies that b̂_{i} = b_{i} for all i such that θ̂_{i} = θ_{i}, otherwise B aborts,

– If c = 1 then B announces θ and A tries to bias [b].

A wants to maximize both her success probability when unveiling and the bias on [b] whenever θ is announced. This is almost identical to the receiver’s situation in the CK protocol[6]. Since we only consider unconditionally concealing string commitments, B gets information about A’s measurements and results only if they are unveiled. As we shall see next, this flavor of commitments allow A to postpone her measurement until the unveiling stage. The commitment stage should nevertheless ensure B that A cannot use this ability for improving her situation compared to the case where she measures completely before committing. In other words, although this flavor of commitment cannot force A to measure upon the committing stage, it should do as such through the actions of a computationally bounded A.

We model the adversary Ã by a family of interactive quantum circuits Ã = {(C̃_{n}^{A}, Õ_{n}^{A}, Ẽ_{n})}_{n>0} where C̃_{n}^{A} and Õ_{n}^{A} are Ã’s circuits for the committing and the opening phases. Circuit Ẽ_{n} allows to extract the parity of b upon the announcement of basis θ. Circuit C̃_{n}^{A} works upon Ã’s internal registers H_{A} together with the register H_{channel} storing the BB84 qubits. We denote by

ψ_{θ,b}⟩^{AB} = (C̃_{n}^{A} ⊙ C_{n}^{B}) b⟩_{θ}^{channel} ,  (9)

the resulting state after the committing phase (step 3). This state should allow Ã to succeed both challenges with good probability. By linearity, we have that for all θ, b, x ∈ {0, 1}^{n},

ψ_{θ,b}⟩ = 2^{− \frac{|x|}{2}} ∑_{y:y⪯x} (−1)^{b⊙x⊕b⊙y} ψ_{θ⊕x,b⊕y} ⟩.  (10)

The probability to open with success p̃_{(θ,b)}^{ok}(n), when b⟩_{θ} was sent, is

p̃_{(θ,b)}^{ok}(n) = ∑_{(θ̂,b̂)∈Δ_{⪯} (θ,b)} ∥ℚ_{(θ̂,b̂)}^{B}(Õ_{n}^{A} ⊙ O_{n}^{B}) ψ_{θ,b}⟩∥^{2} = ∥ℚ_{(θ,b)}^{∗} ψ_{θ,b}⟩∥^{2},  (11)

for ℚ_{(θ̂,b̂)}^{B} the projection operator applied upon B’s registers and leading to a valid opening of (θ̂,b̂) ∈ {0, 1}^{2n}.

The opening of (θ̂,b̂) is accepted by B iff (θ̂,b̂) ∈ Δ_{⪯} (θ, b). For simplicity, circuits Õ_{n}^{A}⊙O_{n}^{B} can be included in the description of ℚ_{(θ̂,b̂)}^{B} so the opening process can be seen as a single projection ℚ_{(θ,b)}^{∗} = ∑ _{(θ̂,b̂)∈Δ_{⪯} (θ,b)} ℚ_{(θ̂,b̂)}^{B}.

The expected probability of success p̃^{ok}(n) is,

p̃^{ok}(n) = \frac{1}{4^{n}} ∑_{b∈\{0,1\}^{n}} ∑_{θ∈\{+,×\}^{n}} p̃_{(θ,b)}^{ok}(n).  (12)

When c = 1, Ã should be able, given the announcement of θ, to extract information about the parity [b].The extractor Ẽ_{n} has access to an extra register H_{Θ} storing the basis θ ∈ {+, ×}^{n}. The extractor stores the guess for [b] in register H_{⊕} . The bias ε̃_{θ,b}(n) provided by the extractor when the qubits were initially in state b⟩_{θ} is

ε̃_{θ,b}(n) = ∥ℙ_{[b]}^{⊕}(Ẽ_{n} ⊗ 1_{B}) θ⟩^{Θ} 0⟩^{⊕} ψ_{θ,b}⟩^{AB}∥^{2},  (13)

where ℙ_{[b]}^{⊕}is applied upon the output register H_{⊕} . The expected value ε̃(n) for the bias provided by Ẽ_{n} is,

ε̃(n) = \frac{1}{4^{n}} ∑_{b∈\{0,1\}^{n}} ∑_{θ∈\{+,×\}^{n}} ε̃_{θ,b}(n).  (14)

We characterize Ã’s behavior against QMC by both p̃^{ok}(n) and ε̃(n). Independently of the string commitment scheme used, there always exists Ã^{∗} preparing a superposition of attacks that 1) provides [b] with certainty and 2) succeeds with probability 1 during the opening. Such an attack can be implemented as follows:

ψ_{θ,b}^{∗}⟩ = α(C_{n}^{A} ⊙ C_{n}^{B}) b⟩_{θ}^{channel} + β(C_{n}^{A} ⊙ C_{n}^{B}) 0^{n}⟩_{+^{n}}^{channel}  (15)

where |α|^{2} + |β|^{2} = 1 and C_{n}^{A} and C_{n}^{B} are the honest circuits for committing. The state ψ_{θ,b}^{∗}⟩ is a superposition of the honest behavior with probability |α|^{2} and the trivial attack consisting in not measuring the qubits received with probability |β|^{2}. The expected probability of success p^{∗}(n) is

p^{∗}(n) = |α|^{2} + |β|^{2}(\frac{3}{4})^{n} ≈ |α|^{2}  (16)

since with probability |α|^{2} an honest QMC was executed and with probability |β|^{2} a QMC to the fixed state 0^{n}⟩_{θ} was made. In the later case, the probability to pass B’s test is (3/4)^{n}. The expected bias satisfies

ε^{∗}(n) = \frac{|α|^{2}}{2} (\frac{1}{2})^{n} + \frac{|β|^{2}}{2} ≈ \frac{|β|^{2}}{2}  (17)

since with probability |α|^{2} a QMC to b⟩_{θ} is recovered (in which case a nonzero bias on [b] occurs only when θ̂ = θ) and with probability |β|^{2} a QMC to a dummy value is made allowing to extract [b] perfectly. Such an attack does not enable the committer to break the binding property of the string commitment but achieves: p^{∗}(n) + 2ε^{∗}(n) > 1. We define two flavors of adversaries against QMC. The first flavor captures any adversary that achieves anything better than the trivial adversary Ã^{∗} defined in (15). The second flavor captures stronger adversaries for which our reduction will be shown to produce attacks against the F_{m}^{n}–binding property of the string commitment.

Definition 2. An adversary Ã = {(C̃_{n}^{A}, Õ_{n}^{A}, Ẽ_{n})}_{n>0} against QMC is δ(n)–non-trivial if p̃^{ok}(n)+2ε̃(n) ≥ 1 + δ(n), and δ(n)–good if p̃^{ok}(n) + 4ε̃(n)^{2} ≥ 1 + δ(n) for p̃^{ok}(n) and ε̃(n) defined as in (12) and (14) respectively.

Notice that if Ã is not δ(n)-good (or δ(n)-non-trivial) then an upper bound on ε̃(n) can be obtained from a lower bound on p̃^{ok}(n). This is how we use QMCs for implementing oblivious transfer in Sect. 6.

4 The Reduction

Using a good adversary Ã against QMC, we would like to build an adversary against the F -binding property of the underlying string commitment. In this section, we provide the first step of the reduction provided Ã’s parity extractor is perfect. We construct a circuit built from Ã allowing to prepare a commitment into which any ψ_{θ,b}⟩ can be inserted efficiently at the opening stage. In Sect. 5, we show how to use this circuit for attacking the binding property of the string commitment.

4.1 The Switching Circuit

Let Ã = {(C̃_{n}^{A}, Õ_{n}^{A}, Ẽ_{n})}_{n>0} be an adversary in QMC. We call H_{Keep} the register kept by Ã after the committing phase. We denote by H_{B} the register containing what is sent by A and kept by B after the committing phase. H_{Q} ≃ H_{2^{n}} denotes the register containing the BB84 qubits before the commitment, H_{Θ} ≃ H_{2^{n}} denotes the register for the basis given as input to the extractor, and H_{⊕} ≃ H_{2} denotes the register in which the guess on [b] is stored by the extractor.

Instead of running C̃_{n} ≡ (C̃_{n}^{A} ⊙ C_{n}^{B}) upon some BB84 qubits, we run it with the maximally entangled state Φ_{n}^{+} ⟩ where the first half is stored in H_{Θ} and the second half stored in H_{Q}. Therefore, the basis given as input to the extractor is not a classical state but is rather entangled with register H_{Q} containing the qubits Ã is committed upon. After the execution of C̃_{n} Φ_{n}^{+} ⟩^{Θ,Q} , transformations B^{⊗b} and T^{⊗θ} are applied to register H_{Θ} in order to prepare the input for the extractor where, B = σ_{X} σ_{Z} and T = H σ_{Z}. Ẽ_{n} is then run before σ_{Z} is applied upon the extractor’s output register H_{⊕} . The transformation is completed by running the extractor in reverse. The resulting circuit is called the switching circuit:

Next, we see that whenever the parity extractor is perfect (i.e. Ẽ_{n} ≡ E_{n}), the switching circuit using transformations B^{⊗b} and T^{⊗θ} generates ψ_{θ,b}⟩. To see this, we follow its evolution from the initial state Φ_{n}^{+} ⟩. We first look at the state generated before the extractor is applied,

Φ_{n}^{+} ⟩ ≡ ∑_{s} \frac{1}{\sqrt{2}^{n}} s⟩ s⟩ C̃_{n} ; ⟼→ ∑_{s} \frac{1}{\sqrt{2}^{n}} s⟩ ψ_{+^{n} ,s}⟩ {B^{⊗b} \atop ⟼→} ∑_{s} \frac{(−1)^{b⊙s}}{\sqrt{2}^{n}} b ⊕ s⟩ ψ_{+^{n} ,s}⟩

{T^{⊗θ} \atop ⟼→} ∑_{s,t : t⪯θ} \frac{(−1)^{b⊙s ⊕ b⊙t ⊕ s⊙t}}{\sqrt{2}^{n+|θ|}}  b ⊕ s ⊕ t⟩ ψ_{+^{n} ,s}⟩  (18)

= ∑_{s,t,v : {t⪯θ \atop v⪯b⊕s⊕t}} \frac{(−1)^{b⊙t ⊕ s⊙v ⊕ s⊙s}}{\sqrt{2}^{n+|θ|+|b⊕s⊕t |}}  b ⊕ s ⊕ t⟩ ψ_{b⊕s⊕t ,s⊕v} ⟩.  (19)

The states up to (18) are obtained by definition of Φ_{n}^{+} ⟩, C̃_{n}, B^{⊗b}, and T^{⊗θ} . Equation (19) follows after changing the basis from +^{n} to b ⊕ s ⊕ t using (10). From (19), we follow the evolution through E_{n}^{†}σ_{Z}E_{n},

Ψ_{θ,b}⟩ ≡ T^{⊗θ} B^{⊗b} C_{n} Φ_{n}^{+} ⟩ {E_{n}^{†} σ_{z} E_{n} \atop ⟼→} ∑_{s,t,v : {t⪯θ \atop v⪯b⊕s⊕t}} \frac{(−1)^{b⊙t ⊕ s⊙v ⊕ v⊙v}}{\sqrt{2}^{n+|θ|+|b⊕s⊕t |}}  b ⊕ s ⊕ t⟩ ψ_{b⊕s⊕t ,s⊕v} ⟩  (20)

= ∑_{x,y,v : {v⊕x⊕y⪯θ \atop v⪯θ⊕x}} \frac{(−1)^{b⊙θ ⊕ b⊙x ⊕ b⊙y ⊕ v⊙y}}{\sqrt{2}^{n+|θ|+|θ⊕x |}}  θ ⊕ x⟩ ψ_{θ⊕x ,b⊕y} ⟩

= ∑_{y⪯x} \frac{(−1)^{b⊙θ ⊕ b⊙x ⊕ b⊙y}}{\sqrt{2}^{n+|θ|+|θ⊕x |−2|θ∧x̄ |}} θ ⊕ x⟩ ψ_{θ⊕x ,b⊕y} ⟩

= ∑_{y⪯x} \frac{(−1)^{b⊙θ ⊕ b⊙x ⊕ b⊙y}}{\sqrt{2}^{n+|x|}}  θ ⊕ x⟩ ψ_{θ⊕x ,b⊕y} ⟩  (21)

= ∑_{x} \frac{(−1)^{b⊙θ}}{\sqrt{2}^{n}} θ ⊕ x⟩ ⊗ ∑_{y : y⪯x} \frac{(−1)^{b⊙x ⊕ b⊙y}}{\sqrt{2}^{|x|}} ψ_{θ⊕x ,b⊕y} ⟩

= ∑_{x} \frac{(−1)^{b⊙θ}}{\sqrt{2}^{n}} θ ⊕ x⟩ ψ_{θ,b}⟩.  (22)

Equation (20) follows from the fact that the extractor is perfect. Equation (21) follows after using (1). We finally get (22) from (10).

In conclusion, a perfect extractor allows to produce a commitment inside which any ψ_{θ,b}⟩ can be put efficiently during the opening phase.

5 Analysis

We analyze the switching circuit when it is run with imperfect parity extractors. We first show how states { Ψ̃_{θ,b}⟩}_{θ,b}, produced in this case, overlap with states { Ψ_{θ,b}⟩}_{θ,b} generated when perfect extractors are available. In Sect. 5.2, we represent the behavior of the switching circuit by a table.In Sect. 5.3, we relate the table representation to attacks against the F_{m}^{n}–binding property of the string commitment.

5.1 Generalization to Imperfect Extractors

Assume the adversary Ã = {(C̃_{n}^{A}, Õ_{n}^{A}, Ẽ_{n})}_{n>0} has access to an imperfect extractor. Ẽ_{n} modeled as follows:

Ẽ_{n} θ⟩^{Θ} ψ_{θ,b}⟩ = θ⟩^{Θ} ⊗ (γ_{θ,b} [b]⟩^{⊕} φ_{θ,b}⟩ + γ̂_{θ,b} 1 ⊕ [b]⟩^{⊕} φ̂_{θ,b}⟩) .  (23)

Without loss of generality, we may assume that both γ_{θ,b} and γ̂_{θ,b} are real positive numbers such that |γ_{θ,b}|^{2} ≥ \frac{1}{2} (i.e. arbitrary phases can be added to φ_{θ,b}⟩ and φ̂_{θ,b}⟩). According (14), the expected bias provided by Ẽ_{n} is,

ε̃(n) ≡ 4^{−n} ∑_{θ} ∑_{b} ε̃_{θ,b}(n) = 4^{−n} ∑_{θ} ∑_{b} ||γ_{θ,b}|^{2} − \frac{1}{2}| .  (24)

Compared to the case where the extractor is perfect, only the effect of transformation Ẽ_{n}^{†}σ_{Z} Ẽ_{n} needs to be recomputed. From (23), we obtain,

Ẽ_{n}^{†}σ_{Z} Ẽ_{n} θ⟩ ψ_{θ,b}⟩ = (−1)^{[b]} θ⟩ ψ_{θ,b}⟩ − 2(−1)^{[b]}γ̂_{θ,b}Ẽ_{n}^{†} ( θ⟩ 1 ⊕ [b]⟩^{⊕} φ̂_{θ,b}⟩) .  (25)

We now define the vector e⃗_{θ,b} such that θ⟩⊗ e⃗_{θ,b} ≡ −2γ̂_{θ,b}Ẽ_{n}^{†}( θ⟩ 1 ⊕ [b]⟩ φ̂_{θ,b}⟩) so that (25) becomes

(Ẽ_{n}^{†}σ_{Z} Ẽ_{n}) θ⟩ ψ_{θ,b}⟩ = (−1)^{[b]} θ⟩⊗ ( ψ_{θ,b}⟩ + e⃗_{θ,b}) .  (26)

The final state Ψ̃_{θ,b}⟩produced by the switching circuit can be obtained easily from (20) using (26). We get,

Ψ̃_{θ,b}⟩= Ẽ_{n}^{†}σ_{z} Ẽ_{n}T^{⊗θ} B^{⊗b} C_{n} Φ_{n}^{+} ⟩ = ∑_{y⪯x} \frac{(−1)^{b⊙θ ⊕ b⊙x ⊕ b⊙y}}{\sqrt{2}^{n+|x|}}  θ ⊕ x⟩ ⊗ ( ψ_{θ⊕x ,b⊕y} ⟩ + e⃗_{θ⊕x,b⊕y} ) .  (27)

Splitting the inner sum of (27) gives,

Ψ̃_{θ,b}⟩= Ψ_{θ,b}⟩ + F⃗_{θ,b} where,  (28)
Ψ_{θ,b}⟩ = ∑_{y⪯x} \frac{(−1)^{b⊙θ⊕b⊙x⊕b⊙y}}{\sqrt{2}^{n+|x|}}  θ ⊕ x⟩ ψ_{θ⊕x,b⊕y} ⟩, and F⃗_{θ,b} = ∑_{y⪯x} \frac{(−1)^{b⊙θ⊕b⊙x⊕b⊙y}}{\sqrt{2}^{n+|x|}}  θ ⊕ x⟩ ⊗ e⃗_{θ⊕x,b⊕y} .

The first part Ψ_{θ,b}⟩ = (2^{−n/2} ∑ _{x}(−1)^{b⊙θ} θ⟩) ⊗ ψ_{θ,b}⟩ is exactly what one gets when the switching circuit is run with a perfect extractor (see (22)). The second part is the error term for which next lemma gives a precise characterization.

Lemma 2. Consider the switching circuit built from adversary Ã = {(C̃_{n}^{A}, Õ_{n}^{A}, Ẽ_{n})}_{n>0} . Then,

4^{−n} ∑_{θ} ∑_{b} ∥F⃗_{θ,b}∥^{2} ≤ 2 − 4ε̃(n).

Proof. Let θ be fixed. Using the definition of F⃗_{θ,b}, we get

2^{−n} ∑_{b∈\{0,1\}^{n}} ∥F⃗_{θ,b}∥^{2} = 2^{−n} ∑_{b} ∥ ∑_{y⪯x} \frac{(−1)^{b⊙θ⊕b⊙x⊕b⊙y}}{\sqrt{2}^{n+|x|}}  θ ⊕ x⟩ ⊗ e⃗_{θ⊕x,b⊕y} ∥^{2}

= 2^{−n} ∑_{b} ∥ ∑_{x} \frac{(−1)^{b⊙θ⊕b⊙x}}{\sqrt{2}^{n+|x|}} θ ⊕ x⟩ ⊗ ∑_{y:y⪯x} (−1)^{b⊙y} e⃗_{θ⊕x,b⊕y} ∥^{2}
= 2^{−2n−|x|} ∑_{x} ∑_{b} ∥ ∑_{y:y⪯x} (−1)^{b⊙y} e⃗_{θ⊕x,b⊕y} ∥^{2},  (29)

where (29) is obtained from the orthogonality of all e⃗_{θ⊕x,b⊕y} when x varies, and from Pythagoras theorem. We now apply Lemma 1 to (29) with A = {y ∈ {0, 1}^{n}|y ⪯ x}, w ≡ b,z ≡ y, and v⃗_{w,z} ≡ e⃗_{θ⊕x,b⊕y} . We first verify that the condition expressed in (2) is satisfied:

∑_{b} ∑_{y_{1}∈A:b⊕y_{1}=s} ∑_{y_{2}∈A:b⊕y_{2}=t} (−1)^{b⊙(y_{1}⊕y_{2})} ⟨e⃗_{θ⊕x,b⊕y_{1}} , e⃗_{θ⊕x,b⊕y_{2}} ⟩ = ⟨e⃗_{θ⊕x,s} , e⃗_{θ⊕x,t} ⟩ ∑_{b⊕s⪯x,b⊕t⪯x^{b:}} (−1)^{b⊙(s⊕t)} = 0

from an identity equivalent to (1) since b runs aver all substrings in the support of s ⊕ t ⪯ x. We therefore apply the conclusion of Lemma 1 to get that for all x ∈ {0, 1}^{n},

∑_{b} ∥ ∑_{y:y⪯x} (−1)^{b⊙y} e⃗_{θ⊕x,b⊕y} ∥^{2} = ∑_{y:y⪯x} ∑_{b} ∥e⃗_{θ⊕x,b⊕y} ∥^{2} ≤ 2^{n+|x|} (2 − 4ε̃(n)).  (30)

The result follows after replacing (30) in (29). ⊓⊔

Using Lemma 2, we show how the the output of the switching circuit with imperfect extractors approaches the one with perfect extractors. Next lemma gives an upper bound on the expected overlap between the states produced using perfect and imperfect extractors.

Lemma 3. Let Ã = {(C̃_{n}^{A}, Õ_{n}^{A}, Ẽ_{n})}_{n>0} be the circuits for the adversary such that the extractor Ẽ_{n} has expected bias ε̃(n). Then, the set of states { Ψ̃_{θ,b}⟩}_{b,θ} produced by the switching circuit satisfies,

SÃ = 4^{−n} ∑_{b,θ} |⟨Ψ̃_{θ,b} Ψ_{θ,b}⟩| ≥ 2ε̃(n).

Proof. According (28), we can write Ψ̃_{θ,b}⟩ = Ψ_{θ,b}⟩ + F⃗_{θ,b} = (1 − α_{θ,b}) Ψ_{θ,b}⟩ + β_{θ,b} Ψ_{θ,b}^{⊥}⟩, where 1 = ∥ Ψ̃_{θ,b}⟩∥^{2} = |(1 − α_{θ,b})|^{2} + |β_{θ,b}|^{2} and ⟨Ψ_{θ,b} Ψ_{θ,b}^{⊥}⟩ = 0. Isolating |α_{θ,b}| and using the fact that |α_{θ,b}|^{2} + |β_{θ,b}|^{2} = ∥F⃗_{θ,b}∥^{2} gives,

|α_{θ,b}| = \frac{∥F⃗_{θ,b}∥^{2}}{2}.  (31)

Using (31) and Lemma 2, SÃ = ∑ _{θ,b}4^{−n} |⟨Ψ̃_{θ,b} Ψ_{θ,b}⟩| ≥ ∑ _{θ,b}4^{−n} (1−|α_{θ,b}|) = 1−∑ _{θ,b}4^{−n} \frac{∥F⃗_{θ,b}∥^{2}}{2} ≥ 2ε̃(n). ⊓⊔

Lemma 3 tells us that with good extractors, one can generate states having large overlap with all QMCs to different BB84 qubits chosen upon the opening stage of the commitment scheme. It remains to show how to use this ability to break the binding property.

5.2 Representing The Switching Circuit by a Table

In this section, we look at how to use the switching circuit in order to attack the binding criteria of the string commitment. Remember first that ψ_{θ,b}⟩ has probability p̃_{(θ,b)}^{ok}(n) = ∥ℚ_{(θ,b)}^{∗} ψ_{θ,b}⟩∥^{2} to open a valid QMC to b⟩_{θ} where ℚ_{(θ,b)}^{∗} is defined as in (11). Remember that a valid opening of b⟩_{θ} consists in the opening of any 2n–bit string (θ̂,b̂) ∈ Δ_{⪯} (θ, b). We take advantage of the structure of Δ_{⪯} (θ, b) in order to exhibit attacks against the binding condition.

Suppose first that adversary Ã has access to a perfect parity extractor E_{n}. From Sect. 4.1, such an adversary can generate ψ_{θ,b}⟩ for any choice of θ ∈ {+, ×}^{n} and b ∈ {0, 1}^{n}. Each of 4^{n} sets of valid announcements Δ_{⪯} (θ, b) is of size #Δ_{⪯} (θ, b) = 3^{n}. We define a table of positive real numbers having 4^{n} rows and 3^{n} columns where each row is labeled by a pair (θ, b). The row (θ, b) contains values T_{θ,b}(τ, β) = ∥ℚ_{(θ⊕τ,b⊕β)}^{B} ψ_{θ,b}⟩∥^{2} for all (τ, β) such that (θ ⊕ τ, b ⊕ β) ∈ Δ_{⪯} (θ, b). This condition is equivalent to (τ, β) such that β ⪯ τ. The table values for the case n = 1 are shown in Fig. 1. The sum of each row is added to the right. The construction is easily generalized for arbitrary n. Each column contains 4^{n} orthogonal projectors

\begin{matrix}∥ℚ_{(+,0)}^{B} ψ_{+,0} ⟩∥^{2} & ∥ℚ_{(×,0)}^{B} ψ_{+,0} ⟩∥^{2} & ∥ℚ_{(×,1)}^{B} ψ_{+,0} ⟩∥^{2} & p̃_{(+,0)}^{ok} (n) = ∥ℚ_{(+,0)}^{∗} ψ_{+,0} ⟩∥^{2} \\ ∥ℚ_{(+,1)}^{B} ψ_{+,1} ⟩∥^{2} & ∥ℚ_{(×,1)}^{B} ψ_{+,1} ⟩∥^{2} & ∥ℚ_{(×,0)}^{B} ψ_{+,1} ⟩∥^{2} & p̃_{(+,1)}^{ok} (n) = ∥ℚ_{(+,1)}^{∗} ψ_{+,1} ⟩∥^{2} \\ ∥ℚ_{(×,0)}^{B} ψ_{×,0} ⟩∥^{2} & ∥ℚ_{(+,0)}^{B} ψ_{×,0} ⟩∥^{2} & ∥ℚ_{(+,1)}^{B} ψ_{×,0} ⟩∥^{2} & p̃_{(×,0)}^{ok} (n) = ∥ℚ_{(×,0)}^{∗} ψ_{×,0} ⟩∥^{2} \\ ∥ℚ_{(×,1)}^{B} ψ_{×,1} ⟩∥^{2} & ∥ℚ_{(+,1)}^{B} ψ_{×,1} ⟩∥^{2} & ∥ℚ_{(+,0)}^{B} ψ_{×,1} ⟩∥^{2} & p̃_{(×,1)}^{ok} (n) = ∥ℚ_{(×,1)}^{∗} ψ_{×,1} ⟩∥^{2} \end{matrix}

Fig. 1. The table for the case n = 1 and perfect extractor.

applied to the 4^{n} states { ψ_{θ,b}⟩}_{θ,b}. The sum of all values in the table is simply 4^{n}p̃^{ok}(n) = ∑ _{θ,b}p̃_{(θ,b)}^{ok}(n).

The table is defined similarly for imperfect parity extractors. In this case, table TÃ = {T_{θ,b}(τ, β)}_{θ,b,τ,β⪯τ} associated with adversary Ã contains elements,

T_{θ,b}(τ, β) = ∥ℚ_{(θ⊕τ,b⊕β)}^{B} Ψ̃_{θ,b}⟩∥^{2}.  (32)

While for perfect extractors the sum over all elements in the table is at least 4^{n}p̃^{ok}(n), next theorem shows that any table TÃ built from a δ(n)–good adversary adds up to 4^{n}poly(δ(n)). The proof is a consequence of Lemma 3 and can be found in Appendix B. Theorem 1. If Ã = {(C̃_{n}^{A}, Õ_{n}^{A}, Ẽ_{n})}_{n>0} is a δ(n)–good adversary against QMC and TÃ = {T_{θ,b}(τ, β)}_{θ,b,τ,β⪯τ} is its associated table, then

∑_{θ,b,τ} ∑_{β⪯τ} T_{θ,b}(τ, β) ≥ \frac{4^{n}δ(n)^{3}}{32}.  (33)

Theorem 1 establishes the existence of one column in TÃ providing a weak attack since any table with 3^{n} columns all summing up to more than \frac{4^{n} δ(n)^{3}}{32} has one column exceeding (\frac{2}{3})^{n} \frac{δ(n)^{2}}{32} ≫ 1 + 1/poly(n). Let (τ, β) be such a column and consider the class of functions 1_{2n} containing only the identity. For (y, y′) ∈ {0, 1}^{2n}, the state Ψ̃_{y⊕τ,y′⊕β} ⟩ can be generated using the switching circuit. The probability to unveil (y, y′) is T_{y⊕τ,y′⊕β} (τ, β) = ∥ℚ_{(y,y′)}^{B} Ψ̃_{y⊕τ,y′⊕β} ⟩∥^{2}. By construction, we have ∑ _{(y,y′)} p̃_{(y,y′)}^{f}(n) = ∑ _{(y,y′)} T_{y⊕τ,y′⊕β} (τ, β) > 1 + 1/poly(n) which provides an attack against the string commitment’s 1_{2n}– binding property in accordance with (7). As we have seen in Sect. 3.1 however, this attack might not even be statistically distinguishable from the trivial adversary. In the next section, we find stronger attacks allowing to relax the binding property required for secure QMC.

5.3 Strong Attacks Against the String Commitment

We now show that the table TÃ, built out of any δ(n)–good adversary Ã, contains an attack against the F_{m}^{n}–binding property of the 2n–string commitment with m ∈ O(polylog(n)) whenever δ(n) ≥ 1/poly(n). We show this using a counting argument. We cover uniformly the table TÃ with all attacks in F_{m}^{n}. Theorem 1 is then invoked in order to conclude that for some f ∈ F_{m}^{n}, condition (7) does not hold.

Attacking the binding condition according to a function f ∈ F_{m}^{n} is done by grouping columns in TÃ as described in (6) and discussed in more details in Appendix C. The number of lines involved in such an attack is clearly 2^{m} while the number of columns can be shown to be 2^{m}3^{n−m} (see Appendix C and Lemma 4). This means that any attack in F_{m}^{n} covers t = 3^{n−m} 4^{m} elements in TÃ. The quality of such an attack is characterized by the sum of all elements in the sub-array defined by the attack since this sum corresponds to the value of (7). Let tÃ = 3^{n}4^{n} be the total number of elements in TÃ and let sÃ be its sum. The following lemma, proved in Appendix D, shows that all attacks in F_{m}^{n} cover TÃ uniformly:

Lemma 4. All attacks f ∈ F_{m}^{n} cover TÃ uniformly, that is, each element in TÃ belongs to exactly a = C(m, n)4^{m} attacks each of size t = 3^{n−m} 4^{m}.

Let s^{∗} be the maximum of (7) for all attacks f ∈ F_{m}^{n}. Clearly, a · s^{∗} ≥ \frac{a·t·sÃ}{tÃ} since by Lemma 4, the covering of TÃ by f ∈ F_{m}^{n} is uniform and a · t/tÃ is the number of times TÃ is generated by attacks in F_{m}^{n}. In other words,

a · s^{∗} ≥ \frac{a · t · sÃ}{tÃ}= \frac{a · t · sÃ}{3^{n}4^{n}}⇒ s^{∗} ≥ \frac{t · sÃ}{3^{n}4^{n}} = \frac{4^{m} · sÃ}{3^{m}4^{n}}.  (34)

Assuming that Ã is δ(n)–good, Theorem 1 tells us that sÃ ≥ \frac{4^{n} δ(n)^{3}}{32} . Replacing in (34) finally leads to,

s^{∗} ≥ \frac{δ(n)^{3}4^{m}}{32 · 3^{m}} ≥ 1 + 1/poly(n),  (35)

for any m ≥ ⌈log_{\frac{4}{3}} ( \frac{32}{δ(n)^{3}} )⌉. Equation (35) guarantees that for at least one f ∈ F_{m}^{n}, condition (7) is not satisfied thereby providing an attack against the F_{m}^{n}–binding criteria. Moreover, since δ(n) ≥ 1/poly(n) it is sufficient that m ∈ O(polylog(n)).

6 The Main Result and Its Application to Oblivious Transfer

Putting together Theorem 1 and (35) leads to our main result:

Theorem 2 (Main). Any δ(n)–good adversary Ã against QMC can break the F_{m}^{n}–binding property of the string commitment it is built upon for m ∈ O(log \frac{1}{δ(n)} ) using a circuit of size O(∥Ã∥_{UG}).

Theorem 2 has an immediate application to the security of 1 − 2-OT in the computational setting. We can easily observe that a QMC implements a weak 1 − 2 oblivious transfer (i.e. WOT) where

- the sender has no information about the receiver’s selection bit and,

- the receiver, according to Theorem 2, can only extract a limited amount of information about both bits. The following primitive, called W_{n}, accepts B’s input bits (β_{0}, β_{1}) and A’s selection bit s and builds a WOT from a QMC (very similar to the CK protocol[6]):

Protocol W_{n}

1. B and A run the committing phase of a QMC (i.e. built from any F_{m}^{n} -binding string commitment scheme) upon b⟩_{θ} for b ∈_{R} {0, 1}^{n}, θ ∈_{R} {+, ×}^{n} picked by B,

2. B chooses c ∈_{R} {0, 1} and announces it to A, – if c = 0 then A unveils the QMC, if unveil succeeds then A and B return to 1 otherwise B aborts,

– if c = 1 then B announces θ, A announces a partition I_{0}, I_{1} ⊆ {1, …, n} such that for all i ∈ I_{s} the measurements were made in basis θ̂_{i} = θ_{i}, then B announces a_{0}, a_{1} ∈ {0, 1} s.t. β_{0} = a_{0} ⊕_{i∈I_{0}} b_{i} and β_{1} = ⊕_{i∈I_{1}} b_{i}:

• A does her best to guess (b̂_{0}, b̂_{1}) ≈ (⨁ _{i∈I_{0}} b_{i}, ⨁ _{i∈I_{1}} b_{i}).

Clearly, W_{n} is a correct 1 − 2 OT since an honest receiver A can always get bit β_{s} = b_{s} ⊕ a_{s}. Ã’s information about the other bit can be further reduced using the following simple protocol accepting B’s input bits (β_{0}, β_{1}) and the selection bit s for the honest receiver:

Protocol R-Reduce(t, W)

1. W is executed t times, with random inputs (β_{0i} , β_{1i}), i = 1..t for the sender and input s for the receiver such that β_{01} ⊕ … ⊕ β_{0t} = β_{0} and β_{11} ⊕ … ⊕ β_{1t} = β_{1}.

2. The receiver computes the XOR of all bits received, that is β_{s} = ⊕_{i=1}^{t} β_{si} .

Classically, it is straightforward to see that the receiver’s information about one-out-of-two bit decreases exponentially in t. We say that a quantum adversary Ã against R-Reduce(t, W_{n}) is promising if it runs in poly-time and the probability to complete the execution is non-negligible. Using Theorem 2, it is not difficult to show that Ã’s information about one of the transmitted bits also decreases exponentially in t whenever Ã is promising:

Theorem 3. For any promising receiver Ã in R-Reduce(t, W_{n}) and for all executions, there exists s̃ ∈ {0, 1} such that Ã’s expected bias on βs̃ is negligible in t (even given β_{s}).

A sketch of proof can be found in Appendix E. It relies upon the fact that any promising adversary must run almost all W_{n} with p̃^{ok}(n) > 1 − δ for any δ > 0. Using Theorem 2, this means that independently for each of those executions 1 ≤ i ≤ t, one bit β_{s̃i} out of (β_{0i}, β_{1i}) cannot be guessed with bias better than ε_{max} (δ) << \frac{1}{2}. In this case, the bias on βs̃ can be shown to be negligible in t similarly to the classical case.

Clearly, the sender B in R-Reduce(t, W_{n})cannot get any non-negligible amount of information about A’s selection bit when the commitments are statistically concealing. This remark together with Theorem 3 and the correctness of R-Reduce(t, W_{n}) lead to:

Corollary 1. A correct and private 1 − 2 OT can be based upon any F_{m}^{n}-binding and statistically concealing quantum string commitment scheme. The resulting OT statistically hides the selection bit and computationally hides one out of two transmitted bits.

In other words, building 1 − 2-OT upon Theorem 2 allows for an easy security proof in the computational setting. Our analysis assumes for simplicity that A and B have access to an error-free quantum channel. Nevertheless, some noise may be tolerated if we construct OT along the lines of BBCS [4] instead of CK [6].

7 Open Questions

An obvious open problem is how to build F_{m}^{n}-string commitment from computationally binding bit commitment schemes. In particular, how one can transform the computationally binding bit commitments of [9] and [7] into F_{m}^{n}–binding string commitments? This would show that QMCs and therefore OT can be based upon any one-way permutation[9] and/or upon any one-way function[7]. It is an open question whether or not Theorem 2 holds for δ(n)–non-trivial adversaries against QMC. Such an extension would show that our reduction from an adversary to QMC into one against the binding condition is optimal. It is also of interest to find attacks against weaker binding properties. In particular, is it possible to transform an adversary against QMC into one against the F –binding property where F is class of functions with range of size in o(log1/δ(n))? Our reduction is non-uniform since we did not provide an efficient way to find a good f– attack.Our result would be stronger if a uniform reduction was found. Finally, it would be very interesting to formally prove the security of the CK protocol using Theorem 2. This would result in a proof of security that, in addition to apply in the computational setting, would be based upon a completely different approach than Yao’s proof [20]. It is also an interesting problem to prove Corollary 1 in the case where the quantum channel is not error-free.

References

1. Adcock, M.,and R. Cleve, “A Quantum Goldreich-Levin Theorem with Cryptographic Applications”, In proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002),to appear, 2002, pages 323–334.

2. Bennett, C. H., and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing”, In Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, pages 175–179. IEEE, 1984.

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

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

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

6. Crépeau, C. and J. Kilian, “Achieving oblivious transfer using weakened security assumptions”, Proceedings of 29th IEEE Symposium on the Foundations of Computer Science, October 1988, pp. 42–52.

7. Crépeau, C., F. Légaré, and L. Salvail, “How to Convert the Flavor of a Quantum Bit Commitment”, Advances in Cryptology : EUROCRYPT ’01 : Proceedings, Lecture Notes in Computer Science, vol. 2045 , Springer-Verlag, 2001, pp. 60–77.

8. Damgård, I., J. Kilian, and L. Salvail, “On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions”, Advances in Cryptology : EUROCRYPT ’99 : Proceedings, Lecture Notes in Computer Science, vol. 1592, Springer-Verlag, 1999, pp. 56–73.

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

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

11. Impagliazzo, R. and S. Rudich, “Limits on Provable Consequences of One-Way Permutations”, Advances in Cryptology : CRYPTO ’88 : Proceedings, Lecture Notes in Computer Science, vol. 403, Springer-Verlag, 1989, pp. 2–7.

12. Kilian, J., “Founding cryptography on oblivious transfer”, Proceedings of the 20th ACM Symposium on Theory of Computing, 1988, pp. 20–31.

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

14. Mayers, D., “The Trouble With Quantum Bit Commitment”, available at http://xxx.lanl.gov/abs/quant-ph/9603015.

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

16. Nielsen, M.A,and I.L. Chuang, “Quantum Computation and Quantum Information”, Cambridge University Press, 2000.

17. van de Graaf, J., Towards a Formal Definition of Security for Quantum Protocols, Ph.D. thesis, Computer Science and Operational Research Department, Université de Montréal, 1997.

18. Watrous, J, “Limits on the Power of Quantum Statistical Zero-Knowledge”, Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, 2002, pp. 495–504.

19. Yao, A. C., “Theory and Applications of Trapdoor Functions”, Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982, pp. 80–91.

20. Yao, A. C., “Security of Quantum Protocols Against Coherent Measurements”, Proceedings of the 27th ACM Symposium on Theory of Computing, 1995, pp. 67–75.

A Proof of Lemma 1

First, we prove the following related claim:

Claim. Let {u⃗_{w,z} }_{w,z} be any family of vectors, indexed by w, z ∈ {0, 1}^{n}, that satisfies,

(∀s, t ∈ {0, 1}^{n}, s ≠ t)[∑_{w} ∑_{z_{1}:w⊕z_{1}=s} ∑_{z_{2}:w⊕z_{2}=t} (−1)^{w⊙(z_{1}⊕z_{2})} ⟨u⃗_{w,z_{1}} , u⃗_{w,z_{2}} ⟩ = 0]  (36)

Then,

∑_{w} ∥ ∑_{z} (−1)^{w⊙z} u⃗_{w,z} ∥^{2} = ∑_{w,z∈{0,1}^{n}} ∥u⃗_{w,z} ∥^{2}.  (37)

Proof. We carry out the calculation for (37):

∑_{w} ∥ ∑_{z} (−1)^{w⊙z} u⃗_{w,z} ∥^{2} = ∑_{w} ⟨∑_{z_{1}} (−1)^{w⊙z_{1}} u⃗_{w,z_{1}} , ∑_{z_{2}} (−1)^{w⊙z_{2}} u⃗_{w,z_{2}} ⟩

= ∑_{w,z_{1},z_{2}} (−1)^{w⊙(z_{1}⊕z_{2})} ⟨u⃗_{w,z_{1}} , u⃗_{w,z_{2}} ⟩
= ∑_{w,z} ∥u⃗_{w,z} ∥^{2} + ∑_{w,z_{1},z_{2}:z_{1} ≠z_{2}} (−1)^{w⊙(z_{1}⊕z_{2})} ⟨u⃗_{w,z_{1}} , u⃗_{w,z_{2}} ⟩.  (38)

We now re-arrange the terms in the right-hand part of (38):

∑_{w,z_{1},z_{2}:z_{1} ≠z_{2}} (−1)^{w⊙(z_{1}⊕z_{2})} ⟨u⃗_{w,z_{1}} , u⃗_{w,z_{2}} ⟩ = ∑_{w,z_{1}} ∑_{s:w⊕z_{1}=s} ∑_{z_{2}:z_{2} ≠z_{1}} ∑_{t:w⊕z_{2}=t} ⟨u⃗_{w,z_{1}} , u⃗_{w,z_{2}} ⟩
= ∑_{s,t:s≠t} ∑_{w} ∑_{z_{1}:w≠z_{1}} ∑_{z_{2}:w⊕z_{2}=t} ⟨u⃗_{w,z_{1}} , u⃗_{w,z_{2}} ⟩
= 0,  (39)

where (39) follows from condition (36). Replacing (39) in (38) concludes the proof. ⊓⊔

Proof (Lemma 1). The proof of Lemma 1 follows from the Claim after setting u⃗_{w,z} = v⃗_{w,z} if z ∉ A and u⃗_{w,z} = 0 if z ∈ A. It is easy to verify that if condition (2) is satisfied by {v⃗_{w,z}}_{w,z} then {u⃗_{w,z} }_{w,z} satisfies (36). Our result then follows from (37). ⊓⊔

B Proof of Theorem 1

Proof. We use Lemma 3 together with the fact that Ã is δ(n)–good. From Lemma 3, any δ(n)–good adversary is such that,

p̃^{ok}(n) + ∑_{θ,b} 4^{−n} |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2} = 4^{−n} ∑_{θ,b} (p̃_{(θ,b)}^{ok}(n) + |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2}) ≥ 1 + δ(n).  (40)

The sum of any row (θ, b) ∈ TÃ is given by,

∥ℚ_{(θ,b)}^{∗} Ψ̃_{θ,b}⟩∥^{2} ≥ ∥ℚ_{(θ,b)}^{∗}( |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩| Ψ_{θ,b}⟩ − \sqrt{1 − |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2}} Ψ_{θ,b}^{⊥}⟩) ∥^{2},  (41)

where Ψ_{θ,b}^{⊥}⟩ is any state orthogonal to Ψ_{θ,b}⟩. Now, notice that we can always write Ψ_{θ,b}⟩ = \sqrt{p̃_{(θ,b)}^{ok}(n)} ξ_{θ,b}⟩+

\sqrt{1 − p̃_{(θ,b)}^{ok}(n)} ξ_{θ,b}^{⊥}⟩ for ξ_{θ,b}⟩ = ℚ_{(θ,b)}^{∗} Ψ_{θ,b}⟩/\sqrt{p̃_{(θ,b)}^{ok}(n)} and ξ_{θ,b}^{⊥}⟩ = ( 1 − ℚ_{(θ,b)}^{∗}) Ψ_{θ,b}⟩/\sqrt{1 − p̃_{(θ,b)}^{ok}(n)} . We

can also write Ψ_{θ,b}^{⊥}⟩ = α_{θ,b} ξ_{θ,b}⟩+ β_{θ,b} ξ_{θ,b}^{⊥}⟩+ ζ_{θ,b} Λ_{θ,b}⟩ where Λ_{θ,b}⟩ is orthogonal to both ξ_{θ,b}⟩ and ξ_{θ,b}^{⊥}⟩and where |α_{θ,b}|^{2} + |β_{θ,b}|^{2} + |ζ_{θ,b}|^{2} = 1. Since by construction ⟨Ψ_{θ,b} Ψ_{θ,b}^{⊥}⟩ = 0, it is easy to verify that

|α_{θ,b}| ≤ \sqrt{1 − p̃_{(θ,b)}^{ok}(n)} . Using the above observations ^{1}, we rewrite (41) as,

∥ℚ_{(θ,b)}^{∗} Ψ̃_{θ,b}⟩∥^{2} ≥ \frac{1}{4} ( ∥⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩ℚ_{(θ,b)}^{∗} Ψ_{θ,b}⟩∥^{2} − ∥\sqrt{1 − |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2}} ℚ_{(θ,b)}^{∗} Ψ_{θ,b}^{⊥}⟩∥^{2}) ^{2}  (42)
≥ \frac{1}{4} ( |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩\sqrt{p̃_{(θ,b)}^{ok}(n)}|^{2} − |\sqrt{1 − |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2}} |α_{θ,b}||^{2}) ^{2}  (43)
≥ \frac{1}{4} (|⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2}p̃_{(θ,b)}^{ok}(n) − (1 − |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2})(1 − p̃_{(θ,b)}^{ok}(n))) ^{2}  (44)
≥ \frac{1}{4} (p̃_{(θ,b)}^{ok}(n) + |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2} − 1) ^{2} .  (45)

Since Ã is δ(n)–good, we use (40) to conclude that the set G = \{(θ, b)|p̃_{(θ,b)}^{ok}(n) + |⟨Ψ_{θ,b} Ψ̃_{θ,b}⟩|^{2} ≥ 1 + \frac{δ(n)}{2} \}

must satisfy #G ≥ 4^{n}δ(n)/2. Any (θ, b) ∈ G is such that (45) is at least \frac{δ(n)^{2}}{4} . The result follows easily from ∑ _{θ,b}∥ℚ_{(θ,b)}^{∗} Ψ̃_{θ,b}⟩∥^{2} ≥ ∑ _{(θ,b)∈G} ∥ℚ_{(θ,b)}^{∗} Ψ̃_{θ,b}⟩∥^{2} ≥ \frac{4^{n} δ(n)^{3}}{32} . ⊓⊔

1 and the fact that (\sqrt{a} − \sqrt{a − b})^{2} ≥ 1/4b^{2} for any 0 ≤ b ≤ a ≤ 1.

C Implementing an f-attack From the Switching Circuit

In this appendix, we briefly describe how one can use the switching circuit in order to attack the binding property of the string commitment relative to some function f ∈ F_{m}^{n}. We call such an attack an f-attack since its purpose is to try to open s ∈ f^{−1} (y) for any y ∈ {0, 1}^{m}. To make the description easier, let us consider the case n = 1 resulting in table TÃ shown at Fig. 2 (this is almost identical to Fig.1). We have

\begin{matrix}∥ℚ_{(+,0)}^{B} Ψ̃_{+,0} ⟩∥^{2} & ∥ℚ_{(×,0)}^{B} Ψ̃_{+,0} ⟩∥^{2} & ∥ℚ_{(×,1)}^{B} Ψ̃_{+,0} ⟩∥^{2} \\ ∥ℚ_{(+,1)}^{B} Ψ̃_{+,1} ⟩∥^{2} & ∥ℚ_{(×,1)}^{B} Ψ̃_{+,1} ⟩∥^{2} & ∥ℚ_{(×,0)}^{B} Ψ̃_{+,1} ⟩∥^{2} \\ ∥ℚ_{(×,0)}^{B} Ψ̃_{×,0} ⟩∥^{2} & ∥ℚ_{(+,0)}^{B} Ψ̃_{×,0} ⟩∥^{2} & ∥ℚ_{(+,1)}^{B} Ψ̃_{×,0} ⟩∥^{2} \\ ∥ℚ_{(×,1)}^{B} Ψ̃_{×,1} ⟩∥^{2} & ∥ℚ_{(+,1)}^{B} Ψ̃_{×,1} ⟩∥^{2} & ∥ℚ_{(+,0)}^{B} Ψ̃_{×,1} ⟩∥^{2} \end{matrix}

Fig. 2. Table TÃ for the case n = 1.

seen how the switching circuit allows for generating any state Ψ̃_{θ,b}⟩. Suppose now that the attacker wants to open a string commitment (in this case the string as length 2) according to function f_{1} ∈ F_{1}^{n} defines as f_{1}(θ, b) = b for θ, b ∈ {0, 1}. One way consists in generating (using the switching circuit) Ψ̃_{+,0} ⟩ in order to open f_{1}(θ, b) = 0 and Ψ̃_{+,1} ⟩ in order to open f_{1}(θ, b) = 1. According to (6), the probability to succeed in unveiling s s.t. f_{1}(s) = 0 and f_{1}(s) = 1 satisfies

p̃_{0}^{f}(n) = ∥(ℚ_{(+,0)}^{B} + ℚ_{(×,0)}^{B} ) Ψ̃_{+,0} ⟩∥^{2} and p̃_{1}^{f}(n) = ∥(ℚ_{(+,1)}^{B} + ℚ_{(×,1)}^{B} ) Ψ̃_{+,1} ⟩∥^{2}.

The quality of this f_{1}–attack is given by (2). That is, the attack succeed if p̃_{0}^{f}(n) + p̃_{1}^{f}(n) > 1 + δ for some large enough δ. Looking at Fig. 2, this particular f_{1}–attack is formed by the 2 × 2 upper left sub-array of TÃ. The quality of the attack p̃_{0}^{f}(n) + p̃_{1}^{f}(n) is simply the sum of all elements in the sub-array. The same function f_{1} can be attacked using the elements in the lower left 2 × 2 sub-array of TÃ. This means that the attacker prepare Ψ̃_{×,0} ⟩and Ψ̃_{×,1} ⟩in order to open s ∈ f_{1}^{−1} (0) and s ∈ f_{1}^{−1} (1) respectively. In this case, one gets p̃_{0}^{f}(n) = ∥(ℚ_{(×,0)}^{B} + ℚ_{(+,0)}^{B} ) Ψ̃_{×,0} ⟩∥^{2} and p̃_{1}^{f}(n) = ∥(ℚ_{(×,1)}^{B} + ℚ_{(+,1)}^{B} ) Ψ̃_{×,1} ⟩∥^{2}. There are two other ways to implement an f_{1}–attack by mixing the first two. The attacker could generate Ψ̃_{+,0} ⟩ to unveil s ∈ f_{1}^{−1} (0) and Ψ̃_{×,1} ⟩ to unveil s ∈ f_{1}^{−1} (1). Similarly, Ψ̃_{+,1} ⟩ to unveil s ∈ f_{1}^{−1} (1) and Ψ̃_{×,0} ⟩ to unveil s ∈ f_{1}^{−1} (0) can be used. This adds up to 4 possible implementations of the f_{1}–attack using the first two columns of TÃ.

Now consider function f_{2} ∈ F_{1}^{n} defines as f_{2}(θ, b) = θ. As for f_{1}–attacks, there are four f_{2}–attacks located in the two last columns of TÃ. In the first case, states Ψ̃_{+,0} ⟩ and Ψ̃_{×,0} ⟩ are generated (by the switching circuit) in order to open s ∈ f_{2}^{−1} (1) and s ∈ f_{2}^{−1} (0) respectively (using ′+′ = 0 and ′×′ = 1). We get p̃_{1}^{f}(n) = ∥(ℚ_{(×,0)}^{B} + ℚ_{(×,1)}^{B} ) Ψ̃_{+,0} ⟩∥^{2} and p̃_{0}^{f}(n) = ∥(ℚ_{(+,0)}^{B} + ℚ_{(+,1)}^{B} ) Ψ̃_{×,0} ⟩∥^{2}. The second way of attacking f_{2} is by generating states Ψ̃_{+,1} ⟩and Ψ̃_{×,1} ⟩in order to open s ∈ f_{2}^{−1} (1) and s ∈ f_{2}^{−1} (0) respectively. The other two are obtained similarly.

There is only one function left in F_{1}^{n}, that is f_{3}(θ, b) = θ ⊕ b. This one can be attacked in four different ways using the first and third columns in TÃ. In the first case, states Ψ̃_{+,0} ⟩ and Ψ̃_{+,1} ⟩ are generated in order to open s ∈ f_{3}^{−1} (0) and s ∈ f_{3}^{−1} (1). We get p̃_{0}^{f}(n) = ∥(ℚ_{(+,0)}^{B} + ℚ_{(×,1)}^{B} ) Ψ̃_{+,0} ⟩∥^{2} and p̃_{1}^{f}(n) = ∥(ℚ_{(+,1)}^{B} + ℚ_{(×,0)}^{B} ) Ψ̃_{+,1} ⟩∥^{2}. The two others can be found similarly.

Remark that any element in TÃ belongs to exactly 4 attacks and that any attack uses exactly 4 elements in TÃ. This is what we mean when we say that all attacks in F_{1}^{n} covers TÃ uniformly. The construction can easily be generalized for arbitrary n. The number of rows of TÃ uses in any f–attack (f ∈ F_{m}^{n}) is 2^{m} and the number of columns is 2^{m}3^{n−m} . That is, the number of elements in TÃ involved in such an f–attack is 4^{m}3^{n−m} . As we shall see in Lemma 4, the covering remains uniform for all values of n.

D Proof of Lemma 4

Lemma 4 follows from the combinatorial lemma 5 below. To make the statement of this combinatorial lemma more succinct we first set the stage for it.

Let T be a 4^{n} lines by 3^{n} columns array. The lines are indexed by the 4^{n} strings (θ, b) ∈ {0, 1}^{n} ×{0, 1}^{n}. The columns are indexed by the 3^{n} strings (τ, β) ∈ {0, 1}^{n} × {0, 1}^{n} such that β ⪯ τ.

We now consider sub-arrays of T. Each sub-array will be composed of cells lying at the intersections of 2^{m} lines of T and 3^{n−m} 2^{m} columns of T. Any choice of the following 3n parameters will define a unique sub-array and different choices of parameters will define different sub-arrays:

r_{1}, r_{2}, …, r_{n} ∈ {0, 1, 2, 3},  (46)
u_{1}, u_{2}, …, u_{n} ∈ {0, 1},  (47)
v_{1}, v_{2}, …, v_{n} ∈ {0, 1}  (48)

subject to the condition

#{j : r_{j} ≠ 0} = m.  (49)

Accordingly, there will be C(m, n)3^{m}4^{n} different sub-arrays.

Let us fix a choice for r_{j} ∈ {0, 1, 2, 3}, u_{j}, v_{j} ∈ {0, 1} for all j ∈ {1, …, n} satisfying (49). We now describe the sub-array defined by that choice. The column (τ, β) is part of the sub-array if and only if:

r_{j} = 0 ⟹ (τ_{j}, β_{j}) ∈ {(0, 0), (1, 0), (1, 1)}  i.e.: β_{j} ⪯ τ_{j},  (50)
r_{j} = 1 ⟹ (τ_{j}, β_{j}) ∈ {(1, 0), (1, 1)}  i.e.: τ_{j} = 1,  (51)
r_{j} = 2 ⟹ (τ_{j}, β_{j}) ∈ {(0, 0), (1, 0)}  i.e.: β_{j} = 0,  (52)
r_{j} = 3 ⟹ (τ_{j}, β_{j}) ∈ {(0, 0), (1, 1)}  i.e.: β_{j} = τ_{j}.  (53)

The line (θ, b) is part of the sub-array if and only if:

r_{j} = 0 ⟹ (θ_{j}, b_{j}) ∈ {(u_{j}, v_{j})},  (54)
r_{j} = 1 ⟹ (θ_{j}, b_{j}) ∈ {(0, u_{j}), (1, v_{j})},  (55)
r_{j} = 2 ⟹ (θ_{j}, b_{j}) ∈ {(u_{j}, 0), (v_{j}, 1)},  (56)
r_{j} = 3 ⟹ (θ_{j}, b_{j}) ∈ {(u_{j}, u_{j}), (v_{j}, 1 − v_{j})}.  (57)

One can easily verify that the lines (50) to (57) define a 2^{m} × 3^{n−m} 2^{m} sub-array, thus containing 3^{n−m} 4^{m} cells, and that different choices of the parameters (46) to (48) will lead to different sub-arrays.

We can now state and prove the combinatorial lemma:

Lemma 5. Every cell (θ, b, τ, β) of T belongs to exactly C(m, n)4^{m} sub-arrays.

Proof. Let us fix j ∈ {1, …, n}. Figure 3 shows the possible values for (r_{j}, u_{j}, v_{j}) given the value of (θ_{j}, b_{j}, τ_{j}, β_{j}). One can verify that, for all j, any 4-tuple (θ_{j}, b_{j}, τ_{j}, β_{j}) allows exactly 1 triplet (r_{j}, u_{j}, v_{j}) if

Fig. 3. Eligible triplets (r_{j} , u_{j} , v_{j}) given (θ_{j} , b_{j} , τ_{j} , β_{j})

r_{j} = 0, and exactly 4 if r_{j} ≠ 0. From that follows the statement of this combinatorial lemma. ⊓⊔

E Sketch of Proof for Theorem 3

Protocol W_{n}, which is almost identical to a QMC, is also a weak form of 1 − 2-OT. Theorem 2 tells us that any efficient adversary Ã against W_{n} must satisfy:

p̃^{ok}(n) + (2ε̃(n))^{2} ≤ 1 + 1/poly(n)  (58)

for some polynomial poly(n) where p̃^{ok}(n) is the probability to succeed in challenge c = 0 and ε̃(n) is the maximum bias on [b] = b_{0} ⊕ b_{1} that Ã can extract in challenge c = 1.

The only difference between W_{n} and a QMC (as far as p̃^{ok}(n) and ε̃(n) are concerned) is that in W_{n}, QMCs are made until challenge c = 1 has been reached. Let p̃_{abort,W_{n}} be the probability for B to abort the execution of W_{n}. Notice that there is no reason for Ã to change p̃^{ok}(n) during the same execution of W_{n} since the challenges are independent and random. We have,

p̃_{abort,W_{n}} = ∑_{j=1}^{∞} 2^{−j} (p̃^{ok}(n))^{j−1} (1 − p̃^{ok}(n)) > \frac{1 − p̃^{ok}(n)}{2} ⇒ p̃^{ok}(n) > 1 − 2p̃_{abort,W_{n}}.  (59)

Let I_{n} = {(I_{0}, I_{1})|I_{0} ∪ I_{1} = {1, …, n}, I_{0} ∩ I_{1} = ∅} be the set of possible announcements for Ã in W_{n}. Let I = (I_{0}, I_{1}) ∈ I_{n} be the set of positions announced by Ã’s during an execution of W_{n}. We define f_{I}(b) as the 2-bit output function:

f_{I}(b) ≡ (⨁_{i∈I_{0}} b_{i}, ⨁_{i∈I_{1}} b_{i}).

For s ∈ {0, 1} and b ∈ {0, 1}^{n}, let h_{I}(b, s) ≡ f_{I}(b)_{[s]} where f_{I}(b)_{[s]} denotes the s-th output bit of f_{I}(b). Let QPoly(n) and QPoly(n,t) be the classes of families of polynomial-size quantum circuits in one and two variables respectively having one-bit output. Let C_{δ} be the non-uniform class of all families of polynomial size circuits allowing to run W_{n} with success probability at least 1 − δ. That is, any family {C_{n}}_{n>0} ∈ C_{δ} can be used to define the committing phase of an adversary Ã = {(C_{n}, ·)}_{n>0} against W_{n} where C_{n} allows for p̃_{abort,W_{n}} ≤ δ given n is large enough. For simplicity, we abuse the notation by writing the output state of the committing phase on b⟩_{θ} as C_{n} b⟩_{θ} although formally, C_{n} is the circuit obtained by combining Ã’s and B’s interactive circuits. Let G_{n} be a quantum circuit with a one-bit output register so G_{n} · (C_{n} b⟩_{θ}) defines a probability distribution over the possible outcomes for the measurement in the computational basis of G_{n}’s output register. When we write out {G_{n} · (C_{n} b⟩_{θ}) ⊗ θ⟩} we are not only designating the value of G_{n}’s output register but any classical mapping from the output into {0, 1}. Using this convention, Pr(h_{I}(b, s) ≠ out \{G_{n} · (C_{n} b⟩_{θ}) ⊗ θ⟩\}) ≥ \frac{1}{2} − ϵ, means that any classical mapping from the value of the output register to \{0, 1\} has expected probability of error at least \frac{1}{2} − ϵ in guessing the value of h_{I}(b, s).

Using (59), we get that Ã also defines an adversary against QMC with p̃^{ok}(n) ≥ 1 − 2δ. From (58), we conclude that

ε̃(n) ≤ \frac{\sqrt{2δ + \frac{1}{poly(n)}}}{2}  (60)

given the output of any family of poly-size quantum circuits {G_{n}}_{n>0} ∈ QPoly(n). Remember that ε̃(n) is the maximum expected bias on h_{I}(b, 0) ⊕ h_{I}(b, 1) for any announcement I ∈ I_{n}. The following lemma follows easily from Theorem 2:

Lemma 6.

(∀{C_{n}}_{n>0} ∈ C_{δ})(∀I ∈ I_{n})(∃s ∈ {0, 1})(∀{G_{n}}_{n>0} ∈ QPoly(n) )(∀n > n_{0})

[Pr(h_{I}(b, s) ≠ out \{G_{n} · (C_{n} b⟩_{θ}) ⊗ θ⟩\}) ≥ \frac{1 − 2ε̃(n)}{10} ] , (61)

where the probability is taken over θ ∈_{R} {+, ×}^{n} and b ∈_{R} {0, 1}^{n} and where ε̃(n) is the function of δ and n defined in (60).

The proof of Lemma 6 is easy and omitted due to space limitations. It proceeds by contradiction showing that if both bits h_{I}(b, 0) and h_{I}(b, 1) can be guessed respectively by G_{n}^{0} and G_{n}^{1} with probability larger than \frac{1−2ε̃(n)}{10} then Ã could attack a QMC with success probability p̃^{ok}(n) ≥ 1 − 2δ and expected bias larger than \sqrt{2δ + 1/poly(n)} /2 contradicting (58).

Let p̃_{abort}(ℓ) be the probability that B aborts the execution no later than during the ℓ–th call to W_{n} in R-Reduce. Let p̃_{stop}(ℓ + 1) be the probability that given the first ℓ calls to W_{n} were successful, B aborts during the ℓ + 1-th execution of W_{n}. We have,

p̃_{abort}(1) = p̃_{abort,W_{n}} and  (62)
p̃_{abort}(ℓ + 1) = p̃_{abort}(ℓ)+ (1 − p̃_{abort}(ℓ))p̃_{stop}(ℓ + 1).  (63)

In order for Ã’s success probability 1 − p̃_{abort}(t) to be non-negligible in t, p̃_{stop}(ℓ) must be small for most executions ℓ ∈ [1 …t]. Let δ > 0 and α > 0 be two arbitrary constants. Assuming p̃_{stop}(ℓ) > δ for all ℓ ∈ L with #L ≥ αt then p̃_{abort}(t) ≥ 1 − (1 − δ)^{αt}. In other words, if p̃_{stop}(ℓ) > δ for a constant fraction of the t executions then 1 − p̃_{abort}(t) is negligible in t. In general, an adversary Ã against R-Reduce(t, W_{n}) is modeled by a family of quantum circuits Ã = {(C_{n,t}, G_{n,t}^{0}, G_{n,t}^{1})}_{n,t>0} where C_{n} runs the committing phase and circuits G_{n}^{0} and G_{n}^{1} extract information about b_{0} and b_{1} respectively. Promising adversaries in R-Reduce(t, W_{n}) are defined as follows:

Definition 3. A polynomial size adversary Ã = {(C_{n,t}, G_{n,t}^{0}, G_{n,t}^{1})}_{n,t>0} against R-Reduce(t, W_{n}) is promising if p̃_{abort}(t) ≤ 1 − \frac{1}{p(t)} for some p(t) ∈ poly(t).

We now consider the limitations implied by (61) to any adversary Ã against R-Reduce(t, W_{n}). Let b⟩_{θ} = ⊗_{i=1}^{t} b^{(i)}⟩_{θ^{(i)}} be the random n · t BB84 qubits picked and sent by B. The following lemma links promising adversaries against R-Reduce(t, W_{n}) to Lemma 6. It tells us that if Ã is promising then there exists a large subset L of all executions of W_{n} in R-Reduce(t, W_{n}) for which independently of each other, predicates h_{I}(b^{ℓ}, s), ℓ ∈ L cannot be guessed with arbitrary precision given the output of any polynomial size circuit.

Lemma 7. Assume the security parameters n and t in R-Reduce(t, W_{n})are polynomially related. Then,

(∀δ > 0)(∀γ > 0)(∀ promising Ã = {(C_{n,t}, ·)}_{n,t>0} )(∃L ⊆ {1, …, t} : #L ≥ (1 − γ)t)(∀ℓ ∈ L)
(∀I ∈ I_{n})(∃s ∈ {0, 1})(∀{G_{n,t}}_{n,t>0} ∈ QPoly(n,t))

[Pr(h_{I}(b^{(ℓ)}, s) ≠ out \{G_{n,t} (C_{n,t} b⟩_{θ}) ⊗ θ⟩\} |\{(b^{(j)}, θ^{(j)})\}_{j≠ℓ} ) ≥ \frac{1 − \sqrt{2δ + \frac{1}{poly(n)}}}{10} ]

(64)

where the probability is computed over b = b^{(1)}, …, b^{(t)}, and θ = θ^{(1)}, …, θ^{(t)} for b^{(i)} ∈_{R} {0, 1}^{n} and θ^{(i)} ∈_{R} {0, 1}^{n} for all i ∈ {1, …, t}.

The proof can easily be obtained using Lemma 6.From Lemma 7, we would like to conclude that given any announcement I⃗ = (I^{(0)}, I^{(1)}, …, I^{(t)}) during R-Reduce(t, W_{n}), the amplification function

gI⃗(b^{(1)}, …, b^{(t)}, s) ≡ ⨁_{i=1}^{t} h_{I^{(i)}} (b^{(i)}, s) ∈ {0, 1}  (65)

is such that for s̃ ∈ {0, 1}, the value gI⃗(b^{(1)}, …, b^{(t)}, s̃) cannot be guessed with bias non-negligible in t. Next theorem follows from Lemma 7 and is equivalent to Theorem 3:

Theorem 4. Let n and t be polynomially related security parameters in R-Reduce(t, W_{n}). Then,

(∀δ > 0)(∀γ > 0)(∀ promising Ã = {(C_{n,t}, ·)}_{n,t>0} )(∀I⃗ ∈ I_{n}^{t})(∃s ∈ {0, 1})

(∀\{G_{n,t}\}_{n,t>0} ∈ QPoly(n,t)) [Pr(gI⃗(b^{(1)}, …, b^{(t)}, s) ≠ out \{G_{n,t} (C_{n,t} b⟩_{θ}) ⊗ θ⟩\} ) ≥ \frac{1}{2} − 2^{−αt} ] ,

for α = \frac{(1−γ)}{2} log \frac{5}{4+\sqrt{δ}} and where the probability is computed over b = b^{(1)}, …, b^{(t)}, and θ = θ^{(1)}, …, θ^{(t)}

for b^{(i)} ∈_{R} {0, 1}^{n} and θ^{(i)} ∈_{R} {0, 1}^{n} for all i ∈ {1, …, t}.