11institutetext:  11email<EMAIL_ADDRESS>

# Skipping Scheme for Gate-hiding Garbled Circuits

Ke Lin 11 0009-0002-5376-7881

###### Abstract

In classic settings of garbled circuits, each gate type is leaked to improve
both space and speed optimization. Zahur et al. have shown in EUROCRYPT 2015
that a typical linear garbling scheme requires at least two $\lambda$-bit
elements per gate with a security parameter of $\lambda$, which limits their
efficiency. In contrast to typical garbled circuits, gate-hiding garbled
circuits have the potential to drastically reduce time costs, although they
have been underappreciated.

We propose the first skipping scheme for gate-hiding garbled circuits to
enhance the efficiency of evaluation by observing prime implicants. Our scheme
introduces skip gates to eliminate the need to calculate the entire circuit,
enabling unnecessary execution paths to be avoided. We also introduce two
variants of our scheme that balance security with parallelism. A proof of
hybrid security that combines simulation-based and symmetry-based security in
semi-honest scenarios is presented to demonstrate its security under gate-
hiding conditions. Our scheme will inspire new directions to improve the
general garbling scheme and lead to more practical ones.

###### Keywords:

Garbled Circuit Gate-hiding Semi-private Funciton Evaluation.

##  1 Introduction

Garbled circuit (GC) was first introduced by Andrew Yao [22] that enables
secure two-party computation. A circuit $C$ and an input $x$ are often used to
derive a garbled circuit $\tilde{C}$ and a garbled input $X$, according to the
typical pipeline of garbling schemes. The correct result $C(x)$ may be
obtained by evaluating $\tilde{C}$ on $X$ and decrypting from $\tilde{C}(X)$
without disclosing anything more. In particular, a simulator can simulate
$\tilde{C}$ and $X$ given only $C(x)$.

In a typical two-party computation scenario, the circuit $C$ that each party
wishes to assess is chosen by consensus [14]. The garbled circuits in these
protocols only need to conceal the inputs to $C$ because $C$ is a public
variable and therefore does not need to be kept secret in any other way. It
should be noted, however, that in other situations, such as private function
evaluation (PFE), it can be advantageous for a garbled circuit to mask any
identifying information about the circuit itself [12].

Unlike classical garbled circuits, gate-hiding garbled circuits allow only the
topology to be leaked. At the same time, the gate functions remain a secret.
Although most optimizations on gate-aware circuits are based on the leakage of
gate types, we demonstrate in this paper that keeping the gate function
unknown has the potential to reduce the time costs of evaluating subcircuits
quasi-exponentially, resulting in a practical garbling scheme.

###  1.1 Related Works

The garbled circuit technique described by Yao was promoted to a cryptographic
primitive, the _garbling scheme_ , by Bellare et al. [2], which is used along
with our scheme in this work. Since this technique has been introduced,
numerous efforts [18] have been made to improve it. Techniques such as Point
and Permute [1], GRR3 [13], FreeXOR [7] and Half Gates [24] improve the
efficiency of execution by significantly reducing the space requirements.
Since Fairplay [10], elegant implementations of garbled circuits have begun to
fill up the gap between theory and practice, including FastGC [4], Obliv-C
[23], and TinyGarble [19]. Despite the advances, Zahur et al. [24] argue that
all linear, and thus, efficient, garbling schemes must contain at least two
$\lambda$-bit elements to function properly. Even though some works attempt to
reduce the lower bound of these gates to $\bigo(1.5\lambda)$ [5, 17], it
appears that the efficiency of classic garbled circuits is reaching its limit.

In contrast to gate-aware garbled circuits, gate-hiding circuits remain
underdeveloped and underappreciated, despite the fact that Yao’s original
protocol achieves gate-obliviousness. There are several garbling schemes
designed to support both AND and XOR gates while masking their type from the
evaluator [5, 16, 21]. The varieties differ in the types of Boolean gates they
can support. Recently, Rosulek et al. [17] achieved the state-of-the-art gate-
hiding garbling, in which _any_ gate is garbled for $1.5\lambda+10$ bits.
Furthermore, their gate-hiding construction is fully compatible with FreeXOR.

Songhori et al. [20] proposed a scheme in 2019 that is very similar to ours to
improve the efficiency of evaluating garbled circuits using SkipGate in the
ARM2GC framework. However, their method only allows efficient secure
evaluation of functions with publicly known inputs. In addition, Kolesnikov
[6] proposes using FreeIF to omit inactive branches from garbled circuits for
free, which is an analogous idea to ours but with online communication.

###  1.2 Our Contributions

We propose an effective skipping scheme at runtime for gate-hiding garbled
circuits. The scheme skips inaccessible execution pathways and promotes
parallelism on the fly. In addition to significantly improving the evaluation
speed, our approach is simple to understand and use. The motivation for this
approach stems from the observation that prime implicants in Boolean algebra
disregard insignificant inputs when evaluating functions. The method can also
be used when the circuit consists of both plain and hidden gates, in which
case the method is applied only to hidden gates. We prove that our skipping
scheme achieves hybrid privacy.

A plain skipping scheme (PSS) and a chained skipping scheme (CSS) are
available in our construction. In both schemes, skip gates are constructed and
can be activated or _triggered_ based on certain requirements. We demonstrate
how unnecessary execution paths can be avoided by utilizing the skipping
scheme in semi-private garbled circuits. Even though there are more gates to
generate, the reducing in executions saves evaluation time and computing
resources. In addition to validating the skipping scheme’s correctness, a
proof of hybrid security is presented to prove its security under gate-hiding
conditions.

The efficiency of (sub)circuit evaluation is generally improved by our scheme,
which eliminates the need to calculate the entire circuit at once. We also
obtain a significant improvement for subcircuits since we only need to use a
fraction of the inputs. It optimizes the calculation of gates that remain
unused and benefit from parallel computation.

##  2 Preliminaries

###  2.1 Notation

The notations are defined as follows: $x\xleftarrow{U}X$ represents that $x$
was sampled randomly from $X$ under a uniform distribution, and
$x\leftarrow\mathrm{Alg}$ indicates that $x$ is generated using the algorithm
$\mathrm{Alg}$. The symbol $\oplus$ signifies the exclusive OR operation on
bitstrings, and $[n]$ is an alias for $\\{1,\dots,n\\}$. $\mathrm{LSB}(S)$
denotes the least significant bit of a bitstring $S$, while the remainder is
represented by $\mathrm{L}(S)$. The security parameter is $\lambda$.

###  2.2 Garbled Circuits

This section presents a formal definition of a garbling scheme and the notion
of simulation-based privacy, following the work of Bellare et al. [2]. Note
that all the gates in this work accept two inputs.

We use notation from Kempka et al. [5], which describes a circuit as

$C:=(n,m,l,A,B,g)$

where $n$ is the number of input wires, $m$ is the number of output wires, and
$l$ is the number of gates. A set of wires can be considered as $W:=[n+l]$, a
circuit input wire set as $W_{\text{input}}:=[n+l]\setminus[n+l-m]$, and the
circuit output wires as $W_{\text{gate}}:=[n+l]\setminus[n]$. The functions
$A:W_{\text{gate}}\to W\setminus W_{\text{output}}$ and $B:W_{\text{gate}}\to
W\setminus W_{\text{output}}$ indicate the first input wire of each gate $i$
and the second input wire $B(i)$. Each gate $i$ is specified by the function
$g(i,\cdot,\cdot)=g_{i}(\cdot,\cdot)$. For simplicity, we will omit the
parameter $i$ in some cases.

######  Definition 1 (Garbling Scheme)

A garbling scheme for a family of circuits
$\mathcal{C}=\\{\mathcal{C}_{n}\\}_{n\in\mathbb{N}}$, where $n$ is a
polynomial in a security parameter $k$, employs probabilistic polynomial-time
algorithms
$\mathrm{GC}=(\mathrm{GC.Gb},\mathrm{GC.Enc},\mathrm{GC.Eval},\mathrm{GC.Dec})$
defined as follows:

  * •

$(\tilde{C},e,d)\leftarrow\mathrm{GC.Gb}(1^{\lambda},C)$: takes as input
security parameter $1^{\lambda}$ and circuit $C\in\mathcal{C}$ and outputs
garbled circuit $\tilde{C}$, encoding information $e$ and decoding information
$d$.

  * •

$X\leftarrow\mathrm{GC.Enc}(e,x)$: takes as input encoding information $e$ and
circuit input $x\in\\{0,1\\}^{n}$, and outputs garbled input $X$.

  * •

$Y\leftarrow\mathrm{GC.Eval}(\tilde{C},X)$: takes as input garbled circuit
$\tilde{C}$ and garbled input $X$, and outputs garbled output $Y$.

  * •

$y\leftarrow\mathrm{GC.Dec}(d,Y)$: takes as input decoding information $d$ and
garbled output $Y$, and outputs circuit output $y$.

A garbling scheme should satisfy the correctness property: For any circuit $C$
and input $x$, after sampling $(\tilde{C},e,d)$ from the garbling scheme, and
the following equation
$C(x)=\mathrm{GC.Dec}(d,\mathrm{GC.Eval}(\tilde{C},\mathrm{GC.Enc}(e,x)))$
holds with all but negligible probability.

We introduce the notion of a random oracle $H$ to allow adversary access. We
also indicate the information on circuit $C$ that is permitted to be leaked by
the garbling scheme by the value $\Phi(C)$. Topology
$\Phi_{\text{topo}}(C)=(n,m,l,A,B)$ or entire circuit information
$\Phi_{\text{circ}}(C)=(n,m,l,A,B,g)$, for example, can be leaked. And the
gate-hiding garbling scheme always sends $\Phi_{\text{topo}}$ instead of the
entire circuit to the evaluator.

##  3 Skipping Scheme

This section presents our basic skipping scheme for semi-honest gate-hiding
circuits. The scheme is first demonstrated for circuits with 2-implicative
components. Then, it is extended from the initial scenario for circuits with
2-implicative components to a more general scenario for $n$-implicative
components.

###  3.1 Construction

We use the following notation. Let $\alpha:=\lito(\lambda)\ll\lambda$ be the
security parameter for hash functions, which can usually be a constant. The
input wires $W_{i}$ may be assigned a value of 0 or 1, which is indicated by
$W_{i}^{0},W_{i}^{1}$. The set of possible assignments of two input wires
$W_{i},W_{j}$ is denoted by
$\mathcal{V}_{i,j}:=\\{(W_{i}^{b_{i}},W_{j}^{b_{j}})\mid
b_{i},b_{j}\in\\{0,1\\}\\}$. We then define the $k$-implicative (sub)circuit
and skippable wires formally.

######  Definition 2 ($k$-implicative)

Let $C$ be a Boolean circuit with $n$ input wires
$\mathcal{W}=\\{W_{i}\\}^{n}_{i=1}$. We say circuit $C$ is $k$-implicative
($k<n$) if: there exist $k$ fixed assignments
$\\{W^{b_{d_{i}}}_{d_{i}}\\}^{k}_{i=1}$ to a subset of input wires
$\mathcal{K}=\\{W_{d_{i}}\\}^{k}_{i=1}\subset\mathcal{W}$ such that for every
assigments $\\{W^{x_{\overline{d_{i}}}}_{\overline{d_{i}}}\\}^{n-k}_{i=1}$ to
$\mathcal{W}\backslash\mathcal{K}$,

$C(W^{x_{1}}_{1},\dots,W^{b_{d_{1}}}_{d_{1}},\dots,W^{b_{d_{k}}}_{d_{k}},\dots,W^{x_{n}}_{n})\equiv\text{constant}$

###### Corollary 1

A $n$-implicative circuit is also $m$-implicative for all $m>n$.

A $k$-implicative circuit implies that $k$ specific assignments to parts of
the inputs are sufficient to compute the final result. This simple observation
leads to the reduction of evaluation costs by skipping the gates which are not
the implicants.

######  Definition 3 (Skippable)

For a circuit $C$, two of its input wires $W_{i}$ and $W_{j}$ are skippable if
there exist 2 different assignment pairs
$v_{0}^{i,j},v_{1}^{i,j}\in\mathcal{V}_{i,j}$ that make the circuit $C$
2-implicative in both cases. These two input wires are also known as a pair of
skippable wires, denoted by $(W_{i},W_{j})\leftarrow\mathrm{Pair}(C)$.

Skippable wires are the basic elements of our skipping scheme. Definition 2
discusses $n$-implicative wires as another form of implicants in Boolean
algebra. Previous research has shown that prime implicants of functions with
many inputs can be found using heuristic methods, which is essentially more
efficient by several orders of magnitude. The entire algorithm for searching
for skippable wires can be found in 0.A.1. Next, we describe our scheme, which
leverages these skippable wires. It should be noted that the skipping scheme
targets the subcircuits of the entire circuit, and we will be abusing the
terms subcircuit and circuit in the following sections.

####  3.1.1 Plain Skipping Scheme.

Let $C$ be a Boolean circuit and
$\tilde{C}\leftarrow\mathrm{GC.Gb}(1^{\lambda},C)$ be its garbled version. Let
$\Gamma=(G,\mathnormal{Enc},\mathnormal{Dec})$ be a CPA-secure symmetric key
encryption scheme, and $\mathnormal{H}_{\alpha}$ be a hash function with
security parameter $\alpha$. The complete PSS is described in Fig. 1.

Trigger value $t$ is an easy-to-compute indicator that provides a fast method
to determine whether the skip gates should be activated. The constant result
of (sub)circuit is precomputed and encrypted as $G_{b}$ for $b\in\\{0,1\\}$.
As there are two pairs of inputs $v_{0},v_{1}$ that lead to the constant
output, ciphertexts are permuted randomly to ensure security. Permute bit $b$
indicates which ciphertext should be used when the skip gate is triggered.
Here $s$ is a shared salt to restrict the permute bit
$b_{0}:=\mathrm{LSB}(t_{0}),b_{1}:=\mathrm{LSB}(t_{1})$ and the remainder
bitstring, such that $b_{0}\neq b_{1}$ and
$\mathrm{L}(t_{0})\neq\mathrm{L}(t_{1})$. Then we compute the ciphertexts

$G_{b}\leftarrow\mathnormal{Enc}_{v_{0}}^{\lambda}(R),~{}G_{1-b}\leftarrow\mathnormal{Enc}_{v_{1}}^{\lambda}(R)$

where $b:=b_{0}$ and
$R:=\tilde{C}(\dots,v_{0},\dots)=\tilde{C}(\dots,v_{1},\dots)$ is the result
label of the garbled circuit given the input $v_{0}$ or $v_{1}$ according to
the Definitions 2 and 3. Note that some superscripts, such as $i,j$, may be
ignored if the reference to the wire pairs is clear.

For simplicity, we denote the skip gates by
$S_{i,j}^{\text{PSS}}:=(\mathrm{L}(t_{0}^{i,j}),\mathrm{L}(t_{1}^{i,j}),G_{0}^{i,j},G_{1}^{i,j})$.

Input: The security parameter $\lambda$ and $\alpha$, the circuit $C$ and the
garbled circuit $\tilde{C}$. Output: Contexts of skip gates
$\mathcal{S}^{\text{PSS}}:=\\{S_{i,j}^{\text{PSS}}\mid(W_{i},W_{j})\in\mathcal{P}\\}$.
[0.5ex]1pt1mm Candidate Selection: Establish a sufficient number of skippable
wires by using the algorithm 0.A.1 and generate a list of candidate skippable
wire pairs
$\mathcal{P}:=\\{(W_{i},W_{j})\mid(W_{i},W_{j})\leftarrow\mathrm{Pair}(C)\\}$.
Gate Generation: Compute the
$S_{i,j}^{\text{PSS}}:=(\mathrm{L}(t_{0}^{i,j}),\mathrm{L}(t_{1}^{i,j}),G_{0}^{i,j},G_{1}^{i,j})$
for each skippable wire pair $(W_{i},W_{j})\in\mathcal{P}$: 1. Compute trigger
values $t_{x}^{i,j}\leftarrow\mathnormal{H}_{\alpha}(s^{i,j},v_{x}^{i,j})$ for
$x\in[4]$ using a generated public salt $s^{i,j}$ which satisfies
$\mathrm{LSB}(t_{0}^{i,j})\neq\mathrm{LSB}(t_{1}^{i,j})$ and each
$\mathrm{L}(t_{x}^{i,j})$ is different. 2. Compute ciphertexts
$G_{b}^{i,j}\leftarrow\mathnormal{Enc}_{v_{0}^{i,j}}^{\lambda}(R)$ and
$G_{1-b}^{i,j}\leftarrow\mathnormal{Enc}_{v_{1}^{i,j}}^{\lambda}(R)$ where
$b:=\mathrm{LSB}(t_{0}^{i,j})$ and
$R:=\tilde{C}(\dots,v_{0}^{i,j},\dots)=\tilde{C}(\dots,v_{1}^{i,j},\dots)$.

Input: The security parameter $\lambda$ and $\alpha$, the garbled circuit
$\tilde{C}$, the contexts of skip gates $\mathcal{S}^{\text{PSS}}$ and the
garbled input $X$. Output: If triggered, returns the
$\mathrm{GC.Eval}(\tilde{C},X)$. Otherwise, no action is taken.
[0.5ex]1pt1mm Trigger Testing: For each
$S_{i,j}^{\text{PSS}}\in\mathcal{S}^{\text{PSS}}$ and the current input wire
pair $v:=(X_{i},X_{j})$, compute the
$t^{i,j}\leftarrow\mathnormal{H}_{\alpha}(s^{i,j},v)$. If
$\mathrm{L}(t^{i,j})$ equals to $\mathrm{L}(t_{0}^{i,j})$ or
$\mathrm{L}(t_{1}^{i,j})$, then it is triggered and the next step is to be
taken. Otherwise, abort the procedure and return nothing. Evaluation: Compute
the permute bit $b\leftarrow\mathrm{LSB}(t^{i,j})$ and decode the final result
of $\tilde{C}$ as $\mathnormal{Dec}_{v}^{\lambda}(G_{b}^{i,j})$.

Figure 1: Procedure of the plain skipping scheme.

####  3.1.2 Chained Skipping Scheme.

In contrast to PSS, CSS could form a decryption chain when evaluating the skip
gates. A CSS chain can only be triggered if the previous gates in the chain
have failed; this prevents leakage of the trigger state of subsequent gates.

In a similar fashion to PSS, we reuse many notations. Let $n$ be the number of
skip gates in the chain. The garbler precomputes the context values for the
$k$-th gate in the chain, which bring the previous skip gate’s information to
the current skip gate.

$\displaystyle
c_{\alpha}^{k}\leftarrow\mathnormal{H}_{\alpha}(s^{k},c_{\alpha}^{k-1},T_{\alpha}(\mathnormal{H}_{\alpha}(s^{k},c_{\alpha}^{k-1},v_{3}),\mathnormal{H}_{\alpha}(s^{k},c_{\alpha}^{k-1},v_{4})))$
(1) $\displaystyle
c_{\lambda}^{k}\leftarrow\mathnormal{H}_{\lambda}(s^{k},c_{\lambda}^{k-1},T_{\lambda}(\mathnormal{H}_{\lambda}(s^{k},c_{\lambda}^{k-1},v_{3}),\mathnormal{H}_{\lambda}(s^{k},c_{\lambda}^{k-1},v_{4})))$

where $s^{k}$ is the salt for the $k$-th gate and
$T_{x}:\\{0,1\\}^{2}\to\\{0,1\\}$ is an irreversible function that is abelian
with respect to its two inputs for $x\in\\{\alpha,\lambda\\}$. Assignment
pairs $v_{3}$ and $v_{4}$ are the pairs that are not included in the
definition of 2-implicative, as opposed to their counterparts $v_{0}$ and
$v_{1}$.

The generating algorithm for CSS skip gates produces two more chain values,
$t_{c}^{k}$ and $G_{c}^{k}$.

$\displaystyle
t_{c}^{k}\leftarrow\mathnormal{H}_{\alpha}(s^{k},c_{\alpha}^{k-1},v_{3})\oplus\mathnormal{H}_{\alpha}(s^{k},c_{\alpha}^{k-1},v_{4})$
(2) $\displaystyle
G_{c}^{k}\leftarrow\mathnormal{H}_{\lambda}(s^{k},c_{\alpha}^{k-1},v_{3})\oplus\mathnormal{H}_{\lambda}(s^{k},c_{\alpha}^{k-1},v_{4})$

These chain values are used to convey the other hash values without revealing
them explicitly. If $\mathnormal{H}_{x}(s^{k},c_{x}^{k-1},v_{y})$ for
$x\in\\{\alpha,\lambda\\},y\in\\{3,4\\}$ is known when the previous gates have
not been triggered, the chain values can then be used to calculate the hash
$\mathnormal{H}_{x}(s^{k},c_{x}^{k-1},v_{7-y})$.

The full CSS is shown in Fig. 2. The pipeline of $\mathrm{CSS.Eval}$’s
evaluation is divided into two distinct branches. The first branch updates the
context value, while the second is for evaluating the actual results.

Input: The security parameter $\lambda$ and $\alpha$, the circuit $C$ and the
garbled circuit $\tilde{C}$. Output: Contexts of skip gates
$\mathcal{S}^{\text{CSS}}:=\\{S_{k}^{\text{CSS}}\mid(W_{i},W_{j},k)\in\mathcal{P}\\}$.
[0.5ex]1pt1mm Candidate Selection: Establish sufficient skippable wires by
Alg. 0.A.1 and an ordered chain of candidate pairs
$\mathcal{P}:=\\{(W_{i},W_{j},k)\\}_{k}$ s.t.
$(W_{i},W_{j})\leftarrow\mathrm{Pair}(C)$. Context Preprocessing: Compute the
context values $\\{c_{\alpha}^{k}\\}$ and $\\{c_{\lambda}^{k}\\}$ by Eq. 1.
Gate Generation: Compute the
$S_{k}^{\text{CSS}}:=(\mathrm{L}(t_{0}^{k}),\mathrm{L}(t_{1}^{k}),t_{c}^{k},G_{0}^{k},G_{1}^{k},G_{c}^{k})$
for each skippable wire pair $(i,j,k)\in\mathcal{P}$: 1. Compute trigger
values
$t_{x}^{k}\leftarrow\mathnormal{H}_{\alpha}(s^{k},c_{\alpha}^{k-1},v_{x}^{k})$
and for $x\in[4]$ using a generated public salt $s^{k}$ s.t.
$\mathrm{LSB}(t_{0}^{k})\neq\mathrm{LSB}(t_{1}^{k})$ and each
$\mathrm{L}(t_{x}^{k})$ is different. 2. Compute ciphertexts
$G_{b}^{k}\leftarrow\mathnormal{Enc}_{v_{0}^{k}}^{\lambda}(R)\oplus
c_{\lambda}^{k-1}$ and
$G_{1-b}^{k}\leftarrow\mathnormal{Enc}_{v_{1}^{k}}^{\lambda}(R)\oplus
c_{\lambda}^{k-1}$ where $b:=\mathrm{LSB}(t_{0}^{k})$ and
$R:=\tilde{C}(\dots,v_{0}^{k},\dots)=\tilde{C}(\dots,v_{1}^{k},\dots)$. 3.
Compute chain values $t_{c}^{k}$ and $G_{c}^{k}$ by Eq. 2.

Input: Similar to PSS. Output: If triggered, returns the
$\mathrm{GC.Eval}(\tilde{C},X)$. Otherwise, no action is taken.
[0.5ex]1pt1mm Trigger Testing: For each
$S_{k}^{\text{CSS}}\in\mathcal{S}^{\text{CSS}}$ and the $k$-th input wire pair
$v^{k}:=(X_{i},X_{j})$, compute the
$t^{k}\leftarrow\mathnormal{H}_{\alpha}(s^{k},c_{\alpha}^{k-1},v^{k})$. If
$\mathrm{L}(t^{k})$ equals to $\mathrm{L}(t_{0}^{k})$ or
$\mathrm{L}(t_{1}^{k})$, then the evaluation triggered. Otherwise, update the
context and continue. Context Update(Not Triggered): If not triggered, $v^{k}$
must be $v_{3}^{k}$ or $v_{4}^{k}$. For $x\in\\{\alpha,\lambda\\}$, compute
the unordered pair of $\mathnormal{H}_{x}(s^{k},c_{x}^{k-1},v_{3}^{k})$ and
$\mathnormal{H}_{x}(s^{k},c_{x}^{k-1},v_{4}^{k})$ using Eq. 2. Next, update
the context value $c_{\alpha}^{k}$ and $c_{\lambda}^{k}$ by Eq. 1.
Evaluation(Triggered): If triggered, compute the permute bit
$b\leftarrow\mathrm{LSB}(t^{k})$ and decode the final result of $\tilde{C}$ as
$\mathnormal{Dec}_{v^{k}}^{\lambda}(G_{b}^{k})$.

Figure 2: Procedure of the chained skipping scheme.

####  3.1.3 Extension for $n$-implicative Circuits.

Let $\mathcal{W}_{n}:=\\{W_{i}^{b_{i}}\\}_{i=1}^{n}$ be the set of input wires
that make the circuit $n$-implicative. Extensions to $n$-implicative circuits
are based on the following techniques:

  1. 1.

Group the elements of the set $\mathcal{W}_{n}$ two by two to obtain the set
of input wire pairs $\mathcal{V}_{n}:=\\{(W_{i}^{b_{i}},W_{j}^{b_{j}})\mid
W_{i}^{b_{i}},W_{j}^{b_{j}}\in\mathcal{W}_{n}\\}$. Note that pairs can overlap
to ensure that all input wires are covered.

  2. 2.

Establish an ordered chain of candidate input wire pairs that will never
trigger in $\mathrm{CSS.Gen}$, except for the last.

  3. 3.

Substitute the above-generated candidate chain for the one used in gate
generation for $\mathrm{CSS.Gen}$.

###  3.2 General Pipeline

Generally, the skipping scheme is constructed on top of the common garbling
scheme. It works in parallel with the classic garbling circuit of [2] and
leaves the garbling scheme intact. Our modified garbling scheme is shown in
Fig. 3.

Garbling phase: • $(\tilde{C},e,d)\leftarrow\mathrm{GC.Gb}(1^{\lambda},C)$:
Generate the garbled circuit $\tilde{C}$ as the original garbling scheme. ★
$\mathcal{S}\leftarrow\mathrm{SS.Gen}(1^{\lambda},1^{\alpha},C,\tilde{C})$:
Generate information of skipping scheme. Evaluating phase: •
$X\leftarrow\mathrm{GC.Enc}(e,x)$: Encode the raw inputs with encoding
information $e$. ★
$Y^{\prime}\leftarrow\mathrm{SS.Eval}(1^{\lambda},1^{\alpha},\tilde{C},\mathcal{S},X)$:
Evaluate the skipping scheme and obtain $Y^{\prime}$. If $Y^{\prime}$ is not
empty, let $Y\leftarrow Y^{\prime}$ and move on to the decoding phase. •
$Y\leftarrow\mathrm{GC.Eval}(\tilde{C},X)$: Evaluate the garbled circuit in
the same manner as the original garbling scheme. Decoding phase: •
$y\leftarrow\mathrm{GC.Dec}(d,Y)$: Decode the $Y$ and output the circuit
output $y$. Figure 3: Patched garbling scheme with skipping scheme. The
algorithm $\mathrm{SS}$ here can be either $\mathrm{PSS}$ or $\mathrm{CSS}$,
depending on the exact skipping scheme.

###  3.3 Efficiency

Our efficiency estimation considers the skipping scheme’s space complexity and
computational complexity.

For a typical garbled circuit, we assume that each basic gate consume
$2\lambda$ space [24] as the starting points. PSS gates require
$2\alpha+2\lambda$ space to store two trigger values and two ciphertexts. CSS
gates require $3\alpha+3\lambda$ space to store two more chain values. We
ignore the salts used in gate generation, as they consume very few bits in
almost every case.

An estimation of the computational costs of each gate can be achieved by
denoting the time costs of the hash function and the decryption by $t_{h}$ and
$t_{d}$. We assume that the decryption time of the basic gate is the same as
the skip gates, i.e. $t_{d}$ is used for decryption of both garbled gates and
skip gates. Whenever a PSS gate is triggered, the evaluation cost is comprised
of one hash for testing the PSS and one decryption for obtaining final
results. Otherwise, if the PSS gate is not triggered, a hash calculation and a
regular gate decryption is performed. A similar analysis can be performed for
CSS costs.

In this work, we estimate the complexity of a circuit consisting of $N$ gates.
Let $n_{c}$ be the number of skip gates. As each gate is triggered
probabilistically, the computational complexity of each gate is analyzed by
estimating both its expectation and the worst-case scenario separately. We
denote $\theta$ as the probability of triggering skip gates for general
analysis. The uniform case without prior knowledge of inputs is one of the
most common cases for our scheme when $\theta=0.5$. Regarding the general case
of the $\theta$ trigger chance and the derivation of average costs, we leave
all the results in Appendix 0.A.2. For future reference, we present a useful
claim derived from Proposition 2.

######  Proposition 1 (Probability of Triggering)

In the case of serial and honest execution, if the probability of triggering
an individual skip gate is $\theta$, then the $k$-th skip gate has a
$\theta(1-\theta)^{k-1}$ probability of being triggered during the entire
procedure, whereas the whole skipping scheme has a $1-(1-\theta)^{n_{c}}$
probability to be triggered.

A summary of the cost estimation can be found in Table 1. It is noteworthy
that the evaluation costs of skipping scheme decreases quasi-exponentially as
$n_{c}$ grows. However, as $n_{c}$ reflects the number of skip gates in a
specific subcircuit, it is highly unpredictable and intractable, depending on
the intrinsic characteristics of the circuit. The capacity for skip gates is
likely to be greater in circuits with fewer inputs, but this is only
empirically proven. This section focuses on intra-subcircuit costs, but
Appendix 0.A.2 examines inter-subcircuit costs in details.

Table 1: Estimation of the efficiency of the serial skipping scheme when $\theta=0.5$.  Costs | Baseline | PSS | CSS
---|---|---|---
per gate
Gate Space | $2\lambda$ | $4\lambda+2\alpha$ | $5\lambda+3\alpha$
Gate Eval. Time | $t_{d}$ | $t_{d}+t_{h}$ |  $t_{d}+t_{h}$ or $t_{d}+5t_{h}$
per circuit
Circuit Eval. Time (Worst) | $Nt_{d}$ | $N(t_{d}+t_{h})$ | $N(t_{d}+5t_{h})$
Circuit Eval. Time (Avg.) | $Nt_{d}$ |  $\leq$ CSS | $Nt_{d}\cdot 2^{-n_{c}}+t_{d}+10t_{h}-\tilde{\mathup{\Theta}}(2^{-n_{c}})$

##  4 Security Analysis

###  4.1 Correctness

The correctness of our skipping scheme is evident from the fact that it does
not impact the regular garbling scheme. In the case of
$\mathcal{S}\leftarrow\mathrm{SS.Gen}(1^{\lambda},1^{\alpha},C,\tilde{C})$, it
is clear that
$\mathrm{SS.Eval}(1^{\lambda},1^{\alpha},\tilde{C},\mathcal{S},X)$ yields the
same result as $\tilde{C}(X)$. Since skipping is disabled if it is not
triggered, we only verify the output when it is activated. Let $R$ be the
constant final result.

##### Correctness of PSS.

Let $S^{\text{PSS}}:=(\mathrm{L}(t_{0}),\mathrm{L}(t_{1}),G_{0},G_{1})$ be the
context of the skip gate that passes the trigger test. We assume that the
$i$-th ($i\in\\{0,1\\}$) value pair $v_{i}$ is the input pair to
$\mathrm{PSS.Eval}$ and the ciphertexts $G$ in $\mathrm{PSS.Gen}$ are
rewritten as follows.

$\displaystyle t_{i}\leftarrow\mathnormal{H}(s,v_{i}),$
$\displaystyle~{}b_{i}\leftarrow\mathrm{LSB}(t_{i})$ $\displaystyle
G_{\mathrm{LSB}(t_{0})}\leftarrow\mathnormal{Enc}_{v_{0}}^{\lambda}(R),$
$\displaystyle~{}G_{\mathrm{LSB}(t_{1})}\leftarrow\mathnormal{Enc}_{v_{1}}^{\lambda}(R)$

We then receive the result.

$\displaystyle G_{b_{i}}$
$\displaystyle=G_{\mathrm{LSB}(t_{i})}\leftarrow\mathnormal{Enc}_{v_{i}}^{\lambda}(R)$
$\displaystyle R$
$\displaystyle\leftarrow\mathnormal{Dec}_{v_{i}}^{\lambda}(G_{b_{i}})=\mathnormal{Dec}_{v_{i}}^{\lambda}(\mathnormal{Enc}_{v_{i}}^{\lambda}(R))$

##### Correctness of CSS.

Suppose CSS gets triggered until $k=n$. For any $k<n$, the CSS gates should
get either $v_{3}^{k}$ or $v_{4}^{k}$ as input. We first prove that the CSS
fails the trigger test when $k=m<n$. Assume that we already have the context
values $c_{\alpha}^{m-1}$ and $c_{\lambda}^{m-1}$ and the context
$S_{m}^{\text{CSS}}$, the $m$-th trigger test then

  1. 1.

calculates
$t^{m}\leftarrow\mathnormal{H}_{\alpha}(s^{m},c_{\alpha}^{m-1},v_{3}^{m})\text{
or }\mathnormal{H}_{\alpha}(s^{m},c_{\alpha}^{m-1},v_{4}^{m})$,

  2. 2.

compares $\mathrm{L}(t^{m})$ with $\mathrm{L}(t_{0}^{m})$ and
$\mathrm{L}(t_{1}^{m})$,

  3. 3.

fails and updates the context values $c_{\alpha}^{m}$ and $c_{\lambda}^{m}$.

Apparently, the iterative trigger test always fails for $k\in[n-1]$. When
$k=n$, the CSS gates receive input pair $v_{0}^{k}$ or $v_{1}^{k}$. Similar to
PSS, for the $n$-th gate that survive the trigger test, let
$S^{\text{CSS}}:=(\mathrm{L}(t_{0}^{n}),\mathrm{L}(t_{1}^{n}),t_{c}^{n},G_{0}^{n},G_{1}^{n},G_{c}^{n})$
be the context, $v_{i}^{n}$ ($i\in\\{0,1\\}$) be the received input pair and
$c_{\alpha}^{n-1},c_{\lambda}^{n-1}$ be the context values. Rewrite
$\mathrm{CSS.Eval}$ as follows:

$\displaystyle
t_{i}^{n}\leftarrow\mathnormal{H}_{\alpha}(s^{n},c_{\alpha}^{n-1},v_{i}^{n}),$
$\displaystyle~{}b_{i}^{n}\leftarrow\mathrm{LSB}(t_{i}^{n})$ $\displaystyle
G_{\mathrm{LSB}(t_{0}^{n})}^{n}\leftarrow\mathnormal{Enc}_{v_{0}^{n}}^{\lambda}(R)\oplus
c_{\lambda}^{n-1},$
$\displaystyle~{}G_{\mathrm{LSB}(t_{1}^{n})}^{n}\leftarrow\mathnormal{Enc}_{v_{1}^{n}}^{\lambda}(R)\oplus
c_{\lambda}^{n-1}$

Similarly, we obtain the same final output as $\tilde{C}(X)$:

$\displaystyle G_{b_{i}^{n}}^{n}$
$\displaystyle=G_{\mathrm{LSB}(t_{i}^{n})}^{n}\leftarrow\mathnormal{Enc}_{v_{i}^{n}}^{\lambda}(R)$
$\displaystyle R$
$\displaystyle\leftarrow\mathnormal{Dec}_{v_{i}^{n}}^{\lambda}(G_{b_{i}^{n}})=\mathnormal{Dec}_{v_{i}^{n}}^{\lambda}(\mathnormal{Enc}_{v_{i}^{n}}^{\lambda}(R))$

###  4.2 Simulation-Based Security

Security of the skipping scheme in semi-honest scenarios is divided into two
categories: untriggered and triggered. In this proof, we demonstrate that the
distribution of _view of the evaluation_ of the original garbled circuit is
indistinguishable from that with the skipping scheme, following the
instructions of Lindell [9, 8]. For simplicity, we only prove the security of
PSS. Distribution of the view of algorithm $\mathcal{G}$ is denoted by
$\mathrm{View}(\mathcal{G})$. Also,
$\mathrm{View}(\mathcal{G}_{1})\equiv\mathrm{View}(\mathcal{G}_{2})$ indicates
that the views of $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ have
(computationally) identical distributions.

######  Definition 4 (Security of Evaluation with Auxiliary Scheme)

For a garbling scheme
$\mathrm{GC}=(\mathrm{GC.Gb},\mathrm{GC.Enc},\mathrm{GC.Eval},\mathrm{GC.Dec})$,
the garbled circuit $\tilde{C}\leftarrow\mathrm{GC.Gb}(1^{\lambda},C)$,
garbled input $X\in\\{0,1\\}^{n}$, auxiliary scheme $\mathcal{G}$, simulator
$\mathrm{Sim}$ and a random oracle $H$, the advantage of the adversary
$\mathcal{A}$ is defined as
$Adv_{\mathcal{A},\mathrm{GC.Eval},\mathcal{G},\mathrm{Sim},\Phi}(\lambda):=$

$\displaystyle\Big{\lvert}$
$\displaystyle\Pr[\mathcal{A}^{H}(\mathrm{View}(\mathrm{GC.Eval}(\Phi(\tilde{C}),X)),\mathrm{View}(\mathcal{G}(\Phi(\tilde{C}),X)))=1]$
$\displaystyle-$
$\displaystyle\Pr[\mathcal{A}^{H}(\mathrm{View}(\mathrm{GC.Eval}(\Phi(\tilde{C}),X)),\mathrm{Sim}(\mathrm{View}(\mathrm{GC.Eval}(\Phi(\tilde{C}),X))))=1]\Big{\rvert}$

A garbling scheme $\mathrm{GC}$ with an auxiliary scheme $\mathcal{G}$ is
secure, if there exists a PPT simulator $\mathrm{Sim}$, such that for any
garbled circuit $\tilde{C}$, garbled input $X$ and PPT adversary
$\mathcal{A}$, the advantage
$Adv_{\mathcal{A},\mathrm{GC.Eval},\mathcal{G},\mathrm{Sim},\Phi}(\lambda)$ is
negligible.

The _view of the skipping scheme_ consists of the garbled input $X$, the
garbled output $\tilde{C}(X)$, the context of the generated skip gates
$\mathcal{S}^{\text{SS}}$, the trigger state $\tau_{\text{st}}$ and the
indices of the trigger gates $\tau_{\text{idx}}$. In the _view of the garbled
circuit_ , these variables have been identified: the garbled input and output
$X,\tilde{C}(X)$, the information of circuit $\Phi(\tilde{C})$, and the
intermediate result $I(\tilde{C},X)$. The security parameter $\lambda$ and
$\alpha$ have been omitted for simplicity.

$\displaystyle\mathrm{View}(\mathcal{G}(\Phi(\tilde{C}),X))$
$\displaystyle:=(X,\tilde{C}(X),\mathcal{S}^{\text{SS}},\tau_{\text{st}},\tau_{\text{idx}})$
$\displaystyle\mathrm{View}(\mathrm{GC.Eval}(\Phi(\tilde{C}),X))$
$\displaystyle:=(X,\tilde{C}(X),\Phi(\tilde{C}),I(\tilde{C},X))$

Simulating the view of the scheme is achieved with the following oracles:

  * •

$\mathcal{O}_{\tau}(\Phi(\tilde{C}))$: Oracle $\mathcal{O}_{\tau}$ is queried
to determine whether the skipping scheme has been triggered.

  * •

$\mathcal{O}_{0}(\Phi(\tilde{C}))$: Oracle $\mathcal{O}_{0}$ is queried to
retrieve the selected wire pairs $\mathcal{P}$.

  * •

$\mathcal{O}_{1}(\Phi(\tilde{C}),i,j)$: Oracle $\mathcal{O}_{1}$ is queried to
obtain trigger values $t$ and salts $s$ that satisfy the partial inequality
criteria.

  * •

$\mathcal{O}_{2}(\Phi(\tilde{C}))$: Oracle $\mathcal{O}_{2}$ is queried to
obtain the indices of triggered gates $\tau_{\text{idx}}$.

####  4.2.1 Untriggered Cases.

######  Theorem 4.1 (Simulation-based Privacy of Untriggered Cases)

Let $n_{c}$ be the number of skip gates. The general skipping scheme
$\mathcal{G}$ described in Section 3 is simulation-based secure in
_untriggered_ cases, for $\Phi=\Phi_{\text{topo}}=(n,m,l,A,B,\mathcal{W})$,
where $\mathcal{W}$ represents the mapping function for ciphertexts of each
gate. More precisely, there exists an adversary $\mathcal{A}$ such that

$\displaystyle
Adv_{\mathcal{A},\mathrm{GC.Eval},\mathcal{G},\mathrm{Sim},\Phi_{\text{topo}}}^{\text{UT}}(\lambda)\leq
n_{c}2^{-(\lambda-1)}.$

###### Proof

Simulated experiments for untriggered cases are conducted using the simulator
$S_{\text{UT}}$, as well as the games
$\mathcal{G}_{0}^{\mathcal{O}_{0},\mathcal{O}_{1}}$ and
$\mathcal{G}_{\text{UT}}$, and described as follows.

  * •

$S_{\text{UT}}(\mathrm{View}(\mathrm{GC.Eval}(\Phi(\tilde{C}),X)))$:
$S_{\text{UT}}$ described in Fig. 4 generates the context of skip gates and
simulates the view of the actual skipping scheme.

  * •

$\mathcal{G}_{0}^{\mathcal{O}_{0},\mathcal{O}_{1}}(\Phi(\tilde{C}),X)$:
$\mathcal{G}_{0}^{\mathcal{O}_{0},\mathcal{O}_{1}}$ given in Fig. 5 simulate
the context of a skipping scheme with information on the garbled circuit and
the garbled input $X$. In this game, we utilize oracles $\mathcal{O}_{0}$ and
$\mathcal{O}_{1}$ to show the robustness of the simulator by fixing part of
the generation of skip gates.

  * •

$\mathcal{G}_{\text{UT}}(\Phi(\tilde{C}),X)$: Real experiment of the skipping
scheme in untriggered cases.

Input: The security parameter $\lambda$ and $\alpha$, and
$\mathrm{View}(\mathcal{G}(\Phi(\tilde{C}),X))$. Output: The simulated view of
skipping scheme
$(X,\tilde{C}(X),\mathcal{S},\tau_{\text{st}},\tau_{\text{idx}})$.
[0.5ex]1pt1mm 1. Set $\tau_{\text{st}}=0$ and $\tau_{\text{idx}}=-1$. 2.
Select sufficient wires randomly as the candidate skippable wire pairs
$\mathcal{P}$. 3. Contexts of skip gates: (a) For every pair
$(W_{i},W_{j})\in\mathcal{P}$, randomly sample two pairs of value
$(r_{0}^{0},r_{1}^{0}),(r_{0}^{1},r_{1}^{1})\xleftarrow{U}\\{0,1\\}^{2\lambda}$,
which do not equals the corresponding wires’ garbled inputs of $X$, i.e.
$(r_{0},r_{1})\neq(X(i),X(j))$. (b) Compute trigger values
$t_{0}^{i,j}\leftarrow\mathnormal{H}_{\alpha}(s^{i,j},(r_{0}^{0},r_{1}^{0}))$
as well as
$t_{1}^{i,j}\leftarrow\mathnormal{H}_{\alpha}(s^{i,j},(r_{0}^{1},r_{1}^{1}))$
using a generated public salt $s^{i,j}$ such that
$\mathrm{LSB}(t_{0}^{i,j})\neq\mathrm{LSB}(t_{1}^{i,j})$ and each
$\mathrm{L}(t_{x}^{i,j})$ is different. (c) Randomly sample ciphertexts
$G_{0}^{i,j},G_{1}^{i,j}\xleftarrow{U}\\{0,1\\}^{\lambda}$. Figure 4: The
simulator $S_{\text{UT}}$ in untriggered cases. Input: The security parameter
$\lambda$ and $\alpha$, $\Phi(\tilde{C})$, and the garbled input $X$. Output:
The simulated view of this game
$(X,\tilde{C}(X),\mathcal{S},\tau_{\text{st}},\tau_{\text{idx}})$.
[0.5ex]1pt1mm 1. Set $\tau_{\text{st}}=0$ and $\tau_{\text{idx}}=-1$. 2.
Retrieve the selected wire pairs from oracle
$\mathcal{P}\leftarrow\mathcal{O}_{0}(\Phi(\tilde{C}))$. 3. Contexts of skip
gates: (a) For every pair $(W_{i},W_{j})\in\mathcal{P}$, compute trigger
values and salts from oracle:
$(t_{0}^{i,j},t_{1}^{i,j})\leftarrow\mathcal{O}_{1}(\Phi(\tilde{C}),i,j)$ with
the corresponding salt $s^{i,j}$. (b) Randomly sample ciphertexts
$G_{0}^{i,j},G_{1}^{i,j}\xleftarrow{U}\\{0,1\\}^{\lambda}$. Figure 5: The game
$\mathcal{G}_{0}^{\mathcal{O}_{0},\mathcal{O}_{1}}$ in untriggered cases.

Now we will demonstrate that the simulators are indistinguishable from the
real protocol.

  * •

$\mathrm{View}(S_{\text{UT}})\equiv\mathrm{View}(\mathcal{G}_{0}^{\mathcal{O}_{0},\mathcal{O}_{1}})$:
The two games differ in two ways. The first is regarding the skip gates
chosen, and the second is regarding the generation of the actual trigger
values. Since the skipping scheme remains untriggered, any shift in the
distribution of the chosen skip gates will not affect the overall view of the
skipping scheme. Given that the trigger values are created by the hash
function $\mathnormal{H}_{\alpha}$ uniformly, the distribution between the one
derived from oracle $\mathcal{O}_{1}(\Phi(\tilde{C}),i,j)$ and the sample one
should be identical.

  * •

$\mathrm{View}(\mathcal{G}_{0}^{\mathcal{O}_{0},\mathcal{O}_{1}})\equiv\mathrm{View}(\mathcal{G}_{\text{UT}})$:
The only difference between these two games is the ciphertexts. Using
ciphertexts in real experiments will prevent malicious decryption from
obtaining the actual output $\tilde{C}(X)$. However, ciphertexts in simulated
games are sampled uniformly and may fail to meet the criteria mentioned above
$\mathnormal{Dec}_{v}^{\lambda}(G^{i,j})\neq\tilde{C}(X)$ for all two
ciphertexts of the skip gates. The probability of failure is
$1-(1-2^{-\lambda})^{2n_{c}}\leq n_{c}2^{-(\lambda-1)}$.

####  4.2.2 Triggered Cases.

######  Theorem 4.2 (Simulation-based Privacy of Triggered Cases)

Let $n_{c}$ be the number of skip gates. The general skipping scheme
$\mathcal{G}$ described in Section 3 is secure based on simulation in the
_triggered_ cases, for $\Phi=\Phi_{\text{topo}}=(n,m,l,A,B,\mathcal{W})$,
where $\mathcal{W}$ represents the mapping function for the ciphertexts of
each gate. More precisely, there exists an adversary $\mathcal{A}$ such that

$\displaystyle
Adv_{\mathcal{A},\mathrm{GC.Eval},\mathcal{G},\mathrm{Sim},\Phi_{\text{topo}}}^{\text{T}}(\lambda)\leq(2n_{c}-1)2^{-\lambda}.$

###### Proof

In triggered cases, we consider simulator $S_{\text{T}}$ in the simulated
experiments of Definition 4, and the games $\mathcal{G}$ as below.

  * •

$S_{\text{T}}(\mathrm{View}(\mathrm{GC.Eval}(\Phi(\tilde{C}),X)))$:
$S_{\text{T}}$ in Fig. 6 generates the context of skip gates, the trigger
state, and simulates the view of the actual skipping scheme.

  * •

$\mathcal{G}_{\fpeval}{1+0}^{\mathcal{O}_{2}}(\Phi(\tilde{C}),X)$:
$\mathcal{G}_{\fpeval}{1+0}^{\mathcal{O}_{2}}$ described in Fig. 7 simulates
the context of skip gates. Queries to oracle $\mathcal{O}_{2}$ constrain the
selection of triggered gates, while eliminating the shift of distribution.

  * •

$\mathcal{G}_{\fpeval}{1+1}^{\mathcal{O}_{0},\mathcal{O}_{1},\mathcal{O}_{2}}(\Phi(\tilde{C}),X)$:
$\mathcal{G}_{\fpeval}{1+1}^{\mathcal{O}_{0},\mathcal{O}_{1},\mathcal{O}_{2}}$
in Fig. 8 simulates the context with two additional oracles. Oracles
$\mathcal{O}_{0}$ and $\mathcal{O}_{1}$ in this game simulate the real
skipping scheme with partially predetermined contexts, as in the untriggered
cases.

  * •

$\mathcal{G}_{\text{T}}$: Real experiment of the skipping scheme in triggered
cases.

Input: The security parameter $\lambda$ and $\alpha$, and
$\mathrm{View}(\mathcal{G}(\Phi(\tilde{C}),X))$. Output: The simulated view of
skipping scheme
$(X,\tilde{C}(X),\mathcal{S},\tau_{\text{st}},\tau_{\text{idx}})$.
[0.5ex]1pt1mm 1. Select sufficient candidate skippable wire pairs
$\mathcal{P}$ randomly. Set $\tau_{\text{st}}=1$. 2. Choose random skippable
wire pairs as triggered gates with the probability of Proposition 1, denoted
by $\mathcal{T}$. Set the indices of $\mathcal{T}$ as $\tau_{\text{idx}}$. 3.
Contexts of skip gates that belong to $\mathcal{T}$: (a) For every pair
$(W_{i},W_{j})\in\mathcal{T}$, set
$(r_{0}^{b^{\prime}},r_{1}^{b^{\prime}})=(X(i),X(j))$ and sample randomly
$(r_{0}^{1-b^{\prime}},r_{1}^{1-b^{\prime}})\xleftarrow{U}\\{0,1\\}^{2\lambda}$,
s.t. $(r_{0}^{1-b^{\prime}},r_{1}^{1-b^{\prime}})\neq(X(i),X(j))$. (b) Compute
trigger values
$t_{b^{\prime}}^{i,j}\leftarrow\mathnormal{H}_{\alpha}(s^{i,j},(r_{0}^{b^{\prime}},r_{1}^{b^{\prime}}))$
as well as
$t_{1-b^{\prime}}^{i,j}\leftarrow\mathnormal{H}_{\alpha}(s^{i,j},(r_{0}^{1-b^{\prime}},r_{1}^{1-b^{\prime}}))$
using a shared salt $s^{i,j}$ s.t.
$\mathrm{LSB}(t_{0}^{i,j})\neq\mathrm{LSB}(t_{1}^{i,j})$ and each
$\mathrm{L}(t_{x}^{i,j})$ is different. (c) Randomly sample ciphertext
$G_{\mathrm{LSB}(t_{1-b^{\prime}}^{i,j})}^{i,j}\xleftarrow{U}\\{0,1\\}^{\lambda}$.
(d) Set ciphertext
$G_{\mathrm{LSB}(t_{b^{\prime}}^{i,j})}^{i,j}=\mathnormal{Enc}_{(X(i),X(j))}^{\lambda}(R)$.
4. Contexts of skip gates that do not belong to $\mathcal{T}$: Same as the
$S_{\text{UT}}$. Figure 6: The simulator $S_{\text{T}}$ in triggered cases.
Input: The security parameter $\lambda$ and $\alpha$, $\Phi(\tilde{C})$, and
the garbled input $X$. Output: The simulated view of this game
$(X,\tilde{C}(X),\mathcal{S},\tau_{\text{st}},\tau_{\text{idx}})$.
[0.5ex]1pt1mm 1. Set $\tau_{\text{st}}=1$ and
$\tau_{\text{idx}}\leftarrow\mathcal{O}_{2}(\Phi(\tilde{C}))$. 2. Select a
sufficient number of wires randomly (with the probability of Proposition 1)
containing $\tau_{\text{idx}}$ as the candidate skippable wire pairs
$\mathcal{P}$, i.e. $\tau_{\text{idx}}\subseteq\mathcal{P}$. 3. Contexts of
skip gates that belong to $\mathcal{T}$: Same as the $S_{\text{T}}$. 4.
Contexts of skip gates that do not belong to $\mathcal{T}$: Same as the
$S_{\text{T}}$. Figure 7: The game
$\mathcal{G}_{\fpeval}{1+0}^{\mathcal{O}_{2}}$ in triggered cases. Input: The
security parameter $\lambda$ and $\alpha$, $\Phi(\tilde{C})$, and the garbled
input $X$. Output: The simulated view of this game
$(X,\tilde{C}(X),\mathcal{S},\tau_{\text{st}},\tau_{\text{idx}})$.
[0.5ex]1pt1mm 1. Set $\tau_{\text{st}}=1$ and
$\tau_{\text{idx}}\leftarrow\mathcal{O}_{2}(\Phi(\tilde{C}))$. 2. Retrieve the
selected wire pairs from oracle
$\mathcal{P}\leftarrow\mathcal{O}_{0}(\Phi(\tilde{C}))$. 3. Contexts of skip
gates that belong to $\mathcal{T}$: • For every pair
$(W_{i},W_{j})\in\mathcal{P}$, compute trigger values and salts from oracle:
$(t_{0}^{i,j},t_{1}^{i,j})\leftarrow\mathcal{O}_{1}(\Phi(\tilde{C}),i,j)$ with
the corresponding salt $s^{i,j}$. Either $t_{0}^{i,j}$ or $t_{1}^{i,j}$ must
be equal to the hash of input
$t_{b^{\prime}}^{i,j}:=\mathnormal{H}_{\alpha}(s^{i,j},(X(i),X(j)))$. •
Randomly sample ciphertext
$G_{\mathrm{LSB}(t_{1-b^{\prime}}^{i,j})}^{i,j}\xleftarrow{U}\\{0,1\\}^{\lambda}$.
• Set ciphertext
$G_{\mathrm{LSB}(t_{b^{\prime}}^{i,j})}^{i,j}=\mathnormal{Enc}_{(X(i),X(j))}^{\lambda}(R)$.
4. Contexts of skip gates that do not belong to $\mathcal{T}$: Same as the
$\mathcal{G}_{0}^{\mathcal{O}_{0},\mathcal{O}_{1}}$. Figure 8: The game
$\mathcal{G}_{\fpeval}{1+1}^{\mathcal{O}_{0},\mathcal{O}_{1},\mathcal{O}_{2}}$
in triggered cases.

Next, we will demonstrate that the simulation and the real experiment are
indistinguishable.

  * •

$\mathrm{View}(S_{\text{T}})\equiv\mathrm{View}(\mathcal{G}_{\fpeval}{1+0}^{\mathcal{O}_{2}})$:
In the game $\mathcal{G}_{\fpeval}{1+0}^{\mathcal{O}_{2}}$, oracle
$\mathcal{O}_{2}$ is queried to access the indices of the current triggered
gates. Since the simulator selects these gates based on the probability of
Proposition 1, their views cannot be distinguished from each other.

  * •

$\mathrm{View}(\mathcal{G}_{\fpeval}{1+0}^{\mathcal{O}_{2}})\equiv\mathrm{View}(\mathcal{G}_{\fpeval}{1+1}^{\mathcal{O}_{0},\mathcal{O}_{1},\mathcal{O}_{2}})$:
As with the untriggered cases, these two games differ in two fundamentally
different ways. The distribution of views remains the same.

  * •

$\mathrm{View}(\mathcal{G}_{\fpeval}{1+1}^{\mathcal{O}_{0},\mathcal{O}_{1},\mathcal{O}_{2}})\equiv\mathrm{View}(\mathcal{G}_{\text{T}})$:
The only difference between these two games is the ciphertexts. The
distribution of the ciphertexts is uniformly sampled based on the assumption
of a CPA-secure encryption scheme. However, the ciphertexts for invalid inputs
in simulated games are sampled uniformly and may fail to reject malicious
decryptions. The probability of failure is
$1-(1-2^{-\lambda})^{2n_{c}-|\mathcal{T}|}\leq(2n_{c}-|\mathcal{T}|)2^{-\lambda}\leq(2n_{c}-1)2^{-\lambda}$.

####  4.2.3 Oracle to Trigger State.

######  Theorem 4.3 (Simulation-based Privacy with Trigger State)

Let $n_{c}$ be the number of skip gates. The general skipping scheme
$\mathcal{G}$ described in Section 3 is simulation-based secure with the
oracle $\mathcal{O}_{\tau}$ to the trigger state $\tau_{\text{st}}$, for
$\Phi=\Phi_{\text{topo}}=(n,m,l,A,B,\mathcal{W})$, where $\mathcal{W}$
represents the mapping function for the ciphertexts of each gate. More
precisely, there exists an adversary $\mathcal{A}$ such that

$\displaystyle
Adv_{\mathcal{A},\mathrm{GC.Eval},\mathcal{G},\mathrm{Sim},\Phi_{\text{topo}}}^{\mathcal{O}_{\tau}}(\lambda)\leq(4n_{c}-1)2^{-\lambda}.$

###### Proof

Theorems 4.1 and 4.2 imply the upper bound from $Adv^{\text{UT}}(\lambda)$ and
$Adv^{\text{T}}(\lambda)$.

###### Lemma 1

The security of evaluation of garbling scheme
$\mathrm{GC.Eval}^{\mathcal{O}_{\tau}}(\Phi(\tilde{C}),X)$ with the oracle
$\mathcal{O}_{\tau}$ to the trigger state is _computationally
indistinguishable_ from the security of the evaluation of the skipping scheme.

The obliviousness of gate functions $g$ is critical for the security of
$\mathrm{GC.Eval}^{\mathcal{O}_{\tau}}$. A leaked circuit with gate functions
$\Phi_{\text{circ}}(\tilde{C})$ may allow the evaluator to obtain the
triggered gates and acquire the final result with significant probability
because of the _circuit satisfiability problems_ (CIRCUIT-SAT) or _Boolean
satisfiability problems_ (BOOLEAN-SAT). Hence, the skipping scheme can only be
applied to gate-hiding circuits.

######  Lemma 2 (Symmetry of Gate-hiding Garbled Circuits)

Let $C$ be a circuit and
$(\tilde{C},e,d)\leftarrow\mathrm{GC.Gb}(1^{\lambda},C)$, with
$\Phi=\Phi_{\text{topo}}=(n,m,l,A,B,\mathcal{W})$. Given a fixed garbled input
$X$, for any PPT adversary $\mathcal{A}$ and $y\in\\{0,1\\}^{n}$, there exists
encoding information $e^{\prime}$ and negligible $\epsilon(\lambda)$ s.t.
$X=\mathrm{GC.Enc}(e^{\prime},y)$ and

$\displaystyle\Big{\lvert}$
$\displaystyle\Pr[(\Phi(\tilde{C}),e,d)\leftarrow\mathrm{GC.Gb}(1^{\lambda},C):\mathcal{A}(\Phi(\tilde{C}),e,d)=1]$
$\displaystyle-$
$\displaystyle\Pr[(\Phi(\tilde{C}),e^{\prime},d)\leftarrow\mathrm{GC.Gb}(1^{\lambda},C):\mathcal{A}(\Phi(\tilde{C}),e^{\prime},d)=1]\Big{\rvert}\leq\epsilon(\lambda)$

###### Proof

Here we describe only the brief process of proving this using a definite
algorithm. For the $i$-th single-bit input, denoted by $x(i)$ and $y(i)$
separately, if

  * •

$x(i)=y(i)$: remain unchanged for encoding information $e$ for this input
wire.

  * •

$x(i)\neq y(i)$: swap the garbled values of 0 and 1 in encoding information
$e$ for this input wire.

It is obvious, then, that the modified encoding information is $e^{\prime}$
such that $X=\mathrm{GC.Enc}(e^{\prime},y)$. In this instance, the encoding
information $e^{\prime}$ is indistinguishable from the original information.

######  Theorem 4.4 (Security with Oracle to Trigger State)

Assuming a gate-hiding garbled circuit
$(\Phi(\tilde{C}),e,d)\leftarrow\mathrm{GC.Gb}(1^{\lambda},C)$ and a random
oracle $H$, for any PPT adversary $\mathcal{A}$ and input $x\in\\{0,1\\}^{n}$
and $X\leftarrow\mathrm{GC.Enc}(e,x)$, it holds that there exists a negligible
$\epsilon(\lambda)$ s.t.

$\displaystyle\Big{\lvert}$
$\displaystyle\Pr[s\leftarrow\mathrm{GC.Dec}(d,\mathrm{GC.Eval}(\Phi(\tilde{C}),X)):\mathcal{A}^{H}(\Phi(\tilde{C}),X,s,d)=x]$
$\displaystyle-$
$\displaystyle\Pr[s\leftarrow\mathrm{GC.Dec}(d,\mathrm{GC.Eval}^{\mathcal{O}_{\tau}}(\Phi(\tilde{C}),X)):\mathcal{A}^{\mathcal{O}_{\tau}}(\Phi(\tilde{C}),X,s,d)=x]\Big{\rvert}\leq\epsilon(\lambda)$

###### Proof

Lemma 2 states that adversary $\mathcal{A}^{\mathcal{O}_{\tau}}$ has no
advantage over adversary $\mathcal{A}^{H}$ in guessing the real inputs since
the property of symmetry enables _any_ input to hold the same view by hiding
the encoding scheme. By doing so, the characteristics of inputs are thoroughly
erased, making the trigger state useless. This results in an equal level of
security between $\mathrm{GC.Eval}^{\mathcal{O}_{\tau}}$ and
$\mathrm{GC.Eval}$.

######  Corollary 2 (Security of Skipping Scheme)

Except for a negligible probability, the garbling scheme
$\mathrm{GC}^{\mathrm{SS}}$ with the skipping scheme is as secure as the
normal garbling scheme $\mathrm{GC}$.

##  5 Conclusion

This paper present the skipping scheme for gate-hiding circuits that allows a
fast evaluation of garbling schemes on skippable subcircuits. As the number of
skip gates increases, the estimated efficiency increases quasi-exponentially,
substantially reducing computational overheads. In the presence of oblivious
gate functions, our theoretical security analysis proves the hybrid security
of our skipping scheme.

## References

  * [1] Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols. In: Proc. 22nd Annu. ACM Symp. Theory Comput. pp. 503–513 (1990)
  * [2] Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Proc. 2012 ACM Conf. Comput. Commun. Secur. pp. 784–796 (2012)
  * [3] Brayton, R.K., Hachtel, G.D., McMullen, C., Sangiovanni-Vincentelli, A.: Logic minimization algorithms for VLSI synthesis, vol. 2. Springer Science & Business Media (1984)
  * [4] Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: USENIX Secur. Symp. vol. 201, pp. 331–335 (2011)
  * [5] Kempka, C., Kikuchi, R., Suzuki, K.: How to circumvent the two-ciphertext lower bound for linear garbling schemes. In: Cheon, J., Takagi, T. (eds) ASIACRYPT 2016\. LNCS. vol. 10032, pp. 967–997. Springer (2016)
  * [6] Kolesnikov, V.: Free if: How to omit inactive branches and implement s-universal garbled circuit (almost) for free. In: Peyrin, T., Galbraith, S. (eds) ASIACRYPT 2018. LNCS. vol. 11274, pp. 34–58. Springer (2018)
  * [7] Kolesnikov, V., Schneider, T.: Improved garbled circuit: Free xor gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. LNCS. vol. 5126, pp. 486–498. Springer (2008)
  * [8] Lindell, Y.: How to simulate it–a tutorial on the simulation proof technique. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich pp. 277–346 (2017)
  * [9] Lindell, Y., Pinkas, B.: A proof of security of yao’s protocol for two-party computation. J. Cryptology 22, 161–188 (2009)
  * [10] Malkhi, D., Nisan, N., Pinkas, B., Sella, Y., et al.: Fairplay-secure two-party computation system. In: USENIX Secur. Symp. vol. 4, p. 9. San Diego, CA, USA (2004)
  * [11] McCluskey, E.J.: Minimization of boolean functions. The Bell System Technical Journal 35(6), 1417–1444 (1956)
  * [12] Mohassel, P., Sadeghian, S.: How to hide circuits in mpc an efficient framework for private function evaluation. In: Johansson, T., Nguyen, P.Q. (eds) EUROCRYPT 2013. EUROCRYPT 2013. LNCS. vol. 7881, pp. 557–574. Springer (2013)
  * [13] Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: Proc. 1st ACM Conf. Electron. Commerce. pp. 129–139 (1999)
  * [14] Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: Matsui, M. (eds) ASIACRYPT 2009. LNCS. vol. 5912, pp. 250–267. Springer (2009)
  * [15] Quine, W.V.: The problem of simplifying truth functions. The American mathematical monthly 59(8), 521–531 (1952)
  * [16] Rosulek, M.: Improvements for gate-hiding garbled circuits. In: Patra, A., Smart, N. (eds) INDOCRYPT 2017. LNCS. vol. 10698, pp. 325–345. Springer (2017)
  * [17] Rosulek, M., Roy, L.: Three halves make a whole? beating the half-gates lower bound for garbled circuits. In: Malkin, T., Peikert, C. (eds) CRYPTO 2021. LNCS. vol. 12825, pp. 94–124. Springer (2021)
  * [18] Saleem, A., Khan, A., Shahid, F., Alam, M.M., Khan, M.K.: Recent advancements in garbled computing: how far have we come towards achieving secure, efficient and reusable garbled circuits. J. Netw. Comput. Appl. 108, 1–19 (2018)
  * [19] Songhori, E.M., Hussain, S.U., Sadeghi, A.R., Schneider, T., Koushanfar, F.: Tinygarble: Highly compressed and scalable sequential garbled circuits. In: 2015 IEEE Symp. Secur. Privacy. pp. 411–428. IEEE (2015)
  * [20] Songhori, E.M., Riazi, M.S., Hussain, S.U., Sadeghi, A.R., Koushanfar, F.: Arm2gc: Succinct garbled processor for secure computation. In: Proc. 56th Annu. Des. Automat. Conf. 2019. pp. 1–6 (2019)
  * [21] Wang, Y., et al.: Reducing garbled circuit size while preserving circuit gate privacy. Cryptology ePrint Archive (2017)
  * [22] Yao, A.C.: Protocols for secure computations. In: 23rd Annu. Symp. Found. Comput. Sci. (sfcs 1982). pp. 160–164. IEEE (1982)
  * [23] Zahur, S., Evans, D.: Obliv-c: A language for extensible data-oblivious computation. Cryptology ePrint Archive (2015)
  * [24] Zahur, S., Rosulek, M., Evans, D.: Two halves make a whole: Reducing data transfer in garbled circuits using half gates. In: Oswald, E., Fischlin, M. (eds) EUROCRYPT 2015. LNCS. vol. 9057, pp. 220–250. Springer (2015)

##  Appendix 0.A Supplement to Skipping Scheme

###  0.A.1 Skippable Wires Searching

This section explains how to select skippable wires in a (sub)circuit $C$. Let
$F_{C}$ be the Boolean function of the circuit, $\mathcal{I}$ be the set of
inputs, and $\mathrm{PIS}(\mathcal{I},F_{C})$ be the procedure for searching
for prime implicants. In general, when $|\mathcal{I}|$ is small,
$\mathrm{PIS}$ can be the Quine-McCluskey algorithm [15, 11], while when
$|\mathcal{I}|$ is large, $\mathrm{PIS}$ can be the ESPRESSO algorithm [3].
The overall algorithm for selecting skippable wires is described below.

Prime Implicants Search: 1. Compute the set of positive prime implicants
$\mathcal{P}_{0}\leftarrow\mathrm{PIS}(\mathcal{I},F_{C})$. 2. Compute the set
of negative prime implicants
$\mathcal{P}_{1}\leftarrow\mathrm{PIS}(\mathcal{I},\neg F_{C})$. Skippable
Pairs Generation: 1. If $|\mathcal{P}_{0}|=1$, then let $P$ be the only
element of $\mathcal{P}_{0}$, and each two inputs to $P$ are skippable wire
pairs. 2. If $|\mathcal{P}_{0}|>1$, for every prime implicants
$P\in\mathcal{P}_{0}$ s.t. $|P|\leq 2$: • If $|P|=1$: Each wire pair with an
input belonging to $P$ is skippable. • If $|P|=2$: The wire pair with exact
the same input as $P$ is skippable. 3. Repeat the same procedure for
$\mathcal{P}_{1}$. Figure 9: Algorithm for selecting skippable wires.

##### Correctness.

Since each $P$ is an implicant of $F_{C}$, the corresponding inputs to $P$
would satisfy the skippable wire definition. Thus, each $P$ in the above
procedure can be mapped to some candidate skippable wire pairs.

###### Remark 1

As $|P|=2$ indicates, only one pair of inputs can be skipped. It is possible
to continue on these wire pairs, but it would reduce the likelihood that skip
gates would be triggered. Practically, it would be better to prioritize the
wire pairs with $|P|=1$ higher on the priority list.

###  0.A.2 Costs of Skipping Scheme

Skipping scheme costs can be divided into two categories: intra-subcircuit
costs and inter-subcircuit costs. The cost of evaluating a subcircuit falls
under the intra-subcircuit cost category, while the inter-subcircuit cost
category relates to the improvement of the interplay between subcircuits.

##### Intra-subcircuit costs.

Our formula for triggering when the chance of triggering is $\theta$ is given
here in its complete mathematical derivation. Let
$\mathrm{ACC}_{N,n_{c}}(\theta)$ be the average costs of $N$-gates garbled
(sub)circuits with $n_{c}$ CSS gates.

######  Proposition 2 (Intra-subcircuit costs)

$\displaystyle\mathrm{ACC}_{N,n_{c}}(\theta)=$
$\displaystyle\sum_{k=1}^{n_{c}}\Pr[k\text{-th gate hit only}]\cdot(k\cdot
5t_{h}+t_{d})+\Pr[\text{All miss}]\cdot Nt_{d}$ $\displaystyle=$
$\displaystyle t_{d}+\frac{5t_{h}}{\theta}+(1-\theta)^{n_{c}}\cdot
Nt_{d}-(1-\theta)^{n_{c}}\cdot[t_{d}+5t_{h}(n_{c}+\frac{1}{\theta})]$

##### Inter-subcircuit costs.

Inter-subcircuit costs assume that the entire circuit is formulated as the
combinations of indivisible subcircuits. A subcircuit’s cost can be calculated
based on the intra-subcircuit costs mentioned above. We are only interested in
the general improvement over the circuit’s topology as a result of skipping.

Let $C_{i}$ denotes the $i$-th subcircuits of the total $n$ subcircutis, and
$P(C_{i})$ be the set of subcircuits that have outputs to the $C_{i}$. Let
$\mathrm{ACC}(C_{i})$ be the intra-subcircuit cost of $C_{i}$, and
$\mathrm{EAC}(C_{i})$ be the expected accumulative time cost of $C_{i}$.
Consider all subcircuits as having a probability of $\theta$ of being skipped.

######  Lemma 3 (Decay of accumulative costs)

$\displaystyle\mathrm{EAC}(C_{i})=\max_{\hat{C}\in
P(C_{i})}\\{(1-\mathup{\Theta}(\theta))\cdot\mathrm{EAC}(\hat{C})\\}+\mathrm{ACC}(C_{i})$

###### Proof

The expected accumulative time cost of $C_{i}$ is determined by the most time-
comsuming part of the previous subcircuits. Almost $\mathup{\Theta}(\theta)$
portion of the time costs are eliminated as expectation. Considering the decay
of time costs from previous subcircuits and the intra-subcircuit costs, the
lemma can be formulated as follows.

The enhancement of inter-subcircuit costs can be measured using
$\mathrm{EAC}(C_{\text{final}})$ in comparison to
$\sum_{i}\mathrm{ACC}(C_{i})$, where $C_{\text{final}}$ is the last subcircuit
of the circuit.

######  Theorem 0.A.1 (Upper bound of $\mathrm{EAC}(C_{\text{final}})$)

Let $D(C_{i})$ denotes the reverse depth of subcircuit $C_{i}$ counting from
the bottom of the topology of the circuit to the top. For example,
$D(C_{\text{final}})=0$ and $D(C_{0})=D_{\text{max}}$. The upper bound of
$\mathrm{EAC}(C_{\text{final}})$ is described as follows:

$\displaystyle\mathrm{EAC}(C_{\text{final}})\leq\sum_{i}B_{i}(k)\cdot\mathrm{ACC}(C_{i})$

where $B_{i}(k)=\mathup{\Theta}((1-\theta)^{k})$ is the accumulative decay
factor for $C_{i}$.

###### Proof

Iteratively expand the $\mathrm{EAC}(C_{\text{final}})$ from the last
subcircuit to the first. The reverse depth determines the decay factor for the
intra-subcircuit cost. And the $\mathrm{EAC}(C_{\text{final}})$ is bounded by
the weighted sum over the intra costs.

###### Corollary 3

In general, deeper circuits benefit more from skipping schemes.


# Genuinely entangling uncorrelated atoms via Jaynes-Cummings interactions

Mazhar Ali  Department of Electrical Engineering, Faculty of Engineering,
Islamic University Madinah, 107 Madinah, Saudi Arabia

###### Abstract

We study three independent pairs of Jaynes-Cummings systems such that two
atoms might be correlated with each other but the third atom is uncorrelated
with rest. We investigate the conditions under which these uncorrelated three
atoms may become genuinely entangled. We find that this task is impossible if
the cavity interacting with uncorrelated atom share classical correlations
with any other cavity. We observe that atomic state can become genuine
multipartite entangled, at least if the cavity with uncorrelated atom, is
highly entangled with any other cavity. This is an interesting and non-trivial
observation and may serve as another technique to generate multipartite
entangled atoms via JC-interactions. The findings can be realized with
available experimental setups.

###### pacs:

03.65.Yz, 03.65.Ud, 03.67.Mn

##  I Introduction

Quantum theory for atom-field interactions predicted certain peculiar
possibilities which were later observed in experiments. Initial findings were
spontaneous emission of excited atoms interacting with vacuum, collapse and
revival of atomic population, micro-masers, lasers, etc. The simplest model
consist of a two-level atom interacting with quantized electromagnetic field
with strong coupling constant. This so called ”toy” model of matter-field
interaction is well known in literature as Jaynes-Cummings (JC) model. It is
well known that atom-field interaction gives a combined atom-field entangled
state. This single JC-model was extended to ”double-JC” model in which two
independent atoms initially entangled with each other were allowed to interact
only with their own cavities. It was shown that entanglement either oscillated
periodically or exhibited collapse and revival phenomenon depending upon
initial state Yonac-JPB39-2006 . After this study, several authors have
applied this simple model to study quantum correlations of atomic systems or
of field states or for various partitions of double or triple JC-systems Li-
JPB40-2007 ; Man-JPB41-2008 ; Qiang-JPB48-2015 ; Wang-SR7-2017 ; Qiang-
QIP17-2018 ; Ghoshal-PRA101-2020 . In a recent work Qiang-QIP17-2018 , the
authors have studied multipartite concurrence for triple JC model. They have
considered the three two-level atoms to be in a specific genuine multipartite
entangled state such that each atom interacts with their own independent
cavity. They have shown that concurrence of three atoms exhibits collapse and
revivals in a periodic fashion. They have also found that three independent
cavities can become genuinely entangled as entanglement is transferred from
the atoms to cavities. More recently, Ding et. al Ding-arx2020  have taken two
identical two-level atoms in a common cavity undergoing JC interaction and
have shown the freezing and thawing of entanglement in this three qubit
system.

In the current work, we raise and answer a different question which to our
knowledge has not been studied so far. We consider the triple JC model in
which three two-level atoms (as qubits) are independent and uncorrelated with
each other in the start of interaction (in a tensor product state instead of a
genuine entangled state). The two atoms can be correlated with each other but
third atoms is not correlated with other atoms. Similarly, two cavities can
share some correlations but one of cavity is uncorrelated with others. Each of
the atom interacts with its own independent cavity. Collectively, atomic as
well as cavities states are uncorrelated. In particular, we do not have any
genuine entanglement in the system at the start. We ask the question that
whether it is possible to entangle all three atoms such that the resulting
atomic state is not bi-separable. Surprisingly, we find that three atoms can
become genuinely entangled. However, this influence is only possible whenever
the cavity containing uncorrelated atom must share an entangled state with any
of other two cavities. We show that it is impossible for three atoms to become
genuinely multipartite entangled, if the cavity containing uncorrelated atom
share only classical correlations with any other cavity. We also explore the
possibility of uncorrelated atom to get entangled with either of the other two
atoms. We find that two atoms which are interacting independently with their
cavities (correlated ones) may get entangled, however, we find no evidence of
entanglement between the atom in uncorrelated cavity with the uncorrelated
atom. We also find that although classical correlations shared between two
cavities can not support genuine entanglement among three atoms, nevertheless,
there do exist other kinds of quantum correlations among three atoms, and
among any pair of atoms. We aim to study such quantum correlations in a
separate report.

This paper is organized as follows. In section II, we briefly describe our
model of interaction, equation of motion and the method to obtain the general
solution. We review the concept of separability, bi-separability, and genuine
entanglement in section III, where we also describe the criteria to detect
such correlations in time evolved atomic state. We present our findings in
section IV and provide a summary of our work in section V.

##  II Triple Jaynes-Cummings interactions: Model and equation of motion

In this section, we illustrate our physical model and the basic equation of
motion. We consider three two-level atoms (qubits) $A$, $B$, and $C$, such
that each atom is interacting with its own cavity $X$, $Y$, and $Z$,
respectively. Figure 1 shows this triple JC system. We assume that neither the
atoms nor the cavities have any direct interaction among themselves. This
means that each JC system is independent and have no direct interaction with
other JC systems. We allow initial correlations between atoms $A$ and $B$ as
well as between cavities $Y$ and $Z$. Atom $C$ (and cavity $X$) is
uncorrelated with other atoms (cavities) at the start. We will show below that
these correlations are responsible for some interesting dynamics in this
system. In the absence of such correlations, three JC systems would be
completely uncoupled and time evolution of such triple JC system would not
develop any correlations with other parts of the system.

Figure 1: (Color online) Three two level atoms, $A$, $B$, and $C$ are
interacting with cavities $X$, $Y$, and $Z$, respectively. There is no direct
interaction among atoms as well as cavities.

We take atoms $A$ and $B$ to be in Werner states, whereas the third atom $C$
is uncorrelated with rest of the system at the start of the interaction. The
initial combined state of three atoms can be written as

$\displaystyle\varrho^{ABC}(0)=\varrho^{AB}\otimes\varrho^{C}\,,$ (1)

where the state of atoms $A$ and $B$ is given as

$\displaystyle\varrho^{AB}=\alpha\,|\psi^{-}\rangle\langle\psi^{-}|+\frac{1-\alpha}{4}\,\mathbb{I}_{4}\,,$
(2)

with $|\psi^{-}\rangle=1/\sqrt{2}(|0,1\rangle-|1,0\rangle)$ is one of
maximally entangled Bell state, $\mathbb{I}_{4}$ is identity matrix, and
$0\leq\alpha\leq 1$. It is clear that atoms $A$ and $B$ would be sharing only
classical correlations for $\alpha=0$. For $0<\alpha\leq 1/3$, the atoms also
share some quantum correlations (like quantum discord, or local quantum
uncertainty, etc) and in addition, two atoms are entangled for $1/3<\alpha\leq
1$. It is sufficient to take the third atom in state

$\displaystyle\varrho^{C}=|\phi\rangle\langle\phi|\,,$ (3)

with $\phi=\beta\,|0\rangle+\sqrt{1-\beta^{2}}\,|1\rangle$, (with
$0\leq\beta\leq 1$) which is a superposition of ground and excited state for
atom $C$. Similarly, we allow cavities $Y$ and $Z$ to share correlations with
each other but cavity $X$ is uncorrelated with any atom or cavity at the start
of interactions. The combined state of three cavities can be written as

$\displaystyle\varrho^{XYZ}(0)=\varrho^{X}\otimes\varrho^{YZ}\,,$ (4)

where we have defined the state of cavities $Y$ and $Z$ similar to atomic
state $\varrho^{AB}$ as

$\displaystyle\varrho^{YZ}=\gamma\,|\psi^{-}\rangle\langle\psi^{-}|+\frac{1-\gamma}{4}\,\mathbb{I}_{4}\,,$
(5)

with $0\leq\gamma\leq 1$, and

$\displaystyle\varrho^{X}=|\zeta\rangle\langle\zeta|\,,$ (6)

with $\zeta=\kappa\,|0\rangle+\sqrt{1-\kappa^{2}}\,|1\rangle$
($0\leq\kappa\leq 1$), which is a superposition of zero and single excitation
in cavity $X$. The initial combined state of three atoms and three cavities is
given as

$\varrho_{XYZ}^{ABC}(0)=\varrho^{ABC}\otimes\varrho^{XYZ}\,.$ (7)

It is clear from this situation that if cavity $Z$ share no correlations of
any kind with other two cavities, then the single JC system (atom $C$ \+
cavity $Z$) would have nothing to do with the rest of atoms and cavities. So
the only way for other atoms and cavities to ”talk” with atom $C$ is via
correlations, which cavity $Z$ may share in the system. We are interested in
the following questions: Is it possible that atomic state $\varrho^{ABC}(t)$
can become genuine multipartite entangled (defined in next section)? If yes,
then what kind of correlations (classical, discord or entanglement) the cavity
$Z$ must share with cavity $Y$ for this phenomenon to happen? In addition, we
can also ask under what conditions, atom $C$ can be entangled with any of the
other two atoms, $A$ or $B$? To answer these questions, we must first describe
the interaction model of atom and field.

The Hamiltonian describing this interaction can be written as Qiang-QIP17-2018

$\displaystyle\hat{H}$ $\displaystyle=$
$\displaystyle\hbar\sum_{k=A,B,C}\,\bigg{[}\nu_{k}\hat{a_{k}}^{\dagger}\hat{a}_{k}+\frac{\omega_{k}}{2}\sigma_{z}^{k}+g_{k}(\hat{a}_{k}^{\dagger}\sigma_{-}^{k}+\hat{a}_{k}\sigma_{+}^{k})\,,\bigg{]}$
(8)

where $\nu_{k}$ is the field frequency, $\omega_{k}$ is the energy difference
between two atomic levels, $g_{k}$ is the atom-field coupling constant,
$\hat{a}_{k}^{\dagger}(\hat{a}_{k})$ is the creation (annihilation) operator
for the cavity field, $\sigma_{z}^{k}=|1_{k}\rangle\langle
1_{k}|-|0_{k}\rangle\langle 0_{k}|$, and $\sigma_{+}^{k}=|1_{k}\rangle\langle
0_{k}|(\sigma_{-}^{k}=|0_{k}\rangle\langle 1_{k}|)$ is the atomic raising
(lowering) operator. For greater simplicity in calculations and notations, we
have considered the zero detuning $\Delta=\nu_{k}-\omega_{k}=0$, also called
resonance condition. In the unitary time evolution method, we can write (for
any single atom-field interaction)

$\hat{U}_{k}=e^{-i\,\frac{\mathcal{H}_{k}\,t}{\hbar}}\,,$ (9)

where $\mathcal{H}_{k}$ is the Hamiltonian in interaction picture. This
unitary operator can be written as Scully-Zubairy

$\displaystyle\hat{U}_{k}=\cos(g_{k}t\sqrt{\hat{a}_{k}^{\dagger}\hat{a}_{k}+1})|1_{k}\rangle\langle
1_{k}|+\cos(g_{k}t\sqrt{\hat{a}_{k}^{\dagger}\hat{a}_{k}})|0_{k}\rangle\langle
0_{k}|$
$\displaystyle-i\frac{\sin(g_{k}t\sqrt{\hat{a}_{k}^{\dagger}\hat{a}_{k}+1})}{\sqrt{\hat{a}_{k}^{\dagger}\hat{a}_{k}+1}}\hat{a}_{k}|1_{k}\rangle\langle
0_{k}|-i\frac{\sin(g_{k}t\sqrt{\hat{a}_{k}^{\dagger}\hat{a}_{k}+1})}{\sqrt{\hat{a}_{k}^{\dagger}\hat{a}_{k}+1}}\hat{a}_{k}^{\dagger}|0_{k}\rangle\langle
1_{k}|\,.$ (10)

The time evolution of an arbitrary initial atom-field state evolves as
$\varrho(t)=\hat{U}_{k}\,\varrho(0)\hat{U}_{k}^{\dagger}$, where $\varrho(0)$
is the initial state of a two-level atom and a cavity. In our case, the
combined state of three atoms and their respective cavities evolve as

$\displaystyle\varrho_{XYZ}^{ABC}(t)=\mathcal{U}\,(\varrho^{ABC}\otimes\varrho^{XYZ})\,\mathcal{U}^{\dagger}\,,$
(11)

where
$\mathcal{U}=\hat{U}_{k}^{A}\otimes\hat{U}_{k}^{B}\otimes\hat{U}_{k}^{C}$ is
the combined unitary operator modeling the interaction of each atom-field
pair. The density matrix of three atoms only can be obtained by taking partial
traces over cavities, that is,

$\displaystyle\varrho^{ABC}(t)=Tr_{XYZ}\big{[}\,\varrho_{XYZ}^{ABC}(t)\,\big{]}\,.$
(12)

In fact we can partial trace over any systems to obtain the density matrix for
the remaining parties. The general solution is simple to obtain, however, the
calculations are quite tedious and lengthy as it is well known for Jaynes-
Cummings interactions. Due to this reason, we do not provide the general
solution here.

##  III Detection of separability, bi-separability, and genuine multipartite
entanglement

For bipartite systems a given quantum state can be either entangled or
separable, whereas for multipartite systems it is not that much simple. It is
well known that a given multipartite state can be either fully separable, bi-
separable or genuinely entangled. This last possibility is the peculiarity of
multipartite systems. For bipartite states if the partial transpose with
respect to any part of a density matrix is negative then the state is
guaranteed to be entangled, whereas for multipartite states it is known that
there are quantum states which have negative partial transpose with respect to
all bipartitions, nevertheless are not genuinely entangled Horodecki-RMP-2009
; gtreview .

Here, we briefly present some of the criteria to detect multipartite
correlations. It is sufficient to consider three qubits $A$, $B$, and $C$,
with obvious extension to $N$ parties and higher dimensions. A three-qubit
state is called fully separable if it can be written as
$\varrho^{fs}=\sum_{i}p_{i}\varrho^{A}\otimes\varrho^{B}\otimes\varrho^{C}$. A
pure state is bi-separable if
$|\psi^{bs}\rangle=|\phi^{A}\rangle|\phi^{BC}\rangle$, where
$|\phi^{BC}\rangle$ is a possible entangled state for $BC$ and same for other
bipartitions. A mixed state is bi-separable if it can be written as
$\varrho^{bs}=\sum_{j}p_{j}|\phi_{j}^{bs}\rangle\langle\phi_{j}^{bs}|$ for all
three bipartitions. Finally a state is said to be genuine entangled if it is
not bi-separable Bastian-PRL106-2011 .

The definitions are easy but to find out that a given quantum state is fully
separable, bi-separable or genuine entangled is a hard task. Some known
conditions are as follows: Let $\varrho$ is a bi-separable three-qubit state
then its matrix elements always satisfy the condition Guehne-NJP-2010

$|\varrho_{18}|\leq\sqrt{\varrho_{22}\varrho_{77}}+\sqrt{\varrho_{33}\varrho_{66}}+\sqrt{\varrho_{44}\varrho_{55}}$
(13)

whereas violation mean three-qubit state is genuinely entangled. The other
variant of the same criterion is
$|\varrho_{27}|\leq\sqrt{\varrho_{11}\varrho_{88}}+\sqrt{\varrho_{33}\varrho_{66}}+\sqrt{\varrho_{44}\varrho_{55}}$,
etc. Another relevant criterion for our work is the observation that for
three-qubit bi-separable state, it holds that

$\displaystyle|\varrho_{23}|+|\varrho_{25}|+|\varrho_{35}|\leq\sqrt{\varrho_{11}\varrho_{44}}+\sqrt{\varrho_{11}\varrho_{66}}+\sqrt{\varrho_{11}\varrho_{77}}$
$\displaystyle+\frac{1}{2}(\varrho_{22}+\varrho_{33}+\varrho_{55})\,,$ (14)

and violation means genuine entanglement. A full separability condition
related with this criterion is

$\displaystyle|\varrho_{23}|+|\varrho_{25}|+|\varrho_{35}|\leq\sqrt{\varrho_{11}\varrho_{44}}+\sqrt{\varrho_{11}\varrho_{66}}+\sqrt{\varrho_{11}\varrho_{77}}\,.$
(15)

It should be mentioned here that these conditions are not necessary and
sufficient. This means if a given quantum state does not violate bi-
separability conditions, then we can not say with certainty that state is bi-
separable.

Detection of genuine entanglement Bastian-PRL106-2011  can be based on using
positive partial transpose (PPT) mixtures. A bipartite state is PPT if its
partially transposed matrix has no negative eigenvalues. It is known that
separable states are always PPT peresppt . The set of separable states with
respect to some partition is therefore contained in a larger set of states
which has a positive partial transpose for that bipartition. Let
$\varrho_{A|BC}^{PPT}$, $\varrho_{B|CA}^{PPT}$, and $\varrho_{C|AB}^{PPT}$ are
PPT states with partitions shown. Then if a state can be written as

$\displaystyle\varrho^{PPTmix}=p_{1}\,\varrho_{A|BC}^{PPT}+p_{2}\,\varrho_{B|AC}^{PPT}+p_{3}\,\varrho_{C|AB}^{PPT}\,,$
(16)

then it is called a PPT mixture. As any bi-separable state is a PPT mixture,
therefore any state which is not a PPT mixture is guaranteed to be genuinely
entangled. PPT mixtures can be fully characterized by semidefinite programming
(SDP), and the set of PPT mixtures is a very good approximation to the set of
bi-separable states. However, it should be noted that there are genuine
entangled states which are PPT mixtures Bastian-PRL106-2011 . So if the below
measure is positive for a given state then it is guaranteed to be genuine
entangled, if not then we can not say with certainty whether the state is bi-
separable or genuinely entangled.

It was proved Bastian-PRL106-2011  that a state is a PPT mixture iff the
following optimization problem

$\displaystyle\min{\rm Tr}(\mathcal{W}\varrho)$ (17)

with constraints that for all bipartition $M|\bar{M}$

$\displaystyle\mathcal{W}=P_{M}+Q_{M}^{T_{M}},\quad\mbox{ with }0\leq
P_{M}\,\leq 1\mbox{ and }0\leq Q_{M}\leq 1\,$ (18)

has a positive solution. The constraints just state that the considered
operator $\mathcal{W}$ is a decomposable entanglement witness for any
bipartition. If this minimum is negative, then $\varrho$ is not a PPT mixture
and hence is genuinely multipartite entangled. The absolute value of the this
minimization is an entanglement monotone for genuine entanglement Bastian-
PRL106-2011 . We denote the measure by $E(\varrho)$. For bipartite systems,
this monotone is equivalent to negativity Vidal-PRA65-2002 , whereas for
multipartite systems, it can be called genuine negativity.

##  IV Results

In this section, we present two key observations. First, by taking correlated
cavities and atoms to be in entangled state, we demonstrate that three atoms
can achieve genuine entangled state. Second, we show explicitly that if
cavities $Y$ and $Z$ are classically correlated then resulting state of three
atoms is bi-separable. However, if cavities are quantum correlated, then we
can not comment on entanglement properties of atomic state. However, based on
relative difference between diagonal and off-diagonal matrix elements, we
guess it to be bi-separable.

Let us take atoms $A$ and $B$ (as well as cavities $Y$ and $Z$) to be
entangled. Although this can be achieved by taking parameter $\alpha>1/3$
($\gamma>1/3$), however, we set them larger than $0.9$ to demonstrate the
genuine entanglement. As the atom $C$ develops entanglement with cavity $Z$
once the interaction is on, we expect that it can also develop entanglement
with other atoms via this indirect interaction. This is precisely what we
observe in Figure (2), where genuine entanglement for three atoms is plotted
against parameter $gt$ for various settings of parameters $\alpha$ and
$\gamma$. We set $\beta=\kappa=1/\sqrt{2}$ for simplicity, although we can
take any other range as well. We conclude two main results from this figure.
First, it is a clear demonstration that it is possible to genuinely entangle
three uncorrelated atoms via JC-interactions. Second, numerical value of
genuine entanglement for state $\varrho_{ABC}(t)$ depends on $\alpha$ and
$\gamma$ as we decrease these parameters, genuine entanglement is also
decreased but periodic behavior is similar. However, we want to clarify again
that this measure of genuine entanglement is not a necessary and sufficient
condition. This means wherever, the measure vanishes, it is not possible for
us to comment whether the quantum state is bi-separable or not. Figure (2)
strictly demonstrate the development of genuine entanglement among three
atoms.

Figure 2: (Color online) genuine entanglement for three atoms is plotted
against parameter $gt$ for various settings of parameters $\alpha$ and
$\gamma$. We can see that all three atoms become genuinely entangled. See text
for details.

Now we check entanglement between atoms $B$ and $C$. We mentioned earlier that
entanglement monotone in this case is equal to negativity for qubit-qubit
systems (which is necessary and sufficient condition for entanglement). Figure
(3) shows entanglement developed between atoms $B$ and $C$. We observe the
similar periodic behavior for different settings of parameters $\alpha$ and
$\gamma$, with numerical value of negativity decreasing with decreasing them.

Figure 3: (Color online) Negativity is plotted for quantum state of atoms $B$
and $C$ for various settings of $\alpha$ and $\gamma$.

We have not detected any entanglement developed between atoms $A$ and $C$ for
any range of parameters $\alpha$ and $\gamma$. Although some quantum
correlations are developed between atoms $A$ and $C$, however, we have not
computed them.

Next, we examine the initial conditions where only classical correlations are
shared by atoms $A$ and $B$ (also among cavities $Y$ and $Z$). This can be
achieved by taking parameters $\alpha=\gamma=0$. In this case, we have the
following observations: All of the off-diagonal elements related with GHZ-type
genuine entanglement are zero, that is,
$\varrho_{18}(t)=\varrho_{27}(t)=\varrho_{36}(t)=\varrho_{45}(t)=0$, hence no
GHZ-type entanglement. For W-type entanglement, we have the following
observation. Some of the important off-diagonal elements are also zero, like
$\rho_{23}(t)=\rho_{35}(t)=\rho_{46}(t)=\rho_{67}(t)=0$. The only nonzero
important matrix elements are $\rho_{25}(t)$ and $\rho_{47}(t)$, however their
absolute value is far low and criteria (14) and (15) always hold. In addition,
$\varrho_{ABC}(\alpha=\gamma=0)(t)$ can be written as convex combination of
bi-separable states, that is, we have been able to write the density matrix as

$\varrho_{ABC}(\alpha=\gamma=0)(t)=\tilde{p}_{1}(t)\,\varrho^{1}_{AC}\otimes|0\rangle_{B}\langle
0|+\tilde{p}_{2}(t)\,\varrho^{2}_{AC}\otimes|1\rangle_{B}\langle 1|\,,$ (19)

where $\tilde{p}_{1}(t)+\tilde{p}_{2}(t)=1$. This clearly demonstrate that
when both atoms $A$ and $B$ and cavities $Y$ and $Z$ are initially classical
correlated then there is no way that all three atoms can develop genuine
entanglement.

We want to mention here that even classical correlations among cavities $Y$
and $Z$ are sufficient to generate some quantum correlations among atoms $A$
and $C$. As we find that in density matrix $\varrho_{AC}(t)$, with $\beta\neq
0,1$, and $\kappa\neq 0,1$, all off-diagonal elements are strictly non-zero.
The presence of these off-diagonal matrix elements are sufficient to suggest
the development of some kind of quantum correlations among atoms $A$ and $C$.
We have found that there is no entanglement generated between any pair of
atoms.

Finally, we consider the initial conditions when atoms $A$ and $B$ (similarly
cavities $Y$ and $Z$) are not entangled but quantum correlated, that is,
$0<\alpha\leq 1/3$ ($0<\gamma\leq 1/3$). We observed that right hand sides of
criteria (13), (14) are far greater than respective left hand sides. Genuine
negativity is also zero for this range of parameters. Therefore, we are unable
to comment about genuine entanglement of three atoms with certainty, however,
we suspect that resulting states are bi-separable. In addition, we have not
detected any entanglement among any pair of atoms as well.

##  V Discussions

We explored the triple JC-model for the possibility of generating multipartite
entanglement among uncorrelated atoms. By considering a realistic situation,
we examined in detail that under what conditions we can entangle three atoms
non-trivially. We found that three atoms can be genuinely entangled if the two
cavities and two atoms share entanglement. However, to demonstrate this
possibility, we took the correlated cavities with a high fraction of pure
entangled states. For lower fractions, it is not easy to comment on
entanglement properties of resulting states. We demonstrated explicitly that
classically correlated cavities can not lead to a genuine entangled state for
three atoms. In addition, based on density matrix for any pair of atoms, we
found that even classical correlated cavities can generate quantum
correlations among uncorrelated atoms. However, classical correlations among
cavities can not generate even bipartite entanglement as we do not find any
pair of atoms to be in an entangled state. We allowed only indirect influence
via the correlations shared between two cavities. Finally, for the case when
correlated cavities and atoms are quantum correlated, we could not figure out
the entanglement properties of resulting state with certainty. Our results
provide an option to generate genuine entangled atoms via JC-systems with no
genuine entanglement at the start. We have present a scheme in which bipartite
entanglement can be turned into multipartite entanglement. Our findings can be
verified with the available experimental setups.

###### Acknowledgements.

The author is grateful to Dr. Farhan Saif for valuable discussions and Dr. S.
H. Dong for sharing their work.

## References

  * (1) M. Yönac, T. Yu and J. H. Eberly, J. Phys. B At. Mol. Opt. 39, S621 (2006).
  * (2) Z. J. Li, J. Q. Li, Y. H. Jin, and Y. H. Nie, J. Phys. B At. Mol. Opt. 40, 3401 (2007).
  * (3) Z. X. Man, Y. J. Xia, and N. B. An, J. Phys. B At. Mol. Opt. 41, 155501 (2008).
  * (4) W-C. Qiang, L. Zhang, and H-P. Zhang, J. Phys. B At. Mol. Opt. 48, 245503 (2015).
  * (5) D. Wang, A. J. Huang, R. D. Hoehn, F. Ming, W. Y. Sun, J. D. Shi, L. Ye, and S. Kais, Sci. Rep. 7, 1066 (2017).
  * (6) W-C. Qiang, G-H. Sun, Q. Dong, O. Camacho-Nieto, and S-H. Dong, Quantum Inf Process 17, 90 (2018).
  * (7) A. Ghoshal, S. Das, A. Sen De, and U. Sen, Phys. Rev. A 101, 053805 (2020).
  * (8) Y. Ding, S. Xie, and J. H. Eberly, arXiv: 2009.12440v1 (2020).
  * (9) M. O. Scully, and M. S. Zubairy, Quantum Optics, Cambridge University Press (1997).
  * (10) R. Horodecki et al., Rev. Mod. Phys. 81, 865 (2009).
  * (11) O. Gühne and G. Tóth, Phys. Rep. 474, 1 (2009).
  * (12) B. Jungnitsch, T. Moroder, and O. Gühne, Phys. Rev. Lett. 106, 190502 (2011); L. Novo, T. Moroder, and O. Gühne, Phys. Rev. A 88, 012305 (2013); M. Hofmann, T. Moroder, and O. Gühne, J. Phys. A: Math. Theor. 47, 155301 (2014).
  * (13) O. Gühne, and M. Seevinck, New. J. Phys. 12, 053002 (2010); O. Gühne, Phys. Lett. A 375, 406 (2011).
  * (14) A. Peres, Phys. Rev. Lett. 77, 1413 (1996).
  * (15) G. Vidal and R.F. Werner, Phys. Rev. A 65 032314 (2002).