1 Introduction↩︎

Since the early stages of quantum cryptography, quantum protocols that achieve information-theoretical security (i.e., security against unbounded adversaries) have been known for primitives that are impossible in the classical setting [1]. However, it was soon realized that even quantumly, a very limited family of cryptographic primitives can achieve such level of security [2], [3], and therefore, the use of computational assumptions is necessary to reach quantum advantage.

Multi-party computation (MPC) is a very versatile primitive that plays a central role in classical cryptography. In MPC, many parties want to collectively compute a function that depends on their private inputs, while maintaining the inputs secret (even if many of these parties are malicious and deviate from the original protocol). This functionality can be constructed from another primitive: oblivious transfer (OT) [4]. However, it is not expected that OT (and thus MPC) can be constructed only from one-way functions (OWFs)¹².

On the other hand, [6], [7] showed that OT can be built from OWFs and quantum resources. More precisely, [6], [7] showed how to build equivocal and extractable commitment schemes, which were known to be sufficient to build quantum protocols for OT  [4] and MPC [8], [9] ³.

One important feature of [6], [7] is that the quantum resources required for such protocols are exactly the same as the ones used in some quantum key distribution (QKD) protocols: they only need to prepare, communicate, and measure one-qubit states in conjugate bases. Given the huge progress in the implementation of QKD in very different setups [12]–[14] [15], it would be expected that one could easily implement such quantum protocols with current technology.

Unfortunately, this is not the case. While the protocols proposed by  [6], [7] are important to theoretically understand the power of quantum resources, their building blocks put serious barriers in their experimental implementation. More concretely, they pose the following difficulties:

• Fragility against errors. The protocols proposed by [6] and [7] do not tolerate experimental errors such as bit flips during the state distribution steps.

• Practical hash functions and zero knowledge proofs. Zero knowledge proofs used in [6] do not make black-box use of OWFs, and the practical implementation of the protocol would require the arithmetical description of the inner functioning of the one-way functions. It is currently unclear how to achieve such descriptions for widespread heuristic implementations of post-quantum OWFs like the secure hash standard (SHA), making their integration in the [6] scheme non-trivial.

• Inefficiency. The iterative structure of the protocol proposed by [7] allows the protocol to make a black-box use of the underlying components but requires a very large quantity of quantum states, which prevents it from being practically implementable. For example, one run of that protocol requires an order of \(10^{13}\) BB84 states [1], which are provided by days of transmission given a state-of-the-art discrete-variable QKD setup.

The main contribution of this work is to provide a noise-tolerant protocol for OT, based on the structure from [7], while avoiding some of its bottlenecks and while making it efficiently implementable. In particular, with this new protocol, we expect that around \(10^{7}\) BB84 states would be sufficient instead of \(10^{13}\), improving the transmission time to the order of seconds. Moreover, we notice that with this amount of quantum resources, we can distill more than one OT at once, which will be crucial in future uses of this protocol to implement MPC.

1.1 Background and our results↩︎

As previously mentioned, the goal of [6], [7] is to achieve a quantum protocol for oblivious transfer, since it can be used to construct MPC in a generic way [8]. Oblivious transfer is a cryptographic primitive where Alice chooses two messages, \(m_0\) and \(m_1\), Bob chooses a bit \(b \in \{0,1\}\), and Bob learns \(m_b\) (notice that Bob should not learn \(m_{\bar{b}}\) and Alice should not learn \(b\)).

In the quantum protocol for OT proposed in [16], [17], Alice sends BB84 states to Bob. The encoded states are \(\left(\left |x^{OT}_i \right \rangle_{\theta^{OT}_i}\right)_{i \in [2\lambda_{OT}]}\), where \(x^{OT}_i\in\{0,1\}\) is the value of the bit, \(\theta^{OT}_i \in \{+, \times\}\) is the choice of encoding bases and \(\lambda_{OT}\) is a security parameter. Bob chooses measurement bases \(\hat{\theta}^{OT}_i \in\{+,\times\}\) and obtains measurement results \(\hat{x}^{OT}_i\in\{0,1\}\). Since we cannot guarantee that a malicious Bob will follow the protocol (in particular, that he keeps these qubits in a quantum memory instead of measuring them), Alice and Bob perform a sub-protocol that will give guarantees to Alice that Bob did measure the quantum state. However, this sub-protocol comes with a cost, since it adds the need for bit commitment, and requires the added cost of cryptographic assumptions. More concretely, to ensure Bob’s measurement, Bob commits to the measurement bases that he chose and the outcomes resulting from the measurement. Alice can then choose a subset of these pairs of measurements/outcomes, and she asks Bob to open the corresponding commitments. Then, she can check if the outcomes are consistent with the BB84 states that she sent. If they are, it can be shown that there are strong guarantees that Bob measured (most of) the qubits sent by Alice [18]. The bit commitment sub-protocol is finished when Alice sends the bases of her original BB84 states. Bob then divides his indices into two different subsets \(I_b=\{i:\theta^{OT}_i=\hat{\theta}^{OT}_i\}\) and \(I_{\bar{b}}=\{i:\theta^{OT}_i\neq\hat{\theta}^{OT}_i\}\), which depend on the bit choice bit \(b\). Bob sends the two sets \(I_0\) and \(I_1\) to Alice who can encode the messages \(m_0\) and \(m_1\) using \(\mathbf{x}_0^{OT}=\{x^{OT}_i: i\in I_0\}\) and \(\mathbf{x}_1^{OT}=\{x^{OT}_i: i\in I_1\}\) as encrypting keys. Bob receives the encoded messages and decodes \(m_b\).

The subtleties here are the properties needed in the commitments to prove that the protocol is secure. In standard bit commitment schemes, there are two properties of interest: hiding, meaning that the receiver cannot learn the committed message before the opening, and binding, meaning that after committing, there is only one value that can be opened by the committer. However, these properties alone do not allow us to prove the security of the quantum OT protocol in the simulation-based setting (which is needed to use this building block in MPC protocols). To prove the simulation-security of the QOT protocol, a strengthening of these properties is needed, namely:

Equivocality: A bit commitment protocol is called equivocal if there is a simulator (also called equivocator) that can perform a “dummy commitment” that can be opened to any desired value. Moreover, such a dummy commitment cannot be distinguished from the real ones by any polynomial-time distinguisher. ⁴

Extractability: A bit commitment protocol is called extractable if there is a simulator (also called extractor) that is able to extract the commitment message in the commitment phase of the protocol. ⁵

In [4], they show that equivocation and extraction of the quantum bit commitment are sufficient properties to prove the simulation-security of the QOT protocols of [16], [17]. Moreover, the technical contribution of [6], [7] was to show a quantum protocol bit commitment that is equivocal and extractable. The main observation that allowed us to improve the parameters of such a protocol is that full extraction is not needed in order to prove the security of the QOT protocol. Instead, we show that relaxed extractability is sufficient, and we show a more efficient bit commitment protocol that achieves this property (and is still equivocal). We describe the details of our contributions in the next section.

1.2 Technical overview↩︎

We explain now the approach of [7] to achieve extractable and equivocal commitment, and discuss how we modify it. In their result, they propose two compilers: in the first one, they propose an equivocal commitment scheme based on any bit commitment scheme that satisfies only “vanilla” binding and hiding. Moreover, the resulting commitment is extractable if the original commitment was also extractable. In the second commitment, they show how to turn an equivocal commitment into an extractable one (while losing equivocality). We notice that in this second step, even if the original bit commitment scheme is classical, the resulting one would be a quantum protocol. They achieve the equivocal and extractable bit commitment scheme by starting with a standard bit commitment scheme, and then applying the equivocal compiler, followed by the extractable compiler, and then finally the equivocal compiler again.

In the equivocal compiler, EqCommitment, the committer generates \(\lambda\) pairs of random bits \((u_i^0,u_i^1)\). For each \(i\), the committer and the receiver proceed as follows, sequentially: the committer commits, using the base bit commitment scheme, to each one of them twice leading to the commitments \((c_{i,0}^0,c_{i,1}^0,c_{i,0}^1,c_{i,1}^1)\). Then, the receiver chooses a random bit \(\gamma_i\) and the committer opens \(c_{i,0}^{\gamma_i},c_{i,1}^{\gamma_i}\). The verifier aborts if such pairs of commitments open to different values. At the end of this interaction, the committer sends \(e_i=b \oplus u^{\bar{\gamma}_i}\) for every \(i\). In the opening phase, the committer chooses bits \(d_i\) and opens \(c_{i,d_i}^{\bar{\gamma}_i}\) and the receiver accepts if all the \(e_i\)’s decommit to the same value \(b\).

In the equivocality proof, the equivocator guesses \(\gamma_i\), and then commits to two different values on \(c_{i,0}^{\bar{\gamma}_i},c_{i,1}^{\bar{\gamma}_i}\). At each step, the equivocator uses Watrous’ rewinding [19] to amplify the success probability to \(1-negl(\lambda)\). In this case, in the opening phase, the equivocator can choose which \(c_{i,d_i}^{\bar{\gamma}_i}\) to open, so that the decommitment will be the desired bit. The binding/equivocal property follows from the fact that, if many of the checks on \(\gamma_i\)’s passed, then most of the pairs \(c_{i,0}^{\bar{\gamma}_i},c_{i,1}^{\bar{\gamma}_i}\) commit to the same value, and therefore the decommitted bit is fixed.

The modification that we propose to the equivocal compiler is simple but impactful. Instead of repeating the commitment/checking \(\lambda\) times sequentially, our protocol only performs it once. The proof of equivocality follows exactly as in [7], but the binding property completely breaks. In particular, a malicious committer can guess \(\gamma\), and commit to two different values of \(c_{0}^{\bar{\gamma}},c_{1}^{\bar{\gamma}}\), and therefore, with probability \(\frac{1}{2}\), the receiver’s checks pass and the committer can open to any value of their choice. However, we show that this protocol satisfies what we call relaxed binding. We defer the formal definition of this property to 3.1, but, intuitively, it says that, if we commit to \(m\) bits using our bit commitment scheme and all of the tests pass, then, with overwhelming probability, only a logarithmic small fraction of these bits are non-binding. As we discuss next, we show that this property is sufficient in the extractable compiler. Moreover, since this sub-protocol is repeated many times in later parts of the protocol, reducing its complexity has a big impact in the runtime of the classical post-processing of our final protocol.

We switch gears now to the extractable compiler of [7]. This compiler is heavily inspired by the structure of the quantum OT protocol of [16], [17]. In this compiler, the committer generates \(2\lambda\) BB84 states and sends them to the receiver. As in the quantum OT protocol, the receiver equivocally commits to measurement bases and outcomes, then the committer challenges the receiver to open a subset of size \(\lambda\) of such commitments and verify the consistency of the opened values with the committer’s original encoded states. If such a test passes, the committer divides the remaining encoded states into \(\sqrt{\lambda}\) strings \(x_1,...,x_{\sqrt\lambda}\) of size \(\sqrt{\lambda}\), and using \(\sqrt{\lambda}\) hashes from a \(2\)-universal hash function \(h_1,...,h_{\sqrt\lambda}\), the committer sends \(\hat{h}_i = h_i(x_i) \oplus b\)

The opening in [7] is followed by the committer sending \(x_1,...,x_{\sqrt\lambda},b\), which is followed by the receiver checking if these values are consistent with their measurement outcomes and if \(\hat{h}_i = h_i(x_i) \oplus b\).

The hiding property of the commitment comes from the properties of \(2\)-universal hash functions along with the entropy of \(x_i\) from the receiver’s perspective due to the uncertainty relations of measurement outcomes that we can achieve with the binding property of the commitment scheme. We notice that the relaxed binding of the base commitment instead of a full binding preserves the overall proof of hiding with minimal losses.

The extraction property is (roughly) proved as follows. Using the equivocality of the base bit commitment scheme, the extractor can delay the measurement until the committer reveals which subset of positions they will check. At this point, the extractor measures those positions on random bases, and then equivocates the opening to these values. Later in the protocol, whenever the committer sends the bases, the extractor is able to measure all of the qubits in the correct bases and find the (purported) values of \(x_1,...,x_{\sqrt\lambda}\), and then extract the committed values from \(\hat{h}_i\).

The first problem of this compiler is that it assumes that all of the parties have access to perfect (noiseless) devices. In particular, noise will make it impossible for the extractor to extract the correct values. A second problem appears while splitting the string in \(\sqrt{\lambda}\) blocks, since it causes a quadratic loss in the security of the protocol. Finally, we notice that, in [7], this protocol is repeated multiple times: firstly in the equivocal compiler, and then to commit to many values in the final quantum OT protocol. This causes the huge overhead needed in the total number of qubits required for their protocol.

In our work, we solve all of these problems at once. First, in order to enable extraction even in the presence of noise, we send the syndrome of the encoded values according to a linear error correcting code, and, as in the QKD setting, this allows the extractor to correct the faulty positions. Second, we replace the use of hashes so that, with the same number of BB84 states, we can commit to many qubits with equivocality and some extraction properties. Our proposed Equivocal and Relaxed-Extractable commitment scheme (ERE-Commitment), can be divided into two main different subroutines: the generation of a set of random seeds that are relaxed-extractable and the use of these seeds as “keys” in a set of equivocal commitments. We show that the keys of almost all the equivocal commitments are extractable, which is sufficient for a simulator to open most of the messages. We notice that the structure of our scheme is conceptually different from the one proposed by [7], allowing the drastic reductions of the needed quantum resources.

The challenge is to generate random seeds that are relaxed-extractable. To do so, we make use of quantum resources again. Given the distribution of BB84 states, the sender can distill random seeds from the encoded states. By using an equivocal commitment subroutine, these seeds cannot be distilled by a receiver that is forced to measure. However, an efficient simulator is able to extract them.

More concretely, we split the encoded string \(\boldsymbol{x}_{EX}\) into \(\left( \tilde{\boldsymbol{x}}^j\right)_{j \in [2k]}\) subsets of size \(m\). Using privacy amplification techniques found in QKD [20], we distill uniformly random strings \(\boldsymbol{s}^j\) which are used as seeds of pseudo-random generators, i.e., we expand them to the pseudo-random strings \(\left(\boldsymbol{p}^j\right)_{j \in [2k]}\). Each \(\boldsymbol{p}^j\) represents a concatenation of \(2w\) values \(\boldsymbol{p}^j_i\) that are used for their randomness as needed in statistically binding bit commitment schemes used for equivocation.

ERE-Commitment allows us to achieve the independence of seeds required to open the different commitments, while avoiding the modular composition proposed by [7]. The reason is that we consider that the \(2k\) seed families \((\boldsymbol{p}^j)_{j \in [2k]}\) are grouped in \(k\) pairs \((\boldsymbol{p}^1, \boldsymbol{p}^2), ...(\boldsymbol{p}^{2k-1},\boldsymbol{p}^{2k})\), so each of the \(r \in [k]\) pairs can be used for parallel commitment of \(w\) values. For the \(r\)-th pair, each of the \(q \in [w]\) instances makes use of two seeds \(\boldsymbol{p}^j_i\) from each family of the pair, in such a way that the final set of seeds for the \(q\)-th EqCommitment instance of the \(r\)-th family pair is \(\left(\left(\boldsymbol{p}_{i_{q,0}}^{j^{r,0}},\boldsymbol{p}_{i_{q,1}}^{j^{r,0}}, \boldsymbol{p}_{i_{q,0}}^{j^{r,1}},\boldsymbol{p}_{i_{q,1}}^{j^{r,1}} \right)_{q \in [w]} \right)_{r \in [k]}\). Afterwards, Bob sends Alice the corresponding \(x^{EX}_i\) and \(\theta^{EX}_i\), then Alice checks that \(x^{EX}_i = \hat{x}^{EX}_i\) whenever \(\theta^{EX}_i = \hat{\theta}^{EX}_i\) and that the \(\boldsymbol{p}^j\) were generated in an honest way. This ensures that the seeds \(\boldsymbol{p}_i^j\) originate from the proper \(\mathbf{x}^{EX}\) with probability \(1-negl(k)\). Bob can then commit to \(\left((\hat{x}_i^{OT},\hat{\theta}_i^{OT})\right)_{i \in [2\lambda_{OT}]}\) using \(\boldsymbol{p}_i^j\).

To prove that ERE-Commitment is relaxed extractable, we make use of equivocality and quantum rewinding. A simulator commits to dummy values instead of \(\left((\hat{x}^{EX}_i,\hat{\theta}^{EX}_i)\right)_{i\in [4 \lambda_{EX}]}\). After learning the challenged subset \(E\), the simulator measures the corresponding states \(\left(\left |x^{EX}_i \right \rangle_{\theta^{EX}_i}\right)_{i \in E}\), and, applying Watrous’ quantum rewinding, opens to the measured values. Once the simulator has passed the decommitment check, Bob announces the bases. The simulator will then measure \(\left(\left |x^{EX}_i \right \rangle_{\theta^{EX}_i}\right)_{i \in \bar{E}}\) in the correct bases obtaining \(\mathbf{x}^{EX}\). It is in this step in which the simulator has to make use of the error correction code for obtaining the correct seeds \((\boldsymbol{p}^j)_{j \in [2k]}\) given the syndromes \((Synd_j)_{j \in [2k]}\). The simulator will obtain the seeds of the equivocal commitments, and thus extracts \(\left|\bar{T}\right|-\omega(\log^2(k))\) of the non-challenged committed values \(\left((\hat{x}_i^{OT},\hat{\theta}_i^{OT})\right)_{i \in \bar{T}}\) with probability \(1-negl(k)\).

Despite these changes, we prove that the OT functionality remains simulation-based secure given access to an equivocal and \(\chi\)-relaxed extractable bit commitment. With a practical implementation as our main goal, we explicitly take into account possible experimental errors and their correction, and we derive analytical expressions based on [18] that facilitate benchmarking of the required quantum resources. The resulting QOT protocol is given in Protocol [protocol:QOT].

Moreover, we propose a method to distill a number \(n_{\mathrm{OT}}\) of QOT keys from a single run of the protocol, which is particularly useful when a large number of BB84 states is employed to achieve a smaller sampling error (and hence a tighter \(\Delta\)-security bound).

1.3 Related works↩︎

We compare and benchmark our proposed protocol with other composably secure QOT protocols based on one-way functions that have been proposed in the literature. In [21], the authors also focus on reducing the round complexity, but they work in the Random Oracle Model (ROM). In this setting, equivocality and extractability of commitments can be obtained from the random oracle, so no additional quantum resources are needed for the commitment layer itself. The cost of the quantum communication in [21] comes entirely from the OT core, which is structurally similar to CK88. Under our common benchmarking assumptions (target trace distance, security level, and an upper bound on the number of RO queries), the resulting number of BB84 states in their protocols is of the same order of magnitude as in our construction, as shown in 1 and detailed in 7. However, these estimates for [21] do not take into account practical errors such as bit-flips, photon loss, or multi-photon events, whereas our benchmark explicitly includes such imperfections.

It is important to stress that the comparison in 1 concerns only the quantum communication cost (number of BB84 states) under a common concrete security target. In particular, we do not claim to match the classical efficiency of ROM-based commitments. Conceptually, our assumption is strictly weaker: our protocol is proved secure in the plain model under the minimal assumption of post-quantum one-way functions, without relying on a random oracle or heuristic instantiations thereof. In this sense, our construction achieves comparable BB84 cost while working under strictly milder computational assumptions than [21].

8pt

On the other hand, the number of BB84 states necessary to instantiate [7] has been obtained by adapting our security bounds to their protocol structure. A detailed explanation of how all entries in 1 are computed is provided in 7.

Further proposals, such as [22], consider relaxed version of simulations, where the run-time of the simulator depends polynomially on the desired security level. In our work, we can achieve negligible distinguishing probability with polynomial-time simulators.

1.4 Paper Organisation↩︎

Section 1 contains important background information and the technical overview of the paper. Section 2 contains preliminary information such as a description of the notation used throughout the paper, and useful definitions. Section 3 contains the proposed equivocal commitment. Section 4 presents the equivocal and relaxed-extractable commitment. Section 5 contains the proof that the QOT protocol we propose is simulation-based secure given relaxed-extractable and equivocal bit commitment.

2 Preliminaries and Definitions↩︎

2.1 Notation and acronyms↩︎

Throughout this paper, we represent classical random variables with capital letters (e.g., \(X\)) while the value they take is represented by lower case letters (e.g., \(x\)). Bold characters (e.g., \(\mathbf{x}\)) are strings of values. Quantum states are represented as density matrices \(\rho \in \mathcal{B}_1(\mathcal{H})\). The probability of distinguishing two density matrices is upper-bounded by \(\frac{1}{2}(1+\Delta(\rho^{1},\rho^{2}))\), where \(\Delta(\rho^{1},\rho^{2})\) is the trace distance. When a negligible function \(\mu(\lambda)\) exists such that \(\Delta(\rho^{1},\rho^{2}) \leq \mu(\lambda)\), \(\rho^{1}\) and \(\rho^{2}\) are said to be statistically close. \(\mu(\lambda)\) is negligible if, for every fixed \(c\), \(\mu(\lambda) = o(1/\lambda^c)\), where \(\lambda\) is the security parameter. Throughout the paper, the security parameters of the different steps are written as \(\lambda_{OT}\) and \(\lambda_{EX}\), for example. When using the symbol \(\perp\), it means to abort.

In the Landau notation, given two functions \(f(n)\) and \(g(n)\), we write \(f(n)=o(g(n))\) if \(\lim_{n\rightarrow \infty} f(n)/g(n) = 0\). In the same way, \(f(n)=\omega(g(n))\) if \(\lim_{n\rightarrow \infty} f(n)/g(n) = \infty\) and \(f(n)=O(g(n))\) if there exists a constant \(C>0\) such that \(\lim_{n\rightarrow \infty} f(n)/g(n) \leq C\). Lastly, \(f(n)=\Omega(g(n))\) if there exists a constant \(C>0\) such that \(\lim_{n\rightarrow \infty} f(n)/g(n) \geq C\) and \(f(n)=\Theta(g(n))\) if both \(f(n)=O(g(n))\) and \(f(n)=\Omega(g(n))\).

We define a classical-quantum hybrid state as a bipartite state of the subsystems \(XE\) such that \(\rho_{XE} = \sum_{x \in \mathcal{X}} p_x(x) \left |x \right \rangle\left \langle x \right| \otimes \sigma_E^x\), where subsystem \(X\) is classical. \(\mathcal{X}\) is a finite set with \(\left|\mathcal{X}\right| = dim(\mathcal{H}_X)\), \(p_x: \mathcal{X}\rightarrow [0,1]\) is a probability distribution and \(\{\left |x \right \rangle\}_{x \in \mathcal{X}}\) an orthonormal basis of \(\mathcal{H}_x\). \(\sigma_E^x \in \mathcal{H}_E\) is the density matrix correlated with the value \(x \in \mathcal{X}\). When we treat a collection of qubits as a single unit, we refer to it as a quantum register.

A function \(h : \mathcal{X}\times \mathcal{S}\rightarrow \mathcal{Y}\) is called 2-universal hash function if, for every two strings \(x \neq x' \in \mathcal{X}\), we have that \(\Pr[h(x,S)=h(x',S)] \leq \frac{1}{\left|\mathcal{Y}\right|}\). In the same way, a function \(G:\{0,1\}^{\ell}\rightarrow\{0,1\}^{n}\) with seed length \(\ell < n\) is a pseudorandom generator (PRG) if, given a non-uniform quantum polynomial time distinguisher \(\mathcal{D}^* = \{\mathcal{D}^*_{\lambda}, \sigma_{\lambda}\}\), there exists a negligible function \(\nu(\cdot)\) such that \(\left|\text{I\kern-0.15em P}_{s \in \{0,1\}^n} [\mathcal{D}^*(1^{\lambda},G(s))=1] - \text{I\kern-0.15em P}_{r \in \{0,1\}^\ell} [\mathcal{D}^*(1^{\lambda},r)=1]\right| \leq \nu(\lambda)\) with \(r\) chosen uniformly at random.

A non-uniform quantum polynomial time distinguisher \(\mathcal{D}^* = \{\mathcal{D}^*_{\lambda}, \sigma_{\lambda}\}\) is composed of a \(\lambda\)-size quantum circuit \(\mathcal{D}^*_{\lambda}\) and a non-uniform \(\lambda\)-size quantum advice \(\sigma_{\lambda} \in \mathcal{B}(\mathcal{H}_{\mathcal{D}})\).

For convenience, we summarize the main acronyms used throughout the paper in 2.

2.2 Bit commitment↩︎

A bit commitment is a two-party interactive functionality between a quantum committer \(\mathcal{C}\) and a quantum receiver \(\mathcal{R}\). A commitment protocol is composed of two phases: the committing phase and the decommitting phase, where \(\mathcal{C}= \{\mathcal{C}_{com}, \mathcal{C}_{dec}\}\) and \(\mathcal{R}= \{\mathcal{R}_{com}, \mathcal{R}_{dec}\}\). During the committing phase, the committer \(\mathcal{C}\) commits to a bit \(b \in \{0,1\}\), with \(\mathcal{C}_{com}(1^{\lambda}, b)\) representing this step for the committer and \(\mathcal{R}_{com}(1^{\lambda})\), for the receiver. After the interaction, \(\mathcal{C}_{com}\) outputs a state \(\rho^{\mathcal{C}}_{com} \in \mathcal{B}_1(\mathcal{H}_{\mathcal{C}})\) and \(\mathcal{R}_{com}\), \(\rho^{\mathcal{R}}_{com} \in \mathcal{B}_1(\mathcal{H}_{\mathcal{R}})\). All in all, the commitment phase is written as \((\rho^{\mathcal{C}}_{com},\rho^{\mathcal{R}}_{com}) \mapsfrom \langle \mathcal{C}_{com}(1^{\lambda},b), \mathcal{R}_{com}(1^{\lambda}) \rangle\). Additionally, \(\rho^{\mathcal{C}}_{com}\) and \(\rho^{\mathcal{R}}_{com}\) may be entangled. During the decommitment phase, the interaction between \(\mathcal{C}_{dec}(\rho^{\mathcal{C}}_{com})\) and \(\mathcal{R}_{dec}(\rho^{\mathcal{R}}_{com})\) leads to an output of \(\mathcal{R}_{dec}\) that is either \(b'\) or \(\perp\).

2.2.1 Security against malicious receiver↩︎

The two notions of security that we use against malicious receivers are as follows:

2.2.2 Security against malicious sender↩︎

The security definitions of bit commitment against malicious sender are written as:

In this work, we use a weaker notion of binding that we call relaxed statistical binding. Unlike the general definition of statistically-binding bit commitment, each individual commitment is not statistically binding by itself. However, committing to a collection of bits binds for a fraction \(1-\eta\) of the bits.

Relaxed extractability works similarly to relaxed binding: after committing to many bits, most of them can be extracted.

2.3 Leftover hash lemma↩︎

2.4 Watrous Rewinding Lemma↩︎

2.5 Error resilience↩︎

Handling error correction in our protocol involves more subtleties compared to, for example, QKD, since in our case Alice and Bob are not trusted. In quantum communication protocols, there are two primary sources of errors: noise and losses. In the case of losses, since the proposed protocol incorporates bit commitments for each BB84 state, the loss of a state will result in the absence of a commitment for that instance of the protocol. Discarding non-committed instances has no impact on the security analysis of the protocol.

The potential presence of malicious parties prevents them from cooperating to estimate the noise. Therefore, an error correction subroutine must be included in the protocol to handle errors without any collaboration between parties [23]–[25]. An \((\mathcal{M}, K, t)\)-error correction code can correct errors in a code \(C\) composed of \(K\) elements from a metric space \(\mathcal{M}\), such that for every element \(w \in \mathcal{M}\), there exists at most one codeword \(c \in C\) within a ball of radius \(t\) around \(w\).

We propose the use of a non-interactive (classical) error correction code, which is syndrome-based, such as Low-Density Parity-Check (LDPC) codes [26]. The syndrome of an element \(w\) is its projection onto the orthogonal subspace of the code, capturing all the necessary information for decoding.

Finally, we consider the possibility of multiphoton events. While an ideal BB84 source generates single photons, experimental sources could accidentally generate more than one copy of a BB84 instance. We take into account this leakage of information for the privacy amplification of our proposed protocol. We present this as a general variable \(\vartheta\) that accounts for the information leakage.

3 Equivocal Commitment↩︎

In this section, we present a compiler that yields an equivocal \(\eta\)-relaxed statistically binding bit commitment from a statistically binding computationally hiding bit commitment. As previously discussed in the Introduction, our compiler is directly based on [7], but we reduce the number of repetitions in order to improve efficiency at the cost of requiring relaxed binding properties. The protocol is described in 1 and we prove the relaxed binding property in 3.1 and equivocality in 3.2.

3.1 Relaxed statistical binding↩︎

Given a statistically-binding and computationally-hiding commitment, we can build a commitment named EqCommitment that is \(\eta\)-relaxed statistically binding (4) and computationally hiding (1).

3.2 Equivocality↩︎

Our proof of equivocality is the same as [7], and we provide it here for completeness. We apply Watrous’ rewinding on the equivocal simulator in 2 to pass the verification test while not having consistent commitments.

4 Equivocal and relaxed-extractable commitment↩︎

We construct an equivocal and \(\chi\)-relaxed extractable commitment (5), named ERE-Commitment, based on an equivocal and \(\eta\)-relaxed statistically binding commitment. We present our protocol in 3 and then prove its equivocality and the relaxed extractability properties.

4.1 Equivocality↩︎

The proof of equivocality is very similar to 2. Nevertheless, we also provide in 1 the condition for the Naor’s commitment subprotocol of the ERE-Commitment to be computationally hiding, giving in 11 an analytical expression that quantifies it.

4.2 Relaxed extractability↩︎

Before proving relaxed-extractability, we first show that our commitment scheme is relaxed-binding.

To prove extractability, we will use the equivocality properties of EqCommitment. To prove that the simulator \(\mathcal{Q}_{\mathcal{C}^*}(\rho)\) defined in 4 that represents the \(Ideal\) interaction from 5 is indistinguishable from the \(Real\) one, we use the following sequence of hybrid arguments:

• Hybrid 0. Corresponds to the real protocol described in Algorithm 3.

• Hybrid 1. Similar to \(\text{Hyb}_0\) except in Step 3, in which we execute the equivocal simulator \(\mathcal{Q}_{\mathcal{R}^*,com}\) for \(i \in [4\lambda_{EX}]\), and in Step 5, to open the challenged commitments \(i \in E\), we execute \(\mathcal{Q}_{\mathcal{R}^*,dec}\).

• Hybrid 2. Similar to \(\text{Hyb}_1\), except that \(\left |\boldsymbol{x} \right \rangle_{\boldsymbol{\theta}}\) is not measured during Step 2 of 3, but rather during Step 3 of Algorithm 4, i.e., only the positions \(i \in E\) are measured and only after obtaining the sequence of indices.

• Hybrid 3. Identical to \(\text{Hyb}_2\) but the simulator performs the error correction as described in Step 7 of 4 and then, the honesty check as described in Step 8 of Algorithm 4.

• Hybrid 4. Identical to \(\text{Hyb}_3\) but the simulator extracts the non-challenged commitments as described in Step 9 of 4.

• Hybrid 5. The \(Ideal\) distribution, i.e., the extractable simulator described in Algorithm 4. The difference with respect to \(\text{Hyb}_4\) is that the simulator opens the non-extracted commitments to the value opened by the malicious committer, as described on Step 10.

Thus, ERE-Commitment is equivocal and \(\omega(\log^2(k)/k)\)-relaxed-extractable in the sense of [def:equivocal,def:extract].

5 OT from equivocal and relaxed-extractable bit commitment↩︎

In this section, we build an oblivious transfer functionality assuming an equivocal and \(\chi\)-relaxed extractable bit commitment, with \(\chi = \omega(\log^2(k)/k)\). The structure is similar to [4], [7], but applying it to our setting. Lastly, we show how to optimize the number of runs of OT in 2.

The oblivious transfer functionality \(\mathcal{F}_{OT}(\cdot, \cdot)\) is a quantum two-parties interactive functionality in which Alice, \(A\), inputs two messages \(m_0, m_1 \in \{0,1\}^{\lambda}\), and Bob, \(B\), inputs a choice bit \(b \in \{0,1\}\). The output after the interaction is \((m_0,m_1)\) on Alice’s side and \((b,m_b)\) on Bob’s side. More concretely, the OT functionality \(\mathcal{F}_{OT}\) works as follows:

• \(\mathcal{F}_{OT}((m_0,m_1), \cdot)\) takes an input \(b\) (or \(\perp\)), returns \(m_b\) to \(B\) and END (or \(\perp\)) to \(A\).

• \(\mathcal{F}_{OT}(\cdot, b)\) takes an input \((m_0,m_1)\) (or \(\perp\)), returns END to \(A\) and \(m_b\) (or \(\perp\)) to \(B\).

5.1 Security against a malicious Alice↩︎

We will now establish the security of Bob against a quantum poly-time non-uniform malicious Alice, given 7. To prove that Eq. ?? holds in the proposed scheme, the following hybrid argument is required:

• Hybrid 0. The \(Real\) distribution given by Algorithm 5.

• Hybrid 1. Similar to \(\text{Hyb}_0\) except in Step 2, where we execute the equivocal simulator \(\mathcal{Q}_{\mathcal{R}^*,com}\) for \(i \in [2\lambda_{OT}]\). The second difference with respect to \(\text{Hyb}_0\) is that in Step 4, to open the challenged commitments \(i \in T\), we execute \(\mathcal{Q}_{\mathcal{R}^*,dec}\).

• Hybrid 2. The \(Ideal\) distribution given by Algorithm 6.

5.2 Security against a malicious Bob↩︎

In this section, we prove security against malicious Bob. We start by analyzing the number of qubits necessary in the protocol to achieve the desired level of security in 11. Then, we prove the security of the protocol in 5.

We now move on to prove the security of the protocol against a quantum-poly time malicious Bob and an honest Alice. The sequence of hybrid arguments for this case is:

• Hybrid 0. The \(Real\) distribution given by Algorithm 5.

• Hybrid 1. Similar to \(\text{Hyb}_0\) except in Step 2, in which we execute the extractable simulator \(\mathcal{Q}_{\mathcal{R}^*,com}\) of Algorithm 4.

• Hybrid 2. The \(Ideal\) distribution given by Algorithm 7.

Acknowledgements↩︎

AY acknowledges Lucas Hanouz for the discussions related with error correction. We also want to acknowledge Matías R. Bolaños for highlighting the necessity of adding multiphoton events and suggesting some improvements in the protocol. Lastly, we want to acknowledge anonymous reviewers for their feedback. ED, ABG and AY are supported by the European Union’s Horizon Europe Framework Programme under the Marie Skłodowska Curie Grant No. 101072637, Project Quantum-Safe Internet (QSI). ED and PL acknowledge PEPR integrated project QCommTestbed ANR-22-PETQ-0011 part of Plan France 2030, VY acknowledges the support of European Research Council Starting Grant QUSCO, 758911. ED and AI acknowledge the support of QuantERA QuantaGENOMICS under Grant Agreement No. 101017733. ABG is supported by ANR JCJC TCS-NISQ ANR-22-CE47-0004. This work was done in part while ABG was visiting the Simons Institute for the Theory of Computing.

6 Distance bound for a malicious Alice↩︎

Since Naor’s commitment is computationally hiding, and so is the extractable layer, the security against a malicious Alice will be bound by the preservation of the hiding property, as discussed in 1. This bound is given by the \(\Delta\)-distance between the key generated by ERE-Commitment and a string of uniformly random bits of length \(\lambda_{PQS}\).

7 Benchmark of QOT protocols↩︎

The numerical benchmark presented in 1 is obtained by numerically optimizing the concrete security bounds of the corresponding protocols.

While [7] does not provide explicit analytical bounds, in [7] the authors refer to [18] for the statistical binding proof. Hence, arguing as in 11, one can derive the following bound for the OT layer: \[\begin{align} & \Delta (\rho_{K_{\bar{b}}K_{b}E}, \frac{1}{2^l} \mathbb{I}\otimes \rho_{K_{b}E}) \leq \\ &\leq \frac{1}{2} \cdot 2^{-\frac{1}{2}[(1-\xi - h(\delta))4\lambda_{OT}-l]} + \sqrt{6} \exp(-\delta^2 8\lambda_{OT}/100) + 2 \exp(- \xi^24\lambda_{OT}) , \end{align}\] where \(\xi,\delta > 0\) denote sampling parameters and \(h(r,x): \{0,1\}^m \times \{0,1\}^n \rightarrow \{0,1\}^{\ell}\) is a universal hash function. Similarly, following the same arguments as in 6, one obtains the following security bound for the extractable layer:

\[\begin{align} & \Delta (\rho_{K_{\bar{b}}K_{b}E}, \frac{1}{2^l} \mathbb{I}\otimes \rho_{K_{b}E}) \leq \\ &\leq \frac{1}{2} \cdot 2^{-\frac{1}{2}[(\frac{1}{2}-\xi - h(\delta))\lambda^2_{EX}-1]} + \sqrt{6} \exp(-\lambda^3_{EX}\delta^2/100) + 2 \exp(-2 \xi^2\lambda^3_{EX}), \end{align}\] where the security parameters are taken following [7]. Following the structure of the protocol in [7], the total number of BB84 states is given by \[\begin{align} \lambda_{\mathrm{BCKM21}} = 16 \cdot \lambda_{OT}\cdot \lambda_{eq} \cdot 4 \cdot 2\cdot \lambda^3_{EX} + 16\cdot \lambda_{OT}, \end{align}\] since each OT layer consists of \(\lambda_{eq}\) equivocal commitments, each of them compounded by four executions of the extractable commitment. Therefore, by setting \(\Delta\leq \varepsilon\) with \(\varepsilon = 10^{-15}\) and \(\lambda_{eq} = 128\), we obtain the value \(\lambda_{\mathrm{BCKM21}} = 2.27\times 10^{13}\) reported in 1.

We now turn to the protocol proposed in [21]. Among their constructions, we focus on the ones based on BB84 states, namely [21] and [21], which implement string OT with random bases. The bound for the 3-round communication protocol of [21] is given in [21]. It requires a total of \(\lambda_{\mathrm{3OT \, ABKK22}}= 23000 \lambda\) BB84 states, where \(\lambda\) is determined by the following security bounds: \[\begin{align} \mu_{\mathrm{R}^*} & =\frac{\sqrt{5}}{2^\lambda}+\frac{4 q_{RO}}{2^{18 \lambda}}+\frac{148(q_{RO}+46000 \lambda+1)^3+1}{2^{2 \lambda}}+\frac{368000 q_{RO} \lambda}{2^\lambda}, \\ \mu_{\mathrm{S}^*} &=\frac{430 q_{RO} \sqrt{\lambda}}{2^\lambda} \,, \end{align}\] where \(\mu_{\mathrm{R}^*}\) and \(\mu_{\mathrm{S}^*}\) are, respectively, the security bounds against a malicious receiver and a malicious sender, and \(q_{RO}\) is an upper bound on the total number of random-oracle queries made by the adversary.

Similarly, [21], which yields a 4-round OT protocol, requires a total of \(\lambda_{\mathrm{4OT \, ABKK22}}=10300 \lambda\) BB84 states, where \(\lambda\) is determined by the bounds in [21]: \[\begin{align} \mu_{\mathrm{R}^*} & =\frac{\sqrt{5}}{2^\lambda}+\frac{1}{2^{9 \lambda}}+\frac{148(q_{RO}+2 n+1)^3+1}{2^{2 \lambda}}+\frac{16 q_{RO} n}{2^\lambda}, \\ \mu_{\mathrm{S}^*} &=\frac{288 q_{RO} \sqrt{\lambda}}{2^\lambda} \,, \end{align}\] where, following [21], we take \(n = 10300\,\lambda\).

As discussed in [21], the random oracle (RO) can be instantiated with SHA-256. Following [28], the optimal success probability for solving the preimage search problem on an \(m\)-bit random oracle with \(q_{RO}\) quantum queries is \(\Theta(q_{RO}^2/2^m)\). Taking \(m = 256\) and imposing \(p_{\mathrm{succ}}\leq 2^{-128}\) yields \(q_{RO} \leq 2^{64}\), corresponding to 128-bit post-quantum preimage security. This upper bound on the number of oracle queries is also consistent with the NIST recommendation of considering at most \(2^{64}\) oracle-like queries in its post-quantum security definitions [29].

By imposing \(\mu_{\mathrm{R}^*} = \mu_{\mathrm{S}^*} \leq \varepsilon\) with \(\varepsilon = 10^{-15}\), and using \(q_{RO}= 2^{64}\), we obtain the numerical values \(\lambda_{\mathrm{3OT \, ABKK22}} = 3.22 \times 10^6\) and \(\lambda_{\mathrm{4OT \, ABKK22}}= 1.43\times 10^6\) BB84 states reported in 1.

For our protocol, the optimization is performed by targeting at most \(\varepsilon = 10^{-15}\) and fixing \(\alpha = 0.006\) and \(\vartheta= 0.001\) in ?? and ?? , with a error correction syndrome of \(q = 0.1\lambda\) ⁶. It is important to emphasize that this is the only benchmark that explicitly incorporates transmission errors, since the protocols in [7], [21] are not robust to such errors. For completeness, we also include in 1 the benchmark corresponding to a noiseless implementation of our protocol.

References↩︎