Execute $\prot{\Sh}(P_i, \vl{p}_i)$ to generate $\shr{\vl{p}_i}$.

* Compute $\shr{\vl{o}} = \shr{\vl{p}_1} + \shr{\vl{p}_2}$. Here $\vl{o} = \vl{z}^{\vl{t}}$ if $\isTr = 1$ and $\vl{z}$ otherwise.

Protocol $\prot{\dotp}$ (fig:piDotP2pcS) (in $\TWthis$) requires $2 \vl{d} \ell (\csec + \ell)$ bits of communication in the preprocessing, and $1$ round and $2 \ell$ bits of communication in the online phase.

§.§ Bit Extraction

To compute most significant bit ($\msb$) of the value $\vl{v}$, note that $\vl{v} = (\mk{\vl{v}} - \pad{\vl{v}}{1}) + (- \pad{\vl{v}}{2})$ as per the sharing semantics (cf. 2pcSsharing). $P_2$ generates the boolean sharing of $- \pad{\vl{v}}{2}$ during the preprocessing, while $P_1$ generates $\shrB{(\mk{\vl{v}} - \pad{\vl{v}}{1})}$ during the online phase using sharing protocol. Parties compute the result by evaluating the bit extraction circuit <cit.>.

§.§ Bit to Arithmetic

Protocol $\prot{\bitA}(\shrB{\bitb})$ (fig:2pcSpiBitA) enables computing $\shr{\bitb}$ of a bit $\bitb$ given its boolean sharing $\shrB{\bitb}$. Let $\arval{\bitb}$ denotes the value of $\bitb \in \bitset$ over the arithmetic ring $\Z{\ell}$. Using our sharing semantics,

\begin{equation}
\label{eq:2pcSbitA}
\arval{\bitb} = \arval{(\mk{\bitb} \xor \pad{\bitb}{})} = \arval{\mk{\bitb}} + \padR{\bitb}(1-2\arval{\mk{\bitb}})
\end{equation}

During the preprocessing, parties interactively generate $\sqr{\cdot}$-sharing of $\padR{\bitb}$ using steps similar to that of $\prot{\MultPre}$. The online phase consists of each $P_1$ and $P_2$ locally computing an additive sharing of $\arval{\bitb}$, generating the corresponding $\shr{\cdot}$-sharing using $\prot{\Sh}$, and locally adding the shares to obtain $\shr{\bitb}$.

Now we describe how to generate $\sqr{\padR{\bitb}}$ in the preprocessing. Since $\pad{\bitb}{} = \pad{\bitb}{1} \xor \pad{\bitb}{2}$, we can write $\padR{\bitb} = \padR{\bitb_1} + \padR{\bitb_2} - 2 \padR{\bitb_1} \padR{\bitb_2}$.

Parties execute $\COT{1}{\ell}$ with $P_1$ being the sender and $P_2$ being the receiver. $P_1$ inputs the correlation $f(x) = x + \padR{\bitb_1}$ and obtains $(m_{0} = r, m_{1} = r + \padR{\bitb_1})$. $P_2$ inputs $c = \pad{\bitb}{2}$ as the choice bit and obtains $m_{c}$ as output. Now the $\sqr{\cdot}$-shares are defined as $\sqr{\padR{\bitb_1} \padR{\bitb_2}}_1 = -r$ and $\sqr{\padR{\bitb_1} \padR{\bitb_2}}_2 = m_{\pad{\bitb}{2}}$.

$\prot{\bitA}(\shrB{\bitb})$Bit to Arithmetic conversion in $\TWthis$.fig:2pcSpiBitA

Input(s): $\shrB{\bitb}$,   Output: $\shr{\vl{y}} = \shr{\arval{\bitb}}$.

* Generating $\sqr{\cdot}$-shares of $\padR{\bitb_1} \padR{\bitb_2}$:

* Execute $\COT{1}{\ell}$ with $P_1$ being the sender with input $f(x) = x + \padR{\bitb_1}$ and $P_2$ being the receiver with input $c = \pad{\bitb}{2}$.

* $P_1$ obtains $(m_{0} = r, m_{1} = r + \padR{\bitb_1})$ while $P_2$ obtains $m_{c}$.

* Set $\sqr{\padR{\bitb_1} \padR{\bitb_2}}_1 = -r$ and $\sqr{\padR{\bitb_1} \padR{\bitb_2}}_2 = m_{c}$.

* $P_i$ for $i \in \{1,2\}$ locally computes $\sqr{\padR{\bitb}}_i = \padR{\bitb_i} - 2 \sqr{\padR{\bitb_1} \padR{\bitb_2}}_i$.

* Locally compute:
$P_1: \vl{y}_1  =  \arval{\mk{\bitb}} + \sqr{\padR{\bitb}}_1 (1 - 2\arval{\mk{\bitb}})~~\Big|~~
P_2:  \vl{y}_2  =  \sqr{\padR{\bitb}}_2 (1 - 2\arval{\mk{\bitb}})$

* $P_i$ for $i \in \{1,2\}$ executes $\prot{\Sh}$ on $\vl{y}_i$ to generate the respective $\shr{\cdot}$-shares.

* Compute $\shr{\vl{y}} = \shr{\vl{y}_1} + \shr{\vl{y}_2}$.

Protocol $\prot{\bitA}$ (fig:2pcSpiBitA) requires $\csec + \ell$ bits of communication in preprocessing, and $1$ round and $2 \ell$ bits of communication in the online phase.

During preprocessing, generation of $\sqr{\padR{\bitb}}$ involves one instance of $\COT{1}{\ell}$. The online phase involves two instances of arithmetic sharing protocol  in parallel, resulting in $1$ round and a communication of $2\ell$ bits.

§.§.§ Bit to Arithmetic:II

Similar to $\prot{\bitA}$ protocol, given the boolean sharings $\shrB{\bitb_1}, \shrB{\bitb_2}$, protocol $\prot{\dbitA}$ computes the arithmetic sharing of $\arval{(\bitb_1 \bitb_2)}$. Let $\Delta_{\bitb_1}$, $\Delta_{\bitb_2}$  denote the value $(1-2\arval{\mk{\bitb_1}})$, $(1-2\arval{\mk{\bitb_2}})$ respectively. Using (<ref>), we can write

\begin{align}
\label{eq:2pcSdbitA}
\arval{(\bitb_1 \bitb_2)} &= \arval{(\mk{\bitb_1} \xor \pad{\bitb_1}{})} \arval{(\mk{\bitb_2} \xor \pad{\bitb_2}{})}
= (\arval{\mk{\bitb_1}} + \padR{\bitb_1}\Delta_{\bitb_1}) (\arval{\mk{\bitb_2}} + \padR{\bitb_2}\Delta_{\bitb_2}) \nonumber \\
&= \arval{\mk{\bitb_1}}\arval{\mk{\bitb_2}} + \padR{\bitb_1}\arval{\mk{\bitb_2}}\Delta_{\bitb_1} + \padR{\bitb_2}\arval{\mk{\bitb_1}}\Delta_{\bitb_2} + \arval{(\pad{\bitb_1}{}\pad{\bitb_2}{})}\Delta_{\bitb_1}\Delta_{\bitb_2}
\end{align}

During preprocessing, the $\sqr{\cdot}$-shares of $\padR{\bitb_1}$, and $\padR{\bitb_2}$ are computed similar to that of $\prot{\bitA}$ (fig:2pcSpiBitA). In parallel, parties execute $\prot{\MultPre}$ on the boolean $\sqr{\cdot}$-shares of $\pad{\bitb_1}{}$ and $\pad{\bitb_2}{}$ to generate $\sqr{\gm{\bitb_1 \bitb_2}{}} = \sqr{\pad{\bitb_1}{}\pad{\bitb_2}{}}$ in boolean form. Once $\sqr{\gm{\bitb_1 \bitb_2}{}}$ is generated, parties compute the $\sqr{\cdot}$-shares of its arithmetic equivalent similar to that of $\prot{\bitA}$.

The online phase is similar to that of $\prot{\bitA}$ protocol.

Protocol $\prot{\dbitA}$ requires $5\csec + 3\ell + 2$ bits of communication in preprocessing, and $1$ round and $2 \ell$ bits of communication in the online phase.

§.§ Bit Injection

Given the boolean sharing of a bit $\bitb$, denoted as $\shrB{\bitb}$, and the arithmetic sharing of $\vl{v} \in \Z{\ell}$, protocol $\prot{\bitinj}$ computes $\shr{\cdot}$-sharing of $\arval{\bitb}\vl{v}$. Let $\Delta_{\bitb}$ denote the value $(1-2\arval{\mk{\bitb}})$.

Similar to $\prot{\bitA}$,

\begin{align}\label{eq:2pcSbitinj}
\arval{\bitb} \vl{v} &= \arval{(\mk{\bitb} \xor \pad{\bitb}{})}(\mk{\vl{v}} - \pad{\vl{v}}{}) = (\arval{\mk{\bitb}} + \padR{\bitb}\Delta_{\bitb})(\mk{\vl{v}} - \pad{\vl{v}}{}) \nonumber \\
&= \arval{\mk{\bitb}}\mk{\vl{v}} - \arval{\mk{\bitb}}\pad{\vl{v}}{} + \padR{\bitb}\mk{\vl{v}}\Delta_{\bitb} - \padR{\bitb}\pad{\vl{v}}{}\Delta_{\bitb}
\end{align}

During the preprocessing, parties generate the $\sqr{\cdot}$-shares of $\padR{\bitb}$ similar to $\prot{\bitA}$ protocol.

To compute $\padR{\bitb}\pad{\vl{v}}{}$, one naive method is to multiply $\padR{\bitb}$ and $\pad{\vl{v}}{}$ using $\prot{\MultPre}$. The cost can be reduced further as follows. Note that

\begin{align}\label{eq:2pcSbitinjB}
\padR{\bitb}\pad{\vl{v}}{} &= (\padR{\bitb_1} + \padR{\bitb_2} - 2 \padR{\bitb_1} \padR{\bitb_2})(\pad{\vl{v}}{1} + \pad{\vl{v}}{2}) \nonumber \\
&=  \padR{\bitb_1}\pad{\vl{v}}{1} + \padR{\bitb_1}\pad{\vl{v}}{2} + \padR{\bitb_2}\pad{\vl{v}}{1} + \padR{\bitb_2}\pad{\vl{v}}{2} - 2 \padR{\bitb_1} \padR{\bitb_2}\pad{\vl{v}}{1}  - 2 \padR{\bitb_1} \padR{\bitb_2}\pad{\vl{v}}{2}
\end{align}

Here $P_1$ can locally compute $\padR{\bitb_1}\pad{\vl{v}}{1}$ while $P_2$ can compute $\padR{\bitb_2}\pad{\vl{v}}{2}$. The $\sqr{\cdot}$-shares for the remaining four terms can be generated using four instances of $\COT{1}{\ell}$ similar to $\prot{\bitA}$ resulting in a communication of $4(\csec + \ell)$ bits. For instance, to compute $\sqr{\cdot}$-shares of $\padR{\bitb_1} \padR{\bitb_2}\pad{\vl{v}}{1}$, parties engage in an instance of $\COT{1}{\ell}$ with $P_1$ as sender with input $ \padR{\bitb_1}\pad{\vl{v}}{1}$ and $P_2$ as receiver with choice bit $\pad{\bitb_2}{}$.

During the online phase, $P_1$ and $P_2$ compute an additive sharing of $\arval{\bitb} \vl{v}$ and execute $\prot{\Sh}$ on them to generate the respective $\shr{\cdot}$-shares.

Protocol $\prot{\bitinj}$ requires $5(\csec +\ell)$ bits of communication in preprocessing, and $1$ round and $2 \ell$ bits of communication in the online phase.

§.§.§ Sum of Bit Injections

Given $m$ pair of values in the shared form, $\{\shrB{\bitb_i}, \shr{\vl{v}_i}\}_{i \in [m]}$, the goal of $\prot{\bitinjS}$ is to compute the $\shr{\cdot}$-share of $\vl{z} = \sum_{i=1}^{m} \arval{\bitb_i} \cdot \vl{v_i}$. For this, parties execute the preprocessing corresponding to $m$ bit injections of the form $\arval{\bitb_i} \cdot \vl{v_i}$.

In the online phase, each of $P_1$ and $P_2$ locally compute an additive sharing of $\vl{z}_i$, corresponding to $\arval{\bitb_i} \cdot \vl{v_i}$ first. Instead of generating the $\shr{\cdot}$-sharing for each of the $m$ terms, parties locally add the shares and execute $\prot{\Sh}$ on the result. Concretely, parties locally compute $\vl{z}^j = \sum_{i=1}^{m} \vl{z}_i^j$ for $j \in \{1,2\}$ and execute $\prot{\Sh}$ on $\vl{z}^j$ to obtain its $\shr{\cdot}$-sharing. This results in an online communication independent of $m$.

Protocol $\prot{\bitinjS}$ requires $5m (\csec +\ell)$ bits of communication in preprocessing, and $1$ round and $2 \ell$ bits of communication in the online phase.

§.§.§ Bit Injection:II

Similar to $\prot{\bitinj}$ protocol, given $\shrB{\bitb_1}, \shrB{\bitb_2}$ and $\shr{\vl{v}}$, protocol $\prot{\dbitA}$ computes the arithmetic sharing of $\arval{(\bitb_1 \bitb_2)}\vl{v}$. Let $\Delta_{\bitb_1}$, $\Delta_{\bitb_2}$  denote the value $(1-2\arval{\mk{\bitb_1}})$, $(1-2\arval{\mk{\bitb_2}})$ respectively. Using (<ref>) and (<ref>), we can write

\begin{align}
\label{eq:2pcSdbitinj}
\arval{(\bitb_1 \bitb_2)} \vl{v} &= \arval{(\mk{\bitb_1} \xor \pad{\bitb_1}{})} \arval{(\mk{\bitb_2} \xor \pad{\bitb_2}{})} (\mk{\vl{v}} - \pad{\vl{v}}{}) \nonumber \\
&= (\arval{\mk{\bitb_1}} + \padR{\bitb_1}\Delta_{\bitb_1}) (\arval{\mk{\bitb_2}} + \padR{\bitb_2}\Delta_{\bitb_2})(\mk{\vl{v}} - \pad{\vl{v}}{}) \nonumber \\
&= \arval{\mk{\bitb_1}}\arval{\mk{\bitb_2}}\mk{\vl{v}}  + \padR{\bitb_1}\arval{\mk{\bitb_2}}\mk{\vl{v}} \Delta_{\bitb_1} + \padR{\bitb_2}\arval{\mk{\bitb_1}}\mk{\vl{v}}\Delta_{\bitb_2} + \arval{(\pad{\bitb_1}{}\pad{\bitb_2}{})}\mk{\vl{v}}\Delta_{\bitb_1}\Delta_{\bitb_2} \nonumber \\
&~~~- \pad{\vl{v}}{}\arval{\mk{\bitb_1}}\arval{\mk{\bitb_2}} - \padR{\bitb_1}\pad{\vl{v}}{}\arval{\mk{\bitb_2}}\Delta_{\bitb_1} - \padR{\bitb_2}\pad{\vl{v}}{}\arval{\mk{\bitb_1}}\Delta_{\bitb_2} - \arval{(\pad{\bitb_1}{}\pad{\bitb_2}{})}\pad{\vl{v}}{}\Delta_{\bitb_1}\Delta_{\bitb_2}
\end{align}

During preprocessing, the $\sqr{\cdot}$-shares of $\padR{\bitb_1}, \padR{\bitb_2}$ and $\arval{(\pad{\bitb_1}{}\pad{\bitb_2}{})}$ are computed similar to that of $\prot{\dbitA}$. Once the $\sqr{\cdot}$-shares are generated, parties compute $\sgr{\padR{\bitb_1}\pd{\vl{v}}}$ and $\sgr{\padR{\bitb_2}\pd{\vl{v}}}$ using steps similar to $\prot{\bitinj}$.

Using the boolean shares of $\sqr{\pad{\bitb_1}{}\pad{\bitb_2}{}}$ computed as part of  $\sqr{\arval{(\pad{\bitb_1}{}\pad{\bitb_2}{})}}$ and the $\sqr{\cdot}$-shares of $\pad{\vl{v}}{}$, parties compute   the $\sqr{\cdot}$-shares of $\arval{(\pad{\bitb_1}{}\pad{\bitb_2}{})}\pad{\vl{v}}{}$ similar to protocol $\prot{\bitinj}$.

The online phase is similar to that of $\prot{\bitinj}$ protocol.

Protocol $\prot{\dbitinj}$ requires $14\csec + 12\ell + 2$ bits of communication in preprocessing, and $1$ round and $2 \ell$ bits of communication in the online phase.

§.§ Equality Test ($\prot{\eql}$)

To check whether $\vl{a} \iseq \vl{b}$ or not, given $\shr{\vl{a}}, \shr{\vl{b}}$, $\prot{\eql}$ proceeds with parties locally computing $\shr{\vl{y}} = \shr{\vl{a}} - \shr{\vl{b}}$. According to our sharing semantics, $\vl{y}$ can be written as $\vl{y} = \vl{y}_1 - \vl{y}_2$ where $\vl{y}_1 = \mk{\vl{y}} - \pad{\vl{y}}{1}$ and $\vl{y}_2 = \pad{\vl{y}}{2}$. $P_2$ generates $\shrB{\vl{y}_2}$ during the preprocessing while $P_1$ generates $\shrB{\vl{y}_1}$ in the online using $\prot{\Sh}$. Note that $\vl{a} = \vl{b}$ implies $\vl{y}_1 = \vl{y}_2$ and hence all the bits of $\vl{v} = \overline{(\vl{y}_1 \xor \vl{y}_2)}$ should be $1$. As mentioned in the introduction of Part II (<ref>), parties use four input AND gates and a tree structure, where $4$ bits are taken at a time and the AND of them is computed in one go.

§ MIXED PROTOCOL FRAMEWORK

2pcSConv compares our sharing conversions with ABY <cit.>. For uniformity, we consider a function, F, to be computed on an $\ell$-bit inputs $\vl{x}, \vl{y}$ using a garbled circuit (GC) in the mixed framework, which gives an $\ell$-bit output $\vl{z} = \mathsf{F(\vl{x}, \vl{y})}$, where $\ell$ denotes the ring size in bits. Let  $\Grb{F}$  denote the corresponding GC. In the table, $\Grb{Sn}$ denotes a ${\sf n}$-input garbled subtraction circuit; $\Grb{An}$ denotes ${\sf n}$-input garbled addition circuit; $\GrbD{}$ denotes the garbled circuit with decoding information; $\Grb{n_1\times1,\ldots,n_m \times m}$ denotes ${\sf n_i}$ instances of GC $\Grb{i}$ for $i \in \{1,\dots,{\sf m}\}$ and $\Size{\Grb{n_1\times1,\ldots,n_m \times m}}$ denotes its size.

2-1VariantNotations: $\ell$ - size of ring in bits, $\kappa$ - computational security parameter, 'pre' - preprocessing, 'on' - online.
2-1Conversion'A' - arithmetic, 'B' - boolean, 'G' - Garbled.
[c]1-3ABY <cit.>

Comm.pre     Comm.on      Roundson

[c]1-2Comm.pre         Comm.on      Roundson

4-11 GC

A-G-A     $14\ell \kappa + \Size{\Grb{2 \times A2,F}}$     $6\ell\kappa + (\ell^2 + 7\ell)/2$     $4$

[r]4-1($3 \ell \kappa + 2\ell$)
+      $\Size{\GrbD{2 \times S2, A2, F}}$
4-1$2\ell\kappa + \ell$     4-1$2$

A-G-B     $12\ell \kappa + \Size{\Grb{F}}$     $6\ell\kappa + 2\ell$     $2$
$\Size{\GrbD{2 \times S2,F}}$

B-G-A     $14\ell \kappa + \Size{\Grb{F}}$     $4\ell\kappa + (\ell^2 + 7\ell)/2$      $4$

B-G-B     $12\ell \kappa + \Size{\Grb{F}}$     $4\ell\kappa + 2\ell$      $2$

2-1Others$\vl{u_1} = \vl{n_2} + 4\vl{n_3} + 11\vl{n_4}$, $\vl{u_2} = \vl{n_2} + \vl{n_3} + \vl{n_4}$ denote the number of AND gates in the optimized adder circuit <cit.> with 2, 3, 4 inputs, respectively. For $\ell = 64$, $\vl{n_2} = 216, \vl{n_3} = 184, \vl{n_4}=179$.

A-B     $2\ell\log \ell (\kappa + \ell)$      $4\ell\log \ell$     $\log \ell$
[r]1-2$2\vl{u_1} (\kappa + \ell)$          $2\vl{u_2} + \ell$     $1 + \log_4 \ell$

B-A      $2\ell\kappa$      $(\ell^2 + 3\ell) / 2$     $2$
[r]1-2$\ell\kappa + \ell^2$          $2\ell$     $1$

Mixed protocol conversions of ABY <cit.> and $\TWthis$.

§.§ Conversions involving Garbled World

Assume the GC is required to compute a function $f$ on inputs $\vl{x}, \vl{y} \in \Z{\ell}$ and let the output be $f(\vl{x}, \vl{y})$.

Case I: Boolean-Garbled-Boolean

Since the inputs to the GC are available in boolean form, say $\shrB{\vl{x}}, \shrB{\vl{y}}$, parties generate $\shrC{\vl{x}}, \shrC{\vl{y}}$ by invoking the garbled sharing protocol $\pigsh$.

Additionally, $P_1$ samples $\vl{R} \in \Z{\ell}$ to mask the function output, $f(\vl{x}, \vl{y})$, and generate $\shrB{\vl{R}}$ and $\shrG{\vl{R}}$. $P_g = P_1$ garbles the circuit which computes $\vl{z} = f(\vl{x}, \vl{y}) \xor \vl{R}$, and sends the GC along with the decoding information to evaluator $P_2$. Upon GC evaluation and output decoding, $P_2$ obtains $\vl{z} = f(\vl{x}, \vl{y}) \xor \vl{R}$, and boolean share $\vl{z}$ to generate $\shrB{\vl{z}}$. Parties then compute $\shrB{f(\vl{x}, \vl{y})} = \shrB{\vl{z}} \xor \shrB{\vl{R}}$.

Case II: Boolean-Garbled-Arithmetic

This is similar to Case I except that the circuit which computes $\vl{z} = f(\vl{x}, \vl{y}) + \vl{R}$ is garbled instead. Boolean sharing of $\vl{z}$ is replaced with arithmetic, followed by computing $\shr{f(\vl{x}, \vl{y})} = \shr{\vl{z}} - \shr{\vl{R}}$.

Cases III & IV: Input in Arithmetic Sharing

The function to be computed $f(\vl{x}, \vl{y})$, is modified as $f^{\prime}(\mk{\vl{x}}, \pad{\vl{x}}{1}, \pad{\vl{x}}{2}, \mk{\vl{y}}, \pad{\vl{y}}{1}, \pad{\vl{y}}{2}) = f(\mk{\vl{x}}-\pad{\vl{x}}{1}-\pad{\vl{x}}{2}, \mk{\vl{y}}-\pad{\vl{y}}{1}-\pad{\vl{y}}{2})$ where inputs $\vl{x}, \vl{y}$ are replaced by the sets $\{\mk{\vl{x}}, \pad{\vl{x}}{1}, \pad{\vl{x}}{2}, \pad{\vl{x}}{3}\}$, $\{\mk{\vl{y}}, \pad{\vl{y}}{1}, \pad{\vl{y}}{2}, \pad{\vl{y}}{3}\}$. The circuit to be garbled thus, corresponds to the function $f^{\prime}$. Parties generate $\shrG{\mk{\vl{x}}}, \shrG{\pad{\vl{x}}{1}}, \shrG{\pad{\vl{x}}{2}}, \shrG{\mk{\vl{y}}}, \shrG{\pad{\vl{y}}{1}}, \shrG{\pad{\vl{y}}{2}}$ via $\pigsh$, following which, parties proceed with the rest of the computation whose steps are similar to Case I, and II, depending on the requirement on the output sharing.

Function $f^{\prime}$ can be further optimized as $f(\av{\vl{x}}-\pad{\vl{x}}{2}, \av{\vl{y}}-\pad{\vl{y}}{2})$ with $\av{\vl{x}} = \mk{\vl{x}} - \pad{\vl{x}}{1}$ and $\av{\vl{y}} = \mk{\vl{y}} - \pad{\vl{y}}{1}$. Similar optimization can be done for the other garbling instance as well.

§.§ Other Conversions

Arithmetic to Boolean

To convert arithmetic sharing of $\vl{v} \in \Z{\ell}$ to boolean sharing, observe that $\vl{v} = \vl{v}_1 + \vl{v}_2$ where $\vl{v}_1 = \mk{\vl{v}} - \pad{\vl{v}}{1}$ is possessed by $P_1$, while $\vl{v}_2 = - \pad{\vl{v}}{2}$ is possessed by $P_2$. Thus, $\shrB{\vl{v}}$  can be computed as $\shrB{\vl{v}} = \shrB{\vl{v}_1} + \shrB{\vl{v}_2}$. For this, $P_2$ can generate $\shrB{\vl{v}_2}$ in the preprocessing, and $\shrB{\vl{v}_1}$ can be generated in the online by $P_1$. The protocol appears in fig:2pcSpiab. Boolean addition, when instantiated using the adder of <cit.>, requires $\log_4(\ell)$ rounds.

$\piab$Arithmetic to Boolean Conversion in $\TWthis$.fig:2pcSpiab
Preprocessing: $P_2$ generates $\shrB{\vl{v}_2}$ using $\prot{\Sh}$, where $\vl{v}_2 = -\pad{\vl{v}}{2}$.

* $P_1$ generates $\shrB{\vl{v}_1}$ using $\prot{\Sh}$, where $\vl{v}_1 = \mk{\vl{v}} -\pad{\vl{v}}{1}$.

* Parties obtain $\shrB{\vl{v}} = \shrB{\vl{v}_1} + \shrB{\vl{v}_2}$ using a boolean adder circuit.

Boolean to Arithmetic

To convert a boolean sharing of $\vl{v} \in \Z{\ell}$ into an arithmetic sharing, note that

\begin{align*}
\vl{v} = \sum_{i=0}^{\ell - 1} 2^{i} \vl{v}[i] = \sum_{i=0}^{\ell - 1} 2^{i} (\pad{\vl{v}[i]}{} \xor \mk{\vl{v}[i]})
= \sum_{i=0}^{\ell - 1} 2^{i} \left( \arval{\mk{\vl{v}[i]}} +  \padR{\vl{v}[i]} (1 - 2\arval{\mk{\vl{v}[i]}}) \right)
\end{align*}

where $\padR{\vl{v}[i]}, \arval{\mk{\vl{v}[i]}}$ denote the arithmetic value of bits $\pad{\vl{v}[i]}{}, \mk{\vl{v}[i]}$ over the ring $\Z{\ell}$.

For each bit $\vl{v}[i]$ of $\vl{v}$, parties generate the $\sqr{\cdot}$-shares of $\padR{\vl{v}[i]}$ in the preprocessing, similar to $\prot{\bitA}$ (fig:2pcSpiBitA). During the online phase, additive shares for each bit $\vl{v}[i]$ are locally computed similar to $\prot{\bitA}$. Parties then multiply the $i$th share with $2^i$ and locally add up to obtain an additive sharing of $\vl{v}$. The rest of the steps are similar to $\prot{\bitA}$, and the formal protocol appears in fig:2pcSpiba.

$\piba(\Partyset, \shrB{\vl{v}})$Boolean to Arithmetic Conversion in $\TWthis$.fig:2pcSpiba
Let $\vl{v}[i]$ denote the $i$th bit of $\vl{v}$. Let $\vl{p}_i = \arval{\mk{\vl{v}[i]}}$, and $\vl{q}_i = \padR{\vl{v}[i]}$.

* For $i \in \{0, 1, \ldots, \ell-1 \} $, execute the preprocessing of $\prot{\bitA}$ (fig:2pcSpiBitA) for each bit $\vl{v}[i]$, to generate $\sqr{{\vl{q}_i}} = (\sqr{\vl{q}_i}_1 , \sqr{\vl{q}_i}_2 )$.

Online: Let $\vl{y}_i = \arval{(\vl{v}[i])}$ and $\vl{y}$ denotes the arithmetic equivalent of $\vl{v}$.

* Locally compute:

\begin{align*}
P_1: \vl{y}^1 = \sum_{i=0}^{\ell-1} 2^i \vl{y}_i^1  &=  \sum_{i=0}^{\ell-1} 2^i (\vl{p}_i + \sqr{\vl{q}_i}_1 (1 - 2\vl{p}_i)) \\
P_2: \vl{y}^2 = \sum_{i=0}^{\ell-1} 2^i \vl{y}_i^2 &=  \sum_{i=0}^{\ell-1} 2^i ( \sqr{\vl{q}_i}_2 (1 - 2\vl{p}_i))
\end{align*}

* $P_j$ for $j \in \{1,2\}$ executes $\prot{\Sh}$ on $\vl{y}^j$ to generate the respective $\shr{\cdot}$-shares.

* Compute $\shr{\vl{y}} = \shr{\vl{y}^1} + \shr{\vl{y}^2}$.

Layer III: Applications

CHAPTER: INTRODUCTION TO LAYER III

Solutions to privacy-preserving machine learning via MPC have been looked at in various works <cit.>. Our work considers PPML algorithms such as linear regression, logistic regression, deep neural networks (NN) and support vector machines (SVM) for benchmarking. We consider both the training and inference phases of all the algorithms except SVM. The training phase of SVM requires additional tools and primitives and is out of the scope of this work. We first give an overview of the ML algorithms, followed by the architectural details of the neural networks and support vector machine that we consider for benchmarking and the corresponding datasets.

§ OVERVIEW OF ML ALGORITHMS

Here we provide an overview of ML algorithms and the detailed benchmarking results. The training phase in most machine learning algorithms consists of two stages– i) forward propagation, where the model computes the output, and ii) backward propagation, where the model parameters are adjusted according to the computed output and the actual output. We define one iteration in the training phase as one forward propagation followed by a backward propagation. We refer readers to <cit.> for formal details.

§.§ Linear Regression

For linear regression, one iteration can be viewed as updating the weight vector $\vct{w}$ using the Gradient Descent algorithm (GD). The update function for $\vct{w}$ is given by

\begin{align*}
\vct{w} = \vct{w} - \frac{\alpha}{B} \Mat{X}_i^{T}  \circ (\Mat{X}_i \circ \vct{w} -\Mat{Y}_i)
\end{align*}

where $\alpha$ denotes the learning rate and $\Mat{X}_i$ denotes a subset of batch size $B$, randomly selected from the entire dataset in the $i$th iteration. Here the forward propagation consists of computing $\Mat{X}_i \circ \vct{w}$, while the weight vector is updated in the backward propagation. The update function consists of a series of matrix multiplications, which can be achieved using dot product protocols. The operations of subtraction, as well as multiplication by a public constant, can be performed locally. We observe that the update function as mentioned above can be computed entirely in the arithmetic domain and can be viewed in the form of $\shr{\cdot}$-shares as

\begin{align*}
\shr{\vct{w}} = \shr{\vct{w}} - \frac{\alpha}{B} \shr{\Mat{X}_j^{T}}  \circ (\shr{\Mat{X}_j} \circ \shr{\vct{w}}-\shr{\Mat{Y}_j})
\end{align*}

§.§ Logistic Regression

The iteration for the case of logistic regression is similar to that of linear regression, apart from an activation function being applied on $\Mat{X}_i \circ \vct{w}$ in the forward propagation. We instantiate the activation function using the sigmoid function. The update function for $\vct{w}$ is given by

\begin{align*}
\vct{w} = \vct{w} - \frac{\alpha}{B} \Mat{X}_i^{T}  \circ \left(\sig(\Mat{X}_i \circ \vct{w})-\Mat{Y}_i\right)
\end{align*}

One iteration of logistic regression incurs an additional cost for computing $\sig(\Mat{X}_j  \circ {\vct{w}})$ as compared with that for linear regression.

§.§ Neural Networks

A neural network can be divided into various layers, where each layer contains a predefined number of nodes. These nodes are a linear function composed of a non-linear “activation” function. The nodes at the input layer or the first layer are evaluated on the input features to evaluate a neural network. The outputs from these nodes are fed as inputs to the nodes in the next layer. This process is repeated for all the layers to obtain the output. The underlying operation involved is the computation of activation matrices in all the layers. This constitutes the forward propagation phase. The backward propagation involves adjusting model parameters according to the difference between the computed and actual output and comprises computing error matrices.

Concretely, each layer comprises matrix multiplications followed by an application of the ReLU function. The maxpool layer additionally follows convolutional layers after the ReLU layer. After evaluating the layers in a sequential manner, at the output layer, we use the MPC friendly variant of the softmax activation function, $\sftmx(u_i) = \frac{\relu(u_i)}{\sum_{j = 1}^{\vl{n}} \relu(u_j)}$, proposed by SecureML <cit.>. To perform the division, we switch from arithmetic to garbled world and then use a division garbled circuit <cit.> followed by a switch back to the arithmetic world.

The network is trained using the Gradient Descent, where the forward propagation comprises of computing activation matrices for all the layers in the network. Here, the activation matrix for all the layers except the output, is defined as $\Mat{A}_i = \relu(\Mat{U}_i)$, where $\Mat{U}_i = \Mat{A}_{i-1} \MatMul \Mat{W}_i$. $\Mat{A}_0$ is initialized to $\Mat{X}_j$, where $\Mat{X}_j$ is a subset of batch size B, randomly selected from the entire dataset for the jth iteration. The activation matrix for the output layer is defined as $\Mat{A}_m = \sftmx(\Mat{U}_m)$.

During the backward propagation, error matrices are computed first. The error matrix for the output layer is defined as $\Mat{E}_m = (\Mat{A}_m - \Mat{T})$, while for the remaining layers it is defined as $\Mat{E}_i = (\Mat{E}_{i+1} \circ \Mat{W}_i^T) \otimes \drelu(\Mat{U}_i)$. Here the operation $\otimes$ denotes element wise multiplication and $\drelu$ denotes the derivative of ReLU. This is followed by updating the weights as $\Mat{W}_i = \Mat{W}_i - \frac{\alpha}{B} \Mat{A}_{i-1}^T  \circ \Mat{E}_i$.

§.§ Support Vector Machines (inference)

We consider Support Vector Machines (SVM) which is a type of supervised learning algorithm used for classification. SVM is a function which takes as input an $n$-dimensional feature vector, $\vct{x}$, and outputs the category to which the feature vector belongs. SVM is implemented as a matrix $\Mat{F}$, of dimension $q \times n$ where each row of $\Mat{F}$ is called the support vector and a vector $\vct{b} = (b_1, \ldots, b_q)$, is called the bias. Each element of $\Mat{F}$ and $\vct{b}$ lies in $\Z{\ell}$. Each support vector along with a scalar from the bias can classify the input $\vct{x}$ into a specific category. More precisely, let $\Mat{F}_i$ denote the $i^{\text{th}}$ row of matrix $\Mat{F}$. Then, the value $\Mat{F}_i \cdot \vct{x} + b_i$ specifies how likely $\vct{x}$ is to be in category $i$. To find the most likely category, we compute argmax over these values, i.e. $\text{category}(\vct{x}) = \text{argmax}_{i \in \{1, \ldots, q\}} \Mat{F}_i \cdot \vct{x} + b_i$.

§ NETWORK ARCHITECTURES

We consider the following networks for benchmarking. These are chosen based on the different range of model parameters and layers used in the network. We refer readers to <cit.> for a detailed architecture of the neural networks.

* SVM: This consists of 10 categories for classification <cit.>.

* NN-1: This is a fully connected network with 3 layers with $\relu$ activation after each layer. This network has around $118$K parameters and is chosen from  <cit.>.

* NN-2: This is a convolutional neural network comprising of 2 hidden layers, with 100 and 10 nodes <cit.>.

* NN-3: This network, called LeNet <cit.>, comprises of $2$ convolutional layers and $2$ fully connected layers with ReLU activation after each layer, additionally followed by maxpool for convolutional layers. This network has approximately $431$K parameters.

* NN-4: This network, called VGG16 <cit.>, was the runner-up of ILSVRC-2014 competition. This network has $16$ layers in total and contains fully-connected, convolutional, ReLU activation and maxpool layers. This network has about $138$ million parameters.

§ DATASETS.

To benchmark the machine learning algorithms, we use the following real-world datasets:

– MNIST <cit.> is a collection of $28 \times 28$ pixel, handwritten digit images with a label between $0$ and $9$ for each. It has $60,000$ and respectively, $10,000$ images in training and test set. We evaluate Linear Regression, Logistic Regression, NN-1, NN-3 and SVM on this dataset.

– CIFAR-10 <cit.> has $32 \times 32$ pixel images of $10$ different classes such as dogs, horses, etc. It has $50,000$ images for training and $10,000$ for testing, with $6000$ images in each class. We evaluate NN-2, NN-4 on this dataset.

§ BENCHMARKING ENVIRONMENT DETAILS

The protocols are benchmarked over a Wide Area Network (WAN), instantiated using n1-standard-64 instances of Google Cloud[https://cloud.google.com/], with machines located in East Australia ($P_0$), South Asia ($P_1$), South East Asia ($P_2$), and West Europe ($P_3$). The machines are equipped with 2.0 GHz Intel (R) Xeon (R) (Skylake) processors supporting hyper-threading, with 64 vCPUs, and 240 GB of RAM Memory. Parties are connected by pairwise authenticated bidirectional synchronous channels (eg. instantiated via TLS over TCP/IP). We use a limited bandwidth of $40$ MBps between every pair of parties and the average round-trip time ($\rtt$)[Time for communicating 1 KB of data between a pair of parties] values among the parties are

c c c c c c
$P_0$-$P_1$     $P_0$-$P_2$     $P_0$-$P_3$     $P_1$-$P_2$     $P_1$-$P_3$     $P_2$-$P_3$

$153.74 ms$     $93.39 ms$     $274.84 ms$     $62.01 ms$      $174.15 ms$      $219.46 ms$

For a fair comparison, we implemented and benchmarked all the protocols, including the protocols of SecureML <cit.> and ABY3 <cit.>, building on the ENCRYPTO library <cit.> in C++17. Primitives such as maxpool, which SecureML and ABY3 do not support, have been run using our building blocks. We would like to clarify that our code is developed for benchmarking, is not optimized for industry-grade use, and optimizations like GPU support can enhance performance. Our protocols are instantiated over a $64$-bit ring ($\Z{64}$), and the collision-resistant hash function is instantiated using SHA-256. We use multi-threading, and our machines are capable of handling a total of 64 threads. Each experiment is run 10 times, and the average values are reported. We use $1$ KB = $8192$ bits and use a batch size of $B = 128$ for training.

p3cm l
Notation     Description

${\sf T}_{\sf on,i}$            Online runtime of party $P_i$.

${\sf T}_{\sf tot,i}$            Total runtime of party $P_i$.

${\sf PT}_{\sf on}$            Protocol online runtime; ${\sf max_i} \{ {\sf T}_{\sf on,i} \}$ .

${\sf PT}_{\sf tot}$            Protocol total runtime;  ${\sf max_i} \{ {\sf T}_{\sf tot,i} \}$ .

${\sf CT}_{\sf on}$             Cumulative online runtime; $\Sigma_i {\sf T}_{\sf on,i}$ .

${\sf CT}_{\sf tot}$             Cumulative total runtime; $\Sigma_i {\sf T}_{\sf tot,i}$ .

${\sf Comm}_{\sf on}$        Online communication.

${\sf Comm}_{\sf tot}$        Total communication.

${\sf Cost}$                         Total monetary cost.

$\TP$                                  [l]Online throughput; higher = better
(#iterations /  #queries per minute in online)

Benchmarking parameters (lower is better, except for $\TP$)

§ BENCHMARKING PARAMETERS

We evaluate the protocols across a variety of parameters as given in notations. In addition to parameters such as runtime, communication, and online throughput ($\TP$) <cit.>, the cumulative runtime (sum of the up-time of all the hired servers) is also reported. This is because when deployed over third-party cloud servers, one pays for them by the communication and the uptime of the hired servers. To analyze the cost of deployment of the framework, monetary cost ($\sf Cost$) <cit.> is reported. This is done using the pricing of Google Cloud Platform[See https://cloud.google.com/vpc/network-pricing for network cost and  https://cloud.google.com/compute/vm-instance-pricing for computation cost.], where for $1$ GB and $1$ hour of usage, the costs are USD $0.08$ and USD $3.04$, respectively. For protocols with an asymmetric communication graph, communication load is unevenly distributed among all the servers, leaving several communication channels underutilized. Load balancing improves the performance by running several execution threads in parallel, each with the roles of the servers changed. Load balancing has been performed in all the protocols benchmarked.

§.§ Discussion

Broadly speaking, we consider two deployment scenarios – optimized for time (T), and for cost (C). In the first one, participants want the result of the output as soon as possible while maximizing the online throughput. In the second one, they want the overall monetary cost of the system to be minimal and are willing to tolerate an overhead in the execution time.

Using multi-input multiplication gates and the 2 GC variant of the garbled makes the online phase faster but incur an increase in monetary cost. This is because they cause an overhead in communication in the preprocessing phase, and communication affects monetary cost more than uptime (in our setting).

CHAPTER: $\TSTHIS$: 3PC SEMI-HONEST APPLICATIONS

$\TSthisT$ uses multi-input multiplication gates and the 2 GC variant of the garbled world and is the fastest variant of the framework. On the other hand, $\TSthisC$ is the variant with a minimal monetary cost. We benchmark our protocols against the 3PC semi-honest framework of ABY3 <cit.>.

§ ML TRAINING

We begin with analyzing the benchmarks for linear and logistic regression.

Starting with the time-optimized variant, $\TSthisT$ is $2.5 - 4\times$ faster than ABY3 <cit.> in online runtime for training.

For linear regression, this reduction is observed due to the different $\rtt$s among the three parties. This difference vanishes if $\rtt$ between every pair of parties is the same. However, the reduction in the online run time for the case of logistic regression is primarily due to the round-optimized bit extraction circuit. Specifically, we use the depth-optimized bit extraction circuit while instantiating the sigmoid activation function using multi-input AND gates.

We observe a reduction of up to $2\times$ in communication (${\sf Comm}_{\sf tot}$) in $\TSthisT$ over ABY3. This is due to the extra cost required for performing truncation in ABY3.

These reductions in communication and run time, coupled with the requirement of one less party in the online phase, directly impact the monetary cost of the system, where $\TSthisT$ brings in a saving of up to $78\%$ over ABY3.

On the other hand, the cost-optimized variant $\TSthisC$ is around $1.5\times$ slower in the online phase than $\TSthisT$. However, it is still faster than ABY3 due to the reason discussed above. Further, this variant has $1.3\times$ lesser communication cost compared to $\TSthisT$.

For neural networks, $\TSthisT$ is up to $3.6 \times$ faster than ABY3 in the online phase, similar to the observation in logistic regression.

Concerning the communication, $\TSthisT$ has a slightly higher communication than ABY3 for smaller NNs. However, the gap closes for larger NNs. This phenomenon is observed because of the trade-off in the increase in communication due to the use of multi-input multiplication versus the reduction in communication due to the free truncation operation. However, the cost-optimized variant, $\TSthisC$, has a better communication cost than ABY3. Further, $\TSthisC$ is up to $1.4 \times$ slower than $\TSthisT$ in terms of online run time, while it is better than ABY3. Note that the requirement of one less party in the online phase coupled with the improvements in communication and run time results in saving up to $87\%$ in the monetary cost of $\TSthisC$ over ABY3, and up to $18\%$ over $\TSthisT$. As the depth increases, we observe that the gap in the monetary cost of $\TSthisC$ and $\TSthisT$ closes in.

These trends can be better captured with a pictorial representation as given in MLPlot3pcS.

§ ML INFERENCE

A similar trend for linear and logistic regression inference is observed for training, where both $\TSthisT$ and $\TSthisC$ outperform ABY3. The exception concerns the slightly higher communication of $\TSthisT$ compared to ABY3 due to the higher communication cost required for multi-input multiplication gates. This difference, however, vanishes for larger circuits, as will be evident from nn3pcS.

For neural networks, the time-optimized variant $\TSthisT$ is faster when it comes to online run time (${\sf PT}_{\sf on}$), by $4.4\times$ over ABY3. This is also reflected in the $\TP$, where the improvement is up to $2.8 \times$, as evident from Inf3pcS. For inference, the communication is in the order of a few megabytes, while run time is in the order of a few seconds. The key observation is that communication is well suited for the bandwidth used (40 MBps). So unlike training, the monetary cost in inference depends more on run time rather than on communication. This is evident from nn3pcS which shows that $\TSthisT$ saves on monetary cost up to a factor of $4$ over ABY3. A similar trend is observed in the case of Support Vector Machines.

Note that the cost-optimized variant underperforms in terms of monetary cost compared to $\TSthisT$. This is because run time plays a more significant role in monetary cost than communication. Hence for inference, the time-optimized variant becomes the optimal choice.

§ ADDITIONAL BENCHMARKING

§.§ Varying batch sizes and feature sizes

nn13pcS shows the online throughput ($\TP$) of neural network (NN-1) training over varying batch sizes and feature sizes using synthetic datasets.

r r r r r
Batch Size     Features     ABY3

10	   1314.59	   2997.27	   2140.91

100	   1314.59	   2997.27	   2140.91

1000	   1104.37	   2625.67	   2139.75

10	   725.66	   2113.79	   2058.65

100	   716.15	   2060.63	   2008.18

1000	   633.13	   1646.47	   1612.81

Online throughput ($\TP$) of NN-1 training (iterations per minute) over various batch sizes and features.

We find that both $\TSthisT, \TSthisC$ are up to $2.9 \times$ higher in $\TP$. However, as the batch size and feature size increase, ABY3 and $\TSthis$ experience a bandwidth bottleneck.

§.§ Comparison operations

compb3pcS compares the performance of the frameworks for circuits of varying depth. At each layer of the circuits, we perform 128 comparisons where the comparison results are generated in arithmetic shared form. The idea is that each layer emulates a comparison layer in an NN with a batch size of 128.

r r r r r
Depth     Parameter     ABY3

${\sf PT}_{\sf on}$	   2.62	   0.53	   0.93

${\sf CT}_{\sf tot}$	   5.87	   1.06	   1.85

${\sf Cost}$	   0.3	   0.05	   0.09

${\sf PT}_{\sf on}$	   20.99	   4.23	   7.41

${\sf CT}_{\sf tot}$	   46.99	   8.47	   14.82

${\sf Cost}$	   2.38	   0.43	   0.75

${\sf PT}_{\sf on}$	   167.93	   33.87	   59.27

${\sf CT}_{\sf tot}$	   375.89	   67.74	   118.54

${\sf Cost}$	   19.06	   3.45	   6.02

Benchmarking of comparisons over various depths. Each of the layer has 128 comparisons. Time is reported in minutes, and monetary cost in USD.

To summarise the experimental results, beyond a depth of roughly 100, the time-optimized variant ($\TSthisT$) starts outperforming in every metric, especially monetary cost, over the cost-optimized one ($\TSthisC$). This is because as the depth increases, runtime (CT) grows at a much higher rate than the total communication. What we can infer from compb3pcS is that if one were to use a DNN with a depth of over 100, $\TSthisT$ becomes the optimal choice.

CHAPTER: $\TTHIS$: 3PC FAIR AND ROBUST APPLICATIONS

$\TthisT$ uses multi-input multiplication gates and the 2 GC variant of the garbled world and is the fastest variant of the framework. On the other hand, $\TthisC$ is the variant with a minimal monetary cost. We report only the numbers for the fair variant of $\Tthis$ and not the robust variant since the overhead of robust over its fair counterpart is very minimal for the algorithms considered in this thesis.

§ ML TRAINING

We begin with analyzing the benchmarks for linear and logistic regression. The improvements observed in the three-party semi-honest case carry forward to $\Tthis$ as well. Both $\TthisT$ and $\TthisC$ showcase an improvement over ABY3 in terms of communication and run time. This also improves the monetary cost over ABY3, where the saving is up to $70\%$. One of the primary reasons for the improvement is the reduction in communication. This is attributed to an improved dot product protocol whose communication cost is independent of the vector dimension and a method for truncation which does not incur any overhead in the online phase. Moreover, our multiplication protocol has around $3.5\times$ improvement in terms of communication over ABY3.

The improvements are more evident in the case of neural networks. Here, $\TthisT$ is up to two orders of magnitude faster than ABY3 in the online phase. The same trend holds true for communication costs.

Like $\TSthis$, the cost-optimized variant, $\TthisC$, saves $15\%$ in monetary cost over $\TthisT$, while incurring the overhead of $1.2\times$ in the online run time.

These trends can be better captured with a pictorial representation as given in MLPlot3pcM.

§ ML INFERENCE

For linear regression, logistic regression and support vector machines, we observe a similar trend as in the inference of $\TSthis$, where $\TthisT$ outperforms ABY3 and $\TthisC$ in terms of run time and monetary cost.

For neural networks, the time-optimized variant $\TthisT$ is faster when it comes to online run time (${\sf PT}_{\sf on}$), by $9.7\times$ over ABY3. This is also reflected in the $\TP$, where the improvement is up to $753 \times$, as evident from nn3pcM. Unlike the inference of $\TSthis$, the cost-optimized variant $\TthisC$ outperforms the rest (ABY3 and $\TthisT$) in terms of the monetary cost and communication as the network becomes deeper. The trends in throughput are captured in Inf3pcM.

§ ADDITIONAL BENCHMARKING

§.§ Varying batch sizes and feature sizes

nn13pcM shows the online throughput ($\TP$) of neural network (NN-1) training over varying batch sizes and feature sizes using synthetic datasets.

r r r r r
Batch Size     Features     ABY3

10	   20.78	   1102.82	   838.56

100	   16.04	   1102.82	   838.56

1000	   4.88	   1102.09	   838.14

10	   10.41	   1102.56	   838.41

100	   8.05	   1102.56	   838.41

1000	   2.46	   981.09	   836.42

Online throughput ($\TP$) of NN-1 training (iterations per minute) over various batch sizes and features.

§.§ Comparison operations

compb3pcM compares the performance of the frameworks for circuits of varying depth. At each layer of the circuits, we perform 128 comparisons where the comparison results are generated in arithmetic shared form. The idea is that each layer emulates a comparison layer in an NN with a batch size of 128.

r r r r r
Depth     Parameter     ABY3

${\sf PT}_{\sf on}$	   4.21	   0.66	   1.06

${\sf CT}_{\sf tot}$	   12.64	   1.33	   2.12

${\sf Cost}$	   0.64	   0.07	   0.11

${\sf PT}_{\sf on}$	   33.71	   5.29	   8.47

${\sf CT}_{\sf tot}$	   101.13	   10.63	   16.98

${\sf Cost}$	   5.14	   0.55	   0.87

${\sf PT}_{\sf on}$	   269.67	   42.33	   67.73

${\sf CT}_{\sf tot}$	   809.07	   85.04	   135.84

${\sf Cost}$	   41.12	   4.41	   6.92

Benchmarking of comparisons over various depths. Each of the layer has 128 comparisons. Time is reported in minutes, and monetary cost in USD.

To summarize, $\Tthis$ improves over ABY3 up to two orders of magnitude in terms of monetary cost. As observed from the nn3pcM, $\TthisT$ provides the best online time while $\TthisC$ attains the best monetary cost, corroborating our claims.

CHAPTER: $\FTHIS$: 4PC FAIR AND ROBUST APPLICATIONS

$\FthisT$ uses multi-input multiplication gates and the 2 GC variant of the garbled world and is the fastest variant of the framework. On the other hand, $\FthisC$ is the variant with a minimal monetary cost. We report only the numbers for the fair variant of $\Fthis$ and not the robust variant since the overhead of robust over its fair counterpart is very minimal for the algorithms considered in this thesis.

For training, we benchmark against the fair 4PC framework of Trident <cit.>. For inference, in addition to Trident, we also benchmark against the 4PC robust protocol of SWIFT <cit.> since it supports NN inference. Note that the best case performance of Fantastic Four <cit.>, when cast in the preprocessing model, resembles that of SWIFT. In contrast, their worst-case execution (3PC malicious) is an order of magnitude slower (cf. <ref>), as demonstrated in their paper (cf. Table 2 of <cit.>).

§ ML TRAINING

Starting with the time-optimized variant, $\FthisT$ is $3 - 4\times$ faster than Trident in online runtime.

The primary factor is the reduction in online rounds of our protocol due to multi-input gates. More precisely, we use the depth-optimized bit extraction circuit while instantiating the ReLU activation function using multi-input AND gates (cf. 4pcBitExt). Looking at the total communication (${\sf Comm}_{\sf tot}$) in nn4pcM, we observe that the gap in ${\sf Comm}_{\sf tot}$ between $\FthisT$ vs. Trident decreases as the networks get deeper. This is justified as the improvement in communication of our dot product with truncation outpaces the overhead in communication caused by multi-input gates. The impact of this is more pronounced with NN-4, as observed by the lower monetary cost of $\FthisT$ over Trident.

Another reason is that there are two active parties ($P_1, P_2$) in our framework, whereas Trident has three. Given the allocation of servers, the best $\rtt$ Trident can get with three parties $(P_0,P_1,P_2)$ is $153.74ms$, compared to $62.01ms$ of Tetrad, contributing to Tetrad being faster. However, if the $\rtt$ among all the parties were similar, this gap would be closed. Concretely, the online runtime (${\sf PT_{on}}$) of Trident will be similar to that of $\FthisC$.

On the other hand, the cost-optimized variant $\FthisC$ is $1.5\times$ slower in the online phase than $\FthisT$. However, it is still faster than Trident owing to the $\rtt$ setup, as discussed above. When it comes to monetary cost, this variant is up to $20-40\%$ cheaper than its time-optimized counterpart and cheaper by around $30\%$ over Trident.

These trends can be better captured with a pictorial representation as given in MLPlot4pcM.

§ ML INFERENCE

Similar to training, the time-optimized variant for inference is faster when it comes to ${\sf PT}_{\sf on}$, by $4 - 6\times$ over Trident. This is also reflected in the $\TP$, where the improvement is about $2.8 - 5.5\times$, as evident from Inf4pcM. In inference, the communication is in the order of megabytes, while run time is in the order of a few seconds. The key observation is that communication is well suited for the bandwidth used (40 MBps). So unlike training, the monetary cost in inference depends more on run time rather than on communication. This is evident from compb4pcM which shows that $\FthisT$ saves on monetary cost up to a factor of $10$ over Trident.

Note that the cost-optimized variant underperforms in terms of monetary cost compared to $\FthisT$. This is because, as mentioned earlier, run time plays a more significant role in monetary cost than communication. Hence for inference, the time-optimized variant becomes the optimal choice.

§ ADDITIONAL BENCHMARKING

§.§ Varying batch sizes and feature sizes

nn14pcM shows the online throughput ($\TP$) of neural network (NN-1) training over varying batch sizes and feature sizes using synthetic datasets.

r r r r r
Batch Size     Features     Trident

10	   1189.08	   2086.28	   1519.17

100	   1189.08	   2086.28	   1519.17

1000	   1188.75	   2083.68	   1517.79

10	   1189.08	   2084.19	   1518.06

100	   1189.08	   2084.19	   1518.06

1000	   1188.75	   2077.69	   1514.62

Online throughput ($\TP$) of NN-1 training (iterations per minute) over various batch sizes and features.

We find that both $\FthisT, \FthisC$ are up to $1.8 \times$ higher in $\TP$. However, as the batch size and feature size increase, Trident and $\Fthis$ experience a bandwidth bottleneck. The effect of the bandwidth limitation is higher for $\Fthis$; hence the gain in $\TP$ over Trident decreases a bit.

§.§ Comparison operations

compb4pcM compares the performance of the frameworks for circuits of varying depth. At each layer of the circuits, we perform 128 comparisons where the comparison results are generated in arithmetic shared form. The idea is that each layer emulates a comparison layer in an NN with a batch size of 128.

r r r r r
Depth     Parameter     Trident

${\sf PT}_{\sf on}$	   3.55	   0.53	   0.93

${\sf CT}_{\sf tot}$	   9.6	   1.06	   1.85

${\sf Cost}$	   0.49	   0.05	   0.09

${\sf PT}_{\sf on}$	   28.42	   4.23	   7.41

${\sf CT}_{\sf tot}$	   76.79	   8.47	   14.82

${\sf Cost}$	   3.89	   0.43	   0.75

${\sf PT}_{\sf on}$	   227.34	   33.87	   59.27

${\sf CT}_{\sf tot}$	   614.3	   67.76	   118.56

${\sf Cost}$	   31.15	   3.48	   6.03

Benchmarking of comparisons over various depths. Each of the layer has 128 comparisons. Time is reported in minutes, and monetary cost in USD.

Interestingly, beyond a depth of roughly 100, the time-optimized variant ($\FthisT$) starts outperforming in every metric, especially monetary cost, over the cost-optimized one ($\FthisC$). This is because as the depth increases, runtime (CT) grows at a much higher rate than the total communication. What we can infer from compb4pcM is that if one were to use a DNN with a depth of over 100, $\FthisT$ becomes the optimal choice.

CHAPTER: $\TWTHIS$: 2PC SEMI-HONEST APPLICATIONS

$\TWthisT$ makes use of multi-input multiplication gates and is the fastest variant of the framework. On the other hand, $\TWthisC$ is the variant with a minimal monetary cost. We benchmark our protocols against the 2PC semi-honest framework of SecureML <cit.>. The preprocessing phase of $\TWthis$ is similar to SecureML except for the use of multi-input multiplication in $\TWthisT$. The preprocessing can be performed either using oblivious transfer or via homomorphic encryption as discussed in Chapter <ref>. Note that the benchmarking is performed only for the online phase.

§ ML TRAINING

Starting with the time-optimized variant, $\TWthisT$ is up to two orders of magnitude faster than SecureML <cit.> in run time as well as communication.

The reduction is primarily due to the following: (i) the improved dot product protocol whose online phase communication is independent of the dimension of the vector, and (ii) improvements in online rounds due to multi-input multiplication.

These reductions in communication and run time directly impact the monetary cost of the system, where $\TWthisT$ brings in a saving of up to $342 \times$ over SecureML.

On the other hand, the cost-optimized variant $\TWthisC$ is around $1.3\times$ slower than $\TWthisT$. However, it is still faster than SecureML due to the reasons discussed above. Further, this variant has a slightly higher communication than $\TWthisT$ due to the absence of multi-input multiplication.

These trends can be better captured with a pictorial representation as given in MLPlot2pcS.

§ ML INFERENCE

Like training, the time-optimized variant for inference is faster when it comes to the performance in the online phase. For shallow NNs such as NN-1, we observe a $4\times$ improvement in the online throughput over SecureML. However, the improvement changes drastically as the network grows bigger. Specifically, we observe a gain in throughput of up to $500\times$ over SecureML for the case of NN-4. The poor performance of SecureML is due to the huge increase in communication costs for deeper networks, which forms the bottleneck.

§ ADDITIONAL BENCHMARKING

§.§ Varying batch sizes and feature sizes

nn12pcS shows the online throughput ($\TP$) of neural network (NN-1) training over varying batch sizes and feature sizes using synthetic datasets.

r r r r r
Batch Size     Features     SecureML

10	   31.02	   1351.09	   1317.96

100	   23.99	   1287.39	   1257.28

1000	   7.34	   874.91	   860.89

10	   15.54	   704.19	   686.21

100	   12.02	   686.49	   669.39

1000	   3.68	   548.57	   537.6

Online throughput ($\TP$) of NN-1 training (iterations per minute) over various batch sizes and features.

§.§ Comparison operations

compb2pcS compares the performance of the frameworks for circuits of varying depth. At each layer of the circuits, we perform 128 comparisons where the comparison results are generated in arithmetic shared form. The idea is that each layer emulates a comparison layer in an NN with a batch size of 128.

r r r r r
Depth     Parameter     SecureML

${\sf PT}_{\sf on}$	   0.93	   0.53	   0.93

${\sf CT}_{\sf on}$	   1.85	   1.06	   1.85

${\sf Cost}$	   0.09	   0.05	   0.09

${\sf PT}_{\sf on}$	   7.41	   4.23	   7.41

${\sf CT}_{\sf on}$	   14.82	   8.47	   14.82

${\sf Cost}$	   0.75	   0.43	   0.75

${\sf PT}_{\sf on}$	   59.27	   33.87	   59.27

${\sf CT}_{\sf on}$	   118.53	   67.73	   118.53

${\sf Cost}$	   6.03	   3.44	   6.01

Benchmarking of comparisons over various depths. Each of the layer has 128 comparisons. Time is reported in minutes, and monetary cost in USD.

Having benchmarked only the online phase, $\TWthisT$ is clearly the winner with respect to all the metrics. We believe a similar trend as observed in the prior frameworks will be followed here as well when considering the overall performance.

CHAPTER: CONCLUSION AND OPEN PROBLEMS

This thesis designed $\thisP$, a robust MPC platform for privacy-preserving machine learning applications. The focus was on the small-party setting of two, three and four parties with at most one corruption under the control of a monolithic static adversary. A unified protocol design was presented, focusing on practical efficiency, which outperforms the state-of-the-art protocols by several orders of magnitude in the respective settings. On the way, several building blocks were identified for the PPML applications, and their efficient realizations were provided. Finally, the protocols were implemented by instantiating over Google Cloud instances and analyzed against various metrics such as run time, communication, throughput and monetary cost. The practicality of our platform was argued through improvements as observed in the benchmarks.

Open Problems
We leave the following problems open for further explorations.

* Applications: The platform was designed for PPML applications such as linear regression, logistic regression, neural networks and support vector machines. However, other PPML applications such as graph neural networks, decision trees and random forests, quantized neural networks have not been explored much in the literature. Extending our platform to provide support for these advanced applications is an interesting direction. This may require support for new building blocks in layer II, such as square-root, exponentiation, batch normalization, to name a few.  While the platform discussed PPML applications, it is worthwhile to explore non-PPML applications such as private-set intersection, private-information retrieval, genome sequence matching.

* Adversarial setting: The focus of the thesis was primarily on the honest majority setting. A step towards a dishonest majority was also taken, albeit in the semi-honest two-party setting. It is an interesting question to explore the dishonest majority setting in the presence of a malicious adversary. While protocols were designed in the synchronous network model with static corruptions, designing protocols in the asynchronous network model and against a stronger adaptive adversary is left open.

The recent notion of Friends-and-Foes <cit.> (FaF) security resembles real-world corruption more closely, where the honest parties are instead considered to be semi-honest. Our protocols do not adhere to this security notion, and designing protocols for the same is an interesting future direction.
Finally, our protocols, together with the above-mentioned adversarial settings, can be explored for the general $n$-party case.

* Federated Learning: The advancements in PPML have paved the way for federated learning which allows collaborative training while ensuring the training data resides only with the data owners. Since the data does not leave its owner, it increases the trust in the system and has gained a lot of attention recently. The traditional approach of realizing PPML via MPC does not extend naively to the federated setting. We leave open the question of realizing our architecture in the federated setting as an open problem.


# Synthetic non-Abelian gauge fields for non-Hermitian systems

Zehai Pang  Department of Physics, The University of Hong Kong, Pokfulam, Hong
Kong, China Jinbing Hu  Department of Physics, The University of Hong Kong,
Pokfulam, Hong Kong, China College of Optical-Electrical Information and
Computer Engineering, University of Shanghai for Science and Technology,
Shanghai 200093, China Yi Yang<EMAIL_ADDRESS>Department of Physics, The
University of Hong Kong, Pokfulam, Hong Kong, China

###### Abstract

Non-Abelian gauge fields are versatile tools for synthesizing topological
phenomena but have so far been mostly studied in Hermitian systems, where
gauge flux has to be defined from a closed loop in order for gauge fields,
whether Abelian or non-Abelian, to become physically meaningful. We show that
this condition can be relaxed in non-Hermitian systems by proposing and
studying a generalized Hatano–Nelson model with imbalanced non-Abelian
hopping. Despite lacking gauge flux in one dimension, non-Abelian gauge fields
create rich non-Hermitian topological consequences. Under only nearest-
neighbor coupling, non-Abelian gauge fields enable Hopf-link bulk braiding
topology, whose phase transition accompanies the emergence of exceptional
points (EPs). At both ends of an open chain, non-Abelian gauge fields lead to
the simultaneous presence of non-Hermitian skin modes, whose population can be
effectively tuned. Asymptotic analysis shows that this tuning mechanism stems
from the interplay between the Abelian Hatano–Nelson coupling and effective
high-order hopping, which becomes substantial near the EP phase transition
condition. The predicted non-Hermitian phenomena, enabled by non-Abelian gauge
fields, could be realized in synthetic dimensional optical platforms such as
time-multiplexed photonic mesh lattices and driven ring resonators.

Open physical systems interacting with external environments are described by
non-Hermitian Hamiltonians that support complex eigenvalues. Compared to
closed systems, non-Hermitian systems exhibit rich unique phenomena, such as
power oscillations Musslimani  _et al._ (2008); Makris  _et al._ (2008);
Regensburger  _et al._ (2012), unidirectional invisibility Feng  _et al._
(2013); Regensburger  _et al._ (2012), and exceptional-point (EP) encirclement
Gao  _et al._ (2015); Doppler  _et al._ (2016), which have no counterparts in
Hermitian systems. Besides their bulk invariants defined from eigenvectors Yao
and Wang (2018); Song  _et al._ (2019); Kunst  _et al._ (2018); Xiong (2018)
as in Hermitian systems, non-Hermitian systems also exhibit eigenvalue
topology Bergholtz  _et al._ (2021); Gong  _et al._ (2018); Kawabata  _et al._
(2019); Yokomizo and Murakami (2019); Zhang  _et al._ (2020); Okuma  _et al._
(2020); Yang  _et al._ (2020a); Wang  _et al._ (2021a); Hu and Zhao (2021);
Borgnia  _et al._ (2020) due to the expansion of eigenenergies from the real
to the complex regime. Importantly, non-Hermitian eigenstates of a non-
vanishing eigenvalue winding number are all localized at the end of open
systems known as the non-Hermitian skin effect (NHSE) Lee (2016); Yao and Wang
(2018); Xiong (2018). NHSE has been implemented widely in photonics Weidemann
_et al._ (2020); Wang  _et al._ (2021b, a); Xiao  _et al._ (2020); Liu  _et
al._ (2022), acoustics Zhang  _et al._ (2021a, b); Gu  _et al._ (2022),
mechanics Wang  _et al._ (2022); Ghatak  _et al._ (2020); Scheibner  _et al._
(2020), and electric circuits Li  _et al._ (2020); Helbig  _et al._ (2020);
Hofmann  _et al._ (2020); Liu  _et al._ (2021); Zou  _et al._ (2021); Shang
_et al._ (2022). Moreover, synthetic gauge fields have been introduced for
better controlling non-Hermitian systems Lin  _et al._ (2021); Midya  _et al._
(2018); Longhi (2017a); Longhi  _et al._ (2015); Longhi (2017b); Wong and Oh
(2021), but most efforts have been dedicated to Abelian gauge fields.

Non-Abelian physics has recently attracted lots of attention in acoustics and
photonics Chen  _et al._ (2019); Yang  _et al._ (2019, 2020b); Guo  _et al._
(2021); Jiang  _et al._ (2021); Brosco  _et al._ (2021); Chen  _et al._
(2022); Sun  _et al._ (2022); You  _et al._ (2022); Noh  _et al._ (2020);
Zhang  _et al._ (2022a); Xu  _et al._ (2016); Yang  _et al._ (2020c, 2022);
Gianfrate  _et al._ (2020); Whittaker  _et al._ (2021); Iadecola  _et al._
(2016); Polimeno  _et al._ (2021); Cheng  _et al._ (2023). In particular, non-
Abelian gauge fields, leveraging the internal degrees of freedom of particles,
are a synthetic control knob for realizing non-Abelian physics in engineered
physical systems Aidelsburger  _et al._ (2018). These gauge fields enable
synthetic spin-orbit interaction and can be used for creating non-Abelian
Aharonov–Bohm interference and lattice models featuring complex gauge
structures. Moreover, recent experiments have demonstrated the possibility of
creating and tuning building blocks of non-Abelian gauge fields in fibers Yang
_et al._ (2019) and circuits Wu  _et al._ (2022), indicating their
applicability for large lattice systems. The effectiveness of synthetic gauge
fields substantially relies on their dimensionality. In particular, pure one-
dimensional (1D) systems forbid the definition of closed loops and the
associated magnetic flux. Thus, synthetic gauge fields, whether Abelian or
non-Abelian, carry little physical consequences in 1D Hermitian systems.
Although the 1D spin-orbit interaction realized with cold atoms Lin  _et al._
(2011) seems to be a counterexample, an extra Zeeman term has to be added for
the Rashba–Dresselhaus gauge fields to become nontrivial. So far, non-Abelian
gauge fields have seldom been explored in non-Hermitian systems, where the
dimensionality constraint above could be violated.

Figure 1: Hatano–Nelson model with Abelian and non-Abelian gauge fields. a-b.
Hatano–Nelson model (a) with nonreciprocal U(1) hopping phases and its single
non-Hermitian band (b) exhibiting a winding number $w=1$. c. Hatano–Nelson
model with nonreciprocal SU(2) hopping phases. d. Two non-Hermitian bands
($E_{+}$ and $E_{-}$) exhibiting four exceptional points (EPs) at momenta
$\left\\{\pm\pi/4,\pm 3\pi/4\right\\}$ (vertical grey lines). e. Phase diagram
of the non-Abelian Hatano–Nelson model under
$J_{\mathrm{L}}/J_{\mathrm{R}}=7/6$, featuring Hopf links with braid degrees
$\nu=\pm 2$. Their phase transition accompanies the appearance EPs (black
solid lines). f-h. Braiding of the two bands under the EP phase transition
(f), $\nu=-2$ (g), and $\nu=2$ (h) Hopf-link phases in the
($\operatorname{Re}E$, $\operatorname{Im}E$, $k$) space. Here we use
$J_{\mathrm{L}}=0.7$, $J_{\mathrm{R}}=0.6$, and $\theta_{\mathrm{R}}=-1.38$
throughout; $\theta_{\mathrm{L}}=-1$ for b,d, and f,
$\theta_{\mathrm{L}}=-0.5$ for g, and $\theta_{\mathrm{L}}=-1.5$ for h,
respectively, as shown by black dots in e.

In this work, we introduce non-Abelian gauge fields to generate non-
Hermiticity and study their manipulation of NHSE. Under bare nearest-neighbor
coupling, the bulk spectrum of a non-Abelian Hatano–Nelson model forms Hopf
links in complex energy braiding, which was realized only with long-range
hopping previously. The Hopf links are characterized by the braiding degree
$\pm 2$, whose phase transition accompanies the appearance of EPs. Non-Abelian
gauge fields enable the simultaneous presence of left- and right-localized
skin modes whose population is tunable, confirmed by both winding-number and
the non-Bloch calculations. Asymptotic analyses further reveal that the
tunability is most effective near the EP phase transition, resulting from the
interplay between the Abelian Hatano–Nelson coupling and effective high-order
hopping on the order of $4N-1$ ($N$ is an integer).

The Hatano–Nelson model Hatano and Nelson (1996) is a prototypical 1D system
that demonstrates NHSE because of its nonreciprocal hoppings. We first extend
the model with U(1) Abelian gauge fields as (Fig. 1a)

$\displaystyle\hat{H}_{0}=\sum_{m}J_{\mathrm{L}}c^{\dagger}_{m}\mathrm{e}^{\mathrm{i}\theta_{\mathrm{L}}}c_{m+1}+J_{\mathrm{R}}c^{\dagger}_{m+1}\mathrm{e}^{\mathrm{i}\theta_{\mathrm{R}}}c_{m}.$
(1)

Here $c^{\dagger}_{m}(c_{m})$ is the creation (annihilation) operator at site
$m$, $J_{\mathrm{L(R)}}$ is the real hopping amplitude leftward (rightward),
and $\theta_{\mathrm{L(R)}}$ the corresponding hopping phases. The
conventional Hatano–Nelson model is restored if
$\theta_{\mathrm{L}}=\theta_{\mathrm{R}}=0$. One can reformulates Eq. (1) as
$H_{0}(k)\mathrm{e}^{-\mathrm{i}\theta_{+}}=J_{\mathrm{L}}\mathrm{e}^{\mathrm{i}(k+\theta_{-})}+J_{\mathrm{R}}\mathrm{e}^{-\mathrm{i}(k+\theta_{-})},$
where $\theta_{+}=\left(\theta_{\mathrm{L}}+\theta_{\mathrm{R}}\right)/2$ and
$\theta_{-}=\left(\theta_{\mathrm{L}}-\theta_{\mathrm{R}}\right)/2$. As in
Hermitian systems, a Peierls substitution of $\theta_{-}$ acts on the momentum
$k$. Meanwhile, on the left-hand side, a Peierls substitution of $\theta_{+}$
acts on the complex energy, i.e. a rotation on the complex energy plane. Thus,
the U(1) fields only lead to trivial modifications to the Hatano–Nelson model.
This is confirmed by the energy band shown in Fig. 1b, which exhibits a
winding number $w=+1$ on the complex energy plane, where
$w\equiv\frac{1}{2\pi}\int_{0}^{2\pi}\partial_{k}\mathrm{arg}(E(k)-E_{\mathrm{b}})\mathop{}\mathrm{d}k=\mathrm{sgn}(J_{\mathrm{L}}-J_{\mathrm{R}})$
and $\pm 1$ indicates counter-clockwise (CCW) and clockwise (CW) rotation,
respectively.

In contrast, the model gets substantially modified with SU(2) non-Abelian
gauge fields (Fig. 1c):

$\displaystyle\hat{H}=\sum_{m}J_{\mathrm{L}}c^{\dagger}_{m}\mathrm{e}^{\mathrm{i}\theta_{\mathrm{L}}\sigma_{y}}c_{m+1}+J_{\mathrm{R}}c^{\dagger}_{m+1}\mathrm{e}^{\mathrm{i}\theta_{\mathrm{R}}\sigma_{x}}c_{m},$
(2)

where $\sigma_{x}$ and $\sigma_{y}$ are Pauli matrices. Notably, in Eq. (2),
both the hopping amplitudes $\left(J_{\mathrm{L}},J_{\mathrm{R}}\right)$ and
the non-Abelian hopping phases
$\left(\theta_{\mathrm{L}},\theta_{\mathrm{R}}\right)$ contribute to non-
Hermiticity. This feature distinguishes our system from a recent study on non-
Hermitian Aubry–André–Harper models Zhou (2023), where the non-Abelian on-site
potentials alone do not cause non-Hermiticity. The Bloch Hamiltonian of Eq.
(2) is

$\displaystyle H(k)$
$\displaystyle=A(k)\sigma_{0}+\mathrm{i}J_{\mathrm{L}}\sin{\theta_{\mathrm{L}}}\mathrm{e}^{\mathrm{i}k}\sigma_{y}+\mathrm{i}J_{\mathrm{R}}\sin{\theta_{\mathrm{R}}}\mathrm{e}^{-\mathrm{i}k}\sigma_{x},$
(3)

where

$\displaystyle
A(k)=J_{\mathrm{L}}\cos{\theta_{\mathrm{L}}}\mathrm{e}^{\mathrm{i}k}+J_{\mathrm{R}}\cos{\theta_{\mathrm{R}}}\mathrm{e}^{-\mathrm{i}k}$
(4)

and $\sigma_{0}$ the identity matrix. The eigen-energy of $\hat{H}$ is given
by

$\displaystyle
E_{\pm}(k)=A(k)\pm\mathrm{i}\sqrt{J_{\mathrm{L}}^{2}\sin^{2}{\theta_{\mathrm{L}}}\mathrm{e}^{\mathrm{i}2k}+J_{\mathrm{R}}^{2}\sin^{2}{\theta_{\mathrm{R}}}\mathrm{e}^{-\mathrm{i}2k}}.$
(5)

Eq. (5) permits EPs at $k_{\mathrm{EP}}=\left\\{\pm\pi/4,\pm 3\pi/4\right\\}$
when

$\displaystyle
J_{\mathrm{L}}^{2}\sin^{2}{\theta_{\mathrm{L}}}=J_{\mathrm{R}}^{2}\sin^{2}{\theta_{\mathrm{R}}}$
(6)

the EP condition is satisfied, as shown by an example spectrum in Fig. 1d.

The two energy bands in Eq. (5) form Hopf link in ($\operatorname{Re}E$,
$\operatorname{Im}E$, $k$) space (different from the exceptional-line links in
three-dimensional momentum space Yang and Hu (2019); Carlström and Bergholtz
(2018)). In fact, the EP condition Eq. (6) is the phase transition of the
energy braiding between two types of Hopf links, defined by a braiding degree
Wang  _et al._ (2021a) $\nu=\pm 2$ (Fig. 1e), where

$\displaystyle\nu\equiv\int_{0}^{2\pi}\frac{\mathop{}\mathrm{d}k}{2\pi\mathrm{i}}\frac{\mathop{}\mathrm{d}}{\mathop{}\mathrm{d}k}\mathrm{ln}\;\mathrm{det}\left(\hat{H}_{k}-\frac{1}{2}\mathrm{Tr}\hat{H}_{k}\right).$
(7)

Fig. 1f-g confirm this transition, where Hopf links of opposite braiding
degrees (Fig. 1g and h) appear on opposite sides of the EP phase transition
(Fig. 1f). Non-Hermitian energy braiding of the Hopf-link type has been
identified previously but requires longer range hopping, such as the next-
nearest-neighbor coupling Wang  _et al._ (2021a); Hu and Zhao (2021). In a
recent paper Hu and Zhao (2021), the Hopf link is achieved by using a building
block Hamiltonian $\left(0,\mathrm{e}^{\mathrm{i}nk};1,0\right)$, where $n=2$
gives rise to Hopf link. Nevertheless, here non-Abelian gauge fields enable
the realization of the Hopf link using nearest-neighbor coupling only.
Therefore, even though no gauge flux can be defined, introducing non-Abelian
gauge fields can sufficiently drive non-Hermitian topological phase
transitions in a 1D bulk, which is impossible for Hermitian systems.

Figure 2: Analysis of non-Hermitian skin effect. a-d. Periodic- (black lines)
and open-boundary (dots) spectra (a and c) and eigenstates (b and d) of the
Abelian (a-b) and non-Abelian (c-d) Hatano–Nelson models. e. Localization
analysis. The unit circle (red) intersects the generalized Brillouin zone
(blue), indicating the simultaneous presence of left- (inside the unit circle)
and right-localized (outside the unit circle) states. The black circles denote
the zero-mode solutions. f. Simultaneous left- and right-localization
confirmed by consistent non-Bloch (squares) and winding-number (circles)
calculations. Here, $J_{\mathrm{L}}=0.7$, $J_{\mathrm{R}}=0.6$,
$\theta_{\mathrm{L}}=-2.5$, $\theta_{\mathrm{R}}=-1.4$.

Next, we show how non-Abelian gauge fields enrich NHSE in Fig. 2. We calculate
the eigen-spectra of $H_{0}$ and $H$ under the periodic boundary condition
(PBC) and the open boundary condition (OBC). Both the PBC spectra of $H_{0}$
and $H$ form closed loops surrounding the zero energy in the complex plane,
indicating point-gapped bulk topology, while their OBC spectra become open
arcs Zhang  _et al._ (2022b); Ashida  _et al._ (2020); Zhang  _et al._ (2020).
Thus, the PBC and OBC spectra are topologically distinct, and NHSE inevitably
occurs in both models as a consequence of topological phase transition Okuma
_et al._ (2020). In Fig. 2a, a PBC spectrum of the Abelian $H_{0}$ is an
ellipse showing uniform CCW winding, and the corresponding OBC arc occupies
the major axis. As determined by
$\absolutevalue{J_{\mathrm{L}}/J_{\mathrm{R}}}>1$, all OBC states are
localized on the left of the chain (Fig. 2b), identical to the conventional
Hatano–Nelson model Gong  _et al._ (2018); it confirms our previous analysis
that the U(1) Abelian gauge field only leads to a trivial Peierls substitution
without modifying the NHSE.

In contrast, the NHSE in the non-Abelian Hatano–Nelson model $H$ is far
richer. The PBC spectrum of $H$ (Fig. 2c), under the same set of parameters,
simultaneously exhibits CW and CCW winding at the four corners and center of
the Hopf link, respectively. Consequently, the OBC arc enclosed by these
sectors should demonstrate leftward (blue in Fig. 2c) and rightward (red in
Fig. 2c) localization, respectively, whose simultaneously presence is
confirmed by the visualization of the eigenstates in Fig. 2d. Meanwhile,
extended states (green in Fig. 2d) also appear at the boundary of the CW and
CCW winding (green circles in Fig. 2c). This simultaneous leftward and
rightward localization cannot be explained solely by the imbalanced hopping
amplitudes $(J_{\mathrm{L}},J_{\mathrm{R}})$.

We adopt both the non-Bloch Yao and Wang (2018); Yang  _et al._ (2020a);
Yokomizo and Murakami (2019) and the winding-number approaches Zhang  _et al._
(2020) to study the effect from non-Abelian gauge fields. Using the non-Bloch
approach, for an OBC energy $E$, we calculate the characteristic polynomial
$\mathrm{det}[H(z)-E]$, a quartic function of $z$ (see Sec. S2 of Ref. SM_ )
The generalized Brillouin zone (GBZ) Yokomizo and Murakami (2019) $C_{z}$ is
thus determined by the trajectory of $z_{2}$ and $z_{3}$ under the condition
$|z_{2}|=|z_{3}|$, where $z_{2}$ and $z_{3}$ are the second and third
solutions to the polynomial sorted by the absolute values in ascending order.
In parallel, we calculate the multi-band winding number (details in Sec. S3)
$w\equiv\sum_{n=1}^{N}\int_{-\pi}^{\pi}\frac{\mathop{}\mathrm{d}k}{2\pi}\partial_{k}\mathrm{arg}(E_{n}(k)-E_{\mathrm{b}}),$
where $E_{\mathrm{b}}$ is a complex OBC energy base point, $n$ labels the band
index, and $N$ is the total number of bands. The sign of $w$ indicates the
localization, i.e. $w>0$ and $w<0$ for left- and right-localization,
respectively, and $w=0$ for extended states. Shown in Fig. 2f, Consistency is
achieved between our non-Bloch and winding-number analyses.

We specifically discuss the properties of zero modes $E=0$ (details in Sec.
S2) under OBC. The associated all four non-Bloch solutions are
$z=\pm\mathrm{i}\sqrt{J_{\mathrm{R}}/J_{\mathrm{L}}\mathrm{e}^{\pm\mathrm{i}\alpha}}$,
where $\alpha=\arctan(\sqrt{1-F^{2}}/F)$ and
$F=\cos(\theta_{\mathrm{R}})\cos(\theta_{\mathrm{L}})$. All roots of the
characteristic polynomial have equal absolute values, guaranteeing the
existence of OBC zero modes, as can be seen by the pinned crossing at $E=0$ in
the complex plane (Fig. 2c). We also prove that the OBC zero modes must be
doubly degenerate (Sec. S2). Furthermore, The absolute values of the zero-mode
non-Bloch solutions depend only on the ratio of the hopping amplitudes, which
indicates that even SU(2) gauge fields cannot modify the localization
direction of the zero modes (proof in Sec. S2).

Nevertheless, the localization of non-zero modes can be effectively
manipulated by non-Abelian gauge fields. The GBZ of the non-Abelian model,
shown in Fig. 2e, exhibits states both inside and outside the unit circle;
these states are thus associated with left- and right-localization,
respectively. We prove that this tunability of the skin modes is not possible
using the U(1) gauge fields in the Abelian Hatano–Nelson model [see Eq. (1)
and proof in Sec. S2.A].

To further elucidate the interplay between the imbalanced hopping amplitudes
and non-Abelian gauge fields, we define a population contrast $\eta$ in the
OBC eigenstates as

$\displaystyle\eta(J_{\mathrm{L}},J_{\mathrm{R}},\theta_{\mathrm{L}},\theta_{\mathrm{R}})\equiv\frac{n_{\mathrm{L}}-n_{\mathrm{R}}}{n_{\mathrm{L}}+n_{\mathrm{R}}+n_{\mathrm{E}}},$
(8)

where $n_{\mathrm{L}}$, $n_{\mathrm{R}}$, and $n_{\mathrm{E}}$ are the number
of left-localized, right-localized, and extended states, respectively. Fig. 3
shows the population contrast as a function of the gauge fields
$(\theta_{\mathrm{L}},\theta_{\mathrm{R}})$ under different choices of
$(J_{\mathrm{L}},J_{\mathrm{R}})$.

Fig. 3a exhibits an equal partition of the left- and right-localization under
$J_{\mathrm{L}}=J_{\mathrm{R}}$, where non-Abelian gauge fields are the only
origin of non-Hermiticity. $\eta$ changes sign across the 45- and 135-degree
lines defined by
$\sin^{2}(\theta_{\mathrm{L}})=\sin^{2}(\theta_{\mathrm{R}})$, exactly the EP
phase transition condition. Notably, when $J_{\mathrm{L}}=J_{\mathrm{R}}$, the
PBC spectrum collapses into an arc that overlaps with the OBC spectrum.
Consequently, the winding number of all OBC energy points is zero, and all
modes are extended. When $\theta_{\mathrm{L}}=\left\\{0,\pi\right\\}$ or
$\theta_{\mathrm{R}}=\left\\{0,\pi\right\\}$, Eq. (5) reduces to the
conventional Hatano-Nelson energy band under $J_{\mathrm{L}}=J_{\mathrm{R}}$,
whose PBC spectrum also collapses into an arc and all OBC modes are extended;
however, there is no phase transition there.

In Fig. 3b and c, as the imbalance between $J_{\mathrm{L}}$ and
$J_{\mathrm{R}}$ appears and increases, localization tunability of the non-
Abelian gauge fields becomes suppressed, as shown by the reduced red-colored
area. Crucially, localization tuning is most effective (indicated by color
variations in Fig. 3) near the EP phase transition [Eq. (6) and solid black
lines in Fig. 3].

Asymptotic analysis (Sec. S4) reveals that the appearance of such tunability
stems from the competition between effective nearest-neighbor and high-order
[$\left(4N-1\right)$-neighbor where $N$ is an integer] coupling. Without loss
of generality, we assume $J_{\mathrm{L}}>J_{\mathrm{R}}$ and obtain asymptotic
expressions (details in Sec. S4) of the eigen-energy $E_{\pm}(k)\simeq$

$\displaystyle
J_{\mathrm{L}}\mathrm{e}^{\pm\mathrm{i}\theta_{\mathrm{L}}}\mathrm{e}^{\mathrm{i}k}+J_{\mathrm{R}}\cos{\theta_{\mathrm{R}}}\mathrm{e}^{-\mathrm{i}k},\text{
if
}\absolutevalue{J_{\mathrm{L}}\sin\theta_{\mathrm{L}}}\gg\absolutevalue{J_{\mathrm{R}}\sin\theta_{\mathrm{R}}},$
(9a) $\displaystyle\begin{aligned}
A(k)\pm\mathrm{i}J_{\mathrm{L}}\sin{\theta_{\mathrm{L}}}\mathrm{e}^{\mathrm{i}k}\sum_{n=0}^{\infty}\mathrm{C}_{n}^{1/2}\left[\left(\frac{J_{\mathrm{R}}\sin{\theta_{\mathrm{R}}}}{J_{\mathrm{L}}\sin{\theta_{\mathrm{L}}}}\right)^{2}\mathrm{e}^{-\mathrm{i}4k}\right]^{n}\\\
\text{ if
}\absolutevalue{J_{\mathrm{L}}\sin\theta_{\mathrm{L}}}\gtrapprox\absolutevalue{J_{\mathrm{R}}\sin\theta_{\mathrm{R}}},\end{aligned}$
(9b) $\displaystyle\begin{aligned}
A(k)\pm\mathrm{i}J_{\mathrm{R}}\sin{\theta_{\mathrm{R}}}\mathrm{e}^{-\mathrm{i}k}\sum_{n=0}^{\infty}\mathrm{C}_{n}^{1/2}\left[\left(\frac{J_{\mathrm{L}}\sin{\theta_{\mathrm{L}}}}{J_{\mathrm{R}}\sin{\theta_{\mathrm{R}}}}\right)^{2}\mathrm{e}^{\mathrm{i}4k}\right]^{n}\\\
\text{ if
}\absolutevalue{J_{\mathrm{L}}\sin\theta_{\mathrm{L}}}\lessapprox\absolutevalue{J_{\mathrm{R}}\sin\theta_{\mathrm{R}}},\end{aligned}$
(9c) $\displaystyle
J_{\mathrm{L}}\cos{\theta_{\mathrm{L}}}\mathrm{e}^{\mathrm{i}k}+J_{\mathrm{R}}\mathrm{e}^{\pm\mathrm{i}\theta_{\mathrm{R}}}\mathrm{e}^{-\mathrm{i}k},\text{
if
}\absolutevalue{J_{\mathrm{L}}\sin\theta_{\mathrm{L}}}\ll\absolutevalue{J_{\mathrm{R}}\sin\theta_{\mathrm{R}}},$
(9d)

where $\mathrm{C}$ denotes combination. Away from the EP phase transition
[Eqs. (9a) and (9d)], the system behaves like a conventional Hatano-Nelson
system with modified hopping amplitudes. Specifically, a complete left-
localization is guaranteed for Eq. (9a) because
$|J_{\mathrm{L}}|>|J_{\mathrm{R}}\cos\theta_{\mathrm{R}}|$, while it
additionally requires
$\absolutevalue{J_{\mathrm{L}}\cos\theta_{\mathrm{L}}}>|J_{\mathrm{R}}|$ for
Eq. (9d). Near the EP phase transition, higher-order terms become non-
negligible, as shown by Eqs. (9b) and (9c) that associate with the two
braiding degrees, respectively. We plot in Fig. 3d two gray-shaded regions
$|J_{\mathrm{L}}\cos{\theta_{\mathrm{L}}}|>|J_{\mathrm{R}}|$ $\cup$
$\absolutevalue{J_{\mathrm{L}}\sin{\theta_{\mathrm{L}}}}>\absolutevalue{J_{\mathrm{R}}\sin{\theta_{\mathrm{R}}}}$.
Their complementary parameter space is colored in white, near which non-
negligible effective high-order hopping occurs. The analysis above indicates
that the simultaneous presence of NHSE on both ends of the open chain and the
localization tunability should appear near the white region, as validated by
the numerical calculation in Fig. 3b.

Figure 3: Tuning non-Hermitian localization with non-Abelian gauge fields.
a-c. Population contrast $\eta$ [Eq. (8)] in the
$(\theta_{\mathrm{L}},\theta_{\mathrm{R}})$ space when
$(J_{\mathrm{L}},J_{\mathrm{R}})=(0.5,0.5)$ (a), $(0.55,0.5)$ (b), and
$(0.6,0.5)$ (c), respectively. The black solid lines define the exceptional-
point phase boundary between the two braiding degrees $\nu=\pm 2$ (see Fig.
1e). d. Analytical asymptotic analysis. Effective high-order hoppings [Eqs.
(9b) and (9c)] are non-negligible in the vicinity of the white region, where
the localization tunability becomes most effective. In d, we use
$(J_{\mathrm{L}},J_{\mathrm{R}})=(0.55,0.5)$, the same as those in b.

In conclusion, we introduce and study non-Abelian gauge fields as an origin of
non-Hermiticity. In a generalized non-Abelian Hatano–Nelson system under
nearest-neighbor coupling only, Hopf-link bulk braiding degrees emerge, whose
phase transition accompanies the appearance of EPs. Near the EP phase
transition, non-Abelian gauge fields also enable NHSE at both ends of an open
chain, and the localization population can be effectively tuned.

Finally, we discuss the potential experimental platforms to realize non-
Abelian gauge fields in non-Hermitian systems. Promising candidates include
time-modulated ring resonators (i.e. the synthetic frequency dimension) Dutt
_et al._ (2019) and time-multiplexed photonic mesh lattices (i.e. the
synthetic time dimension) Regensburger  _et al._ (2011). In both cases, we can
leverage polarization as the pseudospin degree of freedom. The hopping
strength and phases could be engineered by amplitude and phase modulations for
each pseudospin component individually to create the desired non-Abelian gauge
fields. The experimental observables could be the population of localized
modes and their resulting contrast $\eta$ [e.g. Eq. (8)], which can be
spectroscopically measured from the intensity of the frequency components or
temporally resolved from the pulse intensity at the arrival time that
corresponds to the boundaries.

The authors acknowledge the support from the start-up fund of The University
of Hong Kong and the National Natural Science Foundation of China Excellent
Young Scientists Fund (HKU 12222417).

## References

  * Musslimani  _et al._ (2008) Z. Musslimani, K. G. Makris, R. El-Ganainy, and D. N. Christodoulides, Physical Review Letters 100, 030402 (2008).
  * Makris  _et al._ (2008) K. G. Makris, R. El-Ganainy, D. Christodoulides, and Z. H. Musslimani, Physical Review Letters 100, 103904 (2008).
  * Regensburger  _et al._ (2012) A. Regensburger, C. Bersch, M.-A. Miri, G. Onishchukov, D. N. Christodoulides, and U. Peschel, Nature 488, 167 (2012).
  * Feng  _et al._ (2013) L. Feng, Y.-L. Xu, W. S. Fegadolli, M.-H. Lu, J. E. Oliveira, V. R. Almeida, Y.-F. Chen, and A. Scherer, Nature materials 12, 108 (2013).
  * Gao  _et al._ (2015) T. Gao, E. Estrecho, K. Bliokh, T. Liew, M. Fraser, S. Brodbeck, M. Kamp, C. Schneider, S. Höfling, Y. Yamamoto, _et al._ , Nature 526, 554 (2015).
  * Doppler  _et al._ (2016) J. Doppler, A. A. Mailybaev, J. Böhm, U. Kuhl, A. Girschik, F. Libisch, T. J. Milburn, P. Rabl, N. Moiseyev, and S. Rotter, Nature 537, 76 (2016).
  * Yao and Wang (2018) S. Yao and Z. Wang, Physical review letters 121, 086803 (2018).
  * Song  _et al._ (2019) F. Song, S. Yao, and Z. Wang, Physical review letters 123, 246801 (2019).
  * Kunst  _et al._ (2018) F. K. Kunst, E. Edvardsson, J. C. Budich, and E. J. Bergholtz, Physical review letters 121, 026808 (2018).
  * Xiong (2018) Y. Xiong, Journal of Physics Communications 2, 035043 (2018).
  * Bergholtz  _et al._ (2021) E. J. Bergholtz, J. C. Budich, and F. K. Kunst, Reviews of Modern Physics 93, 015005 (2021).
  * Gong  _et al._ (2018) Z. Gong, Y. Ashida, K. Kawabata, K. Takasan, S. Higashikawa, and M. Ueda, Physical Review X 8, 031079 (2018).
  * Kawabata  _et al._ (2019) K. Kawabata, K. Shiozaki, M. Ueda, and M. Sato, Physical Review X 9, 041015 (2019).
  * Yokomizo and Murakami (2019) K. Yokomizo and S. Murakami, Physical review letters 123, 066404 (2019).
  * Zhang  _et al._ (2020) K. Zhang, Z. Yang, and C. Fang, Physical Review Letters 125, 126402 (2020).
  * Okuma  _et al._ (2020) N. Okuma, K. Kawabata, K. Shiozaki, and M. Sato, Physical review letters 124, 086801 (2020).
  * Yang  _et al._ (2020a) Z. Yang, K. Zhang, C. Fang, and J. Hu, Physical Review Letters 125, 226402 (2020a).
  * Wang  _et al._ (2021a) K. Wang, A. Dutt, C. C. Wojcik, and S. Fan, Nature 598, 59 (2021a).
  * Hu and Zhao (2021) H. Hu and E. Zhao, Physical Review Letters 126, 010401 (2021).
  * Borgnia  _et al._ (2020) D. S. Borgnia, A. J. Kruchkov, and R.-J. Slager, Physical review letters 124, 056802 (2020).
  * Lee (2016) T. E. Lee, Physical review letters 116, 133903 (2016).
  * Weidemann  _et al._ (2020) S. Weidemann, M. Kremer, T. Helbig, T. Hofmann, A. Stegmaier, M. Greiter, R. Thomale, and A. Szameit, Science 368, 311 (2020).
  * Wang  _et al._ (2021b) K. Wang, A. Dutt, K. Y. Yang, C. C. Wojcik, J. Vučković, and S. Fan, Science 371, 1240 (2021b).
  * Xiao  _et al._ (2020) L. Xiao, T. Deng, K. Wang, G. Zhu, Z. Wang, W. Yi, and P. Xue, Nature Physics 16, 761 (2020).
  * Liu  _et al._ (2022) Y. G. Liu, Y. Wei, O. Hemmatyar, G. G. Pyrialakos, P. S. Jung, D. N. Christodoulides, and M. Khajavikhan, Light: Science & Applications 11, 336 (2022).
  * Zhang  _et al._ (2021a) X. Zhang, Y. Tian, J.-H. Jiang, M.-H. Lu, and Y.-F. Chen, Nature communications 12, 5377 (2021a).
  * Zhang  _et al._ (2021b) L. Zhang, Y. Yang, Y. Ge, Y.-J. Guan, Q. Chen, Q. Yan, F. Chen, R. Xi, Y. Li, D. Jia, _et al._ , Nature communications 12, 6297 (2021b).
  * Gu  _et al._ (2022) Z. Gu, H. Gao, H. Xue, J. Li, Z. Su, and J. Zhu, Nature Communications 13, 7668 (2022).
  * Wang  _et al._ (2022) W. Wang, X. Wang, and G. Ma, Nature 608, 50 (2022).
  * Ghatak  _et al._ (2020) A. Ghatak, M. Brandenbourger, J. Van Wezel, and C. Coulais, Proceedings of the National Academy of Sciences 117, 29561 (2020).
  * Scheibner  _et al._ (2020) C. Scheibner, W. T. Irvine, and V. Vitelli, Physical Review Letters 125, 118001 (2020).
  * Li  _et al._ (2020) L. Li, C. H. Lee, S. Mu, and J. Gong, Nature communications 11, 5491 (2020).
  * Helbig  _et al._ (2020) T. Helbig, T. Hofmann, S. Imhof, M. Abdelghany, T. Kiessling, L. Molenkamp, C. Lee, A. Szameit, M. Greiter, and R. Thomale, Nature Physics 16, 747 (2020).
  * Hofmann  _et al._ (2020) T. Hofmann, T. Helbig, F. Schindler, N. Salgo, M. Brzezińska, M. Greiter, T. Kiessling, D. Wolf, A. Vollhardt, A. Kabaši, _et al._ , Physical Review Research 2, 023265 (2020).
  * Liu  _et al._ (2021) S. Liu, R. Shao, S. Ma, L. Zhang, O. You, H. Wu, Y. J. Xiang, T. J. Cui, and S. Zhang, Research , 5608038 (2021).
  * Zou  _et al._ (2021) D. Zou, T. Chen, W. He, J. Bao, C. H. Lee, H. Sun, and X. Zhang, Nature Communications 12, 7201 (2021).
  * Shang  _et al._ (2022) C. Shang, S. Liu, R. Shao, P. Han, X. Zang, X. Zhang, K. N. Salama, W. Gao, C. H. Lee, R. Thomale, _et al._ , Advanced Science 9, 2202922 (2022).
  * Lin  _et al._ (2021) Z. Lin, L. Ding, S. Ke, and X. Li, Optics Letters 46, 3512 (2021).
  * Midya  _et al._ (2018) B. Midya, H. Zhao, and L. Feng, Nature communications 9, 2674 (2018).
  * Longhi (2017a) S. Longhi, Physical Review B 95, 014201 (2017a).
  * Longhi  _et al._ (2015) S. Longhi, D. Gatti, and G. Della Valle, Physical Review B 92, 094204 (2015).
  * Longhi (2017b) S. Longhi, Physical Review A 95, 062122 (2017b).
  * Wong and Oh (2021) S. Wong and S. S. Oh, Physical Review Research 3, 033042 (2021).
  * Chen  _et al._ (2019) Y. Chen, R.-Y. Zhang, Z. Xiong, Z. H. Hang, J. Li, J. Q. Shen, and C. T. Chan, Nature communications 10, 1 (2019).
  * Yang  _et al._ (2019) Y. Yang, C. Peng, D. Zhu, H. Buljan, J. D. Joannopoulos, B. Zhen, and M. Soljačić, Science 365, 1021 (2019).
  * Yang  _et al._ (2020b) E. Yang, B. Yang, O. You, H.-C. Chan, P. Mao, Q. Guo, S. Ma, L. Xia, D. Fan, Y. Xiang, _et al._ , Physical Review Letters 125, 033901 (2020b).
  * Guo  _et al._ (2021) Q. Guo, T. Jiang, R.-Y. Zhang, L. Zhang, Z.-Q. Zhang, B. Yang, S. Zhang, and C. T. Chan, Nature 594, 195 (2021).
  * Jiang  _et al._ (2021) B. Jiang, A. Bouhon, Z.-K. Lin, X. Zhou, B. Hou, F. Li, R.-J. Slager, and J.-H. Jiang, Nature Physics 17, 1239 (2021).
  * Brosco  _et al._ (2021) V. Brosco, L. Pilozzi, R. Fazio, and C. Conti, Physical Review A 103, 063518 (2021).
  * Chen  _et al._ (2022) Z.-G. Chen, R.-Y. Zhang, C. T. Chan, and G. Ma, Nature Physics 18, 179 (2022).
  * Sun  _et al._ (2022) Y.-K. Sun, X.-L. Zhang, F. Yu, Z.-N. Tian, Q.-D. Chen, and H.-B. Sun, Nature Physics 18, 1080 (2022).
  * You  _et al._ (2022) O. You, S. Liang, B. Xie, W. Gao, W. Ye, J. Zhu, and S. Zhang, Physical Review Letters 128, 244302 (2022).
  * Noh  _et al._ (2020) J. Noh, T. Schuster, T. Iadecola, S. Huang, M. Wang, K. P. Chen, C. Chamon, and M. C. Rechtsman, Nature Physics 16, 989 (2020).
  * Zhang  _et al._ (2022a) X.-L. Zhang, F. Yu, Z.-G. Chen, Z.-N. Tian, Q.-D. Chen, H.-B. Sun, and G. Ma, Nature Photonics 16, 390 (2022a).
  * Xu  _et al._ (2016) J.-S. Xu, K. Sun, Y.-J. Han, C.-F. Li, J. K. Pachos, and G.-C. Guo, Nature communications 7, 1 (2016).
  * Yang  _et al._ (2020c) Y. Yang, B. Zhen, J. D. Joannopoulos, and M. Soljačić, Light: Science & Applications 9, 177 (2020c).
  * Yang  _et al._ (2022) Y. Yang, H. C. Po, V. Liu, J. D. Joannopoulos, L. Fu, and M. Soljačić, Physical Review B 106, L161108 (2022).
  * Gianfrate  _et al._ (2020) A. Gianfrate, O. Bleu, L. Dominici, V. Ardizzone, M. De Giorgi, D. Ballarini, G. Lerario, K. W. West, L. N. Pfeiffer, D. D. Solnyshkov, D. Sanvitto, and G. Malpuech, Nature 578, 381 (2020).
  * Whittaker  _et al._ (2021) C. Whittaker, T. Dowling, A. Nalitov, A. Yulin, B. Royall, E. Clarke, M. Skolnick, I. Shelykh, and D. Krizhanovskii, Nature Photonics 15, 193 (2021).
  * Iadecola  _et al._ (2016) T. Iadecola, T. Schuster, and C. Chamon, Phys. Rev. Lett. 117, 073901 (2016).
  * Polimeno  _et al._ (2021) L. Polimeno, A. Fieramosca, G. Lerario, L. De Marco, M. De Giorgi, D. Ballarini, L. Dominici, V. Ardizzone, M. Pugliese, C. Prontera, _et al._ , Optica 8, 1442 (2021).
  * Cheng  _et al._ (2023) D. Cheng, K. Wang, and S. Fan, Physical Review Letters 130, 083601 (2023).
  * Aidelsburger  _et al._ (2018) M. Aidelsburger, S. Nascimbene, and N. Goldman, Comptes Rendus Physique 19, 394 (2018).
  * Wu  _et al._ (2022) J. Wu, Z. Wang, Y. Biao, F. Fei, S. Zhang, Z. Yin, Y. Hu, Z. Song, T. Wu, F. Song, _et al._ , Nature Electronics 5, 635 (2022).
  * Lin  _et al._ (2011) Y.-J. Lin, K. Jiménez-García, and I. B. Spielman, Nature 471, 83 (2011).
  * Hatano and Nelson (1996) N. Hatano and D. R. Nelson, Physical review letters 77, 570 (1996).
  * Zhou (2023) L. Zhou, arXiv preprint arXiv:2302.05710 10.48550/arXiv.2302.05710 (2023).
  * Yang and Hu (2019) Z. Yang and J. Hu, Physical Review B 99, 081102 (2019).
  * Carlström and Bergholtz (2018) J. Carlström and E. J. Bergholtz, Physical Review A 98, 042114 (2018).
  * Zhang  _et al._ (2022b) X. Zhang, T. Zhang, M.-H. Lu, and Y.-F. Chen, Advances in Physics: X 7, 2109431 (2022b).
  * Ashida  _et al._ (2020) Y. Ashida, Z. Gong, and M. Ueda, Advances in Physics 69, 249 (2020).
  * (72) See Supplementary Materials for additional notes on (i) Hopf link, (ii) Non-Bloch wave approach, (iii) Winding-number approach, (iv) zero modes, and (v) asymptotic analysis.
  * Dutt  _et al._ (2019) A. Dutt, M. Minkov, Q. Lin, L. Yuan, D. A. Miller, and S. Fan, Nature communications 10, 3122 (2019).
  * Regensburger  _et al._ (2011) A. Regensburger, C. Bersch, B. Hinrichs, G. Onishchukov, A. Schreiber, C. Silberhorn, and U. Peschel, Physical review letters 107, 233902 (2011).