Robust Combiners and Universal Constructions for Quantum Cryptography

Ji, Liu, and Song [JLS18] introduce a notion of PRSGs, and show that it can be constructed from OWFs. Morimae and Yamakawa [MY22b] introduce the notion of OWSGs, and show how to construct them from PRSGs. In the first definition of OWSGs, the output quantum states are restricted to pure states, and its definition is generalized to mixed states by [MY22a]. In this work, we focus on the mixed-state version.

Bennett and Brassard [BB84] initiate the study of quantum bit commitment. Unfortunately, it turns out that statistically secure quantum bit commitments are impossible to achieve [LC97, May97]. Therefore, later works study a quantum bit commitment with computational security [DMS00, CLS01, Yan22, MY22b, MY22a, AQY22, AGQY22, BCQ23, HMY23]. It was shown that quantum bit commitments can be constructed from PRSGs by [MY22b, AQY22], and that quantum bit commitments are equivalent to EFI, oblivious transfer, and multi-party computation [GLSV21, BCKM21, Yan22, BCQ23].

Recently, Khurana and Tomer [KT23] showed that quantum bit commitments can be constructed from OWSGs with pure state. Although their main result is not a combiner for quantum bit commitment, they construct some sort of a combiner for quantum bit commitments as an intermediate tool for achieving their result. In their construction, they construct a uniform quantum bit commitment from a non-uniform one. At this step, they combine quantum bit commitments in the following sense. In their construction, they combine $(n+1)$-quantum bit commitments and generate a new quantum bit commitment. Its hiding and binding property holds as long as one of the original candidates satisfies hiding and binding at the same time and other $n$ candidates also satisfy either hiding or binding. Compared to their technique, our robust combiner does not need to assume other $n$ candidates satisfy hiding or binding. Therefore, our robust combiner can be applied in a more general setting than their technique. Though our construction partially shares a similarity with theirs, we rely on additional ideas to deal with candidate schemes that do not satisfy either binding or hiding.

Broadbent and Lord [BL20] introduced a notion of unclonable encryption. They considered two security definitions for unclonable encryption. One is one-wayness against cloning attacks and they achieve information-theoretic one-wayness by using BB84 states. The other is indistinguishability against cloning attacks (indistinguishable-secure unclonable encryption). However, they did not achieve it. They constructed indistinguishable-secure unclonable encryption only in a very restricted model by using PRFs. Ananth, Kaleoglu, Li, Liu, and Zhandry [AKL⁺22] proposed the first indistinguishable-secure unclonable encryption in the QROM. Ananth and Kaleoglu [AK21] construct unclonable PKE from unclonable encryption and PKE with “classical” ciphertexts. Note that it is unclear how to apply their technique for PKE with quantum ciphertexts. The technique of [HMNY21] can be used to construct unclonable PKE from unclonable encryption and PKE with quantum ciphertexts, which we use in this work.

It is known that robust combiners are known to exist for many fundamental classical cryptographic primitives. Oblivious transfer (OT) is an example of exceptions. It is an open problem how to construct a robust combiner for classical OT and some black-box impossibilities are known [HKN⁺05]. Interestingly, our result implies that a robust combiner for quantum OT exists although a robust combiner for classical OT is still an open problem.

OWSG is a quantum generalization of OWFs and consists of a tuple of quantum polynomial-time algorithms $\Sigma_{\mathsf{OWSG}}\coloneqq(\mathsf{KeyGen},\mathsf{StateGen},\mathsf{Vrfy})$. The $\mathsf{KeyGen}$ algorithm takes as input a security parameter $1^{\lambda}$, and generates a classical key $k$, the $\mathsf{StateGen}$ algorithm takes as input a classical key $k$ and outputs a quantum state $\psi_{k}$, and the $\mathsf{Vrfy}$ algorithm takes as input a classical key $k$ and a quantum state $\psi_{k}$ and outputs $1$ indicating acceptance or $0$ indicating rejection. We require that OWSG $\Sigma$ satisfies correctness and security. The correctness guarantees that $\mathsf{Vrfy}(k,\psi_{k})$ outputs $1$ indicating acceptance with overwhelming probability, where $k\leftarrow\mathsf{KeyGen}(1^{\lambda})$ and $\psi_{k}\leftarrow\mathsf{StateGen}(k)$. The security guarantees that no QPT adversaries given polynomially many copies of $\psi_{k}$ cannot generate $k^{*}$ such that $1\leftarrow\mathsf{Vrfy}(k^{*},\psi_{k})$, where $k\leftarrow\mathsf{KeyGen}(1^{\lambda})$ and $\psi_{k}\leftarrow\mathsf{StateGen}(k)$.

First, we consider the simpler case, where given OWSG candidates $\Sigma_{\mathsf{OWSG}}[1]=(\mathsf{KeyGen}[1],\allowbreak\mathsf{StateGen}[1],\mathsf{Vrfy}[1])$ and $\Sigma_{\mathsf{OWSG}}[2]=(\mathsf{KeyGen}[2],\mathsf{StateGen}[2],\mathsf{Vrfy}[2])$ are promised to satisfy at least correctness. In this case, we can construct a combiner for OWSGs in the same way as OWFs. Namely, a combined protocol $\mathsf{Comb}.\Sigma_{\mathsf{OWSG}}=(\mathsf{KeyGen},\mathsf{StateGen},\mathsf{Vrfy})$ simply runs $\Sigma[1]$ and $\Sigma[2]$ in parallel.

Does the same strategy work for the general setting, where original candidates are not promised to satisfy correctness? Unfortunately, the simple parallel protocol works only when both $\Sigma_{\mathsf{OWSG}}[1]$ and $\Sigma_{\mathsf{OWSG}}[2]$ satisfy correctness because $\mathsf{Comb}.\Sigma_{\mathsf{OWSG}}$ does not satisfy correctness otherwise. We observe that given an OWSG candidate $\Sigma_{\mathsf{OWSG}}$, we can construct $\Sigma_{\mathsf{OWSG}}^{*}$ with the following properties:

• •

  $\Sigma_{\mathsf{OWSG}}^{*}$ satisfies correctness regardless of $\Sigma_{\mathsf{OWSG}}$.

• •

  $\Sigma_{\mathsf{OWSG}}^{*}$ satisfies security as long as $\Sigma_{\mathsf{OWSG}}$ satisfies correctness and security.

Once we have obtained such a transformation, we can construct a robust OWSG combiner $\mathsf{RobComb}.\mathcal{M}_{\mathsf{OWSG}}$ as follows. Given two OWSGs candidates $\Sigma_{\mathsf{OWSG}}[1]$ and $\Sigma_{\mathsf{OWSG}}[2]$, our robust OWSG combiner $\mathsf{RobComb}.\mathcal{M}_{\mathsf{OWSG}}$ first transforms them into $\Sigma_{\mathsf{OWSG}}[1]^{*}$ and $\Sigma_{\mathsf{OWSG}}[2]^{*}$, respectively, and then outputs $\mathsf{Comb}.\Sigma_{\mathsf{OWSG}}$ which runs $\Sigma_{\mathsf{OWSG}}[1]^{*}$ and $\Sigma_{\mathsf{OWSG}}[2]^{*}$ in parallel. $\mathsf{Comb}.\Sigma_{\mathsf{OWSG}}$ satisfies correctness because $\Sigma_{\mathsf{OWSG}}[1]^{*}$ and $\Sigma_{\mathsf{OWSG}}[2]^{*}$ satisfies correctness no matter what $\Sigma_{\mathsf{OWSG}}[1]$ and $\Sigma_{\mathsf{OWSG}}[2]$ are. $\mathsf{Comb}.\Sigma_{\mathsf{OWSG}}$ satisfies security as long as either $\Sigma_{\mathsf{OWSG}}[1]$ or $\Sigma_{\mathsf{OWSG}}[2]$ satisfy correctness and security because either $\Sigma_{\mathsf{OWSG}}[1]^{*}$ or $\Sigma_{\mathsf{OWSG}}[2]^{*}$ satisfies security as long as either $\Sigma_{\mathsf{OWSG}}[1]$ or $\Sigma_{\mathsf{OWSG}}[2]$ satisfies correctness and security.

Now, we consider how to obtain such a transformation. In the previous work [HKN⁺05], it was shown that we can transform PKE $\Sigma_{\mathsf{PKE}}$ into $\Sigma_{\mathsf{PKE}}^{*}$ that satisfies correctness regardless of $\Sigma_{\mathsf{PKE}}$ and satisfies security as long as $\Sigma_{\mathsf{PKE}}$ satisfies correctness and security. In the same way as [HKN⁺05], we can obtain such transformation for OWSGs. However, in this work, we take a different approach because the technique by [HKN⁺05] does not work for unclonable encryption ³³3The technique we introduce here cannot be applied to public-key quantum money. For public-key quantum money, we apply the technique introduced by [HKN⁺05] in order to transform an incorrect candidate into a correct one. The idea of transformation is first checking the correctness of a public-key quantum money candidate $\Sigma=(\mathsf{Mint},\mathsf{Vrfy})$. If the candidate $\Sigma$ satisfies the correctness, then we amplify the correctness by parallel repetition. Otherwise, we use the scheme $\Sigma^{*}=(\mathsf{Mint}^{*},\mathsf{Vrfy}^{*})$, where $\mathsf{Vrfy}^{*}$ algorithm always outputs $\top$. For details, please see Appendix B..

First, we observe that without loss of generality, $\mathsf{Vrfy}(k,\psi)$ can be considered working as follows: It appends $\ket{0}\bra{0}$ to $\psi$, applies $U_{k}$ to $\psi\otimes\ket{0}\bra{0}$, measures the first qubit of $U_{k}(\psi\otimes\ket{0}\bra{0})U_{k}^{\dagger}$, and outputs the measurement outcome. Now, we describe $\Sigma_{\mathsf{OWSG}}^{*}=(\mathsf{KeyGen}^{*},\mathsf{StateGen}^{*},\mathsf{Vrfy}^{*})$. $\mathsf{KeyGen}^{*}$ is the same as the original $\mathsf{KeyGen}$. $\mathsf{StateGen}^{*}(k)$ first runs $\psi_{k}\leftarrow\mathsf{StateGen}(k)$, then measures the first qubit of $U_{k}(\psi_{k}\otimes\ket{0}\bra{0})U_{k}^{\dagger}$ in the computational basis, and obtains $b$. If $b=1$, $\mathsf{StateGen}^{*}(k)$ rewinds its register and outputs the register as $\psi_{k}^{*}$. Otherwise, output $\psi_{k}^{*}=\bot$, where $\bot$ is a special symbol. $\mathsf{Vrfy}^{*}(k,\psi)$ first checks the form of $\psi$. If $\psi=\bot$, $\mathsf{Vrfy}^{*}(k,\psi)$ outputs $1$. Otherwise, $\mathsf{Vrfy}^{*}(k,\psi)$ applies $U_{k}$ to $\psi$, then measures the first qubit of $U_{k}\psi U_{k}^{\dagger}$, and finally outputs the measurement outcome. We can see that $\Sigma^{*}$ satisfies correctness. If $\mathsf{StateGen}^{*}(k)$ outputs $\psi_{k}^{*}=\bot$, then $\mathsf{Vrfy}^{*}$ always outputs $1$. On the other hand, if $\psi^{*}\neq\bot$, then $\mathsf{StateGen}^{*}(k)$ outputs $\psi_{k}^{*}$ with the form $U_{k}^{\dagger}(\ket{1}\bra{1}\otimes\rho)U_{k}$ for some quantum state $\rho$. Therefore, $\mathsf{Vrfy}^{*}(k,\psi_{k}^{*})$ outputs $1$ since $U_{k}\psi_{k}^{*}U_{k}^{\dagger}=\ket{1}\bra{1}\otimes\rho$. Moreover, we can see that $\Sigma^{*}$ satisfies security as long as $\Sigma$ satisfies correctness and security. As long as $\Sigma$ satisfies correctness, if we measure the first qubits of $U_{k}(\psi_{k}\otimes\ket{0}\bra{0})U_{k}^{\dagger}$ in the computational basis, then the measurement result is $1$ with overwhelming probability, where $k\leftarrow\mathsf{KeyGen}(1^{\lambda})$ and $\psi_{k}\leftarrow\mathsf{StateGen}(k)$. This indicates that the measurement does not disturb the quantum state $U_{k}(\psi_{k}\otimes\ket{0}\bra{0})U_{k}^{\dagger}$ from gentle measurement lemma. Therefore, $\psi_{k}^{*}$ is statistically close to $\psi_{k}\otimes\ket{0}\bra{0}$ as long as $\Sigma$ satisfies correctness. In particular, this implies that we can reduce the security of $\Sigma^{*}$ to that of $\Sigma$ as long as $\Sigma$ satisfies correctness.

First of all, we explain the definition of unclonable SKE. Unclonable SKE $\Sigma_{\mathsf{unclone}}$ is the same as standard SKE $\Sigma_{\mathsf{SKE}}$ except that the ciphertext of unclonable SKE is a quantum state and it satisfies unclonable IND-CPA security in addition to standard IND-CPA security. In unclonable IND-CPA security, the cloning adversary $\mathcal{A}$ with oracle $\mathsf{Enc}(\mathsf{sk},\cdot)$ first sends the challenge plaintext $(m_{0},m_{1})$, then receives a ciphertext $\mathsf{CT}_{b}$, where $\mathsf{CT}_{b}\leftarrow\mathsf{Enc}(\mathsf{sk},m_{b})$, and finally generates a quantum state $\rho_{\mathcal{B},\mathcal{C}}$ over the $\mathcal{B}$ and $\mathcal{C}$ registers. The adversary $\mathcal{B}$ (resp. $\mathcal{C}$) receives the $\mathcal{B}$ register (resp. the $\mathcal{C}$ register) and the secret-key $\mathsf{sk}$, and outputs $b_{\mathcal{B}}$ (resp. $b_{\mathcal{C}}$) which is a guess of $b$. The unclonable IND-CPA security guarantees that for any QPT adversaries $(\mathcal{A},\mathcal{B},\mathcal{C})$, we have

$\displaystyle\Pr[b=b_{\mathcal{B}}=b_{\mathcal{C}}]\leq\frac{1}{2}+{\mathsf{negl}}(\lambda).$

(1)

First, we consider the simpler case, where given candidates $\Sigma_{\mathsf{unclone}}[1]=(\mathsf{KeyGen}[1],\mathsf{Enc}[1],\mathsf{Dec}[1])$ and $\Sigma_{\mathsf{unclone}}[2]=(\mathsf{KeyGen}[2],\mathsf{Enc}[2],\mathsf{Dec}[2])$ are promised to satisfy at least correctness. In that case, a combined unclonable SKE scheme $\mathsf{Comb}.\Sigma_{\mathsf{unclone}}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ simply runs $\Sigma_{\mathsf{unclone}}[1]$ and $\Sigma_{\mathsf{unclone}}[2]$ by using X-OR secret sharing. In other words, for encrypting bit $b$, $\mathsf{Comb}.\Sigma_{\mathsf{unclone}}$ first samples $r[1]$ and $r[2]$ such that $r[1]+r[2]=b$, and encrypts $r[1]$ by using $\Sigma_{\mathsf{unclone}}[1]$ and $r[2]$ by using $\Sigma_{\mathsf{unclone}}[2]$. Clearly, $\mathsf{Comb}.\Sigma_{\mathsf{unclone}}$ satisfies correctness and security as long as both $\Sigma_{\mathsf{unclone}}[1]$ and $\Sigma_{\mathsf{unclone}}[2]$ satisfy correctness and either $\Sigma_{\mathsf{unclone}}[1]$ or $\Sigma_{\mathsf{unclone}}[2]$ satisfies security.

Does the same strategy work for the general setting, where original candidates are not promised to satisfy even correctness? Unfortunately, the simple X-OR protocol above works only when both $\Sigma_{\mathsf{unclone}}[1]$ and $\Sigma_{\mathsf{unclone}}[2]$ satisfy correctness because $\mathsf{Comb}.\Sigma_{\mathsf{unclone}}$ does not satisfy correctness otherwise. Our key observation is that given a candidate of unclonable SKE $\Sigma_{\mathsf{unclone}}$ we can construct a new candidate $\Sigma_{\mathsf{unclone}}^{*}$ with the following properties:

• •

  $\Sigma_{\mathsf{unclone}}^{*}$ satisfies correctness regardless of $\Sigma_{\mathsf{unclone}}$.

• •

  $\Sigma_{\mathsf{unclone}}^{*}$ satisfies security as long as $\Sigma$ satisfies correctness and security.

Once we have obtained such a transformation, we can construct a robust combiner for unclonable SKE as follows. Given two unclonable SKE candidates $\Sigma_{\mathsf{unclone}}[1]$ and $\Sigma_{\mathsf{unclone}}[2]$, a robust combiner for unclonable SKE first transforms $\Sigma_{\mathsf{unclone}}[1]$ and $\Sigma_{\mathsf{unclone}}[2]$ into $\Sigma_{\mathsf{unclone}}[1]^{*}$ and $\Sigma_{\mathsf{unclone}}[2]^{*}$, respectively, and then outputs $\mathsf{Comb}.\Sigma_{\mathsf{unclone}}$ which runs $\Sigma_{\mathsf{unclone}}[1]^{*}$ and $\Sigma_{\mathsf{unclone}}[2]^{*}$ by using X-OR secret sharing. $\mathsf{Comb}.\Sigma_{\mathsf{unclone}}$ satisfies correctness because $\Sigma_{\mathsf{unclone}}[1]^{*}$ and $\Sigma_{\mathsf{unclone}}[2]^{*}$ satisfy correctness no matter what $\Sigma_{\mathsf{unclone}}[1]$ and $\Sigma_{\mathsf{unclone}}[2]$ are. Moreover, $\mathsf{Comb}.\Sigma_{\mathsf{unclone}}$ satisfies security as long as either $\Sigma_{\mathsf{unclone}}[1]$ or $\Sigma_{\mathsf{unclone}}[2]$ satisfies correctness and security. This is because either $\Sigma_{\mathsf{unclone}}^{*}[1]$ or $\Sigma_{\mathsf{unclone}}[2]^{*}$ satisfies security as long as either $\Sigma_{\mathsf{unclone}}[1]$ or $\Sigma_{\mathsf{unclone}}[2]$ satisfies correctness and security.

Now, we consider how to obtain such a transformation. It is known that we can obtain such a transformation for PKE [HKN⁺05]. In their technique, they use parallel repetition to amplify correctness. We emphasize that we cannot apply their technique for unclonable encryption because correctness amplification via parallel repetition does not work for unclonable encryption. Therefore, we take a different approach, whose idea is the same as OWSGs. Without loss of generality, we can assume that $\mathsf{Dec}(\mathsf{sk},\mathsf{CT})$ first appends $\ket{0}\bra{0}$ to $\mathsf{CT}$, applies $U_{\mathsf{sk}}$ to $\mathsf{CT}\otimes\ket{0}\bra{0}$, measures the first $\absolutevalue{m}$-bit of $U_{\mathsf{sk}}(\mathsf{CT}\otimes\ket{0}\bra{0})U_{\mathsf{sk}}^{\dagger}$, and outputs the measurement outcome. Now, we describe $\Sigma_{\mathsf{unclone}}^{*}=(\mathsf{KeyGen}^{*},\mathsf{Enc}^{*},\mathsf{Dec}^{*})$. $\mathsf{KeyGen}^{*}$ is the same as the original $\mathsf{KeyGen}$. $\mathsf{Enc}^{*}(\mathsf{sk},m)$ first runs $\mathsf{CT}\leftarrow\mathsf{Enc}(\mathsf{sk},m)$, then measures the first $\absolutevalue{m}$-bit of $U_{\mathsf{sk}}(\mathsf{CT}\otimes\ket{0}\bra{0})U_{\mathsf{sk}}^{\dagger}$ in the computational basis, obtains $m^{*}$, and checks whether $m=m^{*}$. If $m=m^{*}$, $\mathsf{Enc}^{*}(\mathsf{sk},\mathsf{CT})$ rewinds its register and outputs the register as the quantum ciphertext $\mathsf{CT}^{*}$. Otherwise, output $\mathsf{CT}^{*}=(\bot,m)$, where $\bot$ is a special symbol. $\mathsf{Dec}^{*}(\mathsf{sk},\mathsf{CT}^{*})$ first checks the form of $\mathsf{CT}^{*}$, and outputs $m$ if $\mathsf{CT}^{*}$ is of the form $(\bot,m)$. Otherwise, $\mathsf{Dec}^{*}(\mathsf{sk},\mathsf{CT}^{*})$ applies $U_{\mathsf{sk}}$ to $\mathsf{CT}^{*}$, and outputs the measurement outcome of first $\absolutevalue{m}$-qubits of $U_{\mathsf{sk}}\mathsf{CT}^{*}U_{\mathsf{sk}}^{\dagger}$. Clearly, the new construction $\Sigma_{\mathsf{unclone}}^{*}$ satisfies correctness in the same reason as OWSG. Furthermore, $\Sigma_{\mathsf{unclone}}^{*}$ satisfies security as long as $\Sigma_{\mathsf{unclone}}$ satisfies correctness and security. This is because $\mathsf{CT}^{*}$ is statistically close to $\mathsf{CT}\otimes\ket{0}\bra{0}$ as long as $\Sigma_{\mathsf{unclone}}$ satisfies correctness, and thus we can reduce the security of $\Sigma_{\mathsf{unclone}}^{*}$ to that of $\Sigma_{\mathsf{unclone}}$.

In the following, we consider a robust combiner for quantum bit commitment. In this work, we consider a canonical quantum bit commitment. Any quantum bit commitment can be written in the following canonical form [Yan22]. A canonical quantum bit commitment scheme is a pair of unitaries $(Q_{0},Q_{1})$ acting on the registers $\mathbf{C}$ called the commitment register and $\mathbf{R}$ called the reveal register, and works as follows.

• Commit Phase:

  A sender runs $Q_{b}\ket{0}_{\mathbf{C},\mathbf{R}}$ and sends the $\mathbf{C}$ to a receiver for committing a bit $b\in\{0,1\}$.

• Reveal Phase:

  For revealing the committed bit $b$, the sender sends $b$ and the $\mathbf{R}$ register to the receiver. The receiver applies $Q_{b}^{\dagger}$ to the $\mathbf{C}$ and $\mathbf{R}$ register and measures both registers in the computational basis. The receiver accepts if the measurement outcomes are all $0$, and rejects otherwise.

We require that a canonical quantum bit commitment satisfies hiding and binding. The computational (resp. statistical) hiding requires that no quantum polynomial-time (resp. unbounded) adversaries distinguish $Q_{0}\ket{0}_{\mathbf{C},\mathbf{R}}$ from $Q_{1}\ket{0}_{\mathbf{C},\mathbf{R}}$ without touching the $\mathbf{R}$ register with non-negligible probability.

The binding requires that no adversaries can map an honestly generated quantum bit commitment of $0$ (i.e. $Q_{0}\ket{0}_{\mathbf{C,R}}$) to that of $1$ (i.e. $Q_{1}\ket{0}_{\mathbf{C,R}}$) without touching $\mathbf{C}$ registers. More formally, computational (resp. statistical) binding requires that for any quantum polynomial-time (resp. unbounded) unitary $U_{\mathbf{R},\mathbf{Z}}$ acting on the $\mathbf{R}$ and $\mathbf{Z}$ register and any quantum state $\ket{\tau}_{\mathbf{Z}}$ on $\mathbf{Z}$ register, we have

$\displaystyle\norm{(Q_{1}\ket{0}\bra{0}Q_{1}^{\dagger})_{\mathbf{C,R}}(I_{\mathbf{C}}\otimes U_{\mathbf{R,Z}})(Q_{0}\ket{0}_{\mathbf{C},\mathbf{R}}\ket{\tau}_{\mathbf{Z}})}\leq{\mathsf{negl}}(\lambda).$

(2)

It was shown that we can change the flavor of quantum bit commitment [Yan22, HMY23]. More formally, if we have a canonical quantum bit commitment $(Q_{0},Q_{1})$ that satisfies $X$-hiding and $Y$-binding, then we can construct a canonical quantum bit commitment $(\widetilde{Q_{0}},\widetilde{Q_{1}})$ that satisfies $X$-binding and $Y$-hiding for $X,Y\in$ $\{$statistical, computational$\}$.

First, let us clarify our final goal. Given two candidates of canonical quantum bit commitments $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$, our robust combiner $\mathsf{RobComb}.\mathcal{M}_{\mathsf{Commit}}$ generates a new candidate $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ that satisfies hiding and binding as long as either $(Q_{0}[1],Q_{1}[1])$ or $(Q_{0}[2],Q_{1}[2])$ satisfies hiding and binding. More formally, our robust combiner $\mathsf{RobComb}.\mathcal{M}_{\mathsf{Commit}}$ outputs $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ with the following properties:

• •

  $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ satisfies statistical binding regardless of $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$.

• •

  $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ satisfies computational hiding as long as either $(Q_{0}[1],Q_{1}[1])$ or $(Q_{0}[2],Q_{1}[2])$ satisfies computational hiding and computational binding.

To achieve this final goal, let us consider the following simpler goal first, where both candidates $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$ satisfy at least statistical binding. More formally, given candidates $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$, we consider constructing a new candidate $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ with the following properties:

• •

  $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ satisfies statistical binding as long as both $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$ satisfies statistical binding.

• •

  $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ satisfies computational hiding as long as either $(Q_{0}[1],Q_{1}[1])$ or $(Q_{0}[2],Q_{1}[2])$ satisfies computational hiding.

We can construct such $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ by simply using X-OR secret sharing. More formally, for $b\in\{0,1\}$, $\mathsf{Comb}.Q_{b}$ first samples $r[1]$ and $r[2]$ conditioned on $r[1]+r[2]=b$, and then commits $r[1]$ by using $(Q_{0}[1],Q_{1}[1])$ and commits $r[2]$ by using $(Q_{0}[2],Q_{1}[2])$. Our construction satisfies statistical binding as long as both $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$ satisfy statistical binding. The intuitive reason is that the adversary of $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ needs to change $r[1]$ or $r[2]$ after sending the commitment register to break binding of $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$, but the adversary cannot do this because both $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$ satisfy statistical binding. Furthermore, $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ satisfies computational hiding as long as either $(Q_{0}[1],Q_{1}[1])$ or $(Q_{0}[2],Q_{1}[2])$ satisfies computational hiding. The intuitive reason is that the adversary of $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ needs to obtain both $r[1]$ and $r[2]$ from the commitment register of $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$, but the adversary cannot do this because either $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$ satisfies computational hiding.

Does the same strategy work for a robust quantum bit commitment combiner $\mathsf{RobComb}.\mathcal{M}_{\mathsf{Commit}}$? Unfortunately, the simple X-OR protocol above works only when both $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$ satisfy statistical binding because $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ does not satisfy statistical binding otherwise. Our key observation is that, given a candidate of canonical quantum bit commitment $(Q_{0},Q_{1})$, we can construct a new candidate $(Q_{0}^{*},Q_{1}^{*})$ that satisfies at least statistical binding regardless of $(Q_{0},Q_{1})$. More formally, we can construct $(Q_{0}^{*},Q_{1}^{*})$ with the following properties:

• •

  $(Q_{0}^{*},Q_{1}^{*})$ satisfies statistical binding regardless of $(Q_{0},Q_{1})$.

• •

  $(Q_{0}^{*},Q_{1}^{*})$ satisfies computational hiding if $(Q_{0},Q_{1})$ satisfies computational hiding and computational binding.

Once we have obtained such a transformation, we can construct a robust quantum bit commitment combiner $\mathsf{RobComb}.\mathcal{M}_{\mathsf{Commit}}$. Given two candidates of canonical quantum bit commitment $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$, $\mathsf{RobComb}.\mathcal{M}_{\mathsf{Commit}}$ first transforms $(Q_{0}[1],Q_{1}[1])$ and $(Q_{0}[2],Q_{1}[2])$ into $(Q_{0}[1]^{*},Q_{1}[1]^{*})$ and $(Q_{0}[2]^{*},Q_{1}[2]^{*})$, respectively and then outputs $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$, which runs $(Q_{0}[1]^{*},Q_{1}[1]^{*})$ and $(Q_{0}[2]^{*},Q_{1}[2]^{*})$ by using X-OR secret sharing. Clearly, $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ satisfies statistical binding. Moreover, $(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ satisfies computational hiding as long as either $(Q_{0}[1],Q_{1}[1])$ or $(Q_{0}[2],Q_{1}[2])$ satisfies computational hiding and computational binding.

Now, we consider how to obtain such a transformation. Our first observation is that either $(Q_{0},Q_{1})$ or $(\widetilde{Q_{0}},\widetilde{Q_{1}})$, which is the flavor conversion of $(Q_{0},Q_{1})$ obtained by [HMY23], satisfies statistical binding in a possibly weak sense. To see this let us denote $\rho_{b}\coloneqq\Tr_{\mathbf{R}}(Q_{b}\ket{0}_{\mathbf{C,R}})$. Then, there exists some constant $f$ such that

$\displaystyle F(\rho_{0},\rho_{1})=f,$

(3)

where $F(\rho_{0},\rho_{1})$ is the fidelity between $\rho_{0}$ and $\rho_{1}$. If $f$ is small, then $(Q_{0},Q_{1})$ satisfies statistical binding in a possibly weak sense from Uhlmann’s theorem. On the other hand, if $f$ is large, then $(Q_{0},Q_{1})$ does not satisfy statistical binding, but $(\widetilde{Q_{0}},\widetilde{Q_{1}})$ satisfies statistical binding instead. This is because if $f$ is large, then $(Q_{0},Q_{1})$ satisfies statistical hiding, and thus $(\widetilde{Q_{0}},\widetilde{Q_{1}})$ satisfies statistical binding. Therefore, either $(Q_{0},Q_{1})$ or $(\widetilde{Q_{0}},\widetilde{Q_{1}})$ satisfies statistical binding in a possibly weak sense regardless of $(Q_{0},Q_{1})$. Furthermore, we observe that such a possibly weak binding property can be amplified to a strong one by parallel repetition.

Based on these observations, we construct our transformation. Given a candidate of canonical quantum bit commitment $(Q_{0},Q_{1})$, our transformation outputs a new candidate $(Q_{0}^{*},Q_{1}^{*})$ working as follows.

• •

  If we write $\mathbf{C}$ and $\mathbf{R}$ to mean the commitment register and the reveal register of $(Q_{0},Q_{1})$, and write $\mathbf{\widetilde{C}}$ and $\mathbf{\widetilde{R}}$ to mean the commitment and the reveal register of $(\widetilde{Q_{0}},\widetilde{Q_{1}})$, then the commitment register $\mathbf{C^{*}}$ of $(Q_{0}^{*},Q_{1}^{*})$ is $(\mathbf{C}^{\otimes\lambda},\mathbf{\widetilde{C}}^{\otimes\lambda})$, and the reveal register $\mathbf{R^{*}}$ of $(Q_{0}^{*},Q_{1}^{*})$ is $(\mathbf{R}^{\otimes\lambda},\mathbf{\widetilde{R}}^{\otimes\lambda})$.

• •

  For $b\in\{0,1\}$, $Q_{b}^{*}$ works as follows:

  $\displaystyle Q_{b}^{*}\coloneqq(Q_{b}\otimes\widetilde{Q_{b}})^{\otimes\lambda}.$

  (4)

  Note that we have

  $\displaystyle Q_{b}^{*}\ket{0}_{\mathbf{C^{*},R^{*}}}=(Q_{b}\ket{0}_{\mathbf{C,R}})^{\otimes\lambda}\otimes(\widetilde{Q_{b}}\ket{0}_{\mathbf{\widetilde{C},\widetilde{R}}})^{\otimes\lambda}.$

  (5)

We can see that $(Q_{0}^{*},Q_{1}^{*})$ satisfies statistical binding regardless of $(Q_{0},Q_{1})$. If we write $\rho_{b}\coloneqq\Tr_{\mathbf{R}}(Q_{b}\ket{0}_{\mathbf{C,R}})$, there exists some constant $0\leq f\leq 1$ such that

$\displaystyle F(\rho_{0},\rho_{1})=f.$

(6)

If we write $\widetilde{\rho_{b}}\coloneqq\Tr_{\mathbf{\widetilde{R}}}(\widetilde{Q_{b}}\ket{0}_{\mathbf{\widetilde{C},\widetilde{R}}})$, then we can show that

$\displaystyle F(\widetilde{\rho_{0}},\widetilde{\rho_{1}})\leq(1-f)^{1/2}$

(7)

by using the technique by [HMY23]. Therefore, if we write $\rho_{b}^{*}\coloneqq\Tr_{\mathbf{R^{*}}}(Q_{b}^{*}\ket{0}_{\mathbf{C^{*},R^{*}}})$, we have

$\displaystyle F(\rho_{0}^{*},\rho_{1}^{*})=F((\rho_{0}\otimes\widetilde{\rho_{0}})^{\otimes\lambda},(\rho_{1}\otimes\widetilde{\rho_{1}})^{\otimes\lambda})\leq F(\rho_{0},\rho_{1})^{\lambda}F(\widetilde{\rho_{0}},\widetilde{\rho_{1}})^{\lambda}\leq f^{\lambda}(1-f)^{\lambda/2}\leq 2^{-\lambda/2}.$

(8)

This implies that $(Q_{0}^{*},Q_{1}^{*})$ satisfies statistical binding regardless of $(Q_{0},Q_{1})$ from Uhlmann’s Theorem.

Moreover, we can see that $(Q_{0}^{*},Q_{1}^{*})$ satisfies computational hiding as long as $(Q_{0},Q_{1})$ satisfies computational hiding and computational binding. The hiding QPT adversary of $(Q_{0}^{*},Q_{1}^{*})$ needs to obtain $b$ from $\rho_{b}^{*}=(\rho_{b}\otimes\widetilde{\rho_{b}})^{\otimes\lambda}$. For that, the adversary needs to obtain $b$ from $\rho_{b}$ or $\widetilde{\rho_{b}}$. Because $(Q_{0},Q_{1})$ satisfies computational hiding, the QPT adversary cannot obtain $b$ from $\rho_{b}$. Furthermore, $(\widetilde{Q_{0}},\widetilde{Q_{1}})$ also satisfies computational hiding because $(\widetilde{Q_{0}},\widetilde{Q_{1}})$ is a flavor conversion of $(Q_{0},Q_{1})$. Therefore, the QPT adversary cannot obtain $b$ from $\widetilde{\rho_{b}}$.