$\displaystyle=\frac{1}{2^{n-1}}\Tr(\mathsf{Comb}.\Pi_{0}\left(\sum_{\\{r:R=0\\}}\bigotimes_{i\in[n]}\rho_{i,r_{i}}^{*}-\sum_{\\{r:R=1\\}}\bigotimes_{i\in[n]}\rho_{i,r_{i}}^{*}\right))$
(96)
$\displaystyle=\frac{1}{2^{n-1}}\Tr(\mathsf{Comb}.\Pi_{0}\left(\sum_{r}\bigotimes_{i\in[n]}(-1)^{r_{i}}\rho_{i,r_{i}}^{*}\right))$
(97)
$\displaystyle=\frac{1}{2^{n-1}}\Tr(\mathsf{Comb}.\Pi_{0}\bigotimes_{i\in[n]}\left(\rho^{*}_{i,0}-\rho_{i,1}^{*}\right))$
(98)
$\displaystyle=\frac{1}{2^{n-1}}\Tr(\left(\sum_{\\{r:R=0\\}}\bigotimes_{i\in[n]}\Pi^{*}_{i,r_{i}}\right)\left(\bigotimes_{i\in[n]}\rho^{*}_{i,0}-\rho_{i,1}^{*}\right))$
(99)
$\displaystyle=\frac{1}{2^{n-1}}\Tr(\sum_{\\{r:R=0\\}}\left(\bigotimes_{i\in[n]}\Pi^{*}_{i,r_{i}}\left(\rho^{*}_{i,0}-\rho_{i,1}^{*}\right)\right))$
(100)
$\displaystyle=\frac{1}{2^{n-1}}\sum_{\\{r:R=0\\}}\Tr(\bigotimes_{i\in[n]}\Pi^{*}_{i,r_{i}}\left(\rho^{*}_{i,0}-\rho_{i,1}^{*}\right))$
(101)
$\displaystyle=\frac{1}{2^{n-1}}\sum_{\\{r:R=0\\}}\prod_{i\in[n]}\Tr(\Pi^{*}_{i,r_{i}}\left(\rho^{*}_{i,0}-\rho_{i,1}^{*}\right))$
(102)
$\displaystyle=\prod_{i\in[n]}\Tr(\Pi^{*}_{i,0}\left(\rho^{*}_{i,0}-\rho_{i,1}^{*}\right))\geq(1-{\mathsf{negl}}(\lambda))^{n}\geq
1-n\cdot{\mathsf{negl}}(\lambda).$ (103)

Here, we have used that $\Tr(A+B)=\Tr(A)+\Tr(B)$ in the sixth equation, and we
have used $\Tr(A\otimes B)=\Tr(A)\Tr(B)$ in the seventh equation, and we have
used that

$\displaystyle\prod_{i\in[n]}\Tr(\Pi_{i,r_{i}}^{*}\left(\rho_{i,0}^{*}-\rho_{i,1}^{*}\right))=\prod_{i\in[n]}\Tr(\Pi_{i,0}^{*}\left(\rho_{i,0}^{*}-\rho_{i,1}^{*}\right))$
(104)

for all $r\in\\{0,1\\}^{n}$ with $\sum_{i\in[n]}r_{i}=0$ in the final
equation.

Furthermore, we have $F(\mathsf{Comb}.\rho_{0},\mathsf{Comb}.\rho_{1})\leq
1-\mathsf{TD}(\mathsf{Comb}.\rho_{0},\mathsf{Comb}.\rho_{1})^{2}\leq
2n\cdot{\mathsf{negl}}(\lambda)$. From Uhlmann’s theorem (Theorem 3.6), this
implies that
$\\{\mathsf{Comb}.Q_{0}(\lambda),\mathsf{Comb}.Q_{1}(\lambda)\\}_{\lambda\in\mathbb{N}}$
satisfies statistical binding. ∎

###### Proof of Lemma 6.6.

Below, we fix security parameter $\lambda$, and write
$\\{Q_{i,0}^{*},Q_{i,1}^{*}\\}_{i\in[n]}$ and
$(\mathsf{Comb}.Q_{0},\mathsf{Comb}.Q_{1})$ to mean
$\\{Q_{i,0}^{*}(\lambda),Q_{i,1}^{*}(\lambda)\\}_{i\in[n]}$ and
$(\mathsf{Comb}.Q_{0}(\lambda),\mathsf{Comb}.Q_{1}(\lambda))$, respectively.
Let
$\rho_{i,b}^{*}\coloneqq\Tr_{\mathbf{R}_{i}}(Q_{i,b}^{*}\ket{0}_{\mathbf{C}_{i},\mathbf{R}_{i}})$.
We show that
$\\{\mathsf{Comb}.Q_{0}(\lambda),\mathsf{Comb}.Q_{1}(\lambda)\\}_{\lambda\in\mathbb{N}}$
satisfies computational hiding as long as one of $\\{\Sigma_{i}\\}_{i\in[n]}$
satisfies computational hiding and computational binding. Let $\Sigma_{x}$ be
the canonical quantum bit commitment that satisfies computational hiding and
computational binding. Then, from Lemma 6.4, $\Sigma_{x}^{*}$ satisfies
computational hiding. Now, we introduce the following sequence of hybrid
experiments against QPT adversary $\mathcal{A}$.

$\mathsf{Hyb}_{0}(b)$:

  1. 1.

The challenger sends $\mathsf{Comb}.\rho_{b}$ to $\mathcal{A}$.

  2. 2.

$\mathcal{A}$ outputs $b^{*}$.

$\mathsf{Hyb}_{1}(b)$:

  1. 1.

The challenger randomly samples $r_{i}\leftarrow\\{0,1\\}$ for all
$i\in[n]\backslash x$. We write $R$ to mean $\sum_{i\in[n]\backslash x}r_{i}$.

  2. 2.

The challenger sends
$\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,R+b}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*}$
to $\mathcal{A}$.

  3. 3.

$\mathcal{A}$ outputs $b^{*}$.

$\mathsf{Hyb}_{2}(b)$:

  1. 1.

The challenger randomly samples $r_{i}\leftarrow\\{0,1\\}$ for all
$i\in[n]\backslash x$.

  2. 2.

The challenger sends
$\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,0}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*}$.

  3. 3.

$\mathcal{A}$ outputs $b^{*}$.

We have the following Propositions 6.7, 6.8 and 6.9. Therefore, we have

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb}_{0}(0)=1]-\Pr[\mathsf{Hyb}_{0}(1)=1]}\leq{\mathsf{negl}}(\lambda),$
(105)

which implies that
$\\{\mathsf{Comb}.\rho_{0}(\lambda),\mathsf{Comb}.\rho_{1}(\lambda)\\}_{\lambda\in\mathbb{N}}$
satisfies computational hiding.

###### Proposition 6.7.

$\Pr[\mathsf{Hyb}_{0}(b)=1]=\Pr[\mathsf{Hyb}_{1}(b)=1]$ for $b\in\\{0,1\\}$.

###### Proposition 6.8.

If $\Sigma_{x}^{*}$ satisfies computational hiding, then

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb}_{1}(b)=1]-\Pr[\mathsf{Hyb}_{2}(b)=1]}\leq{\mathsf{negl}}(\lambda)$
(106)

for each $b\in\\{0,1\\}$.

###### Proposition 6.9.

$\Pr[\mathsf{Hyb}_{2}(0)=1]=\Pr[\mathsf{Hyb}_{2}(1)=1]$.

Propositions 6.7 and 6.9 trivially follows, and thus we omit the proof.

###### Proof of Proposition 6.8.

For simplicity, we write $\sum_{r}$ to mean that
$\sum_{\\{r:r_{i}\in\\{0,1\\}\mbox{\,\,for\,\,}i\in[n]\backslash x\\}}$, and
recall that $R\coloneqq\sum_{i\in[n]\backslash x}r_{i}$.

Then, we have

$\displaystyle\Pr[\mathsf{Hyb}_{1}(0)=1]-\Pr[\mathsf{Hyb}_{2}(0)=1]$ (107)
$\displaystyle=\frac{1}{2^{n-1}}\sum_{r}\left(\Pr[1\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,R}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]\right)$
(108)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\frac{1}{2^{n-1}}\sum_{r}\left(\Pr[1\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,0}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]\right)$
(109)
$\displaystyle=\frac{1}{2^{n-1}}\sum_{r}\bigg{(}\Pr[1\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,R}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]$
(110)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\Pr[1\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,0}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]\bigg{)}$
(111)
$\displaystyle=\frac{1}{2^{n-1}}\sum_{\\{r:R=1\\}}\bigg{(}\Pr[1\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,1}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]$
(112)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\Pr[1\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,0}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]\bigg{)}$
(113)
$\displaystyle=\frac{1}{2^{n-1}}\sum_{\\{r:R=1\\}}\bigg{(}\Pr[0\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,0}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]$
(114)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\Pr[0\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,1}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]\bigg{)}.$
(115)

For showing a contradiction, assume that there exists some constant $c$ and a
QPT adversary $\mathcal{A}$ such that

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb}_{1}(0)=1]-\Pr[\mathsf{Hyb}_{2}(0)=1]}\geq
1/\lambda^{c}$ (116)

for all sufficiently large security parameters $\lambda\in\mathbb{N}$ and then
construct a QPT algorithm $\mathcal{B}_{x}$ that breaks the computational
hiding of $\Sigma_{x}^{*}$.

  1. 1.

$\mathcal{B}_{x}$ receives $\rho_{x,b}^{*}$ from the challenger of
$\Sigma_{x}^{*}$, where $b$ is randomly sampled from $\\{0,1\\}$.

  2. 2.

$\mathcal{B}_{x}$ randomly samples $r_{i}\leftarrow\\{0,1\\}$ for all
$i\in[n]\backslash x$.

  3. 3.

$\mathcal{B}_{x}$ sends
$\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,b}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*}$
to $\mathcal{A}$.

  4. 4.

$\mathcal{B}_{x}$ receives $b^{*}$ from $\mathcal{A}$.

  5. 5.

$\mathcal{B}_{x}$ outputs $b^{*}+1$ if $R=1$, and outputs $0$ otherwise, where
$R=\sum_{i\in[n]\backslash x}r_{i}$.

We compute
$\absolutevalue{\Pr[1\leftarrow\mathcal{B}_{x}:b=0]-\Pr[1\leftarrow\mathcal{B}_{x}:b=1]}$.
It holds that

$\displaystyle\absolutevalue{\Pr[1\leftarrow\mathcal{B}_{x}:b=0]-\Pr[1\leftarrow\mathcal{B}_{x}:b=1]}$
(117)
$\displaystyle=\frac{1}{2}\absolutevalue{\Pr[0\leftarrow\mathcal{A}:b=0,R=1]-\Pr[0\leftarrow\mathcal{A}:b=1,R=1]}$
(118)
$\displaystyle=\frac{1}{2^{n}}\Bigg{|}\sum_{\\{r:R=1\\}}\left(\Pr[0\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,0}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]\right)$
(119)
$\displaystyle-\sum_{\\{r:R=1\\}}\left(\Pr[0\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,1}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]\right)\Bigg{|}$
(120)
$\displaystyle=\frac{1}{2^{n}}\Bigg{|}\sum_{\\{r:R=1\\}}\bigg{(}\Pr[0\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,0}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]$
(121)
$\displaystyle-\Pr[0\leftarrow\mathcal{A}(\rho_{1,r_{1}}^{*}\otimes\cdots\otimes\rho_{x-1,r_{x-1}}^{*}\otimes\rho_{x,1}^{*}\otimes\rho_{x+1,r_{x+1}}^{*}\otimes\cdots\otimes\rho_{n,r_{n}}^{*})]\bigg{)}\Bigg{|}$
(122)
$\displaystyle=\frac{1}{2}\absolutevalue{\Pr[\mathsf{Hyb}_{1}(0)=1]-\Pr[\mathsf{Hyb}_{2}(0)=1]}.$
(123)

This implies that if there exists a QPT adversary such that
$\absolutevalue{\Pr[\mathsf{Hyb}_{1}(0)=1]-\Pr[\mathsf{Hyb}_{2}(0)=1]}$ is
non-negligible, then $\mathcal{B}_{x}$ breaks the computational hiding of
$\Sigma_{x}^{*}$. Therefore, we have

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb}_{1}(0)=1]-\Pr[\mathsf{Hyb}_{2}(0)=1]}\leq{\mathsf{negl}}(\lambda).$
(124)

In a similar way, we can prove that

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb}_{1}(1)=1]-\Pr[\mathsf{Hyb}_{2}(1)=1]}\leq{\mathsf{negl}}(\lambda).$
(125)

∎

∎

###  6.1 Universal Construction

###### Definition 6.10.

We say that a sequence of uniform QPT unitaries
$\Sigma_{\mathsf{Univ}}=\\{Q_{0}(\lambda),Q_{1}(\lambda)\\}_{\lambda\in\mathbb{N}}$
is a universal construction of canonical quantum bit commitment if
$\Sigma_{\mathsf{Univ}}$ is canonical quantum bit commitment as long as there
exists canonical quantum bit commitment.

###### Theorem 6.11.

There exists a universal construction of canonical quantum bit commitment.

The proof is almost the same as Theorem 4.9, and thus we skip the proof.

##  7 Robust Combiner for Unclonable Encryption

###### Definition 7.1 (Robust Combiner for Unclonable Secret-Key Encryption).

A robust combiner for (one-time) unclonable secret-key encryption with
$\ell(\lambda)$-bit plaintexts is a deterministic classical polynomial-time
Turing machine $\mathcal{M}$ with the following properties:

  * •

$\mathcal{M}$ takes as input $1^{n}$ with $n\in\mathbb{N}$ and $n$-candidates
(one-time) unclonable secret-key encryption with $\ell(\lambda)$-bit
plaintexts
$\\{\Sigma_{i}\coloneqq(\mathsf{KeyGen}_{i},\mathsf{Enc}_{i},\mathsf{Dec}_{i})\\}_{i\in[n]}$
promised that all candidates satisfies efficiency, and outputs a set of
algorithms $\Sigma\coloneqq(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$.

  * •

If all of $\\{\Sigma_{i}\\}_{i\in[n]}$ satisfies efficiency and at least one
of $\\{\Sigma_{i}\\}_{i\in[n]}$ satisfies correctness, (one-time) IND-CPA
security and (one-time) unclonable IND-CPA security, then $\Sigma$ is (one-
time) unclonable secret-key encryption for $\ell(\lambda)$-bit plaintexts that
satisfies efficiency, correctness, (one-time) IND-CPA security and (one-time)
unclonable IND-CPA security.

In this section, we prove the following Theorem 7.2.

###### Theorem 7.2.

There exists a robust combiner for (one-time) unclonable secret-key encryption
with $\ell(\lambda)$-bit plaintexts for all polynomial $\ell$.

As a corollary, we obtain the following Corollary 7.3.

###### Corollary 7.3.

There exists a robust combiner for unclonable public-key encryption with
$\ell(\lambda)$-bit plaintexts for all polynomial $\ell$.

###### Proof of Corollary 7.3.

We give a rough sketch of the proof.

Corollary 7.3 follows from the following observations. We can trivially obtain
one-time unclonable SKE from unclonable PKE. From Theorem 7.2, we have a
robust combiner for one-time unclonable SKE. Furthermore, we can trivially
construct PKE with quantum ciphertexts from unclonable PKE. It is known that
there exists a robust PKE combiner [HKN+05], and we observe that we can also
construct a robust combiner for PKE with quantum ciphertexts in the same way.
Moreover, we can construct unclonable PKE from one-time unclonable SKE, and
PKE with quantum ciphertexts. This is because we can construct unclonable PKE
from one-time SKE and receiver non-committing encryption with quantum
ciphertexts 444 [AK21] shows that unclonable PKE can be constructed from one-
time unclonable SKE and PKE with classical ciphertexts. Note that it is
unclear whether we can construct unclonable PKE from one-time SKE and PKE with
“quantum” ciphertexts in the same way as [AK21]. This is because they use the
existence of OWFs in their proof although it is unclear whether PKE with
quantum ciphertexts implies OWFs. Therefore, we use the technique of [HMNY21]
instead. (For the detail, see Appendix E)  (For the detail, see Appendix E),
and receiver non-committing encryption with quantum ciphertexts can be
constructed from PKE with quantum ciphertexts in the same way as the classical
ciphertext case [CHK05, KNTY19].

By combining these observations, we can construct a robust combiner for
unclonable PKE as follows. Given candidates of unclonable PKE
$\\{\Sigma_{i}\\}_{i\in[n]}$, we first use a robust combiner for one-time
unclonable SKE, and obtain a new candidate of one-time unclonable SKE
$\Sigma_{\mathsf{SKE}}$ regarding each candidate $\Sigma_{i}$ as a one-time
unclonable SKE scheme. Next, we use a robust combiner for PKE with quantum
ciphertexts and obtain a new candidate of PKE with quantum ciphertexts
$\Sigma_{\mathsf{PKE}}$ regarding each candidate $\Sigma_{i}$ as a (not
necessarily unclonable) PKE scheme. Then, we construct a receiver non-
committing encryption with quantum ciphertexts $\Sigma_{\mathsf{NCE}}$ from
$\Sigma_{\mathsf{PKE}}$. Finally, we construct unclonable PKE
$\Sigma_{\mathsf{unclone}}$ from one-time unclonable SKE
$\Sigma_{\mathsf{SKE}}$ and receiver non-committing encryption with quantum
ciphertexts $\Sigma_{\mathsf{NCE}}$. ∎

For proving Theorem 7.2, we introduce the following Lemma 7.4.

###### Lemma 7.4.

Let $\Sigma$ be a candidate for (one-time) unclonable secret-key encryption
with $\ell(\lambda)$-bit plaintexts. From $\Sigma$, we can construct a (one-
time) unclonable secret-key encryption with $\ell(\lambda)$-bit plaintexts
$\Sigma^{*}\coloneqq(\mathsf{KeyGen}^{*},\mathsf{Enc}^{*},\mathsf{Dec}^{*})$
such that:

  1. 1.

$\Sigma^{*}$ is a uniform QPT algorithm, if $\Sigma$ is a uniform QPT
algorithm.

  2. 2.

$\Sigma^{*}$ satisfies perfect correctness.

  3. 3.

$\Sigma^{*}$ satisfies (one-time) IND-CPA security and (one-time) unclonable
IND-CPA security if $\Sigma$ is a uniform QPT algorithm and satisfies
correctness, (one-time) IND-CPA security and (one-time) unclonable IND-CPA
security.

The proof is almost the same as Lemma 4.4. For the reader’s convenience, we
describe the construction of $\Sigma^{*}$ in Appendix D.

###### Proof of Theorem 7.2.

Below, we consider a fixed constant $n$ and a fixed polynomial $\ell$. Let us
describe some notations:

#### Notations.

  * •

Let $\Sigma_{i}$ be a candidate of (one-time) unclonable secret-key encryption
with $\ell(\lambda)$-length for $i\in[n]$.

  * •

For a candidate of (one-time) unclonable secret-key encryption with
$\ell(\lambda)$-bit plaintexts $\Sigma_{i}$, let
$\Sigma_{i}^{*}\coloneqq(\mathsf{KeyGen}^{*}_{i},\mathsf{Enc}^{*}_{i},\mathsf{Dec}^{*}_{i})$
be a candidate of (one-time) unclonable secret-key encryption with
$\ell(\lambda)$-bit plaintexts derived from Lemma 7.4, which satisfies:

    * –

$\Sigma_{i}^{*}$ is a uniform QPT algorithm, if $\Sigma_{i}$ is a uniform QPT
algorithm.

    * –

$\Sigma_{i}^{*}$ satisfies correctness.

    * –

$\Sigma_{i}^{*}$ satisfies (one-time) IND-CPA security and (one-time)
unclonable IND-CPA security if $\Sigma_{i}$ is uniform QPT algorithm and
satisfies correctness, (one-time) IND-CPA security, and (one-time) unclonable
IND-CPA security.

#### Construction of Robust (One-Time) Unclonable Secret-Key Encryption.

A robust combiner for (one-time) unclonable secret-key encryption with
$\ell(\lambda)$-bit plaintexts is a deterministic classical polynomial-time
Turing machine that takes as input $1^{n}$ and $\\{\Sigma_{i}\\}_{i\in[n]}$,
and outputs the following set of algorithms
$\Sigma=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$:

$\mathsf{KeyGen}(1^{\lambda})$:

  * •

For all $i\in[n]$, run
$\mathsf{sk}_{i}^{*}\leftarrow\mathsf{KeyGen}_{i}^{*}(1^{\lambda})$.

  * •

Output $\mathsf{sk}\coloneqq\\{\mathsf{sk}_{i}^{*}\\}_{i\in[n]}$.

$\mathsf{Enc}(1^{\lambda},\mathsf{sk},m)$:

  * •

For all $i\in[n]$, sample $r_{i}\leftarrow\\{0,1\\}^{\ell(\lambda)}$ promised
that $\sum_{i\in[n]}r_{i}=m$, where the $\ell(\lambda)$ is the length of
plaintext $m$.

  * •

For all $i\in[n]$, run
$\mathsf{CT}_{i}^{*}\leftarrow\mathsf{Enc}_{i}^{*}(1^{\lambda},\mathsf{sk}_{i}^{*},r_{i})$
for all $i\in[n]$.

  * •

Output $\mathsf{CT}\coloneqq\\{\mathsf{CT}_{i}^{*}\\}_{i\in[n]}$.

$\mathsf{Dec}(1^{\lambda},\mathsf{sk},\mathsf{CT})$:

  * •

Run
$r_{i}^{*}\leftarrow\mathsf{Dec}_{i}^{*}(1^{\lambda},\mathsf{sk}_{i}^{*},\mathsf{CT}_{i}^{*})$
for all $i\in[n]$.

  * •

Output $\sum_{i\in[n]}r_{i}^{*}$.

Theorem 7.2 follows from the following Lemmata 7.5, 7.6, 7.7 and 7.8.

###### Lemma 7.5.

If all of $\\{\Sigma_{i}\\}_{i\in[n]}$ satisfies efficiency, $\Sigma$
satisfies efficiency.

###### Lemma 7.6.

$\Sigma$ satisfies correctness.

###### Lemma 7.7.

If all of $\\{\Sigma_{i}\\}_{i\in[n]}$ satisfies efficiency and one of
$\\{\Sigma_{i}\\}_{i\in[n]}$, satisfies both correctness and (one-time) IND-
CPA security, then $\Sigma$ satisfies (one-time) IND-CPA security.

###### Lemma 7.8.

If all of $\\{\Sigma_{i}\\}_{i\in[n]}$ satisfies efficiency and one of
$\\{\Sigma_{i}\\}_{i\in[n]}$, satisfies both correctness and (one-time)
unclonable IND-CPA security, then $\Sigma$ satisfies (one-time) unclonable
IND-CPA security.

Lemmata 7.5 and 7.6 trivially follows, and thus we skip the proof. The proof
of Lemma 7.7 is the same as that of Lemma 7.8, and thus we skip the proof.

###### Proof of Lemma 7.8.

We prove the Lemma 7.8 via a standard hybrid argument. For the reader’s
convenience, we describe the proof. For simplicity, we consider the one-time
case where $\Sigma_{i}$ is a candidate of one-time unclonable secret-key
encryption for each $i\in[n]$. We show that $\Sigma$ satisfies unclonable IND-
CPA security as long as all of $\\{\Sigma_{i}\\}_{i\in[n]}$ satisfy efficiency
and one of $\\{\Sigma_{i}\\}_{i\in[n]}$ satisfies one-time unclonable IND-CPA
security. Let $\Sigma_{x}$ be the candidate for one-time unclonable secret-key
encryption that satisfies both correctness and one-time unclonable IND-CPA
security. Then, $\Sigma_{x}^{*}$ satisfies unclonable IND-CPA security from
Lemma 7.4. Assume that there exists a QPT adversary
$(\mathcal{A},\mathcal{B},\mathcal{C})$ that breaks the one-time unclonable
IND-CPA security of $\Sigma$, and then construct a set of QPT adversaries
$(\widetilde{\mathcal{A}_{x}},\widetilde{\mathcal{B}_{x}},\widetilde{\mathcal{C}_{x}})$
that breaks the one-time unclonable security of $\Sigma_{x}^{*}$.

  1. 1.

$\widetilde{\mathcal{A}_{x}}$ receives $(m_{0},m_{1})$ from $\mathcal{A}$.

  2. 2.

$\widetilde{\mathcal{A}_{x}}$ samples
$r_{i}\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all $i\in[n]\backslash x$, and
sends $(M_{0}\coloneqq m_{0}+\sum_{i\in[n]\backslash x}r_{i},M_{1}\coloneqq
m_{1}+\sum_{i\in[n]\backslash x}r_{i})$ to the challenger of $\Sigma_{x}^{*}$.

  3. 3.

The challenger of $\Sigma_{x}^{*}$ samples $b\leftarrow\\{0,1\\}$, and runs
$\mathsf{CT}_{x}[M_{b}]^{*}\leftarrow\mathsf{Enc}_{x}^{*}(1^{\lambda},\mathsf{sk}_{x}^{*},M_{b})$.

  4. 4.

$\widetilde{\mathcal{A}_{x}}$ receives from $\mathsf{CT}_{x}[M_{b}]^{*}$, runs
$\mathsf{sk}_{i}^{*}\leftarrow\mathsf{KeyGen}_{i}^{*}(1^{\lambda})$ for all
$i\in[n]\backslash x$, samples $r_{i}$ for all $i\in[n]\backslash x$, runs
$\mathsf{CT}_{i}[r_{i}]^{*}\leftarrow\mathsf{Enc}_{i}^{*}(1^{\lambda},\mathsf{sk}_{i}^{*},r_{i})$,
and sends
$(\mathsf{CT}_{1}[r_{1}]^{*},\cdots,\mathsf{CT}_{x-1}[r_{x-1}]^{*},\mathsf{CT}_{x}[M_{b}]^{*},\mathsf{CT}_{x+1}[r_{x+1}]^{*},\cdots,\mathsf{CT}_{n}[r_{n}]^{*})$
to $\mathcal{A}$.

  5. 5.

When $\mathcal{A}$ outputs $\rho_{\mathcal{B},\mathcal{C}}$,
$\widetilde{\mathcal{A}_{x}}$ sends $\\{\mathsf{sk}_{i}\\}_{i\in[n]\backslash
x}$ and the $\mathcal{B}$ register (resp. the $\mathcal{C}$ register) to
$\widetilde{\mathcal{B}_{x}}$ (resp. $\widetilde{\mathcal{C}_{x}}$).

  6. 6.

$\widetilde{\mathcal{B}_{x}}$ and $\widetilde{\mathcal{C}_{x}}$ receive
$\mathsf{sk}_{x}^{*}$ from the challenger of $\Sigma_{x}^{*}$.

  7. 7.

$\widetilde{\mathcal{B}_{x}}$ (resp. $\widetilde{\mathcal{C}_{x}}$) sends
$\\{\mathsf{sk}_{i}^{*}\\}_{i\in[n]}$ and the $\mathcal{B}$ register to
$\mathcal{B}$ (resp. the $\mathcal{C}$ register to $\mathcal{C}$).

  8. 8.

The experiment outputs $1$ if $b=b_{\mathcal{B}}=b_{\mathcal{C}}$, where
$b_{\mathcal{B}}$ (resp. $b_{\mathcal{C}}$) is the output of $\mathcal{B}$
(resp. $\mathcal{C}$).

From the construction of
$(\widetilde{\mathcal{A}_{x}},\widetilde{\mathcal{B}_{x}},\widetilde{\mathcal{C}_{x}})$,
it perfectly simulates the challenger of $\Sigma$. Therefore, if
$(\mathcal{A},\mathcal{B},\mathcal{C})$ breaks the one-time unclonable IND-CPA
security of $\Sigma$, then
$(\widetilde{\mathcal{A}_{x}},\widetilde{\mathcal{B}_{x}},\widetilde{\mathcal{C}_{x}})$
breaks the one-time unclonable IND-CPA security of $\Sigma_{x}^{*}$. ∎

∎

###  7.1 Universal Constructions

###### Definition 7.9.

We say that a set of uniform QPT algorithms
$\Sigma_{\mathsf{Univ}}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ is a
universal construction of (one-time) unclonable SKE (resp. PKE) if
$\Sigma_{\mathsf{Univ}}$ is (one-time) unclonable SKE (resp. PKE) as long as
there exists (one-time) unclonable SKE (resp. PKE).

We give a universal construction of unclonable encryption via robust
combiners.

#### Universal Construction via Robust Combiner

###### Theorem 7.10.

There exists a universal construction of (one-time) unclonable SKE and
unclonable PKE.

The proof is almost the same as Theorem 4.9, and thus we skip the proof.

##  8 Universal Plaintext Extension for Unclonable Encryption

In this section, we prove the following Theorem 8.1.

###### Theorem 8.1.

Assume that there exists a decomposable quantum randomized encoding and one-
time unclonable SKE
$\Sigma_{\mathsf{unclone}}=\mathsf{Unclone}.(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$
where the size of the quantum circuit
$\mathsf{Unclone}.\mathsf{Dec}(1^{\lambda},\cdot,\cdot)$ is $\ell(\lambda)$.
Then, for all polynomial $n$, there exists a polynomial $p$ which depends on
the polynomial $n$ and $\ell$ and a set of uniform QPT algorithms
$\Sigma=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ which depends on the
polynomial $p$ such that $\Sigma$ is a one-time unclonable secret-key
encryption for $n(\lambda)$-bit plaintexts.

######  Remark 8.2.

Our construction is universal construction for one-time unclonable SKE in the
sense that our construction does not depend on the single-bit scheme
$\Sigma_{\mathsf{unclone}}$ that is assumed to exist except for the size of
the decryption circuit of $\Sigma_{\mathsf{unclone}}$.

As corollaries, we obtain Corollaries 8.3 and 8.4.

###### Corollary 8.3.

For all polynomial $n$, there exists a set of uniform QPT algorithms
$\Sigma=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ such that $\Sigma$ is
unclonable secret-key encryption for $n(\lambda)$-bit plaintexts if there
exists unclonable secret-key encryption for single-bit plaintexts.

###### Corollary 8.4.

For all polynomial $n$, there exists a set of uniform QPT algorithms
$\Sigma=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ such that $\Sigma$ is
unclonable public-key encryption for $n(\lambda)$-bit plaintexts if there
exists unclonable public-key encryption for single-bit plaintexts.

###### Proof of Corollary 8.4.

We give a rough sketch of the proof of Corollary 8.4. Note that, in the same
way, we can prove Corollary 8.3.

We can construct PKE with quantum ciphertexts and one-time unclonable SKE with
single-bit plaintexts from unclonable PKE for single-bit plaintexts. We can
construct decomposable quantum randomized encoding from PKE with quantum
ciphertexts. Furthermore, from Theorem 8.1, we can construct one-time
unclonable SKE with $n(\lambda)$-bit plaintexts from decomposable quantum
randomized encoding and one-time unclonable SKE with single-bit plaintexts.

On the other hand, we can construct receiver non-committing encryption with
quantum ciphertexts from PKE with quantum ciphertexts. By combining the
receiver non-committing encryption with quantum ciphertexts and one-time
unclonable SKE with $n(\lambda)$-bit plaintexts, we obtain unclonable PKE with
$n(\lambda)$-bit plaintexts (For the detail, see Appendix E). ∎

###### Proof of Theorem 8.1.

First, let us describe notations and observations.

#### Notations and observations.

  * •

Let $C_{\lambda,p}[m]$ be a quantum circuit of size $p(\lambda)$ with
$\lambda$-qubit quantum inputs and $\lambda$-bit classical inputs such that it
outputs $m$ for any inputs, where $p$ is a polynomial which we specify later.

  * •

Let $\Sigma_{\mathsf{RE}}\coloneqq\mathsf{RE}.(\mathsf{Enc},\mathsf{Dec})$ be
a decomposable quantum randomized encoding. Given quantum circuit $C$ and
$n_{1}$-length quantum input and $n_{2}$-length classical input $\mathbf{q}$
and $x$, the encoding $\widehat{C}(\mathbf{q},x)$ can be separated as follows:

$\displaystyle\widehat{C}(\mathbf{q},x,r,e)=(\widehat{C}_{\mathsf{off}},\widehat{C}_{1},\cdots,\widehat{C}_{n_{1}+n_{2}})(\mathbf{q},x,r,e),$
(126)

where $r$ is uniformly ransom string and $e$ is some quantum state. From
decomposability, $\widehat{C}_{\mathsf{off}}$ acts only on $r$ and $e$, and
$\widehat{C_{i}}$ acts only on $\mathbf{q_{i}},r$ and $e$ for $i\in[n_{1}]$,
and $\widehat{C_{i}}$ acts only on $x_{i}$ and $r$ for
$i\in\\{n_{1}+1,\cdots,n_{1}+n_{2}\\}$. For any quantum circuit $C$, we write
$\mathsf{lab}[i,x_{i}]=\widehat{C_{i}}(x_{i},r_{i})$ and
$\mathsf{lab}[i,\mathbf{q}_{i}]=\widehat{C_{i}}(\mathbf{q}_{i},r,e)$.

#### Construction.

We give a construction of one-time unclonable secret-key encryption
$\Sigma\coloneqq(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ with
$n(\lambda)$-bit plaintexts by using decomposable quantum randomized encoding.
In the construction, we only use decomposable quantum randomized encoding. The
construction is secure as long as the underlying decomposable quantum
randomized encoding is secure and there exists one-time unclonable secret-key
encryption for single-bit plaintexts.

$\mathsf{KeyGen}(1^{\lambda})$:

  * •

Sample $x\leftarrow\\{0,1\\}^{\lambda}$.

  * •

Sample $R[i]\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all $i\in[\lambda]$.

  * •

Output $\mathsf{sk}\coloneqq\left(x,\\{R[i]\\}_{i\in[\lambda]}\right)$.

$\mathsf{Enc}(1^{\lambda},\mathsf{sk},m)$:

  * •

Parse $\mathsf{sk}=\left(x,\\{R[i]\\}_{i\in[\lambda]}\right)$.

  * •

Prepare the quantum circuit $C_{\lambda,p}[m]$ that outputs $m$ for any
inputs.

  * •

Compute $\widehat{C_{\lambda,p}}[m]_{\mathsf{off}}$.

  * •

Compute
$\\{\mathsf{lab}[i,0]\\}_{i\in[\lambda]},\,\,\,\mbox{and}\,\,\,\\{\mathsf{lab}[i,b]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},b\in\\{0,1\\}}.$

  * •

Sample $S[i]\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all $i\in[\lambda]$.

  * •

Compute $\mathsf{Lab}.\mathsf{CT}[i+\lambda,x[i]]\coloneqq
R[i]+\mathsf{lab}[i+\lambda,x[i]]$ and
$\mathsf{Lab}.\mathsf{CT}[i+\lambda,1-x[i]]\coloneqq
S[i]+\mathsf{lab}[i+\lambda,1-x[i]]$ for all $i\in[\lambda]$.

  * •

Output

$\displaystyle\mathsf{CT}\coloneqq\left(\widehat{C_{\lambda,p}}[m]_{\mathsf{off}},\
\\{\mathsf{lab}[i,0]\\}_{i\in[\lambda]},\\{\mathsf{Lab}.\mathsf{CT}[i,b]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},b\in\\{0,1\\}}\right).$
(127)

$\mathsf{Dec}(1^{\lambda},\mathsf{sk},\mathsf{CT})$:

  * •

Parse $\mathsf{sk}=\left(x,\\{R[i]\\}_{i\in[\lambda]}\right)$ and

$\displaystyle\mathsf{CT}=\left(\widehat{C_{\lambda,p}}[m]_{\mathsf{off}},\\{\mathsf{lab}[i,0]\\}_{i\in[\lambda]},\\{\mathsf{Lab}.\mathsf{CT}[i,b]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},b\in\\{0,1\\}}\right).$
(128)

  * •

Compute
$\mathsf{lab}[i+\lambda,x[i]]\coloneqq\mathsf{Lab}.\mathsf{CT}[i+\lambda,x[i]]+R[i]$
for all $i\in[\lambda]$.

  * •

Compute

$\displaystyle\mathsf{RE}.\mathsf{Dec}\left(\widehat{C_{\lambda,p}}[m]_{\mathsf{off}},\\{\mathsf{lab}[i,0]\\}_{i\in[\lambda]},\\{\mathsf{lab}[i,x[i]]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\}}\right)$
(129)

and outputs its output.

###### Lemma 8.5.

$\Sigma$ satisfies efficiency if $\Sigma_{\mathsf{RE}}$ is decomposable
quantum randomized encoding.

###### Lemma 8.6.

$\Sigma$ satisfies correctness if $\Sigma_{\mathsf{RE}}$ is decomposable
quantum randomized encoding.

###### Lemma 8.7.

If $\Sigma_{\mathsf{RE}}$ is decomposable quantum randomized encoding and
there exists one-time unclonable secret-key encryption with single-bit
plaintexts, $\Sigma$ satisfies one-time IND-CPA security for some polynomial
$p$.

###### Lemma 8.8.

If $\Sigma_{\mathsf{RE}}$ is decomposable quantum randomized encoding and
there exists one-time unclonable secret-key encryption with single-bit
plaintexts, $\Sigma$ satisfies one-time unclonable IND-CPA security for some
polynomial $p$.

Lemma 8.5 straightforwardly follows. We can see that Lemma 8.6 holds as
follows. First, if $\mathsf{sk}\leftarrow\mathsf{KeyGen}(1^{\lambda})$ and
$\mathsf{CT}\leftarrow\mathsf{Enc}(\mathsf{sk},m)$,
$\mathsf{Dec}(\mathsf{sk},\mathsf{CT})$ outputs the output of
$C_{\lambda,p}[m](0^{\lambda},x)$. From the definition of $C_{\lambda,p}[m]$,
$C_{\lambda,p}[m](0^{\lambda},x)$ outputs $m$ for all $x$.

The proof of Lemma 8.7 is the same as Lemma 8.8, and thus we skip the proof.

###### Proof of Lemma 8.8.

By a standard argument, we can show the following Proposition 8.9.

###### Proposition 8.9.

If there exists one-time unclonable secret-key encryption for single-bit
plaintexts, then there exists a one-time unclonable secret-key encryption for
single-bit plaintexts scheme
$\Sigma_{\mathsf{unclone}}=\mathsf{Unclone}.(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$
such that the following properties are satisfied:

  1. 1.

$\Sigma_{\mathsf{unclone}}$ satisfies perfect correctness.

  2. 2.

For all security parameters $\lambda\in\mathbb{N}$ and $b\in\\{0,1\\}$, we
have
$\absolutevalue{\mathsf{sk}_{\lambda}}=\absolutevalue{\mathsf{CT}_{\lambda,b}}=\lambda$,
where
$\mathsf{sk}_{\lambda}\leftarrow\mathsf{Unclone}.\mathsf{KeyGen}(1^{\lambda})$
and
$\mathsf{CT}_{\lambda,b}\leftarrow\mathsf{Unclone}.\mathsf{Enc}(1^{\lambda},\mathsf{sk}_{\lambda},b)$.

  3. 3.

For all security parameters $\lambda$,
$\mathsf{Unclone}.\mathsf{KeyGen}(1^{\lambda})$ uniformly randomly samples
$\mathsf{sk}_{\lambda}$.

We give the proof of Proposition 8.9 in Appendix F. We
define$D_{\lambda}[m_{0},m_{1}]$ as a quantum circuit that takes as input
$\lambda$-qubit quantum inputs $\rho$ and $\lambda$-bit classical bits $x$,
runs the quantum circuit
$b\leftarrow\mathsf{Unclone}.\mathsf{Dec}(1^{\lambda},x,\rho)$, and outputs
$m_{b}$. Now, we define $p$ as a polynomial large enough to run the circuit
$D_{\lambda}[m_{0},m_{1}]$.

We describe the sequence of hybrids against the adversary
$(\mathcal{A},\mathcal{B},\mathcal{C})$.

$\mathsf{Hyb_{0}}$:

This is the original one-time unclonable IND-CPA security experiment.

  1. 1.

The challenger samples $b\leftarrow\\{0,1\\}$.

  2. 2.

The challenger samples $x\leftarrow\\{0,1\\}^{\lambda}$ and
$R[i]\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all $i\in[\lambda]$.

  3. 3.

$\mathcal{A}$ sends $(m_{0},m_{1})$ to the challenger.

  4. 4.

The challenger computes $\widehat{C_{\lambda,p}}[m_{b}]_{\mathsf{off}}$,
$\\{\mathsf{lab}[i,0]\\}_{i\in[\lambda]}$, and
$\\{\mathsf{lab}[i,\beta]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},\beta\in\\{0,1\\}}$.

  5. 5.

The challenger samples $S[i]\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all
$i\in[\lambda]$, and computes

$\displaystyle\mathsf{Lab}.\mathsf{CT}[i+\lambda,x[i]]\coloneqq
R[i]+\mathsf{lab}[i+\lambda,x[i]]$ (130)
$\displaystyle\mathsf{Lab}.\mathsf{CT}[i+\lambda,1-x[i]]\coloneqq
S[i]+\mathsf{lab}[i+\lambda,1-x[i]]$ (131)

for all $i\in[\lambda]$.

  6. 6.

The challenger sends

$\displaystyle\mathsf{CT}\coloneqq\left(\widehat{C_{\lambda,p}}[m]_{\mathsf{off}},\\{\mathsf{lab}[i,0]\\}_{i\in[\lambda]},\\{\mathsf{Lab}.\mathsf{CT}[i,\beta]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},\beta\in\\{0,1\\}}\right).$
(132)

to $\mathcal{A}$.

  7. 7.

$\mathcal{A}$ produces $\rho_{\mathcal{B},\mathcal{C}}$ and sends the
corresponding registers to $\mathcal{B}$ and $\mathcal{C}$.

  8. 8.

$\mathcal{B}$ and $\mathcal{C}$ receives
$\left(x,\\{R[i]\\}_{i\in[\lambda]}\right)$, and outputs $b_{\mathcal{B}}$ and
$b_{\mathcal{C}}$.

  9. 9.

The experiment outputs $1$ if $b_{\mathcal{B}}=b_{\mathcal{C}}=b$, and
otherwise $0$.

$\mathsf{Hyb_{1}}$:

  1. 1.

The challenger samples $b\leftarrow\\{0,1\\}$.

  2. 2.

The challenger samples $x\leftarrow\\{0,1\\}^{\lambda}$ and
$R[i]\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all $i\in[\lambda]$.

  3. 3.

The adversary $\mathcal{A}$ sends $(m_{0},m_{1})$ to the challenger.

  4. 4.

The challenger computes
$\mathsf{unclone}.\mathsf{CT}_{b}\leftarrow\mathsf{Unclone}.\mathsf{Enc}(1^{\lambda},x,b)$,
where $\mathsf{unclone}.\mathsf{CT}_{b}$ is the $\lambda$-length quantum
states.

  5. 5.

The challenger computes $\widehat{D_{\lambda}}[m_{0},m_{1}]_{\mathsf{off}}$,
$\\{\mathsf{lab}[i,\mathsf{unclone}.\mathsf{CT}_{b}[i]]\\}_{i\in[\lambda]}$,
and
$\\{\mathsf{lab}[i,\beta]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},\beta\in\\{0,1\\}}.$

  6. 6.

The challenger samples $S[i]\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all
$i\in[\lambda]$, and computes

$\displaystyle\mathsf{Lab}.\mathsf{CT}[i+\lambda,x[i]]\coloneqq
R[i]+\mathsf{lab}[i+\lambda,x[i]]$ (133)
$\displaystyle\mathsf{Lab}.\mathsf{CT}[i+\lambda,1-x[i]]\coloneqq
S[i]+\mathsf{lab}[i+\lambda,1-x[i]]$ (134)

for all $i\in[\lambda]$.

  7. 7.

The challenger sends

$\displaystyle\mathsf{CT}\coloneqq\left(\widehat{D_{\lambda}}[m_{0},m_{1}]_{\mathsf{off}},\\{\mathsf{lab}[i,\mathsf{unclone}.\mathsf{CT}_{b}[i]]\\}_{i\in[\lambda]},\\{\mathsf{Lab}.\mathsf{CT}[i,\beta]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},\beta\in\\{0,1\\}}\right)$
(135)

to $\mathcal{A}$.

  8. 8.

$\mathcal{A}$ produces $\rho_{\mathcal{B},\mathcal{C}}$ and sends the
corresponding registers to $\mathcal{B}$ and $\mathcal{C}$.

  9. 9.

$\mathcal{B}$ and $\mathcal{C}$ receives
$\left(x,\\{R[i]\\}_{i\in[\lambda]}\right)$, and outputs $b_{\mathcal{B}}$ and
$b_{\mathcal{C}}$.

  10. 10.

The experiment outputs $1$ if $b_{\mathcal{B}}=b_{\mathcal{C}}=b$, and
otherwise $0$.

Lemma 8.8 follows from the following Propositions 8.10 and 8.11.

###### Proposition 8.10.

If $\Sigma_{\mathsf{RE}}$ is decomposable quantum randomized encoding, then

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb_{0}}=1]-\Pr[\mathsf{Hyb_{1}}=1]}\leq{\mathsf{negl}}(\lambda).$
(136)

###### Proposition 8.11.

If there exists a one-time unclonable secret-key encryption
$\Sigma_{\mathsf{Unclone}}$ with single-bit plaintexts, then

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb}_{1}=1]}\leq\frac{1}{2}+{\mathsf{negl}}(\lambda).$
(137)

∎

###### Proof of Proposition 8.10.

Assume that there exists a QPT adversary
$(\mathcal{A},\mathcal{B},\mathcal{C})$ such that

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb_{0}}=1]-\Pr[\mathsf{Hyb_{1}}=1]}$
(138)

is non-negligible. Then, construct a QPT adversary $\widetilde{\mathcal{A}}$
that breaks the security of $\Sigma_{\mathsf{RE}}$ as follows.

  1. 1.

$\widetilde{\mathcal{A}}$ samples $b\leftarrow\\{0,1\\}$.

  2. 2.

$\widetilde{\mathcal{A}}$ samples $x\leftarrow\\{0,1\\}^{\lambda}$ and
$R[i]\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all $i\in[\lambda]$.

  3. 3.

$\widetilde{\mathcal{A}}$ receives $(m_{0},m_{1})$ from the $\mathcal{A}$.

  4. 4.

$\widetilde{\mathcal{A}}$ computes
$\mathsf{unclone}.\mathsf{CT}_{b}\leftarrow\mathsf{Unclone}.\mathsf{Enc}(1^{\lambda},x,b)$.

  5. 5.

$\widetilde{\mathcal{A}}$ sends
$\left(\\{C_{\lambda,p}[m_{b}],0^{\lambda},x\\},\\{D_{\lambda}[m_{0},m_{1}],\mathsf{unclone}.\mathsf{CT}_{b},x\\}\right)$
to the challenger of $\Sigma_{\mathsf{RE}}$ in Proposition 3.21.

  6. 6.

The challenger samples $b^{*}\leftarrow\\{0,1\\}$, and does the following.

     * •

If $b^{*}=0$, then the challenger computes

$\displaystyle\left(\widehat{C}_{\mathsf{off}},\\{\mathsf{lab}[i]\\}_{i\in[2\lambda]}\right)\leftarrow\mathsf{RE}.\mathsf{Enc}\left(1^{\lambda},C_{\lambda,p}[m_{b}],\left(0^{\lambda},x\right)\right),$
(139)

and sends
$\left(\widehat{C}_{\mathsf{off}},\\{\mathsf{lab}[i]\\}_{i\in[2\lambda]}\right)$
to $\widetilde{\mathcal{A}}$.

     * •

If $b^{*}=1$, then the challenger computes

$\displaystyle\left(\widehat{C}_{\mathsf{off}},\\{\mathsf{lab}[i]\\}_{i\in[2\lambda]}\right)\leftarrow\mathsf{RE}.\mathsf{Enc}\left(1^{\lambda},D_{\lambda,p}[m_{0},m_{1}],\left(\mathsf{unclone}.\mathsf{CT}_{b},x\right)\right),$
(140)

and sends
$\left(\widehat{C}_{\mathsf{off}},\\{\mathsf{lab}[i]\\}_{i\in[2\lambda]}\right)$
to $\widetilde{\mathcal{A}}$.

  7. 7.

$\widetilde{\mathcal{A}}$ samples $S[i]\leftarrow\\{0,1\\}^{\ell(\lambda)}$
for all $i\in[\lambda]$, computes

$\displaystyle\mathsf{Lab}.\mathsf{CT}[i+\lambda,x[i]]\coloneqq
R[i]+\mathsf{lab}[i+\lambda]$ (141)
$\displaystyle\mathsf{Lab}.\mathsf{CT}[i+\lambda,1-x[i]]\coloneqq S[i]$ (142)

for all $i\in[\lambda]$, and runs $\mathcal{A}$ on

$\displaystyle\mathsf{CT}\coloneqq\left(\widehat{C}_{\mathsf{off}},\\{\mathsf{lab}[i]\\}_{i\in[\lambda]},\\{\mathsf{Lab}.\mathsf{CT}[i,\beta]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},\beta\in\\{0,1\\}}\right),$
(143)

and generates $\rho_{\mathcal{B},\mathcal{C}}$.

  8. 8.

$\widetilde{\mathcal{A}}$ sends the corresponding register to $\mathcal{B}$
and $\mathcal{C}$, respectively.

  9. 9.

$\widetilde{\mathcal{A}}$ sends $x$ and $\\{R[i]\\}_{i\in[\lambda]}$ to
$\mathcal{B}$ and $\mathcal{C}$.

  10. 10.

$\mathcal{B}$ and $\mathcal{C}$ outputs $b_{\mathcal{B}}$ and
$b_{\mathcal{C}}$, respectively.

  11. 11.

$\widetilde{\mathcal{A}}$ outputs $1$ if $b=b_{\mathcal{B}}=b_{\mathcal{C}}$,
and outputs $0$ otherwise.

From the construction of $\widetilde{\mathcal{A}}$, if $b^{*}=0$,
$\widetilde{\mathcal{A}}$ perfectly simulates the challenger of
$\mathsf{Hyb_{0}}$. Otherwise, $\widetilde{\mathcal{A}}$ perfectly simulates
the challenger of $\mathsf{Hyb_{1}}$. Furthermore, we have

$\displaystyle
C_{\lambda,p}[m_{b}](0^{\lambda},x)=D_{\lambda}[m_{0},m_{1}](\mathsf{unclone}.\mathsf{CT}_{b},x)=m_{b},$
(144)

and the size of $C_{\lambda,p}$ is equal to $D_{\lambda}[m_{0},m_{1}]$ for an
appropriate polynomial $p$. Therefore, if there exists a QPT adversary
$(\mathcal{A},\mathcal{B},\mathcal{C})$ such that

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb_{0}}=1]-\Pr[\mathsf{Hyb_{1}}=1]}$
(145)

is non-negligible, then it contradicts that $\Sigma_{\mathsf{RE}}$ satisfies
security from Proposition 3.21. ∎

###### Proof of Proposition 8.11.

Assume that there exists a QPT adversary
$(\mathcal{A},\mathcal{B},\mathcal{C})$ such that $\Pr[\mathsf{Hyb_{1}}=1]$ is
non-negligible. Then, construct a QPT adversary
$(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}})$
that breaks the unclonable IND-CPA security of $\Sigma_{\mathsf{unclone}}$ as
follows.

  1. 1.

The challenger of $\Sigma_{\mathsf{unclone}}$ samples $b\leftarrow\\{0,1\\}$.

  2. 2.

$\widetilde{\mathcal{A}}$ samples
$R[i,\beta]\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for all $i\in[\lambda]$ and
$\beta\in\\{0,1\\}$.

  3. 3.

$\widetilde{\mathcal{A}}$ receives $(m_{0},m_{1})$ from the $\mathcal{A}$.

  4. 4.

$\widetilde{\mathcal{A}}$ sends $(0,1)$ to the challenger, and receives
$\mathsf{unclone}.\mathsf{CT}_{b}$, where
$\mathsf{unclone}.\mathsf{CT}_{b}\leftarrow\mathsf{Unclone}.\mathsf{Enc}(1^{\lambda},x,b)$
and $x\leftarrow\\{0,1\\}^{\lambda}$.

  5. 5.

$\widetilde{\mathcal{A}}$ computes
$\widehat{D_{\lambda}}[m_{0},m_{1}]_{\mathsf{off}}$,
$\\{\mathsf{lab}[i,\mathsf{unclone}.\mathsf{CT}_{b}[i]]\\}_{i\in[\lambda]}$,
and
$\\{\mathsf{lab}[i,\beta]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},\beta\in\\{0,1\\}}$.

  6. 6.

$\widetilde{\mathcal{A}}$ computes
$\mathsf{Lab}.\mathsf{CT}[i+\lambda,\beta]\coloneqq
R[i,\beta]+\mathsf{lab}[i+\lambda,\beta]$ for all $i\in[\lambda]$ and
$\beta\in\\{0,1\\}$.

  7. 7.

$\widetilde{\mathcal{A}}$ runs $\mathcal{A}$ on

$\displaystyle\left(\widehat{D_{\lambda}}[m_{0},m_{1}]_{\mathsf{off}},\\{\mathsf{lab}[i,\mathsf{unclone}.\mathsf{CT}_{b}[i]]\\}_{i\in[\lambda]},\\{\mathsf{Lab}.\mathsf{CT}[i,\beta]\\}_{i\in\\{\lambda+1,\cdots,2\lambda\\},\beta\in\\{0,1\\}}\right),$
(146)

obtains $\rho_{\mathcal{B},\mathcal{C}}$, and sends the $\mathcal{B}$ register
and $\\{R[i,\beta]\\}_{i\in[\lambda],\beta\in\\{0,1\\}}$ to $\mathcal{B}$ and
the $\mathcal{C}$ register and
$\\{R[i,\beta]\\}_{i\in[\lambda],\beta\in\\{0,1\\}}$ to $\mathcal{C}$.

  8. 8.

$\widetilde{\mathcal{B}}$ (resp. $\widetilde{\mathcal{C}}$) receives the
secret-key $x$ from the challenger of $\Sigma_{\mathsf{unclone}}$ and sends
$(x,\\{R[i,x[i]]\\}_{i\in[\lambda]})$ and the $\mathcal{B}$ register (resp.
$\mathcal{C}$ register) to $\mathcal{B}$ (resp. $\mathcal{C}$).

  9. 9.

The experiment outputs $1$ if $b=b_{\mathcal{B}}=b_{\mathcal{C}}$ where
$b_{\mathcal{B}}$ and $b_{\mathcal{C}}$ are the outputs of $\mathcal{B}$ and
$\mathcal{C}$, respectively.

From the construction of
$(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}})$,
it perfectly simulates the challenger of $\mathsf{Hyb_{1}}$. Therefore, if
there exists some QPT adversaries $(\mathcal{A},\mathcal{B},\mathcal{C})$ such
that $\Pr[\mathsf{Hyb_{1}}=1]$ is non-negligible, it contradicts that
$\Sigma_{\mathsf{unclone}}$ satisfies unclonable IND-CPA security. ∎

∎

Acknowledgements. TH is supported by JSPS research fellowship and by JSPS
KAKENHI No. JP22J21864.

## References

  * [Aar18] Scott Aaronson.  Shadow tomography of quantum states.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, 50th ACM STOC, pages 325–338. ACM Press, June 2018.
  * [AAS20] Scott Aaronson, Yosi Atia, and Leonard Susskind.  On the hardness of detecting macroscopic superpositions.  Electron. Colloquium Comput. Complex., TR20-146, 2020.
  * [ABJ+19] Prabhanjan Ananth, Saikrishna Badrinarayanan, Aayush Jain, Nathan Manohar, and Amit Sahai.  From FE combiners to secure MPC and back.  In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part I, volume 11891 of LNCS, pages 199–228. Springer, Heidelberg, December 2019\.
  * [AC12] Scott Aaronson and Paul Christiano.  Quantum money from hidden subspaces.  In STOC, pages 41–60. ACM, 2012.
  * [AGQY22] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen.  Pseudorandom (function-like) quantum state generators: New definitions and applications.  In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography, pages 237–265, Cham, 2022. Springer Nature Switzerland.
  * [AJN+16] Prabhanjan Ananth, Aayush Jain, Moni Naor, Amit Sahai, and Eylon Yogev.  Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption.  In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 491–520. Springer, Heidelberg, August 2016.
  * [AJS17] Prabhanjan Ananth, Aayush Jain, and Amit Sahai.  Robust transforming combiners from indistinguishability obfuscation to functional encryption.  In EUROCRYPT (1), pages 91–121. Springer, 2017.
  * [AK21] Prabhanjan Ananth and Fatih Kaleoglu.  Unclonable encryption, revisited.  In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography, pages 299–329, Cham, 2021. Springer International Publishing.
  * [AKL+22] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry.  On the feasibility of unclonable encryption, and more.  In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 212–241, Cham, 2022. Springer Nature Switzerland.
  * [AQY22] Prabhanjan Ananth, Luowen Qian, and Henry Yuen.  Cryptography from pseudorandom quantum states.  In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 208–236, Cham, 2022. Springer Nature Switzerland.
  * [BB84] C. H. Bennett and G. Brassard.  Quantum cryptography: Public key distribution and coin tossing.  In Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, page 175, India, 1984.
  * [BCKM21] James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma.  On the round complexity of secure quantum computation.  In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 406–435, Virtual Event, August 2021. Springer, Heidelberg.
  * [BCQ23] Zvika Brakerski, Ran Canetti, and Luowen Qian.  On the computational hardness needed for quantum cryptography.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 24:1–24:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [BL20] Anne Broadbent and Sébastien Lord.  Uncloneable quantum encryption via oracles.  In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, June 9-12, 2020, Riga, Latvia, volume 158 of LIPIcs, pages 4:1–4:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [BY22] Zvika Brakerski and Henry Yuen.  Quantum garbled circuits.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 804–817, New York, NY, USA, 2022. Association for Computing Machinery.
  * [CHK05] Ran Canetti, Shai Halevi, and Jonathan Katz.  Adaptively-secure, non-interactive public-key encryption.  In Joe Kilian, editor, TCC 2005, volume 3378 of LNCS, pages 150–168. Springer, Heidelberg, February 2005.
  * [CLS01] Claude Crépeau, Frédéric Légaré, and Louis Salvail.  How to convert the flavor of a quantum bit commitment.  In Birgit Pfitzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, pages 60–77. Springer, Heidelberg, May 2001.
  * [CX22] Shujiao Cao and Rui Xue.  On constructing one-way quantum state generators, and more.  Cryptology ePrint Archive, Paper 2022/1323, 2022.  https://eprint.iacr.org/2022/1323.
  * [DH76] Whitfield Diffie and Martin E. Hellman.  New directions in cryptography.  IEEE Transactions on Information Theory, 22(6):644–654, 1976\.
  * [DMS00] Paul Dumais, Dominic Mayers, and Louis Salvail.  Perfectly concealing quantum bit commitment from any quantum one-way permutation.  In Bart Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, pages 300–315. Springer, Heidelberg, May 2000.
  * [ElG85] Taher ElGamal.  A public key cryptosystem and a signature scheme based on discrete logarithms.  IEEE Transactions on Information Theory, 31:469–472, 1985.
  * [FGH+12] Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter W. Shor.  Quantum money from knots.  In Shafi Goldwasser, editor, ITCS 2012, pages 276–289. ACM, January 2012.
  * [GLSV21] Alex B. Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan.  Oblivious transfer is in MiniQCrypt.  In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, pages 531–561. Springer, Heidelberg, October 2021.
  * [GTK16] Shafi Goldwasser and Yael Tauman Kalai.  Cryptographic assumptions: A position paper.  In Eyal Kushilevitz and Tal Malkin, editors, Theory of Cryptography, pages 505–522, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.
  * [Her05] Amir Herzberg.  On tolerant cryptographic constructions.  In Alfred Menezes, editor, Topics in Cryptology – CT-RSA 2005, pages 172–190, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [HKM+23] Taiga Hiroka, Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, Tapas Pal, and Takashi Yamakawa.  Certified everlasting secure collusion-resistant functional encryption, and more.  Cryptology ePrint Archive, Paper 2023/236, 2023.  https://eprint.iacr.org/2023/236.
  * [HKN+05] Danny Harnik, Joe Kilian, Moni Naor, Omer Reingold, and Alon Rosen.  On robust combiners for oblivious transfer and other primitives.  In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 96–113. Springer, Heidelberg, May 2005.
  * [HMNY21] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa.  Quantum encryption with certified deletion, revisited: Public key, attribute-based, and classical communication.  In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, pages 606–636, Cham, 2021. Springer International Publishing.
  * [HMY23] Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa.  From the hardness of detecting superpositions to cryptography: Quantum public key encryption and commitments.  In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, pages 639–667, Cham, 2023. Springer Nature Switzerland.
  * [JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song.  Pseudorandom quantum states.  In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 126–152. Springer, Heidelberg, August 2018.
  * [JMS20] Aayush Jain, Nathan Manohar, and Amit Sahai.  Combiners for functional encryption, unconditionally.  In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 141–168. Springer, Heidelberg, May 2020.
  * [Kan18] Daniel M. Kane.  Quantum money from modular forms.  arXiv:1809.05925, 2018.
  * [KNTY19] Fuyuki Kitagawa, Ryo Nishimaki, Keisuke Tanaka, and Takashi Yamakawa.  Adaptively secure and succinct functional encryption: Improving security and efficiency, simultaneously.  In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 521–551. Springer, Heidelberg, August 2019.
  * [KQST23] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal.  Quantum cryptography in algorithmica.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1589–1602, New York, NY, USA, 2023. Association for Computing Machinery.
  * [Kre21] William Kretschmer.  Quantum Pseudorandomness and Classical Complexity.  In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [KSS22] Daniel M. Kane, Shahed Sharif, and Alice Silverberg.  Quantum money from quaternion algebras, 2022.
  * [KT23] Dakshita Khurana and Kabir Tomer.  Commitments from quantum one-wayness, 2023.
  * [LC97] Hoi-Kwong Lo and H. F. Chau.  Is quantum bit commitment really possible?  Phys. Rev. Lett., 78:3410–3413, 1997.
  * [Lev85] Leonid A. Levin.  One-way functions and pseudorandom generators.  In 17th ACM STOC, pages 363–365. ACM Press, May 1985.
  * [LMZ23] Jiahui Liu, Hart Montgomery, and Mark Zhandry.  Another round of breaking and making quantum money:.  In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, pages 611–638, Cham, 2023. Springer Nature Switzerland.
  * [May97] Dominic Mayers.  Unconditionally secure quantum bit commitment is impossible.  Phys. Rev. Lett., 78:3414–3417, 1997.
  * [MY22a] Tomoyuki Morimae and Takashi Yamakawa.  One-wayness in quantum cryptography.  Cryptology ePrint Archive, Paper 2022/1336, 2022.  https://eprint.iacr.org/2022/1336.
  * [MY22b] Tomoyuki Morimae and Takashi Yamakawa.  Quantum commitments and signatures without one-way functions.  In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 269–295, Cham, 2022. Springer Nature Switzerland.
  * [Reg05] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84–93. ACM Press, May 2005.
  * [WW23] Brent Waters and Daniel Wichs.  Universal amplification of kdm security: From 1-key circular to multi-key kdm.  Cryptology ePrint Archive, Paper 2023/1058, 2023.  https://eprint.iacr.org/2023/1058.
  * [Yan22] Jun Yan.  General properties of quantum bit commitments (extended abstract).  In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, pages 628–657, Cham, 2022. Springer Nature Switzerland.
  * [Zha19] Mark Zhandry.  Quantum lightning never strikes the same state twice.  In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 408–438. Springer, Heidelberg, May 2019.
  * [Zha23a] Mark Zhandry.  Quantum minimalism (talk).  https://www.youtube.com/watch?v=7cqnrASfjco&ab_channel=SimonsInstitute, 2023\.
  * [Zha23b] Mark Zhandry.  Quantum money from abelian group actions.  IACR Cryptol. ePrint Arch., 2023:1097, 2023.

##  Appendix A Proof of Proposition 4.12

Assume that there exists an OWSG. Then, there exists a set of classical Turing
machines $\mathcal{M}\coloneqq(x,y,z)$ such that
$\Sigma[\mathcal{M}]\coloneqq(\mathsf{KeyGen}[x],\mathsf{StateGen}[y],\mathsf{Vrfy}[z])$
satisfies correctness and security because OWSG is a set of uniform QPT
algorithms. Let $c_{x}$, and $c_{y}$, and $c_{z}$ be a constant such that $x$,
$y$, and $z$ halts within $\lambda^{c_{x}}$, $\lambda^{c_{y}}$, and
$\lambda^{c_{z}}$ steps for all sufficiently large $\lambda\in\mathbb{N}$,
respectively. For simplicity, let us assume that $c_{x}\geq c_{y}\geq c_{z}$.
Note that the same argument goes through in the other cases.

For the set of uniform QPT algorithms
$\Sigma[\mathcal{M}]=(\mathsf{KeyGen}[x],\mathsf{StateGen}[y],\mathsf{Vrfy}[z])$,
$\Sigma[\mathcal{M}^{*}]\coloneqq(\mathsf{KeyGen}[x^{*}],\mathsf{StateGen}[y^{*}],\allowbreak\mathsf{Vrfy}[z^{*}])$
is the set of uniform algorithms working as follows:

$\mathsf{KeyGen}[x^{*}](1^{\lambda})$:

  * •

It runs a classical Turing machine $x$ on $1^{\kappa}$ and obtain a general
quantum circuit $C[x]_{\kappa}$, where the $\kappa\in\mathbb{N}$ is the
largest integer such that $\kappa+\kappa^{c_{x}}\leq\lambda$.

  * •

Output $k$, which is the output of $C[x]_{\kappa}$.

$\mathsf{StateGen}[y^{*}](1^{\lambda},k)$:

  * •

It runs a classical Turing machine $y$ on $(1^{\kappa},k)$ and obtain a
general quantum circuit $C[y]_{\kappa,k}$, where the $\kappa\in\mathbb{N}$ is
the largest integer such that $\kappa+\kappa^{c_{x}}\leq\lambda$.

  * •

Output $\psi_{k}$, which is the output of $C[y]_{\kappa,k}$.

$\mathsf{Vrfy}[z^{*}](1^{\lambda},k,\psi_{k})$:

  * •

It runs a classical Turing machine $z$ on
$(1^{\kappa},k,\absolutevalue{\psi_{k}})$ and obtain a general quantum circuit
$C[z]_{\kappa,k,\absolutevalue{\psi_{k}}}$, where the $\kappa\in\mathbb{N}$ is
the largest integer such that $\kappa+\kappa^{c_{x}}\leq\lambda$.

  * •

Output $\top$ if $1\leftarrow
C[z]_{\kappa,k,\absolutevalue{\psi_{k}}}(\psi_{k})$, and output $\bot$ if
$0\leftarrow C[z]_{\kappa,k,\absolutevalue{\psi_{k}}}(\psi_{k})$.

We can see that $x^{*}$, $y^{*}$, and $z^{*}$ halts within $\lambda^{3}$ steps
for all sufficiently large $\lambda\in\mathbb{N}$. Given $1^{\lambda}$,
$x^{*}$ first computes $\kappa$ within $O(\lambda^{2})$ steps. Furthermore,
$x(1^{\kappa})$ halts within $\kappa^{c_{x}}\leq\lambda$ steps. Overall,
$x^{*}$ halts within $O(\lambda^{2})$ steps. For the same reason, $y^{*}$ and
$z^{*}$ also halts within $O(\lambda^{2})$ steps. Therefore, for all
sufficiently large security parameters $\lambda\in\mathbb{N}$,
$x^{*}(1^{\lambda})$, $y^{*}(1^{\lambda})$, and $z^{*}(1^{\lambda})$ halt
within $\lambda^{3}$ steps. Apparently, $\Sigma[\mathcal{M}^{*}]$ satisfies
correctness if $\Sigma[\mathcal{M}]$ satisfies correctness.

Furthermore, by a standard hybrid argument, we can show that the construction
satisfies security as follows. Suppose that $\Sigma[\mathcal{M}^{*}]$ does not
satisfy security and show that $\Sigma[\mathcal{M}]$ does not satisfy
security. Since we assume that $\Sigma[\mathcal{M}^{*}]$ does not satisfy
security, there exists a polynomial $t$, a constant $C$ and a QPT adversary
$\mathcal{A}$ such that

$\displaystyle\Pr[\top\leftarrow\mathsf{Vrfy}[z^{*}](1^{\lambda+\lambda^{c_{x}}},k^{*},\psi_{k}):\begin{array}[]{ll}k\leftarrow\mathsf{KeyGen}[x^{*}](1^{\lambda+\lambda^{c_{x}}})\\\
\psi_{k}\leftarrow\mathsf{StateGen}[y^{*}](1^{\lambda+\lambda^{c_{x}}})\\\
k^{*}\leftarrow\mathcal{A}(\psi_{k}^{\otimes
t(\lambda+\lambda^{c_{x}})})\end{array}]\geq 1/(\lambda+\lambda^{c_{x}})^{C}$
(150)

for infinitely many security parameters $\lambda$. Let $t^{\prime}$ be a
polynomial such that $t^{\prime}(\lambda)\geq t(\lambda+\lambda^{c_{x}})$ for
all $\lambda\in\mathbb{N}$. Now, we construct a QPT adversary $\mathcal{B}$
that breaks $\Sigma[\mathcal{M}]$ as follows.

  1. 1.

$\mathcal{B}$ first receives $\psi_{k}^{\otimes t^{\prime}(\lambda)}$, where
$k\leftarrow\mathsf{KeyGen}[x](1^{\lambda})$ and
$\psi_{k}\leftarrow\mathsf{StateGen}[y](1^{\lambda},k)$.

  2. 2.

$\mathcal{B}$ runs $k^{*}\leftarrow\mathcal{A}(\psi_{k}^{\otimes
t(\lambda+\lambda^{c_{x}})})$.

  3. 3.

$\mathcal{B}$ outputs $k^{*}$.

From the construction of
$(\mathsf{KeyGen}[x^{*}],\mathsf{StateGen}[y^{*}],\mathsf{Vrfy}[z^{*}])$,
$(\mathsf{KeyGen}[x^{*}](1^{\lambda+\lambda^{c_{x}}}),\mathsf{StateGen}[y^{*}](1^{\lambda+\lambda^{c_{x}}},k),\allowbreak\mathsf{Vrfy}[z^{*}](1^{\lambda+\lambda^{c_{x}}},k,\psi_{k}))$
works in the same way as
$(\mathsf{KeyGen}[x](1^{\lambda}),\mathsf{StateGen}[y](1^{\lambda},k),\mathsf{Vrfy}[z](1^{\lambda},k,\psi_{k}))$.
Therefore, there exists some constant $D$ such that

$\displaystyle\Pr[\top\leftarrow\mathsf{Vrfy}[z](1^{\lambda},k^{*},\psi_{k}):\begin{array}[]{ll}k\leftarrow\mathsf{KeyGen}[x](1^{\lambda})\\\
\psi_{k}\leftarrow\mathsf{StateGen}[y](1^{\lambda},k)\\\
k^{*}\leftarrow\mathcal{B}(\psi_{k}^{\otimes
t^{\prime}(\lambda)})\end{array}]$ (154)
$\displaystyle=\Pr[\top\leftarrow\mathsf{Vrfy}[z^{*}](1^{\lambda+\lambda^{c_{x}}},k^{*},\psi_{k}):\begin{array}[]{ll}k\leftarrow\mathsf{KeyGen}[x^{*}](1^{\lambda+\lambda^{c_{x}}})\\\
\psi_{k}\leftarrow\mathsf{StateGen}[y^{*}](1^{\lambda+\lambda^{c_{x}}},k)\\\
k^{*}\leftarrow\mathcal{A}(\psi_{k}^{\otimes
t(\lambda+\lambda^{c_{x}})})\end{array}]\geq
1/(\lambda+\lambda^{c_{x}})^{C}\geq 1/\lambda^{D}$ (158)

for infinitely many $\lambda$. This contradicts that $\Sigma[\mathcal{M}]$
satisfies security. Therefore, $\Sigma[\mathcal{M}^{*}]$ satisfies security.

Therefore,
$\Sigma[\mathcal{M}^{*}]=(\mathsf{KeyGen}[x^{*}],\mathsf{StateGen}[y^{*}],\mathsf{Vrfy}[z^{*}])$
is a OWSG scheme, where $x^{*}$, $y^{*}$, and $z^{*}$ halts within
$\lambda^{3}$ steps.

##  Appendix B Proof of Lemma 5.3

###### Proof of Lemma 5.3.

We describe $\Sigma^{*}=(\mathsf{Mint}^{*},\mathsf{Vrfy}^{*})$.

$\mathsf{Mint}^{*}(1^{\lambda})$:

  * •

Run $\mathsf{Check}(\Sigma)$, where $\mathsf{Check}$ works as follows:

    * –

Run $(s_{i},\rho_{s_{i}})\leftarrow\mathsf{Mint}(1^{\lambda})$ for all
$i\in[\lambda]$.

    * –

Run $\mathsf{Vrfy}(1^{\lambda},s_{i},\rho_{s_{i}})$ for all $i\in[\lambda]$.

    * –

Output $1$ if the number of
$\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s_{i},\rho_{s_{i}})$ is at least
$\frac{11\lambda}{12}$, and output $0$ otherwise.

  * •

If $1\leftarrow\mathsf{Check}(\Sigma)$, then run
$(s_{i},\rho_{s_{i}})\leftarrow\mathsf{Mint}(1^{\lambda})$ for all
$i\in[\lambda]$ and output $s^{*}\coloneqq\\{s_{i}\\}_{i\in[\lambda]}$ and
$\rho_{s}^{*}\coloneqq\bigotimes_{i\in[\lambda]}\rho_{s_{i}}$.

  * •

If $0\leftarrow\mathsf{Check}(\Sigma)$, then run
$(s_{i},\rho_{s_{i}})\leftarrow\mathsf{Mint}(1^{\lambda})$ for all
$i\in[\lambda]$ and output $s^{*}\coloneqq\top$ and
$\rho_{s}^{*}\coloneqq\bigotimes_{i\in[\lambda]}\rho_{s_{i}}$.

$\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho)$:

  * •

Let $\rho$ be a quantum state on the $\lambda$ registers $R[1]\cdots
R[\lambda]$.

  * •

If $s^{*}=\top$, output $\top$.

  * •

If $s^{*}\neq\top$, then parse $s^{*}=\\{s_{i}\\}_{i\in[\lambda]}$, run
$\mathsf{Vrfy}(1^{\lambda},s_{i},\cdot)$ on the $R[i]$ register and obtains
$b[i]$ for all $i\in[\lambda]$. Output $\top$ if the number of $b[i]=\top$ is
at least $\frac{3\lambda}{4}$.

We have the following Propositions B.1, B.2 and B.3.

###### Proposition B.1.

If $\Sigma$ satisfies efficiency, then $\Sigma^{*}$ satisfies efficiency.

###### Proposition B.2.

$\Sigma^{*}$ satisfies correctness.

###### Proposition B.3.

If $\Sigma$ satisfies efficiency, correctness, and security, then $\Sigma^{*}$
satisfies security.

We omit the proof of Proposition B.1. To show Proposition B.2, we use the
following Lemma B.4.

###### Lemma B.4 (Hoeffding’s inequality).

Let $X_{i}\in\\{0,1\\}$ be a two-outcome independent random variable, and let
$S_{n}\coloneqq\sum_{i\in[n]}X_{i}$. Then, we have

$\displaystyle\Pr[\absolutevalue{S_{n}-\operatorname*{\mathbb{E}}[S_{n}]}\geq
t]\leq 2\exp(-2t^{2}/n).$ (159)

###### Proof of Proposition B.2.

First, assume that
$\Pr[\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s,\rho_{s}):(s,\rho_{s})\leftarrow\mathsf{Mint}(1^{\lambda})]<5/6$,
and compute
$\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s^{*}}):(s^{*},\rho_{s^{*}})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})]$.

$\displaystyle\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*}):(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})]$
(160)
$\displaystyle=\sum_{b,s^{*}}\bigg{(}\Pr[b\leftarrow\mathsf{Check}(\Sigma)]\Pr[(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\mid
b\leftarrow\mathsf{Check}(\Sigma)]$ (161) $\displaystyle\hskip
42.67912pt\cdot\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*})\mid(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\wedge
b\leftarrow\mathsf{Check}(\Sigma)]\bigg{)}$ (162)
$\displaystyle\geq\bigg{(}\Pr[0\leftarrow\mathsf{Check}(\Sigma)]\Pr[(\top,\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\mid
0\leftarrow\mathsf{Check}(\Sigma)]$ (163) $\displaystyle\hskip
42.67912pt\cdot\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},\top,\rho_{s}^{*})\mid(\top,\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\wedge
0\leftarrow\mathsf{Check}(\Sigma)]\bigg{)}$ (164)
$\displaystyle=\Pr[0\leftarrow\mathsf{Check}(\Sigma)]$ (165)
$\displaystyle\geq 1-2\exp(-\lambda/72).$ (166)

Here, in the second equation, we have used that
$\mathsf{Vrfy}^{*}(1^{\lambda},s,\rho)$ always outputs $\top$ if $s=\top$ and
$(\top,\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})$ if
$0\leftarrow\mathsf{Check}(\Sigma)$ and in the second inequality, we have used
that $\Pr[0\leftarrow\mathsf{Check}(\Sigma)]\geq 1-2\exp(-\lambda/72)$ when
$\Pr[\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s,\rho_{s}):(s,\rho_{s})\leftarrow\mathsf{Mint}(1^{\lambda})]<5/6$,
which we prove later.

Next, assume that
$\Pr[\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s,\rho_{s}):(s,\rho_{s})\leftarrow\mathsf{Mint}(1^{\lambda})]\geq
5/6$, and compute
$\Pr\allowbreak[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*}):(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})]$.

$\displaystyle\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*}):(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})]$
(167)
$\displaystyle=\sum_{b,s^{*}}\bigg{(}\Pr[b\leftarrow\mathsf{Check}(\Sigma)]\Pr[(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\mid
b\leftarrow\mathsf{Check}(\Sigma)]$ (168) $\displaystyle\hskip
42.67912pt\cdot\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*})\mid(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\wedge
b\leftarrow\mathsf{Check}(\Sigma)]\bigg{)}$ (169)
$\displaystyle=\bigg{(}\sum_{s^{*}\neq\top}\Pr[1\leftarrow\mathsf{Check}(\Sigma)]\Pr[(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\mid
1\leftarrow\mathsf{Check}(\Sigma)]$ (170) $\displaystyle\hskip
42.67912pt\cdot\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*})\mid(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\wedge
1\leftarrow\mathsf{Check}(\Sigma)]\bigg{)}+\Pr[0\leftarrow\mathsf{Check}(\Sigma)]$
(171) $\displaystyle=1-\Pr[1\leftarrow\mathsf{Check}(\Sigma)]$ (172)
$\displaystyle\cdot\Bigg{(}1-\bigg{(}\sum_{s^{*}\neq\top}\Pr[(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\mid
1\leftarrow\mathsf{Check}(\Sigma)]\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*})\mid(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\wedge
1\leftarrow\mathsf{Check}(\Sigma)]\bigg{)}\Bigg{)}$ (173)
$\displaystyle\geq\bigg{(}\sum_{s^{*}\neq\top}\Pr[(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\mid
1\leftarrow\mathsf{Check}(\Sigma)]\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*})\mid(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\wedge
1\leftarrow\mathsf{Check}(\Sigma)]\bigg{)}$ (174) $\displaystyle\geq
1-2\exp(-\lambda/72)).$ (175)

Here, in the second equation, we have used that $\mathsf{Vrfy}^{*}$ outputs
$\top$ if $\mathsf{Check}(\Sigma)$ outputs 0, and in the final inequality, we
have used that

$\displaystyle\sum_{s^{*}\neq\top}\Pr\allowbreak[(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\mid
1\leftarrow\mathsf{Check}(\Sigma)]\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*})\mid(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\wedge
1\leftarrow\mathsf{Check}(\Sigma)]$ (176) $\displaystyle\geq
1-2\exp(-\lambda/72)$ (177)

when
$\Pr\allowbreak[\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s,\rho_{s}):(s,\rho_{s})\leftarrow\mathsf{Mint}(1^{\lambda})]\geq
5/6$, which we will prove later. Therefore, the $\Sigma^{*}$ satisfies the
correctness.

Now, we will prove the part we skipped. That is, we show
$\Pr[0\leftarrow\mathsf{Check}(\Sigma)]\geq 1-2\exp(-\lambda/72)$ when
$\Pr[\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s,\rho_{s}):(s,\rho_{s})\leftarrow\mathsf{Mint}(1^{\lambda})]<5/6$.
We consider the random variable $X_{i}$ as $1$ if
$\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s_{i},\rho_{s_{i}})$ for the $i$-th
running of the verification algorithm while running $\mathsf{Check}$, and
consider $X_{i}$ as $0$ if
$\bot\leftarrow\mathsf{Vrfy}(1^{\lambda},s_{i},\rho_{s_{i}})$. If we denote
$S_{\lambda}\coloneqq\sum_{i\in[\lambda]}X_{i}$, then
$1\leftarrow\mathsf{Check}(\Sigma)$ if and only if
$S_{\lambda}\geq\frac{11\lambda}{12}$. On the other hand, we have
$\operatorname*{\mathbb{E}}[S_{\lambda}]<\frac{5\lambda}{6}$ because
$\Pr[\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s,\rho_{s}):(s,\rho_{s})\leftarrow\mathsf{Mint}(1^{\lambda})]<5/6$.
Therefore, we need to have
$\absolutevalue{S_{\lambda}-\operatorname*{\mathbb{E}}[S_{\lambda}]}\geq\frac{\lambda}{12}$
for $S_{\lambda}\geq\frac{11\lambda}{12}$. Therefore, by applying Lemma B.4,
we have

$\displaystyle\Pr[1\leftarrow\mathsf{Check}(\Sigma)]\leq\Pr[\absolutevalue{S_{\lambda}-\operatorname*{\mathbb{E}}[S_{\lambda}]}\geq\frac{\lambda}{12}]\leq
2\exp(-\frac{\lambda}{72}).$ (178)

In the same way, we can prove that

$\displaystyle\bigg{(}\sum_{s^{*}\neq\top}\Pr[(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\mid
1\leftarrow\mathsf{Check}(\Sigma)]\Pr[\top\leftarrow\mathsf{Vrfy}^{*}(1^{\lambda},s^{*},\rho_{s}^{*})\mid(s^{*},\rho_{s}^{*})\leftarrow\mathsf{Mint}^{*}(1^{\lambda})\wedge
1\leftarrow\mathsf{Check}(\Sigma)]\bigg{)}$ (179) $\displaystyle\geq
1-2\exp(-\lambda/72))$ (180)

when
$\Pr[\top\leftarrow\mathsf{Vrfy}(1^{\lambda},s,\rho_{s}):(s,\rho_{s})\leftarrow\mathsf{Mint}(1^{\lambda})]\geq
5/6$. ∎

###### Proof of Proposition B.3.

Let us introduce the following sequence of hybrids as follows.

$\mathsf{Hyb_{0}}$:

This is the original security experiment of $\Sigma^{*}$.

  1. 1.

The challenger first runs $\mathsf{Check}(\Sigma)$.

  2. 2.

The challenger does the following.

     * •

If $1\leftarrow\mathsf{Check}(\Sigma)$, then run
$(s_{i},\rho_{s_{i}})\leftarrow\mathsf{Mint}(1^{\lambda})$ for all
$i\in[\lambda]$ and send
$(\\{s_{i}\\}_{i\in[\lambda]},\bigotimes_{i\in[\lambda]}\rho_{s_{i}})$ to
$\mathcal{A}$.

     * •

If $0\leftarrow\mathsf{Check}(\Sigma)$, then run
$(s_{i},\rho_{s_{i}})\leftarrow\mathsf{Mint}(1^{\lambda})$ for all
$i\in[\lambda]$ and send $(\bot,\bigotimes_{i\in[\lambda]}\rho_{s_{i}})$ to
$\mathcal{A}$.

  3. 3.

$\mathcal{A}$ sends $\sigma$ consisting of $2\lambda$ registers $\\{R[1]\cdots
R[2\lambda]\\}$.

  4. 4.

The challenger does the following.

     * •

If $1\leftarrow\mathsf{Check}(\Sigma)$, then run
$\mathsf{Vrfy}(1^{\lambda},s_{i},\cdot)$ on the $R[i]$ register and obtain
$b[i]$ for all $i\in[\lambda]$. Set $A=1$ if the number of $i\in[\lambda]$
such that $b[i]=\top$ is at least $3\lambda/4$, and set $A=0$ otherwise. Run
$\mathsf{Vrfy}(1^{\lambda},s_{i},\cdot)$ on the $R[i+\lambda]$ register and
obtain $b[i+\lambda]$ for all $i\in[\lambda]$. Set $B=1$ if the number of
$i\in[\lambda]$ such that $b[i+\lambda]=\top$ is at least $3\lambda/4$, and
set $B=0$ otherwise. If $A=B=1$, then the challenge outputs $\top$, and
outputs $\bot$ otherwise.

     * •

If $0\leftarrow\mathsf{Check}(\Sigma)$, then the challenger always outputs
$\top$.

$\mathsf{Hyb_{1}}$:

This is the same as $\mathsf{Hyb_{0}}$ except that the challenger always
behaves as the case of $1\leftarrow\mathsf{Check}(\Sigma)$.

It is sufficient to show that

$\displaystyle\Pr[\mathsf{Hyb_{0}}=1]\leq{\mathsf{negl}}(\lambda).$ (181)

Because $\Sigma$ satisfies correctness, $1\leftarrow\mathsf{Check}(\Sigma)$
occurs with overwhelming probability. Therefore, we have

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb_{0}}=1]-\Pr[\mathsf{Hyb_{1}}=1]}\leq{\mathsf{negl}}(\lambda).$
(182)

Furthermore, we can show that

$\displaystyle\Pr[\mathsf{Hyb_{1}}=1]\leq{\mathsf{negl}}(\lambda)$ (183)

as long as $\Sigma$ satisfies security as follows. For contradiction assume
that there exists a QPT adversary $\mathcal{A}$ such that

$\displaystyle\Pr[\mathsf{Hyb_{1}}=1]$ (184)

is non-negligible, and then construct a QPT adversary $\mathcal{B}$ that
breaks $\Sigma$ as follows.

  1. 1.

$\mathcal{B}$ receives $(s,\rho_{s})$ from the challenger of $\Sigma$.

  2. 2.

$\mathcal{B}$ samples $i^{*}\in[\lambda]$, and sets $s_{i^{*}}=s$ and
$\rho_{s_{i^{*}}}\coloneqq\rho_{s}$.

  3. 3.

$\mathcal{B}$ generates
$(s_{i},\rho_{s_{i}})\leftarrow\mathsf{Mint}(1^{\lambda})$ for all
$i\in[\lambda]\setminus\\{i^{*}\\}$, and sends
$\left(\\{s_{j}\\}_{j\in[\lambda]},\bigotimes_{j\in[\lambda]}\rho_{s_{j}}\right)$
to $\mathcal{A}$.

  4. 4.

$\mathcal{B}$ receives $\sigma$ consisting of $2\lambda$ registers
$R[1],\cdots,R[2\lambda]$.

  5. 5.

For all $i\in[\lambda]\setminus\\{i^{*}\\}$, $\mathcal{B}$ runs
$\mathsf{Vrfy}(1^{\lambda},s_{i},\cdot)$ on the $R[i]$ and $R[i+\lambda]$
registers, and obtains $b[i]$ and $b[i+\lambda]$, respectively.

  6. 6.

$\mathcal{B}$ sends the $R[i^{*}]$ and $R[i^{*}+\lambda]$ registers to the
challenger, and the challenger runs
$\mathsf{Vrfy}(1^{\lambda},s_{i^{*}},\cdot)$ on the $R[i^{*}]$ and
$R[i^{*}+\lambda]$ registers, and obtains $b[i^{*}]$ and $b[i^{*}+\lambda]$.

Clearly, $\mathcal{B}$ simulates the challenger of $\mathsf{Hyb_{1}}$. We
write $\mathsf{First}$ to mean the event such that the number of
$i\in[\lambda]$ that satisfies $b[i]=\top$ is at least $3\lambda/4$.
Similarly, we write $\mathsf{Second}$ to mean the event such that the number
of $i\in[\lambda]$ that satisfies $b[i+\lambda]=\top$ is at least
$3\lambda/4$. Because $\Pr[\mathsf{Hyb_{1}}=1]$ is non-negligible, both
$\mathsf{First}$ and $\mathsf{Second}$ occur at the same time with non-
negligible probability. This implies that, with non-negligible probability,
the number of $i\in[\lambda]$ such that $b[i]=b[i+\lambda]=\top$ is at least
$\lambda/2$. Because $i^{*}$ is uniformly random and independent from
$\mathcal{A}$, we have $b[i^{*}]=b[i^{*}+\lambda]=\top$ with non-negligible
probability. This contradicts that $\Sigma$ satisfies security. Therefore, we
have $\Pr[\mathsf{Hyb_{1}}=1]\leq{\mathsf{negl}}(\lambda)$. ∎

∎

##  Appendix C Proof of Lemma 3.11

###### Proof of Lemma 3.11.

We prove that if the commitment
$\\{Q_{0}(\lambda),Q_{1}(\lambda)\\}_{\lambda\in\mathbb{N}}$ satisfies $c$-X
hiding, then
$\\{\widetilde{Q}_{0}(\lambda),\widetilde{Q}_{1}(\lambda)\\}_{\lambda\in\mathbb{N}}$
satisfies $\sqrt{c}$-X binding, where $X\in\\{$computational,
statistical$\\}$. Because the same argument goes through, we consider the case
where $X=\mbox{statistical}$. Below, we fix a security parameter, and write
$(Q_{0},Q_{1})$ and $(\widetilde{Q_{0}},\widetilde{Q_{1}})$ to mean
$(Q_{0}(\lambda),Q_{1}(\lambda))$ and
$(\widetilde{Q_{0}}(\lambda),\widetilde{Q_{1}}(\lambda))$, respectively.

First, let us introduce the following Theorem C.1.

###### Theorem C.1 (Equivalence between swapping and distinguishing [AAS20,
HMY23]).

Let $\ket{x_{i}}$, $\ket{y_{i}}$ be orthogonal $n$-qubit states and
$\ket{\tau_{i}}$ be an $m$-qubit state. Let $U$ be a polynomial-time
computable unitary over $(n+m)$-qubit states and define $\Gamma$ as

$\displaystyle\Gamma\coloneqq\norm{(\bra{y}\otimes I^{\otimes
m})U\ket{x}\ket{\tau}+(\bra{x}\otimes I^{\otimes m})U\ket{y}\ket{\tau}}_{1}.$
(185)

Then, there exists a non-uniform QPT distinguisher $\mathcal{A}$ with advice
$\ket{\tau^{\prime}}=\ket{\tau}\otimes\frac{\ket{x}\ket{0}+\ket{y}\ket{1}}{\sqrt{2}}$
that distinguishes $\ket{\psi}=\frac{\ket{x}+\ket{y}}{\sqrt{2}}$ and
$\ket{\phi}=\frac{\ket{x}-\ket{y}}{\sqrt{2}}$ with advantage
$\frac{\Gamma^{2}}{4}$. Moreover, if $U$ does not act on some qubits, then
$\mathcal{A}$ also does not act on those qubits.

Let us assume that
$\\{\widetilde{Q_{0}}(\lambda),\widetilde{Q_{1}}(\lambda)\\}_{\lambda\in\mathbb{N}}$
is not $\sqrt{c}$-statistical biding, and let $d$ be some constant that
satisfies $d\geq\sqrt{c}$. Then, there exists a unitary
$U_{\mathbf{\widetilde{R}Z}}$ over $\mathbf{\widetilde{R}}=\mathbf{C}$ and an
ancillary register $\mathbf{Z}$ and a state $\ket{\tau}_{\mathbf{Z}}$ such
that

$\displaystyle\norm{((\bra{0}\widetilde{Q_{1}}^{\dagger})_{\mathbf{\widetilde{CR}}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{\widetilde{C}}}\otimes
U_{\mathbf{\widetilde{R}Z}})((\widetilde{Q_{0}}\ket{0})_{\mathbf{\widetilde{CR}}}\ket{\tau}_{\mathbf{Z}})}_{1}\geq
d.$ (186)

We observe that $U$ does not act on $\mathbf{D}$, and thus it cannot cause any
interference between states that take $0$ and $1$ in $\mathbf{D}$. Therefore,
we have

$\displaystyle((\bra{0}\widetilde{Q}_{1}^{\dagger})_{\mathbf{\widetilde{CR}}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{\widetilde{C}}}\otimes
U_{\mathbf{\widetilde{R}Z}})(\widetilde{Q}_{0}\ket{0}_{\mathbf{\widetilde{CR}}}\ket{\tau}_{\mathbf{Z}})$
(187)
$\displaystyle=\frac{1}{2}\left(\begin{array}[]{ll}((\bra{0}Q_{1}^{\dagger})_{\mathbf{CR}}\bra{0}_{\mathbf{D}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{R,D}}\otimes
U_{\mathbf{C,Z}})(Q_{0}\ket{0}_{\mathbf{CR}}\ket{0}_{\mathbf{D}}\ket{\tau}_{\mathbf{Z}})\\\
-((\bra{0}Q_{1}^{\dagger})_{\mathbf{CR}}\bra{0}_{\mathbf{D}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{R,D}}\otimes
U_{\mathbf{C,Z}})(Q_{0}\ket{0}_{\mathbf{CR}}\ket{0}_{\mathbf{D}}\ket{\tau}_{\mathbf{Z}})\end{array}\right).$
(190)

Similarly, we have

$\displaystyle((\bra{0}\widetilde{Q}_{0}^{\dagger})_{\mathbf{\widetilde{CR}}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{\widetilde{C}}}\otimes
U_{\mathbf{\widetilde{R}Z}})(\widetilde{Q}_{1}\ket{0}_{\mathbf{\widetilde{CR}}}\ket{\tau}_{\mathbf{Z}})$
(191)
$\displaystyle=\frac{1}{2}\left(\begin{array}[]{ll}((\bra{0}Q_{1}^{\dagger})_{\mathbf{CR}}\bra{0}_{\mathbf{D}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{R,D}}\otimes
U_{\mathbf{C,Z}})(Q_{0}\ket{0}_{\mathbf{CR}}\ket{0}_{\mathbf{D}}\ket{\tau}_{\mathbf{Z}})\\\
-((\bra{0}Q_{1}^{\dagger})_{\mathbf{CR}}\bra{0}_{\mathbf{D}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{R,D}}\otimes
U_{\mathbf{C,Z}})(Q_{0}\ket{0}_{\mathbf{CR}}\ket{0}_{\mathbf{D}}\ket{\tau}_{\mathbf{Z}})\end{array}\right).$
(194)

In particular, we have

$\displaystyle((\bra{0}\widetilde{Q}_{1}^{\dagger})_{\mathbf{\widetilde{CR}}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{\widetilde{C}}}\otimes
U_{\mathbf{\widetilde{R}Z}})(\widetilde{Q}_{0}\ket{0}_{\mathbf{\widetilde{CR}}}\ket{\tau}_{\mathbf{Z}})=((\bra{0}\widetilde{Q}_{0}^{\dagger})_{\mathbf{\widetilde{CR}}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{\widetilde{C}}}\otimes
U_{\mathbf{\widetilde{R}Z}})(\widetilde{Q}_{1}\ket{0}_{\mathbf{\widetilde{CR}}}\ket{\tau}_{\mathbf{Z}}).$
(195)

This implies that

$\displaystyle\norm{\begin{array}[]{ll}((\bra{0}\widetilde{Q}_{1}^{\dagger})_{\mathbf{\widetilde{CR}}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{\widetilde{C}}}\otimes
U_{\mathbf{\widetilde{R}Z}})(\widetilde{Q}_{0}\ket{0}_{\mathbf{\widetilde{CR}}}\ket{\tau}_{\mathbf{Z}})+((\bra{0}\widetilde{Q}_{0}^{\dagger})_{\mathbf{\widetilde{CR}}}\otimes
I_{\mathbf{Z}})(I_{\mathbf{\widetilde{C}}}\otimes
U_{\mathbf{\widetilde{R}Z}})(\widetilde{Q}_{1}\ket{0}_{\mathbf{\widetilde{CR}}}\ket{\tau}_{\mathbf{Z}})\end{array}}_{1}\geq
2d.$ (197)

If we set $\ket{x}\coloneqq\widetilde{Q_{0}}\ket{0}_{\mathbf{\widetilde{CR}}}$
and $\ket{y}\coloneqq\widetilde{Q_{1}}\ket{0}_{\mathbf{\widetilde{CR}}}$, then
$\ket{x}$ and $\ket{y}$ are orthogonal. Then, by Theorem C.1, there exists a
non-uniform distinguisher $\mathcal{A}$ with a polynomial-size advice
$\ket{\tau^{\prime}}$ that does not act on
$\mathbf{\widetilde{C}}=(\mathbf{R},\mathbf{D})$ and distinguishes

$\displaystyle\ket{\psi}=\frac{\ket{x}+\ket{y}}{\sqrt{2}}=(Q_{0}\ket{0}_{\mathbf{CR}})\ket{0}_{\mathbf{D}}$
(198)

and

$\displaystyle\ket{\phi}=\frac{\ket{x}-\ket{y}}{\sqrt{2}}=(Q_{1}\ket{0}_{\mathbf{CR}})\ket{1}_{\mathbf{D}}$
(199)

with $d^{2}\geq c$. This contradicts that $(Q_{0},Q_{1})$ satisfies
$c$-statistical hiding, and thus $(\widetilde{Q_{0}},\widetilde{Q_{1}})$
satisfies $\sqrt{c}$-statistical binding. ∎

##  Appendix D Proof of Lemma 7.4

We give the proof of Lemma 7.4.

###### Proof of Lemma 7.4.

For a candidate of one-time unclonable secret-key encryption
$\Sigma=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ with
$n(\lambda)$-plaintext space, we can assume that
$\mathsf{Dec}(1^{\lambda},\mathsf{sk},\mathsf{CT})$ works as follows without
loss of generality:

For input $(1^{\lambda},\mathsf{sk},\mathsf{CT})$, run a classical Turing
machine $\mathcal{M}$ on
$(1^{\lambda},\mathsf{sk},\absolutevalue{\mathsf{CT}})$, obtain a unitary
$U_{\mathsf{Dec},\mathsf{sk}}$, append auxiliary state $\ket{0\cdots
0}\bra{0\cdots 0}$ to $\mathsf{CT}$, apply a unitary
$U_{\mathsf{Dec},\mathsf{sk}}$ on $\mathsf{CT}\otimes\ket{0\cdots
0}\bra{0\cdots 0}$, obtain $\rho_{\mathsf{CT}}$, and measure the first
$n(\lambda)$ qubit of $\rho_{\mathsf{CT}}$ with the computational basis and
output its output.

#### Construction of one-time unclonable secret key encryption:

We give a construction
$\Sigma^{*}=(\mathsf{KeyGen}^{*},\mathsf{Enc}^{*},\mathsf{Dec}^{*})$.

$\mathsf{KeyGen}^{*}(1^{\lambda})$:

  * •

Run $\mathsf{sk}\leftarrow\mathsf{KeyGen}(1^{\lambda})$.

  * •

Output $\mathsf{sk}^{*}\coloneqq\mathsf{sk}$.

$\mathsf{Enc}^{*}(1^{\lambda},\mathsf{sk}^{*},m)$:

  * •

Parse $\mathsf{sk}^{*}=\mathsf{sk}$.

  * •

Run $\mathsf{CT}\leftarrow\mathsf{Enc}(1^{\lambda},\mathsf{sk},m)$.

  * •

Measure the first $n(\lambda)$-bit of
$U_{\mathsf{Dec},\mathsf{sk}}\left(\mathsf{CT}\otimes\ket{0\cdots
0}\bra{0\cdots 0}\right)U_{\mathsf{Dec},\mathsf{sk}}^{\dagger}$ in the
computational basis, and obtains $m^{*}$ and post-measurement quantum state
$\rho_{m^{*},\mathsf{sk}}$.

    * –

If $m=m^{*}$, then output $\mathsf{CT}^{*}\coloneqq
U_{\mathsf{Dec},\mathsf{sk}}^{\dagger}\left(m\otimes\rho_{m,\mathsf{sk}}\right)U_{\mathsf{Dec},\mathsf{sk}}\otimes\ket{1}\bra{1}$.

    * –

If $m\neq m^{*}$, output $\mathsf{CT}^{*}\coloneqq m\otimes\ket{0}\bra{0}$.

$\mathsf{Dec}^{*}(1^{\lambda},\mathsf{sk}^{*},\mathsf{CT}^{*})$:

  * •

Parse $\mathsf{CT}^{*}=\rho\otimes\ket{b}\bra{b}$ and
$\mathsf{sk}^{*}=\mathsf{sk}$.

  * •

Measure the final bit of $\mathsf{CT}^{*}$ with
$\\{\ket{1}\bra{1},\ket{0}\bra{0}\\}$.

    * –

If the result is $1$, then measure the first $n(\lambda)$-bit of
$U_{\mathsf{Dec},\mathsf{sk}}\rho U_{\mathsf{Dec},\mathsf{sk}}^{\dagger}$ in
the computational basis, and outputs its output.

    * –

If the result is $0$, then measure the first $n(\lambda)$-qubit of
$\mathsf{CT}$ in the computational basis and outputs its output.

∎

##  Appendix E Unclonable PKE from One-Time Unclonable SKE and PKE with
Quantum Ciphertexts

It was shown that unclonable PKE can be constructed from one-time unclonable
SKE and PKE with “classical” ciphertexts [AK21]. However, it is unclear
whether we can construct unclonable PKE from one-time unclonable SKE and PKE
with “quantum” ciphertexts based on their technique. This is because their
security proof relies on the existence of OWFs, but it is an open problem
whether PKE with quantum ciphertexts implies OWFs or not. Therefore, for the
reader’s convenience, we construct unclonable PKE from one-time unclonable SKE
and PKE with quantum ciphertexts.

Our construction is based on the technique of [HMNY21]. First, let us
introduce receiver non-committing encryption with quantum ciphertexts. Note
that in the same way as [KNTY19, HKM+23], we can construct receiver non-
committing encryption with quantum ciphertexts from PKE with quantum
ciphertexts.

###### Definition E.1 (Receiver Non-Committing Encryption with Quantum
Ciphertexts.).

An receiver non-committing encryption is a set of algorithms
$\Sigma\coloneqq(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Fake},\mathsf{Reveal})$
such that:

  * $\mathsf{Setup}(1^{\lambda})$:

It takes $1^{\lambda}$, and outputs a classical key pair
$(\mathsf{pk},\mathsf{MSK})$.

  * $\mathsf{KeyGen}(1^{\lambda},\mathsf{MSK}):$

It takes $1^{\lambda}$ and $\mathsf{MSK}$, and outputs a classical key
$\mathsf{sk}$.

  * $\mathsf{Enc}(1^{\lambda},\mathsf{pk},m)$:

It takes $1^{\lambda}$, $\mathsf{pk}$ and $m$, and outputs a quantum
ciphertext $\mathsf{CT}$.

  * $\mathsf{Dec}(1^{\lambda},\mathsf{sk},\mathsf{CT})$:

It takes $1^{\lambda}$, $\mathsf{sk}$ and $\mathsf{CT}$, and outputs $m$.

  * $\mathsf{Fake}(1^{\lambda},\mathsf{pk})$:

It takes $1^{\lambda}$ and $\mathsf{pk}$, and outputs a fake quantum
ciphertext $\widetilde{\mathsf{CT}}$ and an auxiliary state $\mathsf{aux}$.

  * $\mathsf{Reveal}(1^{\lambda},\mathsf{pk},\mathsf{MSK},\mathsf{aux},m)$:

It takes $1^{\lambda}$, $\mathsf{pk}$, $\mathsf{MSK}$, $\mathsf{aux}$, and
$m$, and outputs a secret key $\widetilde{\mathsf{sk}}$.

#### Efficiency.

The algorithms
$(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Fake},\mathsf{Reveal})$
are uniform QPT algorithms.

#### Correctness.

$\displaystyle\Pr[m\leftarrow\mathsf{Dec}(1^{\lambda},\mathsf{sk},\mathsf{CT}):(\mathsf{pk},\mathsf{MSK})\leftarrow\mathsf{Setup}(1^{\lambda}),\mathsf{sk}\leftarrow\mathsf{KeyGen}(1^{\lambda},\mathsf{MSK}),\mathsf{CT}\leftarrow\mathsf{Enc}(1^{\lambda},\mathsf{pk},m)]\geq
1-{\mathsf{negl}}(\lambda).$ (200)

#### Security.

Given a receiver non-committing encryption $\Sigma$, we consider a security
experiment $\mathsf{Exp_{\Sigma,\mathcal{A}}^{rec\mbox{-}nc}}(\lambda,b)$
against $\mathcal{A}$.

  1. 1.

The challenger runs
$(\mathsf{pk},\mathsf{MSK})\leftarrow\mathsf{Setup}(1^{\lambda})$ and sends
$\mathsf{pk}$ to $\mathcal{A}$.

  2. 2.

$\mathcal{A}$ sends $m$ to the challenger.

  3. 3.

The challenger does the following:

     * •

If $b=0$, the challenger generates
$\mathsf{CT}\leftarrow\mathsf{Enc}(1^{\lambda},\mathsf{pk},m)$ and
$\mathsf{sk}\leftarrow\mathsf{KeyGen}(1^{\lambda},\mathsf{MSK})$, and sends
$(\mathsf{CT},\mathsf{sk})$ to $\mathcal{A}$.

     * •

If $b=1$, the challenger generates
$(\widetilde{\mathsf{CT}},\mathsf{aux})\leftarrow\mathsf{Fake}(1^{\lambda},\mathsf{pk})$
and
$\widetilde{\mathsf{sk}}\leftarrow\mathsf{Reveal}(1^{\lambda},\mathsf{pk},\mathsf{MSK},\mathsf{aux},m)$,
and sends $(\widetilde{\mathsf{CT}},\widetilde{\mathsf{sk}})$ to
$\mathcal{A}$.

  4. 4.

$\mathcal{A}$ outputs $b^{\prime}\in\\{0,1\\}$, and the experiment outputs $1$
if $b^{\prime}=b$.

We say that $\Sigma$ is RNC secure if for all sufficiently large security
parameters $\lambda\in\mathbb{N}$, for any QPT adversary $\mathcal{A}$, it
holds that

$\displaystyle\absolutevalue{\Pr[\mathsf{Exp_{\Sigma,\mathcal{A}}^{rec\mbox{-}nc}}(\lambda,0)=1]-\Pr[\mathsf{Exp_{\Sigma,\mathcal{A}}^{rec\mbox{-}nc}}(\lambda,1)=1]}\leq{\mathsf{negl}}(\lambda).$
(201)

#### Construction

We construct unclonable PKE
$\Sigma=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ from one-time unclonable
SKE
$\Sigma_{\mathsf{SKE}}=\mathsf{SKE}.(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$
and receiver non-committing encryption with quantum ciphertexts
$\Sigma_{\mathsf{NCE}}=\mathsf{NCE}.(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\allowbreak\mathsf{Dec},\mathsf{Fake},\mathsf{Reveal})$:

$\mathsf{KeyGen}(1^{\lambda})$:

  * •

Run
$(\mathsf{nce}.\mathsf{pk},\mathsf{nce}.\mathsf{MSK})\leftarrow\mathsf{NCE}.\mathsf{Setup}(1^{\lambda})$
and
$\mathsf{nce}.\mathsf{sk}\leftarrow\mathsf{NCE}.\mathsf{KeyGen}(1^{\lambda},\mathsf{nce}.\mathsf{MSK})$.

  * •

Output $\mathsf{pk}\coloneqq\mathsf{nce}.\mathsf{pk}$ and
$\mathsf{sk}\coloneqq\mathsf{nce}.\mathsf{sk}$.

$\mathsf{Enc}(1^{\lambda},\mathsf{pk},m)$:

  * •

Parse $\mathsf{pk}=\mathsf{nce}.\mathsf{pk}$.

  * •

Run
$\mathsf{ske}.\mathsf{sk}\leftarrow\mathsf{SKE}.\mathsf{KeyGen}(1^{\lambda})$
and
$\mathsf{ske}.\mathsf{CT}\leftarrow\mathsf{SKE}.\mathsf{Enc}(1^{\lambda},\mathsf{ske}.\mathsf{sk},m)$.

  * •

Run
$\mathsf{nce}.\mathsf{CT}\leftarrow\mathsf{NCE}.\mathsf{Enc}(1^{\lambda},\mathsf{nce}.\mathsf{pk},\mathsf{ske},\mathsf{sk})$.

  * •

Output
$\mathsf{CT}\coloneqq(\mathsf{nce}.\mathsf{CT},\mathsf{ske}.\mathsf{CT})$.

$\mathsf{Dec}(1^{\lambda},\mathsf{sk},\mathsf{CT})$:

  * •

Parse $\mathsf{sk}=\mathsf{nce}.\mathsf{sk}$ and
$\mathsf{CT}=(\mathsf{nce}.\mathsf{CT},\mathsf{ske}.\mathsf{CT})$.

  * •

Run
$\mathsf{ske}.\mathsf{sk}\leftarrow\mathsf{NCE}.\mathsf{Dec}(1^{\lambda},\mathsf{nce}.\mathsf{sk},\mathsf{nce}.\mathsf{CT})$.

  * •

Run
$\mathsf{SKE}.\mathsf{Dec}(1^{\lambda},\mathsf{ske}.\mathsf{sk},\mathsf{ske}.\mathsf{CT})$
and outputs its output.

Obviously, $\Sigma$ satisfies efficiency, correctness, and IND-CPA security.

###### Lemma E.2.

$\Sigma$ satisfies unclonable IND-CPA security.

###### Proof.

We describe the sequence of hybrids against QPT adversaries
$(\mathcal{A},\mathcal{B},\mathcal{C})$.

$\mathsf{Hyb_{0}}$:

This is the original security experiment of $\Sigma$.

  1. 1.

The challenger samples $b\leftarrow\\{0,1\\}$.

  2. 2.

$\mathcal{A}$ receives $\mathsf{nce}.\mathsf{pk}$, where
$(\mathsf{nce}.\mathsf{pk},\mathsf{nce}.\mathsf{MSK})\leftarrow\mathsf{NCE}.\mathsf{Setup}(1^{\lambda})$.

  3. 3.

$\mathcal{A}$ sends $(m_{0},m_{1})$ to the challenger.

  4. 4.

$\mathcal{A}$ receives
$(\mathsf{nce}.\mathsf{CT},\mathsf{ske}.\mathsf{CT}_{b})$ from the challenger,
where
$\mathsf{ske}.\mathsf{sk}\leftarrow\mathsf{SKE}.\mathsf{KeyGen}(1^{\lambda})$,
$\mathsf{nce}.\mathsf{CT}\leftarrow\mathsf{NCE}.\mathsf{Enc}(1^{\lambda},\mathsf{nce}.\mathsf{pk},\mathsf{ske}.\mathsf{sk})$
and
$\mathsf{ske}.\mathsf{CT}_{b}\leftarrow\mathsf{SKE}.\mathsf{Enc}(1^{\lambda},\mathsf{ske}.\mathsf{sk},m_{b})$.

  5. 5.

$\mathcal{A}$ generates $\rho_{\mathcal{B},\mathcal{C}}$ and sends the
$\mathcal{B}$ and $\mathcal{C}$ register to $\mathcal{B}$ and $\mathcal{C}$,
respectively.

  6. 6.

$\mathcal{B}$ and $\mathcal{C}$ receives $\mathsf{nce}.\mathsf{sk}$ and
outputs $b_{\mathcal{B}}$ and $b_{\mathcal{C}}$, respectively, where
$\mathsf{nce}.\mathsf{sk}\leftarrow\mathsf{NCE}.\mathsf{KeyGen}(1^{\lambda},\mathsf{nce}.\mathsf{MSK})$.

  7. 7.

The experiment outputs $1$ if $b=b_{\mathcal{B}}=b_{\mathcal{C}}$.

$\mathsf{Hyb_{1}}$:

This is the same as $\mathsf{Hyb_{0}}$ except that
$(\widetilde{\mathsf{nce}.\mathsf{CT}},\widetilde{\mathsf{nce}.\mathsf{sk}})$
is used instead of $(\mathsf{nce}.\mathsf{CT},\mathsf{nce}.\mathsf{sk})$,
where
$(\widetilde{\mathsf{nce}.\mathsf{CT}},\mathsf{aux})\leftarrow\mathsf{Fake}(1^{\lambda},\mathsf{nce}.\mathsf{pk})$
and
$\widetilde{\mathsf{nce}.\mathsf{sk}}\leftarrow\mathsf{Reveal}(1^{\lambda},\mathsf{nce}.\mathsf{pk},\mathsf{nce}.\mathsf{MSK},\mathsf{aux},\mathsf{ske}.\mathsf{sk})$.

We have the following Propositions E.3 and E.4.

###### Proposition E.3.

If $\Sigma_{\mathsf{NCE}}$ is RNC secure, then

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb_{0}}=1]-\Pr[\mathsf{Hyb_{1}}=1]}\leq{\mathsf{negl}}(\lambda).$
(202)

###### Proposition E.4.

If $\Sigma_{\mathsf{SKE}}$ is one-time unclonable IND-CPA secure, then

$\displaystyle\Pr[\mathsf{Hyb_{1}}=1]\leq 1/2+{\mathsf{negl}}(\lambda).$ (203)

∎

###### Proof of Proposition E.3.

This can be shown by a standard hybrid argument. Assume that there a QPT
adversary $(\mathcal{A},\mathcal{B},\mathcal{C})$ such that

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb_{0}}=1]-\Pr[\mathsf{Hyb_{1}}=1]}$
(204)

is non-negligible. Then, construct a QPT adversary $\widetilde{\mathcal{A}}$
that breaks the RNC security of $\Sigma_{\mathsf{NCE}}$ as follows.

  1. 1.

$\widetilde{\mathcal{A}}$ samples $b\leftarrow\\{0,1\\}$.

  2. 2.

$\widetilde{\mathcal{A}}$ receives $\mathsf{nce}.\mathsf{pk}$ from the
challenger of
$\mathsf{Exp_{\Sigma_{\mathsf{NCE}},\widetilde{\mathcal{A}}}^{rec\mbox{-}nc}}(\lambda,b^{*})$,
where
$(\mathsf{nce}.\mathsf{pk},\mathsf{nce}.\mathsf{MSK})\leftarrow\mathsf{NCE}.\mathsf{Setup}(1^{\lambda})$.

  3. 3.

$\widetilde{\mathcal{A}}$ sends $\mathsf{nce}.\mathsf{pk}$ to $\mathcal{A}$,
and receives $(m_{0},m_{1})$ from $\mathcal{A}$.

  4. 4.

$\widetilde{\mathcal{A}}$ samples
$\mathsf{ske}.\mathsf{sk}\leftarrow\mathsf{SKE}.\mathsf{KeyGen}(1^{\lambda})$,
computes
$\mathsf{ske}.\mathsf{CT}_{b}\leftarrow\mathsf{SKE}.\mathsf{Enc}(1^{\lambda},\mathsf{ske}.\mathsf{sk},m_{b})$,
and sends $\mathsf{ske}.\mathsf{sk}$ to the challenger of
$\mathsf{Exp_{\Sigma_{\mathsf{NCE}},\widetilde{\mathcal{A}}}^{rec\mbox{-}nc}}(\lambda,b^{*})$.

  5. 5.

The challenger of
$\mathsf{Exp_{\Sigma_{\mathsf{NCE}},\widetilde{\mathcal{A}}}^{rec\mbox{-}nc}}(\lambda,b^{*})$
works as follows:

     * •

If $b^{*}=0$, then runs
$\mathsf{nce}.\mathsf{CT}^{*}\leftarrow\mathsf{NCE}.\mathsf{Enc}(1^{\lambda},\mathsf{nce}.\mathsf{pk},\mathsf{ske}.\mathsf{sk})$
and
$\mathsf{nce}.\mathsf{sk}^{*}\leftarrow\mathsf{NCE}.\mathsf{KeyGen}(1^{\lambda},\mathsf{nce}.\mathsf{MSK})$,
and sends $(\mathsf{nce}.\mathsf{CT}^{*},\mathsf{nce}.\mathsf{sk}^{*})$ to
$\widetilde{\mathcal{A}}$.

     * •

If $b^{*}=1$, then runs
$(\mathsf{nce}.\mathsf{CT}^{*},\mathsf{aux})\leftarrow\mathsf{Fake}(1^{\lambda},\mathsf{nce}.\mathsf{pk})$
and
$\mathsf{nce}.\mathsf{sk}^{*}\leftarrow\mathsf{Reveal}(1^{\lambda},\mathsf{nce}.\mathsf{pk},\mathsf{nce}.\mathsf{MSK},\mathsf{aux},\mathsf{ske}.\mathsf{sk})$,
and sends $(\mathsf{nce}.\mathsf{CT}^{*},\mathsf{nce}.\mathsf{sk}^{*})$ to
$\widetilde{\mathcal{A}}$.

  6. 6.

$\widetilde{\mathcal{A}}$ runs $\mathcal{A}$ on
$(\mathsf{ske}.\mathsf{CT}_{b},\mathsf{nce}.\mathsf{CT}^{*})$, and obtains
$\rho_{\mathcal{B},\mathcal{C}}$.

  7. 7.

$\widetilde{\mathcal{A}}$ sends $\mathsf{nce}.\mathsf{sk}^{*}$ and the
$\mathcal{B}$ register (resp. the $\mathcal{C}$ register) to $\mathcal{B}$
(resp. $\mathcal{C}$).

  8. 8.

$\mathcal{B}$ and $\mathcal{C}$ outputs $b_{\mathcal{B}}$ and
$b_{\mathcal{C}}$, respectively.

  9. 9.

$\widetilde{\mathcal{A}}$ outputs $1$ if $b=b_{\mathcal{B}}=b_{\mathcal{C}}$,
and $0$ otherwise.

From the construction of $\widetilde{\mathcal{A}}$,

  * •

If $b^{*}=0$, $\widetilde{\mathcal{A}}$ perfectly simulates the challenger of
$\mathsf{Hyb_{0}}$ and thus it outputs the output of $\mathsf{Hyb_{0}}$.

  * •

If $b^{*}=1$, $\widetilde{\mathcal{A}}$ perfectly simulates the challenger of
$\mathsf{Hyb_{1}}$ and thus it outputs the output of $\mathsf{Hyb_{1}}$.

Therefore, we have

$\displaystyle\absolutevalue{\Pr[\mathsf{Exp_{\Sigma_{\mathsf{NCE}},\widetilde{\mathcal{A}}}^{rec\mbox{-}nc}}(\lambda,0)=1]-\Pr[\mathsf{Exp_{\Sigma_{\mathsf{NCE}},\widetilde{\mathcal{A}}}^{rec\mbox{-}nc}}(\lambda,1)=1]}=\absolutevalue{\Pr[\mathsf{Hyb_{0}}=1]-\Pr[\mathsf{Hyb_{1}}=1]},$
(205)

which contradicts that $\Sigma_{\mathsf{NCE}}$ satisfies RNC security. ∎

###### Proof of Proposition E.4.

This can be shown by a standard hybrid argument. Assume that there there
exists a constant $C$ and QPT adversaries
$(\mathcal{A},\mathcal{B},\mathcal{C})$ such that

$\displaystyle\Pr[\mathsf{Hyb_{1}}=1]\geq 1/2+1/\lambda^{C}$ (206)

for infinitely many security parameters $\lambda\in\mathbb{N}$. Then,
construct a set of QPT adversaries
$(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}})$
that breaks the unclonable IND-CPA security of $\Sigma_{\mathsf{SKE}}$ as
follows.

  1. 1.

The challenge of $\Sigma_{\mathsf{SKE}}$ samples $b\leftarrow\\{0,1\\}$.

  2. 2.

$\widetilde{\mathcal{A}}$ samples
$(\mathsf{nce}.\mathsf{pk},\mathsf{nce}.\mathsf{MSK})\leftarrow\mathsf{NCE}.\mathsf{Setup}(1^{\lambda})$
and sends $\mathsf{nce}.\mathsf{pk}$ to $\mathcal{A}$.

  3. 3.

$\widetilde{\mathcal{A}}$ receives $(m_{0},m_{1})$ from $\mathcal{A}$, and
sends $(m_{0},m_{1})$ to the challenger.

  4. 4.

$\widetilde{\mathcal{A}}$ receives $\mathsf{ske}.\mathsf{CT}_{b}$, where
$\mathsf{ske}.\mathsf{CT}_{b}\leftarrow\mathsf{SKE}.\mathsf{Enc}(1^{\lambda},\mathsf{ske}.\mathsf{sk},m_{b})$
and
$\mathsf{ske}.\mathsf{sk}\leftarrow\mathsf{SKE}.\mathsf{KeyGen}(1^{\lambda})$.

  5. 5.

$\widetilde{\mathcal{A}}$ runs
$(\widetilde{\mathsf{nce}.\mathsf{CT}},\mathsf{aux})\leftarrow\mathsf{Fake}(1^{\lambda},\mathsf{nce}.\mathsf{pk})$,
and runs $\mathcal{A}$ on
$(\widetilde{\mathsf{nce}.\mathsf{CT}},\mathsf{ske}.\mathsf{CT}_{b})$, and
obtains $\rho_{\mathcal{B},\mathcal{C}}$.

  6. 6.

$\widetilde{\mathcal{A}}$ sends $\mathsf{aux}$, $\mathsf{nce}.\mathsf{MSK}$
and the $\mathcal{B}$ (resp. $\mathcal{C}$) register to
$\widetilde{\mathcal{B}}$ (resp. $\widetilde{\mathcal{C}}$).

  7. 7.

$\widetilde{\mathcal{B}}$ (resp. $\widetilde{\mathcal{C}}$) receives
$\mathsf{ske}.\mathsf{sk}$ and runs
$\widetilde{\mathsf{nce}.\mathsf{sk}}\leftarrow\mathsf{Reveal}(1^{\lambda},\mathsf{nce}.\mathsf{pk},\mathsf{nce}.\mathsf{MSK},\mathsf{aux},\mathsf{ske}.\mathsf{sk})$,
and sends $\widetilde{\mathsf{nce}.\mathsf{sk}}$ and the $\mathcal{B}$ (resp.
$\mathcal{C}$) register to $\mathcal{B}$ (resp. $\mathcal{C}$).

  8. 8.

$\mathcal{B}$ and $\mathcal{C}$ outputs $b_{\mathcal{B}}$ and
$b_{\mathcal{C}}$, respectively.

  9. 9.

$\widetilde{\mathcal{B}}$ and $\widetilde{\mathcal{C}}$ outputs
$b_{\mathcal{B}}$ and $b_{\mathcal{C}}$ as the guess for $b$, respectively.

From the construction of
$(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}})$,
it perfectly simulates the challenger of $\mathsf{Hyb_{1}}$. Therefore, we
have $b=b_{\mathcal{B}}=b_{\mathcal{C}}$ with non-negligible probability,
which implies that
$(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}})$
break one-time unclonable IND-CPA security of $\Sigma_{\mathsf{SKE}}$. This is
a contradiction. Therefore, we have

$\displaystyle\Pr[\mathsf{Hyb_{1}}=1]\leq 1/2+{\mathsf{negl}}(\lambda).$ (207)

∎

##  Appendix F Proof of Proposition 8.9

We give the proof of Proposition 8.9.

###### Proof of Proposition 8.9.

In the same way as proof of Lemma 7.4, we can show that if there exists a one-
time unclonable secret-key encryption for single-bit plaintexts, then there
exists a scheme
$\Sigma^{*}=(\mathsf{KeyGen}^{*},\mathsf{Enc}^{*},\mathsf{Dec}^{*})$ that
satisfies perfect correctness.

Now, we construct one-time unclonable secret key encryption
$\overline{\Sigma}\coloneqq(\overline{\mathsf{KeyGen}},\overline{\mathsf{Enc}},\overline{\mathsf{Dec}})$
with uniformly random secret-key and perfect correctness from one-time
unclonable secret key encryption
$(\mathsf{KeyGen}^{*},\mathsf{Enc}^{*},\mathsf{Dec}^{*})$ with perfect
correctness.

$\overline{\mathsf{KeyGen}}(1^{\lambda})$:

  * •

Sample $s\leftarrow\\{0,1\\}^{s(\lambda)}$, where $s(\lambda)$ is the length
of the secret-key $\mathsf{sk}$ that $\mathsf{KeyGen}^{*}(1^{\lambda})$
generates

  * •

Output $\overline{\mathsf{sk}}\coloneqq s$.

$\overline{\mathsf{Enc}}(1^{\lambda},\overline{\mathsf{sk}},m)$:

  * •

Parse $\overline{\mathsf{sk}}\coloneqq s$.

  * •

Run $\mathsf{sk}\leftarrow\mathsf{KeyGen}^{*}(1^{\lambda})$.

  * •

Run $\mathsf{CT}\leftarrow\mathsf{Enc}^{*}(1^{\lambda},\mathsf{sk},m)$.

  * •

Output $\overline{\mathsf{CT}}\coloneqq(\mathsf{CT},\mathsf{sk}+s)$.

$\overline{\mathsf{Dec}}(1^{\lambda},\overline{\mathsf{sk}},\overline{\mathsf{CT}})$:

  * •

Parse $\overline{\mathsf{sk}}=s$ and
$\overline{\mathsf{CT}}=(\mathsf{CT},\mathsf{sk}^{*})$.

  * •

Compute $\mathsf{sk}=\mathsf{sk}^{*}+s$.

  * •

Run $\mathsf{Dec}^{*}(1^{\lambda},\mathsf{sk},\mathsf{CT})$ and output its
output.

From the construction, the secret key of $\Sigma^{*}$ is uniformly random.
Efficiency and perfect correctness of $\overline{\Sigma}$ straightforwardly
follow that of $\Sigma^{*}$. We can show that $\overline{\Sigma}$ satisfies
unclonable IND-CPA security by a standard hybrid argument. For clarity, we
describe the proof of security.

Assume that there exists a QPT adversary
$(\mathcal{A},\mathcal{B},\mathcal{C})$ that breaks the unclonable IND-CPA
security of $\overline{\Sigma}$. Then, construct a QPT adversary
$(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}})$
that breaks the unclonable IND-CPA security of $\Sigma^{*}$.

  1. 1.

The challenger of $\Sigma^{*}$ samples $b\leftarrow\\{0,1\\}$.

  2. 2.

$\widetilde{\mathcal{A}}$ samples $s\leftarrow\\{0,1\\}^{s(\lambda)}$.

  3. 3.

$\widetilde{\mathcal{A}}$ receives $(m_{0},m_{1})$ from $\mathcal{A}$.

  4. 4.

$\widetilde{\mathcal{A}}$ sends $(m_{0},m_{1})$ to the challenger of
$\Sigma^{*}$.

  5. 5.

$\widetilde{\mathcal{A}}$ receives $\mathsf{CT}_{b}$, where
$\mathsf{sk}\leftarrow\mathsf{KeyGen}^{*}(1^{\lambda})$ and
$\mathsf{CT}_{b}\leftarrow\mathsf{Enc}^{*}(1^{\lambda},\mathsf{sk},m_{b})$.

  6. 6.

$\widetilde{\mathcal{A}}$ runs $\mathcal{A}$ on $(\mathsf{CT}_{b},s)$, obtain
$\rho_{\mathcal{B},\mathcal{C}}$, and sends $s$ and the $\mathcal{B}$ register
(resp. $\mathcal{C}$ register) to $\widetilde{\mathcal{B}}$ (resp.
$\widetilde{\mathcal{C}}$).

  7. 7.

$\widetilde{\mathcal{B}}$ (resp. $\widetilde{\mathcal{C}}$) receives
$\mathsf{sk}$ from the challenger of $\Sigma^{*}$, and sends $\mathsf{sk}+s$
and the $\mathcal{B}$ register (resp. $\mathcal{C}$ register) to $\mathcal{B}$
(resp.$\mathcal{C}$).

  8. 8.

The experiment outputs $1$ if $b=b_{\mathcal{B}}=b_{\mathcal{C}}$, where
$b_{\mathcal{B}}$ and $b_{\mathcal{C}}$ are the output of $\mathcal{B}$ and
$\mathcal{C}$,respectively.

From the construction of
$(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}})$,
it perfectly simulates the challenger of $\Sigma^{*}$. Therefore, if
$(\mathcal{A},\mathcal{B},\mathcal{C})$ breaks the unclonable IND-CPA security
of $\overline{\Sigma}$, it contradicts that $\Sigma^{*}$ satisfies unclonable
IND-CPA security.

In the construction $\overline{\Sigma}$, the size of
$\overline{\mathsf{sk}_{\lambda}}$ and $\overline{\mathsf{CT}_{\lambda,b}}$
are not necessarily equal to $\lambda$, where
$\overline{\mathsf{sk}_{\lambda}}\leftarrow\overline{\mathsf{KeyGen}}(1^{\lambda})$
and
$\overline{\mathsf{CT}_{\lambda,b}}\leftarrow\overline{\mathsf{Enc}}(1^{\lambda},\overline{\mathsf{sk}_{\lambda}},b)$.
By wisely choosing a security parameter and a standard padding argument, from
$\overline{\Sigma}$, we can construct
$\Sigma=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ such that
$\absolutevalue{\mathsf{sk}_{\lambda}}=\absolutevalue{\mathsf{CT}_{\lambda,b}}=\lambda$
for all $\lambda\in\mathbb{N}$ and $b$ where
$\mathsf{sk}_{\lambda}\leftarrow\mathsf{KeyGen}(1^{\lambda})$ and
$\mathsf{CT}_{\lambda,b}\leftarrow\mathsf{Enc}(1^{\lambda},\mathsf{sk}_{\lambda},b)$.

For clarity, we describe the construction of $\Sigma$. To describe our
construction, let $c$ be a constant such that
$\absolutevalue{\overline{\mathsf{sk}_{\lambda}}}\leq\absolutevalue{\overline{\mathsf{CT}_{\lambda,b}}}\leq\lambda^{c}$
for all security parameters $\lambda\in\mathbb{N}$ and $b\in\\{0,1\\}$, where
$\overline{\mathsf{sk}_{\lambda}}\leftarrow\overline{\mathsf{KeyGen}}(1^{\lambda})$
and
$\overline{\mathsf{CT}_{\lambda,b}}\leftarrow\overline{\mathsf{Enc}}(1^{\lambda},\overline{\mathsf{sk}_{\lambda}},b)$.

$\mathsf{KeyGen}(1^{\lambda})$:

  * •

Sample $x\leftarrow\\{0,1\\}^{\lambda}$.

  * •

Output $\mathsf{sk}\coloneqq x$.

$\mathsf{Enc}(1^{\lambda},\mathsf{sk},b)$:

  * •

Parse $\mathsf{sk}=x$.

  * •

Let $\lambda^{\prime}$ be the largest integer such that $\lambda^{\prime
c}\leq\lambda$.

  * •

Let $\overline{x}$ be the first
$\absolutevalue{\overline{\mathsf{sk}_{\lambda^{\prime}}}}$-bits of $x$, where
$\overline{\mathsf{sk}_{\lambda^{\prime}}}\leftarrow\overline{\mathsf{KeyGen}}(1^{\lambda^{\prime}})$.

  * •

Run
$\overline{\mathsf{CT}}\leftarrow\overline{\mathsf{Enc}}(1^{\lambda^{\prime}},\overline{x},b)$.
Note that since $\lambda^{\prime c}\leq\lambda$, the size of
$\overline{\mathsf{CT}}$ is smaller than $\lambda$.

  * •

Output
$\mathsf{CT}=(\overline{\mathsf{CT}},0^{\lambda-\absolutevalue{\overline{\mathsf{CT}}}})$.

$\mathsf{Dec}(1^{\lambda},\mathsf{sk},\mathsf{CT})$:

  * •

Parse $\mathsf{sk}=x$ and
$\mathsf{CT}=(\overline{\mathsf{CT}},0^{\lambda-\absolutevalue{\overline{\mathsf{CT}}}})$.

  * •

Let $\lambda^{\prime}$ be the largest integer such that $\lambda^{\prime
c}\leq\lambda$.

  * •

Let $\overline{x}$ be the first
$\absolutevalue{\overline{\mathsf{sk}_{\lambda^{\prime}}}}$-bits of $x$, where
$\overline{\mathsf{sk}_{\lambda^{\prime}}}\leftarrow\overline{\mathsf{KeyGen}}(1^{\lambda^{\prime}})$.

  * •

Compute
$\overline{\mathsf{Dec}}(1^{\lambda^{\prime}},\overline{x},\overline{\mathsf{CT}})$,
and outputs its output.

Efficiency and perfect correctness straightforwardly follow. From the
construction, it is obvious that $\mathsf{sk}_{\lambda}$ is uniformly randomly
sampled and
$\absolutevalue{\mathsf{sk}_{\lambda}}=\absolutevalue{\mathsf{CT}_{\lambda,b}}=\lambda$
for all $\lambda\in\mathbb{N}$ and $b\in\\{0,1\\}$, where
$\mathsf{sk}_{\lambda}\leftarrow\mathsf{KeyGen}(1^{\lambda})$ and
$\mathsf{Enc}(1^{\lambda},\mathsf{sk}_{\lambda},b)$. Furthermore, we can prove
its security by a standard hybrid argument. ∎