l3regexThis package is obsolete

11affiliationtext: Sorbonne Université, CNRS, LIP622affiliationtext: Computer
Science Department, Ben-Gurion University of the Negev

# Encryption with Quantum Public Keys

Alex B. Grilo  Or Sattath  Quoc-Huy Vu

###### Abstract

It is an important question to find constructions of quantum cryptographic
protocols which rely on weaker computational assumptions than classical
protocols. Recently, it has been shown that oblivious transfer and multi-party
computation can be constructed from one-way functions, whereas this is
impossible in the classical setting in a black-box way. In this work, we study
the question of building quantum public-key encryption schemes from one-way
functions and even weaker assumptions. Firstly, we revisit the definition of
IND-CPA security to this setting. Then, we propose three schemes for quantum
public-key encryption from one-way functions, pseudorandom function-like
states with proof of deletion and pseudorandom function-like states,
respectively.

##  1 Introduction

The use of quantum resources to enable cryptographic tasks under weaker
assumptions (or even unconditionally) than classically were actually the first
concrete proposals of quantum computing, with the seminal quantum money
protocol of Wiesner [Wie83] and the key-exchange protocol of Bennet and
Brassard [BB84].

Since then, it became a fundamental question in the field of quantum
cryptography to find other primitives that can be implemented under weaker
computational assumptions. It has recently shown that there exist quantum
protocols for Oblivious Transfer (and therefore arbitrary multi-party
computation (MPC)) based on the existence of one-way functions (OWF) [BCKM21,
GLSV21]. Moreover, the proposed protocols use simple quantum technology that
is available currently. The assumption to construct these primitives has been
recently improved by showing that the existence of pseudo-random states (PRS)
is sufficient for such primitives. Notice that existence of PRS is plausibly a
strictly weaker assumption than the existence of OWF, given that PRS families
can be constructed from OWF in a black-box way [JLS18], and we have oracle
separations between PRS and OWF [Kre21, KQST22].

We notice that classically, OT and MPC are “Cryptomania” objects, meaning that
they can be constructed from assumptions that imply public-key encryption
(PKE), but there are oracle separations between OWF and PKE (and thus OT and
MPC) [IR89]. Therefore, we do not expect that such powerful objects can be
built classically from OWF. In this work, we investigate the following natural
question:

Can we have quantum protocols for public-key encryption, the heart of
Cryptomania, based on post-quantum one-way functions, or even weaker
assumptions?

Recent results imply that it is improbable to achieve PKE schemes from OWF if
the public-key and ciphertext are classical even if the encryption or
decryption algorithms are quantum [ACC+22]. Therefore, in this work, we will
consider schemes where the public-key or ciphertext are quantum states.

We notice that the first problem that we need to address is the syntax of
quantum public-key encryption (qPKE) and the corresponding security games. We
need to provide a general definition for qPKE where both the public-key and
ciphertext might be general quantum states. Furthermore, we note that if the
public-key is a quantum state, it might be measured, and the ciphertexts might
depend on the measurement outcome. This motivates a stronger definition in
which the adversary gets oracle access to the encryption, which we call IND-
CPA-EO security.

With our new security definition in hand, we propose three protocols for
implementing qPKE from OWF or weaker assumptions, with different advantages
and disadvantages. More concretely, we show the following:

  1. 1.

Assuming the existence of post-quantum OWFs, there exists a qPKE scheme with
quantum public-keys and classical ciphertexts that is IND-CPA-EO security.

  2. 2.

Assuming the existence of pseudo-random function-like states with proof of
destruction (PRFSPDs), there is a qPKE scheme with quantum public-key and
classical ciphertext that is IND-CPA-EO secure.

  3. 3.

Assuming the existence of pseudo-random function-like states (PRFSs) with
super-logarithmic input-size111Note that PRS implies PRFS with logarithmic
size inputs. No such implication is known for super-logarithmic inputs., there
is a qPKE scheme with quantum public-key and quantum ciphertext. In this
scheme, the quantum public key enables the encryption of a single message.

We would like to stress that for the first two constructions, even if the
public-key is a quantum state, the ciphertexts are classical and one quantum
public-key can be used to encrypt multiple messages. Our third construction
shows how to construct quantum public key encryption from assumptions (the
existence of pseudorandom function-like states) which are potentially weaker
than post-quantum one-way functions, but the achieved protocol only allows the
encryption of one message per public-key.

We would also like to remark that it has been recently shown that OWFs imply
PRFSs with super-logarithmic input-size [AQY21] and PRFSPDs [BBSS23].
Therefore, the security of the second and third protocols is based on a
potentially weaker cryptographic assumption than the first one. Furthermore,
PRFSs with super-logarithmic input-size is _separated_ from one-way functions
[Kre21]; therefore, our third result shows a black-box separation between a
certain form of quantum public key encryption and one-way functions.

However, the first protocol is much simpler to describe and understand since
it only uses standard (classical) cryptographic objects. Moreover, it is the
only scheme that achieves perfect correctness.

###  1.1 Technical overview

In this section we provide a technical overview of our results. In Section
1.1.1, we explain the challenges and choices in order to define qPKE and its
security definition. In Section 1.1.2, we present our constructions for qPKE.

####  1.1.1 Definitions of qPKE and IND-CPA-EO

In order to consider public-key encryption schemes with quantum public-keys,
we need to first revisit the security definition and we define a new security
game that we call IND-CPA-EO.

In the classical-key case (even with quantum ciphertexts), the adversary is
given a copy the public-key $\pk$ and therefore is able to run the encryption
algorithm $\enc(\pk,\cdot)$ as many times they want (where the only constraint
is that the adversary is polynomially bounded), and just then choose the
messages $m_{0}$ and $m_{1}$ in the IND-CPA game.

In the quantum public-key case, the first issue is that
$\enc(\rho_{\mathpzc{qpk}},\cdot)$ might consume the quantum public-key
$\rho_{\mathpzc{qpk}}$. Moreover, having more copies of the quantum state
could leak information to the adversary (which cannot be the case in the
classical-key case, since the adversary can copy $\pk$). Therefore, the first
modification in IND-CPA towards IND-CPA-EO is that the adversary is given
multiple copies of the public-key $\rho_{\mathpzc{qpk}}$.

Secondly, it could be the case that $\enc(\rho{qpk},\cdot)$ measures
$\rho{qpk}$ and modifying it to $\rho{qpk}^{\prime}$, which is different from
$\rho{qpk}$ but still a valid key that enables encryption. The second
modification that we need is syntactic: $\enc(\rho{qpk},m)$ outputs
$(\rho{qpk}^{\prime},c)$, where $c$ is used as the ciphertext and
$\rho{qpk}^{\prime}$ is used as the key to encrypt the next message.

We notice that in the previous discussion, it could also be the case that
$\enc$ measures $\rho_{\mathpzc{qpk}}$ and the measurement outcome is used to
encrypt all the measurements. In this case, even if the adversary is given
multiple copies of $\rho_{\mathpzc{qpk}}$, they would not be able to post-
select on the same measurement outcome and the distribution of ciphertexts
that they could generate would be different from the ones in the game.
Therefore, we consider a stronger notion of security where the adversary has
also access to the encryption oracle that will be used in the IND-CPA-EO game.
We notice that this issue does not make sense classically since the public-key
used by the challenger and adversary is exactly the same and the distribution
of the ciphertexts would be the same.

Finally, we would like to mention a few problems with having
$\rho_{\mathpzc{qpk}}$ as a mixed state. Firstly, there is no efficient way of
comparing if the two given public-keys are the same, preventing an honest
decryptor to “compare” a purported public-key, whereas for pure states, this
can be achieved using the swap-test. Secondly, if mixed states are allowed,
then the notions of symmetric and public key encryption coincide, both in the
classical and quantum setting: Consider a symmetric encryption scheme
$(\mathsf{SKE}.\mathsf{key\text{-}gen},\mathsf{SKE}.\enc,\mathsf{SKE}.\dec)$.
We can transform it into a public-key scheme. To generate the keys, we use the
output of $\mathsf{SKE}.\mathsf{key\text{-}gen}$ as the secret-key and use it
to create the uniform mixture
$\frac{1}{2^{n}}\sum_{\in\\{0,1\\}^{n}}|x\rangle\langle
x|\otimes|Enc_{sk}(x)\rangle\langle Enc_{sk}(x)|$ as public-key. The
ciphertext of a message $m$ is $(\enc_{x}(m),\enc_{sk}(x))$. To decrypt, the
decryptor would first recover $x$ by decrypting the second element in the
ciphertext using $sk$, and then recover $m$ by decrypting the first item using
$x$ as the secret key. Therefore, we have that the meaningful notion of PKE
with quantum public-keys should consider only pure states as quantum public-
keys.

####  1.1.2 Constructions for qPKE

As previously mentioned, we propose in this work three schemes for qPKE, based
on different assumptions.

##### QPKE from OWFs.

Our first scheme is based on the existence of post-quantum pseudo-random
functions (PRF) and post-quantum IND-CPA secure symmetric-key encryption
schemes, and both of these primitives can be constructed from post-quantum
OWFs. More concretely, let $\\{f_{k}\\}_{k}$ be a keyed PRF family and
$(\mathsf{SE}.\enc,\mathsf{SE}.\dec)$ be a symmetric-key encryption scheme.
The secret key $\mathsf{dk}$ of our scheme is a uniformly random key for the
PRF, and for a fixed $\mathsf{dk}$, the quantum public-key state is

$\displaystyle|\mathpzc{qpk}_{\mathsf{dk}}\rangle=\frac{1}{\sqrt{2^{\secpar}}}\sum_{x\in\\{0,1\\}^{\secpar}}|x\rangle|f_{\mathsf{dk}}(x)\rangle$

For clarity, we will drop the index of $|\mathpzc{qpk}\rangle$ when
$\mathsf{dk}$ is clear from the context.

The encryption algorithm will then measure $|\mathpzc{qpk}\rangle$ in the
computation basis leading to the outcome $(x^{*},f_{\mathsf{dk}}(x^{*}))$. The
ciphertext of a message $m$ is $(x^{*},\mathsf{SE}.\enc_{f(x^{*})}(m))$ and
the decryption algorithm receives as input a ciphertext $(\hat{x},\hat{c})$
and outputs $\mathsf{SE}.\dec_{f(\hat{x})}(\hat{c})$.

Using a hybrid argument, we prove that any adversary that breaks the security
of this qPKE scheme can be used to break the security of the PRF family or the
security of the symmetric-key encryption scheme. The formal construction and
its proof of security is given in Section 4.1.

We notice that such a scheme allows the encryption/decryption of many messages
using the same measurement outcome $(x^{*},f_{\mathsf{dk}}(x^{*}))$.

##### QPKE from PRFSPDs.

Our second scheme is based on pseudo-random function-like states with proof of
destruction (PRFSPDs), which was recently defined in [BBSS23]. A family of
states $\\{|\psi_{k,x}\rangle\\}_{k,x}$ is pseudo-random function-like [AQY21]
if

  1. 1.

there is a quantum polynomial-time algorithm $\mathsf{Gen}$ such that

$\mathsf{Gen}(k,\sum_{x}\alpha_{x}|x\rangle)=\sum_{x}\alpha_{x}|x\rangle|\psi_{k,x}\rangle\text{,
and}$

  2. 2.

no QPT adversary can distinguish $(|\psi_{1}\rangle,...,|\psi_{\ell}\rangle)$
from $(|\phi_{1}\rangle,...,|\phi_{\ell}\rangle)$, where
$|\psi_{i}\rangle=\sum_{x}\alpha^{i}_{x}|x\rangle|\psi_{k,x}\rangle$,
$|\phi_{i}\rangle=\sum_{x}\alpha^{i}_{x}|x\rangle|\phi_{x}\rangle$ and
$\\{|\phi_{x}\rangle\\}_{x}$ are Haar random states and the states
$|\sigma_{i}\rangle=\sum_{x}\alpha^{i}_{x}|x\rangle$ are chosen by the
adversary.

Recently, [BBSS23] extended this notion to pseudo-random function-like states
with proof of destruction, where we have two algorithms $\mathpzc{Del}$ and
$\mathpzc{Ver}$, which allows us to verify if a copy of the PRFS was deleted.

We will discuss now how to provide the one-shot security222Meaning that one
can only encrypt once using $|\mathpzc{qpk}\rangle$. of the encryption of a
one-bit message and we discuss later how to use it to achieve general
security.

The quantum public-key in this simplified case is

$\displaystyle\frac{1}{\sqrt{2^{\secpar}}}\sum_{x\in\\{0,1\\}^{\secpar}}|x\rangle|\psi_{\mathsf{dk},x}\rangle.$
(1)

The encryptor will then measure the first register of $|\mathpzc{qpk}\rangle$
and the post-measurement state is
$|x^{*}\rangle|\psi_{\mathsf{dk},x^{*}}\rangle$. The encryptor will then
generate a proof of deletion
$\pi=\mathpzc{Del}(|\psi_{\mathsf{dk},x^{*}}\rangle)$. The encryption chooses
$r\in\\{0,1\\}^{\lambda}$ uniformly at random and compute the ciphertext
$c=(x^{*},y)$ where $y=\begin{cases}r,&\text{if }b=0\\\ \pi,&\text{if
}b=1\end{cases}$.

The decryptor will receive some value $(\hat{x},\hat{y})$ and decrypt the
message $\hat{b}=\mathpzc{Ver}(\mathsf{dk},\hat{x},\hat{y})$.

The proof of the security of such a scheme closely follows the proof of our
first scheme.

Notice that repeating such a process in parallel trivially gives a one-shot
security of the encryption of a string $m$ and moreover, such an encryption is
classical. Therefore, in order to achieve IND-CPA-EO secure qPKE scheme, we
can actually encrypt a secret key $\sk$ that is chosen by the encryptor, and
send the message encrypted under $\sk$. We leave the details of such a
construction and its proof of security to Section 4.2.

##### QPKE from PRFSs.

Finally, our third scheme uses the public-key

$\displaystyle\frac{1}{\sqrt{2^{\secpar}}}\sum_{x\in\\{0,1\\}^{\secpar}}|x\rangle|\psi_{\mathsf{dk},x}\rangle,$
(2)

where $\\{|\psi_{k,x}\rangle\\}_{k,x}$ is a PRFS family and the size of the
input $x$ is super-logarithmic on the security parameter.

The encryptor will then measure the first register of $|\mathpzc{qpk}\rangle$
and the post-measurement state is
$|x^{*}\rangle|\psi_{\mathsf{dk},x^{*}}\rangle$. The encryptor will then
compute the ciphertext $c=(x^{*},\rho)$ where

$\displaystyle\rho=\begin{cases}I/2^{n},&\text{if }b=0\\\
|\psi_{\mathsf{dk},x^{*}}\rangle\langle\psi_{\mathsf{dk},x^{*}}|,&\text{if
}b=1\end{cases}.$ (3)

The decryptor, on ciphertext $c=(\hat{x},\hat{\rho})$, sets
$\hat{b}\leftarrow\mathsf{Test}(\mathsf{dk},\hat{x},\hat{\rho})$, where
$\mathsf{Test}$ is a tester algorithm checking whether $\hat{\rho}$ is the
output of the PRFS generator with key $\mathsf{dk}$ and input $\hat{x}$, that
is whether
$\hat{\rho}=|\psi_{\mathsf{dk},\hat{x}}\rangle\langle\psi_{\mathsf{dk},\hat{x}}|$.

The proof of the security of such a scheme also closely follows the one of our
first scheme, and we give the formal construction in Section 4.3.

###  1.2 Related works

Gottesman [Got05] has a candidate construction (without formal security
analysis) encryption scheme with quantum public keys and quantum ciphers,
which consumes the public key for encryption. Ref. [OTU00] defines and
constructs a public-key encryption where the keys, plaintexts and ciphers are
classical, but the algorithms are quantum. (In their construction, only the
key-generation uses Shor’s algorithm.)

In [NI09], the authors define and provide impossibility results regarding
encryption with quantum public keys. Classically, it is easy to show that a
(public) encryption scheme cannot have deterministic ciphers; in other words,
encryption must use randomness. They show that this is also true for a quantum
encryption scheme with quantum public keys.

In Ref. [MY22a, MY22b], the authors study digital signatures with quantum
signatures, and more importantly in the context of this work, quantum public
keys.

###  1.3 Concurrent and independent work

Very recently, two concurrent and independent works have achieved similar
tasks. Coladangelo [Col23] shows a qPKE scheme whose construction is very
different from ours, and uses a quantum trapdoor function, which is a new
notion first introduced in their work. The hardness assumption is the
existence of post-quantum OWF. Each quantum public key can be used to encrypt
a single message (compared to our construction from OWF, where the public key
can be used to encrypt multiple messages). The ciphertexts are quantum
(whereas our construction from OWF has classical ciphertexts). Barooti,
Malavolta and Walter [BMW23] also construct a qPKE scheme based on OWF. Their
construction has quantum public keys and classical ciphertexts, and is very
similar to the construction we propose in Section 4.1. They do not discuss the
notion of IND-CPA-EO security, but we believe that the hybrid encryption
approach we use to achieve IND-CPA-EO can be used in their construction as
well. Moreover, their construction also achieves CCA security, which is
stronger than CPA security. They leave open the question of constructing qPKE
from weaker assumptions than OWF, which we answer affirmatively in our work.

##  2 Definitions and Preliminaries

###  2.1 Notation

Throughout this paper, $\secpar$ denotes the security parameter. The notation
$\negl$ denotes any function $f$ such that $f(\lambda)=\lambda^{-\omega(1)}$,
and $\poly$ denotes any function $f$ such that
$f(\lambda)=\mathcal{O}(\lambda^{c})$ for some $c>0$. When sampling uniformly
at random a value $a$ from a set $\mathcal{U}$, we employ the notation
$a\sample\mathcal{U}$. When sampling a value $a$ from a probabilistic
algorithm $\adv$, we employ the notation $a\leftarrow\adv$. Let
$\left|\cdot\right|$ denote either the length of a string, or the cardinal of
a finite set, or the absolute value. By $\ppt$ we mean a polynomial-time non-
uniform family of probabilistic circuits, and by QPT we mean a polynomial-time
family of quantum circuits.

###  2.2 Pseudorandom Function-Like State (PRFS) Generators

The notion of pseudorandom states were first introduced by Ananth, Qian and
Yuen in [AQY21]. A stronger definition where the adversary is allowed to make
superposition queries to the challenge oracles was introduced in the follow-up
work [AGQY23]. We reproduce their definition here:

######  Definition 1 (Quantum-accessible PRFS generator).

We say that a QPT algorithm $G$ is a quantum-accessible secure pseudorandom
function-like state generator if for all QPT (non-uniform) distinguishers $A$
if there exists a negligible function $\epsilon$, such that for all $\lambda$,
the following holds:

$\left|\Pr_{k\leftarrow\\{0,1\\}^{\secparam}}\left[A_{\lambda}^{|{\cal O}_{\sf
PRFS}(k,\cdot)\rangle}(\rho_{\lambda})=1\right]-\Pr_{{\cal O}_{\sf
Haar}}\left[A_{\lambda}^{|{\cal O}_{\sf
Haar}(\cdot)\rangle}(\rho_{\lambda})=1\right]\right|\leq\epsilon(\lambda),$

where:

  * •

${\cal O}_{\sf PRFS}(k,\cdot)$, on input a $d$-qubit register ${\bf X}$, does
the following: it applies an isometry channel that controlled on the register
${\bf X}$ containing $x$, it creates and stores $G_{\secparam}(k,x)$ in a new
register ${\bf Y}$. It outputs the state on the registers ${\bf X}$ and ${\bf
Y}$.

  * •

${\cal O}_{\sf Haar}(\cdot)$, modeled as a channel, on input a $d$-qubit
register ${\bf X}$, does the following: it applies a channel that controlled
on the register ${\bf X}$ containing $x$, stores
$|\vartheta_{x}\rangle\langle\vartheta_{x}|$ in a new register ${\bf Y}$,
where $|\vartheta_{x}\rangle$ is sampled from the Haar distribution. It
outputs the state on the registers ${\bf X}$ and ${\bf Y}$.

Moreover, $A_{\secparam}$ has superposition access to ${\cal O}_{\sf
PRFS}(k,\cdot)$ and ${\cal O}_{\sf Haar}(\cdot)$ (denoted using the ket
notation).

We say that $G$ is a $(d(\lambda),n(\lambda))$-QAPRFS generator to succinctly
indicate that its input length is $d(\lambda)$ and its output length is
$n(\lambda)$.

Given a state $\rho$, it is useful to know whether it is the output of a PRFS
generator with key $k$ and input $x$. The following lemma shows the existence
of a tester algorithm to test any PRFS states in a semi-black-box way.

######  Lemma 1.

[AQY21, Lemma 3.10] Let $G$ be a $(d,n)$-PRFS generator. There exists a QPT
algorithm $\mathsf{Test}(k,x,\cdot)$, called the tester algorithm for
$G(k,x)$, such that here exists a negligible function $\nu(\cdot)$ such that
for all $\lambda$, for all $x\neq y$,

$\Pr_{k}[\mathsf{Test}(k,x,G(k,x))=1]\geq 1-\nu(\lambda),$

and

$\Pr_{k}[\mathsf{Test}(k,x,G(k,y))=1]\leq 2^{-n(\lambda)}+\nu(\lambda).$

###  2.3 Quantum Pseudorandomness with Proofs of Destruction

The rest of this section is taken verbatim from [BBSS23].

Game 1 $\mathsf{Clonning}\text{-}\mathsf{Exp}^{\adv,\textsf{PRSPD}}_{\secpar}$

1:Given input $1^{\secpar}$, Challenger samples
$k\leftarrow\\{0,1\\}^{w(\secpar)}$ uniformly at random.

2:$\adv$ sends $m$ to the challenger.

3:Challenger runs $\mathsf{Gen}(k)^{\otimes m}$ and sends
$|\psi_{k}\rangle^{\otimes m}$ to $\adv$.

4:$\adv$ gets classical oracle access to $\mathpzc{Ver}(k,\cdot)$.

5:$\adv$ outputs $c_{1},c_{2},\ldots,c_{m+1}$ to the challenger.

6:Challenger rejects if $c_{i}$’s are not distinct.

7:for $i\in[m+1]$ do Challenger runs $b_{i}\leftarrow\mathpzc{Ver}(k,c_{i})$

8:end for

9:Return $\wedge_{i=1}^{m+1}b_{i}$.

######  Definition 2 (Pseudorandom function-like state generator with proofs
of destruction).

A PRFSPD scheme with key-length $w(\secpar)$, input-length $d(\secpar)$,
output length $n(\secpar)$ and proof length $c(\secpar)$ is a tuple of QPT
algorithms $\mathsf{Gen},\mathpzc{Del},\mathpzc{Ver}$ with the following
syntax:

  1. 1.

$|\psi^{x}_{k}\rangle\leftarrow\mathsf{Gen}(k,x)$: takes a key
$k\in\\{0,1\\}^{w}$, an input string $x\in\\{0,1\\}^{d(\secpar)}$, and outputs
an $n$-qubit pure state $|\psi^{x}_{k}\rangle$.

  2. 2.

$p\leftarrow\mathpzc{Del}(|\phi\rangle)$: takes an $n$-qubit quantum state
$|\phi\rangle$ as input, and outputs a $c$-bit classical string, $p$.

  3. 3.

$b\leftarrow\mathpzc{Ver}(k,x,q)$: takes a key $k\in\\{0,1\\}^{w}$, a $d$-bit
input string $x$, a $c$-bit classical string $p$ and outputs a boolean output
$b$.

##### Correctness.

A PRFSPD scheme is said to be correct if for every $x\in\\{0,1\\}^{d}$,

$\Pr_{k\xleftarrow{u}\\{0,1\\}^{w}}[1\leftarrow\mathpzc{Ver}(k,x,p)\mid
p\leftarrow\mathpzc{Del}(|\psi^{x}_{k}\rangle);|\psi^{x}_{k}\rangle\leftarrow\mathsf{Gen}(k,x)]=1$

##### Security.

  1. 1.

Pseudorandomness: A PRFSPD scheme is said to be (adaptively) pseudorandom if
for any QPT adversary $\adv$, and any polynomial $m(\secpar)$, there exists a
negligible function $\negl$, such that

$\left|\Pr_{k\leftarrow\\{0,1\\}^{w}}[\adv^{\mathsf{Gen}(k,\cdot)}(1^{\secpar})=1]-\Pr_{\forall
x\in\\{0,1\\}^{d},|\phi^{x}\rangle\leftarrow\mu_{(\CC^{2})^{\otimes
n}}}[\adv^{\mathpzc{Haar}^{\\{|\phi^{x}\rangle\\}_{x\in\\{0,1\\}^{d}}}(\cdot)}(1^{\secpar})=1]\right|=\negl,$

where $\forall x\in\\{0,1\\}^{d}$,
$\mathpzc{Haar}^{\\{|\phi^{x}\rangle\\}_{x\in\\{0,1\\}^{d}}}(x)$ outputs
$|\phi^{x}\rangle$. Here $\adv^{\mathsf{Gen}(k,\cdot)}$ represents that $\adv$
gets classical oracle access to $\mathsf{Gen}(k,\cdot)$.

  2. 2.

$\mathsf{Unclonability\text{-}of\text{-}proofs}$: A PRFSPD scheme satisfies
$\mathsf{Unclonability\text{-}of\text{-}proofs}$ if for any QPT adversary
$\adv$ in cloning game (see Game 2), there exists a negligible function
$\negl$ such that

$\Pr[\mathsf{Clonning}\text{-}\mathsf{Exp}^{\adv,\textsf{PRFSPD}}_{\secpar}=1]=\negl.$

Game 2
$\mathsf{Clonning}\text{-}\mathsf{Exp}^{\adv,\textsf{PRFSPD}}_{\secpar}$

1:Given input $1^{\secpar}$, Challenger samples
$k\leftarrow\\{0,1\\}^{w(\secpar)}$ uniformly at random.

2:Initialize an empty set of variables, $S$.

3:$\adv$ gets oracle access to $\mathsf{Gen}(k,\cdot)$,
$\mathpzc{Ver}(k,\cdot,\cdot)$ as oracle.

4:for $\mathsf{Gen}$ query $x$ made by $\adv$ do

5: if $\exists$ variable $t_{x}\in S$ then $t_{x}=t_{x}+1$.

6: else Create a variable $t_{x}$ in $S$, initialized to $1$.

7: end if

8:end for

9:$\adv$ outputs $x,c_{1},c_{2},\ldots,c_{t_{x}+1}$ to the challenger.

10:Challenger rejects if $c_{i}$’s are not distinct.

11:for $i\in[m+1]$ do $b_{i}\leftarrow\mathpzc{Ver}(k,x,c_{i})$

12:end for

13:Return $\wedge_{i=1}^{m+1}b_{i}$.

##  3 Security definitions for qPKE

In this section, we introduce the new notion of encryption with quantum public
keys (Definition 3) and present our indistinguishability under chosen-
plaintext attacks security for quantum public-key encryption.

######  Definition 3 (Encryption with quantum public keys).

Encryption with quantum public keys (qPKE) consists of 4 algorithms with the
following syntax:

  1. 1.

$\mathsf{dk}\leftarrow\mathsf{Gen}(\secparam)$: a $\ppt$ algorithm, which
receives the security parameter and outputs a classical decryption key.

  2. 2.

$|\mathpzc{qpk}\rangle\leftarrow\mathpzc{QPKGen}(\mathsf{dk})$: a QPT
algorithm, which receives a classical decryption key $\mathsf{dk}$, and
outputs a quantum public key $|\mathpzc{qpk}\rangle$. We require that the
output is a pure state, and that $t$ calls to $\mathpzc{QPKGen}(\mathsf{dk})$
should yield the same state, that is, $|\mathpzc{qpk}\rangle^{\otimes t}$.

  3. 3.

$(\mathpzc{qpk}^{\prime},\mathpzc{qc})\leftarrow\mathpzc{Enc}(\mathpzc{qpk},m)$:
a QPT algorithm, which receives a quantum public key $\mathpzc{qpk}$ and a
plaintext $m$, and outputs a (possibly classical) ciphertext $\mathpzc{qc}$
and a recycled public-key $\mathpzc{qpk}^{\prime}$.

  4. 4.

$m\leftarrow\mathpzc{Dec}(\mathsf{dk},\mathpzc{qc})$: a QPT algorithm, which
uses a decryption key $\mathsf{dk}$ and a ciphertext $\mathpzc{qc}$, and
outputs a classical plaintext $m$. In the case $\mathpzc{qc}$ is classical, we
consider $\mathpzc{Dec}$ as a $\ppt$ algorithm.

We say that a qPKE scheme is complete if for every message $m\in\\{0,1\\}^{*}$
and any security parameter $\secpar\in\NN$, the following holds:

$\Pr\left[\mathpzc{Dec}(\mathsf{dk},\mathpzc{qc})=m\
\middle|\begin{array}[]{r}\mathsf{dk}\leftarrow\mathsf{Gen}(\secparam)\\\
|\mathpzc{qpk}\rangle\leftarrow\mathpzc{QPKGen}(\mathsf{dk})\\\
(\mathpzc{qpk}^{\prime},\mathpzc{qc})\leftarrow\mathpzc{Enc}(|\mathpzc{qpk}\rangle,m)\end{array}\right]\geq
1-\negl,$

where the probability is taken over the randomness of $\mathsf{Gen}$,
$\mathpzc{QPKGen}$ and $\mathpzc{Enc}$.

Next, we present a quantum analogue of classical indistinguishability under
chosen-plaintext attacks security (denoted as IND-CPA) for qPKE.

######  Definition 4.

A qPKE scheme is IND-CPA secure if for every QPT adversary, there exists a
negligible function $\epsilon$ such that the probability of winning the IND-
CPA security game (see Game 3) is at most $\frac{1}{2}+\epsilon(\secpar)$.

Game 3 IND-CPA security game for encryption with quantum public key schemes.

1:The challenger generates $\mathsf{dk}\leftarrow\mathsf{Gen}(\secparam)$.

2:The adversary gets $\secparam$ as an input, and oracle access to
$\mathpzc{QPKGen}(\mathsf{dk})$, and sends $m_{0},m_{1}$ of the same length to
the challenger.

3:The challenger samples $b\in_{R}\\{0,1\\}$, generates
$|\mathpzc{qpk}\rangle\leftarrow\mathpzc{QPKGen}(\mathsf{dk})$ and sends
$c\leftarrow\mathpzc{Enc}(|\mathpzc{qpk}\rangle,m_{b})$ to the adversary.

4:The adversary outputs a bit $b^{\prime}$.

We say that the adversary wins the game (or alternatively, that the outcome of
the game is 1) iff $b=b^{\prime}$.

Note that this is the standard CPA-security game of a public-key encryption
scheme, with the exception that the adversary can receive polynomially many
copies of $|\mathpzc{qpk}\rangle$, by making several calls to the
$\mathpzc{QPKGen}(\mathsf{dk})$ oracle.

In the classical setting, there is no need to provide access to an encryption
oracle since the adversary can use the public key to apply the encryption
herself. In the quantum setting, this is not the case: as we will see, the
quantum public key might be measured, and the ciphertexts might depend on the
measurement outcome. This motivates a stronger definition in which the
adversary gets oracle access to the encryption, denoted as IND-CPA-EO
security.

######  Definition 5.

A qPKE scheme is (single-challenge) IND-CPA-EO secure if for every QPT
adversary, there exists a negligible function $\epsilon$ such that the
probability of winning the IND-CPA-EO security game (see Game 4) is at most
$\frac{1}{2}+\epsilon(\secpar)$.

Game 4 (Single-challenge) Chosen plaintext attack with an encryption oracle
(IND-CPA-EO) security game for encryption with quantum public key schemes.

1:The challenger generates $\mathsf{dk}\leftarrow\mathsf{Gen}(\secparam)$.

2:The adversary gets $\secparam$ as an input, and oracle access to
$\mathpzc{QPKGen}(\mathsf{dk})$.

3:The challenger generates
$|\mathpzc{qpk}\rangle\leftarrow\mathpzc{QPKGen}(\mathsf{dk})$. Let
$\mathpzc{qpk}_{1}\coloneqq|\mathpzc{qpk}\rangle$.

4:For $i=1,\ldots,\ell$, the adversary creates a classical message $m_{i}$ and
send it to the challenger.

5:The challenger computes
$(\mathpzc{qc}_{i},\mathpzc{qpk}_{i+1})\leftarrow\mathpzc{Enc}(\mathpzc{qpk}_{i},m_{i})$
and send $\mathpzc{qc}_{i}$ to the adversary.

6:The adversary sends two messages $m^{\prime}_{0},m^{\prime}_{1}$ of the same
length to the challenger.

7:The challenger samples $b\in_{R}\\{0,1\\}$, computes
$(\mathpzc{qc}^{*},\mathpzc{qpk}_{l+2})\leftarrow\mathpzc{Enc}(\mathpzc{qpk}_{\ell+1},m^{\prime}_{b})$
and sends $\mathpzc{qc}^{*}$ to the adversary.

8:For $i=\ell+2,\ldots,\ell^{\prime}$, the adversary creates a classical
message $m_{i}$ and send it to the challenger.

9:The challenger computes
$(\mathpzc{qc}_{i},\mathpzc{qpk}_{i+1})\leftarrow\mathpzc{Enc}(\mathpzc{qpk}_{i},m_{i})$
and send $\mathpzc{qc}_{i}$ to the adversary.

10:The adversary outputs a bit $b^{\prime}$.

We say that the adversary wins the game (or alternatively, that the outcome of
the game is 1) iff $b=b^{\prime}$.

######  Definition 6.

A qPKE scheme is (multi-challenge) IND-CPA-EO secure if for every QPT
adversary, there exists a negligible function $\epsilon$ such that the
probability of winning the IND-CPA-EO security game (see Game 5) is at most
$\frac{1}{2}+\epsilon(\secpar)$.

Game 5 (Multi-challenge) Chosen plaintext attack with an encryption oracle
(IND-CPA-EO) security game for encryption with quantum public key schemes.

1:The challenger generates $\mathsf{dk}\leftarrow\mathsf{Gen}(\secparam)$.

2:The adversary gets $\secparam$ as an input, and oracle access to
$\mathpzc{QPKGen}(\mathsf{dk})$.

3:The challenger generates
$|\mathpzc{qpk}\rangle\leftarrow\mathpzc{QPKGen}(\mathsf{dk})$. Let
$\mathpzc{qpk}_{1}\coloneqq|\mathpzc{qpk}\rangle$.

4:For $i=1,\ldots,\ell$, the adversary creates a classical message $m_{i}$ and
send it to the challenger.

5:The challenger computes
$(\mathpzc{qc}_{i},\mathpzc{qpk}_{i+1})\leftarrow\mathpzc{Enc}(\mathpzc{qpk}_{i},m_{i})$
and send $\mathpzc{qc}_{i}$ to the adversary.

6:The adversary sends two messages $m^{\prime}_{0},m^{\prime}_{1}$ of the same
length to the challenger.

7:The challenger samples $b\in_{R}\\{0,1\\}$, computes
$(\mathpzc{qc}^{*},\mathpzc{qpk}_{l+2})\leftarrow\mathpzc{Enc}(\mathpzc{qpk}_{\ell+1},m^{\prime}_{b})$
and sends $\mathpzc{qc}^{*}$ to the adversary.

8:For $i=\ell+2,\ldots,\ell^{\prime}$, the adversary creates a classical
message $m_{i}$ and send it to the challenger.

9:The challenger computes
$(\mathpzc{qc}_{i},\mathpzc{qpk}_{i+1})\leftarrow\mathpzc{Enc}(\mathpzc{qpk}_{i},m_{i})$
and send $\mathpzc{qc}_{i}$ to the adversary.

10:The challenger and the adversary can repeat step 3 - 9 polynomially many
times. For the $i$-th repetition, let $\mathpzc{qpk}_{1,i}$ be
$\mathpzc{qpk}_{l^{\prime}+1,i-1}$.

11:The challenger and the adversary can repeat step 3 - 10 polynomially many
times.

12:The adversary outputs a bit $b^{\prime}$.

We say that the adversary wins the game (or alternatively, that the outcome of
the game is 1) iff $b=b^{\prime}$.

######  Theorem 1.

Single-challenge security (Definition 5) implies multi-challenge security
(Definition 6).

###### Proof.

Recall that classically, single-challenge IND-CPA implies multi-challenge IND-
CPA, see, e.g., [KL14, Theorem 3.24]. Following the exact same argument works
in our case as well: single-challenge IND-CPA-EO implies multi-challenge IND-
CPA-EO. ∎

##  4 Constructions

###  4.1 QPKE with Classical ciphertext from OWFs

We show a construction based on the existence of post-quantum one-way
functions. Recalls that post-quantum one-way functions imply a qPRF [Zha12],
and IND-CPA333In fact, this can be strengthened to IND-qCCA security, but this
is unnecessary for our application. symmetric encryption [BZ13].

Assumes: A PRF family $\\{f_{k}\\}_{k}$, and a symmetric encryption scheme
$\\{\enc,\dec\\}$

$\mathsf{Gen}(\secparam)$

  1. 1.

$\mathsf{dk}\leftarrow_{R}\\{0,1\\}^{\secpar}$.

$\mathpzc{QPKGen}(\mathsf{dk})$

  1. 1.

Output
$|\mathpzc{qpk}\rangle=\frac{1}{\sqrt{2^{\secpar}}}\sum_{x\in\\{0,1\\}^{\secpar}}|x\rangle|f_{\mathsf{dk}}(x)\rangle$.

$\mathpzc{Enc}(|\mathpzc{qpk}\rangle,m)$

  1. 1.

Measure both registers of $|\mathpzc{qpk}\rangle$ in the standard basis.
Denote the result as $x$ and $y$.

  2. 2.

Output $c=(x,\enc(y,m))$.

$\dec_{\mathsf{dk}}(c)$

  1. 1.

Interpret $c$ as $(x,z)$

  2. 2.

Set $y:=f_{\mathsf{dk}}(x)$.

  3. 3.

Output $m=\dec(y,z)$.

Figure 1: An encryption scheme with quantum public keys.

######  Theorem 2.

Assuming the existence of quantum-secure PRF family $\\{f_{k}\\}_{k}$ and
post-quantum IND-CPA symmetric-key encryption scheme $(\enc,\dec)$, any QPT
adversary $\adv$ wins the IND-CPA-EO game for the scheme presented in Figure
4.1 with advantage at most $\negl$.

###### Proof.

In order to prove our results, we define the following Hybrids.

Hybrid $H_{0}$. The original security game as defined in Algorithm 4.

Hybrid $H_{1}$. Same as Hybrid $H_{0}$, except that the challenger, instead of
measuring $|\mathpzc{qpk}\rangle$ when the adversary queries the encryption
oracle for the first time, the challenger measures this state before providing
the copies of $|\mathpzc{qpk}\rangle$ to the adversary. Note that by measuring
$|\mathpzc{qpk}\rangle$ in the computational basis, the challenger would
obtain a uniformly random string $x^{*}$ (and the corresponding
$f_{\mathsf{dk}}(x^{*})$).

Hybrid $H_{2}$. Same as Hybrid $H_{1}$, except that the challenger samples
$x^{*}$ as in the previous hybrid, and instead of providing
$|\mathpzc{qpk}\rangle$ to the adversary, she provides

$|\mathpzc{qpk}^{\prime}\rangle=\frac{1}{\sqrt{2^{\lambda}-1}}\sum_{x\in\\{0,1\\}^{*},x\neq
x^{*}}|x\rangle|f_{\mathsf{dk}}(x)\rangle.$

Moreover, the challenger provides ciphertexts
$(x^{*},\enc(f_{\mathsf{dk}}(x^{*}),m))$ for the chosen messages $m$. We note
that this state $|\mathpzc{qpk}^{\prime}\rangle$ can be efficiently prepared
by computing the functions $\delta_{x,x^{*}}$ over the state
$\sum_{x}|x\rangle$ in superposition and measuring the output register. With
overwhelming probability, the post-measurement state is $\sum_{x\neq
x^{*}}|x\rangle$.

Hybrid $H_{3}$. Same as Hybrid $H_{2}$, except the challenger uses a random
function $H$ in place of $f_{\mathsf{dk}}$, and provides
$|\mathpzc{qpk}^{\prime}\rangle=\frac{1}{\sqrt{2^{\lambda}-1}}\sum_{x\in\\{0,1\\}^{*},x\neq
x^{*}}|x\rangle|H(x)\rangle$. Moreover, for each encryption query, the
challenger uses $H(x^{*})$ as $\mathpzc{qpk}_{i}$, and answers the query with
$(x^{*},\enc(H(x^{*}),m))$ for the chosen message $m$.

Hybrid $H_{4}$. Same as Hybrid $H_{3}$, except the challenger samples
uniformly at random a string $z$, and uses $z$ as $\mathpzc{qpk}_{i}$. The
answer to each encryption query is now $(x^{*},\enc(z,m))$ for the chosen
message $m$.

We will now show that, given our assumptions, Hybrids $H_{i}$ and $H_{i+1}$
are indistinguishable except with probability at most $\negl$ and that every
polynomial-time adversary wins $H_{4}$ with advantage at most $\negl$. We can
then use triangle inequality to prove the security of Theorem 2.

######  Lemma 2.

No adversary can distinguish Hybrid $H_{0}$ and Hybrid $H_{1}$ with non-zero
advantage.

###### Proof.

Notice that the operations corresponding to the challenger’s measurement of
$|\mathpzc{qpk}\rangle$ and the creation of the copies of
$|\mathpzc{qpk}\rangle$ given to the adversary commute. In this case, we can
swap the order of these operations and the outcome is exactly the same. ∎

######  Lemma 3.

No adversary can distinguish Hybrid $H_{1}$ and Hybrid $H_{2}$ with non-
negligible advantage.

###### Proof.

Notice that distinguishing the two adversaries imply that we can distinguish
the following quantum states $|\mathpzc{qpk}\rangle^{\otimes
p}\otimes|x^{*}\rangle$ and $|\mathpzc{qpk}^{\prime}\rangle^{\otimes
p}\otimes|x^{*}\rangle$, but these two quantum states have $1-\negl$ trace-
distance for any polynomial $p$. Therefore, this task can be performed with
success at most $\negl$. ∎

######  Lemma 4.

No QPT adversary can distinguish Hybrid $H_{2}$ and Hybrid $H_{3}$ with non-
negligible advantage.

###### Proof.

Suppose that there exists an adversary $\adv$ such that
$\Pr[F_{1}]-\Pr[F_{2}]\geq\frac{1}{p(\lambda)}$ for some polynomial $p$, where
$F_{1}$ is the event where $\adv$ outputs $1$ on $H_{2}$ and $F_{2}$ is the
event where $\adv$ outputs $1$ on $H_{3}$. Then, we show that we can construct
an adversary $\adv^{\prime}$ that can distinguish the PRF family from random.

$\adv^{\prime}$ will behave as the challenger in the CPA-EO game and instead
of computing $f_{\mathsf{dk}}$ to create $|\mathpzc{qpk}^{\prime}\rangle$ and
answer the encryption queries, she queries the oracle $O$ (that is either a
PRF or a random function). $\adv^{\prime}$ then outputs $1$ iff $\adv$ outputs
$1$.

Notice that if $O$ is a PRF, then the experiment is the same as Hybrid
$H_{2}$. On the other hand, if $O$ is a random oracle, the experiment is the
same as Hybrid $H_{3}$.

In this case, we have that

$\displaystyle\Pr_{O\sim\mathcal{F}}[\adv^{\prime
O}()=1]-\Pr_{\mathsf{dk}}[\adv^{\prime f_{\mathsf{dk}}}()=1]$ (7)
$\displaystyle=\Pr[F_{1}]-\Pr[F_{2}]$ (8)
$\displaystyle\geq\frac{1}{p(\lambda)}.$ (9)

∎

######  Lemma 5.

No adversary can distinguish Hybrid $H_{3}$ and Hybrid $H_{4}$ with non-zero
advantage.

###### Proof.

Since the adversary never gets the evaluation of $H(x^{*})$ (as $x^{*}$ was
punctured from all $|\mathpzc{qpk}\rangle$), the distributions of the two
hybrid are identical. ∎

######  Lemma 6.

Any polynomially-bounded adversary wins the game in Hybrid $H_{4}$ with an
advantage at most $\negl$.

###### Proof.

Suppose that there exists an adversary $\adv$ such that wins the game in
Hybrid $H_{4}$ with advantage $\frac{1}{p(\lambda)}$ for some polynomial $p$.
Then, we show that we can construct an adversary $\adv^{\prime}$ that can
break IND-CPA security of the symmetric-key encryption scheme with the same
probability.

$\adv^{\prime}$ will simulate $\adv$ and for that, she picks $x^{*}$ and $z$,
creates
$|\mathpzc{qpk}^{\prime}\rangle=\frac{1}{\sqrt{2^{\lambda}-1}}\sum_{x\in\\{0,1\\}^{*},x\neq
x^{*}}|x\rangle|H(x)\rangle$ using the compressed oracle technique [Zha19] and
uses oracle provided by the IND-CPA game of the symmetric-key encryption
scheme for answering the encryption oracles. $\adv^{\prime}$ will output $1$
iff $\adv$ outputs $1$. We note that the encryption key $z$ is sampled
uniformly at random independently of all other variables. We have that the
winning probability of $\adv^{\prime}$ in the IND-CPA game is the same of
$\adv$ in the IND-CPA-EO game. ∎

∎

###  4.2 QPKE with Classical Ciphertexts from PRFSPDs

In this section, we propose a construction for qPKE from pseudo-random
function-like states with proof of destruction.

Assumes: A PRFSPD family $\\{|\psi_{\mathsf{dk},x}\rangle\\}_{\mathsf{dk},x}$
and a quantum symmetric encryption scheme with classical ciphers
$\\{\enc,\dec\\}$

$\mathsf{Gen}(\secparam)$

  1. 1.

$\mathsf{dk}\leftarrow_{R}\\{0,1\\}^{\secpar}$.

$\mathpzc{QPKGen}(\mathsf{dk})$

  1. 1.

Output
$|\mathpzc{qpk}\rangle=\bigotimes_{i\in[\lambda]}\frac{1}{\sqrt{2^{\secpar}}}\sum_{x^{(i)}\in\\{0,1\\}^{\secpar}}|x^{(i)}\rangle|\psi_{\mathsf{dk},x^{(i)}}\rangle$.

$\mathpzc{Enc}(|\mathpzc{qpk}\rangle,m)$ for $m\in\\{0,1\\}$

  1. 1.

Let
$|\mathpzc{qpk}_{i}\rangle\coloneqq\frac{1}{\sqrt{2^{\secpar}}}\sum_{x^{(i)}\in\\{0,1\\}^{\secpar}}|x^{(i)}\rangle|\psi_{\mathsf{dk},x^{(i)}}\rangle$,
and write $|\mathpzc{qpk}\rangle$ as
$|\mathpzc{qpk}\rangle=\bigotimes_{i\in[\lambda]}|\mathpzc{qpk}_{i}\rangle$.

  2. 2.

Measure the left registers of $|\mathpzc{qpk}_{i}\rangle$ to obtain classical
strings $x^{(i)}$. Denote the post-measurement states as
$|\psi^{\prime}_{i}\rangle$.

  3. 3.

Set $y^{(i)}\leftarrow\mathpzc{Del}(|\psi^{\prime}\rangle)$.

  4. 4.

Pick $k=\\{0,1\\}^{\lambda}$ and $r^{(i)}=\\{0,1\\}^{\left|y^{(i)}\right|}$
uniformly at random.

  5. 5.

Set $\tilde{y}^{(i)}=\begin{cases}r^{(i)}&,\text{if }k_{i}=0\\\
y^{(i)}&,\text{if }k_{i}=1\end{cases}$.

  6. 6.

Output $\left(\enc(k,m),\left((x^{(i)},\tilde{y}^{(i)})\right)_{i}\right)$

$\dec_{\mathsf{dk}}(c)$

  1. 1.

Interpret $c$ as
$\left(c^{\prime},\left((x^{(i)},\tilde{y}^{(i)})\right)_{i}\right)$

  2. 2.

Let $k^{\prime}_{i}=\mathpzc{Ver}(x^{(i)},\tilde{y}^{(i)})$.

  3. 3.

Output $\dec(k^{\prime},c^{\prime})$

Figure 2: An encryption scheme with quantum public keys.

In this section, we construct a qPKE scheme based on PRFSPD. For that, we need
the following result that builds _symmetric_ -key encryption from such an
assumption.

######  Proposition 1 ([BBSS23]).

If quantum-secure PRFSPD exists, then there exists a quantum CPA symmetric
encryption with classical ciphertexts.

######  Theorem 3.

If quantum-secure PRFSPD with super-logarithmic input size exists, then there
exists a public-key encryption with classical ciphertexts which is IND-CPA-EO
secure.

###### Proof.

Our construction is given in Section 4.2. It uses a PRFSPD, as well as a
quantum CPA _symmetric_ encryption with classical ciphertexts. Such symmetric
encryption is known to exist, based on PRFSPD:

In order to prove our results, we define the following Hybrids.

Hybrid $H_{0}$. This is the original security game.

Hybrid $H_{1}$. Same as Hybrid $H_{0}$, except that the challenger picks
${x^{(i)}}^{*}$ uniformly at random, instead of providing
$|\mathpzc{qpk}\rangle$ to the adversary, she provides

$|\mathpzc{qpk}^{\prime}\rangle=\bigotimes_{i\in[\lambda]}\frac{1}{\sqrt{2^{\secpar}-1}}\sum_{x^{(i)}\in\\{0,1\\}^{\secpar},x^{(i)}\neq{x^{(i)}}^{*}}|x^{(i)}\rangle|\psi_{\mathsf{dk},x^{(i)}}\rangle.$

The challenger uses the states
$|{x^{(i)}}^{*}\rangle|\psi_{\mathsf{dk},{x^{(i)}}^{*}}\rangle$ to encrypt the
challenge.

Hybrid $H_{2}$. Same as Hybrid $H_{1}$, but to answer the encryption queries,
the challenger picks each $\tilde{y}^{(i)}$ uniformly at random and answers
the encryption queries with
$\left(\enc(k,m),\left((x^{(i)},\tilde{y}^{(i)})\right)_{i}\right)$

We will now show that, given our assumptions, Hybrids $H_{i}$ and $H_{i+1}$
are indistinguishable except with probability at most $\negl$ and that every
polynomial-time adversary wins $H_{3}$ with advantage at most $\negl$. We can
then use triangle inequality to prove the security of Theorem 3.

######  Lemma 7.

No adversary can distinguish Hybrid $H_{0}$ and Hybrid $H_{1}$ with non-zero
advantage.

###### Proof.

The proof follows analogously to Lemmas 2 and 3 and the triangle inequality. ∎

######  Lemma 8.

No adversary can distinguish Hybrid $H_{2}$ and Hybrid $H_{3}$ with non-
negligible advantage.

###### Proof.

Suppose that there exists an adversary $\adv$ such that
$\Pr[F_{1}]-\Pr[F_{2}]\geq\frac{1}{p(\lambda)}$ for some polynomial $p$, where
$F_{1}$ is the event where $\adv$ outputs $1$ on $H_{2}$ and $F_{2}$ is the
event where $\adv$ outputs $1$ on $H_{3}$. Then, we show that we can construct
an adversary $\adv^{\prime}$ that can break the PRFSPD family scheme.

$\adv^{\prime}$ will behave as the challenger in the CPA-EO game and instead
of computing $|\mathpzc{qpk}^{\prime}\rangle$ by herself, she queries the
oracle $O$ (that on input $|x\rangle|0\rangle$ answers either a PRFSPD
$|x\rangle|\psi_{\mathsf{dk},x}\rangle$ or a Haar random state
$|x\rangle|\vartheta_{x}\rangle$). Then, $\adv^{\prime}$ picks a random bit
$b$ and performs as follows:

  * •

if $b=0$, $\adv^{\prime}$ answers the encryption queries as Hybrid $H_{2}$

  * •

if $b=1$, $\adv^{\prime}$ picks each $\tilde{y}^{(i)}$ uniformly at random and
answers the encryption queries with
$\left(Enc_{k}(m),\left((x^{(i)},\tilde{y}^{(i)})\right)_{i}\right)$

$\adv^{\prime}$ then outputs $1$ iff $\adv$ outputs $1$.

Notice that if $b=0$ and $O$ answers a PRFSPD, then the experiment is the same
as Hybrid $H_{2}$. On the other hand, if $b=0$ and $O$ is a random oracle or
if $b=1$, the experiment is the same as Hybrid $H_{3}$. Let us define the
event $E_{1}$ be the event where $\adv^{\prime}$ outputs $1$ if $O$ is a
PRFSPD, and $E_{2}$ be the event where $\adv^{\prime}$ outputs $1$ if $O$
answers with Haar random states.

In this case, we have that $\adv^{\prime}$ distinguishes the PRFS family from
Haar random states with probability

$\displaystyle\Pr[E_{1}]-\Pr[E_{2}]$ (10)
$\displaystyle=\frac{1}{2}\left(\Pr[E_{1}\wedge b=0]+\Pr[E_{1}\wedge
b=1]-\Pr[E_{2}\wedge b=0]-\Pr[E_{2}\wedge b=1]\right)$ (11)
$\displaystyle=\frac{1}{2}\left(\Pr[F_{1}]+\Pr[F_{2}]-\Pr[F_{2}]-\Pr[F_{2}]\right)$
(12) $\displaystyle\geq\frac{1}{2p(\lambda)}.$ (13)

∎

######  Lemma 9.

Any polynomially-bounded adversary wins the game in Hybrid $H_{3}$ with an
advantage at most $\negl$.

###### Proof.

Suppose that there exists an adversary $\adv$ such that wins the game in
Hybrid $H_{3}$ with advantage $\frac{1}{p(\lambda)}$ for some polynomial $p$.
Then, we show that we can construct an adversary $\adv^{\prime}$ that can
break IND-CPA security of the symmetric-key encryption scheme.

$\adv^{\prime}$ will simulate $\adv$ and for that, she picks $\mathsf{dk}$ and
creates $|\mathpzc{qpk}^{\prime}\rangle$ and in order to answer the encryption
queries, they use the encryption oracle provided by the IND-CPA game.
$\adv^{\prime}$ will output $1$ iff $\adv$ outputs $1$. We have that the
winning probability of $\adv^{\prime}$ in its IND-CPA game is the same of
$\adv$ in its IND-CPA-EO game. ∎

∎

###  4.3 QPKE with Quantum Ciphertexts from PRFSs

We finally present our third scheme for qPKE, whose security is based on the
existence of PRFS with super-logarithmic input size.

######  Theorem 4.

The construction in Section 4.3 is IND-CPA secure (see Definition 4), assuming
$\\{|\psi_{k,x}\rangle\\}_{k,x}$ is a PRFS with super-logarithmic input-size.

The proof of this theorem uses the same proof strategy of Theorem 2 and
Theorem 3, the only difference is that here the scheme is only IND-CPA secure,
while the previous ones are IND-CPA-EO secure.

Assumes: A PRFS family $\\{|\psi_{\mathsf{dk},x}\rangle\\}_{\mathsf{dk},x}$
with super-logarithmic input-size

$\mathsf{Gen}(\secparam)$

  1. 1.

$\mathsf{dk}\leftarrow_{R}\\{0,1\\}^{\secpar}$.

$\mathpzc{QPKGen}(\mathsf{dk})$

  1. 1.

Output
$|\mathpzc{qpk}\rangle=\frac{1}{\sqrt{2^{\secpar}}}\sum_{x\in\\{0,1\\}^{\secpar}}|x\rangle|\psi_{\mathsf{dk},x}\rangle$.

$\mathpzc{Enc}(|\mathpzc{qpk}\rangle,m)$ for $m\in\\{0,1\\}$

  1. 1.

Measure left register, denoted by $x$. Let
$|\phi\rangle=|\psi_{\mathsf{dk},x}\rangle$ if $m=0$, and a maximally mixed
state otherwise.

  2. 2.

Output $c=(x,|\phi\rangle)$.

$\dec_{\mathsf{dk}}(c)$

  1. 1.

Interpret $c$ as $(x,|\phi\rangle)$

  2. 2.

Output 0 if $|\phi\rangle=|\psi_{\mathsf{dk},x}\rangle$, otherwise output 1.

Figure 3: An encryption scheme with quantum public keys based on a PRFS.

### Acknowledgments

We wish to thank Prabhanjan Ananth and Umesh Vazirani for related discussions.
ABG and QHV are supported by ANR JCJC TCS-NISQ ANR-22-CE47-0004, and by the
PEPR integrated project EPiQ ANR-22-PETQ-0007 part of Plan France 2030. OS was
supported by the Israeli Science Foundation (ISF) grant No. 682/18 and
2137/19, and by the Cyber Security Research Center at Ben-Gurion University.

OS has received funding from the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No 756482).

## References

  * [ACC+22] P. Austrin, H. Chung, K. Chung, S. Fu, Y. Lin, and M. Mahmoody.  On the Impossibility of Key Agreements from Quantum Random Oracles.  In Y. Dodis and T. Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II, volume 13508 of Lecture Notes in Computer Science, pages 165–194. Springer, 2022, Cryptology ePrint Archive: Report 2022/218.
  * [AGQY23] P. Ananth, A. Gulati, L. Qian, and H. Yuen.  Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications.  In Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I, pages 237–265. Springer, 2023.
  * [AQY21] P. Ananth, L. Qian, and H. Yuen.  Cryptography from Pseudorandom Quantum States, 2021, arXiv: 2112.10020.
  * [BB84] C. H. Bennett and G. Brassard.  An Update on Quantum Cryptography.  In G. R. Blakley and D. Chaum, editors, Advances in Cryptology, Proceedings of CRYPTO ’84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings, volume 196 of Lecture Notes in Computer Science, pages 475–480. Springer, 1984.
  * [BBSS23] A. Behera, Z. Brakerski, O. Sattath, and O. Shmueli.  Quantum pseudorandomness with proof of destruction.  Private communication, 2023.
  * [BCKM21] J. Bartusek, A. Coladangelo, D. Khurana, and F. Ma.  One-Way Functions Imply Secure Computation in a Quantum World.  In T. Malkin and C. Peikert, editors, Advances in Cryptology - CRYPTO 2021, volume 12825, pages 467–496. Springer, 2021, Cryptology ePrint Archive: Report 2020/1487.
  * [BMW23] K. Barooti, G. Malavolta, and M. Walter.  A Simple Construction of Quantum Public-Key Encryption from Quantum-Secure One-Way Functions.  Cryptology ePrint Archive, Paper 2023/306, 2023.  https://eprint.iacr.org/2023/306.
  * [BZ13] D. Boneh and M. Zhandry.  Quantum-Secure Message Authentication Codes.  In T. Johansson and P. Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 592–608. Springer, 2013, Cryptology ePrint Archive: Report 2012/606.
  * [Col23] A. Coladangelo.  Quantum trapdoor functions from classical one-way functions.  Cryptology ePrint Archive, Paper 2023/282, 2023.  https://eprint.iacr.org/2023/282.
  * [GLSV21] A. B. Grilo, H. Lin, F. Song, and V. Vaikuntanathan.  Oblivious Transfer Is in MiniQCrypt.  In EUROCRYPT (2), volume 12697 of Lecture Notes in Computer Science, pages 531–561. Springer, 2021, arXiv: 2011.14980.
  * [Got05] D. Gottesman.  Quantum Public Key Cryptography with Information-Theoretic Security.  https://www2.perimeterinstitute.ca/personal/dgottesman/Public-key.ppt, 2005\.
  * [IR89] R. Impagliazzo and S. Rudich.  Limits on the Provable Consequences of One-Way Permutations.  In D. S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA, pages 44–61. ACM, 1989.
  * [JLS18] Z. Ji, Y. Liu, and F. Song.  Pseudorandom Quantum States.  In H. Shacham and A. Boldyreva, editors, Advances in Cryptology \- CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III, volume 10993 of Lecture Notes in Computer Science, pages 126–152. Springer, 2018, arXiv: 1711.00385.
  * [KL14] J. Katz and Y. Lindell.  Introduction to Modern Cryptography, Second Edition.  CRC Press, 2014.
  * [KQST22] W. Kretschmer, L. Qian, M. Sinha, and A. Tal.  Quantum Cryptography in Algorithmica, 2022, arXiv: 2212.00879.
  * [Kre21] W. Kretschmer.  Quantum Pseudorandomness and Classical Complexity.  In M. Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, July 5-8, 2021, Virtual Conference, volume 197 of LIPIcs, pages 2:1–2:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [MY22a] T. Morimae and T. Yamakawa.  Quantum Commitments and Signatures Without One-Way Functions.  In Y. Dodis and T. Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I, volume 13507 of Lecture Notes in Computer Science, pages 269–295. Springer, August 2022, arXiv: 2112.06369.
  * [MY22b] T. Morimae and Y. Yamakawa.  One-Wayness in Quantum Cryptography, October 2022, arXiv: 2210.03394.
  * [NI09] G. M. Nikolopoulos and L. M. Ioannou.  Deterministic quantum-public-key encryption: Forward search attack and randomization.  Phys. Rev. A, 79:042327, Apr 2009.
  * [OTU00] T. Okamoto, K. Tanaka, and S. Uchiyama.  Quantum Public-Key Cryptosystems.  In M. Bellare, editor, Advances in Cryptology - CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000, Proceedings, volume 1880 of Lecture Notes in Computer Science, pages 147–165. Springer, 2000.
  * [Wie83] S. Wiesner.  Conjugate Coding.  SIGACT News, 15(1):78–88, jan 1983.
  * [Zha12] M. Zhandry.  How to Construct Quantum Random Functions.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 679–687. IEEE Computer Society, 2012.
  * [Zha19] M. Zhandry.  How to record quantum queries, and applications to quantum indifferentiability.  In Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II 39, pages 239–268. Springer, 2019.


figurec

# Generic Approach to Intrinsic Magnetic Second-order Topological Insulators
via Inverted $p-d$ Orbitals

Zhao Liu<EMAIL_ADDRESS>Department of Materials Science and Engineering,
Monash University, Victoria 3800, Australia  ARC Centre of Excellent in Future
Low-Energy Electronics Technologies, Monash University, Victoria 3800,
Australia  Bing Liu  School of Physics and Electronic Information, Weifang
University, Weifang, Shandong 261061, China  Yuefeng Yin  Department of
Materials Science and Engineering, Monash University, Victoria 3800, Australia
ARC Centre of Excellent in Future Low-Energy Electronics Technologies, Monash
University, Victoria 3800, Australia  Nikhil V. Medhekar
<EMAIL_ADDRESS>Department of Materials Science and Engineering,
Monash University, Victoria 3800, Australia  ARC Centre of Excellent in Future
Low-Energy Electronics Technologies, Monash University, Victoria 3800,
Australia

###### Abstract

The integration of intrinsically magnetic and topologically nontrivial two-
dimensional materials holds tantalizing prospects for the exotic quantum
anomalous Hall insulators and magnetic second-order topological insulators
(SOTIs). Compared with the well-studied nonmagnetic counterparts, the pursuit
of intrinsic magnetic SOTIs remains limited. In this work, we address this gap
by focusing on $p-d$ orbitals inversion, a fundamental but often overlooked
phenomena in the construction of topological materials. We begin by developing
a theoretical framework to elucidate $p-d$ orbitals inversion through a
combined density-functional theory calculation and Wannier downfolding.
Subsequently we showcase the generality of this concept in realizing
ferromagnetism SOTIs by identifying two real materials with distinct lattices:
1$T$-VS2 in a hexagonal lattice, and CrAs monolayer in a square lattice. We
further compare it with other mechanisms requiring spin-orbit coupling and
explore the similarities to topological Kondo insulators. Our findings
establish a generic pathway towards intrinsic magnetic SOTIs.

Introduction. In recent years, the concept of $\mathbb{Z}_{2}$ topological
insulators (TIs) Kane2005 ; Bernevig2006  has evolved to encompass higher-
order topology Benalcazar2017a ; Benalcazar2017b ; Langbehn2017 ; Song2017 ;
Schindler2018a ; Miert2018 ; Xie2021 , where an $m$-dimensional $n$-th order
TI is characterized by gapless states in the $(m-n)$-dimensional subspace.
With $n$ = 2, the second order three-dimensional/two-dimensional topological
insulator (3D/2D SOTI for $m$ = 3/2) host gapless 1D hinge/0D corner states,
respectively. For real applications, 1D hinge states provide a good platform
for realizing Luttinger liquid Wang2023  and 0D corner states for Majorana
zero modes Yan2018 ; Yan2019 . The hallmark gapless 1D hinge states have been
experimentally observed between two gapped surfaces in bulk bismuth
Schindler2018b , $T_{d}$-WTe2 Choi2020 ; LeeJ2023  and Bi4Br4 Noguichi2021 .
In the realm of 2D SOTI, pioneering studies have focused on "breathing"
lattices where intercell and intracell hoppings differ Motohiko2018 , such as
the breathing kagome lattice realized in transition metal dichalcogenide
Jung2022 ; Zeng2021 , and the breathing Kekule lattice in both graphyne
Sheng2019 ; Liub2019 ; Lee2020  and covalent organic frameworks Hu2022 ;
Ni2022 . The mechanical twisting of trivial 2D materials offers another
approach to realize SOTI and has been reported in both twisted bilayer
graphene and $h$-BN Liub2021 . Recently, the unique 0D corner state has been
experimentally identified in metal organic framework Ni3(HITP)2 Hu2023 .

Nevertheless, the requirement of time-reversal symmetry for $\mathbb{Z}_{2}$
TIs generally excludes the large family of magnetic materials, especially the
recently discovered 2D ferromagnetic insulators Huang2017 ; Gong2017 ;
Zhang2019 ; Kong2019 ; Deng2020 ; LeeK2021 ; Li2023 ; Liu2023 . Since 2D
topological materials are attractive for device applications, it is crucial to
extend the idea of higher-order topology to 2D magnetic materials.
Accordingly, candidate materials such as monolayer $2H$-MX2 (M = Ru, Os and X=
Br, Cl) LuR2023 ; Cai2023  and CrSiTe3 WangX2023 , have been proposed as
ferromagnetic SOTIs. However, compared to their nonmagnetic counterparts, the
underlying mechanisms for realizing 2D magnetic SOTIs remain relatively
restricted. The engineering of first-order TI via Zeeman field is expected to
provide a universal approach towards magnetic SOTI Ren2020 ; Chen2020 ; Mu2022
, as long as the applied Zeeman field does not alter the band ordering
protected by spin-orbit coupling (SOC). Nevertheless, this condition is always
violated in intrinsic ferromagnetic insulators where the exchange field
($\sim$ 1.0 eV) determined by electron-electron interactions significantly
outweighs SOC ($\sim$ 0.1 eV).

Physically, band inversions due to orbitals with different parities have
played a crucial role in achieving first-order topology. In topological Kondo
insulators, when the strong electron-electron interactions push up $f$
orbitals into a $d$ band, band inversion takes place, triggering a topological
phase transition Dzero2010 ; Dzero2016 . In noble metals like Au and Ag, the
outermost $s$ orbital has a high energy with respect to $p$ orbitals, giving
rise to a topological origin to Shockley surface states Yan2015 ; Zhang2017 .
Transition metal compounds (TMCs) present another scenario where metal
cation’s $d$ and the ligand’s $p$ orbitals naturally exhibit opposite
parities. For example, the band inversion occurs between $p$ and $d$ orbitals
have lead to quantum spin Hall insulators in $1T^{\prime}$ transition metal
dichalcogenides Qian2014 . Considering the fact TMCs often exemplify
correlated materials, the correlated charge gap tends to be topologically
trivial. However, as we illustrate below, correlated TMCs can harbor a hidden
$p-d$ orbitals order termed as $p-d$ orbitals inversion. This phenomenon, as
fundamental as electron-electron correlations, can engender higher-order
topology without the aid of SOC.

Figure 1: (a) Four high symmetric WPs in 2D $\mathcal{P}$-symmetric lattice:
the fractional coordinates are $1a$ = (0.0, 0.0), $1b$ = (0.5, 0.0), $1c$ =
(0.0, 0.5) and $1d$ = (0.5, 0.5). (b) Four TRIM in the first BZ: $\Gamma$,
$X$, $Y$, and $M$. (c) The linear combination of one $p_{x}$ orbital at WP
$2e$ gives SACOs $|p_{x\pm}>$ with parity "$\pm$". Orbital interaction diagram
for (d) normal ordered $p-d$ orbitals and (e) inverted $p-d$ orbitals.
Blue/red color is used to mark parity $\pm$. Figure 2: (a) Top and side view
of 1$T$-VS2 monolayer, the center of inversion locates at V site. Band
structure of hybrid functionals for (b) spin up and (c) spin down channel.
Label "+/-" indicates (degenerated) Bloch states are parity even/odd. The band
gap is shaded by grey color. (d) Energy spectrum of for a hexagonal cluster
(inset) in the spin up channel. (e) The spatial charge distributions of the
six states marked by red dots in (d). Figure 3:  Determination of (a) $d$
SACOs and (b) $p$ SACOs at $\Gamma$ in 1$T$-VS2 monolayer. (c) Orbital
interaction diagram, the curve in the middle is the band dispersion near
$\Gamma$. (d) Top and side view of the charge densities for Bloch states
labelled as ①-⑦ in (c). For degenerated states, only one charge density is
plotted.

Topological invariant based on parity. Topological invariant is effective in
diagnosing topological phases. As intrinsic magnetic insulators commonly
occupy inversion symmetry $\mathcal{P}$, here we consider $\mathcal{P}$-based
topological invariant Miert2018 ; Po2017 ; Kruthoff2017 . A
$\mathcal{P}$-invariant 2D unit cell is displayed in  Fig. 1 (a), together
with the four Wyckoff positions (WPs) $1a$, $1b$, $1c$, and $1d$ whose site
symmetry including $\mathcal{P}$. In duality, four time-reversal invariant
momentum (TRIM) $\Gamma$, $X$, $Y$ and $M$ exist in the first Brillouin zone
(BZ) as shown in  Fig. 1(b). Denoting $\Gamma_{+/-},X_{+/-},Y_{+/-}$, and
$M_{+/-}$ as the number of occupied Bloch states with odd/even parity at the
four TRIM, the electric dipole ($p_{x},p_{y}$) and quadrupole polarization
($q_{xy}$) are calculated as SI :

$\begin{split}(p_{x},p_{y})&=(\frac{\Gamma_{-}-X_{-}}{2},\frac{\Gamma_{-}-Y_{-}}{2})\mod
1\\\ q_{xy}&=\frac{\Gamma_{-}-X_{-}-Y_{-}+M_{-}}{8}\mod\frac{1}{2}\\\
\end{split}$ (1)

Since a nonvanishing $q_{xy}$ requires vanishing dipole polarization,
following Eq.1, the condition for a SOTI phase is

$\begin{split}&(\Gamma_{-}-X_{-})\mod 2=(\Gamma_{-}-Y_{-})\mod 2=0\\\
&\frac{\Gamma_{-}-X_{-}-Y_{-}+M_{-}}{8}\mod\frac{1}{2}\neq 0\\\ \end{split}$
(2)

If both $(\Gamma_{-}-X_{-})$ and $(\Gamma_{-}-Y_{-})$ are odd rather than
even, first-order TIs is preferred via the Fu-Kane formula Fu2007 . Therefore
Eq.2 puts strong constraints on the numbers of band inversions in realizing
SOTI. For spin polarized materials, we can treat each spin channel separately,
mainly due to the linearity of the topological invariant.

Figure 4:  (a) Top and side view of CrAs monolayer, the center of inversion
locates at the middle of two Cr sites. Band structure of hybrid functionals
for (b) spin up and (c) spin down channel with parity distributions. The label
"(8+4-)" at $\Gamma$ means 8/4 valence states have even/odd parity. (d) Energy
spectrum of for a square cluster (inset) in spin up channel. (e) The spatial
charge distributions of the four states marked by red dot in (d). (f)
Determination of $d$ SACOs $|xy_{\pm}>$ at $\Gamma$ point. All the left $d$
SACOs are topological inert and ignored. (g) Determination of $p$ SACOs at
$\Gamma$. (h) Orbital interaction diagram, the curve in the middle is the band
dispersion around $\Gamma$. For simplicity, only SACOs related to band
inversions are plotted. (i) Top and side view of the charge densities for
Bloch states labelled by ①-③ in (h).

Characterization of $p-d$ orbitals inversion. TMCs are described by the multi-
band $d-p$ model:

$\hat{H}=\hat{H}_{d}+\hat{H}_{p}+\hat{H}_{dp}$ (3)

where $\hat{H}_{d}$ ($\hat{H}_{p}$) describes $d$ ($p$) orbitals of metal
cations (ligand anions) and $\hat{H}_{dp}$ contains interactions between $p$
and $d$ orbitals, like the $p-d$ orbitals hybridization. It is assumed that
the strong correlations in Eq.3 give an ordered phase that can be captured by
a mean-field theory, such as the long-range ferromagnetism discussed herein.
Therefore, magnetic Wannier orbitals serve as a natural basis.

For magnetic Wannier orbitals at the same WPs, we can take their linear
combinations to form cluster orbitals with either odd or even parity at TRIM,
which we dubbed as symmetry-adapted cluster orbitals (SACOs).  Fig. 1 (c)
shows the two $p$ SACOs $|p_{x\pm}>$ ($\pm$ means parity even/odd) constructed
from the $p_{x}$ orbital at WP $2e$. Since intracell hopping is always larger
than that of intercell, $|p_{x+}>$ will always has lower energy than
$|p_{x-}>$. Obviously both $d$ and $p$ orbitals can form SACOs and according
to their onsite energy differences, we have at least two cases: (1) if all $p$
SACOs are occupied at all TRIM as shown in  Fig. 1 (d), we have normal ordered
$p-d$ orbitals, which is shared by most TMCs; (2) if at certain TRIM, there
exists unoccupied $p$ SACO which is higher than all $d$ SACOs as shown in
Fig. 1 (e), it is called inverted $p-d$ orbitals. With further inclusion of
$p-d$ orbital hybridization, if $p$ and $d$ SACOs share the same parity, they
will repeal each other and form gap sandwiched by bonding and antibonding
SACOs $|bonding_{\pm}>/|antibonding_{\pm}>$, as sketched in the orbital
interaction diagram  Fig. 1 (d)-(e). The square of
$|bonding_{\pm}>/|antibonding_{\pm}>$ gives the charge densities which are
accessible through density-functional theory (DFT) calculations. Nevertheless,
when examining charge densities alone, the difference between the orbital
orders represented by  Fig. 1 (d) and  Fig. 1 (e) is always ignored, as both
are contributed by $p$ and $d$ orbitals. To recover the information about the
orbital order, it is necessary to switch off $p-d$ orbital hybridization.
Since DFT can not switch off $\hat{H}_{dp}$, here we take advantage of Wannier
downfolding: Wannier downfolding is firstly conducted using all $d$ and $p$
orbitals to derive an effective Hamiltonian $\hat{H}_{eff}$ approximating
$\hat{H}$. Then, by setting all $p-d$ orbital hybridizations to zero,
$\hat{H}_{eff}$ is reduced to a diagonal form
$\hat{H}_{d,eff}+\hat{H}_{p,eff}$, allowing for the extraction of onsite
energies of $p$ and $d$ SACOs at all TRIM. In this way, the $p-d$ orbital
order can be mapped out. It is emphasized that $p-d$ orbitals inversion can be
regarded as a real space manifestation of band inversion defined in the
reciprocal momentum space. Notably, the $\mathcal{P}$ symmetry applied here
can be replaced by any other crystalline symmetry. Therefore, $p-d$ orbitals
inversion does not inherently depend on specific crystalline symmetries and
should manifest as a generic phenomenon across various crystalline systems. In
the following, we will illustrate how inverted $p-d$ orbitals give rise to
intrinsic ferromagnetic SOTIs in the 1$T$-VS2 monolayer in a hexagon lattice
and the CrAs monolayer in a square lattice.

Hexagonal lattice. The 2D 1$T$-VS2 shares a hexagon lattice as depicted in
Fig. 2 (a). Being a prototypical $d^{1}$ system, 1$T$-VS2 is anticipated to
display phenomena such as charge density wave (CDW) and ferromagnetism.
However, there are controversies regarding CDW and ferromagnetism in both
experiments and theoretical studies. In bulk 1$T$-VS2, magnetic
Murphy-1977-exp  and nuclear magnetic resonance Tsuda-1983-exp  measurements
have indicated a CDW transition below 305 K, while high-pressure samples have
not detected CDW down to 94 K Gauzzi-2014-exp . For monolayers, Arnold et al.
Arnold-2018-exp  found no evidence of CDW on Au(111) surface; however Efferen
et al. Efferen-2021-exp  observed a CDW gap above the Fermi level on
graphene/Ir(111) surface. Predicted to be a ferromagnetic metal Ma-2012-theo
without CDW Issacs-2016-theo ; Zhuang-2016-theo , Gao et al. Gao-2013-exp
reported room temperature ferromagnetism in ultrathin 1$T$-VS2 nanosheets by
observing magnetic hysteresis and ferromagnetic resonance. Subsequently, Guo
et al. Guo-2017-exp  revealed that 1$T$-VS2 undergoes a ferromagnetic
semiconductor to ferromagnetic metal transition with respect to van der Waals
gaps. Here we concentrate on the ferromagnetic semiconducting phase.

Employing DFT calculations with hybrid functionals SI ,  Fig. 2 (b)-(c)
suggest 1$T$-VS2 is a small gap ferromagnetic semiconductor, in consistent
with the experiment Guo-2017-exp . Although the long-range ferromagnetic order
breaks all vertical mirror symmetries, the rotoinversion $S_{6z}$ is conserved
and $X$, $Y$, and $M$ share the same parity distribution, thus Eq.2 now is

$\Gamma_{-}-M_{-}=2\mod 4$ (4)

According to the parity eigenvalues listed in  Fig. 2 (b)-(c),
$\Gamma_{-}=1,M_{-}=3$ ($\Gamma_{-}=M_{-}=3$) in the spin up (down) channel
gives a SOTI (trivial) phase. Due to the bulk-boundary correspondence in
SOTIs, the nonvanishing $q_{xy}$ in the spin up channel implies the existence
of spin-polarized gapped edge states (see Fig. S2 SI ) and corner states.
Given that TMD nanoflakes always adopt hexagonal and triangular shapes during
growth,  Fig. 2 (d) shows the energy spectrum of a hexagon cluster with an
edge length of 8$a_{0}$ ($a_{0}$ = 3.23 Å, the optimized in-plane lattice
constant of 2D 1$T$-VS2, in good agreement with experiment Gauzzi-2014-exp ).
It is clear that there are six isolated states whose charge densities are
localized at the six corners, reflecting the nontrivial topology in the bulk.
Such topological corner states can also be found in triangular shapes SI .

The topological distinction between spin up and down channel can be readily
understood through the underlying $p-d$ orbitals order. As shown in Fig. S1 SI
, spin down channel has a normal ordered $p-d$ orbitals, where the six valence
(five conduction) bands in  Fig. 2 (c) originate from the $p$ orbitals of S
($d$ orbitals of V). In other words, the spin down channel is adiabatically
connected to an atomic insulator (AI) formed by the S sublattice. This
explains why the spin down channel exhibits a parity distribution
$\Gamma_{-}=\Gamma_{+}=M_{-}=M_{+}=3$ in  Fig. 2 (c), and must be topological
trivial. Conversely, the situation in the spin up channel varies
significantly, particularly at $\Gamma$ when comparing parity distribution in
Fig. 2 (b) and  Fig. 2 (c). As illustrated in  Fig. 3 (a)-(b), there is a
$p-d$ orbitals inversion at $\Gamma$: the $p$ SACOs $|x_{\pm}>/|y_{\pm}>$ are
higher than all the $d$ SACOs. When $p-d$ orbital hybridization is taken into
account, $|x_{-}>/|y_{-}>$ becomes (degenerate) nonbonding states ② in  Fig. 3
(c), where the charge densities are entirely contributed by $p_{x/y}$
orbitals, as shown in  Fig. 3 (d). Since such (degenerate) nonbonding states
are the lowest conduction states at $\Gamma$, the spin up channel now only has
$\Gamma_{-}=1$, in contrast to $\Gamma_{-}=3$ in the spin down channel. This
discrepancy leads to nontrivial topology in the spin up channel as $M_{-}=3$
for both spin channels.

Square lattice. CrAs monolayer, featuring an anti-PbO type structure shown in
Fig. 4(a), is predicted to be a high Curie temperature ferromagnetic
semiconductor with a good stability Liu2023 ; Ma2020 . The pronounced
ferromagnetism in this system is demonstrated to be mediated by the
significant number of $p$ holes on As atoms Liu2023 . As we elucidate later,
the emergence of such non-negligible $p$ holes is a direct consequence of
$p-d$ orbitals inversion.

As CrAs monolayer shares a nonsymmorphic space group $p\frac{4}{n}mm$, the
Bloch states at $X$, $Y$, $M$ are two-fold degenerate and each degeneracy
shares opposite parity eigenvalues SI . Under such circumstances, Eq.2
becomes:

$\Gamma_{-}-\Gamma_{+}=4\mod 8$ (5)

which implies the construction of SACOs can be narrowed down to $\Gamma$.

Fig. 4(b)-(c) presents the DFT band structures based on hybrid functionals and
the parity distributions for the 12 (6) valance bands in the spin up (down)
channel. The parity distribution $\Gamma_{-}=\Gamma_{+}=3$ in the spin down
channel indicates a trivial phase according to Eq.5. In contrast, for the spin
up channel, we observe $\Gamma_{-}-\Gamma_{+}=-4$, suggesting a SOTI phase.
Fig. 4(d) displays the energy spectrum of a square cluster with an edge length
of $20a_{0}$ ($a_{0}$ = 4.20 Å). Notably, there are four isolated states with
charge localized at the four corners, signifying a nonvanishing $q_{xy}$ in
the spin up channel.

Next we turn to the orbital order. In the spin down channel, the $p-d$
orbitals exhibit a normal ordering SI  which is continuously connected to the
AI formed by the As sublattice, akin to the scenario observed in 1$T$-VS2
monolayer. In contrast, the $p-d$ orbitals are inverted in the spin up
channel, as illustrated in  Fig. 4(f)-(g). Here all antibonding $p$ SACOs
$|x_{-}/y_{-}/z_{-}>$ are higher than all $d$ SACOs, contributing to
$\Gamma_{-}-\Gamma_{+}=-3$. Additionally, the $d$ SACO $|xy_{-}>$ also plays a
crucial role as it constitutes the conduction state ③ at $\Gamma$, as
illustrated in  Fig. 4(h)-(i). With all the left $d$ SACOs occupied, $d$ SACO
$|xy_{-}>$ contributes $\Gamma_{-}-\Gamma_{+}=-1$. Combining $p$ and $d$ SACOs
together, we obtain $\Gamma_{-}-\Gamma_{+}=-4$ in the spin up channel, in
agreement with the parity distribution observed in  Fig. 4(b).

Discussions. In the 1$T$-VS2 monolayer, the $d$ SACOs are topologically inert
as the parity eigenvalues at $\Gamma$ and $M$ are always the same.
Consequently, band inversion can only occur through the empty $p$ SACOs
$|x_{-}>/|y_{-}>$. In the CrAs monolayer, the $d$ SACOs do participate in band
inversion like $|xy_{-}>$, it seems that SOTI can be realized without the aid
of $p-d$ orbitals inversion. However this assumption is incorrect. In an
insulator without $p-d$ orbitals inversion, the $p$ orbitals form a closed
shell with all $p$ SACOs occupied. To achieve a nonvanishing $q_{xy}$,
according to Eq.5, we must select another six occupied states from the ten $d$
SACOs to satisfy $\Gamma_{-}-\Gamma_{+}=4\mod 8$. Nevertheless this is
impossible as only $|xy_{-}>$ and $|z^{2}_{-}>$ possess higher energy than
$|xy_{+}>$ and $|z^{2}_{+}>$ among all the $d$ SACOs. Therefore the maximum
value $\Gamma_{-}-\Gamma_{+}$ can reach is 2, as found in the configuration
$(xy_{-})^{1}(xy_{+})^{1}(z^{2}_{+})^{1}(xz_{-})^{1}(yz_{-})^{1}((x^{2}-y^{2})_{-})^{1}$.
Hence, the empty $p$ SACOs are necessity for achieving SOTI in the spin up
channel, underscoring the significance of inverted $p-d$ orbitals in the CrAs
monolayer.

In $\mathbb{Z}_{2}$ TIs, SOC is necessary to open a nontrivial gap. In
magnetic SOTIs via $p-d$ orbitals inversion, the gap is created through $p-d$
orbital hybridization. Therefore, the magnetic SOTIs studied here are robust
to SOC as long as SOC does not alter the orbital order. Given that the gap at
$\Gamma$ in the spin up channel is significantly larger than the strength of
SOC in both 1$T$-VS2 and CrAs monolayers, the SOTI phase should persist even
when SOC is considered, as confirmed by our calculations SI . Thus, magnetic
SOTIs originating from $p-d$ orbitals inversion represent another class of
SOC-free topological phases Alexandradinata2014 , distinct from the universal
approach Ren2020 ; Chen2020  where SOC is indispensable. We would like to
highlight the similarity between magnetic SOTIs generated by $p-d$ orbitals
inversion and topological Kondo insulators. In both topological phases, band
inversion is induced by orbital inversions under electron-electron
interactions and gap is created via orbital hybridization.

Where to find materials with $p-d$ orbitals inversion ? It is suggested that
TMCs with high formally valance states, such as V4+ and Cr3+ studied in this
work, should demonstrate $p-d$ orbitals inversion Khomskii2014 . With inverted
$p-d$ orbitals, electrons tend to transfer from $p$ to $d$ orbitals to avoid
high formally valance states, resulting in a surplus of holes in the ligands.
These holes is capable of stabilizing strong ferromagnetic order Khomskii1997
; Liu2023 , thus illustrating the dual roles of $p-d$ orbitals inversion in
achieving both ferromagnetism and nontrivial topology. This is how strong
correlation and nontrivial topology reconcile in this type of materials. It is
worth noting that a broad range of TMDs possess high formally valance states
and should represent potential candidates for realizing $p-d$ orbitals
inversion, as suggested by a recent study Cheng2024 .

In conclusion, this study unveils that $p-d$ orbitals inversion provides a
generic approach to SOTIs in intrinsic ferromagnetic insulators, and
demonstrates that ferromagnetic 1$T$-VS2 and CrAs monolayer exhibiting
inverted $p-d$ orbitals can indeed host a robust SOTI phase. These findings
not only advance the current understanding of magnetic SOTIs but also open up
a novel avenue for exploring nontrivial topological phases in correlated
materials, like SOTI phase in Kondo lattice Dzero2016 .

Z. L., Y. Y. and N. V. M. gratefully acknowledge the support from National
Computing Infrastructure, Pawsey Supercomputing Facility and the Australian
Research Council’s Centre of Excellence in Future Low-Energy Electronic
Technologies (CE170100039). B. L. is funded by the National Natural Science
Foundation of China under Grant No. 12204356 and the Natural Science
Foundation of Shandong Province under Grant No. ZR2022QA024.

## References

  * (1) C. L. Kane, and E. J. Mele, _Phys. Rev. Lett._ 95, 146802 (2005).
  * (2) B. A. Bernevig, T. L. Hughes, and S. C. Zhang, _Science_ 314, 1757 (2006).
  * (3) W. A. Benalcazar, B. A. Bernevig, and T. L. Hughes, _Science_ 357, 61 (2017).
  * (4) W. A. Benalcazar, B. A. Bernevig, and T. L. Hughes, _Phys. Rev. B_ 96, 245115 (2017).
  * (5) J. Langbehn, Y. Peng, L. Trifunovic, F. von Oppen, and P. W. Brouwer, _Phys. Rev. Lett._ 119, 246401 (2017).
  * (6) Z. Song, Z. Fang, and C. Fang, _Phys. Rev. Lett._ 119, 246402 (2017).
  * (7) F. Schindler, A. M. Cook, M. G. Vergniory, Z. Wang, S. S. P. Parkin, B. A. Bernevig, and T. Neupert, _Sci. Adv._ 4, eaat0346 (2018).
  * (8) G. van Miert, and C. Ortix, _Phys. Rev. B_ 98, 081110(R) (2018).
  * (9) B. Xie, H.-X. Wang, X. Zhang, P. Zhang, J.-H. Jiang, M. Lu, and Y. Chen, _Nat. Rev. Phys._ 3, 520 (2021).
  * (10) A. Wang, Y. Li, G. Yang et al. _Nat. Commun._ 14, 7647 (2023).
  * (11) Z. Yan, F. Song, and Z. Wang, _Phys. Rev. Lett._ 121, 096803 (2018).
  * (12) Z. Yan, _Phys. Rev. B_ 100, 205406 (2019).
  * (13) M. Ezawa, _Phys. Rev. Lett._ 120, 026801 (2018).
  * (14) J. Jung, and Y.-H. Kim _Phys. Rev. B_ 105, 085138 (2022).
  * (15) J. Zeng, H. Liu, H. Jiang, Q.-F. Sun, and X. C. Xie, _Phys. Rev. B_ 104, L161108 (2021).
  * (16) X.-L. Sheng, C. Chen, H. Liu, Z. Chen, Z.-M. Yu, Y. X. Zhao, and S. A. Yang, _Phys. Rev. Lett._ 123, 256402 (2019).
  * (17) B. Liu, G. Zhao, Z. Liu, and Z. F. Wang, _Nano Lett._ 19, 6492 (2019).
  * (18) E. Lee, R. Kim, J. Ahn, and B.-J. Yang, _npj Quantum Mater._ 5, 1 (2020).
  * (19) T. Hu, T. Zhang, H. Mu, and Z. Wang, _J. Phys. Chem. Lett._ 13, 10905 (2022).
  * (20) X. Ni, H, Huang, and J.-L. Brédas _J. Am. Chem. Soc._ 144, 22778 (2022).
  * (21) T. Hu, W. Zhong, T. Zhang, W. Wang, and Z. F. Wang, _Nat. Commun._ 14, 7092 (2023).
  * (22) B. Liu, L. Xian, H. Mu, G. Zhao, Z. Liu, A. Rubio, and Z. F. Wang, _Phys. Rev. Lett._ 126, 066401 (2021).
  * (23) H. Huang, J. Fan, D. Li, and F. Liu, _Nano Lett._ 21, 7056 (2021).
  * (24) M. Pan, D. Li, J. Fan, and H. Huang, _npj Quantum Mater._ 8, 1 (2022).
  * (25) F. Schindler, M. Brzezińska, W. A. Benalcazar, M. Iraola, A. Bouhon, S. S. Tsirkin, M. G. Vergniory, and T. Neupert, _Phys. Rev. Research_ 1, 033074 (2019).
  * (26) Z. Wang, B. J. Wieder, J. Li, B. Yan, and B. A. Bernevig, _Phys. Rev. Lett._ 123, 186401 (2019).
  * (27) F. Schindler, Z. Wang, M. G. Vergniory et al. _Nat. Phys._ 14, 918 (2018).
  * (28) Y.-B. Choi, Y. Xie, C.-Z.Chen et al. _Nat. Mater._ 19, 974 (2020).
  * (29) J. Lee, J. Kwon, E. Lee, J. Park, S. Cha, K. Watanabe, T. Taniguchi, M.-H. Jo, and H. Choi, _Nat. Commun._ 14, 1801 (2023).
  * (30) R. Noguichi, M. Kobayashi, Z. Jiang et al. _Nat. Mater._ 20, 473 (2021).
  * (31) B. Huang, G. Clark, E. Navarro-Moratalla et al. _Nature_ 546, 270-273 (2017).
  * (32) C. Gong, L. Li, Z. Li et al. _Nature_ 546, 265-269 (2017).
  * (33) Z. Zhang, J. Shang, C. Jiang, A. Rasmita, W. Gao, and T. Yu, _Nano Lett._ 19, 3138 (2019).
  * (34) T. Kong, K. Stolze, E. I. Timmons, J. Tao, D. Ni, S. Guo, Z. Yang, R. Prozorov, and R. J. Cava, _Adv. Mater._ 31, 1808074 (2019).
  * (35) Y. Deng, Y. Yu, M. Z. Shi, Z. Guo, Z. Xu, J. Wang, X. H. Chen, and Y. Zhang, _Science_ 367, 895 (2020).
  * (36) K. Lee, A. H. Dismukes, E. J. Telford, R. A. Wiscons, J. Wang, X. Xu, C. Nuckolls, C. R. Dean, X. Roy, and X. Zhu, _Nano Lett._ 21, 3511 (2021).
  * (37) X. Li, Q.-B. Liu, Y. Tang, W. Li, N. Ding, Z. Liu, H.-H. Fu, S. Dong, X. Li, and J. Yang, _J. Am. Chem. Soc._ 145, 7869 (2023).
  * (38) Z. Liu, X. Li, W. Zhu, Z. F. Wang, and J. Yang, _Phys. Rev. B_ 107, 014413 (2023).
  * (39) R. Li, N. Mao, X. Wu, B. Huang, Y. Dai, and C. Niu, _Nano Lett._ 2023, 91-97 (2023).
  * (40) L. Cai, R. Li, X. Wu, B. Huang, Y. Dai, and C. Niu, _Phys. Rev. B_ 107, 245116 (2023).
  * (41) X. Wang, X.-P. Li, J. Li, C. Xie, J. Wang, H. Yuan, W. Wang, Z. Cheng, Z.-M. Yu and G. Zhang, _Adv. Funct. Mater._ , 2304499 (2023).
  * (42) Y. Ren, Z. Qiao, and Q. Niu, _Phys. Rev. Lett._ 124, 166804 (2020).
  * (43) C. Chen, Z. Song, J.-Z. Zhao, Z. Chen, Z.-M. Yu, X.-L. Sheng, and S. A. Yang, _Phys. Rev. Lett._ 125, 056402 (2020).
  * (44) H. Mu, G. Zhao, H. Zhang, and Z. F. Wang, _npj Comp. Mater._ 8, 82 (2022).
  * (45) M. Dzero, K. Sun, V. Galitski, and P. Coleman, _Phys. Rev. Lett._ 104, 106408 (2010).
  * (46) M. Dzero, J. Xia, V. Galitski, and P. Coleman, _Annu. Rev. Condens. Matter Phys._ 7, 249-280 (2016).
  * (47) B. Yan, B. Stadtmüller, N. Haag, S. Jakobs, J. Seidel, D. Jungkenn, S. Mathias, M. Cinchetti, M. Aeschlimann, and C. Felser, _Nat. Commun._ 6, 10167 (2015).
  * (48) P. Zhang, J.-Z. Ma, Y. Ishida et al. _Phys. Rev. Lett._ 118, 046802 (2017).
  * (49) X. Qian, J. Liu, L. Fu, and J. Li, _Science_ 346, 1344 (2014).
  * (50) A.-N. Ma, P.-J. Wang, and C.-W. Zhang, _Nanoscale_ 12, 5464 (2020).
  * (51) H. C. Po, A. Vishwanath, H. Watanabe, _Nat. Commun._ 8, 1 (2017).
  * (52) J. Kruthoff, J. de Boer, J. V. Wezel, C. L. Kane, and R.-J. Slager, _Phys. Rev. X_ 7, 041069 (2017).
  * (53) See Supplemental Material.
  * (54) L. Fu, and C. L. Kane, _Phys. Rev. B_ 76, 045302 (2007).
  * (55) D. W. Murphy, C. Cros, F. J. Di Salvo, and J. V. Waszczak, _Inorg. Chem._ 16, 3207 (1977).
  * (56) T. Tsuda, H. Yasuoka, Y. Kitaoka, and F. J. Di Salvo, _J. Magn. Magn. Mater._ 31-34, 1101 (1983).
  * (57) A. Gauzzi, A. Sellam, G. Rousse et al. _Phys. Rev. B_ 89, 235125 (2014).
  * (58) F. Arnold, R.-M. Stan, S. K. Mahatha, H. E. Lund, D. Curcio, M. Dendzik, H. Bana, E. Travaglia, L. Bignardi, and P. Lacovig, _2D Mater._ 5, 045009 (2018).
  * (59) C. van Efferen, J. Begers, J. Hall et al. _Nat. Commun._ 12, 6873 (2021).
  * (60) Y. Ma, Y. Dai, M. Guo, C. Niu, Y. Zhu, and B. Huang, _ACS nano_ 6, 1695 (2012).
  * (61) E. B. Isaacs, and C. A. Marianetti, _Phys. Rev. B_ 94, 035120 (2016).
  * (62) H. L. Zhuang, and R. G. Hennig, _Phys. Rev. B_ 93, 054429 (2016).
  * (63) D. Gao, Q. Xue, X. Mao, W. Wang, Q. Xu, and D. Xue, _J. Mater. Chem. C_ 1, 5909 (2013).
  * (64) Y. Guo, H. Deng, X. Sun et al. _Adv. Mater._ 29, 1700715 (2017).
  * (65) J. Ahn, D. Kim, Y. Kim, and B.-J. Yang, _Phys. Rev. Lett._ 121, 106403 (2018).
  * (66) A. Alexandradinata, C. Fang, M. J. Gilbert, and B. A. Bernevig, _Phys. Rev. Lett._ 113, 116403 (2014).
  * (67) D. I. Khomskii, _Transition metal compounds_ , (Cambridge University Press, Cambridge, 2014).
  * (68) D. I. Khomskii, and G. A. Sawatzky, _Solid State Commun._ 102, 87 (1997).
  * (69) J. Cheng, J. Ban, B. Ruan et al. _J. Am. Chem. Soc._ 146, 5908 (2024).


..boundary value problems via topological methods….

# Existence results for quasilinear elliptic boundary value problems via
topological methods

Quô´ c Anh Ngô  Department of Mathematics,
College of Science, Viêt Nam National University
Hà Nôi, Viêt Nam<EMAIL_ADDRESS>
(Date: May 01, 2008)

###### Abstract.

In this paper, existence and localization results of $C^{1}$-solutions to
elliptic Dirichlet boundary value problems are established. The approach is
based on the nonlinear alternative of Leray-Schauder.

###### Key words and phrases:

Quasilinear; Elliptic; Boundary value problem; Dirichlet, Leray-Schauder
principle, Fixed point

###### 2000 Mathematics Subject Classification:

35J20, 35J65, 47H10

This paper was typeset using AmS-LaTeX

##  1\. Introduction

In this paper, we consider the boundary value problem

$\begin{gathered}-\Delta_{p}u=f(x,u),\quad\mbox{in }\Omega,\\\
u=0,\quad\mbox{on }\partial\Omega,\end{gathered}$ (1)

where $\Omega\subset\operatorname{\mathbb{R}}^{N}$ ($N\geqq 1$) is a nonempty
bounded open set with smooth boundary $\partial\Omega$ and
$f:\Omega\times\operatorname{\mathbb{R}}\to\operatorname{\mathbb{R}}$ is a
continuous function. We seek $C^{1}$-solutions, i.e. function $u\in
C^{1}(\overline{\Omega})$ which satisfy (1) in the sense of distributions.

In recent years, many authors have studied the existence of solutions for
problem (1) from several points of view and with different approaches (see,for
example, [A, AR, CCN, CTY]). For instance, Afrouzi and Rasouli [AR] ensure the
existence of solutions for special types of nonlinearities, by using the
method of sub- and supersolutions.

Existence and multiplicity results for problem (1) are also presented by
Anello [A], where $f$ admits the decomposition $f=g+h$ with $g$ and $h$ two
Carathéodory functions having no growth conditions with respect to the second
variable. His approach is variational and mainly based on a critical point
theorem by B. Ricceri.

In [CCN], Castro, Cossio and Neuberger apply the minmax principle to obtain
sign-changing solutions for superlinear and asymptotically linear Dirichlet
problems.

A novel variational approach is presented by Costa, Tehrani and Yang [CTY] to
the question of existence and multiplicity of positive solutions to problem
(1), where they consider both the sublinear and superlinear cases. Another
useful method for the investigation of solutions to semilinear problems is
based on the Leray-Schauder continuation principle, or equivalently, on
Schaefer s fixed point theorem. For example, in [GT] this method is used for
solutions in Hölder spaces, while in [OP], solutions are found in Sobolev
spaces.

In this paper, we present new existence and localization results for
$C^{1}$-solutions to problem (1), under suitable conditions on the
nonlinearity $f$. No growth conditions of subcritical exponent type are
required. Our approach is based on regularity results for the solutions of
linear Dirichlet problems and again on the nonlinear alternative of Leray-
Schauder (see [DG, Z]). We also notice that our present paper is motivated by
the paper [MP] where the same results are obtained for semilinear elliptic
boundary value problems.

Our approach is mainly based on the following well-known theorem.

######  Theorem 1.

Let $B[0,r]$ denote the closed ball in a Banach space $E$ with radius $r$, and
let $T:B[0,r]\to E$ be a compact operator. Then either

  1. (i)

the equation $\lambda Tu=u$ has a solution in $B[0,r]$ for $\lambda=1$, or

  2. (ii)

there exists an element $u\in E$ with $\|u\|=r$ satisfying $\lambda Tu=u$ for
some $0<\lambda<1$.

It is worth noticing that contrary to most papers in the literature where the
Leray-Schauder principle is used together with the a priori bounds technique,
in the proof of our main result, Theorem 2, no a priori bounds of solutions of
(3) are established. In addition, Theorem 2 not only that guarantees the
existence of a solution, but also gives information about its localization.
This is derived from a very general growth condition, inequality (3), which in
particular contains both sublinear and superlinear cases without any
restriction of exponent.

##  2\. Main results

Here and in the sequel $E$ will denote the space

$C_{0}\left({\overline{\Omega}}\right)=\left\\{{u\in
C\left({\overline{\Omega}}\right):u=0{\mbox{ on }}\partial\Omega}\right\\}$

endowed with the sup-norm

$\left\|u\right\|_{0}=\mathop{\sup}\limits_{x\in\overline{\Omega}}\left|{u\left(x\right)}\right|.$

Also by $C^{1}_{0}(\Omega)$ we mean the space $C^{1}(\overline{\Omega})\cap
C_{0}(\overline{\Omega})$. We start with an existence and localization
principle for (1)

######  Theorem 2.

Assume that there is a constant $r>0$, independent of $\lambda>0$, with

$\|u\|_{0}\neq r,$ (2)

for any solution $u\in C^{1}_{0}(\overline{\Omega})$ to

$\begin{gathered}-\Delta_{p}u=\lambda f(x,u),\quad\mbox{in }\Omega,\\\
u=0,\quad\mbox{on }\partial\Omega,\end{gathered}$ (3)

and for each $\lambda\in(0,1)$. Then the boundary value problem (1) has at
least one solution $u\in C^{1}_{0}(\overline{\Omega})$ with $\|u\|_{0}\leqq
r$.

In order to prove Theorem 2, we firstly recall a well-known property of the
operator $-\Delta_{p}$.

######  Lemma 1 (See [AC], Lemma 1.1).

Let $\Omega\subset\operatorname{\mathbb{R}}^{N}$ be a bounded domain of class
$C^{1,\beta}$ for some $\beta\in(0,1)$ and $g\in L^{\infty}(\Omega)$. Then the
problem

$\begin{gathered}\int_{\Omega}{|\nabla u|^{p-2}\nabla u\nabla\varphi
dx}=\int_{\Omega}{g\varphi dx},\quad\mbox{ for all }\varphi\in
C_{0}^{\infty}(\Omega),\\\ u\in W_{0}^{1,p}(\Omega),\quad p>1,\end{gathered}$
(4)

has a unique solution $u\in C^{1}_{0}(\overline{\Omega})$. Moreover, if we
define the operator $K:L^{\infty}(\Omega)\to
C^{1}_{0}(\overline{\Omega}):g\mapsto u$ where $u$ is the unique solution of
(6), then $K$ is continuous, compact and order-preserving.

###### PROOF OF THEOREM 2.

According to Lemma 1, the operator $(-\Delta_{p})^{-1}$ from
$L^{\infty}(\Omega)$ to $C^{1}_{0}(\overline{\Omega})$ is well-defined,
continuous, compact and order-preserving. We shall apply Theorem 1 to
$E=C_{0}(\overline{\Omega})$ and to the operator
$T:C_{0}(\overline{\Omega})\to C_{0}(\overline{\Omega})$, with
$Tu=(-\Delta_{p})^{-1}Fu$, where $F:C(\overline{\Omega})\to
C(\overline{\Omega})$ is given by $(Fu)(x)=f(x,u(x))$. Notice that, On the
other hand, it is clear that the fixed points of $T$ are the solutions of
problem (1). Now the conclusion follows from Theorem 1 since condition (ii) is
excluded by hypothesis. ∎

Theorem 2.1 immediately yields the following existence and localization
result.

######  Theorem 3.

Assume that there exist nonnegative continuous functions $\alpha$, $\beta$ and
a continuous nondecreasing function
$\psi:\operatorname{\mathbb{R}}_{+}\to\operatorname{\mathbb{R}}_{+}$ such that

$\left|{f\left({x,u}\right)}\right|\leqq\alpha\left(x\right)\psi\left({\left|u\right|}\right)+\beta\left(x\right),\quad\forall\left({x,u}\right)\in\Omega\times\operatorname{\mathbb{R}}.$
(5)

Suppose in addition that there exists a real number $r>0$ such that

$r\geqq\left\|{\left({-\Delta_{p}}\right)^{-1}\alpha}\right\|_{0}\psi\left(r\right)+\left\|{\left({-\Delta_{p}}\right)^{-1}\beta}\right\|_{0}.$
(6)

Then the boundary value problem (1) has at least one solution in
$C_{0}^{1}(\overline{\Omega})$ with $\|u\|_{0}\leqq r$.

###### Proof.

In order to apply Theorem 2, we have to show that condition (2) holds true for
all solutions to (3). Assume $u$ is any solution of (3) for some
$\lambda\in(0,1)$ with $\|u\|_{0}=r$. Then

$u=\lambda Tu=\lambda\left({-\Delta_{p}}\right)^{-1}Fu.$

Futhermore, for all $x\in\overline{\Omega}$, we have

$\displaystyle\left|{u\left(x\right)}\right|$
$\displaystyle=\lambda\left|{\left({-\Delta_{p}}\right)^{-1}Fu\left(x\right)}\right|\hfill$
$\displaystyle\leqq\lambda\left|{\left({-\Delta_{p}}\right)^{-1}\left({\alpha\left(x\right)\psi\left({\left|{u\left(x\right)}\right|}\right)+\beta\left(x\right)}\right)}\right|\hfill$
$\displaystyle\leqq\lambda\left({\left\|{\left({-\Delta_{p}}\right)^{-1}\alpha}\right\|_{0}\psi\left({\left\|u\right\|_{0}}\right)+\left\|{\left({-\Delta_{p}}\right)^{-1}\beta}\right\|_{0}}\right)\hfill$
$\displaystyle\leqq\lambda\left({\left\|{\left({-\Delta_{p}}\right)^{-1}\alpha}\right\|_{0}\psi\left(r\right)+\left\|{\left({-\Delta_{p}}\right)^{-1}\beta}\right\|_{0}}\right).$

Taking the supermum in the above inequality, we obtain

$\left\|u\right\|_{0}\leqq\lambda\left({\left\|{\left({-\Delta_{p}}\right)^{-1}\alpha}\right\|_{0}\psi\left(r\right)+\left\|{\left({-\Delta_{p}}\right)^{-1}\beta}\right\|_{0}}\right).$

Therefore $r\leqq\lambda r<r$ since $\lambda\in(0,1)$ and $\|u\|_{0}\leqq r$.
This is a contradiction. ∎

## Acknowledgments

This manuscript has NOT been SUBMITTED/ACCEPTED/REJECTED for publication
before. This is the FIRST submission.

## References

  * [A] G. Anello, Existence of solutions for a perturbed Dirichlet problem without growth conditions, J. Math. Anal. Appl. 330(2), 1169-1178.
  * [AC] C. Azizieh and Ph. Clément, A priori estimates and continuation methods for positive solutions of p-Laplace equations, J. Diff Eqns, 179 (2002), 213-245.
  * [AR] G.A. Afrouzi and S.H. Rasouli, On positive solutions for some nonlinear semipositone elliptic boundary value problems Nonlinear Analysis: Modelling and Control, 11 (4), (2006), 323-329.
  * [CCN] A. Castro, J. Cossio and J.M. Neuberger, A minmax principle, index of the critical point, and existence of sign-changing solutions to elliptic boundary value problems, Electron. J. Diff Eqns, 1998, no. 2, 18 pp.
  * [CTY] D.G. Costa, H. Tehrani and J.J. Yang, On a variational approach to existence and multiplicity results for semipositone problems , Electron. J. Diff Eqns, 2006, no. 11, 10 pp.
  * [DG] J. Dugundji and A. Granas, Fixed Point Theory, Monographie Math., Warsaw, 1982.
  * [GT] D. Gilbarg and N. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer, Berlin, 1983.
  * [MP] T. Moussaoui and R. Precup, Existence results for semilinear elliptic boundary value problems via topological methods, Applied Mathematics Letters (2008), doi:10.1016/j.aml.2008.03.002.
  * [OP] D. O Regan and R. Precup, Theorems of Leray-Schauder Type and Applications, Gordon and Breach, Amsterdam, 2001.
  * [Z] E. Zeidler, Nonlinear Functional Analysis : Part I, Springer-Verlag, New York, 1985.