# On Free $\omega$-Continuous and Regular Ordered Algebras

Zoltán Ésik  Institute of Informatics, University of Szeged, P.O. Box 652,
H-6701 Szeged, Hungary  and  Dexter Kozen  Computer Science Department,
Cornell University, Ithaca, NY 14853-7501, USA<EMAIL_ADDRESS>
###### Abstract.

Let $E$ be a set of inequalities between finite $\Sigma$-terms. Let
${\mathcal{V}}_{\omega}$ and ${\mathcal{V}}_{r}$ denote the varieties of all
$\omega$-continuous ordered $\Sigma$-algebras and regular ordered
$\Sigma$-algebras satisfying $E$, respectively. We prove that the free
${\mathcal{V}}_{r}$-algebra $R(X)$ on generators $X$ is the subalgebra of the
corresponding free ${\mathcal{V}}_{\omega}$-algebra $F_{\omega}(X)$ determined
by those elements of $F_{\omega}(X)$ denoted by the regular $\Sigma$-coterms.
We actually establish this fact as a special case of a more general
construction for families of algebras specified by syntactically restricted
completeness and continuity properties. Thus our result is also applicable to
ordered regular algebras of higher order.

###### Key words and phrases:

Regular algebra; $\omega$-continuous algebra; iteration theories

##  1\. $\omega$-Continuous Algebras

Let $\Sigma$ be a ranked alphabet, which will be fixed throughout. A
$\Sigma$-algebra $A$ is called _ordered_ if $A$ is partially ordered by a
relation $\leq$ with least element $\bot^{A}$ and the algebraic operations are
monotone with respect to $\leq$; that is, if $f\in\Sigma_{n}$ and
$a_{i},b_{i}\in A$ with $a_{i}\leq b_{i}$ for $1\leq i\leq n$, then
$f^{A}(a_{1},\ldots,a_{n})\leq f^{A}(b_{1},\ldots,b_{n})$. A morphism $h:A\to
B$ of ordered algebras is a strict monotone map that commutes with the
algebraic operations:

$\displaystyle a\leq b\Rightarrow h(a)\leq h(b)\qquad\
h(\bot^{A})=\bot^{B}\qquad\
h(f^{A}(a_{1},\ldots,a_{n}))=f^{B}(h(a_{1}),\ldots,h(a_{n}))$

for all $a,b,a_{1},\ldots,a_{n}\in A$ and $f\in\Sigma_{n}$, $n\geq 0$.

For each set $X$, there is a free ordered algebra $\mathsf{T}X$ freely
generated by $X$. The elements of $\mathsf{T}X$ are represented by the finite
partial $\Sigma$-terms over $X$; here _partial_ means that some subterms may
be missing, which is the same as having the empty term $\bot^{\mathsf{T}X}$ in
that position. When $t\in\mathsf{T}X$ and $A$ is an ordered algebra, $t$
induces a function $t^{A}:A^{X}\to A$ in the usual way.

An ordered algebra $A$ is _$\omega$ -continuous_ [5, 7, 8] if it is
$\omega$-complete and the operations are $\omega$-continuous. That is, any
countable directed set (or countable chain) $C$ has a supremum $\bigvee C$,
and when $n\geq 0$, $f\in\Sigma_{n}$, and $C_{i}$ is a countable directed set
for $1\leq i\leq n$, then

$\displaystyle f^{A}(\bigvee C_{1},\ldots,\bigvee C_{n})$
$\displaystyle=\bigvee\\{f^{A}(x_{1},\ldots,x_{n})\mid x_{i}\in C_{i},\ 1\leq
i\leq n\\}.$

A morphism of $\omega$-continuous algebras is an $\omega$-continuous ordered
algebra morphism.

For each set $X$, there is a free $\omega$-continuous algebra $\mathsf{C}X$
freely generated by $X$. The elements of $\mathsf{C}X$ are the partial coterms
over $\Sigma$ (finite or infinite partial terms). When $t\in\mathsf{C}X$ and
$A$ is an $\omega$-continuous algebra, $t$ induces a function $t^{A}:A^{X}\to
A$.

Suppose that $X_{\omega}$ is a fixed countably infinite set. A set of
inequalities $t\sqsubseteq t^{\prime}$ between terms in
$\mathsf{T}{X_{\omega}}$ determines in the usual way a _variety of ordered
algebras_ , denoted ${\mathcal{V}}$, and a _variety of $\omega$-continuous
algebras_, devoted ${\mathcal{V}}_{\omega}$. An ordered algebra $A$ belongs to
${\mathcal{V}}$ iff $t^{A}\leq t^{\prime A}$ in the pointwise ordering of
functions $A^{X_{\omega}}\to A$ whenever $t\sqsubseteq t^{\prime}$ is in $E$.
The class ${\mathcal{V}}_{\omega}$ contains all $\omega$-continuous algebras
in ${\mathcal{V}}$. It is known that all free algebras exist both in
${\mathcal{V}}$ and in ${\mathcal{V}}_{\omega}$ [3, 8]. Moreover, the free
algebra in ${\mathcal{V}}$ freely generated by a set $X$ can be represented as
the $X$-generated ordered subalgebra $F(X)$ of the free $\omega$-continuous
algebra $F_{\omega}(X)$ in ${\mathcal{V}}_{\omega}$. Moreover, $F_{\omega}(X)$
is the completion of $F(X)$ by $\omega$-ideals (see §2).

More generally, for $C$ a subset of an ordered algebra $A$, define

$\displaystyle{C}\kern-2.0pt\downarrow$ $\displaystyle=\\{c\mid\exists a\in C\
c\leq a\\}.$

The set $C$ is an _order ideal_ if it is directed and downward closed; that
is, if $a,b\in C$ implies there exists $c\in C$ such that $a,b\leq c$, and if
$a\leq b$ and $b\in C$, then $a\in C$, i.e. $C={C}\kern-2.0pt\downarrow$. An
order ideal $C\mathrel{\subseteq}A$ is called an _$\omega$ -ideal_ if it is
countably generated; that is, there is a countable directed set
$C_{0}\mathrel{\subseteq}C$ such that $C={C_{0}}\kern-2.0pt\downarrow$. The
set $I_{\omega}(A)$ of all $\omega$-ideals of $A$ ordered by set inclusion
$\mathrel{\subseteq}$ is an $\omega$-complete poset, where the supremum of an
$\omega$-ideal $\mathcal{A}$ of $\omega$-ideals is the union
$\bigcup\mathcal{A}$. We can turn $I_{\omega}(A)$ into an $\omega$-continuous
algebra by defining

$\displaystyle f^{I_{\omega}(A)}(C_{1},\ldots,C_{n})$
$\displaystyle={\\{f^{A}(a_{1},\ldots,a_{n})\mid a_{i}\in C_{i},\ 1\leq i\leq
n\\}}\kern-2.0pt\downarrow,$

the order ideal generated by the set $\\{f^{A}(a_{1},\ldots,a_{n})\mid
a_{i}\in C_{i},\ 1\leq i\leq n\\}$. It is clear that $A$ can be embedded in
$I_{\omega}(A)$ by the ordered algebra morphism mapping $a\in A$ to the order
ideal ${\\{a\\}}\kern-2.0pt\downarrow$ generated by $a$. In fact, it is known
that $I_{\omega}(A)$ is the _free completion_ of $A$ to an $\omega$-continuous
algebra [3, 8]. In particular, $\mathsf{C}X$ is isomorphic to
$I_{\omega}(\mathsf{T}X)$ for all $X$.

##  2\. Free Completion

Every ordered algebra can be completed to an $\omega$-continuous algebra by
the method of completion by $\omega$-ideals. This result is well known and can
be proved by standard universal-algebraic argument [3, 8]. In this section we
give a more general construction that will allow us to apply this idea more
widely.

Suppose we have a monad $(F,\mu^{F},\eta^{F})$ on some category $C$.

$F^{3}$$F^{2}$$F^{2}$$F$$F\mu^{F}$$\mu^{F}F$$\mu^{F}$$\mu^{F}$$F$$F^{2}$$F^{2}$$F$$F\eta^{F}$$\eta^{F}F$$1F$$\mu^{F}$$\mu^{F}$
(1)

An _$F$ -algebra_ (aka Eilenberg–Moore algebra for $F$) is a pair
$(X,\alpha)$, where $\alpha:FX\to X$ is the _structure map_ of the algebra. It
must satisfy

$F^{2}X$$FX$$FX$$X$$F\alpha$$\mu^{F}_{X}$$\alpha$$\alpha$$X$$FX$$X$$\eta^{F}_{X}$$1_{X}$$\alpha$
(2)

An _$F$ -algebra morphism_ is a morphism of the underlying category $C$ that
commutes with the structure maps. The category of $F$-algebras and $F$-algebra
morphisms is denoted $F\mbox{-}\mathsf{Alg}$.

In our application, the underlying category $C$ is the category of posets with
$\bot$ and strict monotone maps. An $F$-algebra is a pair $(X,\alpha)$ where
$\alpha:FX\to X$ is a morphism of $C$. For functors representing algebraic
signatures (polynomial functors with an added $\bot$ or partial term
algebras), this implies that the algebraic operations are monotone, but not
necessarily strict.

The free ordered algebra $\mathsf{T}X$ and the free $\omega$-continuous
algebra $\mathsf{C}X$ are Eilenberg-Moore algebras for the partial term monad
and partial coterm monad for the signature $\Sigma$, respectively.

Suppose further that we have another monad $(D,\mu^{D},\eta^{D})$ on $C$,
along with a distributive law $\lambda:FD\to DF$.

$FD^{2}$$DFD$$D^{2}F$$FD$$DF$$\lambda
D$$F\mu^{D}$$D\lambda$$\mu^{D}F$$F^{2}D$$FDF$$DF^{2}$$F\lambda$$\mu^{F}D$$\lambda
F$$D\mu^{F}$$\lambda$$F$$FD$$DF$$F\eta^{D}$$\eta^{D}F$$D$$\eta^{F}D$$D\eta^{F}$$\lambda$
(3)

One can show that $D$ lifts to a monad $(\widehat{D},\mu^{D},\eta^{D})$ on
$F\mbox{-}\mathsf{Alg}$ with

$\displaystyle\widehat{D}(X,\alpha)$
$\displaystyle=(DX,D\alpha\circ\lambda_{X})$ $\displaystyle\widehat{D}h$
$\displaystyle=Dh.$

The monad operations $\mu^{D}$ and $\eta^{D}$ of $\widehat{D}$ are the same as
those of $D$. The monad laws (1) hold for $\widehat{D}$ because they are the
same as those for $D$. We must also show that the Eilenberg-Moore properties
(2) hold and that $\mu^{D}_{X}$, $\eta^{D}_{X}$ are $F\mbox{-}\mathsf{Alg}$
morphisms.

$F^{2}DX$$FDX$$FDX$$DX$$F(D\alpha\circ\lambda_{X})$$\mu^{F}_{DX}$$D\alpha\circ\lambda_{X}$$D\alpha\circ\lambda_{X}$$DX$$FDX$$DX$$\eta^{F}_{DX}$$1_{DX}$$D\alpha\circ\lambda_{X}$
$FD^{2}X$$FDX$$D^{2}X$$DX$$F\mu^{D}_{X}$$D(D\alpha\circ\lambda_{X})\circ\lambda_{DX}$$\mu^{D}_{X}$$D\alpha\circ\lambda_{X}$$FX$$FDX$$X$$DX$$F\eta^{D}_{X}$$\alpha$$\eta^{D}_{X}$$D\alpha\circ\lambda_{X}$

These results follow from the monad properties (1) for $F$ and $D$, the
Eilenberg-Moore properties (2) for $(X,\alpha)$, and the distributive laws (3)
by straightforward arrow chasing.

Now suppose $(X,\beta)$ is a $D$-algebra. Under what conditions can we
sensibly augment an $F$-algebra $(X,\alpha)$ with the new operation $\beta$? A
sufficient condition is when $((X,\alpha),\beta)$ forms a
$\widehat{D}$-algebra; that is, when $\beta$ is an $F\mbox{-}\mathsf{Alg}$
morphism $\beta:\widehat{D}(X,\alpha)\to(X,\alpha)$.

$FDX$$DX$$FX$$X$$D\alpha\circ\lambda_{X}$$F\beta$$\alpha$$\beta$ (4)

This gives an $F+D$-algebra $(X,\alpha,\beta)=((X,\alpha),\beta)$ is in which
$D$ distributes over $F$. Moreover, this is also a $\widehat{D}$-algebra,
since the conditions (2) are the same.

Now, as is well known, because we have a monad
$(\widehat{D},\mu^{D},\eta^{D})$, the functor
$(X,\alpha)\mapsto(DX,D\alpha\circ\lambda_{X},\mu^{D}_{X})$ is left adjoint to
the forgetful functor $(X,\alpha,\beta)\mapsto(X,\alpha)$. The algebra
$(DX,D\alpha\circ\lambda_{X},\mu^{D}_{X})$ is the free completion of
$(X,\alpha)$. The unit of the adjunction
$\eta^{D}_{X}:(X,\alpha)\to(DX,D\alpha\circ\lambda_{X})$ embeds the original
$F$-algebra in its completion. The counit
$(DX,D\alpha\circ\lambda_{X},\mu^{D}_{X})\to(X,\alpha,\beta)$ is $\beta$.

Let $C$ be the category of posets with $\bot$ and strict monotone maps.
Consider the monad $(D,\mu^{D},\eta^{D})$ such that $DX$ is the set of all
countably generated order ideals ordered by set inclusion.

$\displaystyle DX$ $\displaystyle=\\{{A}\kern-2.0pt\downarrow\ \mid
A\mathrel{\subseteq}X,\ \text{$A$ is a countable directed set}\\}.$

For $\mathcal{A}\mathrel{\subseteq}DX$ a countable directed set of order
ideals of $X$, and for $x\in X$, let

$\displaystyle\mu^{D}_{X}({\mathcal{A}}\kern-2.0pt\downarrow)$
$\displaystyle={(\textstyle\bigcup\mathcal{A})}\kern-2.0pt\downarrow$
$\displaystyle\eta^{D}_{X}(a)$ $\displaystyle={\\{a\\}}\kern-2.0pt\downarrow.$

The distributive law $\lambda_{X}:FDX\to DFX$ takes a term or coterm over a
countable collection of order ideals to an order ideal of terms or coterms
over $X$ of the same shape. For example, for $f\in\Sigma_{n}$,

$\displaystyle\lambda_{X}:f(A_{1},\ldots,A_{n})\ \mapsto\
{\\{f(a_{1},\ldots,a_{n})\mid a_{i}\in A_{i},\ 1\leq i\leq
n\\}}\kern-2.0pt\downarrow.$

If $(X,\alpha)$ is an ordered $\Sigma$-algebra, applying $D\alpha$ to the
right-hand side applies $\alpha$ to every element of that set, which is the
same as interpreting the term in the $F$-algebra $(X,\alpha)$. For example,

$\displaystyle D\alpha\circ\lambda_{X}:f(A_{1},\ldots,A_{n})\ \mapsto\
{\\{f^{(X,\alpha)}(a_{1},\ldots,a_{n})\mid a_{i}\in A_{i},\ 1\leq i\leq
n\\}}\kern-2.0pt\downarrow.$

This is the algebra $\widehat{D}(X,\alpha)=(DX,D\alpha\circ\lambda_{X})$.

An Eilenberg-Moore algebra $(X,\beta)$ for the monad $D$ is simply an
$\omega$-complete poset, the operation $\beta:DX\to X$ giving the supremum of
a countably generated directed set. The property (4) says exactly that the
algebraic operations commute with the supremum operator; that is, the
algebraic operations are $\omega$-continuous.

The $\widehat{D}$-algebra $(DX,D\alpha\circ\lambda_{X},\mu^{D}_{X})$, the free
extension of $(X,\alpha)$ to an $F+D$-algebra, is the completion by countably
generated order ideals. The unit of the adjunction
$\eta^{D}_{X}:(X,\alpha)\to(DX,D\alpha\circ\lambda_{X},\mu^{D}_{X})$ embeds
the original $F$-algebra in its ideal completion. The counit
$(DX,D\alpha\circ\lambda_{X},\mu^{D}_{X})\to(X,\alpha,\beta)$ is the supremum
operator $\beta$.

##  3\. Quasi-Regular Families

In this section we study limited completeness conditions in which not all
suprema need exist, but only those of a certain syntactically restricted form.

For each set $X$, let $\Delta X$ denote an ordered subalgebra of $\mathsf{C}X$
containing $X$. The set $\Delta X$ is a set of partial coterms closed under
the algebraic operations $\Sigma$. Note that each finite term in $\mathsf{T}X$
is in $\Delta X$, thus $\mathsf{T}X\mathrel{\subseteq}\Delta
X\mathrel{\subseteq}\mathsf{C}X$.

We further assume for all $X$ and $Y$ and for all morphisms
$h:\mathsf{C}X\to\mathsf{C}Y$ of $\omega$-continuous algebras with
$h(X)\mathrel{\subseteq}\Delta Y$ that $h(\Delta X)\mathrel{\subseteq}\Delta
Y$. A family of term algebras $(\Delta X)_{X}$ satisfying this property is
called a _quasi-regular family_.

Under these conditions, $\Delta$ determines a submonad
$(\Delta,\mu^{\Delta},\eta^{\Delta})$ of the coterm monad. The monad
operations are the same, except with suitably restricted domain. Thus
$\eta^{\Delta}_{X}:X\to\Delta X$ makes a singleton term $x$ out of an element
$x\in X$, and $\mu^{\Delta}_{X}:\Delta^{2}X\to\Delta X$ takes a term of terms
over $X$ and collapses it to a term over $X$.

Two examples of quasi-regular families are $\Delta X=\mathsf{C}X$, the set of
all partial coterms over $X$, and $\Delta X=\mathsf{T}X$, the set of all
partial terms over $X$. These are the maximum and minimum quasi-regular
families, respectively, for a given signature $\Sigma$. The regular or
algebraic trees [5, 8], or more generally, the set of regular (or rational)
trees of order $n$ [6] also form quasi-regular families. Also, the union of
the $n$-regular trees over $X$ for all $n\geq 0$ is a quasi-regular family.

######  Lemma 1.

For any set $X$, the set $\Delta X$ is uniquely determined by
$\Delta{X_{\omega}}$.

######  Proof 3.1.

Let $h:X\to Y$ be an injection. Then $h$ extends uniquely to a morphism
$\widehat{h}=\mu_{Y}\circ\Delta h:\Delta X\to\Delta Y$ of $\omega$-continuous
algebras. We claim that

$\displaystyle\Delta Y$ $\displaystyle=\\{\widehat{h}(t)\mid
X\mathrel{\subseteq}X_{\omega},\ \text{$h:X\to Y$ is an injection},\
t\in\Delta X\\}.$

The reverse inclusion holds by our assumption $\widehat{h}(\Delta
X)\mathrel{\subseteq}\Delta Y$. For the forward inclusion, suppose $s\in\Delta
Y$. Then $s\in\Delta Y^{\prime}$ for some finite or countable subset
$Y^{\prime}\mathrel{\subseteq}Y$, as there are at most countably many subterms
of $s$. Let $X\mathrel{\subseteq}X_{\omega}$ be of the same cardinality as
$Y^{\prime}$ and let $h:X\to Y^{\prime}$ be a bijection. Then
$\widehat{h}^{-1}(s)\in\Delta X_{\omega}$, $h:X\to Y$ is an injection, and
$s=\widehat{h}(\widehat{h}^{-1}(s))$.

For terms $t_{1},t_{2}\in\mathsf{C}X$, define $t_{1}\ll t_{2}$ if $t_{1}$ is
finite, but agrees as a labeled tree with $t_{2}$ wherever it is defined. That
is, $t_{1}\in\mathsf{T}X$ and $t_{1}$ can be obtained from $t_{2}$ by deleting
subterms. Clearly $t_{1}\leq t_{2}$ whenever $t_{1}\ll t_{2}$.

Let $A$ be an ordered $\Sigma$-algebra. The structure map
$\beta:\mathsf{T}A\to A$ interprets finite terms as elements of $A$. A set
$B\mathrel{\subseteq}A$ is called a _$\Delta$ -set_ if there is a term
$t\in\Delta A$ such that $B=\\{\beta(s)\mid s\ll t\\}$. The set $\\{s\mid s\ll
t\\}$ is a countable directed subset of $\mathsf{T}A$, and as $\beta$
preserves order, $B$ is a countable directed subset of $A$.

We say that an ordered algebra $A$ is a _$\Delta$ -regular algebra_ if the
suprema of all $\Delta$-sets exist and the algebraic operations preserve the
suprema of $\Delta$-sets.

We will show that any $\Delta$-regular algebra can be extended to an
Eilenberg-Moore algebra for the monad $\Delta$. Note that $\Delta X$ itself is
a $\Delta$-regular algebra. This is due to the fact that $\Delta$ is a monad.

######  Theorem 2.

Let $A$ be a $\Delta$-regular algebra with structure map $\beta:\mathsf{T}A\to
A$. Extend $\beta$ to domain $\Delta A$ by defining

$\displaystyle\beta(t)=\bigvee\\{\beta(s)\mid s\ll t\\}.$

The suprema of $\Delta$-sets exist by assumption. Then $A$ with the extended
structure map $\beta$ is an Eilenberg-Moore algebra for the monad $\Delta$.

######  Proof 3.2.

We must show that the Eilenberg-Moore properties (2) hold: $\beta(a)=a$, and
for any indexed set $(s_{i}\mid i\in I)$ of elements of $\Delta A$ and
$t(s_{i}\mid i\in I)\in\Delta^{2}A$,

$\displaystyle\beta(t(s_{i}\mid i\in I))$
$\displaystyle=\beta(t(\beta(s_{i})\mid i\in I)).$ (5)

The first property holds since $(A,\beta)$ is an Eilenberg-Moore algebra for
the term monad $\mathsf{T}$. Property (5) holds for finite $t$ and finite
$s_{i}$ for the same reason.

More generally, by our assumption that the algebraic operators preserve
suprema of $\Delta$-sets, it follows by induction that for finite
$t\in\mathsf{T}\\{x_{1},\ldots,x_{n}\\}$ and $s_{i}\in\Delta A$, $1\leq i\leq
n$,

$\displaystyle\beta(t(\beta(s_{1}),\ldots,\beta(s_{n}))$
$\displaystyle=\bigvee_{\begin{subarray}{c}s_{i}^{\prime}\ll s_{i}\\\ 1\leq
i\leq
n\end{subarray}}\beta(t(\beta(s_{1}^{\prime}),\ldots,\beta(s_{n}^{\prime}))).$
(6)

Now to show (5) in the general case,

$\displaystyle\beta(t(s_{i}\mid i\in I))$
$\displaystyle=\bigvee_{t^{\prime}\ll t(s_{i}\mid i\in I)}\beta(t^{\prime})$
(7) $\displaystyle=\bigvee_{t^{\prime}\ll t}\
\bigvee_{\begin{subarray}{c}s_{i}^{\prime}\ll s_{i}\\\ i\in
I\end{subarray}}\beta(t^{\prime}(s_{i}^{\prime}\mid i\in I))$ (8)
$\displaystyle=\bigvee_{t^{\prime}\ll t}\
\bigvee_{\begin{subarray}{c}s_{i}^{\prime}\ll s_{i}\\\ i\in
I\end{subarray}}\beta(t^{\prime}(\beta(s_{i}^{\prime})\mid i\in I))$ (9)
$\displaystyle=\bigvee_{t^{\prime}\ll t}\ \beta(t^{\prime}(\beta(s_{i})\mid
i\in I))$ (10) $\displaystyle=\beta(t(\beta(s_{i})\mid i\in I)).$ (11)

Step (7) is by definition of $\beta$. Step (8) is by definition of $\ll$. Step
(9) is by property (5) for finite terms. Step (10) is by property (6).
Finally, step (11) is by definition of $\beta$.

We have shown that every $\Delta$-regular algebra is a $\Delta$-algebra, that
is, an Eilenberg-Moore algebra for the monad $\Delta$. Henceforth, we drop the
“regular” and just call them $\Delta$-algebras.

The value of $\beta$ is uniquely determined on all elements of $\Delta A$,
thus each ordered algebra with $\bot$ can be turned into a $\Delta$-algebra in
at most one way. Moreover, every $\Delta$-algebra is determined by the
interpretation of the terms in $\Delta(X_{\omega})$.

A _morphism_ of $\Delta$-algebras is a morphism on the carriers as ordered
sets with $\bot$ that commutes with the structure maps. It follows that any
morphism of $\Delta$-algebras preserves suprema of $\Delta$-sets, as we now
show.

######  Theorem 3.

Let $(A,\alpha)$ and $(B,\beta)$ be $\Delta$-algebras and $h:A\to B$ a
morphism. For any $\Delta$-set $D\mathrel{\subseteq}A$, its image $\\{h(a)\mid
a\in D\\}\mathrel{\subseteq}B$ is a $\Delta$-set in $B$, and

$\displaystyle h(\bigvee D)$ $\displaystyle=\bigvee\\{h(a)\mid a\in D\\}.$

######  Proof 3.3.

Let $t\in\Delta A$ such that $D=\\{\alpha(s)\mid s\ll t\\}$. We must show that
$\\{h(\alpha(s))\mid s\ll t\\}$ is a $\Delta$-set in $B$ and

$\displaystyle h(\alpha(t))$ $\displaystyle=\bigvee\\{h(\alpha(s))\mid s\ll
t\\}.$

Since $h$ commutes with the structure maps,

$\displaystyle\\{h(\alpha(s))\mid s\ll t\\}$ $\displaystyle=\\{\beta(\Delta
h(s))\mid s\ll t\\}=\\{\beta(u)\mid u\ll\Delta h(t)\\},$

and this is a $\Delta$-set in $B$. Moreover,

$\displaystyle h(\alpha(t))$ $\displaystyle=\beta(\Delta
h(t))=\bigvee\\{\beta(u)\mid u\ll\Delta h(t)\\}=\bigvee\\{h(\alpha(s))\mid
s\ll t\\}.$

If $\Delta=\mathsf{T}$, then a $\Delta$-algebra is just an ordered algebra. If
$\Delta X$ is the collection of all regular trees over $X$, then a
$\Delta$-algebra is an ordered regular algebra [10, 11]. If $\Delta X$ is the
set of all regular trees of order $n$, $n\geq 0$, then a $\Delta$-algebra is
an $n$-regular (or $n$-rational) algebra of [6].

We have defined $\Delta$-algebras $A$ in terms of suprema of $\Delta$-sets in
$A$. However, one could generalize the notion of $\Delta$-set to include any
set of terms with a supremum in $\Delta A$.

Suppose that $(A,\alpha)$ is a $\Delta$-algebra. A subset
$E\mathrel{\subseteq}\Delta A$ is said to be _consistent_ if any two elements
of $E$, considered as labeled trees, agree wherever both are defined. That is,
if $t_{1},t_{2}\in E$, and $t_{1}$ and $t_{2}$ both have a node at position
$x$ in the tree, then the element of $\Sigma$ labeling $t_{1}$ at $x$ is the
same as the element of $\Sigma$ labeling $t_{2}$ at $x$. Any consistent set of
terms has a unique supremum.

We say that a set $D\mathrel{\subseteq}A$ is an _extended $\Delta$-set_ if
there is a consistent set $E\mathrel{\subseteq}\Delta A$ such that $\bigvee
E\in\Delta A$ and $D=\\{\alpha(t)\mid t\in E\\}$.

We state the following theorem without proof, but it is not difficult to prove
using the same technique as in Theorems 2 and 3.

######  Theorem 4.

The algebraic operations of any $\Delta$-algebra and all $\Delta$-algebra
morphisms preserve suprema of extended $\Delta$-sets.

As every $\Delta$-set is an extended $\Delta$-set, we can replace the
definition of $\Delta$-regular algebra by the stronger property that suprema
of all extended $\Delta$-sets exist and are preserved by the algebraic
operations.

##  4\. Main Result

We can introduce varieties of $\Delta$-algebras defined by a set of
inequalities between finite partial terms in $\mathsf{T}X_{\omega}$ in the
expected way.

Suppose that ${\mathcal{V}}_{\omega}$ is a variety of $\omega$-continuous
algebras defined by a set of inequalities between finite partial terms. Let
${\mathcal{V}}_{r}$ denote the variety of all $\Delta$-algebras defined by the
same set of inequalities. Let $F_{r}(X)$ denote the free ordered algebra on
generators $X$ in ${\mathcal{V}}_{r}$. Let $F_{\omega}(X)$ denote the free
$\omega$-continuous algebra on generators $X$ in ${\mathcal{V}}_{\omega}$ (see
[8]). Let $R(X)$ denote the ordered $\Delta$-subalgebra of $F_{\omega}(X)$
generated by $X$. The elements of $R(X)$ are all elements of $F_{\omega}(X)$
denoted by the terms in $\Delta X$:

$\displaystyle R(X)$ $\displaystyle=\\{t^{F_{\omega}(X)}\mid t\in\Delta X\\}.$

######  Theorem 5.

$R(X)$ is the free $\Delta$-algebra in ${\mathcal{V}}_{r}$ on generators $X$.
It is isomorphic to the completion of $F_{r}(X)$ by $\Delta$-ideals. (A
_$\Delta$ -ideal_ is simply the down-closure ${B}\kern-2.0pt\downarrow$ of a
$\Delta$-set $B$.)

######  Proof 4.1.

Since $R(X)$ embeds in $F_{\omega}(X)$, we have that
$R(X)\in{\mathcal{V}}_{r}$ by Birkhoff’s theorem.

Suppose that $A$ is an ordered $\Delta$-regular algebra and $h:X\to A$.
Consider the completion $I_{\omega}(A)$ of $A$ by $\omega$-ideals, which is an
$\omega$-continuous algebra in ${\mathcal{V}}_{\omega}$ [3, 8]. The function
$\eta^{D}_{A}:a\mapsto{\\{a\\}}\kern-2.0pt\downarrow$ embeds $A$ in
$I_{\omega}(A)$, so we can view $h$ as a function $X\to I_{\omega}(A)$. Since
$I_{\omega}(A)\in{\mathcal{V}}_{\omega}$, there is a unique extension of $h$
to a morphism $\widehat{h}:F_{\omega}(X)\to I_{\omega}(A)$ of
$\omega$-continuous algebras. The restriction of $\widehat{h}$ to $R(X)$ is an
ordered $\Delta$-regular algebra morphism $R(X)\to I_{\omega}(A)$. Let $R(A)$
denote the image of $R(X)$ under $\widehat{h}$. Then $R(A)$ is a
$\Delta$-regular subalgebra of $I_{\omega}(A)$ generated by $A$, and $R(A)$ is
in ${\mathcal{V}}_{r}$ because it is a homomorphic image of $R(X)$, which is
in ${\mathcal{V}}_{r}$.

Finally, let $\bigvee$ be the supremum operator on $R(A)$. The elements of
$R(A)$ are $\omega$-ideals generated by $\Delta$-sets, therefore the suprema
exist. The map $\bigvee$, being a component of the counit of the completion
construction, is a morphism of $\Delta$-algebras; that is, a strict monotone
function that preserves suprema of $\Delta$-sets and commutes with the
algebraic operations.

Now the restriction of $\widehat{h}$ composed with $\bigvee$ is the required
unique extension of $h$ to a morphism $R(X)\to A$ of $\Delta$-algebras.

We can also construct $R(X)$ directly as the free completion of $F_{r}(X)$ by
$\Delta$-ideals. Here we use the general construction of §2. Let
$F=\mathsf{T}$, the finite term monad for the signature $\Sigma$ and $D$ the
monad of $\Delta$-ideals. The algebra $F_{r}(X)$ is an $F$-algebra. We must
check that the monad $D$ satisfies the condition (4); but this is almost
automatic, as $D$ is a submonad of the monad of Example 2.

The free completion is
$(D(F_{r}(X)),D\alpha\circ\lambda_{F_{r}(X)},\mu^{D}_{F_{r}(X)})$, where
$\alpha$ is the structure map of $F_{r}(X)$. It is the free $\Delta$-algebra
on generators $X$. As $R(X)$ is also a $\Delta$-algebra, there is unique
$\Delta$-algebra morphism $g$ from $D(F_{r}(X))$ to $R(X)$ mapping $x\in X$ to
$x$. Since both algebras are generated by $X$, $g$ is surjective. Similarly,
since $D(F_{r}(X))$ is a $\Delta$-algebra, as noted above, there is a
$\Delta$-algebra morphism $h$ from $R(X)$ to $D(F_{r}(X))$ mapping $x\in X$ to
$x$. The composition $h\circ g$ is the unique morphism on $D(F_{r}(X))$
extending the identity on $X$, thus must be the identity morphism. Thus $R(X)$
and $D(F_{r}(X))$ are isomorphic.

The free $\omega$-continuous semiring on generators $X$ is the semiring of
power series ${\mathbb{N}}_{\infty}\llangle X^{*}\rrangle$ with a countable
support having coefficients in ${\mathbb{N}}_{\infty}$ obtained from the
semiring of natural numbers by adding a point at infinity. It follows that the
free regular semiring over $X$ is the semiring ${\mathbb{N}}_{\infty}^{\rm
alg}\llangle X^{*}\rrangle$ of all algebraic elements of
${\mathbb{N}}_{\infty}\llangle X^{*}\rrangle$.

The free $\omega$-continuous idempotent semiring on $X$ is the semiring of all
at most countably infinite languages in $X^{*}$. The $\omega$-continuous
idempotent semirings are the same as the closed semirings used in the study of
shortest-path algorithms [2] (modulo minor corrections to the axiomatization).
The free “1-regular” idempotent semiring over $X$ is the semiring of OI-macro
languages over $X$.

The free star-continuous Kleene algebra on generators $X$ is the family of
regular subsets of $X^{*}$ [9]. This is the free $\Delta$-algebra for $\Delta$
the set of regular coterms defined by finite systems of linear affine
equations in the variety of idempotent semirings. The family of context-free
languages is the free $\Delta$-algebra for $\Delta$ the set of regular coterms
defined by finite systems of algebraic equations in the variety of idempotent
semirings. The free $\omega$-continuous idempotent semiring is the completion
of the free Kleene algebra by countably generated star-ideals [9].

A final example is given by the category of iteration theories [4], which is
isomorphic to the category of Eilenberg-Moore algebras for the rational-tree
monad on the category of signatures [1].

## References

  * [1] J. Adámek, S. Milius, and J. Velebil.  What are iteration theories?  In L. Kučera and A. Kučera, editors, Mathematical Foundations of Computer Science (MFCS 2007), pages 240–252, Berlin, Heidelberg, August 2007. Springer.
  * [2] A. V. Aho, J. E. Hopcroft, and J. D. Ullman.  The Design and Analysis of Computer Algorithms.  Addison Wesley, 1975.
  * [3] S. L. Bloom.  Varieties of ordered algebras.  J. Comp. Syst. Sci., 13:200–212, 1976.
  * [4] S. L. Bloom and Z. Ésik.  Iteration Theories.  Springer, 1993.
  * [5] B. Courcelle.  Fundamental properties of infinite trees.  Theor. Comput. Sci., 25:95–169, 1983.
  * [6] J. H. Gallier.  The semantics of recursive programs with function parameters of finite types: $n$-rational algebras and logic of inequalities.
  * [7] J. A. Goguen, J. W. Thatcher, E. G. Wagner, and J. B. Wright.  Initial algebra semantics and continuous algebras.  J. ACM, 24:68–95, 1977.
  * [8] I. Guessarian.  Algebraic semantics.  LNCS, 99, 1981.
  * [9] D. Kozen.  On Kleene algebras and closed semirings.  In Rovan, editor, Proc. Mathematical Foundations of Computer Science (MFCS 1990), volume 452 of Lecture Notes in Computer Science, pages 26–47, Banska-Bystrica, Slovakia, 1990. Springer-Verlag.
  * [10] J. Tiuryn.  Fixed points and algebras with infinitely long expressions I.  Fundamenta Informaticae, 2:103–128, 1978.
  * [11] J. Tiuryn.  Fixed points and algebras with infinitely long expressions II.  Fundamenta Informaticae, 2:317–335, 1979.


# SEEK: model extraction attack against hybrid secure inference protocols

Si Chen<EMAIL_ADDRESS>Junfeng Fan<EMAIL_ADDRESS>
###### Abstract

Security concerns about a machine learning model used in a prediction-as-a-
service include the privacy of the model, the query and the result. Secure
inference solutions based on homomorphic encryption (HE) and/or multiparty
computation (MPC) have been developed to protect all the sensitive
information. One of the most efficient type of solution utilizes HE for linear
layers, and MPC for non-linear layers. However, for such hybrid protocols with
semi-honest security, an adversary can malleate the intermediate features in
the inference process, and extract model information more effectively than
methods against inference service in plaintext. In this paper, we propose
SEEK, a general extraction method for hybrid secure inference services
outputing only class labels. This method can extract each layer of the target
model independently, and is not affected by the depth of the model. For
ResNet-18, SEEK can extract a parameter with less than 50 queries on average,
with average error less than $0.03\%$.

##  1 Introduction

For a machine learning model used in a prediction-as-a-service (PaaS) setting,
the model provider usually is concerned about the privacy of the deployed
model. Revealing the model information will enable a user to develop his own
model. In addition, the model information can be reverse-engineered to reveal
its training data [1, 2], or enable an attacker to fabricate adversarial
samples [3]. On the other hand, users of PaaS may have privacy concerns about
the input data, and do not want to upload the input in plaintext to a service
hosted by the model provider. Thus neither the server side nor the client side
is a satisfactory place to perform the model inference computation.

To solve this dilemma, secure inference protocols are proposed, which enables
the client to query a model deployed in a remote server, while preventing the
client and server to learn any additional information. Secure inference
solutions are based on homomorphic encryption (HE), multiparty computation
(MPC), or both families of techniques. Solutions based on homomorphic
encryption suffer from limitation of the practical FHE schemes. The levelled,
and relatively efficient FHE schemes, including BFV, BGV, and CKKS, support
fixed number of multiplications without bootstrapping. By replacing the
activation functions with polynomial functions, the levelled FHE schemes can
compute both the linear layers and non-linear layers, but cannot support
multiplication depth needed by a deep neural network with more than 3 or 4
layers [4, 5]. On the other hand, the most efficient secure inference protocol
based on MPC either use garbled circuit and generally incur higher
communication cost [6, 7, 8], or require three non-colluding parties [9, 10,
11], which is an additional requirement not readily satisfied in practice.

To perform secure inference for deep neural networks, while utilizing the
efficiency of levelled FHE schemes, hybrid solutions based on FHE and MPC
emerged [12, 13, 14, 15, 16]. The linear part of a neural network, which
contains the majority of computation cost, is processed by a FHE scheme, while
the non-linear part is process by a MPC scheme. Between linear layers and non-
linear layers, a pair of protocols are performed to transfer the internal
features between encrypted form and secret-shared form.

However, these hybrid secure inference solutions assume semi-honest
participants. Such assumption is not guaranteed in real scenarios. We observe
that by considering malicious behavior, the client can secretly shift the
internal features during inference, and observe its effect on the final output
of the model. With this additional opportunity of changing the intermediate
data, in this paper we propose a general model extraction method called SEEK
(Safe-Error Extraction attacK), with which the client can extract the model
parameters, more effectively than the extraction attack on models without
secure inference.

##  2 Related Works

A model extraction attack method attepmts to retrieve information about a
remotely-deployed model, and consequently copy the model parameters, mimic the
model’s functionality, or infer information about its training data. For a
classification model, the target inference service may return class labels,
top-$k$ probabilities, logits (or equivalently, all class probabilities), or
even some intermediate features and/or gradients, among which class labels
contain minimal information, leading to the most secure setup.

Most existing model extraction attacks [17, 18, 19, 20] target traditional
model inference service in plaintext, while [21] and this work target
encrypted model inference service. Extraction methods also differ in their
objectives. We follow the taxonomy made in [19], which categorized the
extraction objectives into the following types:

  * •

Exact Extraction: extract all parameters of the target model. This objective
is not possible for plaintext inference service, due the model’s inherent
symmetries. We will show it can be efficiently achieved for encrypted model
inference service.

  * •

Functionally Equivalent Extraction: construct a model such that its output is
identical with that of the target model. The extracted model has the same
structure as the target model, and the same paramters up to a symmetry
transformation. This is the highest possible objective against a plaintext
inference service.

  * •

Fidelity Extraction: For some input data distribution $\mathcal{D}$ and some
goal similarity function $S(\cdot,\cdot)$, Fidelity Extraction aims to
construct a model $\hat{O}$, such that
$\textrm{Pr}_{x\sim\mathcal{D}}[S(\hat{O}(x),O(x))]$ is maximized. Typically,
Fidelity Extraction only guarantee the outputs from the constructed model and
the target model are similar enough on some test dataset.

  * •

Task Accuracy Extraction: construct a model to match or exceed the accuracy of
the target model.

Learning-based methods access the target model to generate a training dataset,
with which a substitute model is trained. Typically, learning-based methods do
not attempt to extract individual parameters, resulting in Fidelity Extraction
as the objective, and is generally query-efficient. In [18], in order to find
the decision boundaries between classes efficiently, an iterative training
algorithm is proposed, which uses the substitute model to create samples close
to decision boundaries. In [19], the authors leveraged several recent
optimizations in training, including unlabelled training, distillation,
rotation loss, and MixMatch, to be able to train a substitute model with much
fewer queries than the size of the original training set.

Direct recovery methods, which aims Functionally Equivalent Extraction, treat
the target model as a function explicitly expressed by the parameters, and
attempt to solve for the parameters given model query inputs and outputs. In
[19], for neural networks which use ReLU activation and return logits, an
extraction algorithm is devised by solving the parameters in the model, which
is a piecewise-linear function. In [20], the authors utilized methodologies
from cryptoanalysis, and carefully improved the differential extraction method
in [19], by treating more efficiently the issues arising from larger depths
and numerical errors.

In [21], the target inference service is performed with the hybrid MPC-HE
scheme, and is assumed to return logits. The extraction method shifts the
features so that the inference becomes a linear system, whose paramters can be
solved with enough query inputs and outputs.

Features of the related works are summarized in table 1. In comparison, the
proposed method SEEK considers the most restrictive setup in which only class
labels are returned. Additionally, by utilizing the “safe-error attack” method
[22, 23], SEEK does not suffer from the numerical error induced by very deep
networks, and can apply to models with arbitrary number of layers.

Method | Extraction method | Extraction target |  | Model
---
output
| Highest
---
model depth
| # model calls
---
per parameter
Tramèr et al. [17] | Learning | Functional Equivalence | logits | 2 | $0.5\sim 5$
Tramèr et al. [17] | Direct Recovery | Functional Equivalence | labels | 1 | $20\sim 50$
Tramèr et al. [17] | Learning | Fidelity | labels | 3 | $\sim 100$
Papernot et al. [18] | Learning | Fidelity | labels | unlimited | $<1$
Jagielski et al. [19] | Learning | Fidelity | labels | unlimited | $\ll 1$
Jagielski et al. [19] | Direct Recovery | Functional Equivalence | logits | 2 | $\sim 10$
Carlini et al. [20] | Direct Recovery | Functional Equivalence | logits | 4 | $\sim 200$
MUSE [21] | MPC Malleation | Exact Extraction | logits | 10 | $1/n_{c}$
SEEK | MPC Malleation | Exact Extraction | labels | unlimited | $\sim 50$
Table 1: Feature of the extraction methods against neural network and logistic
regression models.

It is well-known that the MPC protocol malleation attacks as in [21] and this
work can be mitigated by using a protocol with malicious security. Recently, a
line of work with client-malicious model are proposed [21, 24, 25]. These
protocols are designed based on authenticated shares, and are closing the gap
of computational and communicational efficiency with respect to the protocols
with semi-honest security.

##  3 Secure inference setup

We consider a general deep convolutional neural network (CNN), trained for a
classification task. Layers in CNN can be categorized into linear layers and
non-linear layers. Linear layers include convolution layers, fully-connected
(FC) layers, as well as normalization layers, average-pooling layers. Addition
and concatenation layers can be viewed as linear layers as well. Consecutive
linear layers can be merged together to form a single linear layer. A linear
layer indexed with $\ell$ in general can be expressed as

$y_{\ell}=w_{\ell}\cdot x_{\ell}+b_{\ell},$ (1)

where $x_{\ell}$ is the input feature map, $y_{\ell}$ is the output feature
map, $w_{\ell}$ is the weight parameter, and $b_{\ell}$ is the bias parameter.
In this formalism, for a convolution layer, the weight parameters are sparse
due to localized kernel, and the values are shared across spatial locations.

Non-linear layers include activation layers, which perform some element-wise
nonlinear function, as well as max-pooling, softmax, and argmax layers. In
this paper, for activation layers, we use the most common ReLU activation. For
our purpose, two adjacent non-linear layers will be viewed as a single non-
linear layer. Typically for a CNN, a non-linear layer indexed with $\ell$ is
composed of an activation layer

$z_{\ell}=\textrm{ReLU}(y_{\ell}),$ (2)

or composed of a max-pooling layer followed by an activation layer,

$z_{\ell}=\textrm{ReLU}(\textrm{maxpool}(y_{\ell})),$ (3)

or, for the last layer, composed of an argmax layer,

$z_{\ell}=\textrm{argmax}(y_{\ell}),$ (4)

where $y_{\ell}$ is the input feature map, and $z_{\ell}$ is the output
feature map. We do not restrict the network structure to be linear, and
structures such as skip connection and Inception are allowed.

With hybrid secure inference solutions, the client encrypts its input $x_{0}$
into $[\\![{x_{0}}]\\!]$, and sends $[\\![{x_{0}}]\\!]$ to the server. For
each linear layer as in equation (1), the server computes

$[\\![{y_{\ell}}]\\!]=w_{\ell}\cdot[\\![{x_{\ell}}]\\!]+b_{\ell}.$

To perform a non-linear layer as in equation (2), (3), and (4), the server
generates a random mask $r^{y}_{\ell}$, computes
$[\\![{y_{\ell}}]\\!]-r^{y}_{\ell}=[\\![{y_{\ell}-r^{y}_{\ell}}]\\!]$, and
send this encrypted value to the client. The client decrypts to get
$y_{\ell}-r^{y}_{\ell}$. Now the two parties hold secret shares of the
intermediate value $y_{\ell}$. The server and the client invoke a two-party
MPC protocol corresponding to the non-linear layer. As the result, the client
holds $z_{\ell}-r^{z}_{\ell}$, and the server holds $r^{z}_{\ell}$. To
transform $z_{\ell}$ back to encrypted form, the client encrypts
$z_{\ell}-r^{z}_{\ell}$ and sends $[\\![{z_{\ell}-r^{z}_{\ell}}]\\!]$ to the
server, who can compute $[\\![{z_{\ell}}]\\!]$ and proceed to the next layer.
After all layers are processed, the client and the server run another MPC
protocol to compute equation (4), and the client reconstructs the shares to
get $c$.

Security of the hybrid protocol guarantees the privacy of input data,
intermediate features, final result, as well as the model parameters, if the
two parties follow the semi-honest model. However, we observe that the client
can add arbitrary shifts to the secret shares in this protocol, and semantic
security of the protocol ensures the server cannot detect the shift. Instead
of using $y_{\ell}-r^{y}_{\ell}$ as input of the MPC calculation, the client
can change it to $y_{\ell}-r^{y}_{\ell}+\delta y_{\ell}$, effectively changing
the underlying value from $y_{\ell}$ to $y_{\ell}+\delta y_{\ell}$. Similarly,
the client can change $z_{\ell}-r^{z}_{\ell}$ to $z_{\ell}-r^{z}_{\ell}+\delta
z_{\ell}$, effectively changing the underlying value from $z_{\ell}$ to
$z_{\ell}+\delta z_{\ell}$.

Thus the client is capable of shifting all inputs and outputs of the non-
linear layers by arbitrary values, although the client is ignorant of the
values of the features. We consider how the client can exploit these
additional inputs, to efficiently extract the model parameters. From the
viewpoint of a malicious client, the model service can be formulated as

$\displaystyle c$ $\displaystyle=C_{\\{w\\}}(x_{0},\\{\delta y_{\ell},\delta
z_{\ell}:\ell\in N\\})$
$\displaystyle=\textrm{argmax}(F_{\\{w\\}}(x_{0},\\{\delta y_{\ell},\delta
z_{\ell}:\ell\in N\\})),$

where $\\{w\\}$ denotes all model parameters, $C$ is the functionality of the
classification model, which outputs the predicted class index, $N$ is the set
of non-linear layers, and $F$ is the output of the last linear layer.

To ease the notation, we use “named arguments” to denote the set of inputs as
$(x_{0},\\{\delta y_{\ell},\delta z_{\ell}:\ell\in
N\\})=V(\widetilde{x_{0}}=x_{0},\ldots,\widetilde{\delta y_{\ell}}=\delta
y_{\ell},\ldots,\widetilde{\delta z_{\ell^{\prime}}}=\delta
z_{\ell^{\prime}},\ldots)$. If an input is not present in the list of
arguments of $v$, it means the input is set to zeros. For example,
$V(\widetilde{\delta y_{\ell}}=\delta
y_{\ell})=V(\widetilde{x_{0}}=0,\widetilde{\delta y_{\ell}}=\delta
y_{\ell},\widetilde{\delta y_{\ell^{\prime}}}=0,\widetilde{\delta
z_{\ell^{\prime\prime}}}=0)$, for all $\ell^{\prime}\neq\ell$ and all
$\ell^{\prime\prime}$. Two sets of inputs can be added with the natural
element-wise addition.

Because the output of the model is a discrete value, in order to extract model
parameters, the adversary needs to find the boundary between classes, where
for

$y_{\ell_{\textrm{last}}}=F_{\\{w\\}}(v),$

it satisfies

$y_{\ell_{\textrm{last}},c_{1}}=y_{\ell_{\textrm{last}},c_{2}}$ (5)

for two different classes $c_{1},c_{2}$, and

$y_{\ell_{\textrm{last}},c_{1}}>y_{\ell_{\textrm{last}},c^{\prime}}$ (6)

for all other $c^{\prime}$. In the following, we call a set of input
satisfying the above relations a critical point, and denote the corresponding
input variables with a $*$ subscript.

Starting from a set of inputs and changing feature values on a layer, a
critical point can always be found. Algorithm 1 shows a routine for finding a
critical point using bisection, in which all input variables are fixed except
$\delta y_{\ell}$.

##  4 Extraction of intermediate features

In this section, we present the concrete method of SEEK. The adversary is able
to shift all the inputs and outputs of the activation layers, and observe the
effect on the model output. One way to extract the parameters is to find the
space of critical points formed by shifting the intermediate features.
However, because the landscape of model output as a function of the shifts can
be very complicated, this method becomes intractable when the target layer is
far away from the output layer. Instead, starting from a critical point, the
proposed method will add a particular set of shifts, such that if the
corresponding feature satisfies certain condition, the added shifts would
cancel itself and do not affect any other features. We can test the
criticality of the shifted input, and determine the value of the target
feature. In this way, we keep the effect of the shifts to a minimal level,
making this extraction method numerically stable and the errors in the
extracted parameters independent of each other. This extraction strategy is in
concept similar with the safe-error attack [22, 23] as a type of fault
injection attack to security systems.

Input : A fixed set of inputs $v^{0}$, variable input layer index $\ell$, norm
$d$, and error threshold $\epsilon$

Output : $\delta y^{*}_{\ell}$

1 do

2 Randomly sample $\delta y^{1}_{\ell}$ and $\delta y^{2}_{\ell}$ with norm
$d$;

3 $c^{1}\leftarrow C\left(v^{0}+V(\widetilde{\delta y_{\ell}}=\delta
y^{1}_{\ell})\right)$, $c^{2}\leftarrow C\left(v^{0}+V(\widetilde{\delta
y_{\ell}}=\delta y^{2}_{\ell})\right)$;

4

5while  _$c^{1}=c^{2}$_ ;

6while  _$|\delta y^{2}_{\ell}-\delta y^{1}_{\ell}| >\epsilon$_ do

7 $\delta y^{3}_{\ell}\leftarrow(\delta y^{1}_{\ell}+\delta y^{2}_{\ell})/2$,
and normalize $\delta y^{3}_{\ell}$ with norm $d$;

8 $c^{3}\leftarrow C\left(v^{0}+V(\widetilde{\delta y_{\ell}}=\delta
y^{3}_{\ell})\right)$;

9 if  _$c^{3}=c^{1}$_ then

10 $\delta y^{1}_{\ell}\leftarrow\delta y^{3}_{\ell}$;

11

12 else

13 $\delta y^{2}_{\ell}\leftarrow\delta y^{3}_{\ell}$, $c^{2}\leftarrow
c^{3}$;

14

15 end if

16

17 end while

_18_ return _$\delta y^{*}_{\ell}\leftarrow\delta y^{2}_{\ell}$ ;_

Algorithm 1 search_critical – Find a critical point by shifting $y_{\ell}$
from a given set of inputs.

###  4.1 Extraction of standalone ReLU layer inputs

In this subsection, we present the method to extract an input feature value of
a standalone ReLU activation as in equation (2).

Consider a critical point $v^{*}$. A target feature $y_{\ell,i}$, which is the
input of a standalone ReLU activation, takes the value $y^{*}_{\ell,i}$ from
the set of input $v^{*}$. If $y^{*}_{\ell,i}<0$, shifting it by a small
positive or any negative $\delta y_{\ell,i}$ will not affect the model output,
because $\textrm{ReLU}(y^{*}_{\ell,i}+\delta
y_{\ell,i})=\textrm{ReLU}(y^{*}_{\ell,i})=0$. In this case we add a positive
shift to $y_{\ell,i}$. If $\delta y_{\ell,i}$ is large enough such that
$y^{*}_{\ell,i}+\delta y_{\ell,i}>0$, which implies
$\textrm{ReLU}(y^{*}_{\ell,i}+\delta
y_{\ell,i})\neq\textrm{ReLU}(y^{*}_{\ell,i})$, the input is no longer a
critical point. We can test the criticality of the input while varying $\delta
y_{\ell,i}$. At the boundary between critical points and non-critical points,
$y^{*}_{\ell,i}=-\delta y_{\ell,i}$.

On the other hand, if $y^{*}_{\ell,i}>0$, subtracting a small positive or any
negative $\delta y_{\ell,i}$ from $y_{\ell,i}$, and at the same time adding
the same shift $\delta y_{\ell,i}$ to $z_{\ell,i}$, will not affect the model
output, because $\textrm{ReLU}(y^{*}_{\ell,i}-\delta y_{\ell,i})+\delta
y_{\ell,i}=\textrm{ReLU}(y^{*}_{\ell,i})=y^{*}_{\ell,i}$. If $\delta
y_{\ell,i}$ is large enough such that $y^{*}_{\ell,i}-\delta y_{\ell,i}<0$,
the input is no longer a critical point. We can test the criticality of the
input while varying $\delta y_{\ell,i}$. At the boundary between critical
points and non-critical points, $y^{*}_{\ell,i}=\delta y_{\ell,i}$.

To test the criticality of a set of inputs $v$, we use the properties equation
(5) and (6). Consider we start from a critical point $v^{*}$ at the boundary
between class $c_{1}$ and $c_{2}$, and add some shifts $\delta v$ to
$y_{\ell}^{*}$ and $z_{\ell}^{*}$. If the added shifts do not change any
feature values other than $y_{\ell}$ and $z_{\ell}$, then the set of inputs
$v=v^{*}+\delta v$ is also a critical point between class $c_{1}$ and $c_{2}$.
In this case, $v$ satisfy

$C\left(v+V(\widetilde{\delta
y_{\textrm{last},c_{1}}}=\epsilon)\right)=c_{1},$

and

$C\left(v+V(\widetilde{\delta
y_{\textrm{last},c_{2}}}=\epsilon)\right)=c_{2},$

where $\epsilon$ is a small positive value. If the added shifts affect other
feature values, then the above equations are not satisfied with overwhelming
probability.

The algorithm for extracting a input feature of a standalone ReLU is shown in
algorithm 2.

Input : Input critical point $v^{*}$, target activation layer index $\ell$,
and target feature index $i$

Output : $y^{*}_{\ell,i}$

1 if  _$v=v^{*}+V(\widetilde{\delta y_{\ell,i}}=-1)$ is critical_ then

// $y^{*}_{\ell,i}\leq 0$

2 For points of the form $v=v^{*}+V(\widetilde{\delta y_{\ell,i}}=\eta)$,
where $\eta\in[0,\infty)$, search for the boundary $\eta=\bar{\eta}$ between
critical points and non-critical points;

3 return _$y^{*}_{\ell,i}\leftarrow-\bar{\eta}$_ ;

4

5else

// $y^{*}_{\ell,i}>0$

6 For points of the form $v=v^{*}+V(\widetilde{\delta
y_{\ell,i}}=-\eta,\widetilde{\delta z_{\ell,i}}=\eta)$, where
$\eta\in[0,\infty)$, search for the boundary $\eta=\bar{\eta}$ between
critical points and non-critical points;

7 return _$y^{*}_{\ell,i}\leftarrow\bar{\eta}$_ ;

8

9 end if

Algorithm 2 extract_feature – Extraction of an intermediate feature value at a
critical point

###  4.2 Extraction of maxpool-ReLU layer inputs

In this subsection, we present the method to extract an input feature value of
a maxpool layer followed by a ReLU layer, as in equation (3).

The method is similar with the one in previous subsection. Because the maxpool
layer maps multiple features into one feature, when adjusting one input
feature and one output feature, we need to find a way to suppress the effect
of the other related input features.

Assume the feature value to be extracted is $y_{\ell,i}$, and the set of
output features affected by shifting $y_{\ell,i}$ is $Z_{\ell,i}$. We can add
a large negative shift to all features in $y_{\ell}$, except $y_{\ell,i}$. As
a result, $z_{\ell}$ will be zero everywhere except features in $Z_{\ell,i}$,
which takes the value of $y_{\ell,i}$. Now we can shift the value of
$y_{\ell,i}$ and values in $Z_{\ell,i}$, observe the effect on the
criticality, and consequently extract $y_{\ell,i}$. The extraction process is
similar with algorithm 2, except now the feature $z_{\ell,i}$ is replaced by a
set of features which should be shifted together. See figure 1 for an
illustration of this method.

Figure 1: An example of extraction method for a maxpool-ReLU layer input
feature. Features in the orange boxes are the target feature $y_{\ell,i}$ and
its related features $Z_{\ell,i}$ in the post-target layer, respectively. The
dashed rectangles are ranges of maxpool kernels. $C$ is a large positive
constant, added in order to suppress the effect from other features on
$y_{\ell}$ to $Z_{\ell,i}$.

###  4.3 Extraction of linear layer parameters

The methods presented in the previous two subsections can extract all the
intermediate features of a critical point. Then for each linear layer as in
equation (1), with the input features and output features known, the formula
is a set of linear equations for $w_{\ell}$ and $b_{\ell}$. We can repeat this
process and collect enough equations to solve all the model parameters.

To further simplify the extraction process, we note that we can add a large
negative shift to the input of a ReLU activation, and ensure its output to be
zero. We can also add arbitrary shifts to the zeroed outputs. Thus we have a
means to accurately control the output values of ReLU activations. In equation
(1), by setting $x_{\ell}$ to be identically zero and extracting $y_{\ell}$,
the value of $b_{\ell}$ can be read off,

$b_{\ell,j}=y_{\ell,j},$

where $j$ is an output feature index. By setting all but one feature value of
$x_{\ell}$ zero and extracting $y_{\ell}$, the weight parameters can be
derived as,

$w_{\ell,j,i_{0}}=\frac{y_{\ell,j}-b_{\ell,j}}{x_{\ell,i_{0}}},$

where $i_{0}$ is index of non-zero $x_{\ell}$ value.

We observe that algorithm 2 can work on multiple target feature indices, if
all the target features at these indices have the same value. In practice,
running algorithm 2 on more indices improves the accuracy, because the
influence of a change of their value is more significant to the model output.
For convolutional layers, we can use its structure to create multiple target
features with the same value. For the bias, by setting $x_{\ell}$ to be
identically zero, all values on $y_{\ell,c_{\textrm{out}}}$ are equal to
$b_{\ell,c_{\textrm{out}}}$, where $c_{\textrm{out}}$ is an output channle
index. For the weight, instead of setting one feature value on $x_{\ell}$
nonzero, for an input channel index $c_{\textrm{in}}$, we can set
$x_{\ell,c_{\textrm{in}}}$ to be periodically nonzero, so that the target
kernel value is repeated on $y_{\ell}$.

The above extraction process is illustrated in figure 2. Algorithm 3 shows the
complete algorithm to extract the parameters in a convolution layer. For
clarity, we assume that the stride of the convolution to be 1. The extraction
algorithm for a fully-connected layer is similar, and is omitted for brevity.

###  4.4 Extraction of last linear layer parameters

The extraction method described in the previous subsection applies to all the
linear layers, except the last fully-connected layer before the argmax layer.
Without a ReLU layer after the last fully-connected layer, the features
$y_{\textrm{last}}$ cannot be extracted with the extract_feature routine.
Instead, the following method can be applied. Assume the numbers of input and
output features of the last fully-connected layer are $n_{0}$ and $n_{1}$,
respectively. To extract $b_{\textrm{last}}$, we can add shifts to the layer
before the last layer, so that $x_{\textrm{last}}=0$. Then we search for
critical points by varying $\delta y_{\textrm{last}}$, which gives the
relation about $b_{\textrm{last}}$,

$b_{\textrm{last},c_{1}}+\delta
y^{*}_{\textrm{last},c_{1}}=b_{\textrm{last},c_{2}}+\delta
y^{*}_{\textrm{last},c_{2}}.$

$n_{1}-1$ such equations give the values of $b_{\textrm{last}}$ up to an
additive constant. Similarly for $w_{\textrm{last}}$, we can manipulate the
layer before the last layer, so that $x_{\textrm{last}}$ is zero except at
feature $i_{0}$. Then we search for critical points by varying $\delta
y_{\textrm{last}}$, which gives the relation about $w_{\textrm{last}}$,

$\displaystyle
w_{\textrm{last},c_{1},i_{0}}x_{\textrm{last},i_{0}}+b_{\textrm{last},c_{1}}+\delta
y^{*}_{\textrm{last},c_{1}}$
$\displaystyle=w_{\textrm{last},c_{2},i_{0}}x_{\textrm{last},i_{0}}+b_{\textrm{last},c_{2}}+\delta
y^{*}_{\textrm{last},c_{2}},$ $\displaystyle
w_{\textrm{last},c_{1},i_{0}}-w_{\textrm{last},c_{2},i_{0}}$
$\displaystyle=\frac{(b_{\textrm{last},c_{2}}-b_{\textrm{last},c_{1}})+\delta
y^{*}_{\textrm{last},c_{2}}-\delta
y^{*}_{\textrm{last},c_{1}}}{x_{\textrm{last},i_{0}}}.$

$(n_{1}-1)n_{0}$ such equations gives the values of $w_{\textrm{last}}$, up to
$n_{0}$ additive constants. In fact, because only the class label is observed,
this is all the degrees of freedom of $w_{\textrm{last}}$ that can be
determined.

Figure 2: An example of the convolutin layer extraction method, as shown in
algorithm 3. For simplicity, only one channel for each layer is shown. By
setting the pre-target feature $x_{\ell}$ to be nonzero with a period of
kernel size, the target feature layer $y_{\ell}$ is also periodic, and the
values in the orange boxes can be extracted together for better accuracy,
which reveal the values of target convolution layer parameters.

Input : Target convolution layer index $\ell$, numbers of output and input
channels $n_{\textrm{out}}$ and $n_{\textrm{in}}$, convolution kernal size
$(k_{h},k_{w})$, input feature size $(f_{h},f_{w})$

Output : Target convolution layer parameters $b_{\ell}$ and $w_{\ell}$

1 Get the layer index $\ell_{0}$ whose output is the input of layer $\ell$,
i.e., $z_{\ell_{0}}=x_{\ell}$;

2 Get the index of last non-linear layer $\ell_{\textrm{last}}$;

3 Add a large negative shift $-d$ to all features in $y_{\ell_{0}}$;

4 $\delta
z^{*}_{\ell_{\textrm{last}}}\leftarrow\textsf{search\\_critical}(V(\widetilde{x_{0}}=x_{0},\widetilde{\delta
y_{\ell_{0}}}=-d),\ell_{\textrm{last}})$;

5 $v^{*}\leftarrow V(\widetilde{x_{0}}=x_{0},\widetilde{\delta
y_{\ell_{0}}}=-d,\widetilde{\delta z_{\ell_{\textrm{last}}}}=\delta
z^{*}_{\ell_{\textrm{last}}})$;

6 for  _$c_{\textrm{out}}\leftarrow 0$ to $n_{\textrm{out}}-1$_ do

7 $\beta\leftarrow\\{(c_{\textrm{out}},i,j):0\leq i<f_{h},0\leq j<f_{w}\\}$;

8
$b_{\ell,c_{\textrm{out}}}\leftarrow\textsf{extract\\_feature}(v^{*},\ell,\beta)$;

9

10 end for

11$k_{h}^{\prime}\leftarrow(k_{h}-1)/2,k_{w}^{\prime}\leftarrow(k_{w}-1)/2$;

12 $\Delta\leftarrow(n_{\textrm{in}}\cdot k_{h}\cdot k_{w}/4)^{1/2}$;

13 for  _$c_{\textrm{in}}\leftarrow 0$ to $n_{\textrm{in}}-1$_ do

14 Create a feature map $\alpha$ of size $(f_{h},f_{w})$ whose values are
$\alpha_{i,j}=\Delta\cdot\hat{\delta}((i-k_{h}^{\prime})\%k_{h})\cdot\hat{\delta}((j-k_{w}^{\prime})\%k_{w}))$,
where $\hat{\delta}(\cdot)$ is the discrete delta function;

15 $\delta
z^{*}_{\ell_{\textrm{last}}}\leftarrow\textsf{search\\_critical}(V(\widetilde{x_{0}}=x_{0},\widetilde{\delta
y_{\ell_{0}}}=-d,\widetilde{\delta
x_{\ell,c_{\textrm{in}}}}=\alpha,\ell_{\textrm{last}})$;

16 $v^{*}\leftarrow V(\widetilde{x_{0}}=x_{0},\widetilde{\delta
y_{\ell_{0}}}=-d,\widetilde{\delta
x_{\ell,c_{\textrm{in}}}}=\alpha,\widetilde{\delta
z_{\ell_{\textrm{last}}}}=\delta z^{*}_{\ell_{\textrm{last}}})$;

17 for  _$c_{\textrm{out}}\leftarrow 0$ to $n_{\textrm{out}}-1$_ do

18 for  _$i\leftarrow 0$ to $k_{h}-1$_ do

19 for  _$j\leftarrow 0$ to $k_{w}-1$_ do

20 $\beta\leftarrow\\{(c_{\textrm{out}},i^{\prime},j^{\prime}):0\leq
i^{\prime}<f_{h},(i^{\prime}-k_{h}+1+i)\%k_{h}=0,0\leq
j^{\prime}<f_{w},(j^{\prime}-k_{w}+1+j)\%k_{w}=0\\}$;

21
$y_{\ell,c_{\textrm{out}},i,j}\leftarrow\textsf{extract\\_feature}(v^{*},\ell,\beta)$;

22
$w_{\ell,c_{\textrm{out}},c_{\textrm{in}},i,j}\leftarrow(y_{\ell,c_{\textrm{out}},i,j}-b_{\ell,c_{\textrm{out}}})/\Delta$;

23

24 end for

25

26 end for

27

28 end for

29

30 end for

31return _$b_{\ell}$ and $w_{\ell}$_;

Algorithm 3 Extraction of parameters in a convolution layer

##  5 Experiment

We test the proposed SEEK method on ResNet-18 [26], implemented in the latest
PyTorch [27] release. The model contains 11.7M parameters, and is trained for
ImageNet classification task.

In ResNet-18, some of the linear layers have a single preceding layer, while
the layers immediately after the addition layers have two preceding layers. In
addition, some skip connections are identity connections, and some are down-
sampling connections, which have their own convolution weights. In all of
these cases, we can use the methods in the previous section to extract the
linear layers’ parameters. Figure 3 shows several extraction paths for
different cases in ResNet.

Figure 3: Examples of extraction paths for ResNet. A large negative value is
added to the grey layers, so that the feature values in the pre-target layers
(yellow) can be adjusted to some convenient values. A bisection search is
performed on the last feature layers (blue) to find a critical point. The
feature values of the post-target layers (green) are extracted, based on
properties of the non-linear succeeding non-linear layers. Then the parameters
of the target layers (red) are extracted.

We implemented the extraction algorithm, and experimentally tested its
performance. Figure 4 shows the average number of model calls required for
extracting each parameter, as well as the average relative error, for
different layers in ResNet-18. For each parameter, the average number of model
calls is $45.8$. The average relative error of bias is $6.68\times 10^{-6}$,
and the average relative error of weight is $4.35\times 10^{-5}$.

Figure 4: Result of the proposed extraction method on ResNet-18.
$N_{\textrm{bias}}$($N_{\textrm{weight}}$) is the average number of model
calls for extracting a bias(weight) parameter.
$e_{\textrm{bias}}$($e_{\textrm{weight}}$) is the average relative error of
the extracted bias(weight) parameter.

As figure 4 shows, the average error of weight tends to be larger as the layer
is closer to the model output, except for the last FC layer. The reason for
this phenomenon is, if the shift of the target feature is larger than its
value (see algorithm 2), the output of ReLU function $z=z^{*}+\delta z$ will
be different from its original value $z^{*}$ and in turn changes the final
logits. However, for a layer closer to the model output, the relationship
between $\delta z$ and the final logits $y_{\textrm{last},c_{1}}$ and
$y_{\textrm{last},c_{2}}$ becomes simpler. In some rare cases, $\delta z$
affects $y_{\textrm{last},c_{1}}$ and $y_{\textrm{last},c_{2}}$ approximately
in the same way in a small neighborhood. In this small neighborhood of $\delta
z$ value, algorithm 2 cannot distinct the shift by criticality test, and
resulting in a larger error. This issue can be mitigated by repeating the
extraction multiple times with different initial critical points.

##  6 Conclusion and discussion

In this work, we proposed SEEK, a model extraction attack method against HE-
MPC hybrid inference service with semi-honest security, with the most
stringent assumption that the model outputs class labels only. Our method
makes use of the piecewise-linear property of the ReLU activation, and the
principle of safe-error attack, thus achieving an extraction process that can
accurately extract each layer’s parameters. As the method tests whether a
shift to the internal feature affects the criticality of the whole input, it
is not affected by the depth of the model, which can incur numerical issues
for other extraction methods. Furthermore, because the extraction of
parameters in a layer is not dependent on the extraction result of any other
layer, a distributed extraction attack is straightforward.

SEEK can be generalized to other secure inference protocols with semi-honest
security. In particular, if the ReLU activation function is replaced by other
piecewise-linear functions, such as ReLU6 or leaky ReLU, our method can be
applied in essentially the same manner. If the activation function is linear
only in part of the input range, such as the swish activation, we can also
manipulate the input so that it falls in the region of linear activation. For
secure inference of decision tree models, the general method of safe-error
attack is applicable, because the discrete nature of decision tree inference
makes it possible to change individual intemediate feature and observe the
effect on the final output. We leave the security analysis of the case of
decision tree models for future work.

As demonstrated by the proposed extraction method, the capability of changing
all the intermediate features with arbitrary shifts is quite powerful, and it
is non-trivial to prevent such attack. Shuffling the features in a layer
before the MPC protocol only increases the difficulty of this attack by a
constant factor. The model inference protocols with client-malicious security
[21, 24, 25], albeit with significant communicational and computational cost,
provide systematic countermeasure against our attack. Secure inference based
on fully homomorphic encryption with bootstrapping [28, 29], or garbled
circuits [6, 7, 8], lead to another direction of mitigation, in which the
inference is processed in constant communication rounds, so an adversary do
not have the oppotunity to malleate intermediate model features.

## References

  * [1] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , 2015, pp. 1322–1333.
  * [2] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, “Membership inference attacks against machine learning models,” in _2017 IEEE symposium on security and privacy (SP)_. IEEE, 2017, pp. 3–18.
  * [3] D. Lowd and C. Meek, “Adversarial learning,” in _Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining_ , 2005, pp. 641–647.
  * [4] R. Gilad-Bachrach, N. Dowlin, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, “Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy,” in _International conference on machine learning_. PMLR, 2016, pp. 201–210.
  * [5] A. Brutzkus, R. Gilad-Bachrach, and O. Elisha, “Low latency privacy preserving inference,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 812–821.
  * [6] B. D. Rouhani, M. S. Riazi, and F. Koushanfar, “Deepsecure: Scalable provably-secure deep learning,” in _Proceedings of the 55th annual design automation conference_ , 2018, pp. 1–6.
  * [7] M. Ball, B. Carmer, T. Malkin, M. Rosulek, and N. Schimanski, “Garbled neural networks are practical,” _Cryptology ePrint Archive_ , 2019.
  * [8] M. S. Riazi, M. Samragh, H. Chen, K. Laine, K. Lauter, and F. Koushanfar, “$\\{$XONN$\\}$:$\\{$XNOR-based$\\}$ oblivious deep neural network inference,” in _28th USENIX Security Symposium (USENIX Security 19)_ , 2019, pp. 1501–1518.
  * [9] P. Mohassel and P. Rindal, “Aby3: A mixed protocol framework for machine learning,” in _Proceedings of the 2018 ACM SIGSAC conference on computer and communications security_ , 2018, pp. 35–52.
  * [10] S. Wagh, D. Gupta, and N. Chandran, “Securenn: 3-party secure computation for neural network training.” _Proc. Priv. Enhancing Technol._ , vol. 2019, no. 3, pp. 26–49, 2019.
  * [11] N. Kumar, M. Rathee, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “Cryptflow: Secure tensorflow inference,” in _2020 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2020, pp. 336–353.
  * [12] C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, “$\\{$GAZELLE$\\}$: A low latency framework for secure neural network inference,” in _27th USENIX Security Symposium (USENIX Security 18)_ , 2018, pp. 1651–1669.
  * [13] F. Boemer, A. Costache, R. Cammarota, and C. Wierzynski, “ngraph-he2: A high-throughput framework for neural network inference on encrypted data,” in _Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography_, 2019, pp. 45–56.
  * [14] P. Mishra, R. Lehmkuhl, A. Srinivasan, W. Zheng, and R. A. Popa, “Delphi: A cryptographic inference service for neural networks,” in _29th USENIX Security Symposium (USENIX Security 20)_ , 2020, pp. 2505–2522.
  * [15] D. Rathee, M. Rathee, N. Kumar, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “Cryptflow2: Practical 2-party secure inference,” in _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 325–342.
  * [16] Z. Huang, W.-j. Lu, C. Hong, and J. Ding, “Cheetah: Lean and fast secure two-party deep neural network inference.” _IACR Cryptol. ePrint Arch._ , vol. 2022, p. 207, 2022.
  * [17] F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart, “Stealing machine learning models via prediction $\\{$APIs$\\}$,” in _25th USENIX security symposium (USENIX Security 16)_ , 2016, pp. 601–618.
  * [18] N. Papernot, P. McDaniel, I. Goodfellow, S. Jha, Z. B. Celik, and A. Swami, “Practical black-box attacks against machine learning,” in _Proceedings of the 2017 ACM on Asia conference on computer and communications security_ , 2017, pp. 506–519.
  * [19] M. Jagielski, N. Carlini, D. Berthelot, A. Kurakin, and N. Papernot, “High accuracy and high fidelity extraction of neural networks,” in _29th USENIX Security Symposium (USENIX Security 20)_ , 2020, pp. 1345–1362.
  * [20] N. Carlini, M. Jagielski, and I. Mironov, “Cryptanalytic extraction of neural network models,” in _Annual International Cryptology Conference_. Springer, 2020, pp. 189–218.
  * [21] R. Lehmkuhl, P. Mishra, A. Srinivasan, and R. A. Popa, “Muse: Secure inference resilient to malicious clients,” in _30th USENIX Security Symposium (USENIX Security 21)_ , 2021, pp. 2201–2218.
  * [22] S.-M. Yen and M. Joye, “Checking before output may not be enough against fault-based cryptanalysis,” _IEEE Transactions on computers_ , vol. 49, no. 9, pp. 967–970, 2000.
  * [23] M. Joye and S.-M. Yen, “The montgomery powering ladder,” in _International workshop on cryptographic hardware and embedded systems_. Springer, 2002, pp. 291–302.
  * [24] N. Chandran, D. Gupta, S. L. B. Obbattu, and A. Shah, “Simc: Ml inference secure against malicious clients at semi-honest cost,” _Cryptology ePrint Archive_ , 2021.
  * [25] G. Xu, X. Han, T. Zhang, H. Li, and R. H. Deng, “Simc 2.0: Improved secure ml inference against malicious clients,” _arXiv preprint arXiv:2207.04637_ , 2022.
  * [26] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [27] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, high-performance deep learning library,” in _Advances in Neural Information Processing Systems 32_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, Eds. Curran Associates, Inc., 2019, pp. 8024–8035. [Online]. Available: http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf
  * [28] I. Chillotti, M. Joye, and P. Paillier, “Programmable bootstrapping enables efficient homomorphic inference of deep neural networks,” in _International Symposium on Cyber Security Cryptography and Machine Learning_. Springer, 2021, pp. 1–19.
  * [29] J.-W. Lee, H. Kang, Y. Lee, W. Choi, J. Eom, M. Deryabin, E. Lee, J. Lee, D. Yoo, Y.-S. Kim _et al._ , “Privacy-preserving machine learning with fully homomorphic encryption for deep neural network,” _IEEE Access_ , vol. 10, pp. 30 039–30 054, 2022.