# Private Simultaneous Messages Based on Quadratic Residues

Kazumasa Shinagawa  Ibaraki University  National Institute of Advanced
Industrial Science and Technology (AIST)  Reo Eriguchi  The University of
Tokyo  National Institute of Advanced Industrial Science and Technology (AIST)
Shohei Satake  Meiji University  Koji Nuida  Institute of Mathematics for
Industry (IMI), Kyushu University  National Institute of Advanced Industrial
Science and Technology (AIST)

###### Abstract

Private Simultaneous Messages (PSM) model is a minimal model for secure
multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai
(Cryptology and Information Security Series 2013) constructed PSM protocols
based on quadratic residues. In this paper, we define QR-PSM protocols as a
generalization of these protocols. A QR-PSM protocol is a PSM protocol whose
decoding function outputs the quadratic residuosity of what is computed from
messages. We design a QR-PSM protocol for any symmetric function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ of communication complexity $O(n^{2})$.
As far as we know, it is the most efficient PSM protocol since the previously
known best PSM protocol was of $O(n^{2}\log n)$ (Beimel et al., CRYPTO 2014).
We also study the sizes of the underlying finite fields $\mathbb{F}_{p}$ in
the protocols since the communication complexity of a QR-PSM protocol is
proportional to the bit length of the prime $p$. In particular, we show that
the $N$-th Peralta prime $P_{N}$, which is used for general QR-PSM protocols,
can be taken as at most $(1+o(1))N^{2}2^{2N-2}$, which improves the Peralta’s
known result (Mathematics of Computation 1992) by a constant factor
$(1+\sqrt{2})^{2}$.

##  1 Introduction

_Private Simultaneous Messages (PSM) model_ introduced by Feige, Kilian, and
Naor [17] and named by Ishai and Kushilevitz [20] is a minimal model for non-
interactive secure multiparty computation with information-theoretic security.
In the PSM model, there are $n$ _players_ and a special party called a
_referee_. Each player $P_{i}$ computes a message $m_{i}$ from $P_{i}$’s input
$x_{i}$ and a _shared randomness_ $r$, and sends $m_{i}$ to the referee. Here,
the shared randomness $r$ is known by all players but the referee. Given $n$
messages $m_{1},m_{2},\ldots,m_{n}$, the referee computes an output value $y$,
which is expected to be $y=f(x_{1},x_{2},\ldots,x_{n})$ for a function $f$
agreed upon by all players and the referee. The security of the protocol
ensures that the referee cannot learn anything about the secret inputs beyond
what can be inferred from the output value. The efficiency of PSM protocols is
mainly measured by the communication complexity $\sum_{i=1}^{n}|m_{i}|$, where
$|\cdot|$ denotes the bit length.

###  1.1 PSM Protocols Based on Quadratic Residues

In this paper, we study PSM protocols based on quadratic residues. As far as
we know, there are two existing PSM protocols based on quadratic residues.
Feige, Kilian, and Naor [17] proposed such a protocol for comparing two
numbers $x$ and $y$, i.e., deciding whether $x\geq y$ or not. Ishai [19]
designed such a protocol for any function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$.

####  1.1.1 Feige-Kilian-Naor’s Protocol

The protocol based on quadratic residues by Feige, Kilian, and Naor [17] is a
two-player PSM protocol computing the comparison function ${\sf
COMP}:\\{0,1,2\\}\times\\{0,1,2\\}\rightarrow\\{-1,0,1\\}$ as follows:

${\sf COMP}(x_{1},x_{2})=\begin{cases}1&\text{if $x_{1}>x_{2}$},\\\ 0&\text{if
$x_{1}=x_{2}$},\\\ -1&\text{if $x_{1}<x_{2}$}.\end{cases}$

The shared randomness of the protocol is a pair $(r_{1},r_{2})$ of an element
$r_{1}$ of $\mathbb{Z}/7\mathbb{Z}$ and a nonzero quadratic residue $r_{2}$
modulo $7$. The first player $P_{1}$ computes a message
$m_{1}\in\mathbb{Z}/7\mathbb{Z}$ as $m_{1}:=r_{1}+r_{2}x_{1}\;(\bmod\;7)$, and
the second player $P_{2}$ computes a message $m_{2}\in\mathbb{Z}/7\mathbb{Z}$
as $m_{2}:=-r_{1}-r_{2}x_{2}\>(\bmod\;7)$. Given $m_{1},m_{2}$, the referee
computes the quadratic residuosity of $m:=m_{1}+m_{2}\;(\bmod\;7)$, and
outputs $1$ if $m$ is a non-zero quadratic residue, $-1$ if $m$ is a quadratic
nonresidue, and $0$ if $m=0$.

####  1.1.2 Ishai’s Protocol

The protocol based on quadratic residues by Ishai [19] is an $n$-player PSM
protocol computing any function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. Let $p$
be a prime and $0<a\leq p-2^{n}$ an integer such that
$a+\sum_{i=1}^{n}2^{i-1}b_{i}$ is a quadratic residue modulo $p$ if and only
if $f(b_{1},b_{2},\ldots,b_{n})=1$. From the result by Peralta [21], such a
prime $p$ with $p=2^{O(n)}$ exists. The shared randomness of the protocol is a
tuple $(r_{0},r_{1},r_{2},\ldots,r_{n})$ of a nonzero quadratic residue
$r_{0}$ modulo $p$ and $r_{1},r_{2},\ldots,r_{n}\in\mathbb{Z}/p\mathbb{Z}$
such that $\sum_{i=1}^{n}r_{i}\equiv 0\;(\bmod\;p)$. The player $P_{i}$
holding $x_{i}\in\\{0,1\\}$ computes a message
$m_{i}\in\mathbb{Z}/p\mathbb{Z}$ as
$m_{i}:=2^{i-1}r_{0}x_{i}+r_{i}\;(\bmod\;p)$ if $2\leq i\leq n$ and
$m_{1}:=r_{0}(a+x_{1})+r_{1}\;(\bmod\;p)$ if $i=1$. Given
$m_{1},m_{2},\ldots,m_{n}$, the referee computes the quadratic residuosity of
$m:=\sum_{i=1}^{n}m_{i}\;(\bmod\;p)$, and outputs $1$ if $m$ is a quadratic
residue and $0$ otherwise.

###  1.2 Our Contributions

First, we introduce the notions of _quadratic residue based PSM (QR-PSM)
protocols_ and _linear QR-PSM (LQR-PSM) protocols_. Let $p$ be a prime. A QR-
PSM protocol modulo $p$ is a PSM protocol such that the decoding function of
the protocol outputs the quadratic residuosity (Legendre symbol) of
$\phi(m_{1},m_{2},\ldots,m_{n})$ modulo $p$, where $\phi$ is a function from
messages to $\mathbb{Z}/p\mathbb{Z}$, and $m_{i}$ is the $i$-th message for
$1\leq i\leq n$. An LQR-PSM protocol modulo $p$ is a QR-PSM protocol modulo
$p$ such that
$\phi(m_{1},m_{2},\ldots,m_{n})=\sum_{i=1}^{n}m_{i}\;(\bmod\;p)$. We remark
that Feige-Kilian-Naor’s protocol and Ishai’s protocol are LQR-PSM protocols.

Next, we construct new QR-PSM and LQR-PSM protocols. For any symmetric
function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, we obtain an LQR-PSM protocol
of communication complexity $O(n^{2})$. We note that it is the most efficient
PSM protocol for symmetric functions so far since the previously known best
protocol was of $O(n^{2}\log n)$ proposed by Beimel, Gabizon, Ishai,
Kushilevitz, Meldgaard, and Paskin-Cherniavsky [7]. For any weighted threshold
function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ with weight vector $\bm{w}$ and
threshold $t$, we also obtain an LQR-PSM protocol of communication complexity
$O(n\cdot\sum_{i=1}^{n}|w_{i}|)$. We remark that these protocols are more
efficient than the protocols obtained by applying Ishai’s protocol to these
specific functions (see Table 1 for efficiency comparison). In addition, we
show that QR-PSM protocols can be obtained from decomposable randomized
encodings (DRE). In particular, we show that if a function $f$ is “embedded”
into another function $g$ and $g$ admits a DRE of output length $s$, we have a
QR-PSM protocol with communication complexity $O(s\cdot l(g))$, where $l(g)$
is the “embedding length” of $g$ (see Section 3.2 for the definition of the
embedding). This construction can be viewed as a generalization of our LQR-PSM
protocols since it admits not only linear polynomials but also higher-degree
polynomials.

In QR-PSM protocols, the communication complexity is dominated by the size of
modulus $p$. Thus, it is important to give upper and lower bounds on the
primes. We study two kinds of primes which we name the _Peralta primes_ and
the _LQR-PSM primes_ : the $n$-th Peralta prime $P_{n}$ is the smallest prime
$p$ such that every $n$-bit string appears in the “quadratic residue sequence
modulo $p$” as a subsequence; and the $n$-th LQR-PSM prime $L_{n}$ is the
smallest prime $p$ such that every function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ has an LQR-PSM protocol modulo $p$. We
first show that $L_{n}\leq P_{2^{n-1}}$ and $L_{n}\geq 2^{\frac{2^{n}-2}{n}}$.
Since it holds $P_{n}\leq(1+\sqrt{2})^{2}n^{2}2^{2n-2}$ for sufficiently large
$n$ from the result by Peralta [21], we have upper and lower bounds on the
LQR-PSM primes. We also show a slightly better upper bound on the Peralta
primes by using graph theory. In particular, we have
$P_{n}\leq(1+o(1))n^{2}2^{2n-2}$, which improves the Peralta’s result by a
constant factor $(1+\sqrt{2})^{2}$.

Table 1: The communication complexity of QR-PSM protocols (see Section 3.2 for the notations) | function | communication complexity
---|---|---
Ishai [19] | any function | $O(n\cdot 2^{n})$
Corollary 3.4 | symmetric function | $O(n^{2})$
Corollary 3.5 | weighted threshold function with weight vector $\bm{w}$ | $O(n\cdot\sum_{i=1}^{n}|w_{i}|)$

###  1.3 Related Work

The PSM model was firstly introduced by Feige, Kilian, and Naor [17]. Besides
the QR-PSM protocol described in Section 1.1.1, they also constructed a two-
player PSM protocol for any function
$f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ of complexity
$O(2^{n})$. Beimel, Ishai, Kumaresan, and Kushilevitz [8] improved it to
$O(2^{n/2})$ by introducing a decomposable private information retrieval
protocol. This is still the state-of-the-art two-player PSM protocol among
those applicable to arbitrary function
$f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. As an impossibility
result, Applebaum, Holenstein, Mishra, and Shayevitz [4] showed that any two-
player PSM protocol computing a random function
$f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ requires the
complexity $3n-O(\log n)$. Narrowing this exponential gap between the upper
and lower bounds is an important open problem in cryptography [23].

For the case of $k$ players for $k\geq 3$, Beimel, Kushilevitz, and Nissim [9]
constructed a $k$-player PSM protocol for any function
$f:(\\{0,1\\}^{n})^{k}\rightarrow\\{0,1\\}$ of complexity $O(poly(k)\cdot
2^{nk/2})$. Assouline and Liu [5] improved it to $O(2^{n(k-1)/2})$ for
infinitely many $k$’s and conjectured that it holds for any $k$.

For a specific class of functions, Ishai and Kushilevitz [20] constructed a
PSM protocol for a Boolean modulo-$p$ branching program
$BP:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ of size $a$ with communication
complexity $O(\log p\cdot n\cdot a^{2})$.

##  2 Preliminaries

###  2.1 Notations

For an integer $n\geq 2$, we denote $[n]:=\\{1,2,\ldots,n\\}$ and
$\mathbb{Z}_{n}:=\mathbb{Z}/n\mathbb{Z}$. For a set $S$, we denote by $\\#S$
the cardinality of $S$. For a bit string $m\in\\{0,1\\}^{*}$, we denote by
$|m|$ the bit length of $m$. For an integer $a\in\mathbb{Z}$, we denote by
$|a|$ the absolute value of $a$.

Let $A$ be a ring. An _arithmetic formula_ over $A$ is a rooted binary tree,
where each leaf is labeled by either an input variable $x_{i}$ ($1\leq i\leq
n$) or a constant $c\in A$, and each intermediate node called a _gate_ is
labeled by either addition or multiplication. Its _depth_ is defined by the
length of the longest path from the root to a leaf. An arithmetic formula can
be regarded as a function $f:A^{n}\rightarrow A$ naturally. A _Boolean
formula_ is an arithmetic formula over $A=\mathbb{Z}_{2}$. In this paper, the
basis of Boolean formulas is always $\\{\wedge,\oplus\\}$.

A _polynomial_ over $A$ is a polynomial whose coefficients are elements of
$A$. A polynomial can be regarded as a function $f:A^{n}\rightarrow A$
naturally. Every arithmetic formula over $A$ can be represented by a
polynomial over $A$. In particular, every Boolean formula
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ can be represented by a polynomial over
$\mathbb{Z}_{2}$ (over the basis $\\{\wedge,\oplus\\}$), which is called the
_Reed-Muller canonical form_ of $f$.

###  2.2 PSM Protocols

######  Definition 2.1 (PSM protocol).

Let $n\geq 2$ be an integer, and
$X_{1},X_{2},\ldots,X_{n},Y,R,M_{1},M_{2},\ldots,M_{n}$ finite sets. Set
$X=\prod_{1\leq i\leq n}X_{i}$ and $M=\prod_{1\leq i\leq n}M_{i}$. Let
$\mathsf{Enc}_{i}:X_{i}\times R\rightarrow M_{i}$ ($1\leq i\leq n$) and
$\mathsf{Dec}:M\rightarrow Y$ be functions. Here,
$X_{i},Y,R,M_{i},\mathsf{Enc}_{i},\mathsf{Dec}$ ($1\leq i\leq n$) are called
the _$i$ -th input space_, the _output space_ , the _randomness space_ , the
_$i$ -th message space_, the _$i$ -th encoding function_, and the _decoding
function_ , respectively. A _private simultaneous messages (PSM) protocol
$\Pi$_ for a function $f:X\rightarrow Y$ is a $7$-tuple

$\Pi=(n,X,Y,R,M,(\mathsf{Enc}_{i})_{1\leq i\leq n},\mathsf{Dec}),$

satisfying the following conditions:

Correctness.

For any $(x_{1},\ldots,x_{n})\in X$ and any $r\in R$, it holds that

$\mathsf{Dec}((\mathsf{Enc}_{1}(x_{1},r),\ldots,\mathsf{Enc}_{n}(x_{n},r))=f(x_{1},\ldots,x_{n}).$

Security.

For any $m\in M$ and
$x=(x_{1},\ldots,x_{n}),x^{\prime}=(x^{\prime}_{1},\ldots,x^{\prime}_{n})\in
X$ with $f(x)=f(x^{\prime})$, it holds that

$\Pr_{r\in
R}\bigl{[}(\mathsf{Enc}_{1}(x_{1},r),\ldots,\mathsf{Enc}_{n}(x_{n},r))=m\bigr{]}=\Pr_{r\in
R}\bigl{[}(\mathsf{Enc}_{1}(x^{\prime}_{1},r),\ldots,\mathsf{Enc}_{n}(x^{\prime}_{n},r))=m\bigr{]},$

where $r\in R$ is chosen uniformly at random.

The communication complexity is defined by $\sum_{i=1}^{n}\log_{2}(\\#M_{i})$
and the randomness complexity is defined by $\log_{2}(\\#R)$.

###  2.3 Decomposable Randomized Encodings

In this section, we define the notions of _randomized encodings_ and
_decomposable randomized encodings (DRE)_. A DRE over $\mathbb{Z}_{p}$ for a
prime $p$ is used as a building block for constructing QR-PSM protocols.

######  Definition 2.2 (Randomized encoding).

Let $X,Y,\hat{Y},R$ be finite sets, and $f:X\rightarrow Y$ a function. A
_randomized encoding_ $\hat{f}:X\times R\rightarrow\hat{Y}$ is a function
satisfying the following conditions:

Correctness.

There exists a function $\mathsf{Dec}:\hat{Y}\rightarrow Y$ called a _decoder_
such that for any $x\in X$ and $r\in R$, it holds
$\mathsf{Dec}(\hat{f}(x,r))=f(x)$.

Security.

For any $\hat{y}\in\hat{Y}$ and $x,x^{\prime}\in X$ such that
$f(x)=f(x^{\prime})$, it holds that

$\Pr_{r\in R}\bigl{[}\hat{f}(x,r)=\hat{y}\bigr{]}=\Pr_{r\in
R}\bigl{[}\hat{f}(x^{\prime},r)=\hat{y}\bigr{]},$

where $r\in R$ is chosen uniformly at random.

######  Definition 2.3 (DRE).

Let $A$ be a finite ring, and $f:A^{n}\rightarrow A$ a function. A
_decomposable randomized encoding (DRE)_ of $f$ is a randomized encoding
$\hat{f}:A^{n}\times A^{m}\rightarrow A^{s}$ as follows:

$\hat{f}((x_{1},x_{2},\ldots,x_{n}),r)=(\hat{f}_{0}(r),\hat{f}_{1}(x_{1},r),\hat{f}_{2}(x_{2},r),\ldots,\hat{f}_{n}(x_{n},r))$

where $\hat{f}_{0}:A^{m}\rightarrow A^{s_{0}}$ and $\hat{f}_{i}:A\times
A^{m}\rightarrow A^{s_{i}}$ ($1\leq i\leq n$) are functions such that
$\sum_{i=0}^{n}s_{i}=s$. The integer $s$ is called the _output length_ of the
DRE.

For a function $f:\mathbb{Z}^{n}\rightarrow\mathbb{Z}$, we define the _DRE
complexity_ of $f$.

######  Definition 2.4 (DRE complexity).

Let $f:\mathbb{Z}^{n}\rightarrow\mathbb{Z}$ be a function. For a prime $p$,
define $f_{p}:\mathbb{Z}_{p}^{n}\rightarrow\mathbb{Z}_{p}$ as the function
such that $f_{p}\equiv f\;(\bmod\;p)$. The _DRE complexity_ of $f$, denoted by
${\sf D}(f)$, is defined by the minimum integer $s$ such that for every prime
$p$, there exists a DRE of $f_{p}$ with output length at most $s$.

Based on Cleve’s result [14] on straight-line programs, Cramer, Fehr, Ishai,
and Kushilevitz designed a constant-round multiparty computation protocol for
arithmetic formulas [16, Theorem 3]. This construction can be viewed as a DRE
of arithmetic formulas.

######  Theorem 2.5 (Cramer-Fehr-Ishai-Kushilevitz [16]).

Let $f:A^{n}\rightarrow A$ be an arithmetic formula of depth $d$. Then, there
exists a DRE of $f$ with output length $2^{d+O(\sqrt{d})}$.

######  Corollary 2.6.

Let $f:\mathbb{Z}^{n}\rightarrow\mathbb{Z}$ be an arithmetic formula of depth
$d$. Then, we have ${\sf D}(f)\leq 2^{d+O(\sqrt{d})}$.

Based on Theorem 2.5, we have a DRE of polynomials.

######  Theorem 2.7.

Let $f:A^{n}\rightarrow A$ be a degree-$k$ polynomial having $m$ terms. Then,
there exists a DRE of $f$ with output length $m\cdot k\cdot 2^{O(\sqrt{\log
k})}$.

###### Proof.

Let $g:A^{k+1}\rightarrow A$ be a function such that
$g(y_{0},y_{1},\ldots,y_{k})=y_{0}+\prod_{i=1}^{k}y_{i}$. Since $g$ can be
represented by an arithmetic formula of depth $d=\lceil\log_{2}k\rceil+1$, it
has a DRE with output length $2^{d+O(\sqrt{d})}=k\cdot 2^{O(\sqrt{\log k})}$
from Theorem 2.5. Suppose that the $i$-th term of $f$ is a degree-$k^{\prime}$
term of the form $cx_{j_{1}}x_{j_{2}}\cdots x_{j_{k^{\prime}}}$ ($c\in A$,
$k^{\prime}\leq k$). Let $r_{1},r_{2},\ldots,r_{m}\in A$ be random numbers
such that $\sum_{i=1}^{m}r_{i}=0$. Then, we have a DRE of
$cx_{j_{1}}x_{j_{2}}\cdots x_{j_{k^{\prime}}}+r_{i}$ from the DRE of $g$, by
setting

$(y_{0},y_{1},y_{2},\ldots,y_{k^{\prime}},y_{k^{\prime}+1},y_{k^{\prime}+2},\ldots,y_{k})\leftarrow(r_{i},cx_{j_{1}},x_{j_{2}},\ldots,x_{j_{k^{\prime}}},1,1,\ldots,1).$

Juxtaposing them for each term, we obtain the DRE of $f$ with output length
$m\cdot k\cdot 2^{O(\sqrt{\log k})}$. ∎

Let $f:A^{n}\rightarrow A$ be a degree-$k$ polynomial having $m$ terms. Since
$f$ can be represented by an arithmetic formula of depth
$d=\lceil\log_{2}k\rceil+\lceil\log_{2}m\rceil$, Theorem 2.5 results in a DRE
of $f$ with output length $2^{\log_{2}d+O(\sqrt{d})}=m\cdot k\cdot
2^{O(\sqrt{\log k+\log m})}$. On the other hand, Theorem 2.7 results in a DRE
of $f$ with output length $m\cdot k\cdot 2^{O(\sqrt{\log k})}$. Thus, Theorem
2.7 is more efficient than Theorem 2.5 by the factor $2^{O(\sqrt{\log m})}$ in
this case.

###  2.4 Quadratic Residues

We denote by $\mathcal{R}_{p}\subset\mathbb{Z}_{p}$ the set of non-zero
quadratic residues modulo $p$ and by $\mathcal{N}_{p}\subset\mathbb{Z}_{p}$
the set of quadratic nonresidues modulo $p$. For an integer $a\in\mathbb{Z}$,
the _Legendre symbol_ $(\frac{a}{p})$ is defined as follows:

$\left(\dfrac{a}{p}\right)=\begin{cases}1&\text{if $a\not\equiv 0\;(\bmod\;p)$
is a quadratic residue modulo $p$,}\\\ 0&\text{if $a\equiv 0\;(\bmod\;p)$,}\\\
-1&\text{if $a$ is a quadratic nonresidue modulo $p$.}\\\ \end{cases}$

For a prime $p$, we define _the quadratic residue sequence modulo $p$_ as the
string $\mathsf{S}_{p}\in\\{0,1\\}^{p-1}$ such that for every $i\in[p-1]$, the
$i$-th bit (from the left) of $\mathsf{S}_{p}$ is equal to $1$ if
$(\frac{i}{p})=1$ and $0$ otherwise. If a string $t\in\\{0,1\\}^{*}$ is a
substring of $\mathsf{S}_{p}$, then we say that _$\mathsf{S}_{p}$ contains
$t$_. The quadratic residue sequences modulo primes from $2$ to $19$ are shown
as follows:

$p$ | $\mathsf{S}_{p}$
---|---
$2$ | $1$
$3$ | $10$
$5$ | $1001$
$7$ | $110100$
$11$ | $1011100010$
$13$ | $101100001101$
$17$ | $1101000110001011$
$19$ | $100111101010000110$

By Weil’s character sum estimation over finite fields, Peralta [21] gave a
sufficient condition on primes for containing every $n$-bit string
$t\in\\{0,1\\}^{n}$.

######  Theorem 2.8 (Peralta [21]).

Let $p$ be a prime. If $p\cdot\left(\frac{1}{2}\right)^{n}>n(\sqrt{p}+3)$,
then $\mathsf{S}_{p}$ contains every $n$-bit string $t\in\\{0,1\\}^{n}$.

We say that a prime $p$ is _$n$ -Peralta_ if $\mathsf{S}_{p}$ contains every
$n$-bit string $t\in\\{0,1\\}^{n}$. We define _the $n$-th Peralta prime
$P_{n}$_ as the smallest $n$-Peralta prime. The $n$-th Peralta primes for
$1\leq n\leq 8$ obtained by computer experiments are shown as follows:

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---
$P_{n}$ | 3 | 7 | 11 | 37 | 67 | 181 | 367 | 1091

Applying the Baker-Harman-Pintz theorem on prime gaps in [6], we obtain the
following corollary.

######  Corollary 2.9.

For any sufficiently large $n$, there exists an $n$-Peralta prime $p$ with
$p\leq c+c^{0.525}$, where $c=(1+\sqrt{2})^{2}n^{2}2^{2n-2}$. Hence, $\log
P_{n}=O(n)$ holds.

###### Proof.

From Theorem 2.8, any prime $p$ satisfying

$\sqrt{p}>n2^{n-1}+\sqrt{n^{2}2^{2n-2}+3n2^{n}}$

is $n$-Peralta. As $\sqrt{2}n2^{n-1}>\sqrt{n^{2}2^{2n-2}+3n2^{n}}$ for all
$n\geq 3$, any prime $p$ satisfying

$\sqrt{p}>(1+\sqrt{2})n2^{n-1}$

is also $n$-Peralta. By the Baker-Harman-Pintz theorem on prime gaps, there
exists a prime $p$ in $[c,c+c^{0.525}]$ for $c=(1+\sqrt{2})^{2}n^{2}2^{2n-2}$,
as desired. ∎

In Section 4.3, we improve the upper bound on Peralta primes by a constant
factor $(1+\sqrt{2})^{2}$.

##  3 QR-PSM Protocols

###  3.1 Definition of QR-PSM Protocols

We define quadratic residue based PSM protocols. It is a PSM protocol whose
decoding function outputs the Legendre symbol of what is computed from
messages.

######  Definition 3.1 (QR-PSM protocol).

Let $\Pi=(n,X,Y,R,M,(\mathsf{Enc}_{i})_{1\leq i\leq n},\mathsf{Dec})$ be a PSM
protocol such that $Y=\\{-1,0,1\\}$. Let $p$ be a prime. We say that $\Pi$ is
a _quadratic residue based PSM (QR-PSM) protocol modulo $p$_ if there exists a
function $\phi:M\rightarrow\mathbb{Z}_{p}$ such that for any
$(m_{1},\ldots,m_{n})\in M$,

$\mathsf{Dec}(m_{1},m_{2},\ldots,m_{n})=\left(\dfrac{\phi(m_{1},m_{2},\ldots,m_{n})}{p}\right).$

We remark that Feige-Kilian-Naor’s protocol (see Section 1.1.1) is a QR-PSM
protocol modulo $7$. We also point out that Ishai’s protocol (see Section
1.1.2) is a QR-PSM protocol modulo a prime $p$.

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a Boolean function. We say that a
QR-PSM protocol computes $f$ if it outputs $(-1)^{f(x)}$. Throughout this
paper, we focus on the QR-PSM protocols for Boolean functions in this sense.

###  3.2 LQR-PSM Protocols

We say that a function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is _embedded_
into a function $g:\mathbb{Z}^{n}\rightarrow\mathbb{Z}$ if
$g(x)=g(x^{\prime})$ implies $f(x)=f(x^{\prime})$ for any
$x,x^{\prime}\in\\{0,1\\}^{n}$. The function $g$ is called an _embedding of
$f$_. The _embedding length_ of $g$, denoted by $l(g)$, is defined as follows:

$l(g):=\max_{x\in\\{0,1\\}^{n}}(g(x))-\min_{x\in\\{0,1\\}^{n}}(g(x))+1.$

If a function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ can be embedded into a
linear function $g=a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n}$, we obtain an
efficient QR-PSM protocol which we call a _linear QR-PSM (LQR-PSM) protocol_.

######  Definition 3.2 (Linear QR-PSM protocol).

Let $p$ be a prime and $a_{0},a_{1},a_{2},\ldots,a_{n}\in\mathbb{Z}_{p}$. _A
linear QR-PSM (LQR-PSM) protocol modulo $p$_, denoted by
$[a_{0},a_{1},a_{2},\ldots,a_{n}]_{p}$, is a QR-PSM protocol
$\Pi=(n,\\{0,1\\}^{n},\\{-1,0,1\\},R,\mathbb{Z}_{p}^{n},(\mathsf{Enc}_{i})_{1\leq
i\leq n},\mathsf{Dec})$ modulo $p$ in the following.

  * •

The randomness space $R$ is

$R=\left\\{(r_{0},r_{1},r_{2},\ldots,r_{n})\in\mathbb{Z}_{p}^{n+1}\;\middle|\;r_{0}\in\mathcal{R}_{p},~{}\sum_{i=1}^{n}r_{i}\equiv
0\;(\bmod\;p)\right\\}.$

  * •

The encoding function $\mathsf{Enc}_{i}:\\{0,1\\}\times
R\rightarrow\mathbb{Z}_{p}$ is

$\mathsf{Enc}_{i}(x_{i},r)=\begin{cases}r_{0}(a_{0}+a_{i}x_{i})+r_{i}\;(\bmod\;p)&\text{if
$i=1$},{}\\\ r_{0}a_{i}x_{i}+r_{i}\;(\bmod\;p)&\text{otherwise},\end{cases}$

where $r=(r_{0},r_{1},r_{2},\ldots,r_{n})\in R$ and $x_{i}\in\\{0,1\\}$.

  * •

The decoding function
$\mathsf{Dec}:(\mathbb{Z}_{p})^{n}\rightarrow\\{-1,0,1\\}$ is

$\mathsf{Dec}(m_{1},m_{2},\ldots,m_{n})=\left(\dfrac{\sum_{i=1}^{n}m_{i}}{p}\right).$

######  Theorem 3.3.

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a function. Let
$g:\mathbb{Z}^{n}\rightarrow\mathbb{Z}$ be an embedding of $f$ such that
$g=a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n}$ for some
$a_{1},a_{2},\ldots,a_{n}\in\mathbb{Z}$. Then, there exists an LQR-PSM
protocol for $f$ with communication complexity $n\cdot\log_{2}P_{l(g)}$, where
$P_{l(g)}$ is the $l(g)$-th Peralta prime.

###### Proof.

Set $p:=P_{l(g)}$. Since $p$ is the $l(g)$-th Peralta prime, there exists
$a_{0}\in\mathbb{Z}_{p}$ such that
$\left(\dfrac{a_{0}+g(x)}{p}\right)=(-1)^{f(x)}$ for all $x\in\\{0,1\\}^{n}$.
We claim that $[a_{0},a_{1},a_{2},\ldots,a_{n}]_{p}$ is an LQR-PSM protocol
for $f$. By setting $m_{i}:=\mathsf{Enc}_{i}(x_{i},r)$, we have

$(m_{1},m_{2},\ldots,m_{n})=(r_{0}(a_{0}+a_{1}x_{1})+r_{1},r_{0}a_{2}x_{2}+r_{2},\ldots,r_{0}a_{n}x_{n}+r_{n}).$

Since $r_{0}$ is a nonzero quadratic residue, we have

$\left(\dfrac{\sum_{i=1}^{n}m_{i}}{p}\right)=\left(\dfrac{r_{0}(a_{0}+a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n})}{p}\right)=\left(\dfrac{r_{0}(a_{0}+g(x))}{p}\right)=\left(\dfrac{a_{0}+g(x)}{p}\right).$

Thus, it correctly computes $f$. The communication complexity of the protocol
is $n\cdot\log_{2}P_{l(g)}$. ∎

Theorem 3.3 implies a protocol for any symmetric function.

######  Corollary 3.4.

For any symmetric function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, there exists
an LQR-PSM protocol with communication complexity
$n\cdot\log_{2}P_{n+1}=O(n^{2})$.

###### Proof.

It follows from Theorem 3.3 since any symmetric function is embedded to a
linear function $g(x_{1},x_{2},\ldots,x_{n})=x_{1}+x_{2}+\cdots+x_{n}$ of
embedding length $n+1$. ∎

_A weighted threshold function $f_{\bm{w},t}$ associated with
$\bm{w}=(w_{1},w_{2},\ldots,w_{n})\in\mathbb{Z}^{n}$ and $t\in\mathbb{N}$_ is
defined as

$f_{\bm{w},t}(x_{1},x_{2},\ldots,x_{n})=\begin{cases}1&\text{if
$\sum_{i=1}^{n}w_{i}x_{i}\geq t$,}\\\ 0&\text{otherwise.}\end{cases}$

######  Corollary 3.5.

For any $\bm{w}\in\mathbb{Z}^{n}$ and $t\in\mathbb{N}$, there exists an LQR-
PSM protocol for the weighted threshold function
$f_{\bm{w},t}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ associated with $\bm{w},t$
with communication complexity $n\cdot\log_{2}P_{W+1}=O(n\cdot W)$ for
$W=\sum_{i=1}^{n}|w_{i}|$.

###### Proof.

It follows from Theorem 3.3 since a weighted threshold function associated
with $\bm{w},t$ is embedded to a linear function
$g(x_{1},x_{2},\ldots,x_{n})=w_{1}x_{1}+w_{2}x_{2}+\cdots+w_{n}x_{n}$ of
embedding length $\sum_{i=1}^{n}|w_{i}|+1$. ∎

Theorem 3.3 also implies Ishai’s protocol (see Subsection 1.1.2).

######  Corollary 3.6 (Ishai [19]).

For any function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, there exists an LQR-
PSM protocol with communication complexity $n\cdot\log_{2}P_{2^{n}}=O(n\cdot
2^{n})$.

###### Proof.

It follows from Theorem 3.3 since any function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is embedded to a linear function
$g(x_{1},x_{2},\ldots,x_{n})=x_{1}+2x_{2}+\cdots
2^{i-1}x_{i}+\cdots+2^{n-1}x_{n}$ of embedding length $2^{n}$. ∎

We also obtain an LQR-PSM protocol for a composition of symmetric functions.

######  Corollary 3.7.

Let $h:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ be any function and
$g_{i}:\\{0,1\\}^{k}\rightarrow\\{0,1\\}$ ($1\leq i\leq m$) be symmetric
functions. Set $n=mk$. Define a function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
as follows:

$f(x_{1},x_{2},\ldots,x_{n})=h(g_{1}(x_{1},\ldots,x_{k}),g_{2}(x_{k+1},\ldots,x_{2k}),\ldots,g_{m}(x_{n-k+1},\ldots,x_{n})).$

Then, there exists an LQR-PSM protocol for $f$ with communication complexity
$n\cdot\log_{2}P_{L}=O(n\cdot L)$ for $L=(k+1)^{n/k}$.

###### Proof.

We can observe that the function $f$ can be embedded to a linear function
$g:\mathbb{Z}^{n}\rightarrow\mathbb{Z}$ in the following:

$g(x_{1},x_{2},\ldots,x_{n})=\sum_{i=1}^{k}x_{i}+\sum_{i=k+1}^{2k}(k+1)x_{i}+\sum_{i=2k+1}^{3k}(k+1)^{2}x_{i}+\cdots+\sum_{i=(m-1)k+1}^{mk}(k+1)^{m-1}x_{i}.$

We have

$l(g)=1+k+(k+1)k+(k+1)^{2}k+\cdots+(k+1)^{m-1}k=(k+1)^{n/k}.$

From Theorem 3.3, we have an LQR-PSM protocol with communication complexity
$n\cdot\log_{2}P_{L}=O(n\cdot L)$ for $L=(k+1)^{n/k}$. ∎

######  Remark 3.8.

By setting $(m,k)=(1,n)$, we obtain Corollary 3.4. By setting $(m,k)=(n,1)$,
we obtain Corollary 3.6. In this sense, Corollary 3.7 is a generalization of
Corollaries 3.4 and 3.6.

By computer experiment, we search LQR-PSM protocols for several symmetric
functions with minimum communication complexity in Table 2: AND is the logical
AND function, XOR is the logical exclusive OR function, EQ is a function that
outputs $1$ if and only if all bits are equal, and MAJ is a function which
outputs $1$ if and only if half or more bits are $1$. Note that these
protocols are more efficient than those of Corollary 3.4.

Table 2: The list of LQR-PSM protocols for AND, XOR, EQ, and MAJ. $n$ | AND | XOR | EQ | MAJ
---|---|---|---|---
$2$ | $[2,1,1]_{5}$ | $[2,2,4]_{5}$ | $[1,1,2]_{5}$ | $[2,2,2]_{5}$
$3$ | $[6,1,1,1]_{11}$ | $[6,3,3,3]_{7}$ | $[1,1,1,1]_{5}$ | $[3,3,3,2]_{7}$
$4$ | $[5,1,1,1,1]_{13}$ | $[12,1,1,1,7]_{17}$ | $[5,1,1,1,1]_{11}$ | $[6,2,2,2,2]_{11}$
$5$ | $[11,1,1,1,1,1]_{41}$ | $[14,2,2,2,2,2]_{19}$ | $[4,1,1,1,1,1]_{13}$ | $[6,2,2,2,2,2]_{11}$
$6$ | $[18,1,1,1,1,1,1]_{53}$ | $[15,1,1,1,1,1,6]_{41}$ | $[10,1,1,1,1,1,1]_{41}$ | $[21,3,3,3,3,3,3]_{31}$
$7$ | $[52,1,1,1,1,1,1,1]_{83}$ | $[35,1,1,1,1,1,1,1]_{79}$ | $[17,1,1,1,1,1,1,1]_{53}$ | $[21,3,3,3,3,3,3,2]_{31}$

###  3.3 QR-PSM Protocols from DREs

In this subsection, we construct QR-PSM protocols from DREs.

######  Theorem 3.9.

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a function, and
$g:\mathbb{Z}^{n}\rightarrow\mathbb{Z}$ an embedding of $f$. Let
$h:\mathbb{Z}^{n+2}\rightarrow\mathbb{Z}$ be a function such that
$h(x_{1},x_{2},\ldots,x_{n+2}):=(g(x_{1},x_{2},\ldots,x_{n})+x_{n+1})\cdot
x_{n+2}$. Then, there exists a QR-PSM protocol computing $f$ with
communication complexity $O({\sf D}(h)\cdot l(g))$.

###### Proof.

From Theorem 2.8 and Corollary 2.9, there exists a prime $p$ with
$\log_{2}p=O(l(g))$ containing every $l(g)$-bit string. Since
$g(x)=g(x^{\prime})$ implies $f(x)=f(x^{\prime})$, we can take an offset
$a_{0}\in\mathbb{Z}_{p}$ such that
$\left(\dfrac{a_{0}+g(x)}{p}\right)=(-1)^{f(x)}$ for all $x\in\\{0,1\\}^{n}$.

From the assumption of the statement, there exists a DRE of
$h=(g+x_{n+1})\cdot x_{n+2}$ with output length ${\sf D}(h)$. Set $s:={\sf
D}(h)$. Let
$\hat{h}:\mathbb{Z}_{p}^{n+2}\times\mathbb{Z}_{p}^{m}\rightarrow\mathbb{Z}_{p}^{s}$
be the DRE of $h=(g+x_{n+1})\cdot x_{n+2}$ with output complexity $s$. It has
the following form:

$\hat{h}((x_{1},x_{2},\ldots,x_{n+2}),r)=(\hat{h}_{0}(r),\hat{h}_{1}(x_{1},r),\hat{h}_{2}(x_{2},r),\ldots,\hat{h}_{n+2}(x_{n+2},r))$

where $\hat{h}_{0}:\mathbb{Z}_{p}^{m}\rightarrow\mathbb{Z}_{p}^{s_{0}}$ and
$\hat{h}_{i}:\mathbb{Z}_{p}\times\mathbb{Z}_{p}^{m}\rightarrow\mathbb{Z}_{p}^{s_{i}}$
($1\leq i\leq n+2$) are functions such that $\sum_{i=0}^{n+2}s_{i}=s$. Let
${\sf dec}:\mathbb{Z}_{p}^{s}\rightarrow\mathbb{Z}_{p}$ be the decryption
function of the DRE.

The QR-PSM protocol
$\Pi=(n,\\{0,1\\}^{n},\\{-1,0,1\\},R,M,(\mathsf{Enc}_{i})_{1\leq i\leq
n},\mathsf{Dec})$ modulo $p$ is defined as follows:

  * •

$M_{1}=\mathbb{Z}_{p}^{s_{0}+s_{1}+s_{n+1}+s_{n+2}}$ and
$M_{i}=\mathbb{Z}_{p}^{s_{i}}$ for all $2\leq i\leq n$.

  * •

$R=\mathbb{Z}_{p}^{m}\times\mathcal{R}_{p}$. (Recall that $\mathcal{R}_{p}$ is
the set of nonzero quadratic residues modulo $p$).

  * •

$\mathsf{Enc}_{1}(x_{1},(r,r^{\prime}))=(\hat{h}_{0}(r),\hat{h}_{1}(r^{\prime}\cdot
x_{1},r),\hat{h}_{n+1}(a_{0},r),\hat{h}_{n+2}(r^{\prime},r))$ and
$\mathsf{Enc}_{i}(x_{i},(r,r^{\prime}))=\hat{h}_{i}(x_{i},r)$ for $2\leq i\leq
n$, where $r\in\mathbb{Z}_{p}^{m}$ and $r^{\prime}\in\mathcal{R}_{p}$.

  * •

$\mathsf{Dec}(m_{1},m_{2},\ldots,m_{n})=\left(\dfrac{{\sf
dec}(m_{1},m_{2},\ldots,m_{n})}{p}\right)$.

The correctness of the protocol follows from the correctness of the DRE, i.e.,
${\sf dec}(m_{1},m_{2},\ldots,m_{n})=(g(x)+a_{0})\cdot r^{\prime}$. The
security of the protocol follows from the security of the DRE $\hat{h}$
directly. The communication complexity of the protocol is $s\log_{2}p=O({\sf
D}(h)\cdot l(g))$. ∎

######  Corollary 3.10.

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a function which is embedded into
a degree-$d$ polynomial $g:\mathbb{Z}^{n}\rightarrow\mathbb{Z}$ having $m$
terms. Then, there exists a QR-PSM protocol computing $f$ with communication
complexity $m^{2}\cdot d\cdot 2^{O(\sqrt{\log d})}$.

###### Proof.

Let $h:\mathbb{Z}^{n+2}\rightarrow\mathbb{Z}$ be a function defined by
$h:=(g+x_{n+1})\cdot x_{n+2}$. By expanding the formula, $h$ can be regarded
as a degree-$(d+1)$ polynomial having $m+1$ terms. From Theorem 2.7, we have a
DRE of $h$ with output length $m\cdot d\cdot 2^{O(\sqrt{\log d})}$. From
Theorem 3.9, we have a QR-PSM protocol computing $f$ with communication
complexity $O({\sf D}(h)\cdot l(g))=m^{2}\cdot d\cdot 2^{O(\sqrt{\log d})}$
since the embedding length of $g$ is $l(g)=m+1$. ∎

##  4 Upper Bound on Primes for QR-PSM Protocols

###  4.1 LQR-PSM Primes

We define _the $n$-th linear QR-PSM (LQR-PSM) prime $L_{n}$_ as the smallest
prime $p$ such that for any function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$,
there exists a linear QR-PSM protocol modulo $p$ computing $f$. The $n$-th
LQR-PSM prime for $1\leq n\leq 4$ are: $L_{1}=3,L_{2}=7,L_{3}=11$, and
$L_{4}=37$. Although $P_{i}=L_{i}$ for $1\leq n\leq 4$, it does not hold in
general. Indeed, from Theorem 4.2 and Corollary 2.9, we have $L_{n}>P_{n}$ for
sufficiently large $n$.

An LQR-PSM prime is upper bounded by a Peralta prime. A trivial bound is
$L_{n}\leq P_{2^{n}}$ since the length of the truth table is $2^{n}$. The
following lemma gives a somewhat non-trivial bound on LQR-PSM primes.

######  Lemma 4.1.

We have $L_{n}\leq P_{2^{n-1}}$.

###### Proof.

Set $p=P_{2^{n-1}}$. Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be any
function. For a bit $b\in\\{0,1\\}$, let
$f_{b}:\\{0,1\\}^{n-1}\rightarrow\\{0,1\\}$ be a function such that
$f_{b}(x_{1},x_{2},\ldots,x_{n-1})=f(x_{1},x_{2},\ldots,x_{n-1},b)$, and
$t_{b}\in\\{0,1\\}^{2^{n-1}}$ a string such that the $i$-th bit ($0\leq
i<2^{n-1}$) of $t_{b}$ is $f_{b}(i_{1},i_{2},\ldots,i_{n-1})$ if
$i=\sum_{j=1}^{n-1}2^{j-1}i_{j}$, i.e., $t_{b}$ is the truth table of $f_{b}$.
From the property of Peralta prime, $\mathsf{S}_{p}$ contains both $t_{0}$ and
$t_{1}$. Let $b_{0},b_{1}\in\mathbb{Z}_{p}$ be the offset of the truth tables
$t_{0},t_{1}$, i.e., $t_{0}$ (resp. $t_{1}$) starts at the $b_{0}$-th (resp.
the $b_{1}$-th) bit of $\mathsf{S}_{p}$. Without loss of generality, we can
assume $b_{0}\leq b_{1}$. Now we have a LQR-PSM protocol
$[a_{0},a_{1},a_{2},\ldots,a_{n}]_{p}$ computing $f$, where $a_{0}=b_{0}$,
$a_{i}=2^{n-1-i}$ for $1\leq i\leq n-1$, and $a_{n}=b_{1}-b_{0}$. Therefore,
we have $L_{n}\leq P_{2^{n-1}}$. ∎

We obtain a lower bound on LQR-PSM primes via counting the number of LQR-PSM
protocols.

######  Theorem 4.2.

We have $L_{n}\geq 2^{\frac{2^{n}-2}{n}}$.

###### Proof.

We say that two protocols $[a_{0},a_{1},\ldots,a_{n}]_{p}$ and
$[b_{0},b_{1},\ldots,b_{n}]_{p}$ are _conjugate_ if there exists a quadratic
residue $s\in\mathcal{R}_{p}$ such that $b_{i}=sa_{i}$ for $0\leq i\leq n$.
Note that if two protocols are conjugate, they compute the same function.
Since the number of $n$-variable Boolean functions $2^{2^{n}}$ is a lower
bound on the number of protocols $\frac{2p^{n+1}}{p-1}$ (up to conjugate), we
have $\frac{2p^{n+1}}{p-1}\geq 2^{2^{n}}$. Since it holds
$4\geq\frac{2p}{p-1}$ for every prime $p$, we have $4p^{n}\geq 2^{2^{n}}$.
Taking logarithms, we have $p\geq 2^{\frac{2^{n}-2}{n}}$. ∎

###  4.2 Paley Graphs and Paley Tournaments

We introduce Paley graphs and Paley tournaments, which play important roles in
many areas, such as graph theory and additive combinatorics. In this paper, a
graph is an undirected graph without multiple edges and loops, and a
tournament is an oriented complete graph.

######  Definition 4.3 (Paley graph).

Let $p\equiv 1\pmod{4}$ be a prime. Then, the Paley graph $G_{p}$ with $p$
vertices is a graph with vertex set $\mathbb{Z}_{p}$ in which two distinct
vertices $x$ and $y$ are adjacent if and only if $x-y\in\mathcal{R}_{p}$.

Note that the adjacency of $x,y$ is independent of the order of $x,y$ since
$(\frac{-1}{p})=1$, which follows from the assumption of $p$.

######  Definition 4.4 (Paley tournament).

Let $p\equiv 3\pmod{4}$ be a prime. Then, the Paley tournament $T_{p}$ with
$p$ vertices is a tournament with vertex set $\mathbb{Z}_{p}$ in which for two
distinct vertices $x$ and $y$, there is a directed edge from $x$ to $y$ if and
only if $x-y\in\mathcal{R}_{p}$.

Note that the Paley tournament is a tournament, i.e., every distinct vertex
$x,y$ have either a directed edge from $x$ to $y$ or a directed edge from $y$
to $x$ since $(\frac{-1}{p})=-1$ holds, which follows from the assumption of
$p$.

Figure 2 shows Paley graph $G_{17}$ and Figure 2 shows Paley tournament
$T_{7}$ as examples.

Figure 1: $G_{17}$

Figure 2: $T_{7}$

Paley graph (tournament) is known as a typical example of graphs (tournaments)
satisfying various “random-like” properties, which means properties that
random graphs (tournaments) realize with high probability [1, Chapter 9], [12,
22].

The following property is one of such random-like properties.

######  Definition 4.5.

Let $n\geq 1$ be an integer. Then, a graph $G$ with vertex set
$\mathbb{Z}_{p}$ is said to have the property $(*)_{n}$ if for any set $S$ of
$n$ consecutive elements of $\mathbb{Z}_{p}$ and any pair of disjoint
(possibly empty) sets of elements, say $A$ and $B$, with $A\cup B=S$, there
exists a vertex $z_{A,B}\notin S$ such that $z_{A,B}$ is adjacent to all
vertices in $A$, but none in $B$. Similarly, a tournament $T$ with vertex set
$\mathbb{Z}_{p}$ is said to have the property $(*)_{n}$ if for any set $S$ of
$n$ consecutive elements of $\mathbb{Z}_{p}$ and any pair of disjoint
(possibly empty) sets of elements $A$ and $B$ with $A\cup B=S$, there exists a
vertex $z_{A,B}\notin S$ such that for every vertex $a\in A$ and $b\in B$,
there exist an edge from $z_{A,B}$ to $a$ and an edge from $b$ to $z_{A,B}$.

######  Remark 4.6.

The property $(*)_{n}$ is a weaker version of the $n$-existentially closed
($n$-e.c.) property which is known as a finite-analogue of the axiom of the
countable random graph (a.k.a. the Rado graph, see, e.g., [13]). The details
of the $n$-e.c. property and its application to constructing circulant almost
orthogonal arrays can be found in [12] and [24].

###  4.3 Upper Bound on Peralta Primes

The following theorem establishes a connection between Paley graphs,
tournaments and Peralta primes. The fundamental idea to prove this theorem can
be found in [24].

######  Theorem 4.7.

Let $n\geq 1$ be an integer and $p>n$ denote an odd prime. When $p\equiv
1\pmod{4}$, $p$ is $n$-Peralta if and only if $G_{p}$ has the property
$(*)_{n}$. Similarly, when $p\equiv 3\pmod{4}$, $p$ is $n$-Peralta if and only
if $T_{p}$ has the property $(*)_{n}$.

###### Proof.

Let $n\geq 1$ and assume that $p\equiv 1\pmod{4}$ is a prime with $p>n$; the
discussion below works for the case of a prime $p\equiv 3\pmod{4}$ as well.
Suppose that the Paley graph $G_{p}$ has the property $(*)_{n}$. Let
$t:=(t_{1},t_{2},\ldots,t_{n})\in\\{0,1\\}^{n}$ be an arbitrarily given
sequence. Set $A:=\\{i\in\\{1,2,\ldots,n\\}\mid t_{i}=1\\}$ and
$B:=\\{i\in\\{1,2,\ldots,n\\}\mid t_{i}=0\\}$. Notice that $A\cup
B=\\{1,2,\ldots,n\\}$. Then, from the assumption of $G_{p}$, there exists some
$z=z_{A,B}\in\mathbb{Z}_{p}\setminus\\{1,2,\ldots,n\\}$ such that
$(\frac{i-z}{p})=1$ if and only if $i\in A$. Here notice that for any
$i\in\\{1,2,\ldots,n\\}$ we have $(\frac{i-z}{p})\neq 0$ since
$z\notin\\{1,2,\ldots,n\\}$. Now consider the sequence

$\mathsf{S}_{z}:=\biggl{(}\frac{1}{2}+\frac{1}{2}\left(\dfrac{1-z}{p}\right),\frac{1}{2}+\frac{1}{2}\left(\dfrac{2-z}{p}\right),\ldots,\frac{1}{2}+\frac{1}{2}\left(\dfrac{n-z}{p}\right)\biggr{)}.$

Since $z\notin\\{1,2,\ldots,n\\}$, $\mathsf{S}_{z}$ forms a consecutive
subsequence of $\mathsf{S}_{p}$, and we now have $\mathsf{S}_{z}=t$.
Conversely if $p$ is an $n$-peralta prime, then $\mathsf{S}_{p}$ contains any
sequence $t\in\\{0,1\\}^{n}$. Since the permutation $x\mapsto x+1$ on
$\mathbb{Z}_{p}$ is an automorphism of $G_{p}$, to prove that $G_{p}$ has the
property $(*)_{n}$, it suffices to check that there exists $z_{A,B}$ with
respect to the subsets $A,B$ defined above, which is obvious from the
assumption of $p$. ∎

Thus, we immediately obtain the following corollary.

######  Corollary 4.8.

For $n\geq 1$, let $m^{(G)}_{n}$ be the least prime $p\equiv 1\pmod{4}$ such
that $G_{p}$ has the property $(*)_{n}$, and similarly, $m^{(T)}_{n}$ denotes
the least prime $p\equiv 3\pmod{4}$ such that $T_{p}$ has the property
$(*)_{n}$. Set $m_{n}:=\min\\{m^{(G)}_{n},m^{(T)}_{n}\\}$. Then, we have
$P_{n}=m_{n}$.

Substantially, the following theorem was proved by Graham and Spencer [18],
Blass, Exoo and Harary [10], Bollobás and Thomason [11] in the context of
graph theory.

######  Theorem 4.9 ([10, 11, 18]).

For $n\geq 1$ and every prime $p>n^{2}2^{2n-2}$, both of $G_{p}$ and $T_{p}$
have the property $(*)_{n}$. In particular, $m_{n}>n^{2}2^{2n-2}$ for $n\geq
1$.

Furthermore, it was proved in [2, 3] that for an odd prime $p$, both of
$G_{p}$ and $T_{p}$ have the property $(*)_{n}$ if
$p>\\{(n-3)2^{n-1}+2\\}\sqrt{p}+(n+1)2^{n-1}-1$.

The following corollary is a direct consequence of Theorems 4.7, 4.9 and
Corollary 4.8, which improves Corollary 2.9 by a constant factor
$(1+\sqrt{2})^{2}\fallingdotseq 5.828$.

######  Corollary 4.10.

If an odd prime $p$ satisfies that $p>n^{2}2^{2n-2}$, then $p$ is $n$-Peralta.
As a consequence, we have $P_{n}<n^{2}2^{2n-2}$ for $n\geq 1$.

Applying the Baker-Harman-Pintz theorem on prime gaps in [6], we obtain the
following corollary.

######  Corollary 4.11.

For any sufficiently large $n$, there exists an $n$-Peralta prime $p$ with
$p\in[n^{2}2^{2n-2},n^{2}2^{2n-2}+(n^{2}2^{2n-2})^{0.525}]$, which means that
$p=(1+o(1))n^{2}2^{2n-2}$.

######  Remark 4.12.

A modification of the proof of [15, Theorem 4.1] shows that for each $n\geq 1$
there is a graph (and tournament) with vertex set $\mathbb{Z}_{p}$ such that
$p=O(n2^{n})$ satisfying the property $(*)_{n}$, where such a graph can be
constructed from random Cayley graphs over $\mathbb{Z}_{p}$. Since it is known
that the Paley graph $G_{p}$ has various properties that random Cayley graphs
over $\mathbb{Z}_{p}$ satisfy with high probability, we guess that in fact
$m_{n}=P_{n}=o(n^{2}2^{2n})$. Although at present there seems to be no known
direct approach toward this conjecture, it may be possible to obtain some
supporting evidences by considering the following “random” graph, for example.
Suppose that $p\equiv 1\pmod{4}$ is a prime and $1/2\leq q\leq 1$ is a real
number. Then the set $\mathcal{R}_{p}$ can be partitioned into two non-empty
sets $\mathcal{R}_{p}^{+}$ and $\mathcal{R}_{p}^{-}$ with same size such that
$\mathcal{R}_{p}^{-}=\\{-r\mid r\in\mathcal{R}_{p}^{+}\\}$. Then for each
$r\in\mathcal{R}_{p}^{+}$ choose a pair $\\{r,-r\\}$ independently with
probability $q$ and form the set $U_{p}\subseteq\mathcal{R}_{p}$ consisting of
all chosen quadratic residues in $\mathcal{R}_{p}^{+}$ and their additive
inverses in $\mathcal{R}_{p}^{-}$. Then construct a graph (denoted by
$G_{p}(q)$) with vertex set $\mathbb{Z}_{p}$ and connect two vertices $x$ and
$y$ if and only if $x-y\in U_{p}$. (A similar construction for primes $p\equiv
3\pmod{4}$ can be established as well.) Notice that $G_{p}(q)$ is a spanning
subgraph of $G_{p}$, and the “closer” $G_{p}(q)$ is to $G_{p}$, the closer $q$
is to $1$ (in particular $G_{p}(q)=G_{p}$ if $q=1$). We believe that for
$q=1-\varepsilon$ with any $\varepsilon>0$ the probability that $G_{p}(q)$
with $p=o(n^{2}2^{2n})$ has the property $(*)_{n}$ tends to $1$ (as
$n\to\infty$). At present it is possible to confirm this claim for $q<3/4$
which follows from a simple computation showing that the probability that
$G_{p}(q)$ does not have the property $(*)_{n}$ is at most
$2^{n}(1-(1-q)^{n})^{p-n}$, which however seems to be far from sharp
estimations.

## Acknowledgments

The first author was supported during this work by JSPS KAKENHI Grant Number
JP21K17702. The second author was supported during this work by JSPS KAKENHI
Grant Number JP20J20797. The third author was supported during this work by
JSPS KAKENHI Grant Number JP20J00469. The last author was supported during
this work by JSPS KAKENHI Grant Number JP19H01109, JST CREST Grant Number
JPMJCR2113, and JST AIP Acceleration Research JPMJCR22U5.

## References

  * [1] N. Alon and J. H. Spencer.  The Probabilistic Method.  John Wiley & Sons, 2016.
  * [2] W. Ananchuen and L. Caccetta.  On the adjacency properties of paley graphs.  Networks, 23(4):227–236, 1993.
  * [3] W. Ananchuen and L. Caccetta.  On tournaments with a prescribed property.  Ars Combinatoria, 36:89–96, 1993.
  * [4] B. Applebaum, T. Holenstein, M. Mishra, and O. Shayevitz.  The Communication Complexity of Private Simultaneous Messages, Revisited.  Journal of Cryptology, 33(3):917–953, 2020.
  * [5] L. Assouline and T. Liu.  Multi-party PSM, Revisited: - Improved Communication and Unbalanced Communication.  In K. Nissim and B. Waters, editors, Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part II, volume 13043 of Lecture Notes in Computer Science, pages 194–223. Springer, 2021.
  * [6] R. C. Baker, G. Harman, and J. Pintz.  The difference between consecutive primes, II.  Proceedings of the London Mathematical Society, 83(3):532–562, 2001\.
  * [7] A. Beimel, A. Gabizon, Y. Ishai, E. Kushilevitz, S. Meldgaard, and A. Paskin-Cherniavsky.  Non-Interactive Secure Multiparty Computation.  In J. A. Garay and R. Gennaro, editors, Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II, volume 8617 of Lecture Notes in Computer Science, pages 387–404. Springer, 2014.
  * [8] A. Beimel, Y. Ishai, R. Kumaresan, and E. Kushilevitz.  On the Cryptographic Complexity of the Worst Functions.  In Y. Lindell, editor, Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014\. Proceedings, volume 8349 of Lecture Notes in Computer Science, pages 317–342. Springer, 2014.
  * [9] A. Beimel, E. Kushilevitz, and P. Nissim.  The Complexity of Multiparty PSM Protocols and Related Models.  In J. B. Nielsen and V. Rijmen, editors, Advances in Cryptology \- EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, volume 10821 of Lecture Notes in Computer Science, pages 287–318. Springer, 2018.
  * [10] A. Blass, G. Exoo, and F. Harary.  Paley graphs satisfy all first-order adjacency axioms.  Journal of Graph Theory, 5(4):435–439, 1981.
  * [11] B. Bollobás and A. Thomason.  Graphs which Contain all Small Graphs.  European Journal of Combinatorics, 2(1):13–15, 1981.
  * [12] A. Bonato.  The search for $N$-e.c. graphs.  Contributions to Discrete Mathematics, 4(1), 2009.
  * [13] P. J. Cameron.  The Random Graph.  In R. L. Graham, J. Nesetril, and S. Butler, editors, The Mathematics of Paul Erdős II, pages 353–378. Springer, 2013.
  * [14] R. Cleve.  Towards Optimal Simulations of Formulas by Bounded-Width Programs.  In H. Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 271–277. ACM, 1990.
  * [15] A. Costea.  Computational and Theoretical Aspects of $N$-e.c. Graphs.  Master’s thesis, Wilfrid Laurier University, 2010.
  * [16] R. Cramer, S. Fehr, Y. Ishai, and E. Kushilevitz.  Efficient Multi-party Computation over Rings.  In E. Biham, editor, Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, pages 596–613. Springer, 2003.
  * [17] U. Feige, J. Kilian, and M. Naor.  A minimal model for secure computation (extended abstract).  In F. T. Leighton and M. T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 554–563. ACM, 1994.
  * [18] R. L. Graham and J. H. Spencer.  A constructive solution to a tournament problem.  Canadian Mathematical Bulletin, 14(1):45–48, 1971.
  * [19] Y. Ishai.  Randomization Techniques for Secure Computation.  In M. Prabhakaran and A. Sahai, editors, Secure Multi-Party Computation, volume 10 of Cryptology and Information Security Series, pages 222–248. IOS Press, 2013.
  * [20] Y. Ishai and E. Kushilevitz.  Private Simultaneous Messages Protocols with Applications.  In Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997, Ramat-Gan, Israel, June 17-19, 1997, Proceedings, pages 174–184. IEEE Computer Society, 1997.
  * [21] R. Peralta.  On the distribution of quadratic residues and nonresidues modulo a prime number.  Mathematics of Computation, 58(197):433–440, Jan. 1992.
  * [22] S. Satake.  On Explicit Random-Like Tournaments.  Graphs and Combinatorics, 37(4):1451–1463, 2021.
  * [23] V. Vaikuntanathan.  Some open problems in information-theoretic cryptography.  In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [24] K. Yoshida, S. Satake, F. Phoa, and M. Sawa.  Circulant almost-orthogonal arrays with strength 3 and bandwidth 1: constructions and existence.  preprint.


# Rashba dominated spin-splitting in the bulk ferroelectric oxide perovskite
KIO3

Sajjan<EMAIL_ADDRESS>Manish Kumar, Preeti Bhumla,
Saswata<EMAIL_ADDRESS>Department of Physics,
Indian Institute of Technology Delhi, New Delhi 110016, India

###### Abstract

The momentum-dependent Rashba and Dresselhaus spin-splitting has gained much
attention for its highly promising applications in spintronics. In the present
work, ab initio density functional theory calculations are performed to study
the spin-splitting effect in ferroelectric oxide perovskite KIO3. Our
calculations are additionally supported by symmetry adapted two-band k.p
Hamiltonian. Non-negligible spin-splitting effect is observed at conduction
band minimum (CBm) and valence band maximum (VBM) for rhombohedral $R3m$ and
$R3c$ phases. Linear Rashba terms successfully explain the splitting at VBM.
However, cubic terms become important in realizing spin-orientation near CBm.
Our results show the enhancement in Rashba parameters on tuning the
ferroelectric order parameter. Further, we have observed reversal of spin-
orientation on switching the direction of polarization.

DFT, Rashba, Dresselhaus, ferroelectricity, symmetry, spin-orbit coupling, k.p
theory

##  I Introduction

Ferroelectric Rashba semiconductors have recently created a huge sensation in
the field of spintronics owing to their robust spontaneous electrical
polarization Picozzi (2014); Martin and Rappe (2016); Zhou (2020); Yang  _et
al._ (2021). These materials find applications in spin field effect
transistors, ferroelectric tunnel junctions, storage and memory devices Garcia
and Bibes (2014); Picozzi (2014); Wang  _et al._ (2020). The long-range order
dipoles aligned in same direction induce polarization in ferroelectric
materials, leading to inversion asymmetry. Ferroelectric Rashba semiconductors
interlink the phenomena of Rashba-type splitting and ferroelectricity,
enabling the electric control of electrons’ spin. In ferroelectric Rashba
semiconductors, Rashba parameters can be enhanced with the application of
ferroelectric (FE) polarization. Interestingly, the spin-orientation can be
inverted by reversing the direction of polarization using external electric
field da Silveira  _et al._ (2016). Electrical control of spin degree of
freedom makes them suitable for spintronic devices. Some well known examples
of ferroelectric Rashba semiconductors are KTaO3 King  _et al._ (2012), BiAlO3
da Silveira  _et al._ (2016), LiZnSb Narayan (2015) and FASnI3
(FA=Formamidinium) Stroppa  _et al._ (2014).

Ferroelectric materials, because of their robust spontaneous electrical
polarization, are widely used in various applications. GeTe was the first
ferroelectric material, in which Rashba effect was predicted theoretically Di
Sante  _et al._ (2013) and observed experimentally Liebmann  _et al._ (2016).
However, it has a tendency to form Ge vacancy Kolobov  _et al._ (2003), which
leads to $p$-type semiconducting behavior. This in turn poses a challenge to
electric control of the spin. In this context, ferroelectric oxide perovskites
such as KIO3 (KIO) show excellent piezoelectric, pyroelectric and non-linear
optical properties Yin and Lü (1992); Kader  _et al._ (2013). KIO, in
particular, is experimentally synthesized at high temperature in non-
centrosymmetric rhombohedral phase with $R3m$ space group symmetry Kasatani
_et al._ (2003). A dynamically favorable rhombohedral $R3c$ phase is also
theoretically predicted Bayarjargal  _et al._ (2012); Kader  _et al._ (2013);
Crane (1975). In both phases, distortion of octahedra centered at I-atom
induces spontaneous FE polarization. Furthermore, the presence of heavy
element (I), contributing to significant spin-orbit coupling (SOC) and
inversion asymmetric nature may induce interesting Rashba- and Dresselhaus-
type band splitting.

Note that SOC and broken inversion symmetry play a pivotal role for the
materials to exhibit Rashba and Dresselhaus effect. In crystals, lacking
inversion symmetry, a relativistically moving electron experiences a Lorentz-
transformed magnetic field due to a finite potential gradient. This results in
spin-based splitting of degenerate bands at non-time-reversal-invariant
k-points, which lifts the Kramer’s degeneracy leading to Rashba and
Dresselhaus splitting. The spin-orientation is determined by the momentum
dependent spin-orbit field. For acentric non-polar crystals, Dresselhaus was
the first to show band splitting, which has a cubic dependence on momentum for
zincblende-type crystal structures Dresselhaus (1955). For gyrotropic point
group symmetries, linear Dresselhaus-type spin-splitting can also be realized.
In polar crystals and 2D electron gas, linear splitting terms are allowed as
shown by Rashba and Bychkov Rashba (1960); Vas’ko (1979); Bychkov and Rashba
(1984). The SOC Hamiltonian $H_{SO}=\bm{\Omega}(\textbf{{k}}).\bm{\sigma}$
describes these effects, where $\bm{\sigma}$ is pauli matrices vector and
$\bm{\Omega}(\textbf{{k}})$ is spin-orbit field. The latter is odd in momentum
space (i.e. $\bm{\Omega}(-\textbf{{k}})=-\bm{\Omega}(\textbf{{k}})$) to
preserve the time-reversal symmetry of $H_{SO}$. $\bm{\Omega}(\textbf{{k}})$
depends on the spatial symmetry of the system. For simplest case, C2v point
group symmetry, $\bm{\Omega}(\textbf{{k}})$ can be written as vector sum of
linear Rashba ($\bm{\Omega}_{R}=\alpha_{R}(k_{y},-k_{x},0)$) and Dresselhaus
($\bm{\Omega}_{D}=\alpha_{D}(k_{y},k_{x},0)$) spin-orbit fields Tao and
Tsymbal (2021). Here, $\alpha_{R}$ and $\alpha_{D}$ are the Rashba and
Dresselhaus coefficients, respectively. These coefficients mainly depend on
the amount of SOC and symmetry of the crystal Tao  _et al._ (2017). Rashba and
Dresselhaus effects lead to the same type of band splitting. However, type of
splitting can be characterized by projecting spin-orientation in Fourier
space, usually referred as spin texture Winkler  _et al._ (2003).

In this article, we have studied the Rashba and Dresselhaus effects in $R3m$
and $R3c$ phases of FE oxide KIO3 using state-of-the-art density functional
theory (DFT) and symmetry adapted two-band k.p Hamiltonian. Firstly, we have
determined the FE polarization in both the phases. Subsequently, the
electronic atom-projected partial density of states (pDOS) and band structures
are determined using DFT. The crucial effect of SOC has been shown in the band
structures. The Rashba spin-splitting energy and offset momentum have been
determined from the splitting at valence band maximum (VBM) and conduction
band minimum (CBm). Further, the type of splitting has been characterized by
plotting the spin texture. The Rashba and Dresselhaus parameters are
determined after fitting the k.p Hamiltonian to the DFT band structure.
Finally, the effect of polarization on the aforementioned parameters has been
investigated.

##  II COMPUTATIONAL METHODS

The calculations are performed using Vienna ab initio simulation package
(VASP) Kresse and Hafner (1993); Kresse and Furthmüller (1996) within the
framework of DFT using projector augmented wave (PAW) pseudopotentials. The
Perdew-Burke-Ernzerhof (PBE) exchange-correlation ($\epsilon_{xc}$) functional
is used for DFT calculations Perdew  _et al._ (1996). For better accuracy of
excited state properties and validations of PBE results, non local Heyd-
Scuseria-Ernzerhof (HSE06) $\epsilon_{xc}$ functional is used Heyd  _et al._
(2003). For effective interpretation of results, conventional hexagonal
setting is also considered. A cutoff energy of 600 eV is used throughout the
calculations. Rhombohedral phases $R3c$ and $R3m$ are relaxed without
including SOC with 9$\times$9$\times$4 and 9$\times$9$\times$8 k-grids,
respectively, generated using Monkhorst-Pack scheme Pack and Monkhorst (1977).
Insignificant role of SOC in relaxation is also verified by test calculations.
The pDOS and band structure calculations are done using 12$\times$12$\times$6
k-grid. Spin texture calculations are done with closely spaced 13$\times$13
k-grid around high symmetry points. In structural optimization, the total
energy difference between two ionic relaxation steps is set to smaller than
$10^{-5}$ eV and tolerance on forces between two consecutive steps is set to
0.001 eV/Å. FE properties are calculated within the framework of berry phase
theory for polarization King-Smith and Vanderbilt (1993); Resta (1994);
Spaldin (2012). Spin textures are calculated using expectation values of spin
operators $S_{i}$ (si=$\langle S_{i}\rangle$)
333$s_{i}=\bra{\Psi_{k}}{S_{i}}\ket{\Psi_{k}}$=$\frac{\hbar}{2}\bra{\Psi_{k}}\sigma_{i}\ket{\Psi_{k}}$,
$\hbar$=1. (i=x, y, z), given by

$s_{i}=\frac{1}{2}\bra{\Psi_{k}}\sigma_{i}\ket{\Psi_{k}}$ (1)

where $\sigma_{i}$ are the pauli matrices and $\Psi_{k}$ is the spinor
eigenfunction obtained from noncollinear spin calculations.

Table 1: Lattice parameters and polarization for rhombohedral phases of KIO. Space group | a(Å) | c(Å) | V(Å3) | P($\mu$C/cm2)
---|---|---|---|---
$R3c$ | 6.37 | 15.91 | 558.6 | 29
$R3m$ | 6.29 | 8.11 | 278.1 | 41

##  III STRUCTURAL AND FERROELECTRIC PROPERTIES

KIO mainly exists in Pm$\bar{3}$m, $R3m$ and $R3c$ space group symmetries.
Pm$\bar{3}$m phase is centrosymmetric i.e., contains an inversion center and
therefore, does not show the Rashba-type splitting. Hence, we have studied the
non-centrosymmetric symmorphic rhombohedral phases $R3m$ and $R3c$ in detail
for Rashba and Dresselhaus properties. The structural details used in the
present work are provided in Table 1. For $R3m$ phase, we have calculated
change in ferroelectric polarization i.e., dipole moment per unit volume
($\frac{\textbf{p}}{V}$) with respect to centrosymmetric structure, of 41
$\mu$C/cm2 along the [0001] direction in hexagonal setting (along the [111]
direction in rhombohedral setting). However, in $R3c$ phase, we have found
slightly smaller polarization of 29 $\mu$C/cm2 along the [0001] direction in
hexagonal setting. In previous studies on BiFeO3 thin films, it has been shown
that FE polarization can be enhanced to as large as 150 $\mu$C/cm2 using the
strain Ederer and Spaldin (2005); Ricinschi  _et al._ (2006); Heon Kim  _et
al._ (2014). In view of this, we have also verified the enhancement in FE
polarization of KIO on the application of strain. The FE polarization has
increased from 29 to 35 $\mu$C/cm2 and 41 to 50 $\mu$C/cm2 in $R3m$ and $R3c$
phases, respectively, on applying uniaxial strain of 10% in the direction of
polarization (in z-direction) within the harmonic approximation (see
discussion later).

##  IV ELECTRONIC PROPERTIES AND Rashba-Dresselhaus EFFECTS

Figure 1: Band structure and pDOS for $R3m$ phase calculated using PBE (a)
without SOC and (b) with SOC. The Fermi energy is set to VBM. Here, inset
shows the first Brillouin zone for the hexagonal phase.

Fig. 1a shows the calculated band structure for the $R3m$ phase without SOC
along the high-symmetry path (HSP) in the first Brillouin zone (see Fig. 1a
inset for HSP). A direct band gap of 2.51 eV is observed. Since PBE is known
to underestimate the band gap, it is also calculated using HSE06. A larger
direct band gap of 3.50 eV is observed at the k-point A with no significant
changes in band profile. The CBm and VBM occur at the k-point A. The uppermost
valence band has a width of about 2.5 eV and the electronic states are mainly
derived from O-2p orbitals (see pDOS in Fig. 1). The lowest conduction band
has a width of nearly 4 eV and the electronic states are mainly derived from
equal contribution of I-5p and O-2p orbitals. Fig. 1b shows the calculated
band structure and pDOS with inclusion of SOC. The VBM and CBm shift from
k-point A towards L, which is known as the offset momentum ($\delta k$). A
slightly indirect band gap of 2.24 and 3.27 eV is observed using PBE+SOC and
HSE06+SOC, respectively. Despite the underestimation of the band gap by PBE,
the band dispersion around the high symmetry point is known to be similar to
HSE06 Di Sante  _et al._ (2013). We have compared the band structures obtained
using PBE+SOC and HSE06+SOC and found that they are resulting in similar
Rashba parameters (see Section I of Supplemental Information (SI)). Therefore,
all the calculations are performed using PBE, since it is more cost effective.
The presence of large SOC is attributed to the heavy elements like I. Dominant
spin-splitting can be seen in the plane kz=$\frac{\pi}{c}$, which is
perpendicular to the polarization axis (see Fig. 1b along A-L and A-H
directions). In contrast, splitting is completely absent in direction
$\Gamma$-A, which is parallel to the polarization axis [0001]. It is
consistent with the Rashba model, where splitting occurs in direction
perpendicular to the polarization axis. The energy difference between the
k-point A and extremum is known as the Rashba spin-splitting energy ($\delta
E$).

Figure 2: Spin texture in $R3m$ phase, calculated at constant energy surface,
near (a) VBM (E=E${}_{\textrm{F}}$$-$0.2 eV) and (b) CBm
(E=E${}_{\textrm{F}}$$+$2.5 eV) centered at k-point A. Spin-splitting of the
(c) VBM and (d) CBm around k-point A. Band structure is plotted along
direction
($\frac{2\pi}{a}$0.25,0,0.5)-(0,0,0.5)-($\frac{2\pi}{a}$0.16,$\frac{2\pi}{b}$0.16,0.5)
of Fourier space, which is along L-A-H. DFT and k.p band structures are
plotted with dashed lines and dots, respectively. Here, the color is
representing the spin-projection.

In order to have better understanding of the spin-splitting nature, spin
texture is plotted near the VBM and CBm around k-point A. The 2D spin texture
is calculated by projecting expectation values of $\sigma_{x}$, $\sigma_{y}$
and $\sigma_{z}$ in Fourier plane (kx-ky) using PyProcar Herath  _et al._
(2020). Fig. 2a and 2b show the calculated x-, y\- and z-component of spin
texture near VBM and CBm, respectively. The in-plane spin components (Sx, Sy)
show helical nature with inner and outer bands having opposite orientation.
This confirms the existence of Rashba-type splitting. A significant out of
plane spin component can also be seen near CBm, which is absent near VBM. The
out of plane spin component ($S_{z}$) has three-fold symmetry, which is in
agreement with the three fold rotation symmetry of the crystal. The little
group of k-point A is $C_{3v}$, consisting of three-fold rotations $C_{3}$,
one reflection through vertical plane containing z-axis ($\sigma_{xz}$) and
two reflections through diagonal planes ($M_{d1}$, $M_{d2}$) lin (a, b)
(besides trivial identity operation). Band dispersion relation and spin
texture around k-point A in plane orthogonal to polar axis can be derived
using all the symmetry-allowed terms such that
$O^{\dagger}H(\textbf{{k}})O=H(\textbf{{k}})$, where $O$ is the symmetry
operation belonging to the little group da Silveira  _et al._ (2016). The
constructed two-band k.p Hamiltonian including linear and cubic Rashba terms
satisfying the $C_{3v}$ symmetry near k-point A takes the form Vajna  _et al._
(2012) (for more details see Section II in SI)

$H_{A}(\textbf{{k}})=H_{o}(\textbf{{k}})+H_{SO}$ (2)

where,

$H_{SO}=\alpha\sigma_{y}k_{x}+\beta\sigma_{x}k_{y}+\gamma\sigma_{z}[(k_{x}^{3}+k_{y}^{3})-3(k_{x}k_{y}^{2}+k_{y}k_{x}^{2})]$
(3)

and $H_{o}(\textbf{{k}})$ is free particle Hamiltonian. $\alpha$, $\beta$ are
the coefficients of linear terms and $\gamma$ is the coefficient of cubic term
in SOC Hamiltonian. Two energy eigenvalues of Hamiltonian are

$E(\textbf{{k}})^{\pm}=\frac{\hbar^{2}k_{x}^{2}}{2m_{x}}+\frac{\hbar^{2}k_{y}^{2}}{2m_{y}}\pm
E_{SO}$ (4)

where, $m_{x}$ and $m_{y}$ represent the effective masses in $x$ and $y$
directions, respectively. $E_{SO}$ is the energy eigenvalue of SOC Hamiltonian
given by
$E_{SO}(\textbf{{k}})=\sqrt{\alpha^{2}k_{x}^{2}+\beta^{2}k_{y}^{2}+\gamma^{2}f^{2}(k_{x},k_{y})}$,
where $f(k_{x},k_{y})=(k_{x}^{3}+k_{y}^{3})-3(k_{x}k_{y}^{2}+k_{y}k_{x}^{2})$.
Normalized spinor wavefunctions corresponding to energy eigenvalues are given
by

$\Psi_{\textbf{{k}}}^{\pm}=\frac{e^{i\textbf{{k.r}}}}{\sqrt{2\pi(\rho^{2}_{\pm}+1})}\begin{pmatrix}\frac{i\alpha
k_{x}-\beta k_{y}}{\gamma f(k_{x},k_{y})\mp E_{SO}}\\\ 1\end{pmatrix}$ (5)

where $\rho^{2}_{\pm}=\frac{\alpha^{2}k_{x}^{2}+\beta^{2}k_{y}^{2}}{(\gamma
f(k_{x},k_{y})\mp E_{SO})^{2}}$. The expectation values of spin operators are
given by

$\\{s_{x},s_{y},s_{z}\\}^{\pm}=\pm\frac{1}{E_{so}}\\{\beta k_{y},\alpha
k_{x},\gamma f(k_{x},k_{y})\\}$ (6)

Spin orientation in x (y) direction depends on $k_{y}$ ($k_{x}$) and it
becomes zero at ky=0 (kx=0). In-plane spin components are reproduced using
$\alpha$ and $\beta$, whereas $\gamma$ reproduces out of plane spin component.
In-plane spin components are small if $\gamma$ is much larger than $\alpha$
and $\beta$, and vice versa. Spin texture calculated using DFT satisfies the
model Hamiltonian predictions. Three-fold degeneracy of z-component of spin is
the consequence of cubic nature of $f(k_{x},k_{y})$ (see Section II in SI for
more details).

Fig. 2c and 2d show the comparison between the DFT and k.p model predicted
band structures near VBM and CBm, respectively, in the vicinity of k-point A.
The k.p model produces band structure, which is in close agreement with the
DFT band structure. Near the k-point A, cubic terms have negligible
contribution in band structure calculations that allows to estimate the values
of $\alpha$ and $\beta$. Hence, energy eigenvalues of the Hamiltonian are
given by
$E(\textbf{{k}})^{\pm}=\frac{\hbar^{2}k_{x}^{2}}{2m_{x}}+\frac{\hbar^{2}k_{y}^{2}}{2m_{y}}\pm\sqrt{\alpha^{2}k_{x}^{2}+\beta^{2}k_{y}^{2}}$,
which estimate only the magnitude of $\alpha$ and $\beta$. The signs of
$\alpha$ and $\beta$ are determined by the orientation of spins in Fourier
space. Rashba and Dresselhaus coefficients are defined as
$\alpha_{R}=\frac{\alpha-\beta}{2}$ and $\alpha_{D}=\frac{\alpha+\beta}{2}$,
respectively (the details can be seen in Section II of SI). For VBM, $\delta
E$=15.1 meV and $\delta k$=0.062 Å-1 are obtained from the DFT band structure
along HSP L-A (see Fig. 2c). It provides $\alpha$=$2\delta E/\delta k=0.49$
eVÅ. In A-H direction, Rashba spin-splitting is same as in L-A direction.
However, the value of $\delta k$ is 0.051 Å-1 (see Fig. 2c). Thus, fitting the
DFT band structure in that direction gives
$\sqrt{\alpha^{2}+\beta^{2}}$=$2\delta E/\delta k$=0.59 eVÅ. It results into
$\beta$=$-$0.33 eVÅ. $\alpha_{R}$ and $\alpha_{D}$ are found to be 0.41 eVÅ
and 0.08 eVÅ , respectively, using $\alpha$ and $\beta$. For CBm, in L-A and
A-H directions, a larger Rashba spin-splitting of 23.2 meV is calculated (see
Fig. 2d). The offset momentum is observed to be 0.054 Å-1 and 0.042 Å-1 in L-A
and A-H directions, respectively (see Fig. 2d). Using the same approach as for
VBM, $\alpha_{R}$=0.77 eVÅ and $\alpha_{D}$=0.11 eVÅ are calculated. All the
calculations are summarized in Table 2. We have observed comparatively larger
Rashba splitting at CBm than VBM due to the higher contribution of I-5p
orbitals at CBm (see Fig. 1). The model Hamiltonian with $\alpha$=0.50 eVÅ,
$\beta$=$-$0.33 eVÅ and $\gamma$=$-$0.06 eVÅ3 reproduces the band structure
and spin texture near k-point A for VBM, that are well in agreement with the
DFT predictions (see Fig. 2a and 2c). Similarly, for CBm, $\alpha$=0.87 eVÅ,
$\beta$=$-$0.67 eVÅ and $\gamma$=$-$4.38 eVÅ3 reproduce the DFT band structure
and spin texture (see Fig. 2b and 2d).

Table 2: Rashba parameters for band-splitting at k-point A for $R3m$ phase. Position |  $\delta E$ |  $\delta$k${}_{\textrm{A-L}}$ |  $\delta$k${}_{\textrm{A-H}}$ |  $\alpha_{R}$ |  $\alpha_{D}$
---|---|---|---|---|---
|  (meV) |  (Å-1) |  (Å-1) |  (eVÅ) |  (eVÅ)
VBM |  15.1 |  0.062 |  0.051 |  0.41 |  0.08
CBm |  23.2 |  0.054 |  0.042 |  0.77 |  0.11
Figure 3: Band structure and pDOS for $R3c$ phase calculated using PBE (a)
without SOC and (b) with SOC. The Fermi energy is set to VBM.

Fig. 3a and 3b show the band structure and pDOS for $R3c$ phase without and
with inclusion of SOC, respectively. It has a direct band gap of 2.86 eV at
k-point $\Gamma$ without including SOC, which is 0.41 eV larger than for the
$R3m$ phase. The contribution of atomic orbitals in the pDOS near VBM and CBm
for the $R3c$ phase are nearly similar to the $R3m$ phase. With the inclusion
of SOC, VBM and CBm shift towards k-point K. A slightly indirect band gap of
2.65 eV on including SOC confirms the importance of SOC in the calculations. A
better estimate of band gap using HSE06+SOC is calculated to be 3.80 eV. Spin-
splitting can be seen throughout the Brillouin zone except for $\Gamma$-A,
which again confirms the polarization direction parallel to $\Gamma$-A (see
Fig. 3b). Dominant spin-splitting can be seen along HSP $\Gamma$-M and
$\Gamma$-K. Fig. 4a and 4b show the plotted spin texture near VBM and CBm,
respectively, around k-point $\Gamma$. In-plane spin textures form helical-
type spin texture with different orientation for inner and outer bands,
confirming the Rashba-type splitting of degenerate levels. A significant out
of plane spin component can also be seen near CBm, which is absent near VBM.
The little group of k-point $\Gamma$ is $C_{3v}$. The model Hamiltonian given
by Eq. 2 can explain the band properties of VBM and CBm near k-point $\Gamma$.
Fig. 4c and 4d show that DFT and k.p model predicted band structures near the
k-point $\Gamma$ are comparable. Rashba spin-splitting energy of 5.4 and 14.8
meV are obtained for VBM and CBm, respectively. The calculations for $R3c$
phase along $\Gamma$-M and $\Gamma$-K directions are done by proceeding the
same as for $R3m$ phase. We have found that $\alpha_{R}$=0.26 eVÅ,
$\alpha_{D}$=0.04 eVÅ for VBM and $\alpha_{R}$=0.52 eVÅ, $\alpha_{D}$=0.11 eVÅ
for CBm. The Hamiltonian given in Eq. 2 with $\alpha$=0.30 eVÅ,
$\beta$=$-$0.21 eVÅ and $\gamma$=$-$0.01 eVÅ3 well satisfies the DFT results
for splitting near VBM (see 4a and 4c). CBm splitting is well approximated by
$\alpha$=0.63 eVÅ, $\beta$=$-$0.41 eVÅ and $\gamma$=$-$3.34 eVÅ3 (see 4b and
4d). For quick review, all the parameters are summarized in Table 3. Rashba
coefficients of some selected ferroelectric materials are compared with KIO in
Section III of SI.

Table 3: Rashba parameters for band-splitting at k-point $\Gamma$ for $R3c$ phase. Position |  $\delta E$ |  $\delta$k${}_{\Gamma-\textrm{M}}$ |  $\delta$k${}_{\Gamma-\textrm{K}}$ |  $\alpha_{R}$ |  $\alpha_{D}$
---|---|---|---|---|---
|  (meV) |  (Å-1) |  (Å-1) |  (eVÅ) |  (eVÅ)
VBM |  5.4 |  0.035 |  0.029 |  0.26 |  0.04
CBm |  14.8 |  0.047 |  0.039 |  0.52 |  0.11
Figure 4: Spin texture in $R3c$ phase, calculated at constant energy surface,
near (a) VBM (E=E${}_{\textrm{F}}$$-$0.2 eV) and (b) CBm
(E=E${}_{\textrm{F}}$$+$3.0 eV) centered at k-point $\Gamma$. Spin-splitting
of the (c) VBM and (d) CBm around k-point $\Gamma$. Band structure is plotted
along direction
($\frac{2\pi}{a}$0.25,0,0)-(0,0,0)-($\frac{2\pi}{a}$0.16,$\frac{2\pi}{b}$0.16,0)
of Fourier space, which is along M-$\Gamma$-K. DFT and k.p band structures are
plotted with dashed lines and dots, respectively. Here, the color is
representing the spin-projection. Figure 5: (a) Rashba spin-splitting energy
($\delta E$), (b) offset momentum ($\delta k$), (c) Rashba parameter
($\alpha_{R}$) and Dresselhaus parameter ($\alpha_{D}$) as a function of
ferroelectric order parameter ($\tau$). The values are calculated for CBm in
$R3m$ phase. The calculated values are linearly fitted. Note that $\delta E$
is same along both A-H and A-L directions.

Effect of ferroelectric order parameter ($\tau$) on the Rashba parameters is
also studied for CBm in $R3m$ phase. $\tau$ (representing the relative
distance between atoms in the unit cell) is varied from -0.10 to 0.10. Here
$\tau$ is defined as

$\tau=\frac{c-c_{0}}{c_{0}}$ (7)

where $c$ and $c_{0}$ are the lattice constants of strained and unstrained
unit cell, respectively. We have observed the linear trend in Rashba spin-
splitting energy and offset momentum along HSP A-L and A-H (see Fig. 5a and
5b). The change in Rashba coefficient is more significant as compared to
Dresselhaus coefficient (see Fig. 5c). The spin degeneracy can be restored by
bringing back Rashba spin-splitting and offset momentum to zero via tuning the
$\tau$. The calculations on BAO showed that Rashba and Dresselhaus parameters
can be made negative by switching the direction of spontaneous polarization
using external electric field da Silveira  _et al._ (2016). The full reversal
of spin texture on reversing the direction of electric field is also observed
in KIO (see Fig. 5a and 5b). However, the change in parameters is
significantly higher for KIO than BAO. The $\alpha_{R}$ can be tuned from 0.38
eVÅ to 1.1 eVÅ by varying the $\tau$ from -0.10 to 0.10 (see Fig. 5c). Rashba
parameters are larger for KIO than BAO, despite significantly larger
ferroelectric polarization in BAO. Therefore, we infer that larger
ferroelectric polarization does not directly imply the larger splitting. A
thorough analysis of symmetry and electronic structure analysis is always
required.

##  V CONCLUSION

In summary, we have performed the relativistic first-principles density
functional theory calculations to study Rashba and Dresselhaus effects in
ferroelectric rhombohedral phases of KIO with $R3m$ and $R3c$ space group
symmetries. Ferroelectric and electronic properties are explored using DFT,
which are also supported by symmetry adapted k.p Hamiltonian. Near VBM and
CBm, the states are mainly derived from I-5p and O-2p orbitals. A sufficiently
wide and slightly indirect band gap is calculated for $R3m$ (2.24 (PBE+SOC),
3.27 (HSE06+SOC) eV) and $R3c$ (2.65 (PBE+SOC), 3.80 (HSE06+SOC) eV) phases,
respectively. Due to significant amount of SOC, spin-splitting effects are
observed at both VBM and CBm around k-points A and $\Gamma$ for $R3m$ and
$R3c$ phases, respectively. Helical-type in-plane spin texture confirms that
the spin-splitting mainly consists of Rashba-type splitting. Out of plane spin
texture shows importance of cubic terms in model Hamiltonian. Hamiltonian
satisfying C3v symmetry reproduces band structure and spin texture near CBm
and VBM, that are well in agreement with the DFT results. The largest Rashba
coefficient is found for CBm in $R3m$ phase. Full reversal of spin texture on
reversing the direction of polarization is also verified. Further, we have
investigated the effect of strain on Rashba and Dresselhaus parameters and
found that they increase linearly with strain. Control of spin-based
properties using the external electric field makes it suitable for spintronics
applications. The larger Rashba coefficient than other contemporary materials
(viz. BAO and LaWN3) makes KIO a promising addition into this class of
material having Rashba-based applications.

##  VI Acknowledgement

S.S. acknowledges CSIR, India, for the junior research fellowship [Grant No.
09/086(1432)/2019-EMR-I]. M.K. acknowledges CSIR, India, for the senior
research fellowship [Grant No. 09/086(1292)/2017-EMR-I]. P.B. acknowledges
UGC, India, for the senior research fellow-ship [1392/(CSIR-UGC NET JUNE
2018)]. S.B. acknowledges the financial support from SERB under Core Research
Grant (Grant No. CRG/2019/000647). We acknowledge the High Performance
Computing (HPC) facility at IIT Delhi for computational resources.

## References

  * Picozzi (2014) S. Picozzi, Frontiers in Physics 2, 10 (2014).
  * Martin and Rappe (2016) L. W. Martin and A. M. Rappe, Nature Reviews Materials 2, 1 (2016).
  * Zhou (2020) B. Zhou, Nanoscale 12, 5533 (2020).
  * Yang  _et al._ (2021) X. Yang, X.-M. Li, Y. Li, Y. Li, R. Sun, J.-N. Liu, X. Bai, N. Li, Z.-K. Xie, L. Su, Z.-Z. Gong, X.-Q. Zhang, W. He, and Z. Cheng, Nano Letters 21, 77 (2021).
  * Garcia and Bibes (2014) V. Garcia and M. Bibes, Nature communications 5, 1 (2014).
  * Wang  _et al._ (2020) H. Wang, P. Gopal, S. Picozzi, S. Curtarolo, M. B. Nardelli, and J. Sławińska, npj Computational Materials 6, 1 (2020).
  * da Silveira  _et al._ (2016) L. G. D. da Silveira, P. Barone, and S. Picozzi, Physical Review B 93, 245159 (2016).
  * King  _et al._ (2012) P. King, R. He, T. Eknapakul, P. Buaphet, S.-K. Mo, Y. Kaneko, S. Harashima, Y. Hikita, M. Bahramy, C. Bell, _et al._ , Physical review letters 108, 117602 (2012).
  * Narayan (2015) A. Narayan, Physical Review B 92, 220101 (2015).
  * Stroppa  _et al._ (2014) A. Stroppa, D. Di Sante, P. Barone, M. Bokdam, G. Kresse, C. Franchini, M.-H. Whangbo, and S. Picozzi, Nature communications 5, 1 (2014).
  * Di Sante  _et al._ (2013) D. Di Sante, P. Barone, R. Bertacco, and S. Picozzi, Advanced materials 25, 509 (2013).
  * Liebmann  _et al._ (2016) M. Liebmann, C. Rinaldi, D. Di Sante, J. Kellner, C. Pauly, R. N. Wang, J. E. Boschker, A. Giussani, S. Bertoli, M. Cantoni, _et al._ , Advanced Materials 28, 560 (2016).
  * Kolobov  _et al._ (2003) A. V. Kolobov, J. Tominaga, P. Fons, and T. Uruga, Applied Physics Letters 82, 382 (2003).
  * Yin and Lü (1992) X. Yin and M. K. Lü, Applied Physics Letters 60, 2849 (1992).
  * Kader  _et al._ (2013) M. A. Kader, F. El-Kabbany, H. Naguib, and W. Gamal, in  _Journal of Physics: Conference Series_ , Vol. 423 (IOP Publishing, 2013) p. 012036.
  * Kasatani  _et al._ (2003) H. Kasatani, S. Aoyagi, Y. Kuroiwa, K. Yagi, R. Katayama, and H. Terauchi, Nuclear Instruments and Methods in Physics Research Section B: Beam Interactions with Materials and Atoms 199, 49 (2003).
  * Bayarjargal  _et al._ (2012) L. Bayarjargal, L. Wiehl, A. Friedrich, B. Winkler, E. A. Juarez-Arellano, W. Morgenroth, and E. Haussuehl, Journal of Physics: Condensed Matter 24, 325401 (2012).
  * Crane (1975) G. Crane, Zeitschrift für Kristallographie-Crystalline Materials 141, 312 (1975).
  * Dresselhaus (1955) G. Dresselhaus, Phys. Rev. 100, 580 (1955).
  * Rashba (1960) E. I. Rashba, Soviet Physics, Solid State 2, 1109 (1960).
  * Vas’ko (1979) F. T. Vas’ko, ZhETF Pisma Redaktsiiu 30, 574 (1979).
  * Bychkov and Rashba (1984) Y. A. Bychkov and E. I. Rashba, Journal of Physics C: Solid State Physics 17, 6039 (1984).
  * Tao and Tsymbal (2021) L. Tao and E. Y. Tsymbal, Journal of Physics D: Applied Physics 54, 113001 (2021).
  * Tao  _et al._ (2017) L. Tao, T. R. Paudel, A. A. Kovalev, and E. Y. Tsymbal, Physical Review B 95, 245141 (2017).
  * Winkler  _et al._ (2003) R. Winkler, S. Papadakis, E. De Poortere, and M. Shayegan,  _Spin-Orbit Coupling in Two-Dimensional Electron and Hole Systems_ , Vol. 41 (Springer, 2003).
  * Kresse and Hafner (1993) G. Kresse and J. Hafner, Physical Review B 47, 558 (1993).
  * Kresse and Furthmüller (1996) G. Kresse and J. Furthmüller, Physical review B 54, 11169 (1996).
  * Perdew  _et al._ (1996) J. P. Perdew, K. Burke, and M. Ernzerhof, Physical review letters 77, 3865 (1996).
  * Pack and Monkhorst (1977) J. D. Pack and H. J. Monkhorst, Physical Review B 16, 1748 (1977).
  * King-Smith and Vanderbilt (1993) R. King-Smith and D. Vanderbilt, Physical Review B 47, 1651 (1993).
  * Resta (1994) R. Resta, Reviews of modern physics 66, 899 (1994).
  * Spaldin (2012) N. A. Spaldin, Journal of Solid State Chemistry 195, 2 (2012).
  * Heyd  _et al._ (2003) J. Heyd, G. E. Scuseria, and M. Ernzerhof, The Journal of Chemical Physics 118, 8207 (2003).
  * Note (1) $s_{i}=\mathinner{\langle{\Psi_{k}}|}{S_{i}}\mathinner{|{\Psi_{k}}\rangle}$=$\frac{\hbar}{2}\mathinner{\langle{\Psi_{k}}|}\sigma_{i}\mathinner{|{\Psi_{k}}\rangle}$, $\hbar$=1.
  * Ederer and Spaldin (2005) C. Ederer and N. A. Spaldin, Phys. Rev. Lett. 95, 257601 (2005).
  * Ricinschi  _et al._ (2006) D. Ricinschi, K.-Y. Yun, and M. Okuyama, Journal of Physics: Condensed Matter 18, L97 (2006).
  * Heon Kim  _et al._ (2014) Y. Heon Kim, A. Bhatnagar, E. Pippel, M. Alexe, and D. Hesse, Journal of Applied Physics 115, 043526 (2014).
  * Herath  _et al._ (2020) U. Herath, P. Tavadze, X. He, E. Bousquet, S. Singh, F. Munoz, and A. H. Romero, Computer Physics Communications 251, 107080 (2020).
  * lin (a) “Bilbao crystallographic server, generators and generalpositions,” https://www.cryst.ehu.es/cryst/get_gen.html (a).
  * lin (b) “Bilbao crystallographic server, point group tables,” https://www.cryst.ehu.es/rep/point.html (b).
  * Vajna  _et al._ (2012) S. Vajna, E. Simon, A. Szilva, K. Palotas, B. Ujfalussy, and L. Szunyogh, Physical Review B 85, 075404 (2012).