11institutetext: Sorbonne Université, CNRS, LIP6, 4 Place Jussieu, Paris
F-75005, France

# A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

Eleni Diamanti  Alex B. Grilo  Adriano Innocenzi  Pascal Lefebvre
Verena Yacoub  Álvaro Yángüez Corresponding author<EMAIL_ADDRESS>
###### Abstract

We present a new simulation-secure quantum oblivious transfer (QOT) protocol
based on one-way functions in the plain model. With a focus on practical
implementation, our protocol surpasses prior works in efficiency, promising
feasible experimental realization. We address potential experimental errors
and their correction, offering analytical expressions to facilitate the
analysis of the required quantum resources. Technically, we achieve simulation
security for QOT through an equivocal and relaxed-extractable quantum bit
commitment.

##  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 [BB84]. However, it was soon realized that even quantumly, a
very limited family of cryptographic primitives can achieve such level of
security [LC97, May97], 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) [DFL+09]. However, it is not
expected that OT (and thus MPC) can be constructed only from one-way functions
(OWFs)111One-way functions are functions that are easy to compute and hard to
invert. These are considered the minimal computational assumption in classical
cryptography.222More formally, [IR90] shows that no MPC protocol can be built
from OWF in a black-box way..

On the other hand, [GLSV21, BCKM21] showed that OT can be built from OWFs and
quantum resources. More precisely, [GLSV21, BCKM21] showed how to build
equivocal and extractable commitment schemes, which were known to be
sufficient to build quantum protocols for OT [DFL+09] and MPC [IPS08, Kil88]
333We notice that later, it was shown that MPC can be built even from weaker
computation assumptions such as pseudo-random states [MY22, AQY22]..

One important feature of [GLSV21, BCKM21] 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 [AAB+23,
GBR+23, PSC+23] [ZMM+24], 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 [GLSV21]
[BCKM21] 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 [GLSV21] and [BCKM21] 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 [GLSV21] 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 [GLSV21] scheme non-trivial.

  * •

Inefficiency. The iterative structure of the protocol proposed by [BCKM21]
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 [BB84], 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 [BCKM21], while avoiding some of its
bottlenecks and while making it efficiently implementable. In particular, with
this new protocol, we expect that around $10^{6}$ 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 distil 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 [GLSV21, BCKM21] is to achieve a quantum
protocol for oblivious transfer, since it can be used to construct MPC in a
generic way [IPS08]. 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_{\overline{b}}$ and Alice should not learn $b$).

In the quantum protocol for OT proposed in [CK88, BBCS92], 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\\}$. However, 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 basis 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 [BF12]. The bit commitment
sub-protocol is finished when Alice sends the basis 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.
444We notice that for this to be true, the simulator has to have some leverage
(e.g., a trapdoor, or the ability to rewind), otherwise the protocol would not
be secure.

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. 555We have here the same
considerations as in Footnote 4.

In [DFL+09], they show that equivocation and extraction of the quantum bit
commitment are sufficient properties to prove the simulation-security of the
QOT protocols of [CK88, BBCS92]. Moreover, the technical contribution of
[GLSV21, BCKM21] 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 [BCKM21] 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 commuter 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}}^{\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}^{\overline{\gamma_{i}}},c_{i,1}^{\overline{\gamma_{i}}}$. At each
step, the equivocator uses Watrous’ rewinding [Wat06] 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}}^{\overline{\gamma_{i}}}$ to open, so
that the decommitment will be the desired bit. The binding/extractable
property follows from the fact that, if many of the checks on $\gamma_{i}$’s
passed, then most of the pairs
$c_{i,0}^{\overline{\gamma_{i}}},c_{i,1}^{\overline{\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 [BCKM21], but the binding property completely breaks. In
particular, a malicious committer can guess $\gamma$, and commit to two
different values of $c_{0}^{\overline{\gamma}},c_{1}^{\overline{\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 Section 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 [BCKM21]. This compiler is
heavily inspired by the structure of the quantum OT protocol of [CK88,
BBCS92]. 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 basis 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 [BCKM21] 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 basis, and then
equivocates the opening to these values. Later in the protocol, whenever the
committer sends the basis, the extractor is able to measure all of the qubits
in the correct basis 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
[BCKM21], 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 [BCKM21], 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(\boldsymbol{\tilde{x}^{j}}\right)_{j\in[2k]}$ subsets of size $m$.
Using privacy amplification techniques found in QKD [Ren08], 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
[BCKM21]. 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 $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[8\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 is simulation-based
secure given an equivocal and a $(\chi,\epsilon)$-relaxed extractable bit
commitment. Having a practical implementation as our final goal, we take into
account the possible experimental errors as well as their correction, and we
provide analytical expressions based on [BF12] that facilitates the bench-
marking of the needed quantum resources. Moreover, we propose a method to
distill a number of $n_{OT}$ QOT keys from a single run of the protocol. This
could be done if a large number of BB84 states was required to reach a desired
smaller sampling error (thus a tighter $\Delta$-security bound).

###  1.3 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

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.

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^{\prime}\in\mathcal{X}$, we have that
$\Pr[h(x,S)=h(x^{\prime},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-1.49994ptP}_{s\in\\{0,1\\}^{n}}[\mathcal{D}^{*}(1^{\lambda},G(s))=1]-\text{I\kern-1.49994ptP}_{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}})$.

###  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^{\prime}$ or $\perp$.

####  2.2.1 Security against malicious receiver.

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

######  Definition 1 (Computational hiding)

A bit commitment protocol $(\mathcal{C},\mathcal{R})$ is computationally
hiding if, given any polynomial-size interactive receiver
$\mathcal{R}^{*}_{com}=\\{\mathcal{R}^{*}_{com,\lambda},\mathbf{\rho}_{\lambda}\\}$
with
$\text{OUT}_{\mathcal{R}}\langle\mathcal{C}(1^{\lambda},b),\mathcal{R}^{*}_{com,\lambda}(\mathbf{\rho}_{\lambda})\rangle$
being the output of the receiver after the commitment phase, there exists a
negligible function $\nu(\cdot)$ such that:

$\displaystyle\Big{|}\text{I\kern-1.49994ptP}[OUT_{\mathcal{R}}\langle\mathcal{C}_{com}(1^{\lambda},0),\mathcal{R}^{*}_{com}(\rho_{\lambda})\rangle=1]-$
$\displaystyle\text{I\kern-1.49994ptP}[OUT_{\mathcal{R}}\langle\mathcal{C}_{com}(1^{\lambda},1),\mathcal{R}^{*}_{com}(\rho_{\lambda})\rangle=1]\Big{|}=\nu(\lambda).$

######  Definition 2 (Equivocality)

Given a set of auxiliary states
$\\{\rho_{\lambda},\sigma_{\lambda}\\}_{\lambda\in\mathbb{N}}$ with
$\rho_{\lambda},\sigma_{\lambda}\in\mathcal{B}_{1}(\mathbb{C}^{n})$, a bit
commitment protocol $(\mathcal{C},\mathcal{R})$ is equivocal if, for any poly-
size receiver
$\mathcal{R}^{*}=\\{\mathcal{R}_{com,\lambda}^{*},\mathcal{R}_{dec,\lambda}^{*},\rho_{\lambda}\\}$,
there exists a non-uniform quantum polynomial time equivocator
$\mathcal{Q}_{\mathcal{R}^{*}}=\\{\mathcal{Q}_{\mathcal{R}^{*},com},\mathcal{Q}_{\mathcal{R}^{*},dec}\\}$
such that, for any poly-size distinguisher
$\mathcal{D}=\\{\mathcal{D}_{\lambda},\sigma_{\lambda}\\}$, there exists a
negligible function $\nu(\lambda)>0$ for the committed bit $b\in\\{0,1\\}$:

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma_{\lambda},Real_{b})=1]-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma_{\lambda},Ideal_{b})=1\right|=\nu(\lambda),$

provided that:

Realb: Interaction between $\mathcal{R}_{com}^{*}(\rho)$ and
$\mathcal{C}_{com}(1^{\lambda},b)$ such that
$(\rho^{\mathcal{C}}_{com},\rho^{\mathcal{R}^{*}}_{com})\mapsfrom\langle\mathcal{C}_{com}(b),\mathcal{R}_{com}^{*}(\rho)\rangle$
and
$\rho^{\mathcal{R}^{*}}_{final}\mapsfrom\langle\mathcal{C}_{dec}(\rho^{\mathcal{C}}_{com}),\mathcal{R}_{dec}^{*}(\rho^{\mathcal{R}^{*}}_{com})\rangle$.

Idealb: The quantum simulator outputs
$(\rho^{\mathcal{C}}_{com},\rho^{\mathcal{R}}_{com})\mapsfrom\mathcal{Q}_{\mathcal{R}^{*},com}(\rho)$.
Then, $\rho^{\mathcal{R}^{*}}_{final}$ $\mapsfrom$
$\langle\mathcal{Q}_{\mathcal{R}^{*},dec}(\rho^{\mathcal{C}}_{com}),\mathcal{R}_{dec}^{*}(\rho^{\mathcal{R}^{*}}_{com})\rangle$.

####  2.2.2 Security against malicious sender.

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

######  Definition 3 (Statistical binding)

A bit commitment protocol $(\mathcal{C},\mathcal{R})$ is statistical-binding
if, for all poly-size committer
$\mathcal{C}^{*}=\\{\mathcal{C}_{com}^{*},\mathcal{C}_{dec}^{*}\\}$ and
$\lambda\in\mathbb{N}$, such that:

$\displaystyle\left(\rho^{\mathcal{C}^{*}}_{com},\rho^{\mathcal{R}}_{com}\right)\mapsfrom\left(\langle\mathcal{C}^{*}_{com}(1^{{\lambda}},b),\mathcal{R}_{com}(1^{{\lambda}})\rangle\right),$

there exists a bit $b\in\\{0,1\\}$ for which:

$\text{I\kern-1.49994ptP}[OUT_{\mathcal{R}}\langle\mathcal{C}_{dec}^{*}(1^{\lambda},\rho^{\mathcal{C}^{*}}_{com}(\lambda)),\mathcal{R}_{dec}(1^{\lambda},\rho^{\mathcal{R}}_{com}((\lambda))\rangle\
\neq b]\leq\nu(\lambda).$

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.

######  Definition 4 ($(\eta,\epsilon)$-relaxed statistical binding)

Let $(\mathcal{C},\mathcal{R})$ be a bit commitment protocol. For a sequence
of $m$ commitments
$\left(\mathcal{C}_{i}^{*}=(\mathcal{C}_{com,i}^{*},\mathcal{C}_{dec,i}^{*})\right)_{i\in
m}$ with $\lambda\in\mathbb{N}$ such that:

$\displaystyle\left(\boldsymbol{\rho}^{\mathcal{C}^{*}}_{com}(\lambda),\boldsymbol{\rho}^{\mathcal{R}}_{com}(\lambda)\right)=\left(\bigotimes_{i=1}^{m}\rho^{\mathcal{C}^{*}}_{com,i},\bigotimes_{i=1}^{m}\rho^{\mathcal{R}}_{com,i}\right)\mapsfrom\left(\langle\mathcal{C}^{*}_{com,i}(1^{{\lambda}},b_{i}),\mathcal{R}_{com,i}(1^{{\lambda}})\rangle\right)_{i\in
m}.$

$(\mathcal{C},\mathcal{R})$ is ($\eta,\epsilon$)-relaxed-binding if there
exists a set $I\subseteq[m]$, where $I\geq(1-\eta)m$, and a string
$\boldsymbol{b}\in\\{0,1\\}^{|I|}$, if, with probability at least
$1-\epsilon$, there exists a negligible function $\nu(\lambda)$ such that:

$\text{I\kern-1.49994ptP}[OUT_{\mathcal{R}}\langle\mathcal{C}_{dec}^{*}(1^{\lambda},\boldsymbol{\rho}^{\mathcal{C}^{*}}_{com}(\lambda)),\mathcal{R}_{dec}(1^{\lambda},\boldsymbol{\rho}^{\mathcal{R}}_{com}((\lambda))\rangle|_{I}\neq\boldsymbol{b}(\lambda)]\leq\nu(\lambda).$

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

######  Definition 5 (($\chi$,$\epsilon$)-relaxed extractability)

Let $(\mathcal{C},\mathcal{R})$ be a bit commitment protocol. Given a sequence
of auxiliary states $\left(\rho_{i},\sigma_{i}\right)_{i\in m}$ where
$\rho_{i},\sigma_{i}\in\mathcal{B}_{1}(\mathbb{C}^{{\lambda}})$ and
$\lambda\in\mathbb{N}$, $m$ sequential repetitions of commitments
$(\rho^{\mathcal{C}^{*}}_{com,1},\rho^{\mathcal{R}}_{com,1}),$
$...,(\rho^{\mathcal{C}^{*}}_{com,m},\rho^{\mathcal{R}}_{com,m})$ are
($\chi$,$\epsilon$)-relaxed-extractable if, for any poly-size quantum
malicious committer $\mathcal{C}^{*}$
$=\\{(\mathcal{C}^{*}_{com,i}(1^{{\lambda}}))_{i\in m},$
$\bigotimes_{i=1}^{m}\rho_{i}\\}$, there exists a quantum polynomial time
extractor
$\mathcal{Q}_{\mathcal{C}^{*}}=\\{\mathcal{Q}_{\mathcal{C}^{*},com},\mathcal{Q}_{\mathcal{C}^{*},dec}\\}$
such that, for any poly-size distinguisher
$\mathcal{D}^{*}=\\{(\mathcal{D}^{*}_{i})_{i\in
m},\bigotimes_{i=1}^{m}\sigma_{i}\\}$ and for every polynomial-size opening
strategy $\left(\mathcal{C}^{*}_{dec,i}\right)_{i\in m}$, there is a
negligible function $\nu(\lambda)>0$ that obeys:

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma_{\lambda},Real)=1]-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma_{\lambda},Ideal)=1]\right|=\nu(\lambda),$

with:

Real: Interaction between $\mathcal{R}_{dec}(\rho^{\mathcal{R}}_{com})$ and
$\mathcal{C}^{*}_{dec}(\rho^{\mathcal{C}^{*}}_{com})$ such that
$(\rho^{\mathcal{C}^{*}}_{final},b_{i})$
$\mapsfrom\langle\mathcal{C}^{*}_{dec}(\rho^{\mathcal{C}^{*}}_{com}),\mathcal{R}_{dec}(\rho^{\mathcal{R}}_{com})\rangle_{i}$,
with $b_{i}\in\\{0,1,\perp\\}$. Then, the output after $m$ sequential
repetitions is given by
$\left(\boldsymbol{\rho}^{\mathcal{C}^{*}}_{final}(\lambda),\boldsymbol{b}(\lambda)\right)\mapsfrom\left(\langle\mathcal{C}^{*}_{com,i}(1^{{\lambda}},b_{i}),\mathcal{R}_{com,i}(1^{{\lambda}})\rangle\right)_{i\in
m}$, where $\boldsymbol{b}\in\\{0,1\\}^{|I|}$ with $I\geq(1-\chi)m$.

Ideal: The simulator computes
$(\boldsymbol{\rho}^{\mathcal{C}}_{com}(\lambda),\boldsymbol{\rho}^{\mathcal{R}}_{com}(\lambda),\boldsymbol{b^{*}}(\lambda))\mapsfrom(\mathcal{Q}_{\mathcal{C}^{*},com}(\rho_{i}))_{i\in\lambda}$,
where $\boldsymbol{b}^{*}\in\\{0,1,\mathbbold{\qm}\\}^{m}$. Then,
$(\boldsymbol{\rho}^{\mathcal{C}}_{final}(\lambda),\boldsymbol{b}(\lambda))$
$\mapsfrom$
$\langle\mathcal{C}^{*}_{dec}(\boldsymbol{\rho}^{\mathcal{C}}_{com}(\lambda)),\mathcal{R}_{dec}(\boldsymbol{\rho}^{\mathcal{R}}_{com}(\lambda))\rangle$.
The simulator outputs FAIL if :

  * •

$|\\{i:b^{*}_{i}=\mathbbold{\qm}\\}|\geq\chi$, or

  * •

if for any $i$ such that $b^{*}_{i}\in\\{0,1\\}$, $b_{i}\neq b^{*}_{i}$.

If the simulator does not output FAIL, it outputs
$(\boldsymbol{\rho}^{\mathcal{C}}_{final}(\lambda),\boldsymbol{b}_{S}(\lambda))$,
where $\boldsymbol{b}_{S}(j)=\boldsymbol{b^{*}}(j)$ every time
$b^{*}_{i}\neq\mathbbold{\qm}$, and replaces the $\mathbbold{\qm}$ cases by
the values $\boldsymbol{b}(j)$ opened by
$\mathcal{C}^{*}_{dec}(\boldsymbol{\rho}^{\mathcal{C}}_{com}(j))$.

###  2.3 Leftover hash lemma

######  Definition 6 (Quantum conditional min-entropy [Ren08])

Given a classical-quantum hybrid state
$\rho_{XE}=\sum_{x\in\mathcal{X}}p_{x}(x)\left|x\right\rangle\left\langle
x\right|\otimes\sigma_{E}^{x}$, the conditional min-entropy
$\text{H}_{\text{min}}(X|E)$ is defined as:

$\text{H}_{\text{min}}(X|E)=\text{H}_{\text{min}}(\rho_{XE}|E)=\sup_{\sigma_{E}}\max\\{h\in\mathbb{R}:2^{-h}\,\text{I}\otimes\sigma_{E}-\rho_{XE}\geq
0\\}.$

######  Lemma 1 (Leftover Hash Lemma with Quantum Side Information [Ren08])

Let $\rho_{XE}$ be a hybrid state and
$h(r,x):\\{0,1\\}^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\ell}$ a two-
universal hash function, with $r$ uniformly distributed over $\mathcal{R}$.
Then, $K=h(r,x)$ satisfies:

$\Delta(\rho_{K_{\bar{b}}K_{b}E},\frac{1}{2^{\ell}}\text{I}\otimes\rho_{K_{b}E})\leq\frac{1}{2}\sqrt{2^{\ell-
H_{min}(X|E)}}.$

######  Lemma 2 (Conditional min-entropy [BF12])

Given an $n$-qubit system $A$, let the state
$\left|\psi_{AE}\right\rangle=\sum_{\begin{subarray}{c}\textbf{b}\in\\{0,1\\}^{n}\\\
\left|w(\textbf{b})-\alpha\right|\leq\delta\end{subarray}}\left|b\right\rangle\otimes\left|\psi_{E}^{b}\right\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{E}$
have a relative Hamming weight $\delta$-close to $\alpha$, with
$\delta+\alpha\leq 1/2$. Let $X$ be the random variable obtained by measuring
$A$ in the bases
$H^{\boldsymbol{\theta}}\\{\left|0\right\rangle,\left|1\right\rangle\\}^{\otimes
n}$ for $\boldsymbol{\theta}\in\\{0,1\\}^{n}$. Then:

$H_{\text{min}}(X|E)\geq
d_{H}(\boldsymbol{\theta},\boldsymbol{\hat{\theta}})-h_{2}(\delta+\alpha)n,$
(2.1)

where $\boldsymbol{\hat{\theta}}\in\\{0,1\\}^{n}$ denotes the measurement
bases committed by Bob, $h_{2}(\cdot):[0,1]\rightarrow[0,1]$, the binary
entropy function and
$d_{H}(\cdot,\cdot):\\{0,1\\}^{n}\times\\{0,1\\}^{n}\rightarrow\mathbb{N}$,
the Hamming distance function.

###  2.4 Watrous Rewinding Lemma

######  Lemma 3 (Rewinding lemma with small perturbations [Wat06])

Let $Q$ be an $(n,k)$-quantum circuit that outputs a classical bit $b$ and $m$
qubits. For any input state
$\left|\psi\right\rangle\in\mathcal{B}_{1}(\mathbb{C}^{n})$, let $p(\psi)$ be
the probability of measuring the classical bit $b=0$ such that the state after
measuring the action of the the circuit $Q$ is
$\left|\phi_{0}(\psi)\right\rangle\in\mathcal{B}_{1}(\mathbb{C}^{m})$. Let
$p_{0}\in(0,1)$, $\epsilon\in(0,1/2)$ and $q\in(0,1)$, where $q$ is the
probability that the quantum circuit acts like a unitary, be such that:

  1. 1.

$\left|p(\psi)-q\right|<\epsilon$,
$\forall\left|\psi\right\rangle\in\mathcal{B}_{1}(\mathbb{C}^{n})$,

  2. 2.

$p_{0}<p(\psi)$,
$\forall\left|\psi\right\rangle\in\mathcal{B}_{1}(\mathbb{C}^{n})$,

  3. 3.

$p_{0}(1-p_{0})\leq q(1-q)$.

Then, there exists a general quantum circuit $\mathcal{R}$ of size
$\mathcal{O}\left(\frac{\log(1/\epsilon)\left|Q\right|}{p_{0}(1-p_{0})}\right)$,
such that, for every input state $\left|\psi\right\rangle$, the output
$R(\left|\psi\right\rangle)$ satisfies:

$\left\lVert
R(\left|\psi\right\rangle)-\left|\phi_{0}(\psi)\right\rangle\right\rVert_{1}\leq
4\sqrt{\epsilon}\frac{\log(1/\epsilon)}{p_{0}(1-p_{0})}.$

##  3 Equivocal Commitment

In this section, we present a compiler that yields an equivocal ($\eta$,
$\epsilon$)-relaxed statistically binding bit commitment from a statistically
binding computationally hiding bit commitment. As previously discussed in the
Introduction 1, our compiler is directly based on [BCKM21], 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 Algorithm 1 and we
prove the relaxed binding property in Section 3.1 and equivocality in Section
3.2.

###  3.1 Relaxed statistical binding

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

Algorithm 1 EqCommitment: Equivocal commitment

Input of $\mathcal{C}$: bit $b\in\\{0,1\\}$, seeds
$\boldsymbol{p}^{0}_{0},\boldsymbol{p}^{0}_{1},\boldsymbol{p}^{1}_{0},\boldsymbol{p}^{1}_{1}\in\\{0,1\\}^{\lambda_{PQS}}$.
Assumptions: Bit commitment $Com_{r}$ that is statistically binding and
computationally hiding and which uses $r$ as the randomness for the commitment

1:

2:$\mathcal{C}$ chooses two random bits $u^{0},u^{1}\in\\{0,1\\}$.

3:$\mathcal{C}$ and $\mathcal{R}$ commit to four values, by using the input
seeds in the following way:

  * •

$c_{0}^{0}$ =
$Com_{\boldsymbol{p}^{0}_{0}}\langle\mathcal{C}(u^{0}),\mathcal{R}\rangle$

  * •

$c^{0}_{1}$ =
$Com_{\boldsymbol{p}^{0}_{1}}\langle\mathcal{C}(u^{0}),\mathcal{R}\rangle$

  * •

$c^{1}_{0}$ =
$Com_{\boldsymbol{p}^{1}_{0}}\langle\mathcal{C}(u^{1}),\mathcal{R}\rangle$

  * •

$c_{1}^{1}$ =
$Com_{\boldsymbol{p}^{1}_{1}}\langle\mathcal{C}(u^{1}),\mathcal{R}\rangle$

4:$\mathcal{R}$ sends a bit $\gamma\in\\{0,1\\}$ to $\mathcal{C}$

5:$\mathcal{R}$ and $\mathcal{C}$ decommit
$u^{\gamma}_{0}=Decom_{\boldsymbol{p}^{\gamma}_{0}}(c^{\gamma}_{0})$ and
$u^{\gamma}_{1}=Decom_{\boldsymbol{p}^{\gamma}_{1}}(c^{\gamma}_{1})$

6:$\mathcal{R}$ aborts if $u^{\gamma}_{0}\neq u^{\gamma}_{1}$.

7:$\mathcal{C}$ computes $e=b\oplus u^{\bar{\gamma}}$ and sends it to
$\mathcal{R}$.

8:

9:$\mathcal{C}$ chooses a random bit $\delta\in\\{0,1\\}$ and sends both,
$\delta$ and $b$ to $\mathcal{R}$.

10:$\mathcal{C}$ and $\mathcal{R}$ decommit $c^{\bar{\gamma}}_{\delta}$:
$u^{\bar{\gamma}}_{\delta}=Decom_{\boldsymbol{p}_{\delta}^{\bar{\gamma}}}(c^{\bar{\gamma}}_{\delta})$

11:$\mathcal{R}$ aborts if $u^{\bar{\gamma}}_{\delta}\neq b\oplus e$.

###### Theorem 3.1

If $Com$ is a statistically binding commitment scheme, then, for any function
$\eta(n)$, EqCommitment is $\left(\eta,2^{-n\eta}\right)$-relaxed
statistically binding.

###### Proof

Let us consider $n$ sequential repetitions of the EqCommitment protocol. Let
us denote $c^{\gamma}_{\delta,i}$ as the commitment $c^{\gamma}_{\delta}$ of
the $i$-th run of the protocol. Notice that all $c^{\gamma}_{\delta,i}$ are
statistically binding, so with overwhelming probability, we can define the
values $u^{\gamma}_{\delta,i}$ such that the opening of
$c^{\gamma}_{\delta,i}$ to a value that is different than
$u^{\gamma}_{\delta,i}$ fails.

Let us define the set of $B_{0}=\\{i:\exists{\gamma}\quad
u^{{\gamma}}_{0,i}\neq u^{{\gamma}}_{1,i}\\}$. Let us also define the event
$E$ where the check on Step 4 passes on all runs of the protocol. Notice that
for each $j\not\in B_{0}$, the $j$-th run of the commitment is statistically
binding, and the goal is now to connect $|B_{0}|$ and
$\text{I\kern-1.49994ptP}[E]$. It can be shown that:

$\displaystyle\text{I\kern-1.49994ptP}[E]\leq\frac{1}{2^{|B_{0}|}},$ (3.1)

which is equivalent to the fact that if
$\text{I\kern-1.49994ptP}[E]\geq\epsilon=2^{-n\eta}$, then $|B_{0}|\leq
n\eta$, which shows that EqCommitment is $(\eta,2^{-n\eta})$-relaxed
statistically binding. The proof of Equation 3.1 holds since for each $i\in
B_{0}$, there exists one $\gamma_{i}^{*}$ such that
$u^{\gamma_{i}^{*}}_{0,i}\neq u^{\gamma_{i}^{*}}_{1,i}$, and in order for $E$
be true, the challenged $\gamma_{i}$ for that run is different than
$\gamma_{i}^{*}$, which happens with probability $\frac{1}{2}$. Since all
challenges are picked independently, the probability is:

$\text{I\kern-1.49994ptP}[\forall i\in
B_{0}:\gamma_{i}\neq\gamma^{*}_{i}]=\prod_{i\in B_{0}}\
\text{I\kern-1.49994ptP}[\gamma_{i}\neq\gamma^{*}_{i}]\leq\frac{1}{2^{|B_{0}|}},$

where the inequality accounts for the trivial case where $\nexists\gamma_{i}$
such that $u^{\gamma_{i}}_{0,i}\neq u^{\gamma_{i}}_{1,i}$, resulting in
$\text{I\kern-1.49994ptP}[E]=0$.

###  3.2 Equivocality

Algorithm 2 Equivocal simulator $\mathcal{Q}_{Eq}$

1:$\mathcal{Q}_{\mathcal{R}^{*}}$ samples a random bit
$\tilde{\gamma}\in\\{0,1\\}$ and stores it in P.

2:$\mathcal{C}$ samples two random bits $\tilde{u},\tilde{y}\in\\{0,1\\}$

3:Commitment subprotocol for the simulated committer $\tilde{\mathcal{C}}$

  * •

If $\tilde{\gamma}=0$, $\tilde{\mathcal{C}}$ commits to:

    1. 1.

$\tilde{c}_{0}^{0}$ =
$Com_{\boldsymbol{p}_{0}^{0}}\langle\tilde{\mathcal{C}}(\tilde{y}),\mathcal{R}^{*}\rangle$

    2. 2.

$\tilde{c}^{0}_{1}$ =
$Com_{\boldsymbol{p}_{1}^{0}}\langle\tilde{\mathcal{C}}(\tilde{y}),\mathcal{R}^{*}\rangle$

    3. 3.

$\tilde{c}^{1}_{0}$ =
$Com_{\boldsymbol{p}_{0}^{1}}\langle\tilde{\mathcal{C}}(\tilde{u}),\mathcal{R}^{*}\rangle$

    4. 4.

$\tilde{c}_{1}^{1}$ =
$Com_{\boldsymbol{p}_{1}^{1}}\langle\tilde{\mathcal{C}}(1-\tilde{u}),\mathcal{R}^{*}\rangle$

  * •

If $\tilde{\gamma}=1$, $\tilde{\mathcal{C}}$ commits to:

    1. 1.

$\tilde{c}_{0}^{0}$ =
$Com_{\boldsymbol{p}_{0}^{0}}\langle\tilde{\mathcal{C}}(\tilde{u}),\mathcal{R}^{*}\rangle$

    2. 2.

$\tilde{c}^{0}_{1}$ =
$Com_{\boldsymbol{p}_{1}^{0}}\langle\tilde{\mathcal{C}}(1-\tilde{u}),\mathcal{R}^{*}\rangle$

    3. 3.

$\tilde{c}^{1}_{0}$ =
$Com_{\boldsymbol{p}_{0}^{1}}\langle\tilde{\mathcal{C}}(\tilde{y}),\mathcal{R}^{*}\rangle$

    4. 4.

$\tilde{c}_{1}^{1}$ =
$Com_{\boldsymbol{p}_{1}^{1}}\langle\tilde{\mathcal{C}}(\tilde{y}),\mathcal{R}^{*}\rangle$

  * •

Run commitment phase between $\mathcal{C}$ and $\mathcal{R}^{*}$.

  * •

Measure $\gamma$ in the register A. If $\tilde{\gamma}=\gamma$, the simulator
was successful, output 0. Otherwise, output 1.

4:Let $u=b\oplus e$

5:$\mathcal{Q}_{\mathcal{R}^{*}}$ and $\mathcal{R}^{*}$ decommits to:

  * •

If $\tilde{\gamma}=0$, decommits to the $(u\oplus\tilde{u}+2)^{th}$ committed
bit.

  * •

If $\tilde{\gamma}=1$, decommits to the $(u\oplus\tilde{u})^{th}$ committed
bit.

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

###### Theorem 3.2

If Com is a computationally hiding commitment, then EqCommitment is an
equivocal bit commitment

###### Proof

In order to apply the rewinding lemma, we can consider a communication scheme
as follows.

  * •

$\mathcal{C}$: the committer $\mathcal{C}$ commits and communicates with the
malicious receiver $\mathcal{R}^{*}$ through the polynomial-size register M.

  * •

$\mathcal{R}^{*}$: the malicious receiver has three different registers: W, V
and A. The first one, W, represents the quantum input. The registers V and A
are the work space of $\mathcal{R}^{*}$ and both are initialized in the zero
state. While V is a polynomial-size register, A is a one qubit register.
$\mathcal{R}^{*}$ measures this second register A for sampling
$\gamma\in\\{0,1\\}$. After the honesty check, $\mathcal{R}^{*}$ outputs the
registers (W,V,A,M).

  * •

$\mathcal{Q}_{\mathcal{R}^{*}}$: the quantum simulator works with registers P
and Z in addition to (W,V,A,M). P is a one qubit register for the guess
$\tilde{\gamma}$, and Z is the auxiliary register in which Algorithm 2 is
implemented.

The condition to apply Watrous’ lemma is that the probability for the
simulator to guess the output has to be nearly independent of the probability
distribution of the malicious receiver $\mathcal{R}^{*}$’s choice. This is
guaranteed by the computationally hiding property of the underlying bit
commitment. Then, $\left|p(\psi)-1/2\right|=negl(\lambda)$, for every input
state $\left|\psi\right\rangle$ of $\mathcal{R}^{*}$ in $\mathcal{Q}_{Eq}$.
Due to Lemma 3, there is a poly-size circuit $\mathcal{R}$ that outputs a
state inverse-exponentially close to the final state conditioned to
$\tilde{\gamma}=\gamma$ of the Algorithm 2.

Once the simulator $\mathcal{Q}_{R^{*},com}$ has measured the qubit register P
and obtained $\gamma$, it proceeds to do the honesty check, as described in
Algorithm 2 and outputs the registers (W,V,A,M) after tracing out the
remaining registers.

Algorithm 3 ERE-Commitment: Equivocal and relaxed extractable commitment

Committer $\mathcal{C}$ Input: A sequence of bits $(b_{i})_{i\in[wk]}$.
Assumptions: The parties use a
$PRG:\\{0,1\\}^{\lambda_{PQS}}\rightarrow\\{0,1\\}^{2w\cdot\lambda_{PQS}}$,
2-universal hash functions
$h_{j}(\cdot,\cdot):\\{0,1\\}^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\lambda_{PQS}}$,
an EqCommitment that is equivocal and a statistically binding and
computationally hiding commitment $Com_{r}$ which uses $r$ as the randomness
of the commitment.

1:$\mathcal{C}$ samples $\boldsymbol{x}\leftarrow\\{0,1\\}^{4\lambda_{EX}}$
and $\boldsymbol{\theta}\leftarrow\\{+,\times\\}^{4\lambda_{EX}}$ and sends
$\left|\boldsymbol{x}\right\rangle_{\boldsymbol{\theta}}$ to $\mathcal{R}$.

2:$\mathcal{R}$ chooses his measurement bases
$\boldsymbol{\hat{\theta}}\leftarrow\\{+,\times\\}^{4\lambda_{EX}}$ and
measures $\boldsymbol{\hat{x}}\leftarrow\\{0,1\\}^{4\lambda_{EX}}$.

3:$\mathcal{R}$ commits to
$\left((\hat{x}_{i},\hat{\theta}_{i})\right)_{i\in[4\lambda_{EX}]}$ using
EqCommitment.

4:$\mathcal{C}$ challenges a random subset $E\subset[4\lambda_{EX}]$, such
that $\left|E\right|=2\lambda_{EX}$.

5:$\mathcal{C}$ and $\mathcal{R}$ execute EqDecommitment sequentially for
every $i\in E$. Then, $\mathcal{C}$ obtains
$\left((\hat{x}_{i},\hat{\theta}_{i})\right)_{i\in E}$. $\mathcal{C}$ aborts
if the commitment fails to open.

6:$\mathcal{C}$ checks that $x_{i}=\hat{x}_{i}$ whenever
$\theta_{i}=\hat{\theta}_{i}$, up to a fraction $\alpha$ due to the
experimental error. If the test does not pass, $\mathcal{C}$ aborts.

7:$\mathcal{C}$ randomly samples $2k$ disjoint subsets $M_{j}\subseteq\bar{E}$
of size $m$, with $m$ given by the size of the preimage of a 2-universal hash
function
$\\{h_{j}(\cdot,\cdot):\\{0,1\\}^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\lambda_{PQS}}\\}_{j\in[2k]}$,
where $k=\lfloor\lambda_{EX}/m\rfloor$.

8:For every $j\in[2k]$, $\mathcal{C}$ samples
$\boldsymbol{r}^{j}\in\\{0,1\\}^{n}$ and compute
$\boldsymbol{s}^{j}=h_{j}(\boldsymbol{r}^{j},\tilde{\mathbf{x}}^{j})$ where
$\tilde{\mathbf{x}}^{j}=\\{x_{i}:i\in M_{j}\\}$.

9:Given
$PRG:\\{0,1\\}^{\lambda_{PQS}}\rightarrow\\{0,1\\}^{2w\cdot\lambda_{PQS}}$,
$\mathcal{C}$ generates
$\boldsymbol{p}^{j}=PRG(\boldsymbol{s}^{j})=(\boldsymbol{p}^{j}_{1},...,\boldsymbol{p}^{j}_{2w})$
for every $j\in[2k]$, where
$\boldsymbol{p}^{j}_{i}\in\\{0,1\\}^{\lambda_{PQS}}$.

10:$\mathcal{C}$ sends $(M_{j})_{j\in[2k]}$, $\boldsymbol{\theta}$ and
$(\boldsymbol{r}^{j})_{j\in[2k]}$ to $\mathcal{R}$. $\mathcal{C}$ sends the
syndromes $(Synd_{j})_{j\in 2k}$ to correct a proportion $\alpha$ of errors.

11:$\mathcal{C}$ and $\mathcal{R}$ sequentially execute $k$ sessions of $w$
parallel EqCommitment. For each $r\in[k]$:

  1. 11.1:

$\mathcal{C}$ commits in parallel to $w$ pairs of random bits with
$\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]}=\left(\boldsymbol{p}_{2q-1}^{2r-1},\boldsymbol{p}_{2q}^{2r-1},\boldsymbol{p}_{2q-1}^{2r},\boldsymbol{p}_{2q}^{2r}\right)_{q\in[w]}$
as seeds.

  2. 11.2:

For the honesty check of the EqCommitment, $\mathcal{R}$ samples
$\gamma_{r}\xleftarrow{\$}\\{0,1\\}$ and sends it to $\mathcal{C}$.

  3. 11.3:

$\mathcal{C}$ sends $\tilde{\mathbf{x}}^{j^{r,\gamma_{r}}}$ and
$p^{j^{r,\gamma_{r}}}$ to $\mathcal{R}$. $\mathcal{R}$ checks if,

     * •

$\tilde{x}_{i}=\hat{x}_{i}$ whenever $\tilde{\theta}_{i}=\hat{\theta}_{i}$ up
to an experimental error $\alpha$ and, if not, aborts.

     * •

$PRG(h_{j^{r,\gamma_{r}}}(\tilde{\mathbf{x}}^{j^{r,\gamma_{r}}}))=\boldsymbol{p}^{j^{r,\gamma_{r}}}$
and, if not, aborts.

     * •

$Decom_{\boldsymbol{p}_{i_{q,0}}^{j^{r,\gamma_{r}}}}(c_{i_{q,0}}^{j^{r,\gamma_{r}}})=Decom_{\boldsymbol{p}_{i_{q,1}}^{j^{r,\gamma_{r}}}}(c_{i_{q,1}}^{j^{r,\gamma_{r}}})$
for every $q\in[w]$ and, if not, aborts.

  4. 11.4:

$\mathcal{C}$ commits to each $(b_{i})_{i\in[w]}$ as described in
EqCommitment.

12:When necessary, $\mathcal{C}$ and $\mathcal{R}$ open to any of the
committed bits $(b_{i})_{i\in[wk]}$ by executing EqDecommitment. In order to
do so, $\mathcal{C}$ sends the seeds
$\boldsymbol{p}_{i_{q,\delta}}^{j^{r,\bar{\gamma}}}$ to $\mathcal{R}$.

If a quantum poly-time distinguisher
$\mathcal{D}^{*}=\\{\mathcal{D}^{*}_{\lambda},\sigma_{\lambda}\\}$ could
distinguish $Real_{b}$ and $Ideal_{b}$, it would mean that $\mathcal{D}^{*}$
is able to discriminate the commitments of the simulator $\mathcal{Q}_{R^{*}}$
and the honest committer $\mathcal{C}$. This would imply that the
distinguisher is able to open the committed values which contradicts the
definition of computational hiding of the base commitment scheme. ∎

##  4 Equivocal and relaxed extractable commitment

We construct an equivocal and ($\chi$, $\epsilon$)-relaxed extractable
commitment (Definition 5), named ERE-Commitment, based on an equivocal and
($\eta$, $\epsilon$)-relaxed statistically binding commitment. To achieve
this, we first demonstrate the equivocality and relaxed statistically binding
properties of the ERE-Commitment, and then proceed to prove its relaxed
extractability.

###  4.1 ($\eta$,$2^{-k\eta}$)-relaxed statistical binding of the ERE-
Commitment

###### Theorem 4.1

If $Com$ is a statistically binding commitment scheme, then for any function
$\eta(k)$ ERE-Commitment is $\left(\eta,2^{-k\eta}\right)$-relaxed
statistically binding.

###### Proof

The proof is similar to the one of Theorem 3.1. In ERE-Commitment, the seeds
of the base commitments $Com_{r}$ are used as described in Algorithm 3.
Therefore, when the honesty check is done, the sampled population is not the
number of sequential repetitions of the EqCommitment $wk$ but the number of
different families $k$ since the EqCommitment instances which make use of
seeds derived from the same family $\boldsymbol{p}^{j}$ are opened together.

∎

###  4.2 Equivocality

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

###### Theorem 4.2

If Com is computationally hiding, then ERE-Commitment is an equivocal bit
commitment.

###### Proof

The main difference with respect to the proof for EqCommitment is that the
equivocal simulator has to answer correctly the commitment of $w$ equivocal
boxes in parallel with single challenge bit $\gamma_{r}$. Given a
computationally hiding bit commitment,
$\left|p(\psi)-1/2\right|=negl(\lambda)$ also for this case. Hence, all the
properties of the Algorithm 2 and the application of Watrous’ rewinding lemma
are equivalent for this scheme. Therefore, from computational hiding,
$Real_{b}$ and $Ideal_{b}$ of Def. 2 are indistinguishable. ∎

###### Corollary 1

If $Com_{\boldsymbol{p}^{j}_{i}}$ is implemented using Naor’s bit commitment
with input seeds $\boldsymbol{p}^{j}_{i}\in\\{0,1\\}^{\lambda_{PQS}}$, where
$(\boldsymbol{p}^{j}_{1},...,\boldsymbol{p}^{j}_{2w})=PRG(\boldsymbol{s}^{j})$
for $\boldsymbol{s}^{j}\in\\{0,1\\}^{\lambda_{PQS}}$ , then ERE-Commitment is
an equivocal bit commitment.

###### Proof

We have to prove that the Naor’s bit commitment scheme [Nao91] is
computationally hiding giving the pseudorandom seeds
$\boldsymbol{p}^{j}_{i}\in\\{0,1\\}^{\lambda_{PQS}}$. Naor’s bit commitment is
an interactive bit commitment in which the receiver sends
$k\xleftarrow{\$}\\{0,1\\}^{\lambda^{3}}$ to the committer, which commits to
the bit $b$ by sending $(b\cdot k)\oplus W(r)$, where
$r\xleftarrow{\$}\\{0,1\\}^{\lambda}$ and
$W:\\{0,1\\}^{\lambda}\rightarrow\\{0,1\\}^{\lambda^{3}}$ is a pseudo-random
generator. Thus, the computational hiding property is guaranteed by the
pseudorandomness property of $W$. In this case, the seed
$\boldsymbol{p}^{j}_{i}$ of the Naor’s base commitment is not randomly sampled
by the committer, but obtained as the output of a PRG which input is
$(\boldsymbol{s}^{j})_{j\in[2k]}$. $(\boldsymbol{s}^{j})_{j\in[2k]}$ are
generated by hashing the strings $(\tilde{\boldsymbol{x}}^{j})_{j\in[2k]}$.
Therefore, computational hiding would be fulfilled if the strings
$(\boldsymbol{s}^{j})_{j\in[2k]}$ are random strings. By applying the leftover
hash lemma (Lemma 1), the obtained seeds are arbitrarily close to a random
string, as proven in Theorem 0.A.1 of Appendix 0.A. ∎

###  4.3 Relaxed-extractability

To prove extractability, we will use the equivocality properties of
EqCommitment. To prove that the simulator
$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ defined in Algorithm 4 that represents
the $Ideal$ interaction from Definition 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 instead of performing the honesty
check given by Step 11 of Algorithm 3, it does it as 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.

###### Lemma 4

There exists a negligible function $\nu(\lambda)$, such that:

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{1})=1]-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{0})=1]\right|=\nu(\lambda).$

###### Proof

Suppose that there exists a non-negligible function for which
$\mathcal{D}^{*}$ can distinguish between $\text{Hyb}_{0}$ and
$\text{Hyb}_{1}$. This is equivalent to:

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{0,i-1})=1]-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{0,i})=1]\right|\geq\frac{1}{poly(\lambda)4\lambda},$

where $\text{Hyb}_{0,j}$ is the sub-hybrid that is identical to
$\text{Hyb}_{0}$ until the committed bit $j\in[4\lambda_{EX}]$ and then
identical to $\text{Hyb}_{1}$. Therefore, $\mathcal{D}^{*}$ would be able to
distinguish between the outputs $\rho^{CO}_{final}$ of an honest and an
equivocated commitment, contradicting Definition 2. ∎

Algorithm 4 Extractable simulator

1:$\mathcal{C}^{*}(\rho)$ outputs $\mathbf{\Psi}$

2:For $i\in[4\lambda_{EX}]$, execute the quantum equivocal simulator
$\mathcal{Q}_{\mathcal{R}^{*}}$ to generate a tuple of
$((c^{\bar{\gamma}}_{\delta})^{i}_{\delta=0,1})_{i\in[4\lambda_{EX}]}$ dummy
commitments. After each commitment session,
$(\rho^{\mathcal{S}}_{i},\rho^{y}_{com,i})\mapsfrom\mathcal{Q}_{\mathcal{R}^{*},com}(\rho)$,
where $\rho^{\mathcal{S}}_{i}$ is stored by
$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$, and $\boldsymbol{\rho}^{y}_{com,i}$ is
used by the malicious committer $\mathcal{C}^{*}$ as an input in the next
session.

3:Once $\mathcal{C}^{*}$ has announced the challenged subset
$E\subset[4\lambda_{EX}]$, $\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ samples
$\boldsymbol{\hat{\theta}}\leftarrow\\{+,\times\\}^{2\lambda_{EX}}$.
$\mathcal{Q}_{\mathcal{C}^{*}}$ measures the $i^{th}$ qubit of
$\mathbf{\Psi}$, $\Psi_{i}$, for every $i\in E$ in the previous sampled bases,
obtaining $(\hat{x}_{i})_{i\in[E]}$.

4:By applying the equivocal simulator $\mathcal{Q}_{Eq}$,
$\mathcal{Q}_{\mathcal{C}^{*}}$ opens the challenged bits $z_{i}\in E$ to the
correct values $(\hat{x}_{i},\hat{\theta}_{i})_{i\in[E]}$. To do so, it
executes sequentially for each $i\in[E]$: $\rho^{x}_{final}$ $\mapsfrom$
$\langle\mathcal{Q}_{\mathcal{R}^{*},dec}(\hat{x}_{i},\hat{\theta}_{i},z_{i},\rho^{x}_{com}),\mathcal{C}_{dec}^{*}(\rho^{y}_{com})\rangle$,
where $\rho^{x}_{com}$ is the current state of $\mathcal{C}^{*}$, updated
after each session.

5:If $\mathcal{C}^{*}$ aborts at any point,
$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ outputs $\perp$, otherwise continues.

6:$\mathcal{C}^{*}$ and $\mathcal{R}$ discard the tested positions and both
reorder their respective tuples $((x_{i},\theta_{i}))_{i\in\bar{E}}$ and
$((\hat{x}_{i},\hat{\theta}_{i}))_{i\in\bar{E}}$. $\mathcal{C}^{*}$ sends
$\boldsymbol{\theta}$ , computes the $(\boldsymbol{p}^{j})_{j\in[2k]}$ as
described in Algorithm 3 and sends $(\boldsymbol{r}^{j})_{j\in[2k]}$.

7:$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ measures each qubit
$\mathbf{\psi}_{i}\in\bar{E}$ in the bases $\theta_{i}$ to obtain
$\hat{x}_{i}=x_{i}$. $\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ performs the error
correction on $\hat{\boldsymbol{x}}$ by using the syndrome $Synd$. Then,
$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ computes the seeds
$\left(\left(\hat{\boldsymbol{p}}_{i_{q,0}}^{j^{r,0}},\hat{\boldsymbol{p}}_{i_{q,1}}^{j^{r,0}},\hat{\boldsymbol{p}}_{i_{q,0}}^{j^{r,1}},\hat{\boldsymbol{p}}_{i_{q,1}}^{j^{r,1}}\right)_{q\in[w]}\right)_{r\in[k]}$.

8:$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ executes the honesty check as
described in Step 11 of Algorithm 3.

9:$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ extracts the non challenged
commitments:

  1. 9.1:

$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ checks if
$Decom_{\hat{\boldsymbol{p}}_{i_{q,0}}^{j^{r,\gamma}}}(c_{i_{q,0}}^{j^{r,\gamma}})=Decom_{\hat{\boldsymbol{p}}_{i_{q,1}}^{j^{r,\gamma}}}(c_{i_{q,1}}^{j^{r,\gamma}})$
where $\hat{\boldsymbol{p}}_{i_{q,\delta}}^{j^{r,\gamma}}$ are the ones
obtained in Step 7.

  2. 9.2:

For the positions where this is the case,
$b_{r,q}^{*}=Decom_{\hat{\boldsymbol{p}}_{i_{q,0}}^{j^{r,\gamma}}}(c_{i_{q,0}}^{j^{r,\gamma}}\oplus
e_{r,q})$, otherwise $b^{*}_{r,q}=\mathbbold{\qm}$.

  3. 9.3:

If the proportion of $b^{*}_{i}=\mathbbold{\qm}$ is larger than
$\chi=\eta+\zeta$, with $\eta=\zeta=\log^{2}(k)$,
$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ outputs aborts, where $i=(r-1)*w+q$ are
the reordered indexes.

  4. 9.4:

Otherwise, $\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ outputs
$(\boldsymbol{\rho}^{\mathcal{C}}_{com},\boldsymbol{\rho}^{\mathcal{R}}_{com},\boldsymbol{b}^{*})$,
where $\boldsymbol{b}^{*}\in\\{0,1\\}^{wk}$ is the string of bits in which
$\boldsymbol{b}_{i}^{*}=b_{i}^{*}$ for the positions in which the output was
not $\mathbbold{\qm}$ and an equivocated dummy commitment for the remaining
positions by executing the quantum equivocal simulator $\mathcal{Q}_{Eq}$.
$\boldsymbol{\rho}^{\mathcal{C}}_{com}$ is the resulting state of
$\mathcal{C}^{*}$ and
$\boldsymbol{\rho}^{\mathcal{R}}_{com}=(\boldsymbol{\theta},\boldsymbol{\hat{\theta}},\boldsymbol{\hat{x}})$.

10:$\mathcal{Q}_{\mathcal{C}^{*}}(\rho)$ opens the equivocated commitments
corresponding to $\mathbbold{\qm}$ to the value opened by $\mathcal{C}^{*}$ in
these positions by applying the equivocal simulator $\mathcal{Q}_{Eq}$.

###### Lemma 5

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{2})=1]\equiv\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{1})=1]\right|$.

###### Proof

Since the states corresponding to the subset $E\subset 4\lambda_{EX}$ are also
measured with randomly sampled bases $(\hat{\theta}_{i})_{i\in E}$, the two
experiments have exactly the same output distribution. ∎

###### Lemma 6

There exists a negligible function $\nu(\lambda)$, such that,

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{3})=1]-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{2})=1]\right|=\nu(\lambda).$

###### Proof

A quantum poly-time distinguisher $\mathcal{D}^{*}$ would be able to
discriminate between both distributions if $Hyb_{2}$ and $Hyb_{3}$ had
different probabilities for output $\perp$ during the honesty check. Since the
honesty check is performed in the same way in both Hybrids, they are
indistinguishable. ∎

###### Lemma 7

There exists a negligible function $\nu(\lambda)$ such that:

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{4})=1]-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{3})=1]\right|=\nu(\lambda).$

###### Proof

The only difference between $\text{Hyb}_{3}$ and $\text{Hyb}_{4}$ comes from
the fact that the $Ideal$ distribution, given by $\text{Hyb}_{4}$, outputs
FAIL whenever $b_{i}^{*}\notin\\{\perp,b_{i},\mathbbold{\qm}\\}$ and the
number of $\mathbbold{\qm}$ outputs is larger than the proportion
$\chi\leq\eta+\zeta$, where $\zeta$ is the proportion of commitments seeded in
a dishonest way.

In order to bound the probability of having more than a proportion $\zeta$ of
dishonestly seeded commitments, let us consider again $k$ sequential
repetitions of $w$ parallel EqCommitment protocols, as described in Algorithm
3. For the $r$-th instance, the $q$-th EqCommiment
$\left(c_{i_{q,0}}^{j^{r,0}},c_{i_{q,1}}^{j^{r,0}},c_{i_{q,0}}^{j^{r,1}},c_{i_{q,1}}^{j^{r,1}}\right)$
of the $w$ parallel commitments, uses as seeds
$\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)$.

Each $r\in[k]$ sequential honesty check is composed of a sequence of $w$
EqCommitment that use the seeds
$\boldsymbol{p}^{j^{r,0}}\leftarrow\tilde{\boldsymbol{x}}^{j^{r,0}}$ and
$\boldsymbol{p}^{j^{r,1}}\leftarrow\tilde{\boldsymbol{x}}^{j^{r,1}}$. Let us
define $B_{1}$ as the set of $r$ indexes with at least one dishonestly seeded
commitment
$B_{1}=\\{r:\exists{\gamma,\delta,q}\quad\boldsymbol{p}_{i_{q,\delta}}^{j^{r,\gamma}}\text{is
not the seed of the commitment}\\}$. Let us also define the event $E_{1}$
where the check on Step 11 of Algorithm 3 passes on all $k$ sets. The goal is
now to connect $|B_{1}|$ and $\text{I\kern-1.49994ptP}[E_{1}]$. It can be
shown that:

$\displaystyle\text{I\kern-1.49994ptP}[E_{1}]\leq\frac{1}{2^{|B_{1}|}},$ (4.1)

which is equivalent to the fact that, if
$\text{I\kern-1.49994ptP}[E_{1}]\geq\epsilon=2^{-\zeta k}$, then
$|B_{1}|\leq\zeta k$. The proof of Equation 4.1 holds since, for each $r\in
B_{1}$, there exists one set of indexes $\\{\gamma^{*},\delta^{*},q^{*}\\}$
such that $\boldsymbol{p}_{i_{q^{*},\delta^{*}}}^{j^{r,\gamma^{*}}}$ is not
the seed of the commitment, and in order for $E_{1}$ to be true, the
challenged family of commitments seeded by $\boldsymbol{p}^{j^{r,\gamma}}$ for
the $r$-th set of $w$ EqCommitment instances is different from
$\boldsymbol{p}^{j^{r,\gamma^{*}}}$, which happens with probability
$\frac{1}{2}$. Since all challenges are picked independently, the probability
that

$\text{I\kern-1.49994ptP}[\forall r\in B_{1}:\gamma\neq\gamma^{*}]=\prod_{r\in
B_{1}}\
\text{I\kern-1.49994ptP}[\gamma\neq\gamma^{*}]\leq\frac{1}{2^{|B_{1}|}}.$

$Hyb_{3}$ and $Hyb_{4}$ would be distinguishable if the malicious committer
$\mathcal{C}^{*}$ has committed to $b_{i}$ with an equivocated commitment more
than a proportion $\zeta=\omega(\log^{2}(k)/k)$, or if the malicious committer
$\mathcal{C}^{*}$ uses as seeds $\boldsymbol{p}^{j}\neq
PRG(h(\tilde{\mathbf{x}}^{j}))$ in more than a proportion
$\zeta=\omega(\log^{2}(k)/k)$ of the keys and $\text{Hyb}_{3}$ has not output
$\perp$ in the honesty check phase. This happens with probability:

$\begin{split}\text{I\kern-1.49994ptP}[\text{FAIL}|\text{Ideal}]=&\text{I\kern-1.49994ptP}[\text{
number of non extractable commitments}\geq\eta+\zeta]\\\
&\leq\text{I\kern-1.49994ptP}[\text{ number of non extractable
commitments}\geq\zeta].\end{split}$

Then, $\text{I\kern-1.49994ptP}[\text{FAIL}|\text{Ideal}]<negl(\lambda)$ given
Theorem 4.1. ∎

###### Lemma 8

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{5})=1]\equiv\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\sigma,\text{Hyb}_{4})=1]\right|$.

###### Proof

Similar to the proof of Lemma 4. In the opening phase, since the opened value
is the same as the one opened by the malicious committer $\mathcal{C}^{*}$,
both distributions are indistinguishable. ∎

Thus, ERE-Commitment is equivocal and
($\omega(\log^{2}(k)/k),\epsilon$)-relaxed-extractable in the sense of
Definitions 2 and 5, with $\epsilon=1-negl(k)$.

##  5 OT from equivocal and relaxed-extractable bit commitment

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

Algorithm 5 Oblivious transfer protocol

Alice $A$ Input: Messages $m_{0},m_{1}\in\\{0,1\\}^{\lambda}$.
Bob $B$ Input: Bit $b\in\\{0,1\\}$.
Assumptions: The parties use an ERE-Commitment that is $\chi$-relaxed
extractable and equivocal,
$PRG:\\{0,1\\}^{\lambda_{PQS}}\rightarrow\\{0,1\\}^{w}$ and 2-universal hash
functions
$h_{j}(\cdot,\cdot):\\{0,1\\}^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\lambda_{PQS}}$.

1:$A$ chooses $\boldsymbol{x}\leftarrow\\{0,1\\}^{2\lambda_{OT}}$ and
$\boldsymbol{\theta}\leftarrow\\{+,\times\\}^{2\lambda_{OT}}$ and sends
$\left|x\right\rangle_{\theta}$ to $B$.

2:$B$ samples his measurement bases
$\boldsymbol{\hat{\theta}}\leftarrow\\{+,\times\\}^{2\lambda_{OT}}$ and
measures $\boldsymbol{\hat{x}}\leftarrow\\{0,1\\}^{2\lambda_{OT}}$. $A$ and
$B$ execute ERE-Commitment to commit to
$\left((\hat{x}_{i},\hat{\theta}_{i})\right)_{i\in[2\lambda_{OT}]}$.

3:$A$ challenges a random subset $T\subset[2\lambda_{OT}]$, such that
$\left|T\right|=\lambda_{OT}$.

4:$A$ and $B$ execute ERE-Decommitment sequentially for every $i\in T$. Then,
$A$ obtains $\left((\hat{x}_{i},\hat{\theta}_{i})\right)_{i\in T}$.

5:$A$ checks that $x_{i}=\hat{x}_{i}$ whenever $\theta_{i}=\hat{\theta}_{i}$,
up to an experimental error $\alpha$. If the test does not pass, $A$ aborts.

6:$A$ and $B$ discard the tested positions and both reorder their respective
sequences $\left((x_{i},\theta_{i})\right)_{i\in\bar{T}}$ and
$\left((\hat{x}_{i},\hat{\theta}_{i})\right)_{i\in\bar{T}}$. $A$ sends
$\boldsymbol{\theta}$ to $B$.

7:$B$ partitions the set $\bar{T}$ into two different subsets: the subset in
which both have measured in the same bases
$I_{b}=\\{i:\theta_{i}=\hat{\theta}_{i}\\}$ and the subset in which they have
not measured in the same bases
$I_{\bar{b}}=\\{i:\theta_{i}\neq\hat{\theta}_{i}\\}$. $B$ sends
$(I_{0},I_{1})$ to $A$.

8:$A$ sends the syndromes $Synd_{0}$ and $Synd_{1}$ for correcting a
proportion $\alpha$ of errors of the bit strings $\boldsymbol{x}_{0}$ and
$\boldsymbol{x}_{1}$ to $B$, where $\boldsymbol{x}_{0}=\\{x_{i}:i\in I_{0}\\}$
and $\boldsymbol{x}_{1}=\\{x_{i}:i\in I_{1}\\}$.

9:$A$ samples seeds $s_{0},s_{1}\leftarrow\\{0,1\\}^{k(\lambda_{PQS})}$ and
sends $(s_{0},PRG(h(s_{0},\boldsymbol{x}_{0}))\oplus
m_{0},s_{1},PRG(h(s_{1},\boldsymbol{x}_{1}))\oplus m_{1})$.

10:$B$ performs error correction on $\boldsymbol{x}_{b}$ using the syndrome
$Synd_{b}$ and decrypts $m_{b}$ by using $\hat{\boldsymbol{x}}_{b}$, with
$\hat{\boldsymbol{x}}_{b}=\\{\hat{x}_{i}:i\in I_{b}\\}$.

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 $\mathbf{\mathcal{F}_{OT}}$ works as follows:

  * •

$\mathbf{\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$.

  * •

$\mathbf{\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$.

######  Definition 7 (Secure OT functionality)

A protocol $\langle A(m_{0},m_{1}),B(b)\rangle$ that implements the ideal OT
functionality $\mathcal{F}_{OT}(\cdot,\cdot)$ is said to be simulation-based
secure if it satisfies:

  * •

Security against a malicious Alice. Given the interaction between a quantum
poly-time non-uniform malicious Alice, $A^{*}$, and an honest Bob, their final
state will be $\mathbf{\rho}_{OUT,A^{*}}\langle
A^{*}(m_{0},m_{1}),B(b)\rangle$ and $\text{OUT}_{B}\langle
A^{*}(m_{0},m_{1}),$ $B(b)\rangle$. There exists a simulator
$\text{Sim}_{A^{*}}$ that interacts with the ideal functionality
$\mathcal{F}_{OT}(\cdot,b)$ in the following way. For every non-uniform advice
$\rho,\sigma\in\mathcal{B}_{1}(\mathcal{H})$, where $\rho$ and $\sigma$ may be
entangled, $\text{Sim}_{A^{*}}(\rho)$ sends either $(m_{0},m_{1})$ or $\perp$
to $\mathcal{F}_{OT}(\cdot,b)$ and outputs the final state
$\mathbf{\rho}_{SIM,OUT,A^{*}}$. The output of the ideal functionality to the
Bob is given by $\text{OUT}_{B}$. Then, for any quantum poly-time non-uniform
distinguisher $\mathcal{D}^{*}$:

$\begin{split}&\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\mathbf{\rho}_{SIM,\text{OUT},A^{*}},\text{OUT}_{B}))=1]\right.\\\
&\left.-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\mathbf{\rho}_{\text{OUT},A^{*}}\langle
A^{*}(m_{0},m_{1}),B(b)\rangle,\text{OUT}_{B}\langle
A^{*}(m_{0},m_{1}),B(b)\rangle))=1]\right|\\\
&=\text{negl}(\lambda)\end{split}$ (5.1)

  * •

Security against a malicious Bob. Given the interaction between an honest
Alice and a quantum poly-time non-uniform malicious Bob, $B^{*}$, their final
state will be $\text{OUT}_{A}\langle A(m_{0},m_{1}),B^{*}(b)\rangle$ and
$\mathbf{\rho}_{OUT,B^{*}}\langle A(m_{0},m_{1}),B^{*}(b)\rangle$. There
exists a simulator $\text{Sim}_{B^{*}}$ that interacts with the ideal
functionality $\mathcal{F}_{OT}((m_{0},m_{1}),\cdot)$ in the following way.
For every non-uniform advice $\rho,\sigma\in\mathcal{B}_{1}(\mathcal{H})$,
where $\rho$ and $\sigma$ may be entangled, $\text{Sim}_{B^{*}}(\rho)$ sends
either $b\in\\{0,1\\}$ or $\perp$ to $\mathcal{F}_{OT}((m_{0},m_{1}),\cdot)$
and outputs the final state $\mathbf{\rho}_{SIM,OUT,B^{*}}$. The output of the
ideal functionality to Bob is given by $\text{OUT}_{A}$. Then, for any quantum
poly-time non-uniform distinguisher $\mathcal{D}^{*}$:

$\begin{split}&\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\text{OUT}_{A},\mathbf{\rho}_{SIM,\text{OUT},B^{*}})=1]\right.\\\
&\left.-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\text{OUT}_{A}\langle
A(m_{0},m_{1}),B^{*}(b)\rangle),\mathbf{\rho}_{\text{OUT},B^{*}}\langle
A(m_{0},m_{1}),B^{*}(b)\rangle)=1]\right|\\\
&=\text{negl}(\lambda).\end{split}$ (5.2)

###  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 Definition 7. To prove that Eq. 5.1 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.

Algorithm 6 Simulator $\text{Sim}_{A^{*}}$

1:$A^{*}(\mathbf{\rho})$ outputs the message $\mathbf{\Psi}$.

2:$\text{Sim}_{A^{*}}$ executes $2\lambda_{OT}$ sessions of ERE-Commitment to
commit to dummy values by executing the equivocal simulator
$\mathcal{Q}_{\mathcal{R}^{*}}$.

3:$\text{Sim}_{A^{*}}$ obtains the challenged set $T\subset 2\lambda_{OT}$
output by $A^{*}$.

4:$\text{Sim}_{A^{*}}$ samples
$\boldsymbol{\hat{\theta}}\leftarrow\\{+,\times\\}^{\lambda_{OT}}$.
$\text{Sim}_{A^{*}}$ measures the $i^{th}$ qubit of $\mathbf{\Psi}$,
$\Psi_{i}$, for every $i\in T$ in the previous sampled bases, obtaining
$\\{\hat{x}\\}_{i\in[T]}$. By applying Watrous’ rewinding,
$\text{Sim}_{A^{*}}$ opens the challenged bits to the correct values
$\\{\hat{x}_{i},\hat{\theta}_{i}\\}_{i\in[T]}$.

5:$\text{Sim}_{A^{*}}$ discards the tested positions. $A$ sends
$\boldsymbol{\theta}$ to $B$. $\text{Sim}_{A^{*}}$ obtains $\theta$ and
measures each of the qubits $\mathbf{\psi}_{i}\in\bar{T}$ in the bases
$\theta_{i}$ to obtain $\hat{x_{i}}=x_{i}$.

6:$\text{Sim}_{A^{*}}$ partitions the set $\bar{T}$ into two different
subsets, by randomly sampling a bit $d_{i}\in\\{0,1\\}$ for each
$i\in\bar{T}$, to create the sequences $I_{0}=\\{i:d_{i}=0\\}$ and
$I_{1}=\\{i:d_{i}=1\\}$. $\text{Sim}_{A^{*}}$ sends $(I_{0},I_{1})$ to
$A^{*}$.

7:$\text{Sim}_{A^{*}}$ obtains $(s_{0},PRG(h(s_{0},\boldsymbol{x}_{0}))\oplus
m_{0},s_{1},PRG(h(s_{1},\boldsymbol{x}_{1}))\oplus m_{1})$, and computes
$m_{0}$ and $m_{1}$.

8:If $A^{*}$ aborts at any point, $\text{Sim}_{A^{*}}$ sends $\perp$ to
$\mathcal{F}_{OT}(\cdot,b)$. Otherwise, it sends $(m_{0},m_{1})$ to
$\mathcal{F}_{OT}(\cdot,b)$. The output is the final state of $A^{*}$.

###### Lemma 9

There exists a negligible function $\nu(\lambda)$, such that:

$\begin{split}&\Big{|}\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},\text{Hyb}_{1})=1]-\\\
&\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\mathbf{\rho}_{\text{OUT},A^{*}}\langle
A^{*}(\mathbf{\rho}),B(b)\rangle,\text{OUT}_{B}\langle
A^{*}(\mathbf{\rho}),B(b)\rangle))=1]\Big{|}=\nu(\lambda).\end{split}$

###### Proof

It follows from the equivocality property of ERE-Commitment.∎

###### Lemma 10

$\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},\text{Hyb}_{1})=1]\equiv\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\mathbf{\rho}_{SIM,\text{OUT},A^{*}},\text{OUT}_{B}))=1]$.

###### Proof

It follows from the fact that the delay in the measurement of $\psi_{i}$ with
$i\in T$ cannot be noticed by $A^{*}$ since, in both cases, the measurement
bases are sampled at random, similar to Lemma 5. ∎

###  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 Lemma 11. Then, we prove the security of the
protocol in Theorem 5.1.

######  Lemma 11 (Distance bound for a malicious Bob in QOT)

Consider a QOT protocol between an honest Alice and a malicious Bob (Algorithm
5) with ERE-Commitment as the bit commitment subprotocol (Algorithm 3). Let
$b\in\\{0,1\\}$ be a random bit and
$K_{b}=h(r,\boldsymbol{x}_{I_{b}})\in\\{0,1\\}^{\ell}$ and
$K_{\bar{b}}=h(r,\boldsymbol{x}_{I_{\bar{b}}})\in\\{0,1\\}^{\ell}$, the keys.
$h(r,x):\\{0,1\\}^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\ell}$ is a
2-universal hash function, and $I_{0}$ and $I_{1}$ are the two subsets in
which $\bar{T}\subset[2\lambda_{OT}]$ the unchallenged commitments are
divided. Then, given $K_{b}$, for any sampling errors $\xi,\delta>0$ and an
experimental error $\alpha\geq 0$:

$\begin{split}&\Delta(\rho_{K_{\bar{b}}K_{b}E},\frac{1}{2^{\ell}}\text{I}\otimes\rho_{K_{b}E})\\\
&\leq\frac{1}{2}\cdot 2^{-\frac{1}{2}[(\frac{1}{2}-\xi-
h_{2}(\delta+\alpha+\chi))\lambda_{OT}/2-\ell-q]}\\\
&+\sqrt{6}\exp(-\lambda_{OT}\delta^{2}/100)+2\exp(-\xi^{2}\lambda_{OT}/2),\end{split}$
(5.3)

where $E$ denotes Bob’s quantum state, $k$, the number of different seed
families as described in Algorithm 3 and $q$, the length of the syndrome
needed for performing the error correction code.
$\text{I}\in\mathcal{B}(\mathbb{C}^{2^{\ell}})$ is the identity operator.

###### Proof

The opening and checking process, which is based on sampling, follows a
structure akin to the proof provided in [BF12]. Interested readers can refer
to it for a detailed analysis of the proof. This proof is done in the EPR
setting in which Alice distributes half of an EPR pair to Bob in order for her
to perform the sampling. Since Bob’s and Alice’s actions are equivalent in
both settings, it suffices to prove the bound in the EPR setting. As the
measurement bases are chosen randomly by Alice and Bob, the sampling strategy
will be performed on a random subset $S\subseteq T$ defined as $S=\\{i\in
T:\theta_{i}=\hat{\theta}_{i}\\}$. Alice will accept the opening phase of the
bit commitment if
$w(\boldsymbol{x}|_{S},\boldsymbol{\hat{x}}|_{S})\leq\alpha$, where
$w(\cdot)=d_{H}(\cdot)/n$, with $n\in\mathbb{N}$ being the length of the bit-
string.

Once the testing phase is accepted, the joint state
$\left|\psi_{A_{\bar{T}}E}\right\rangle$ will be a superposition of states
with relative Hamming weight $\delta$ close to $\alpha$ within $A_{\bar{T}}$
due to the statistical error of the sampling. This error given by the sampling
strategy will be bounded by Hoeffding’s bound:

$\epsilon^{\delta}\leq\sqrt{6}\exp(-\lambda_{OT}\delta^{2}/100).$

This bound is obtained in Appendix B.4 of [BF12]. Assuming that Alice chooses
her bases following a uniform random distribution and for
$\boldsymbol{\theta}|_{\bar{T}}$ representing the subsets of bases that were
not challenged,
$d_{H}(\boldsymbol{\theta}|_{\bar{T}},\boldsymbol{\hat{\theta}}|_{\bar{T}})\geq(1/2-\gamma)|\bar{T}|=(1/2-\gamma)\lambda_{OT}$
with Hoeffding’s bound:

$\epsilon^{\gamma}\leq 2\exp(-2\gamma^{2}\lambda_{OT}).$

After the commitment and check subprotocols, the next step in the QOT protocol
is when Alice sends the bases $\boldsymbol{\theta}|_{\bar{T}}$ to Bob, and Bob
partitions $\bar{T}$ into two sets, $I_{0}$ and $I_{1}$. There exists a bit
$b\in\\{0,1\\}$ such that
$d_{H}(\boldsymbol{\theta}|_{I{\bar{b}}},\boldsymbol{\hat{\theta}}|_{I{\bar{b}}})\geq(1/2-\epsilon)\lambda_{OT}/2$,
regardless of how Bob splits the sets of indexes. By applying Equation 2.1 to
our state $\rho_{X_{\bar{b}}A^{b}E}$, itself obtained from measuring the
subsystem $A^{\bar{b}}$ on $\left|\psi_{A^{\bar{b}}A^{b}E}\right\rangle$,
privacy amplification gives, for $\xi=2\gamma$:

$\begin{split}H_{\text{min}}(X_{\bar{b}}|A^{b}E)\geq&d_{H}(\boldsymbol{\theta}|_{I{\bar{b}}},\boldsymbol{\hat{\theta}}|_{I{\bar{b}}})-h_{2}(\delta+\alpha+\eta+\zeta)|I_{\bar{b}}|\\\
&\geq\left(\frac{1}{2}-\xi-
h_{2}(\delta+\alpha+\chi)\right)\frac{\lambda_{OT}}{2}.\end{split}$

Given a $(\chi,\epsilon)$-relaxed extractable ERE-Commitment, with
$\chi=\eta+\zeta=\omega(\log^{2}(k)/k)$, ERE-Commitment is relaxed extractable
with probability $\epsilon=1-negl(k)$. ∎

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.

Algorithm 7 Simulator $\text{Sim}_{B^{*}}$

1:$\text{Sim}_{B^{*}}$ chooses
$\boldsymbol{x}\leftarrow\\{0,1\\}^{2\lambda_{OT}}$ and
$\boldsymbol{\theta}\leftarrow\\{+,\times\\}^{2\lambda_{OT}}$ and sends
$\left|\boldsymbol{x}\right\rangle_{\boldsymbol{\theta}}$ to $B$.

2:$B$ and $\text{Sim}_{B^{*}}$ execute $2\lambda_{OT}$ sessions of ERE-
Commitment. Then, $\text{Sim}_{B^{*}}$ extracts the committed values
$\left(\hat{\theta}_{i},\hat{x}_{i}\right)_{i\in[2\lambda_{OT}]}$ by applying
the extractable simulator given by Algorithm 4 and aborts if the number of
extracted commitments equal to $\mathbbold{\qm}$ are larger than
$\chi=\eta+\zeta$.

3:$\text{Sim}_{B^{*}}$ challenges a random subset $T\subset 2\lambda_{OT}$,
such that $\left|T\right|=\lambda_{OT}$.

4:$\text{Sim}_{B^{*}}$ and $B$ execute ERE-Decommitment sequentially for every
$i\in T$. Then, $\text{Sim}_{B^{*}}$ obtains the set
$\left((\hat{x}_{i},\hat{\theta}_{i})\right)_{i\in T}$ and checks that
$x_{i}=\hat{x}_{i}$ whenever $\theta_{i}=\hat{\theta}_{i}$, up to an
experimental error $\alpha$. If the test does not pass, $\text{Sim}_{B^{*}}$
aborts.

5:$\text{Sim}_{B^{*}}$ discards the tested positions and sends
$\boldsymbol{\theta}$ to $B^{*}$.

6:$\text{Sim}_{B^{*}}$ obtains $I_{0}$ and $I_{1}$. Let $S$ be the sequence of
indices in $I_{0}$ such that $\theta_{i}\neq\hat{\theta}_{i}$. If
$\left|S\right|\geq\left(1/2-\xi\right)\lambda_{OT}/2$ set $b=1$, otherwise
set $b=0$.

7:$\text{Sim}_{B^{*}}$ obtains $m_{b}$ from $\mathcal{F}_{OT}$ and sets
$m_{\bar{b}}=0$.

8:$\text{Sim}_{B^{*}}$ samples seeds
$s_{0},s_{1}\leftarrow\\{0,1\\}^{k(\lambda_{PQS})}$ and sends
$(s_{0},PRG(h(s_{0},\boldsymbol{x}_{0}))\oplus
m_{0},s_{1},PRG(h(s_{1},\boldsymbol{x}_{1}))\oplus m_{1})$, where
$\boldsymbol{x}_{0}=\\{x_{i}:i\in I_{0}\\}$ and
$\boldsymbol{x}_{1}=\\{x_{i}:i\in I_{1}\\}$. $\text{Sim}_{B^{*}}$ outputs the
final state of $R^{*}$.

###### Theorem 5.1

There exists a negligible function $\nu(\lambda)$, such that,

$\displaystyle\Big{|}\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},\text{Hyb}_{1})=1]$
$\displaystyle-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\text{OUT}_{A}\langle
A(m_{0},m_{1}),B^{*}(b)\rangle),\mathbf{\rho}_{\text{OUT},B^{*}}\langle
A(m_{0},m_{1}),B^{*}(b)\rangle)=1]\Big{|}=\nu(\lambda)$

###### Proof

It follows from the $(\omega(\log^{2}(k)/k)),negl(k))$-relaxed-extractability
definition of the bit commitment. ∎

###### Lemma 12

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},\text{Hyb}_{1})=1]-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\text{OUT}_{A},\mathbf{\rho}_{SIM,\text{OUT},B^{*}})=1]\right|=\nu(\lambda)$.

###### Proof

This can be proven by contradiction. Suppose that there exists a distinguisher
such that:

$\left|\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},\text{Hyb}_{1})=1]-\text{I\kern-1.49994ptP}[\mathcal{D}^{*}(\mathbf{\sigma},(\text{OUT}_{A},\mathbf{\rho}_{SIM,\text{OUT},B^{*}})=1]\right|\geq\frac{1}{poly(\lambda)}.$

This would mean that there is a non-uniform quantum poly-time distinguisher
$\mathcal{D}^{*}$ that can distinguish between the messages $m_{\bar{b}}$
obtained in $\text{Hyb}_{1}$ and $m_{\bar{b}}$ obtained in $\text{Hyb}_{2}$.
Since $m_{\bar{b}}$ is encoded as $PRG(h(s_{\bar{b}},x_{\bar{b}}))\oplus
m_{\bar{b}}$, this would be equivalent to distinguishing between the seeds
$h(s_{\bar{b}},x_{\bar{b}})$ of $\text{Hyb}_{1}$ and $\text{Hyb}_{2}$. This
leads to a contradiction since $h(s_{\bar{b}},x_{\bar{b}})$ is statistically
close to a random string due to privacy amplification, as proven in Lemma 11.
∎

###### Corollary 2

Given one implementation of the QOT protocol described in Algorithm 5 with the
quantum distributed key $\boldsymbol{x}\in\\{0,1\\}^{2\lambda_{OT}}$, a
quantity $n_{OT}$ of 1-out-of-2 oblivious transfers can be distilled, where
$n_{OT}=\lfloor\lambda_{OT}/v\rfloor$ and where $v$ is the size of the
preimage of a hash function such that
$h(r,x):\\{0,1\\}^{m(\lambda_{PQS})}\times\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{\lambda_{PQS}}$.
The parameter $v$ is determined in such a way that:

$\begin{split}&\Delta(\rho_{K_{\bar{b}}K_{b}E},\frac{1}{2^{\ell}}\text{I}\otimes\rho_{K_{b}E})\\\
&\leq\frac{1}{2}\cdot 2^{-\frac{1}{2}[(\frac{1}{2}-\xi-
h_{2}(\delta+\alpha+\chi)v/2-\ell-q]}+\sqrt{6}\exp(-\lambda_{OT}\delta^{2}/100)+2\exp(-\xi^{2}\lambda_{OT}/2),\end{split}$

with $\ell=\lambda_{PQS}$.

###### Proof

The proof is similar to the one in Lemma 11. The sampling requires a large
number of $\hat{x}_{i}$ and $\hat{\theta}_{i}$. On step 7 of Algorithm 5, Bob
can choose subsets of length $v$ of $\hat{\theta}_{i}$ and $\hat{x}_{i}$ to
generate $n_{OT}$ seeds $s_{i}\in\\{0,1\\}^{\lambda_{PQS}}$. By selecting a
large enough $v$, we avoid finite-set sampling errors, leading $\xi$ and
$\delta$ to be representative of the whole population as in Theorem 3.2, and
thus:

$H_{\text{min}}(X_{\bar{b}}|A^{b}E)\geq(\frac{1}{2}-\xi-
h_{2}(\delta+\alpha+\chi))\frac{v}{2}.$ (5.4)

In order to obtain $n_{OT}$ 2-out-of-1 OTs, the first difference with respect
to Algorithm 5 is that, in Step 7, Bob chooses the tuple of sets
$(I_{b,j})_{j\in[n_{OT}]}$ and $(I_{\bar{b},j})_{j\in[n_{OT}]}$, such that
$I_{b,j}=\\{i:\theta_{i}=\hat{\theta}_{i}\\}$, $I_{b,j}\cap
I_{b,j^{\prime}}=\varnothing$,
$I_{\bar{b},j}=\\{i:\theta_{i}\neq\hat{\theta}_{i}\\}$ and $I_{\bar{b},j}\cap
I_{\bar{b},j^{\prime}}=\varnothing$. Then B sends
$((I_{0},I_{1})_{j})_{j\in[n_{OT}]}$ to A. The second difference is that, in
Step 8, we define $\mathbf{x}_{0,j}=\\{x_{i}:i\in I_{0,j}\\}$ and
$\mathbf{x}_{1,j}=\\{x_{i}:i\in I_{1,j}\\}$. Alice can then send
$((m_{0},m_{1})_{j})_{j\in[n_{OT}]}$ different encoded messages. For each
encoded message, Alice chooses at random a pair $(I_{0},I_{1})_{j}$ over the
entire tuple $((I_{0},I_{1}))_{j}\\}_{j\in[n_{OT}]}$ and shares it with Bob,
who can decrypt $m$ messages $m_{b}$ by using the strings
$(\hat{\mathbf{x}}_{b,j})_{j\in[n_{OT}]}$ with
$\hat{\mathbf{x}}_{b,j}=\\{\hat{x}_{i}:i\in I_{b,j}\\}$. ∎

##  6 Acknowledgements

ED, ABG and AY are supported by the European Union’s Horizon Europe Framework
Programme under the Marie Sklodowska 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.

## References

  * [AAB+23] Costantino Agnesi, Marco Avesani, Federico Berra, Luca Calderaro, Sebastiano Cocchi, Giulio Foletto, Davide Scalcon, Andrea Stanco, Giuseppe Vallone, and Paolo Villoresi.  A versatile and low-error polarization encoder for quantum communications.  In Quantum 2.0, pages QTu3A–25. Optica Publishing Group, 2023.
  * [AQY22] P. Ananth, L. Qian, and H. Yuen.  Cryptography from pseudorandom quantum states.  In Y. Dodis and T. Shrimpton, editors, Advances in Cryptology–CRYPTO 2022, Lecture Notes in Computer Science, pages 208–236, Cham, 2022. Springer Nature Switzerland.
  * [BB84] C. H. Bennett and G. Brassard.  Quantum cryptography: Public key distribution and coin tossing.  Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, pages 175–179, 1984.
  * [BBCS92] Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Maria H. Skubiszewska.  Practical quantum oblivious transfer.  In Joan Feigenbaum, editor, Advances in Cryptology — CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 351–366, Berlin, Heidelberg, 1992. Springer.
  * [BCKM21] James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma.  One-way functions imply secure computation in a quantum world.  In Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I 41, pages 467–496. Springer, 2021.
  * [BF12] Niek J. Bouman and Serge Fehr.  Sampling in a quantum population, and applications, 2012.
  * [CK88] Claude Crépeau and Joe Kilian.  Weakening security assumptions and oblivious transfer (abstract).  In Advances in Cryptology - CRYPTO ’88, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings, volume 403 of Lecture Notes in Computer Science, pages 2–7. Springer, 1988.
  * [DFL+09] Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner.  Improving the security of quantum protocols via commit-and-open.  In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, page 408–427, Heidelberg, August 2009. Springer.
  * [GBR+23] Fadri Grünenfelder, Alberto Boaron, Giovanni V Resta, Matthieu Perrenoud, Davide Rusca, Claudio Barreiro, Raphaël Houlmann, Rebecka Sax, Lorenzo Stasi, Sylvain El-Khoury, et al.  Fast single-photon detectors and real-time key distillation enable high secret-key-rate quantum key distribution systems.  Nature Photonics, 17(5):422–426, 2023.
  * [GLSV21] Alex B Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan.  Oblivious transfer is in miniqcrypt.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 531–561. Springer, 2021.
  * [IPS08] Yuval Ishai, Manoj Prabhakaran, and Amit Sahai.  Founding cryptography on oblivious transfer–efficiently.  In Advances in Cryptology–CRYPTO 2008: 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008\. Proceedings 28, pages 572–591. Springer, 2008.
  * [IR90] Russell Impagliazzo and Steven Rudich.  Limits on the provable consequences of one-way permutations.  In Shafi Goldwasser, editor, Advances in Cryptology — CRYPTO’ 88, pages 8–26, New York, NY, 1990. Springer New York.
  * [Kil88] Joe Kilian.  Founding cryptography on oblivious transfer.  In 20th ACM STOC, pages 20–31. ACM Press, May 1988.
  * [LC97] Hoi-Kwong Lo and Hoi Fung Chau.  Is quantum bit commitment really possible?  Physical Review Letters, 1997.
  * [May97] Dominic Mayers.  Unconditionally secure quantum bit commitment is impossible.  Physical review letters, 1997.
  * [MY22] Tomoyuki Morimae and Takashi Yamakawa.  Quantum Commitments and Signatures Without One-Way Functions, page 269–295.  Springer Nature Switzerland, 2022.
  * [Nao91] Moni Naor.  Bit commitment using pseudorandomness.  Journal of cryptology, 4(2):151–158, 1991.
  * [PSC+23] Yoann Pelet, Grégory Sauder, Mathis Cohen, Laurent Labonté, Olivier Alibart, Anthony Martin, and Sébastien Tanzilli.  Operational entanglement-based quantum key distribution over 50 km of field-deployed optical fibers.  Physical Review Applied, 20(4):044006, 2023.
  * [Ren08] Renato Renner.  Security of quantum key distribution.  International Journal of Quantum Information, 6(01):1–127, 2008\.
  * [Wat06] John Watrous.  Zero-knowledge against quantum attacks.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, pages 296–305, 2006.
  * [ZMM+24] Mujtaba Zahidy, Mikkel T Mikkelsen, Ronny Müller, Beatrice Da Lio, Martin Krehbiel, Ying Wang, Nikolai Bart, Andreas D Wieck, Arne Ludwig, Michael Galili, et al.  Quantum key distribution using deterministic single-photon sources over a field-installed fibre link.  npj Quantum Information, 10(1):2, 2024.

##  Appendix 0.A 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 Corollary 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}$.

######  Theorem 0.A.1 (Distance bound in ERE-Commitment for a malicious
receiver)

Consider ERE-Commitment (see Algorithm 3), between an honest sender and a
malicious receiver with a computationally hiding and ($\eta$, $2^{-\eta
n}$)-relaxed statistically binding EqCommitment as base commitment. Let
$K\coloneqq g(r,\boldsymbol{x})$ be the key in $\\{0,1\\}^{\ell}$ output by
Alice, where
$h(r,x):\\{0,1\\}^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\ell}$ is a
universal hash function, and $\bar{T}\subset[4\lambda_{EX}]$, the set of
commitments that have not been challenged. Moreover, $m\in\bar{T}$ is a
randomly chosen subset of non-challenged commitments that are input in the
hash function. Then, for any sampling error $\xi,\delta>0$ and an experimental
error $\alpha\geq 0$,

$\begin{split}&\Delta(\rho_{KE},\frac{1}{2^{\ell}}\text{I}\otimes\rho_{E})\leq\\\
&\leq\frac{1}{2}\cdot 2^{-\frac{1}{2}[(\frac{1}{2}-\xi-
h_{2}(\delta+\alpha+\eta))m-\ell-q]}+\sqrt{6}\exp(-2\lambda_{EX}\delta^{2}/100)+2\exp(-4\xi^{2}\lambda_{EX}),\end{split}$
(0.A.1)

where $E$ denotes Bob’s quantum state, $q$ the length of the syndrome needed
for performing the error correction code and
$\text{I}\in\mathcal{B}(\mathbb{C}^{2^{\ell}})$ is the identity operator.

###### Proof

Since the sampling strategy is the same as the one of the OT layer, the
sampling errors will be the same. The main difference is that, for this layer,
the set of not challenged commitments $\bar{T}\subset[2\lambda_{EX}]$ is not
divided into two different subsets. Therefore, the malicious Bob has less
prior information:

$H_{\text{min}}(X|E)\geq
d_{H}(\boldsymbol{\theta}|_{\bar{T}},\boldsymbol{\hat{\theta}}|_{\bar{T}})-h_{2}(\delta+\alpha+\eta)|{\bar{T}}|\geq\left(\frac{1}{2}-\xi-
h_{2}(\delta+\alpha+\eta)\right)2\lambda_{EX}.$ (0.A.2)

As the subset $m\in{\bar{T}}$ is randomly chosen from the set ${\bar{T}}$, the
sampling error for the bases and the states will be the same ones as for the
set ${\bar{T}}$ for a large enough $m$. Therefore, its min-entropy will be:

$H_{\text{min}}(X_{m}|E)\geq\left(\frac{1}{2}-\xi-
h_{2}(\delta+\alpha+\eta)\right)m.$ (0.A.3)

Given a $(\eta,2^{-k\eta})$-relaxed statistical binding EqCommitment, the
probability of being relaxed statistical binding is $1-negl(k)$ when
$\eta=\omega(\log^{2}(k)/k)$

∎