* [CMP20] Andrea Coladangelo, Christian Majenz, and Alexander Poremba.  Quantum copy-protection of compute-and-compare programs in the quantum random oracle model.  Cryptology ePrint Archive, Paper 2020/1194, 2020.  https://eprint.iacr.org/2020/1194.
  * [Got02] Daniel Gottesman.  Unclonable encryption, 2002.
  * [GZ20] Marios Georgiou and Mark Zhandry.  Unclonable decryption keys.  Cryptology ePrint Archive, Paper 2020/877, 2020.  https://eprint.iacr.org/2020/877.
  * [Hel69] Carl W. Helstrom.  Quantum detection and estimation theory.  Journal of Statistical Physics, 1:231–252, 1969.
  * [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.
  * [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, ASIACRYPT 2021, Part I, volume 13090 of LNCS, pages 606–636. Springer, Heidelberg, December 2021.
  * [HMNY22] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa.  Certified everlasting zero-knowledge proof for QMA.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 239–268. Springer, Heidelberg, August 2022.
  * [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, EUROCRYPT 2023, Part I, volume 14004 of LNCS, pages 639–667. Springer, Heidelberg, April 2023.
  * [Hol73] A.S Holevo.  Statistical decision theory for quantum systems.  Journal of Multivariate Analysis, 3(4):337–394, 1973.
  * [JQSY19] Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun.  General linear group action on tensors: A candidate for post-quantum cryptography.  In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part I, volume 11891 of LNCS, pages 251–281. Springer, Heidelberg, December 2019\.
  * [KL07] Jonathan Katz and Yehuda Lindell.  Introduction to Modern Cryptography.  Chapman and Hall/CRC Press, 2007.
  * [KN22] Fuyuki Kitagawa and Ryo Nishimaki.  Functional encryption with secure key leasing.  In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV, volume 13794 of LNCS, pages 569–598. Springer, Heidelberg, December 2022.
  * [KNY21] Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.  Secure software leasing from standard assumptions.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 31–61. Springer, Heidelberg, November 2021\.
  * [KNY23] Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.  Publicly verifiable deletion from minimal assumptions.  Cryptology ePrint Archive, Paper 2023/538, 2023.  https://eprint.iacr.org/2023/538.
  * [LLQZ22] Jiahui Liu, Qipeng Liu, Luowen Qian, and Mark Zhandry.  Collusion resistant copy-protection for watermarkable functionalities.  In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022, Part I, volume 13747 of LNCS, pages 294–323. Springer, Heidelberg, November 2022.
  * [Mer88] Ralph C. Merkle.  A digital signature based on a conventional encryption function.  In Carl Pomerance, editor, CRYPTO’87, volume 293 of LNCS, pages 369–378. Springer, Heidelberg, August 1988.
  * [MY22] Tomoyuki Morimae and Takashi Yamakawa.  Quantum commitments and signatures without one-way functions.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 269–295. Springer, Heidelberg, August 2022.
  * [NY89] Moni Naor and Moti Yung.  Universal one-way hash functions and their cryptographic applications.  In 21st ACM STOC, pages 33–43. ACM Press, May 1989.
  * [Por23] Alexander Poremba.  Quantum proofs of deletion for learning with errors.  ITCS 2023: 14th Innovations in Theoretical Computer Science, 2023.
  * [Reg05] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  In STOC, pages 84–93. ACM Press, 2005.
  * [Riv98] Ronald L. Rivest.  Can we eliminate certificate revocation lists?  In Rafael Hirschfeld, editor, Proceedings Financial Cryptography ’98, volume 1465 of Lecture Notes in Computer Science, pages 178–183. Springer, 1998.
  * [RS19] Roy Radian and Or Sattath.  Semi-quantum money.  arXiv/1908.08889, 2019.
  * [Shm22] Omri Shmueli.  Semi-quantum tokenized signatures.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 296–319. Springer, Heidelberg, August 2022.
  * [Stu95] S. Stubblebine.  Recent-secure authentication: enforcing revocation in distributed systems.  In 2012 IEEE Symposium on Security and Privacy, page 0224, Los Alamitos, CA, USA, may 1995. IEEE Computer Society.
  * [Unr15] Dominique Unruh.  Revocable quantum timed-release encryption.  J. ACM, 62(6):49:1–49:76, 2015.
  * [Wie83] Stephen Wiesner.  Conjugate coding.  SIGACT News, 15(1):78–88, 1983.
  * [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.

##  Appendix A Proof of Theorem 5.4

Here we show Theorem 5.4. Assume that there exist a QPT adversary
$\mathcal{A}_{\lambda}$, a polynomial ${\mathrm{poly}}$, and bits
$b_{1},...,b_{n}\in\\{0,1\\}$ such that

$\displaystyle\left\|\widetilde{\mathcal{Z}}_{\lambda}^{\mathcal{A}_{\lambda}}(b_{1},...,b_{n})-\widetilde{\mathcal{Z}}_{\lambda}^{\mathcal{A}_{\lambda}}(0,...,0)\right\|_{\rm
tr}\geq\frac{1}{{\mathrm{poly}}(\lambda)}$ (219)

for infinitely often $\lambda$. Then due to the triangle inequality of the
trace distance, there exist an integer $k$ and bits
$a_{1},...,a_{k-1},a_{k+1},...,a_{n}\in\\{0,1\\}$ such that

$\displaystyle\left\|\widetilde{\mathcal{Z}}_{\lambda}^{\mathcal{A}_{\lambda}}(a_{1},...,a_{k-1},0,a_{k+1},...,a_{n})-\widetilde{\mathcal{Z}}_{\lambda}^{\mathcal{A}_{\lambda}}(a_{1},...,a_{k-1},1,a_{k+1},...,a_{n})\right\|_{\rm
tr}\geq\frac{1}{{\mathrm{poly}}(\lambda)}.$ (220)

From such $\mathcal{A}_{\lambda}$, we can construct a QPT adversary
$\mathcal{B}_{\lambda}$ that breaks Theorem 5.3 as follows:

  1. 1.

Get

$\displaystyle\mathcal{Z}_{\lambda}\left(x_{0}\oplus
x_{1},y_{0},y_{1},\frac{\ket{x_{0}}+(-1)^{b}\ket{x_{1}}}{\sqrt{2}}\right)$
(221)

as input.

  2. 2.

Sample $x_{i}^{0},x_{i}^{1}\leftarrow\\{0,1\\}^{\ell(\lambda)}$ for each
$i\in[n]\setminus\\{k\\}$. Define $y_{i}^{0}=f(x_{i}^{0})$ and
$y_{i}^{1}=f(x_{i}^{1})$ for each $i\in[n]\setminus\\{k\\}$. Initialize
$\mathcal{A}_{\lambda}$ with

$\displaystyle\bigotimes_{i=1}^{k-1}\mathcal{Z}_{\lambda}\left(x_{i}^{0}\oplus
x_{i}^{1},y_{i}^{0},y_{i}^{1},\frac{\ket{x_{i}^{0}}+(-1)^{a_{i}}\ket{x_{i}^{1}}}{\sqrt{2}}\right)$
(222) $\displaystyle\otimes\mathcal{Z}_{\lambda}\left(x_{0}\oplus
x_{1},y_{0},y_{1},\frac{\ket{x_{0}}+(-1)^{b}\ket{x_{1}}}{\sqrt{2}}\right)$
(223)
$\displaystyle\otimes\bigotimes_{i=k+1}^{n}\mathcal{Z}_{\lambda}\left(x_{i}^{0}\oplus
x_{i}^{1},y_{i}^{0},y_{i}^{1},\frac{\ket{x_{i}^{0}}+(-1)^{a_{i}}\ket{x_{i}^{1}}}{\sqrt{2}}\right).$
(224)

  3. 3.

$\mathcal{A}_{\lambda}$’s output is parsed as strings
$x^{\prime}_{i}\in\\{0,1\\}^{\ell(\lambda)}$ for $i\in[n]$ and a residual
state on register $\mathsf{A}^{\prime}$.

  4. 4.

If $f(x^{\prime}_{i})\in\\{y_{i}^{0},y_{i}^{1}\\}$ for all
$i\in[n]\setminus\\{k\\}$, then output $x_{k}^{\prime}$ and
$\mathsf{A}^{\prime}$. Otherwise output $\bot$.

It is clear that the output of the above game for $b\in\\{0,1\\}$ is
equivalent to
$\widetilde{\mathcal{Z}}_{\lambda}^{\mathcal{A}_{\lambda}}(a_{1},...,a_{k-1},b,a_{k+1},...,a_{n})$
(up to $\\{x_{i}^{0},x_{i}^{1}\\}_{i\in[n]\setminus\\{k\\}}$). Therefore, from
Equation 220, $\mathcal{B}_{\lambda}$ breaks Theorem 5.3.

##  Appendix B Digital Signatures with Quantum Revocable Signing Keys from
Group Actions

In this section, we construct digital signatures with quantum revocable
signing keys from group actions. Note that in this case, the revocation is
quantum, i.e., not a classical deletion certificate but the quantum signing
key itself is returned. The syntax, correctness, and security are the same as
those of the classical revocation case, Definition 4.1, except that there is
no deletion algorithm, $\mathsf{Del}$, and $\mathsf{cert}$ is not a classical
bit string but the signing key $\mathsf{sigk}_{i}$ itself.

The outline of this section is as follows. In Section B.1, we review basics of
group actions. We then review claw-free swap-trapdoor function pairs [HMY23]
and mention that it can be constructed from group actions with the one-wayness
property in Section B.2. We next define two-tier quantum lightning with
classical semi-verification in Section B.3, and construct it from claw-free
swap-trapdoor function pairs (and therefore from group actions with the one-
wayness property) in Section B.4. We finally construct digital signatures with
quantum revocable signing keys from two-tier quantum lightning with classical
semi-verfication in Section B.5.

###  B.1 Group Actions

Here we review basics of group actions [JQSY19]. Content of this subsection is
taken from [HMY23]. First, group actions are defined as follows.

###### Definition B.1 (Group actions).

Let $G$ be a (not necessarily abelian) group, $S$ be a set, and $\star:G\times
S\rightarrow S$ be a function where we write $g\star s$ to mean $\star(g,s)$.
We say that $(G,S,\star)$ is a _group action_ if it satisfies the following:

  1. 1.

For the identity element $e\in G$ and any $s\in S$, we have $e\star s=s$.

  2. 2.

For any $g,h\in G$ and any $s\in S$, we have $(gh)\star s=g\star(h\star s)$.

To be useful for cryptography, we have to at least assume that basic
operations about $(G,S,\star)$ have efficient algorithms. We require the
following efficient algorithms similarly to [JQSY19].

###### Definition B.2 (Group actions with efficient algorithms).

We say that a group action $(G,S,\star)$ has _efficient algorithms_ if it
satisfies the following:161616Strictly speaking, we have to consider a family
$\\{(G_{\lambda},S_{\lambda},\star_{\lambda})\\}_{\lambda\in\mathbb{N}}$ of
group actions parameterized by the security parameter to meaningfully define
the efficiency requirements. We omit the dependence on $\lambda$ for
notational simplicity throughout the paper.

  * Unique representations:

Each element of $G$ and $S$ can be represented as a bit string of length
${\mathrm{poly}}(\lambda)$ in a unique manner. Thus, we identify these
elements and their representations.

  * Group operations:

There are classical deterministic polynomial-time algorithms that compute $gh$
from $g\in G$ and $h\in G$ and $g^{-1}$ from $g\in G$.

  * Group action:

There is a classical deterministic polynomial-time algorithm that computes
$g\star s$ from $g\in G$ and $s\in S$.

  * Efficient recognizability:

There are classical deterministic polynomial-time algorithms that decide if a
given bit string represents an element of $G$ or $S$, respectively.

  * Random sampling:

There are PPT algorithms that sample almost uniform elements of $G$ or $S$
(i.e., the distribution of the sample is statistically close to the uniform
distribution), respectively.

  * Superposition over $G$:

There is a QPT algorithm that generates a state whose trace distance from
$\ket{G}\coloneqq\sum_{g\in G}\ket{g}$ is ${\mathsf{negl}}(\lambda)$.

######  Remark B.3 (A convention on “Random sampling” and “Superposition over
$G$” properties).

In the rest of this paper, we assume that we can sample elements from
_exactly_ uniform distributions of $G$ and $S$. Similarly, we assume that we
can _exactly_ generate $\ket{G}$ in QPT. They are just for simplifying the
presentations of our results, and all the results hold with the above
imperfect version with additive negligible loss for security or correctness.

######  Remark B.4.

The above requirements are identical to those in [JQSY19] except for the
“superposition over $G$” property. We remark that all candidate constructions
proposed in [JQSY19] satisfy this property.

We define one-wayness [JQSY19] as follows.

###### Definition B.5 (One-wayness).

We say that a group action $(G,S,\star)$ with efficient algorithms is _one-
way_ if for any non-uniform QPT adversary $\mathcal{A}$, we have

$\displaystyle\Pr\left[g^{\prime}\star s=g\star
s:\begin{array}[]{l}s\leftarrow S,g\leftarrow
G,g^{\prime}\leftarrow\mathcal{A}(s,g\star
s)\end{array}\right]={\mathsf{negl}}(\lambda).$

###  B.2 Swap-Trapdoor Functions Pairs

In order to show the construction of two-tier quantum lightning with classical
semi-verification from group actions, it is convenient to use swap-trapdoor
function pairs (STF), which was introduced in [HMY23]. In this subsection, we
define STF and point out that STF can be constructed from group actions
[JQSY19, HMY23]. Content of this subsection is taken from [HMY23].

The formal definition of STF is given as follows.

###### Definition B.6 (Swap-Trapdoor Function Pair [HMY23]).

A _swap-trapdoor function pair (STF)_ consists a set
$(\mathsf{Setup},\mathsf{Eval},\mathsf{Swap})$ of algorithms such that

  * •

$\mathsf{Setup}(1^{\lambda})\to(\mathsf{pp},\mathsf{td})$: It is a PPT
algorithm that takes the security parameter $\lambda$ as input, and outputs a
public parameter $\mathsf{pp}$ and a trapdoor $\mathsf{td}$. The public
parameter $\mathsf{pp}$ specifies functions
$f_{b}^{(\mathsf{pp})}:\mathcal{X}\rightarrow\mathcal{Y}$ for each
$b\in\\{0,1\\}$. We often omit the dependence on $\mathsf{pp}$ and simply
write $f_{b}$ when it is clear from the context.

  * •

$\mathsf{Eval}(\mathsf{pp},b,x)\to y$: It is a deterministic classical
polynomial-time algorithm that takes a public parameter $\mathsf{pp}$, a bit
$b\in\\{0,1\\}$, and an element $x\in\mathcal{X}$ as input, and outputs
$y\in\mathcal{Y}$.

  * •

$\mathsf{Swap}(\mathsf{td},b,x)\to x^{\prime}$: It is a deterministic
classical polynomial-time algorithm that takes a trapdoor $\mathsf{td}$, a bit
$b\in\\{0,1\\}$, and an element $x\in\mathcal{X}$ as input, and outputs
$x^{\prime}\in\mathcal{X}$.

We require a STF to satisfy the following:

Evaluation correctness. For any
$(\mathsf{pp},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})$ ,
$b\in\\{0,1\\}$, and $x\in\mathcal{X}$, we have
$\mathsf{Eval}(\mathsf{pp},b,x)=f_{b}(x)$.

Swapping correctness. For any
$(\mathsf{pp},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})$,
$b\in\\{0,1\\}$, and $x\in\mathcal{X}$, if we let
$x^{\prime}\leftarrow\mathsf{Swap}(\mathsf{td},b,x)$, then we have $f_{b\oplus
1}(x^{\prime})=f_{b}(x)$ and $\mathsf{Swap}(\mathsf{td},b\oplus
1,x^{\prime})=x$. In particular, $\mathsf{Swap}(\mathsf{td},b,\cdot)$ induces
an efficiently computable and invertible one-to-one mapping between
$f^{-1}_{0}(y)$ and $f^{-1}_{1}(y)$ for any $y\in\mathcal{Y}$.

Efficient random sampling over $\mathcal{X}$. There is a PPT algorithm that
samples an almost uniform element of $\mathcal{X}$ (i.e., the distribution of
the sample is statistically close to the uniform distribution).

Efficient superposition over $\mathcal{X}$. There is a QPT algorithm that
generates a state whose trace distance from
$\ket{\mathcal{X}}=\frac{1}{\sqrt{|\mathcal{X}|}}\sum_{x\in\mathcal{X}}|x\rangle$
is ${\mathsf{negl}}(\lambda)$.

Claw-freeness. For any non-uniform QPT algorithm $\mathcal{A}$,

$\displaystyle\Pr[f_{0}(x_{0})=f_{1}(x_{1}):(\mathsf{pp},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda}),(x_{0},x_{1})\leftarrow\mathcal{A}(\mathsf{pp})]={\mathsf{negl}}(\lambda).$

######  Remark B.7 (A convention on “Efficient random sampling over
$\mathcal{X}$” and “Efficient superposition over $\mathcal{X}$” properties).

In the rest of this paper, we assume that we can sample elements from
_exactly_ the uniform distribution of $\mathcal{X}$. Similarly, we assume that
we can _exactly_ generate $\ket{\mathcal{X}}$ in QPT. They are just for
simplifying the presentations of our results, and all the results hold with
the above imperfect version with additive negligible loss for security or
correctness.

A STF can be constructed from group actions. Let $(G,S,\star)$ be a group
action with efficient algorithms (as defined in Definition B.2). Then, we
construct a STF as follows.

  * •

$\mathsf{Setup}(1^{\lambda})$: Generate $s_{0}\leftarrow S$ and $g\leftarrow
G$, set $s_{1}\coloneqq g\star s_{0}$, and output
$\mathsf{pp}\coloneqq(s_{0},s_{1})$ and $\mathsf{td}\coloneqq g$. For
$b\in\\{0,1\\}$, we define $f_{b}:G\rightarrow S$ by $f_{b}(h)\coloneqq h\star
s_{b}$.

  * •

$\mathsf{Eval}(\mathsf{pp}=(s_{0},s_{1}),b,h)$: Output $f_{b}(h)=h\star
s_{b}$.

  * •

$\mathsf{Swap}(\mathsf{td}=g,b,h)$: If $b=0$, output $hg^{-1}$. If $b=1$,
output $hg$.

In [HMY23], the following theorem is shown.

###### Theorem B.8 ([HMY23]).

If $(G,S,\star)$ is one-way, then
$(\mathsf{Setup},\mathsf{Eval},\mathsf{Swap})$ is claw-free.

###  B.3 Definition of Two-Tier Quantum Lightning with Classical Semi-
Verification

The formal definition of two-tier quantum lightning with classical semi-
verification is given as follows. The difference from the original two-tier
quantum lightning [KNY21] is that the semi-verification algorithm
$\mathsf{SemiVer}$ accepts a classical certificate $\mathsf{cert}$ instead of
a quantum state, and there is an additional QPT algorithm $\mathsf{Del}$ that
outputs $\mathsf{cert}$ on input $\psi$.

###### Definition B.9 (Two-Tier Quantum Lightning with Classical Semi-
Verification).

Two-tier quantum lighting with classical semi-verification is a set
$(\mathsf{Setup},\mathsf{StateGen},\mathsf{Del},\mathsf{SemiVer},\mathsf{FullVer})$
of algorithms such that

  * •

$\mathsf{Setup}(1^{\lambda})\to(\mathsf{sk},\mathsf{pk}):$ It is a QPT
algorithm that, on input the security parameter $\lambda$, outputs a classical
secret key $\mathsf{sk}$ and a classical public key $\mathsf{pk}$.

  * •

$\mathsf{StateGen}(\mathsf{pk})\to(\psi,\mathsf{snum}):$ It is a QPT algorithm
that, on input $\mathsf{pk}$, outputs a quantum state $\psi$ and a classical
serial number $\mathsf{snum}$.

  * •

$\mathsf{Del}(\psi)\to\mathsf{cert}:$ It is a QPT algorithm that, on input
$\psi$, outputs a classical certificate $\mathsf{cert}$.

  * •

$\mathsf{SemiVer}(\mathsf{pk},\mathsf{snum},\mathsf{cert})\to\top/\bot:$ It is
a classical deterministic polynomial-time algorithm that, on input
$\mathsf{pk}$, $\mathsf{cert}$, and $\mathsf{snum}$, outputs $\top/\bot$.

  * •

$\mathsf{FullVer}(\mathsf{sk},\mathsf{snum},\psi)\to\top/\bot:$ It is a QPT
algorithm that, on input $\mathsf{sk}$, $\psi$, and $\mathsf{snum}$, outputs
$\top/\bot$.

We require the following properties.

#### Correctness:

$\displaystyle\Pr\left[\top\leftarrow\mathsf{SemiVer}(\mathsf{pk},\mathsf{snum},\mathsf{cert}):\begin{array}[]{rr}(\mathsf{sk},\mathsf{pk})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(\psi,\mathsf{snum})\leftarrow\mathsf{StateGen}(\mathsf{pk})\\\
\mathsf{cert}\leftarrow\mathsf{Del}(\psi)\end{array}\right]\geq
1-{\mathsf{negl}}(\lambda)$ (228)

and

$\displaystyle\Pr\left[\top\leftarrow\mathsf{FullVer}(\mathsf{sk},\mathsf{snum},\psi):\begin{array}[]{rr}(\mathsf{sk},\mathsf{pk})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(\psi,\mathsf{snum})\leftarrow\mathsf{StateGen}(\mathsf{pk})\\\
\end{array}\right]\geq 1-{\mathsf{negl}}(\lambda).$ (231)

#### Security:

For any QPT adversary $\mathcal{A}$,

$\displaystyle\Pr\left[\top\leftarrow\mathsf{SemiVer}(\mathsf{pk},\mathsf{snum},\mathsf{cert})\wedge\top\leftarrow\mathsf{FullVer}(\mathsf{sk},\mathsf{snum},\psi):\begin{array}[]{rr}(\mathsf{sk},\mathsf{pk})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(\mathsf{cert},\psi,\mathsf{snum})\leftarrow\mathcal{A}(\mathsf{pk})\\\
\end{array}\right]\leq{\mathsf{negl}}(\lambda).$ (234)

###  B.4 Construction from Group Actions

Here we construct two-tier quantum lightning with classical semi-verification
from STF (and therefore from group actions).

###### Theorem B.10.

If group actions with the one-wayness property exist, then two-tier quantum
lightning with classical semi-verification exists.

###### Proof of Theorem B.10.

Let $(\mathsf{Setup},\mathsf{Eval},\mathsf{Swap})$ be a SFT. From Theorem B.8,
a SFT exists if group actions that satisfy one-wayness exist. From it, we
construct two-tier quantum lightning with classical semi-verification
$(\mathsf{Setup},\mathsf{StateGen},\mathsf{Del},\mathsf{SemiVer},\mathsf{FullVer})$
as follows.

  * •

$\mathsf{Setup}(1^{\lambda})\to(\mathsf{sk},\mathsf{pk}):$ Run
$(\mathsf{pp},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})$. Output
$\mathsf{pk}\coloneqq\mathsf{pp}$ and
$\mathsf{sk}\coloneqq(\mathsf{pp},\mathsf{td})$.

  * •

$\mathsf{StateGen}(\mathsf{pk})\to(\psi,\mathsf{snum}):$ Parse
$\mathsf{pk}\coloneqq\mathsf{pp}$. For each $i\in[n]$, repeat the following:

    1. 1.

Generate
$\sum_{b\in\\{0,1\\}}\sum_{x\in\mathcal{X}}\ket{b}\ket{x}\ket{\mathsf{Eval}(\mathsf{pp},b,x)}$.

    2. 2.

Measure the third register in the computational basis to get the measurement
result $y_{i}$. The post-measurement state is
$\psi_{i}\coloneqq\ket{0}\otimes\sum_{x\in
f_{0}^{-1}(y_{i})}\ket{x}+\ket{1}\otimes\sum_{x\in f_{1}^{-1}(y_{i})}\ket{x}$.

Output $\psi\coloneqq\bigotimes_{i\in[n]}\psi_{i}$ and
$\mathsf{snum}\coloneqq\\{y_{i}\\}_{i\in[n]}$.

  * •

$\mathsf{Del}(\psi)\to\mathsf{cert}:$ Parse
$\psi=\bigotimes_{i\in[n]}\psi_{i}$. Measure $\psi_{i}$ in the computational
basis to get the result $(b_{i},z_{i})\in\\{0,1\\}\times\mathcal{X}$ for each
$i\in[n]$. Output $\mathsf{cert}\coloneqq\\{b_{i},z_{i}\\}_{i\in[n]}$.

  * •

$\mathsf{SemiVer}(\mathsf{pk},\mathsf{cert},\mathsf{snum})\to\top/\bot:$ Parse
$\mathsf{pk}\coloneqq\mathsf{pp}$, $\mathsf{cert}=\\{b_{i},z_{i}\\}_{i\in[n]}$
and $\mathsf{snum}=\\{y_{i}\\}_{i\in[n]}$. If
$\mathsf{Eval}(\mathsf{pp},b_{i},z_{i})=y_{i}$ for all $i\in[n]$, output
$\top$. Otherwise, output $\bot$.

  * •

$\mathsf{FullVer}(\mathsf{sk},\psi,\mathsf{snum})\to\top/\bot:$ Parse
$\mathsf{sk}\coloneqq(\mathsf{pp},\mathsf{td})$,
$\psi=\bigotimes_{i\in[n]}\psi_{i}$, and
$\mathsf{snum}=\\{y_{i}\\}_{i\in[n]}$. For each $i\in[n]$, do the following:

    1. 1.

Apply unitary $U$ such that
$U\ket{b}\ket{x}\ket{0...0}=\ket{b}\ket{x}\ket{\mathsf{Eval}(\mathsf{pp},b,x)}$
on $\psi_{i}\otimes\ket{0...0}\bra{0...0}$, and measure the third register in
the computational basis. If the measurement result is not $y_{i}$, output
$\bot$ and abort.

    2. 2.

Apply the operation that maps $x$ to $\mathsf{Swap}(\mathsf{td},1,x)$ on the
second register of the post-measurement state conditioned that the first
register is 1.171717Such an operation can be done in the following way: First,
change $\ket{x}\ket{0...0}$ into
$\ket{x}\ket{\mathsf{Swap}(\mathsf{td},1,x)}$. Then, change this state into
$\ket{x\oplus\mathsf{Swap}(\mathsf{td},0,\mathsf{Swap}(\mathsf{td},1,x))}\ket{\mathsf{Swap}(\mathsf{td},1,x)}=\ket{0...0}\ket{\mathsf{Swap}(\mathsf{td},1,x)}$.
Finally, if we swap the first and the second register, we get
$\ket{\mathsf{Swap}(\mathsf{td},1,x)}\ket{0...0}$. Measure the first register
in the Hadamard basis. If the result is 1 (i.e., if the result $\ket{-}$ is
obtained), output $\bot$ and abort.

Output $\top$.

The correctness for the semi-verification is clear. The correctness for the
full-verification is also clear because if each $\psi_{i}$ is

$\displaystyle\psi_{i}=\ket{0}\otimes\sum_{x\in
f_{0}^{-1}(y_{i})}\ket{x}+\ket{1}\otimes\sum_{x\in f_{1}^{-1}(y_{i})}\ket{x},$
(235)

then the first operation of the semi-verification algorithm does not change
it, and the second operation gives

$\displaystyle\ket{0}\otimes\sum_{x\in
f_{0}^{-1}(y_{i})}\ket{x}+\ket{1}\otimes\sum_{x\in
f_{1}^{-1}(y_{i})}\ket{\mathsf{Swap}(\mathsf{td},1,x)}$
$\displaystyle=\ket{0}\otimes\sum_{x\in
f_{0}^{-1}(y_{i})}\ket{x}+\ket{1}\otimes\sum_{x\in f_{0}^{-1}(y_{i})}\ket{x}$
(236) $\displaystyle=\ket{+}\otimes\sum_{x\in f_{0}^{-1}(y_{i})}\ket{x}.$
(237)

To show the security, we define the sequence of hybrids. Hybrid 0 (Figure 1)
is the original security game. For the sake of contradiction, we assume that
there exists a QPT adversary $\mathcal{A}$ such that

$\displaystyle\Pr[{\rm
Hybrid~{}0}\to\top]\geq\frac{1}{{\mathrm{poly}}(\lambda)}$ (238)

for infinitely many $\lambda$.

Hybrid 0 1. The challenger $\mathcal{C}$ runs
$(\mathsf{td},\mathsf{pp})\leftarrow\mathsf{Setup}(1^{\lambda})$, and sends
$\mathsf{pp}$ to $\mathcal{A}$. 2. $\mathcal{A}$ sends a quantum state $\psi$
on the register $\mathbf{F}$, a classical bit string
$\mathsf{cert}=\\{b_{i},z_{i}\\}_{i\in[n]}$, and bit strings
$\mathsf{snum}=\\{y_{i}\\}_{i\in[n]}$ to $\mathcal{C}$. The register
$\mathbf{F}$ consists of sub-registers $(\mathbf{F}_{1},...,\mathbf{F}_{n})$.
Each $\mathbf{F}_{i}$ is a $(|\mathcal{X}|+1)$-qubit register. 3. If
$\mathsf{Eval}(\mathsf{pp},b_{i},z_{i})\neq y_{i}$ for an $i\in[n]$ , output
$\bot$ and abort. 4. From $i=1$ to $n$, $\mathcal{C}$ does the following: (a)
Apply $U$ such that
$U\ket{b}\ket{x}\ket{0...0}=\ket{b}\ket{x}\ket{\mathsf{Eval}(\mathsf{pp},b,x)}$
on $\mathbf{F}_{i}\otimes\ket{0...0}\bra{0...0}$, and measure the ancilla
register in the computational basis. If the result is not $y_{i}$, output
$\bot$ and abort. (b) Apply the operation that maps $x$ to
$\mathsf{Swap}(\mathsf{td},1,x)$ on the second register of the post-
measurement state on $\mathbf{F}_{i}$ conditioned that the first qubit is 1.
(c) Measure the first qubit of $\mathbf{F}_{i}$ in the Hadamard basis. If the
result is 1 (i.e., if the result is $\ket{-}$), output $\bot$ and abort. 5.
Output $\top$.

Figure 1:  Hybrid 0

Hybrid 1 1. The same as Hybrid 0. 2. The same as Hybrid 0. 3. The same as
Hybrid 0. 4. From $i=1$ to $n$, $\mathcal{C}$ does the following: (a) The same
as Hybrid 0. (b) The same as Hybrid 0. (c) Measure all qubits of
$\mathbf{F}_{i}$ in the computational basis to get the result
$(e_{i},w_{i})\in\\{0,1\\}\times\mathcal{X}$. 5. If there is $i\in[n]$ such
that $b_{i}\neq e_{i}$, output $\top$. Otherwise, output $\bot$.

Figure 2:  Hybrid 1

Hybrid 2 1. The same as Hybrid 1. 2. The same as Hybrid 1. 3. The same as
Hybrid 1. 4. The same as Hybrid 1 except that the step (b) is skipped for each
$i\in[n]$. 5. The same as Hybrid 1.

Figure 3:  Hybrid 2

Hybrid 3 1. The same as Hybrid 2. In addition, $\mathcal{C}$ chooses
$i^{*}\leftarrow[n]$. 2. The same as Hybrid 2. 3. The same as Hybrid 2. 4. The
same as Hybrid 2. 5. If $b_{i^{*}}\neq e_{i^{*}}$, output $\top$. Otherwise,
output $\bot$.

Figure 4:  Hybrid 3

###### Lemma B.11.

If $\Pr[{\rm Hybrid~{}0}\to\top]\geq\frac{1}{{\mathrm{poly}}(\lambda)}$ for
infinitely many $\lambda$, then $\Pr[{\rm
Hybrid~{}1}\to\top]\geq\frac{1}{{\mathrm{poly}}(\lambda)}$ for infinitely many
$\lambda$.

###### Proof.

Let $\Pr[b_{1},...,b_{n}]$ be the probability that $\mathcal{A}$ outputs
$\\{b_{i}\\}_{i\in[n]}$ and $\mathcal{C}$ finishes Item 4b of Figure 1 without
aborting. Then

$\displaystyle\epsilon$ $\displaystyle\coloneqq\Pr[\mbox{Hybrid 0}\to\top]$
(239)
$\displaystyle=\sum_{b_{1},...,b_{n}}\Pr[b_{1},...,b_{n}]\mathrm{Tr}[(\ket{+}\bra{+}^{\otimes
n}\otimes I)\psi_{b_{1},...,b_{n}}],$ (240)

where $\psi_{b_{1},...,b_{n}}$ is the state of the register $\mathbf{F}$ after
the end of Item 4b of Figure 1. From the standard average argument, we have

$\displaystyle\sum_{(b_{1},...,b_{n})\in
G}\Pr[b_{1},...,b_{n}]\geq\frac{\epsilon}{2},$ (241)

where

$\displaystyle
G\coloneqq\Big{\\{}(b_{1},...,b_{n}):\mathrm{Tr}[(\ket{+}\bra{+}^{\otimes
n}\otimes I)\psi_{b_{1},...,b_{n}}]\geq\frac{\epsilon}{2}\Big{\\}}.$ (242)

Define

$\displaystyle\Lambda_{b_{1},...,b_{n}}\coloneqq\sum_{(e_{1},...,e_{n})\in\\{0,1\\}^{n}\setminus(b_{1},...,b_{n})}\ket{e_{1},e_{2},...,e_{n}}\bra{e_{1},e_{2},...,e_{n}}.$
(243)

As is shown later, for any $m$-qubit state $\rho$, where $m\geq n$, and any
$(b_{1},...,b_{n})\in\\{0,1\\}^{n}$, we have

$\displaystyle\mathrm{Tr}[(\ket{+}\bra{+}^{\otimes n}\otimes I)\rho]\leq
2\mathrm{Tr}[(\Lambda_{b_{1},...,b_{n}}\otimes I)\rho]+2^{-n+1}.$ (244)

Then

$\displaystyle\Pr[\mbox{Hybrid 1}\to\top]$
$\displaystyle=\sum_{b_{1},...,b_{n}}\Pr[b_{1},...,b_{n}]\mathrm{Tr}[(\Lambda_{b_{1},...,b_{n}}\otimes
I)\psi_{b_{1},...,b_{n}}]$ (245) $\displaystyle\geq\sum_{(b_{1},...,b_{n})\in
G}\Pr[b_{1},...,b_{n}]\mathrm{Tr}[(\Lambda_{b_{1},...,b_{n}}\otimes
I)\psi_{b_{1},...,b_{n}}]$ (246) $\displaystyle\geq\sum_{(b_{1},...,b_{n})\in
G}\Pr[b_{1},...,b_{n}]\Big{(}\frac{1}{2}\mathrm{Tr}\left[(\ket{+}\bra{+}^{\otimes
n}\otimes I)\psi_{b_{1},...,b_{n}}\right]-2^{-n}\Big{)}$ (247)
$\displaystyle\geq\frac{\epsilon}{2}\Big{(}\frac{\epsilon}{4}-2^{-n}\Big{)}$
(248) $\displaystyle\geq\frac{1}{{\mathrm{poly}}(\lambda)}.$ (249)

Here, to derive Equation 247, we have used Equation 244. To derive Equation
248, we have used Equation 241 and Equation 242. ∎

###### Lemma B.12.

$\Pr[{\rm Hybrid~{}2}\to\top]=\Pr[{\rm Hybrid~{}1}\to\top]$.

###### Proof.

The controlled $\mathsf{Swap}(\mathsf{td},1,\cdot)$ operations do not change
the distribution of $(e_{1},...,e_{n})$. ∎

###### Lemma B.13.

$\Pr[{\rm Hybrid~{}3}\to\top]\geq\frac{1}{n}\Pr[{\rm Hybrid~{}2}\to\top]$.

###### Proof.

It is trivial. ∎

In summary, from Equation 238 and Lemmata B.11, B.12 and B.13, we conclude
that $\Pr[{\rm Hybrid~{}3}\to\top]\geq\frac{1}{{\mathrm{poly}}(\lambda)}$ for
infinitely many $\lambda$. From such $\mathcal{A}$ of Hybrid 3, we construct a
QPT adversary $\mathcal{B}$ that breaks the claw-freeness of STF as in Figure
5. It is easy to verify that

$\displaystyle\Pr[\mathcal{B}~{}\mbox{wins}]$ $\displaystyle\geq\Pr[{\rm
Hybrid~{}3}\to\top]$ (250)
$\displaystyle\geq\frac{1}{{\mathrm{poly}}(\lambda)}$ (251)

for infinitely many $\lambda$. Therefore, $\mathcal{B}$ breaks the claw-
freeness of the STF.

$\mathcal{B}$ 1. Get $\mathsf{pp}$ as input. 2. Run
$(\psi,\\{b_{i},z_{i}\\}_{i\in[n]},\\{y_{i}\\}_{i\in[n]})\leftarrow\mathcal{A}(\mathsf{pp})$.
Choose $i^{*}\leftarrow[n]$. 3. Measure all qubits of $\mathbf{F}_{i^{*}}$ in
the computational basis to get the result $(e_{i^{*}},w_{i^{*}})$. 4. If
$b_{i^{*}}=0$ and $e_{i^{*}}=1$, output $(z_{i^{*}},w_{i^{*}})$. If
$b_{i^{*}}=1$ and $e_{i^{*}}=0$, output $(w_{i^{*}},z_{i^{*}})$. Otherwise,
output $\bot$.

Figure 5:  $\mathcal{B}$

∎

###### Proof of Equation 244.

Because of the linearity of $\mathrm{Tr}$, we have only to show it for pure
states. We have

$\displaystyle\mathrm{Tr}[(\ket{+}\bra{+}^{\otimes n}\otimes
I)\ket{\psi}\bra{\psi}]$ $\displaystyle=\Big{\|}(\bra{+}^{\otimes n}\otimes
I)\ket{\psi}\Big{\|}^{2}$ (252)
$\displaystyle=\frac{1}{2^{n}}\Big{\|}\sum_{e_{1},...,e_{n}}(\bra{e_{1},...,e_{n}}\otimes
I)|\psi\rangle\Big{\|}^{2}$ (253)
$\displaystyle=\frac{1}{2^{n}}\Big{\|}\sum_{(e_{1},...,e_{n})\neq(b_{1},...,b_{n})}(\bra{e_{1},...,e_{n}}\otimes
I)|\psi\rangle+(\bra{b_{1},...,b_{n}}\otimes I)|\psi\rangle\Big{\|}^{2}$ (254)
$\displaystyle\leq\frac{1}{2^{n-1}}\Big{\|}\sum_{(e_{1},...,e_{n})\neq(b_{1},...,b_{n})}(\bra{e_{1},...,e_{n}}\otimes
I)|\psi\rangle\Big{\|}^{2}$ (255)
$\displaystyle~{}~{}~{}~{}+\frac{1}{2^{n-1}}\Big{\|}(\bra{b_{1},...,b_{n}}\otimes
I)|\psi\rangle\Big{\|}^{2}$ (256)
$\displaystyle\leq\frac{1}{2^{n-1}}(2^{n}-1)\sum_{(e_{1},...,e_{n})\neq(b_{1},...,b_{n})}\|(\bra{e_{1},...,e_{n}}\otimes
I)|\psi\rangle\|^{2}+2^{-n+1}$ (257)
$\displaystyle=\frac{2^{n}-1}{2^{n-1}}\mathrm{Tr}[(\Lambda_{b_{1},...,b_{n}}\otimes
I)\ket{\psi}\bra{\psi}]+2^{-n+1}$ (258) $\displaystyle\leq
2\mathrm{Tr}[(\Lambda_{b_{1},...,b_{n}}\otimes
I)\ket{\psi}\bra{\psi}]+2^{-n+1}.$ (259)

Here, we have used the triangle inequality and Jensen’s inequality. ∎

###  B.5 Construction of Digital Signatures with Quantum Revocable Signing
Keys

We construct digital signatures with quantum revocable signing keys. Its
definition is given as follows.

###### Definition B.14 (Digital Signatures with quantum revocable signing
keys).

The syntax, correctness, and security are the same as those of Definition 4.1,
except that there is no deletion algorithm, $\mathsf{Del}$, and
$\mathsf{cert}$ is not a classical bit string, but the signing key
$\mathsf{sigk}_{i}$ itself.

Digital signatures with quantum revocable signing keys can be constructed from
group actions as follows.

###### Theorem B.15.

If group actions with the one-wayness property exist, then digital signatures
with quantum revocable signing keys exit.

###### Proof.

Let
$(\mathsf{QL}.\mathsf{Setup},\mathsf{QL}.\mathsf{StateGen},\mathsf{QL}.\mathsf{Del},\mathsf{QL}.\mathsf{SemiVer},\mathsf{QL}.\mathsf{FullVer})$
be two-tier quantum lightning with classical semi-verification, which exists
if group actions with the one-wayness property exist (Theorem B.10). From it,
we construct digital signatures with quantum revocable signing keys with the
message space $\\{0,1\\}$ that satisfy one-time variants of correctness, EUF-
CMA security, deletion correctness, and deletion security as follows. With
similar proofs given in Section 4, we can upgrade it to the full version of
digital signatures with quantum revocable signing keys.

  * •

$\mathsf{Setup}(1^{\lambda})\to(\mathsf{ck},\mathsf{pp}):$ Run
$(\mathsf{sk},\mathsf{pk})\leftarrow\mathsf{QL}.\mathsf{Setup}(1^{\lambda})$.
Output $\mathsf{ck}\coloneqq\mathsf{sk}$ and
$\mathsf{pp}\coloneqq\mathsf{pk}$.

  * •

$\mathsf{KeyGen}(\mathsf{pp})\to(\mathsf{sigk},\mathsf{vk}):$ Parse
$\mathsf{pp}=\mathsf{pk}$. Run
$(\psi_{0},\mathsf{snum}_{0})\leftarrow\mathsf{QL}.\mathsf{StateGen}(\mathsf{pk})$
and
$(\psi_{1},\mathsf{snum}_{1})\leftarrow\mathsf{QL}.\mathsf{StateGen}(\mathsf{pk})$.
Output $\mathsf{sigk}\coloneqq(\psi_{0},\psi_{1})$ and
$\mathsf{vk}\coloneqq(\mathsf{snum}_{0},\mathsf{snum}_{1})$.

  * •

$\mathsf{Sign}(\mathsf{pp},\mathsf{sigk},m)\to(\mathsf{sigk}^{\prime},\sigma):$
Parse $\mathsf{pp}=\mathsf{pk}$ and $\mathsf{sigk}=(\psi_{0},\psi_{1})$. Run
$\mathsf{ql}.\mathsf{cert}\leftarrow\mathsf{QL}.\mathsf{Del}(\psi_{m})$.
Output $\sigma\coloneqq\mathsf{ql}.\mathsf{cert}$ and
$\mathsf{sigk}^{\prime}\coloneqq(1-m,\psi_{1-m})$.

  * •

$\mathsf{Ver}(\mathsf{pp},\mathsf{vk},m,\sigma)\to\top/\bot:$ Parse
$\mathsf{pp}=\mathsf{pk}$,
$\mathsf{vk}=(\mathsf{snum}_{0},\mathsf{snum}_{1})$, and
$\sigma=\mathsf{ql}.\mathsf{cert}$. Run
$\mathsf{SemiVer}(\mathsf{pk},\mathsf{snum}_{m},\mathsf{ql}.\mathsf{cert})$
and output its output.

  * •

$\mathsf{Cert}(\mathsf{pp},\mathsf{vk},\mathsf{ck},\mathsf{sigk},S)\to\top/\bot:$
Parse $\mathsf{pp}=\mathsf{pk}$,
$\mathsf{vk}=(\mathsf{snum}_{0},\mathsf{snum}_{1})$,
$\mathsf{ck}=\mathsf{sk}$.

    * –

If $S=\emptyset$, parse $\mathsf{sigk}=(0,1,\psi_{0},\psi_{1})$. (Output
$\bot$ if $\mathsf{sigk}$ is not of this form.) Output $\top$ if
$\mathsf{QL}.\mathsf{FullVer}(\mathsf{sk},\mathsf{snum}_{b},\psi_{b})=\top$
for both $b=0,1$.

    * –

If $S=\\{m\\}$ for some $m\in\\{0,1\\}$, parse
$\mathsf{sigk}=(1-m,\psi_{1-m})$. (Output $\bot$ if $\mathsf{sigk}$ is not of
this form.) Output $\top$ if
$\mathsf{QL}.\mathsf{FullVer}(\mathsf{sk},\mathsf{snum}_{1-m},\psi_{1-m})=\top$.

    * –

If $S=\\{0,1\\}$, output $\bot$.

One-time correctness, one-time EUF-CMA security, one-time deletion
correctness, and one-time deletion security are shown in similar ways as those
in Section 4.2. ∎