§ INTRODUCTION

§ PRELIMINARIES

An alphabet $\Sigma$ is a finite nonempty set of letters. The  empty word is denoted by $\epsilon$, the length of a word $w$ is denoted by $\size{w}$, and the $n^\text{th}$ letter of $w$ is denoted by $w(n)$ (starting with $n = 0$). The set of (finite) words over $\Sigma$ is denoted by $\Sigma^*$, the set of nonempty (finite) words over $\Sigma$ by $\Sigma^+$, and the set of finite words of length at most $n$ by $\Sigma^{\leq n}$.
A language over $\Sigma$ is a subset of $\Sigma^*$.

For alphabets $\Sigma_1,\Sigma_2$, we extend functions $f \colon \Sigma_1 \rightarrow \Sigma_2^*$ homomorphically to words over $\Sigma_1$ via
$f(w) = f(w(0)) f(w(1)) f(w(2)) \cdots$.

§.§ Pushdown automata

§ HISTORY-DETERMINISTIC PUSHDOWN AUTOMATA

§ EXPRESSIVENESS

§ SUCCINCTNESS

§ HISTORY-DETERMINISTIC VISIBLY PUSHDOWN AUTOMATA

§ CLOSURE PROPERTIES

§ COMPOSITIONALITY WITH GAMES

One of the appeals of  automata consists of the good compositional properties that they enjoy, which allows them to be used to solve  games. Namely, we consider arena-based games, in which two players, called Player 1 and Player 2, build a path, with the owner of the current position choosing an outgoing edge at each turn, and Player 2 wins if the label of the path is in the winning condition. If the winning condition is the language of a deterministic or  automaton $\daut$ with acceptance condition $C$, taking the product (or composition) of the arena with $\daut$ yields an arena which, when treated as a game with winning condition $C$, has the same winner as the original game with winning condition $L(\daut)$. In short, this product construction reduces games with winning conditions recognised by deterministic or  $C$-automata into $C$-games. For example, it can be used to reduce games with $\omega$-regular winning conditions, which are recognised by  and deterministic parity automata, into parity games. In this sense,   automata are just as good as deterministic automata when it comes to solving games via composition, making them appealing for applications such as reactive synthesis, which can be solved via games.

Here we first show that , like regular   automata, enjoy this compositional property, both with respect to finite and infinite arenas.
We then consider the converse question, namely, whether all  that behave well with respect to composition, are . This is the case for ($\omega$-)regular automata <cit.>, but not for quantitative automata <cit.>. We show that for  over finite words, those that enjoy compositionality with infinitely branching games are exactly those that are . On the other hand, unlike for the ($\omega$-)regular setting, compositionality with finitely branching games does not suffice to guarantee that the automaton is , even for automata over finite words.

Our proof of equivalence of compositionality with games and history-determinism for PDA over finite words uses the determinacy of  safety games.
Generalising this proof to automata over infinite words would require determinacy of games with $\omega$-context-free winning conditions, which is a large cardinal assumption <cit.>.

A $\Sigma$-arena $A=(V, V_1, V_2,E,\iota, \ell)$ consists of a directed graph $(V, E)$ of which the positions $V$ are partitioned into those belonging to Player $1$, $V_1$, and those belonging to Player $2$, $V_2$, of which the edges $E$ are labelled with $\Sigma \cup \set{\sink}$ via a labelling $\ell\colon E\rightarrow \Sigma\cup \{\sink\})$, and rooted at an initial position $\iota\in V$. We assume that all $\sink$-edges lead to a terminal position, that is,  without outgoing edges, that all other positions have at least one successor, and that all edges leading to a terminal position are labelled $\sink$.

A play on $A$ is a finite path ending a terminal position, or an infinite path. A strategy for a player is a mapping from finite paths ending in a position that belongs to that player to one of its outgoing edges. A play is consistent with Player $i$'s strategy $\sigma$ if for all of its prefixes $\pi$ ending in $V_i$, the next edge is $\sigma(\pi)$.

An (arena-based) game $(A, L)$ consists of a $\Sigma$-arena $A$ and a language $L\subseteq \Sigma^*$.
A finite play is winning for Player 2 if it is labelled with a word in $L\cdot\sink$.
Note that Player $2$ loses in particular all infinite plays.
Winning strategies are defined in the usual way, and we say that a player wins the game if they have a winning strategy.

We now consider the composition of an arena and an automaton, that is, a product game in which Player 2 not only has to guarantee that the label of the play in the arena is in the language of the automaton, but she also has to build an accepting run over that word, transition by transition, as the play in the arena progresses.

More formally, the positions of the product game $G(A,\aut)$ of a $\Sigma$-arena $A=(V,V_1,V_2,E,\iota, \ell)$ and a  $\aut=(Q,\Sigma, \Gamma,q_I,\Delta,F)$ consists of a position in $V$ and a configuration of $\aut$, the initial position being $(\iota, q_I, \bot)$.
At each round $i$ from position $(v,q,\gamma)$, the player who owns the position $v$ chooses an outgoing edge $(v,v')\in E$, labelled by some letter $\ell(v,v')=a$. If $a\neq \sink$, Player $2$ then chooses a possibly empty sequence of $\varepsilon$-transitions followed by one $a$-transition, so that the combined sequence induces a finite run from  $(q,\gamma)$ leading to some $(q',\gamma')$.
Then, the play proceeds in round $i+1$ from $(v', q',\gamma')$. If $a=\sink$, then the play ends in $(v',q,\gamma)$, as $v'$ is by assumption a terminal position of the arena. Player $2$ wins by reaching a position $(v,q,\gamma)$ where $v$ is the terminal position and $q$ is final. Again, strategies, winning strategies and winning the game are defined as expected.

Observe that $G(A,\aut)$ may have an infinite number of positions, and may have infinite branching, due to unbounded $\varepsilon$-transition sequences. If $A$ is finitely representable, so is $G(A,\aut)$. In particular, if $A$ is finite, then $G(A,\aut)$ is a reachability game on the configuration graph of a pushdown automaton.

Let $\aut$ be a  over an alphabet $\Sigma$.

* $\aut$ is compositional if the following holds for all (finitely or infinitely branching) $\Sigma$-arenas $A$: Player $2$ wins the game $(A,L(\aut))$ if and only if she wins $G(A,\aut)$.

* $\aut$ is weakly compositional if the following holds for all finitely branching $\Sigma$-arenas $A$: Player $2$ wins the game $(A,L(\aut))$ if and only if she wins $G(A,\aut)$.

Note that compositionality implies weak compositionality.
In the remainder of this section, we compare history-determinism and (weak) compositionality.

Every  is compositional.

Let $\aut$ be an  over $\Sigma$ and let $A$ be a $\Sigma$-arena.
If Player $2$ wins the game $(A,L(\aut))$ with a strategy $\strat$, then she wins $G(A,\aut)$ by using $\strat$ in the $A$-component of $G(A,\aut)$ and the resolver $r$ that witnesses the  of $\aut$ in the $\aut$-component of $G(A,\aut)$. Then, $\strat$ guarantees that the word built in $A$ is in $L(\aut)\cdot\sink$, and $r$ guarantees that Player $2$ reaches a final state at the end of the word in $L(\aut)$, before $\sink$ is encountered.

Conversely, a winning strategy for Player $2$ in $G(A,\aut)$ projected onto the $A$-component is a winning strategy for Player $2$ in $(A, L(\aut))$.

We now consider the converse: whether it is the case that all (weakly) compositional  are . In the regular setting, automata are weakly compositional if and only if they are compositional <cit.>.
Here, however, we observe that the answer depends on whether infinite branching is permitted in the arenas considered.

There exists a  that is weakly compositional, but not history-deterministic.

Consider the 3-state  in Fig. <ref> that recognises $a^*b$, by first guessing an upper bound $m$ on the number of $a$'s in the word, then processing $a$ no more than $m$ times, followed by a $b$.

The automaton accepts $a^nb$ by pushing $m\geq n$ elements onto the stack before reading $n$ times $a$, followed by $b$.

every state/.style = minimum size =22
[state] (i) at (0*,0) $q_1$;
[state] (m) at (2*, 0) $q_2$;
[state,fill=lightgray] (fin) at (4*,0) $f$;

(-.75,0) edge (i)
(i) edge[loop above] node[] $\varepsilon, X\mid Xa$ ()
(i) edge node[below] $\varepsilon,X\mid X$ (m)
(m) edge[] node[below] $b,X\mid X$ (fin)

(m) edge[loop above] node[] $a, a\mid \epsilon$ ()

A PDA recognising $a^* b$ that is weakly compositional but not . Grey states are final, and $X$ is an arbitrary stack

It is clearly not an , as the resolver would have to predict the number of $a$'s to be seen.
However, for all finitely branching $\Sigma$-arenas $A$, if Player $2$ wins the game $(A,L(\aut))$, she also wins $G(A,\aut)$. Indeed, if Player $2$ wins $(A,L(\aut))$ with a strategy $\strat$, then by König's lemma, there is some bound $n$ on the number of $a$'s in any play that is consistent with $\strat$. Then, in $G(A,\aut)$, Player $2$ wins by first pushing $n$ letters onto the stack in $\aut$, then playing $\strat$ in the $A$-component. Since $\strat$ guarantees that there are at most $n$ occurrences of $a$ in the play of $L(\aut)$, this strategy is winning for Player $2$.

In contrast,  are exactly the  that preserve winners when composed with infinitely branching arenas.

A  is history-deterministic if and only if it is compositional.

One direction of the equivalence was shown in Lemma <ref>: every  is compositional.

For the other direction, we show that from a  that is not history-deterministic, we can construct an arena that witnesses the failure of compositionality.
To characterize automata that are not history-deterministic, we rely on the so-called letter game, a game-based characterisation of history-determinism due to Henzinger and Piterman <cit.>.

Given a  $\aut$, the letter game is played by two players, called Challenger and Resolver, and $\aut$ is history-deterministic if and only if Resolver wins the letter game induced by $\aut$.
The game is played in rounds: in each round $i$, Challenger chooses a letter $a_i$ and then Resolver responds with $\rho_i$, the concatenation of a (potentially empty) sequence of $\varepsilon$-transitions and an $a_i$-transition. Resolver's winning condition is a safety condition: before each round $i$, either the word $w=a_0a_1\cdots a_{i-1}$ built by Challenger so far is not in the language $L(\aut)$ or the sequence $\rho_0\rho_1\cdots \rho_{i-1}$ played by Resolver so far induces an accepting run of $\aut$ over $w$. This game characterises history-determinism, as a winning strategy for Resolver is exactly a resolver witnessing the history-determinism of $\aut$.

We now crucially rely on the determinacy of the letter game, which we can easily show for  over finite words. Indeed, the winning condition for Resolver is a safety condition, in the sense that all losing plays have a finite prefix of which all continuations are losing. The winning condition is therefore Borel, and, by Martin's theorem <cit.>, determined.
This implies that if $\aut$ is not history-deterministic, then Challenger has a winning strategy ${\strat_C}$ in the letter game.

We now build an arena $A_{\strat_C}$, based on ${\strat_C}$, such that Player $2$ wins $(A_{\strat_C}, L(\aut))$, but loses the composition game $G(A_{\strat_C},\aut)$, thus witnessing that $\aut$ is not compositional.

The arena $A_{\strat_C}$ emulates the strategy tree for ${\strat_C}$, in the sense that all the plays of the arena are plays that are consistent with the strategy ${\strat_C}$.
Furthermore, the branching in the arena corresponds to the branching of the strategy tree of ${\strat_C}$, which represents Resolver's choices in the letter game.
All positions of $A_{\strat_C}$ belong to Player $1$.

Note that a play in the letter game has the form $a_0 \rho_0 a_1 \rho_1 a_2 \rho_2 \cdots$ where each $a_i$ is a letter in $\Sigma$ and each $\rho_i$ is a (possibly empty) sequence of $\varepsilon$-transitions concatenated with an $a_i$-transition.
Furthermore, as Resolver picks the $\rho_i$, it is her turn to make a move after a prefix of the form $a_0 \rho_0 a_1 \cdots \rho_{i-1} a_i$ for $i \ge 0$.
Now, the positions of $A_{\strat_C}$ are the empty play prefix, which is the initial position, and all play prefixes that are consistent with ${\strat_C}$ and end with a letter, i.e. it is Resolver's turn.
There is an $a$-labeled edge from the initial position $\epsilon$ to the position $a$, where $a$ is the letter picked by ${\strat_C}$ in round zero.
Furthermore, for every position of the form $a_0 \rho_0 a_1 \cdots \rho_{i-2} a_{i-1}\rho_{i-1} a_i$ for $i \ge 1$, there is an $a_{i}$-labeled edge from $a_0 \rho_0 a_1 \cdots \rho_{i-2} a_{i-1}$ to $a_0 \rho_0 a_1 \cdots \rho_{i-2} a_{i-1}\rho_{i-1} a_i$.

Consider a position $a_0 \rho_0 a_1 \cdots \rho_{i-1} a_i$ for $i \ge 1$.
If $w = a_0 \cdots a_{i-1}$ is in $L(\aut)$, but $\rho_0 \cdots \rho_{i-1}$ is not an accepting run processing $w$, then we replace the label $a_i$ of the edge from $a_0 \rho_0 a_1 \cdots \rho_{i-2} a_{i-1}$ to $a_0 \rho_0 a_1 \cdots \rho_{i-2} a_{i-1}\rho_{i-1} a_i$ by $\sink$ and remove all outgoing transitions of $a_0 \rho_0 a_1 \cdots \rho_{i-2} a_{i-1}\rho_{i-1} a_i$.

Note that $A_{\strat_C}$ may be infinitely branching, if Resolver can pick arbitrarily long sequences of $\epsilon$-transitions (e.g. recall the  presented in the proof of Lemma <ref>).

Recall that ${\strat_C}$ is a winning strategy for Challenger, i.e. during every play that is consistent with it, there is a round at which the word picked by Challenger is in $L(\aut)$, but Resolver has not picked an accepting run on that word.
Thus, by construction, there is no infinite play in $A_{\strat_C}$ and every maximal play ends in a terminal position and is labeled by a word in $L(\aut)\cdot \sink$.
Hence, Player $2$ wins $(A_{\strat_C}, L(\aut))$.

Now, towards a contradiction, assume that she also wins $G(A_{\strat_C}, \aut)$, say with a strategy $\strat_2$. We argue that Resolver can mimic $\strat_2$ in the letter game, and thereby win against ${\strat_C}$, a contradiction.
Indeed, $\strat_2$ only chooses transitions in $\aut$, since all positions in $A_{\strat_C}$ belong to Player $1$.
However, note that $\strat_2$ in $G(A_{\strat_C}, \aut)$ can base its decisions on the sequence of transitions picked by Player $1$ during the play.
By only considering those plays where Player $1$'s choices mimic the choices made by $\strat_2$, which is possible due to the construction of $A_{\strat_C}$, we eliminate this additional information.

So, let us define the strategy for the letter game mimicking $\strat_2$ inductively:
In round zero, Challenger picks some $a$ according to $\strat_C$ in the letter game.
Now, let $\rho_0$ be the sequence of transitions picked by $\strat_2$ in $G(A_{\strat_C},\aut)$ in reaction to the initial move, which leads via an $a$-labeled edge from $\epsilon$ to $a$.
Then, Resolver picks $\rho_0$ during the first round of the letter game.

Now, assume we are in round $i>0$ of the letter game, Challenger has picked $a_0 \cdots a_{i}$ so far, Resolver has answered with $\rho_0 \cdots \rho_{i-1}$, and now has to pick $\rho_i$.
Consider the position $a_0 \rho_0 \cdots \rho_{i-1}a_i$ of $A_{\strat_C}$.
As $A_{\strat_C}$ is a tree, there is a unique play prefix ending in that position.
By construction of our strategy, this play prefix is consistent with $\strat_2$.
Now, let $\rho_i$ be the sequence of transitions picked by $\strat_2$ for that play prefix.
Then, Resolver picks $\rho_i$ during the $i^{\text{th}}$ round of the letter game.

Recall that $\strat_2$ is a winning strategy for Player $2$ in $G(A_{\strat_C},\aut)$.
So, for every maximal play in $A_{\strat_C}$, which by construction is labeled by a word in $L(\aut)\cdot\sink$, $\strat_2$ constructs an accepting run of $\aut$ processing that word.
Thus, the mimicking strategy in the letter game is winning for Resolver.
Thus, we have derived the desired contradiction.

We conclude that if $\aut$ is not history-deterministic, then we can build, from a winning strategy for Challenger in the letter game, an arena such that Player $2$ wins in the arena, but not in the composition with $\aut$, witnessing that $\aut$ is not compositional.

Observe that infinite branching is key for this proof to work, as exhibited by the counter-example in the proof of Lemma <ref>. Another ingredient we use is the determinacy of the letter game. While this is easy enough to obtain for   over finite words, for which the letter game is a safety game (albeit with a potentially complex safe region), this becomes trickier for  over infinite words. Indeed, then the letter game's winning condition for Resolver is no longer a safety condition and it involves the negation of an $\omega$-context-free language. The determinacy of games with a winning condition given by a Büchi one-counter automaton is a large cardinal assumption <cit.>, so obtaining determinacy for these letter games on $\omega$- is likely to be challenging.

§ SOLVING GAMES AND UNIVERSALITY

One of the motivations for automata is that solving games with winning conditions given by automata is easier than for nondeterministic automata. This makes them appealing for applications such as the synthesis of reactive systems, which can be modelled as a game between an antagonistic environment and the system. Solving games is undecidable for PDA in general <cit.>, both over finite and infinite words, while for $\omega$--PDA, it is $\exptime$-complete <cit.>. As a corollary, universality is also decidable for $\omega$--PDA, while it is undecidable for PDA, both over finite and infinite words <cit.>.

Here, we consider Gale-Stewart games <cit.>, abstract games induced by a language in which two players alternately pick letters, thereby constructing an infinite word. One player aims to construct a word that is in the language while the other aims to construct one that is not in the language. We use Gale-Stewart games rather than the arena-based games from the previous section since they are more convenient to work with.
This is not a restriction, since arena-based games with finite arenas and Gale-Stewart games, both with winning conditions recognised by PDA, are effectively equivalent: a finite arena can be simulated by the PDA recognising the winning condition while a Gale-Stewart game can be seen as an arena-based game with a trivial arena.

Formally, given a language $L\subseteq (\Sigma_1\times \Sigma_2)^*$ of sequences of letter pairs, the game $G(L)$ is played between Player 1 and Player 2 in rounds $i=0,1,\ldots$ as follows: At each round $i$, Player 1 plays a letter $a_i\in\Sigma_1$ and Player 2 answers with a letter $b_i\in \Sigma_2$. A play of $G(L)$ is an infinite word $\binom{a_0}{b_0}\binom{a_1}{b_1}\cdots$ and Player 2 wins such a play if and only if each of its prefixes is in the language $L$.
A strategy for Player $2$ is a mapping from $\Sigma_1^+$ to $\Sigma_2$ that gives for each prefix played by Player 1 the next letter to play. A play is consistent with a strategy $\sigma$ if for each $i$, $b_i=\sigma(a_0a_1\dots a_i)$.
Player 2 wins $G(L)$ if she has a strategy such that all plays that are consistent with it are winning for Player 2. Observe that Player 2 loses whenever the projection of $L$ onto its first component is not universal.
Finally, universality reduces to solving these games: $\aut$ is universal if and only if Player 2 wins $G(L)$ for $L=\{\binom{w(0)}{\#} \cdots \binom{w(n)}{\#}\mid w(0) \cdots w(n)\in L(\aut)\}$.

We now argue that solving games for -PDA easily reduces to the case of $\omega$--PDA, which are just -PDA over infinite words, where acceptance is not determined by final state, since runs are infinite, but rather by the states or transitions visited infinitely often. Here, we only need safety $\omega$--PDA, in which every infinite run is accepting (i.e. rejection is implemented via missing transitions). The infinite Gale-Stewart game over a language $L$ of infinite words, also denoted by $G(L)$, is as above, except that victory is determined by whether the infinite word built along the play is in $L$.

Given an -PDA $\aut$, there is a safety $\omega$--PDA $\aut'$ no larger than $\aut$ such that Player 2 wins $G(L(\aut))$ if and only if she wins $G(L(\aut'))$.

Let $\aut'$ be the PDA obtained from $\aut$ by  removing all transitions $(q,X,a,q',\gamma)$ of $\aut$ with $a \in \Sigma$ and with non-final $q'$.
Note that all $\epsilon$-transitions are preserved.

With a safety condition, in which every infinite run is accepting, $\aut'$ recognises exactly those infinite words whose prefixes are all accepted by $\aut$.
Hence, the games $G(L(\aut))$ and $G(L(\aut'))$ have the same winning player.
Note that the correctness of this construction crucially relies on our definition of -PDA, which requires a run on a finite word to end as soon as the last letter is processed.
Then, the word is accepted if and only if the state reached by processing this last letter is final.

Finally, since $\aut$ is , so is $\aut'$. Consider an infinite input in $L(\aut')$. Then, every prefix $w$ has an accepting run of $\aut$ induced by its resolver, which implies that the last transition of this run (which processes the last letter of $w$) is not one of those that are removed to obtain $\aut'$. Now, an induction shows that the same resolver works for $\aut'$ as well, relying on the fact that if $w$ and $w'$ with $\size{w}<\size{w'}$ are two such prefixes, then the resolver-induced run of $\aut$ on $w$ is a prefix of the resolver-induced run of $\aut$ on $w'$.

Our main results of this section are now direct consequences of the corresponding results on $\omega$-words <cit.>.

Given an -PDA $\aut$, deciding whether $L(\aut)=\Sigma^*$ and whether Player 2 wins $G(L(\aut))$ are both in $\exptime$.

§ RESOLVERS

The definition of a resolver does not put any restrictions on its complexity. In this section we study the complexity of the resolvers that -PDA need. We consider two somewhat orthogonal notions of complexity: memory and machinery. On one hand, we show that resolvers can always be chosen to be positional, that is, dependent on the current state and stack configuration only. Note that this is not the case for $\omega$-regular automata[A positional resolver for $\omega$-regular automata implies determinisability by pruning, and we know that this is not always possible <cit.>], let alone $\omega$--PDA. On the other hand, we show that they are not always implementable by pushdown transducers.

More formally, a resolver $r$ is positional, if for any two sequences $\rho$ and $\rho'$ of transitions inducing runs ending in the same configuration, $r(\rho, a)=r(\rho',a)$ for all $a\in \Sigma$.

Every -PDA has a positional resolver.

Let $r'$ be a (not necessarily positional) resolver for $\aut$. We define a resolver $r$ such that for each configuration and input letter, it makes a choice consistent with $r'$ for some input leading to this configuration.
In other words, for every reachable configuration $c$, let $\rho_c$ be an input to $r'$ inducing a run ending in $c$.
Then, we define $r(\rho, a) = r'(\rho_c, a)$, where $c$ is the last configuration of the run induced by $\rho$.

We claim that $r$, which is positional by definition, is a resolver.
Towards a contradiction, assume that this is not the case, i.e. there is a word $w\in L(\aut)$ such that the run $\rho$ induced by $r$ is rejecting. Since this run is finite and $w \in L(\aut)$, there is some last configuration $c$ along the run $\rho$ from which the rest of the word, say $u$, is accepted[Observe that this is no longer true over infinite words as an infinite run can stay within configurations from where an accepting run exists without being itself accepting. In fact, the lemma does not even hold for coBüchi automata <cit.> as the existence of positional resolvers implies determinisability by pruning.] (by some other run of $\aut$ having the same prefix as $\rho$ up to configuration $c$). Let $\tau$ be the next transition along $\rho$ from $c$. Since $r$ chose $\tau$, the resolver $r'$ also chooses $\tau$ after some history leading to $c$, over some word $v$. Since $u$ is accepted from $c$, the word $vu$ is in $L(\aut)$; since $r'$ is a resolver, there is an accepting run over $u$ from $c$ starting with $\tau$, contradicting that $c$ is the last position on $\rho$ from where the rest of the word could be accepted.

Contrary to the case of finite and $\omega$-regular automata, since -PDA  have an infinite configuration space, the existence of positional resolvers does not imply determinisability.
On the other hand, if an -PDA has a resolver which only depends on the mode of the current configuration, then it is determinisable by pruning, as transitions that are not used by the resolver can be removed to obtain a deterministic automaton.
However, not all -PDA are determinisable by pruning, e.g. the -PDA for the languages $C_n$ used to prove Theorem <ref>.

We now turn to how much resources a machine needs in order to implement a resolver for an -PDA.
First, we introduce transducers as a way to implement a resolver. A transducer is an automaton with outputs instead of acceptance, i.e., it computes a function from input sequences to outputs. A pushdown resolver is a pushdown transducer that implements a resolver.

Note that a resolver has to pick enabled transitions in order to induce accepting runs for all inputs in the language.
To do so, it needs access to the mode of the last configuration.
However, to keep track of this information on its own, the pushdown resolver would need to simulate the stack of the -PDA it controls.
This severely limits the ability of the pushdown resolver to implement computations on its own stack.
Thus, we give a pushdown resolver access to the current mode of the -PDA via its output function, thereby freeing its own stack to implement further functionalities.

Formally, a pushdown transducer (PDT for short) $\taut= (\daut, \lambda)$ consists of a DPDA $\daut$ augmented with an output function $\lambda : Q^\daut \rightarrow \Theta$ mapping the states $Q^\daut$ of $\daut$ to an output alphabet $\Theta$.
The input alphabet of $\taut$ is the input alphabet of $\daut$.

Then, given a PDA $\aut=(Q, \Sigma, \Gamma, q_\initmark, \Delta, F )$, a pushdown resolver for $\aut$ consists of a pushdown transducer $\taut= (\daut,\lambda)$ with input alphabet $\Delta$ and output alphabet $Q\times \Gammabot \times \Sigma\rightarrow \Delta$ such that
the function $r_\taut$, defined as follows, is a resolver for $\aut$:
$ r_\taut(\tau_0\dots \tau_k,a)= \lambda(q_\taut)(q_\aut,X,a)$

* $q_\taut$ is the state of the last configuration of the longest run of $\daut$ on $\tau_0\dots \tau_k$ (recall that while $\daut$ is deterministic, it may have several runs on an input which differ on trailing $\epsilon$-transitions);

* $(q_\aut, X)$ is the mode of the last configuration of the run of $\aut$ induced by $\tau_0\dots\tau_k$.

In other words, a transducer implements a resolver by processing the run so far, and then uses the output of the state reached and the state and top stack symbol of the -PDA to determine the next transition in the -PDA.

every state/.style = minimum size =22
[state] (i) at (0*,0) $q_1$;
[state] (ii) at (2*, 0) $q_2$;
[state] (iii) at (4*,0) $q_3$;
[state] (iv) at (4*,-2*) $p_1$;
[state] (vi) at (6*,-2*) $p_2$;
[state] (vii) at (8*,-2*) $p_3$;
[state,fill=lightgray] (viii) at (10*,-2*) $f$;

(-.75,0) edge (i)
(i) edge[loop above] node[] $a, X \mid Xa $ ()
(ii) edge[loop above] node[] $a, X \mid Xa $ ()
(iii) edge[loop above] node[] $a, X \mid Xa $ ()
(iv) edge[loop below] node[] $\epsilon, a \mid \epsilon $ ()
(vi) edge[loop below] node[] $\epsilon, a \mid \epsilon $ ()
(vii) edge[loop below] node[] $b,a\mid \epsilon$ ()
(i) edge node[above] $\$,X \mid X\$ $ (ii)
(ii) edge node[above] $\$,X\mid X\$ $ (iii)
(iii) edge[] node[left] $\$, X \mid X$ (iv)
(iii) edge[bend left =20] node[right,near start,yshift=.2cm] $\$, X \mid X$ (vii)
(iii) edge[bend left=0] node[right,xshift=.1cm] $\$, X \mid X$ (vi)
(iv) edge node[above,near start,xshift=.2cm] $\epsilon, \$ \mid \epsilon$ (vi)
(vi) edge node[above, near start,xshift=.2cm] $\epsilon, \$ \mid \epsilon$ (vii)
(vii) edge node[above] $\$,X \mid X\$ $ (viii)

The PDA $\aut_{\lmax}$ for $\lmax$. Grey states are final, and $X$ is an arbitrary stack symbol.

We now give an example of an -PDA which does not have a pushdown resolver. The language in question is the language $
\lmax=\{a^i\$a^j\$a^k\$b^l\$\mid l\leqslant\max(i,j,k)\}$.
Compare this to the language $B_2$ in Section <ref> which does have a pushdown resolver.
Let $\aut_{\lmax}$ be the automaton in Figure <ref>, which works analogously to the automaton for $B_2$ in Figure <ref>.

This automaton recognises $\lmax$: for a run to end in the final state, the stack, and therefore the input, must have had an $a$-block longer than or equal to the final $b$-block; conversely, if the $b$-block is shorter than or equal to some $a$-block, the automaton can nondeterministically pop the blocks on top of the longest $a$-block off the stack before processing the $b$-block. Furthermore, this automaton is : the nondeterminism can be resolved by removing from the stack all blocks until the longest $a$-block is at the top of the stack, and this choice can be made once the third $\$$ is processed.

We now argue that this -PDA needs more than a pushdown resolver.
The reason is that a pushdown resolver needs to be able to determine which of the three blocks is the longest while processing a prefix of the form $a^*\$a^*\$a^*$. However, at least one of the languages induced by these three choices is not context-free, yielding the desired contradiction.

The -PDA $\aut_{\lmax}$ has no pushdown resolver.

Towards a contradiction, assume that there is a pushdown resolver $r$ for $\aut_{\lmax}$,
implemented by a PDT $\taut= (\daut, \lambda)$.

We construct, for each $i\in \{1,2,3\}$, a PDA $\daut_i$ that recognises the language of words $w \in a^+ \$ a^+ \$ a^+$ such that $\taut$ chooses the transition of $\aut_{\lmax}$ going from $q_3$ to $p_i$ when constructing a run on $w\$$.
Then, we show that at least one of the languages $L(\daut_i)$ is not context-free, thereby obtaining the desired contradiction.

To this end, we first restrict the possible inputs $\daut$ can process.
Let $\tau_i$ for $i \in \set{1,2,3}$ be the self-loop processing $a$ on state $q_i$ of $\aut_{\lmax}$ and let $\tau_i'$ for $i \in\set{1,2}$ be the $\$$-transition from $q_i$ to $q_{i+1}$.
Now, let $\auta$ be a DFA for the regular language $\tau_1^+ \tau_1' \tau_2^+ \tau_2' \tau_3^+$ and let $\daut'$ be obtained by taking the product of $\daut$ with $\auta$.
Note that $\daut'$ does not process any $\epsilon$-transitions nor $b$-transitions of $\aut_{\lmax}$.

Now the PDA $\daut_i$ for $i\in\set{1,2,3}$ is obtained from $\daut'$ by modifying each transition of $\daut'$ processing a transition $\tau$ of $\aut_{\lmax}$ to now process $\ell(\tau)\in \{a,\$\}$, and final states are defined as follows:
Recall that states of $\daut'$ are of the form $(q,q')$ where $q$ is a state of $\daut$ and $q'$ is a state of $\auta$.
Such a state is final in $\daut_i$ if $q'$ is final in $\auta$, i.e., a word of the form $a^+\$a^+\$a^+$ has been processed, and $\lambda(q)(q_3,a,\$)=(q_3,\$, a, p_i, a)$, i.e., $\taut$ chooses the transition of $\aut_{\lmax}$ going from $q_3$ to $p_i$.

The language $a^+\$a^+\$a^+$
is partitioned among the languages recognized by $\daut_1$, $\daut_2$ and $\daut_3$,
which implies that there is at least one $i\in \{1,2,3\}$
such that $\daut_i$ accepts $a^m\$a^m\$a^m$ for infinitely many $m$'s.
Let us fix such an index $i$ for the rest of the proof.
Note that for every $m_1,m_2,m_3 \in \mathbb{N}$, the resolver $\daut$
needs to be able to prolong the run selected over the input $a^{m_1}\$a^{m_2}\$a^{m_3}\$$
into an accepting run if the suffix $b^{\max(m_1,m_2,m_3)}$ is encountered.
This is only possible from the states $q_j$ satisfying $\max(m_1,m_2,m_3)= m_j$,
which implies that every word $a^{m_1}\$a^{m_2}\$a^{m_3}$
accepted by $\daut_i$ satisfies $\max(m_1,m_2,m_3)= m_i$.

To reach a contradiction, we now argue that this $\daut_i$ recognises a language that is not context-free. Indeed, if it were, then by applying the pumping lemma for context-free languages, there would be a large enough $m$ such that the word $a^m\$a^m\$a^m\in L(\daut_i)$ could be decomposed as $uvwyz$ such that $|vy|\geqslant 1$ and $uv^n w y^n z$ is in the language of $\daut_i$ for all $n\geqslant 0$. In this decomposition, $v$ and $y$ must be $\$$-free. Then, if either $v$ or $y$ occurs in the $i^{\text{th}}$ block and is non-empty, by setting $n=0$ we obtain a contradiction as the $i^{\text{th}}$ block is no longer the longest. Otherwise, we obtain a similar contradiction by setting $n=2$. In either case, this shows that $\taut$ is not a pushdown resolver for $\aut$.

Another restricted class of resolvers are finite-state resolvers, which can be seen as pushdown resolvers that do not use their stack.
Similarly to the case of $\omega$--PDA <cit.>, the product of an -PDA and a finite-state resolver yields a DPDA for the same language.

Every -PDA with a finite-state resolver is determinisable.

Note that the converse does not hold. For example, consider the regular, and therefore deterministic context-free, language $L_{10}$ of words $w\#$ with $w \in \set{a,b}^*$ with infix $a^{10}$. An -PDA $\aut_{10}$ recognising $L_{10}$ can be constructed as follows: $\aut_{10}$ pushes its input  onto its stack until processing the first $\#$. Before processing this letter, $\aut_{10}$ uses $\epsilon$-transitions to empty the stack again. While doing so, it can nondeterministically guess whether the next $10$ letters removed from the stack are all $a$'s. If yes, it accepts; in all other cases (in particular if the input word does not end with the first $\#$ or the infix $a^{10}$ is not encountered on the stack) it rejects.
This automaton is history-deterministic, as a resolver has access to the whole prefix before the first $\#$ when searching for $a^{10}$ while emptying the stack. This is sufficient to resolve the nondeterminism.
On the other hand, there is no finite-state resolver for $\aut_{10}$, as resolving the nondeterminism, intuitively, requires to keep track of the whole prefix before the first $\#$ (recall that a finite-state resolver only has access to the topmost stack symbol).

We consider another model of pushdown resolver, namely one that does not only have access to the mode of the -PDA, but can check the full stack for regular properties.

Thus, we consider a more general model where the transducer can use information about the whole stack when determining the next transition.
More precisely, we consider a regular abstraction of the possible stack contents by fixing a DFA running over the stack and allowing the transducer to base its decision on the state reached by the DFA as well.

Then, given a PDA $\aut=(Q, \Sigma, \Gamma, q_\initmark, \Delta, F )$, a pushdown resolver with regular stack access $\taut= (\daut, \auta, \lambda)$ consists a DPDA $\aut$ with input alphabet $\Delta$, a DFA $\auta$ over $\Gammabot$ with state set $Q^\auta$, and an output function $\lambda$ with output alphabet $Q\times Q^\auta \times \Sigma\rightarrow \Delta$ such that
the function $r_\taut$ defined as follows, is a resolver for $\aut$:

\[ r_\taut(\tau_0\dots \tau_k,a)= \lambda(q_\taut)(q_\aut,q_\auta,a)\]

* $q_\taut$ is the state of the last configuration of the longest run of $\daut$ on $\tau_0\dots \tau_k$ (recall that while $\daut$ is deterministic, it may have several runs on an input which differ on trailing $\epsilon$-transitions).

* Let $c$ be the last configuration of the run of $\aut$ induced by $\tau_0\dots\tau_k$. Then, $q_\aut$ is the state of $c$ and $q_\auta$ is the state of $\auta$ reached when processing the stack content of $c$.

Every pushdown resolver with only access to the current mode is a special case of a pushdown resolver with regular stack access.
On the other hand, having regular access to the stack is strictly stronger than having just access to the mode. However, by adapting the underlying -PDA, one can show that the languages recognised by -PDA with pushdown resolvers does not increase when allowing regular stack access.

Every -PDA with a pushdown resolver with regular stack access can be turned into an equivalent -PDA with a pushdown resolver.

Let $\aut=(Q, \Sigma, \Gamma, q_\initmark, \Delta, F )$ be an -PDA and let $(\daut, \auta, \lambda)$ be a pushdown resolver with stack access for $\aut$.
We keep track of the state $\auta$ reaches on the current stack as in the proof of Lemma <ref>:
If a stack content $\bot(X_1, q_1) \cdots (X_s, q_s)$ is reached, then $q_j$ is the unique state of $\aut$ reached when processing $\bot X_1 \cdots X_j$.
Now, it is straightforward to turn $(\daut, \auta, \lambda)$ into a pushdown resolver for $\aut$ that has only access to the top stack symbol.

Finally, for -VPA, the situation is again  much better. Using the one-token game discussed in the proof of Theorem <ref> and known results <cit.> about VPA games having VPA strategies, we obtain our final theorem.

Every -VPA has a (visibly) pushdown resolver that can be computed in exponential time.

Recall the one-token game that characterises of a VPA $\aut$ from the proof of Theorem <ref>.
We argued there that the one-token game is a safety game played on the configuration graph of a deterministic VPA whose size is polynomial in the size of $\aut$.
Therefore, Player $2$, when she wins, has a winning strategy that can be implemented by a visibly pushdown transducer, which can be computed in exponential time <cit.>.
The proof of Theorem <ref> shows that such a strategy for Player $2$ in the one-token game for VPA induces a resolver. We conclude that -VPA have visibly pushdown resolvers computable in exponential time.

Note that in the above proof, we could also compute directly a strategy to the letter game, rather than the one-token game, by using the closure of VPA under complementation and union to encode the letter game as a safety game on the configuration graph of a VPA. However, the resulting VPA would be of exponential, rather than polynomial, size.

§ CONCLUSION

We have continued the study of history-deterministic pushdown automata, focusing on expressiveness and succinctness. In particular, we have shown that -PDA are not only more expressive than DPDA (as had already been shown for the case of infinite words), but also more succinct than DPDA:
We have introduced the first techniques for using nondeterminism to succinctly represent languages that do not depend on the coBüchi condition.
Similarly, for the case of VPA, for which deterministic and nondeterministic automata are equally expressive, we proved a (tight) exponential gap in succinctness.

Solving games and universality are decidable for -PDA, but is undecidable and -PDA have limited closure properties.
On the other hand, for VPA is decidable and they inherit the closure properties of VPA, e.g. union, intersection and complementation, making -VPA an exciting class of pushdown automata.
Finally, we have studied the complexity of resolvers for -PDA, showing that positional ones always suffice, but that they are not always implementable by pushdown transducers.
Again, -VPA are better-behaved, as they always have a resolver implementable by a VPA.

Let us conclude by mentioning some open problems raised by our work.

* It is known that the succinctness gap between PDA and DPDA is noncomputable <cit.>, i.e. there is no computable function $f$ such that any PDA of size $n$ that has some equivalent DPDA also has an equivalent DPDA of size $f(n)$. Due to our hierarchy results, at least one of the succinctness gaps between PDA and -PDA and between -PDA and DPDA has to be uncomputable, possibly both.

* We have shown that some -PDA do not have pushdown resolvers.
It is even open whether every -PDA has a computable resolver.

* On the level of languages, it is open whether every language in has an -PDA recognising it with a resolver implementable by a pushdown transducer.

* We have shown that is undecidable, both for PDA and for context-free languages. Is it decidable whether a given -PDA has an equivalent DPDA?

* Equivalence of DPDA is famously decidable <cit.> while it is undecidable for PDA <cit.>. Is equivalence of -PDA decidable?

* Does every -PDA that is equivalent to a DPDA have a finite-state resolver with regular stack access?

* There is a plethora of fragments of context-free languages one can compare to, let us just mention a few interesting ones: Height-deterministic context-free languages <cit.>, context-free languages with bounded nondeterminism <cit.> and preorder typeable visibly pushdown languages <cit.>.

* We have shown that history-determinism and good-for-gameness coincide for PDA over finite words; it remains open whether this is also the case for PDA over infinite words.


11institutetext: National Key Laboratory for Novel Software Technology,
Nanjing University, China
School of Artificial Intelligence, Nanjing University, China
11email<EMAIL_ADDRESS>
# Bi-CryptoNets: Leveraging Different-Level Privacy
For Encrypted Inference

Man-Jie Yuan  Zheng Zou  Wei Gao(✉)

###### Abstract

Privacy-preserving neural networks have attracted increasing attention in
recent years, and various algorithms have been developed to keep the balance
between accuracy, computational complexity and information security from the
cryptographic view. This work takes a different view from the input data and
structure of neural networks. We decompose the input data (e.g., some images)
into sensitive and insensitive segments according to importance and privacy.
The sensitive segment includes some important and private information such as
human faces and we take strong homomorphic encryption to keep security,
whereas the insensitive one contains some background and we add perturbations.
We propose the bi-CryptoNets, i.e., plaintext and ciphertext branches, to deal
with two segments, respectively, and ciphertext branch could utilize the
information from plaintext branch by unidirectional connections. We adopt
knowledge distillation for our bi-CryptoNets by transferring representations
from a well-trained teacher neural network. Empirical studies show the
effectiveness and decrease of inference latency for our bi-CryptoNets.

###### Keywords:

Neural network Encryption Privacy-preserving inference.

##  1 Introduction

Recent years have witnessed increasing attention on privacy-preserving neural
networks [14, 4, 25], which can be viewed as a promising security solution to
the emerging Machine Learning as a Service (MLaaS) [30, 13, 15]. Specifically,
some clients can upload their encrypted data to the powerful cloud
infrastructures, and then obtain machine learning inference services; the
cloud server performs inference without seeing clients’ sensitive raw data by
cryptographic primitives, and preserve data privacy.

Privacy-preserving neural networks are accompanied with heavy computational
costs because of homomorphic encryption [12, 2], and various algorithms and
techniques have been developed to keep the balance between accuracy,
information security and computation complexity. For example, Brutzkus et al.
proposed the LoLa network for fast inference over a single image based on
well-designed packing methods [4], and Lou and Jiang introduced the circuit-
based network SHE with better accuracies [27], implemented with the TFHE
scheme [7]. Dathathri et al. presented the compiler CHET to optimize data-flow
graph of HE computations for privacy-preserving neural networks [10] . Yin et
al. presented a comprehensive survey on privacy-preserving networks [39].

Figure 1: An illustration for input data (e.g., some images222Download from
ILSVRC dataset [38].), which consists of two segments with different
importance and privacy.

Previous studies mostly encrypted the entire input data and treated
indiscriminately. In some applications, however, input data may consist of
sensitive and insensitive segments according to different importance and
privacy. As shown in Figure 2, a fighter is more sensitive than background
such as sky and mountains in a military picture, and a human face is more
private than landscape in a photo.

This work presents new privacy-preserving neural network from the view of
input data and network structure, and the main contributions can be summarized
as follows:

  * •

We decompose input data (e.g., images) into sensitive and insensitive segments
according to importance and privacy. We adopt strong homomorphic encryption to
keep the security of sensitive segment, yet mingle some perturbations [11, 38]
to insensitive segment. This could reduce computational overhead and perform
private inference of low latency, without unnecessary encryption on
insensitive segment.

  * •

We propose the bi-CryptoNets, i.e., ciphertext and plaintext branches, to deal
with sensitive and insensitive segments, respectively. The ciphertext branch
could use information from plaintext branch by unidirectional connections, but
the converse direction does not hold because of the spread of ciphertexts. We
integrate features for the final predictions, from the outputs of both
branches.

  * •

We present the feature-based knowledge distillation to improve the performance
of our bi-CryptoNets, from a teacher of convolutional neural network trained
on the entire data without decomposition.

  * •

We present empirical studies to validate the effectiveness and decrease of
inference latency for our bi-CryptoNets. We could improve inference accuracy
by $0.2\%\sim 2.1\%$, and reduce inference latency by $1.15\times\sim
3.43\times$ on a single image, and decrease the amortized latency by
$4.59\times\sim 13.7\times$ on a batch of images.

The rest of this work is organized as follows: Section 2 introduces relevant
work. Section 3 presents our bi-CryptoNets. Section 4 proposes the feature-
based knowledge distillation. Section 5 conducts experiments, and Section 6
concludes with future work.

##  2 Relevant Work

Homomorphic encryption. Homomorphic Encryption (HE) is a cryptosystem that
allows operations on encrypted data without requiring access to a secret key
[12]. In addition to encryption function $E$ and decryption function $D$, HE
scheme provides two operators $\oplus$ and $\otimes$ such that, for every pair
of plaintexts $x_{1}$ and $x_{2}$,

$\displaystyle D(E(x_{1})\oplus E(x_{2}))=x_{1}+x_{2}\ ,\quad
D(E(x_{1})\otimes E(x_{2}))=x_{1}\times x_{2}\ ,$

where $+$ and $\times$ are the standard addition and multiplication,
respectively. Hence, we could directly perform private addition,
multiplication and polynomial functions over encrypted data, by using $\oplus$
and $\otimes$ operators without knowing true values in plaintexts.

The commonly-used HE cryptosystems include CKKS [6], BGV [3] and TFHE [7] for
privacy-preserving machine learning. The BGV and TFHE schemes support integer
and bits computations, while the CKKS scheme supports fixed-point
computations. For CKKS, a ciphertext is an element in the ring
$\mathcal{R}_{p}^{2}$, where $\mathcal{R}_{p}=\mathbb{Z}_{p}[x]/(x^{N}+1)$ is
the residue ring of polynomial ring, with polynomial degree $N$. In addition
to HE, a recent study introduced a new data encryption scheme by incorporating
crucial ingredients of learning algorithm, specifically the Gini impurity in
random forests [37].

Privacy-preserving neural networks. Much attention has been paid on the
privacy-preserving neural networks in recent years. For example, Gilad-
Bachrach et al. proposed the first CryptoNets to show the feasibility of
private CNN inference by HE scheme [14]. Brutzkus et al. proposed the LoLa to
optimize the implementation of matrix-vector multiplication by different
packing methods, and achieve fast inference for single image [4]. In those
studies, the ReLU activation has been replaced by squared activation because
the used HE schemes merely support polynomial functions. Lou and Jiang
presented a circuit-based quantized neural network SHE implemented by TFHE
scheme, which could perform ReLU and max pooling by comparison circuits to
obtain good accuracies [27]. Recent studies utilized the CKKS scheme to avoid
quantization of network parameters for better accuracies [9, 25].

Knowledge Distillation. Knowledge distillation focuses on transferring
knowledge from a pretrained teacher model to a student model [22, 26].
Traditional methods aimed to match the output distributions of two models by
minimizing the Kullback-Leibler divergence loss [22]. Subsequently, a variety
of innovative distillation techniques have been developed. Romero et al.
proposed Fitnets [31], which matches the feature activations, while Zagoruyko
and Komodakis suggested matching attention maps between two models [40]. Gou
et al. gave an extensive review on knowledge distillation [17].

Threat model. Our threat model follows previous studies on private inference
[1, 28, 8]. A honest but curious cloud-based machine learning service hosts a
network, which is trained on plaintext data (such as public datasets) and
hence the network weights are not encrypted [14]. To ensure the
confidentiality of client’s data, the client could encrypt the sensitive
segment of data by using HE scheme and send data to the cloud server for
performing private inference service without decrypting data or accessing the
client’s private key. Only the client could decrypt the inference result by
using the private key.

Figure 2: Counts of HE multiplications and activations for decomposed and
entire image.

Figure 3: The fast spread of ciphertext via CNN layers.

##  3 Our bi-CryptoNets

In this section, we will present new privacy-preserving neural network
according to different-level privacy of input data. Our motivation is to
decompose input data into _sensitive_ and _insensitive_ segments according to
their privacy. The sensitive segment includes some important and private
information such as human faces in an image, whereas the insensitive one
contains some background information, which is not so private yet beneficial
to learning algorithm.

Based on such decomposition, we could take the strongest homomorphic
encryption to keep data security for sensitive segment, while mingle with some
perturbations [11, 38] to the data of insensitive segment. This is quite
different from previous private inference [14, 25], where homomorphic
encryption is applied to the entire input data.

Notice that we can not directly use some previous neural networks to tackle
such decomposition with much smaller computational cost, as shown in Figure 3.
We compare with three private networks LoLa [4], SHE [27], CryptoDL [20], and
two conventional networks VGG16 and ResNet18. Prior networks can not reduce HE
operations because ciphertexts could quickly spread over the entire image via
several convolution and pooling operations, as shown in Figure 3.

Our idea is quite simple and intuitive for the decomposition of input data. We
construct a bi-branch neural network to deal with the sensitive and
insensitive segments, which are called _ciphertext_ and _plaintext_ branch,
respectively. The ciphertext branch can make use of features from plaintext
branch by unidirectional connections, while the converse direction does not
hold because of the quick spread of ciphertexts. We take the feature
integration for final predictions from the outputs of two branches of network.

Figure 4 presents an overview for our new privacy-preserving neural network,
and it is short for _bi-CryptoNets_. We will go to the details of bi-
CryptoNets in the following.

###  3.1 The bi-branch of neural network

We construct ciphertext and plaintext branches to deal with the sensitive and
insensitive segments of an input instance, respectively. The plaintext branch
deals with the entire input instance, where the insensitive segment is mingled
with some perturbations [11, 38], while the sensitive segment is simply filled
with zero. The ciphertext branch tackles the sensitive segment with the
homomorphic encryption due to its privacy.

The HE operations are restricted in the ciphertext branch to avoid the
ciphertext spread on plaintext branch. This could keep the proportion of HE
operations in a stable level, rather than previous close approximation to $1$
as depth increases [14]. Hence, our bi-branch structure could decease HE
operations. Moreover, plaintext branch can be computed with full precision for
performing inference, rather than quantized homomorphic ciphertext in prior
privacy-preserving neural networks [20].

Figure 4: The overview of our proposed bi-CryptoNets, where grey layers are
computed with encrypted inputs, and other layers are computed with plaintext
inputs.

###  3.2 The unidirectional connections

It is well-known that one great success of deep learning lies in the strong
features or representations by plentiful co-adaptations of neural network [21,
35, 16]. Our bi-branch neural network reduces some co-adaptations of features
obviously, to restrict the spread of ciphertexts. Hence, it is necessary to
strengthen features’ representations by exploiting some correlations in bi-
branches.

Notice that the ciphertext branch can make use of features from plaintext
branch, while the converse direction does not hold because of the spread of
ciphertexts. In this work, we consider the simple addition to utilize features
from plaintext branch as convolutional neural network [19, 36, 29].
Concatenation is another effective way to utilize features [24, 23], while it
yields more HE operations and computational costs.

Table 1: The comparisons of latency (ms) for three schemes and four operations. HE Scheme |  Add${}_{\text{PC}}$ |  Add${}_{\text{CC}}$ |  Mul${}_{\text{PC}}$ |  Mul${}_{\text{CC}}$
---|---|---|---|---
BGV | 0.049 | 0.077 | 2.055 | 3.379
CKKS | 0.039 | 0.077 | 0.173 | 0.390
TFHE | 56.03 | 256.8 | 1018 | 1585

One reason for addition is of small computational costs, since it yields
relatively few homomorphic additions between plaintext and ciphertext, as
shown in Table 1. We compare with addition (Add${}_{\text{PC}}$) and
multiplication (Mul${}_{\text{PC}}$) between a plaintext and a ciphertext, as
well as addition (Add${}_{\text{CC}}$) and multiplication
(Mul${}_{\text{CC}}$) between two ciphertexts. We compare with four operations
under three popular HE schemes: BGV [3], CKKS [6] and TFHE [7], and it is
evident that the Add${}_{\text{PC}}$ has the smallest latency.

For unidirectional connections, we first resize the feature map of plaintext
branch to fit the addition with ciphertext branch, and then introduce a
channel-rotation for ciphertext channel to extract some information from
multiple plaintext channels. Specifically, suppose there are $L$ layers in
ciphertext and plaintext branches, and denote by $\mathcal{F}_{\text{c},l}$
and $\mathcal{F}_{\text{p},l}$ their respective $l$-th layer. For every
$l\in[L]$, we consider the following two steps:

i) Resizing feature map of plaintext branch

We begin with the resizing function

$\bm{y}_{\text{p},l}=\text{Resize}_{l}(\bm{x}_{\text{p},l})\colon\mathbb{R}^{h_{\text{p},l}\times
w_{\text{p},l}\times\text{ch}_{\text{p},l}}\to\mathbb{R}^{h_{\text{c},l}\times
w_{\text{c},l}\times\text{ch}_{\text{p},l}}$

where $\bm{x}_{\text{p},l}\in\mathbb{R}^{h_{\text{p},l}\times
w_{\text{p},l}\times\text{ch}_{\text{p},l}}$ denotes the output feature maps
from the $l$-th plaintext layer $\mathcal{F}_{\text{p},l}$ with
$h_{\text{p},l}$ rows, $w_{\text{p},l}$ columns and $\text{ch}_{\text{p},l}$
channels, and $h_{\text{c},l}$ and $w_{\text{c},l}$ denote the number of row
and column in ciphertext branch.

For resizing function, a simple yet effective choice is the cropping [32],
which maintains the center features of size $h_{\text{c},l}\times
w_{\text{c},l}\times\text{ch}_{\text{p},l}$ because those features can capture
more important information around the sensitive segment. We can also select
pooling or convolution operations for resizing function [19].

ii) Channel-rotation for ciphertext channel

We now introduce the channel-rotation function as follows:

$\bm{z}_{\text{p},l}=\text{CRot}_{l}(\bm{y}_{\text{p},l})=\left[\text{CRot}^{1}_{l}(\bm{y}_{\text{p},l}),\cdots,\text{CRot}^{i}_{l}(\bm{y}_{\text{p},l}),\cdots,\text{CRot}^{\text{ch}_{\text{c},l}}_{l}(\bm{y}_{\text{p},l})\right]$

where $\text{ch}_{\text{c},l}$ is number of channels in ciphertext branch, and
$\text{CRot}^{i}_{l}(\bm{y}_{\text{p},l})$ denotes the $i$-th channel of
$\text{CRot}_{l}(\bm{x})$, that is,

$\text{CRot}^{i}_{l}(\bm{y}_{\text{p},l})=\sum_{j=1}^{\text{ch}_{\text{p},l}}\bm{W}_{\text{CRot},l}^{i,j}\cdot\bm{y}_{\text{p},l}^{j}\
\ \text{ for }\ \ i\in[\text{ch}_{\text{c},l}]\ .$

Here, $\bm{y}_{\text{p},l}^{j}\in\mathbb{R}^{h_{\text{c},l}\times
w_{\text{c},l}}$ denotes the $j$-th channel of $\bm{y}_{\text{p},l}$ for
$j\in[\text{ch}_{\text{p},l}]$, and
$\bm{W}_{\text{CRot},l}=(\bm{W}_{\text{CRot},l}^{i,j})_{\text{ch}_{\text{c},l}\times\text{ch}_{\text{p},l}}$
is the weight matrix for channel-rotation in the $l$-th layer.

The channel-rotation is helpful for ciphertext channels to extract useful
information automatically from plaintext channels. This is because channel-
rotation could compress, rotate and scale different channels of plaintext
feature maps, without the requirements of channel-wise alignments and
identical numbers and magnitudes of channels. Moreover, each channel, in
connection with ciphertext branch, can be viewed as a linear combination of
multiple plaintext channels, rather than one plaintext channel. Therefore, the
ciphertext branch can get better information from plaintext branch and achieve
better performance with the help of channel-rotation.

After resizing and channel-rotation, the ciphertext branch can make use of
features from plaintext branch by addition. The unidirectional connections can
be written as

$\bm{x}_{\text{c},l+1}=\mathcal{F}_{\text{c},l+1}\left(\bm{x}_{\text{c},l}+\bm{z}_{\text{p},l}\right)=\mathcal{F}_{\text{c},l+1}\left(\bm{x}_{\text{c},l}+\text{CRot}_{l}\left(\text{Resize}_{l}(\bm{x}_{\text{p},l})\right)\right)\
,$

where $\bm{x}_{\text{c},l}\in\mathbb{R}^{h_{\text{c},l}\times
w_{\text{c},l}\times\text{ch}_{\text{c},l}}$ denotes the output feature maps
of $\mathcal{F}_{\text{c},l}$ with $h_{\text{c},l}$ rows, $w_{\text{c},l}$
columns and $\text{ch}_{\text{c},l}$ channels.

Finally, it is feasible to improve computational efficiency by implementing
plaintext and ciphertext branches in parallel, because computing the plaintext
branch and unidirectional connections is much faster than that of ciphertext
branch.

###  3.3 The feature integration

We now design a two-layer neural network to integrate the outputs from
ciphertext and plaintext branches. In the first layer, we split all neurons
into two halves, one half for ciphertext yet the other for plaintext. The
plaintext neurons are only connected with the outputs from plaintext branch,
whereas the ciphertext neurons have full connections. We take full connections
in the second layer.

Specifically, there are $n_{1}$ (even) and $n_{2}$ neurons in the first and
second layer, respectively. Let
$\bm{x}_{\text{c}}\in\mathbb{R}^{n_{\text{c}}}$ and
$\bm{x}_{\text{p}}\in\mathbb{R}^{n_{\text{p}}}$ denote the flattened outputs
from ciphertext and plaintext branches with $n_{\text{c}}$ and $n_{\text{p}}$
features, respectively. Then, the outputs of ciphertext and plaintext neurons
in the first layer can be given by, respectively,

$\displaystyle\bm{x}_{\text{p}}^{\langle
1\rangle}=\sigma(\bm{W}^{\prime}_{\text{p},1}\bm{x}_{\text{p}}+\bm{b}^{\prime}_{1})\
,\quad\bm{x}_{\text{c}}^{\langle
1\rangle}=\sigma(\bm{W}_{\text{c},1}\bm{x}_{\text{c}}+\bm{W}_{\text{p},1}\bm{x}_{\text{p}}+\bm{b}_{1})\
,$

where $\sigma(\cdot)$ is an activation function,
$\bm{b}_{1},\bm{b}^{\prime}_{1}\in\mathbb{R}^{n_{1}/2}$ are bias vectors,
$\bm{W}_{\text{c},1}\in\mathbb{R}^{n_{\text{c}}\times n_{1}/2}$ and
$\bm{W}_{\text{p},1}\in\mathbb{R}^{n_{\text{p}}\times n_{1}/2}$ are the weight
for ciphertext neurons, yet
$\bm{W}^{\prime}_{\text{p},1}\in\mathbb{R}^{n_{\text{p}}\times n_{1}/2}$ is
the weight for plaintext neurons. The final output in the second layer can be
given by

$\bm{x}_{\text{out}}=\sigma(\bm{W}_{\text{c},2}\bm{x}_{\text{c}}^{\langle
1\rangle}+\bm{W}_{\text{p},2}\bm{x}_{\text{p}}^{\langle 1\rangle}+\bm{b}_{2})\
,$

where $\bm{b}_{2}\in\mathbb{R}^{n_{2}}$ is a bias vector, and
$\bm{W}_{\text{c},2}\in\mathbb{R}^{n_{1}/2\times n_{2}}$ and
$\bm{W}_{\text{p},2}\in\mathbb{R}^{n_{1}/2\times n_{2}}$ are the weight
matrices for ciphertext and plaintext neurons, respectively. Here, we consider
two-layer neural network for simplicity, and similar constructions could be
made for deeper neural networks based on the splitting of plaintext and
ciphertext neurons.

##  4 Knowledge Distillation for bi-CryptoNets

Figure 5: The overview of our feature-based knowledge distillation.

Knowledge distillation has been an effective way to improve learning
performance by distilling knowledge from a teacher network [22, 17]. This
section develops a feature-based knowledge distillation for bi-CryptoNets, as
shown in Figure 5. The basic idea is to supplement the representations of two
branches of bi-CryptoNets by imitating a teacher network.

For the teacher network, we learn a classical convolutional neural network
from training data over the entire images without decomposition. Hence, the
teacher network has plentiful connections between different neurons, and
strengthens the intrinsic correlations for better performance.

We learn the representations of our two branches from the corresponding
intermediate representations of teacher network, and also learn the final
outputs of our bi-CryptoNets from that of teacher network. This is partially
motivated from previous knowledge distillations on internal representations
[31].

Specifically, we first pad the output of ciphertext branch with $0$ to match
the size of plaintext output and add them together, as in convolutional neural
network literature [16, 18]. We then train two branches of bi-CryptoNets to
learn teacher’s intermediate representations by minimizing the following loss
function:

$\mathcal{L}_{\text{IR}}(\bm{W}_{\text{T}}^{h},\bm{W}_{\text{c}},\bm{W}_{\text{p}})=\big{\|}\mathcal{F}_{T}^{h}(\bm{x},\bm{W}_{\text{T}}^{h})-\left(\text{Pad}(\mathcal{F}_{\text{c}}(\bm{x},\bm{W}_{\text{c}}))+\mathcal{F}_{\text{p}}(\bm{x},\bm{W}_{\text{p}})\right)\big{\|}^{2}_{2}\
,$ (1)

where $\mathcal{F}_{T}^{h}(\cdot;\bm{W}_{\text{T}}^{h})$ is the first $h$
layers of teacher network of parameter $\bm{W}_{\text{T}}^{h}$, and
$\mathcal{F}_{\text{c}}(\cdot;\bm{W}_{\text{c}})$ and
$\mathcal{F}_{\text{p}}(\cdot;\bm{W}_{\text{p}})$ denote the ciphertext and
plaintext branches of parameter $\bm{W}_{\text{c}}$ and $\bm{W}_{\text{p}}$,
respectively, and $\text{Pad}(\cdot)$ is the zero-padding function.

Here, we denote by $h$ the corresponding $h$-th layer in the teacher network
that has the same output size as plaintext branch’s output. Such loss can help
the sum of outputs from two branches to approximate the teacher’s intermediate
output. In this manner, two branches could obtain stronger representations,
and this makes it much easier for further learning in the following layers of
our bi-CryptoNets.

After training two branches, we then perform knowledge distillation to the
whole network. The student network is trained such that its output is similar
to that of the teacher and to the true labels. Given bi-CryptoNets’ output
$\bm{a}_{S}$ and teacher’s output $\bm{a}_{T}$, we first get softened output
as

$\bm{p}_{T}^{\tau}=\text{softmax}({\bm{a}_{T}}/{\tau})\ \ \text{ and }\ \
\bm{p}_{S}^{\tau}=\text{softmax}({\bm{a}_{S}}/{\tau})\ ,$

where $\tau>1$ is a relaxation parameter. We try to optimize the following
loss function:

$\mathcal{L}_{\text{KD}}(\bm{W}_{\text{T}},\bm{W}_{\text{BCN}})=\mathcal{H}(\bm{y}_{\text{True}},\bm{p}_{s})+\lambda\mathcal{H}(\bm{p}_{T}^{\tau},\bm{p}_{s}^{\tau})\
,$ (2)

where $\bm{y}_{\text{True}}$ is the true label,
$\bm{p}_{s}=\text{softmax}(\bm{a}_{S})$, $\mathcal{H}$ refers to the cross-
entropy, $\bm{W}_{\text{T}}$ and $\bm{W}_{\text{BCN}}$ are the parameters of
teacher network and our bi-CryptoNets, respectively, and $\lambda\in[0,1]$ is
a hyperparameter balancing two cross-entropies. With our proposed method, two
branches in our bi-CryptoNets can learn better representations, enhancing
overall performance. More details can be found in Appendix 0.G.

##  5 Experiments

This section presents empirical studies on datasets333Downloaded from
yann.lecun.com/exdb/mnist and www.cs.toronto.edu/~kriz/cifar MNIST, CIFAR-10
and CIFAR-100, which have been well-studied in previous private inference
studies [4, 27, 25]. We develop different backbones for our bi-CryptoNets
according to different datasets. We adopt the 3-layer CNN [14, 4] as backbone
for MNIST, and we take 11-layer CNN [5], VGG-16 [34] and ResNet-18 [19] for
CIFAR-10 and CIFAR-100. Figure 4 presents our bi-CryptoNets with VGG-16
backbone, and more details are shown in Appendix 0.C.

We take the CKKS scheme for sensitive segment with polynomial degree
$N=2^{14}$, and mingle with Gaussian noise for insensitive segment. We further
improve packing method for our bi-CryptoNets to perform inference for multiple
images simultaneously.

For simplicity, we focus on the regular images, where the area of sensitive
segment is restricted to a quarter in the center of every image, and we could
take some techniques of zooming, stretching and rotating to adjust those
irregular images.

Ablation studies

We conduct ablation studies to verify the effectiveness of feature-based
knowledge distillation and the structures of our bi-CryptoNets. Table 2
presents the details of experimental results of inference accuracies on three
datasets.

We first exploit the influence of feature-based knowledge distillation in our
bi-CryptoNets. We consider two different methods: bi-CryptoNets without
knowledge distillation and bi-CryptoNets with conventional knowledge
distillation. As can be seen from Table 2, it is observable that our feature-
based knowledge distillation could effectively improve the inference accuracy
by $0.54\%\sim 8.39\%$, in comparison to bi-CryptoNets without knowledge
distillation; it also achieves better inference accuracy by $1.45\%\sim
10.27\%$ than that of conventional knowledge distillation, which fails to
stably improve accuracy with our bi-branch structure.

We then study the influence of unidirectional connections in bi-CryptoNets,
and consider two variants: our bi-CryptoNets without unidirectional
connections and bi-CryptoNets with resizing yet without channel-rotations. As
can be seen from Table 2, the unidirectional connections are helpful for
ciphertext branch to extract useful information from plaintext branch. This is
because the unidirectional connections with only resizing can enhance
inference accuracy by $0.13\%\sim 5.40\%$, and it could further improve
accuracy by $0.26\%\sim 5.61\%$ with both resizing and channel-rotations.

We finally compare the inference accuracies of our bi-CryptoNets with the
backbone network, which is trained and tested on the entire input images
without decomposition. From Table 2, it is observable that our bi-CryptoNets
with feature-based knowledge distillation achieves comparable or even better
inference accuracies than the corresponding backbone networks without data
decomposition; therefore, our proposed bi-CryptoNets could effectively
compensate for the information loss of plaintext and ciphertext branches under
the help of feature-based knowledge distillation.

Table 2: The accuracies (%) on MNIST, CIFAR-10 and CIFAR-100 datasets (KD refers to the conventional knowledge distillation; FKD refers to our feature-based knowledge distillation). Models | Knowledge | MNIST | CIFAR-10 | CIFAR-100
---|---|---|---|---
Distillation | CNN-3 | CNN-11 | VGG-16 | ResNet-18 | VGG-16 | ResNet-18
Backbone network (w/o decomposition) | w/o KD | $99.21$ | $90.99$ | $93.42$ | $94.30$ | $72.23$ | $74.00$
bi-CryptoNets | w/o KD | $98.60$ | $81.91$ | $90.36$ | $92.04$ | $64.85$ | $69.46$
bi-CryptoNets | KD | $98.61$ | $80.03$ | $88.91$ | $92.43$ | $64.96$ | $65.67$
bi-CryptoNets (w/o uni. connections) | FKD | $98.89$ | $84.69$ | $91.78$ | $91.73$ | $70.61$ | $70.29$
bi-CryptoNets (w/o channel-rotations) | FKD | $98.90$ | $90.09$ | $92.14$ | $91.86$ | $71.43$ | $71.40$
bi-CryptoNets | FKD | $\mathbf{99.15}$ | $\mathbf{90.30}$ | $\mathbf{93.27}$ | $\mathbf{93.91}$ | $\mathbf{72.35}$ | $\mathbf{73.33}$

Experimental comparisons

We compare our bi-CryptoNets with the state-of-the-art schemes on privacy-
preserving neural networks [8, 20, 4, 27, 9, 25]. We also implement the
structure of backbone network with square activation for fair comparisons. We
take the batch size $20$ and $32$ for MNIST and CIFAR-10, respectively. We
employ commonly-used criteria in experiments, i.e., inference accuracy,
inference latency and the number of homomorphic operations as in [8, 28]. We
also consider the important amortized inference latency in a batch of images
[25], and concern the number of activations for ciphertexts [27, 4, 9]. Tables
3 and 4 summarize experimental comparisons on MNIST and CIFAR-10,
respectively. Similar results could be made for CIFAR-100, presented in
Appendix 0.E.

From Table 3, our bi-CryptoNets can reduce HE operations by $2.35\times$ and
inference latency by $3.43\times$ in contrast to backbone network. Our bi-
CryptoNets could decrease the amortized latency by $13.7\times$, and achieve
better accuracy (about $0.2\%$) than backbone because of our knowledge
distillation and precise inference in the plaintext branch.

From Table 4, our bi-CryptoNets reduces HE operations by $1.43\times$, and
inference latency by $1.15\times$ in contrast to backbone network. Our bi-
CryptoNets could decrease the amortized latency by $4.59\times$ and improve
accuracy by $2.1\%$. We also implement our bi-CryptoNets with VGG-16 and
ResNet-18 as backbones, and deeper networks yield better inference accuracies,
i.e., $93.27\%$ for VGG-16 and $93.91\%$ for ResNet-18.

From Tables 3 and 4, our bi-CryptoNets takes a good balance between inference
accuracies and computation cost in comparison with other neural networks. Our
bi-CryptoNets achieves lower inference latency and amortized latency than
other methods except for LoLa, where light-weight neural network is
implemented with complicated packing method and smaller HE operations. Our bi-
CryptoNets takes relatively-good inference accuracies except for SHE, CryptoDL
and VDSCNN, where deeper neural networks are adopted with larger computational
overhead. Based on deeper backbones such as VGG-16 and ResNet-18, our bi-
CryptoNets could achieve better inference accuracy, comparable inference
latency and smaller amortized latency.

Table 3: The experimental comparisons on MNIST. Scheme | HEOPs | Add${}_{\text{CC}}$ | Mul${}_{\text{PC}}$ | Act${}_{\text{C}}$ | Latency(s) | Amortized Latency(s) | Acc(%)
---|---|---|---|---|---|---|---
FCryptoNets [8] | 63K | 38K | 24K | 945 | 39.1 | 2.0 | 98.71
CryptoDL [20] | 4.7M | 2.3M | 2.3M | 1.6K | 320 | 16.0 | 99.52
LoLa [4] | 573 | 393 | 178 | 2 | 2.2 | 2.2 | 98.95
SHE [27] | 23K | 19K | 945 | 3K | 9.3 | 9.3 | 99.54
EVA [9] | 8K | 4K | 4K | 3 | 121.5 | 121.5 | 99.05
VDSCNN [25] | 4K | 2K | 2K | 48 | 105 | 105 | 99.19
Backbone CNN-3 | 1962 | 973 | 984 | 5 | 7.2 | 1.4 | 98.95
bi-CryptoNets (CNN-3) | 830 | 406 | 418 | 6 | 2.1 | 0.1 | 99.15
Table 4: The experimental comparisons on CIFAR-10. Scheme | HEOPs | Add${}_{\text{CC}}$ | Mul${}_{\text{PC}}$ | Act${}_{\text{C}}$ | Latency(s) | Amortized Latency(s) | Acc(%)
---|---|---|---|---|---|---|---
FCryptoNets [8] | 701M | 350M | 350M | 64K | 22372 | 1398 | 76.72
CryptoDL [20] | 2.4G | 1.2G | 1.2G | 212K | 11686 | 731 | 91.50
LoLa [4] | 70K | 61K | 9K | 2 | 730 | 730 | 76.50
SHE [27] | 4.4M | 4.4M | 13K | 16K | 2258 | 2258 | 92.54
EVA [9] | 135K | 67K | 67K | 9 | 3062 | 3062 | 81.50
VDSCNN [25] | 18K | 8K | 9K | 752 | 2271 | 2271 | 91.31
Backbone CNN-11 | 1.0M | 493K | 521K | 246 | 1823 | 228 | 88.21
bi-CryptoNets (CNN-11) | 709K | 341K | 368K | 246 | 1587 | 49 | 90.30
bi-CryptoNets (VGG-16) | 3.4M | 1.5M | 1.9M | 1.1K | 2962 | 92 | 93.27
bi-CryptoNets (ResNet-18) | 15.5M | 6.9M | 8.6M | 2.8K | 6760 | 211 | 93.91

##  6 Conclusion

Numerous privacy-preserving neural networks have been developed to keep the
balance between accuracy, efficiency and security. We take a different view
from the input data and network structure. We decompose the input data into
sensitive and insensitive segments, and propose the bi-CryptoNets, i.e.,
plaintext and ciphertext branches, to deal with two segments, respectively. We
also introduce feature-based knowledge distillation to strengthen the
representations of our network. Empirical studies verify the effectiveness of
our bi-CryptoNets. An interesting future work is to exploit multiple levels of
privacy of input data and multiple branches of neural network, and it is also
interesting to generalize our idea to other settings such as multi-party
computation.

## Acknowledgements

The authors want to thank the reviewers for their helpful comments and
suggestions. This research was supported by National Key R&D Program of China
(2021ZD0112802), NSFC (62376119) and CAAI-Huawei MindSpore Open Fund.

## References

  * [1] Boemer, F., Costache, A., Cammarota, R., Wierzynski, C.: nGraph-HE2: A high-throughput framework for neural network inference on encrypted data. In: WAHC@CCS. pp. 45–56 (2019)
  * [2] Boulemtafes, A., Derhab, A., Challal, Y.: A review of privacy-preserving techniques for deep learning. Neurocomputing 384, 21–45 (2020)
  * [3] Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory 6(3), 1–36 (2014)
  * [4] Brutzkus, A., Gilad-Bachrach, R., Elisha, O.: Low latency privacy preserving inference. In: ICML. pp. 812–821 (2019)
  * [5] Chabanne, H., Wargny, A., Milgram, J., Morel, C., Prouff, E.: Privacy-preserving classification on deep neural network. Cryptol. ePrint Arch. (2017)
  * [6] Cheon, J., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: ASIACRYPT. pp. 409–437 (2017)
  * [7] Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: Fast fully homomorphic encryption over the torus. J. Cryptol. 33(1), 34–91 (2020)
  * [8] Chou, E., Beal, J., Levy, D., Yeung, S., Haque, A., Fei-Fei, L.: Faster CryptoNets: Leveraging sparsity for real-world encrypted inference. CoRR/abstract 1811.09953 (2018)
  * [9] Dathathri, R., Kostova, B., Saarikivi, O., Dai, W., Laine, K., Musuvathi, M.: EVA: An encrypted vector arithmetic language and compiler for efficient homomorphic computation. In: PLDI. pp. 546–561 (2020)
  * [10] Dathathri, R., Saarikivi, O., Chen, H., Laine, K., Lauter, K., Maleki, S., Musuvathi, M., Mytkowicz, T.: CHET: An optimizing compiler for fully-homomorphic neural-network inferencing. In: PLDI. pp. 142–156 (2019)
  * [11] Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. J. Priv. Confidentiality 7(3), 17–51 (2016)
  * [12] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC. pp. 169–178 (2009)
  * [13] Ghodsi, Z., Jha, N., Reagen, B., Garg, S.: Circa: Stochastic ReLUs for private deep learning. In: NeurIPS. pp. 2241–2252 (2021)
  * [14] Gilad-Bachrach, R., Dowlin, N., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In: ICML. pp. 201–210 (2016)
  * [15] Gong, X., Chen, Y., Yang, W., Mei, G., Wang, Q.: InverseNet: Augmenting model extraction attacks with training data inversion. In: IJCAI. pp. 2439–2447 (2021)
  * [16] Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press (2016)
  * [17] Gou, J., Yu, B., Maybank, S., Tao, D.: Knowledge distillation: A survey. Int. J. Comput. Vis. 129(6), 1789–1819 (2021)
  * [18] Hashemi, M.: Enlarging smaller images before inputting into convolutional neural network: Zero-padding vs. interpolation. J. Big Data 6(1), 1–13 (2019)
  * [19] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: CVPR. pp. 770–778 (2016)
  * [20] Hesamifard, E., Takabi, H., Ghasemi, M.: Deep neural networks classification over encrypted data. In: CODASPY. pp. 97–108 (2019)
  * [21] Hinton, G., Srivastava, N., Krizhevsky, A., Sutskever, I., Salakhutdinov, R.: Improving neural networks by preventing co-adaptation of feature detectors. CoRR/abstract 1207.0580 (2012)
  * [22] Hinton, G., Vinyals, O., Dean, J.: Distilling the knowledge in a neural network. CoRR/abstract 1503.02531 (2015)
  * [23] Huang, G., Liu, Z., Maaten, L., Weinberger, K.: Densely connected convolutional networks. In: CVPR. pp. 2261–2269 (2017)
  * [24] Iandola, F., Moskewicz, M., Ashraf, K., Han, S., Dally, W., Keutzer, K.: SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <1MB model size. CoRR/abstract 1602.07360 (2016)
  * [25] Lee, E., Lee, J., Lee, J., Kim, Y., Kim, Y., No, J., Choi, W.: Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions. In: ICML. pp. 12403–12422 (2022)
  * [26] Li, Z., Li, X., Yang, L., Zhao, B., Song, R., Luo, L., Li, J., Yang, J.: Curriculum temperature for knowledge distillation. In: AAAI. pp. 1504–1512 (2023)
  * [27] Lou, Q., Jiang, L.: SHE: A fast and accurate deep neural network for encrypted data. In: NeurIPS. pp. 10035–10043 (2019)
  * [28] Lou, Q., Lu, W., Hong, C., Jiang, L.: Falcon: Fast spectral inference on encrypted data. In: NeurIPS. pp. 2364–2374 (2020)
  * [29] Radosavovic, I., Kosaraju, R., Girshick, R., He, K., Dollár, P.: Designing network design spaces. In: CVPR. pp. 10425–10433 (2020)
  * [30] Ribeiro, M., Grolinger, K., Capretz, M.: MLaaS: Machine learning as a service. In: ICMLA. pp. 896–902 (2015)
  * [31] Romero, A., Ballas, N., Kahou, S., Chassang, A., Gatta, C., Bengio, Y.: Fitnets: Hints for thin deep nets. In: ICLR (2015)
  * [32] Ronneberger, O., Fischer, P., Brox, T.: U-Net: Convolutional networks for biomedical image segmentation. In: MICCAI. pp. 234–241 (2015)
  * [33] Microsoft SEAL (release 4.0). https://github.com/Microsoft/SEAL (Mar 2022), microsoft Research, Redmond, WA.
  * [34] Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition. CoRR/abstract 1409.1556 (2014)
  * [35] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., Salakhutdinov, R.: Dropout: A simple way to prevent neural networks from overfitting. JMLR 15(1), 1929–1958 (2014)
  * [36] Tan, M., Le, Q.: EfficientNet: Rethinking model scaling for convolutional neural networks. In: ICML. pp. 6105–6114 (2019)
  * [37] Xie, X.R., Yuan, M.J., Bai, X.T., Gao, W., Zhou, Z.H.: On the Gini-impurity preservation for privacy random forests. In: NeurIPS (2023)
  * [38] Yang, K., Yau, J., Fei-Fei, L., Deng, J., Russakovsky, O.: A study of face obfuscation in imagenet. In: ICML. pp. 25313–25330 (2022)
  * [39] Yin, X., Zhu, Y., Hu, J.: A comprehensive survey of privacy-preserving federated learning: A taxonomy, review, and future directions. ACM Comput. Surv. 54(6), 131:1–131:36 (2021)
  * [40] Zagoruyko, S., Komodakis, N.: Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer. In: ICLR (2017)

Supplementary Material (Appendix)

##  Appendix 0.A CKKS Scheme

In this section, we will describe CKKS scheme in more details. CKKS is a HE
scheme that supports fixed-point arithmetic operations on encrypted data. The
ciphertext of the CKKS scheme is an element $\bm{c}\in\mathcal{R}^{2}$, where
$\mathcal{R}$ denotes the polynomial ring
$\mathcal{R}_{p}^{N}=\mathbb{Z}_{p}[x]/(x^{N}+1)$,
$\mathbb{Z}_{p}[x]=\mathbb{Z}/p\mathbb{Z}$, and $p=\prod_{i=1}^{l}q_{i}$ is a
product of $l$ prime numbers, $N$ is the polynomial degree. In CKKS scheme, we
can encrypt $n=N/2$ plaintext in $N/2$ slots of a single ciphertext, and
perform Single Instruction Multiple Data (SIMD) operations at no extra cost.
Let $E(\cdot)$ and $D(\cdot)$ denote the encryption and decryption function
respectively. Let
$\bm{c},\bm{c}_{1},\bm{c}_{2},\bm{c}_{\text{add}},\bm{c}_{\text{mult}},\bm{c}_{\text{rot}}$
denote ciphertext, and $\bm{u}$ denotes a plaintext vector in
$\mathbb{R}^{n}$. CKKS scheme supports following homomorphic operations:

  * •

Homomorphic addition:

$\text{Add}(\bm{c},\bm{u})\to\bm{c}_{\text{add}}\ ,\ \text{ s.t. }\
D(\bm{c}_{\text{add}})=D(\bm{c}_{1})+\bm{u}\ ,$
$\text{Add}(\bm{c}_{1},\bm{c}_{2})\to\bm{c}_{\text{add}}\ ,\ \text{ s.t. }\
D(\bm{c}_{\text{add}})=D(\bm{c}_{1})+D(\bm{c}_{2})\ .$

  * •

Homomorphic multiplication:

$\text{Mult}(\bm{c},\bm{u})\to\bm{c}_{\text{mult}}\ ,\ \text{ s.t. }\
D(\bm{c}_{\text{mult}})=D(\bm{c}_{1})\cdot\bm{u}\ ,$
$\text{Mult}(\bm{c}_{1},\bm{c}_{2})\to\bm{c}_{\text{mult}}\ ,\ \text{ s.t. }\
D(\bm{c}_{\text{mult}})=D(\bm{c}_{1})\cdot D(\bm{c}_{2})\ ,$

where $\cdot$ is the element-wize multiplication between two vectors.

  * •

Homomorphic rotation:

$\text{Rot}(\bm{c},r)\to\bm{c}_{\text{rot}}\ ,\ \text{ s.t. }\
D(\bm{c}_{\text{rot}})=\langle D(\bm{c})\rangle_{r}\ ,$

where $r\in\mathbb{Z}$, $\langle\cdot\rangle_{r}$ denotes cyclically shifting
a vector by $r$ to the left when $r>0$, and shifting by $-r$ to the right when
$r<0$.

Gilad-Bachrach et al. performed single instruction multiple data operations
without additional costs by packing multiple plaintext into one ciphertext for
HE [14]. Specifically, a vector of $N/2$ fixed-point numbers can be packed
into $N/2$ slots of a single ciphertext for CKKS [6], and element-wize
multiplication and addition between two vectors can be performed with only one
HE operation. Such technique has been used to reduce HE computations in
privacy-preserving neural networks, such as packing multiple channels of input
data or multiple neurons into one ciphertext [4, 9].

##  Appendix 0.B Experiment Details

#### Datasets.

We conduct experiments on MNIST, CIFAR-10 and CIFAR-100 datasets. MNIST has
$10$ output classes with $60,000$ training images and $10,000$ testing images,
and each image’s size is $28\times 28\times 1$. CIFAR-10 and CIFAR-100 have
$10$ and $100$ output classes respectively, and both of them consist of
$50,000$ training images and $10,000$ testing images, and each image’s size is
$32\times 32\times 3$.

#### Parameter settings.

Datasets have been preprocessed by image centering, that is, subtracting mean
and dividing standard deviation, and images have been augmented by using the
random horizontal flips and random crops. We also adopt the squared activation
in ciphertext branch and feature integration, since CKKS only supports
homomorphic addition and multiplication. In training, we use Adam optimizer to
train our network with batch size of $256$. We adopt the learning rate of
$0.0001$ with cosine decay. For feature-based knowledge distillation, the
teacher network takes backbone network with ReLU activation and hyper-
parameters $\tau=4$ and $\lambda=0.9$. Our experiments are conducted on the HE
scheme library SEAL [33] on AMD Ryzen Threadripper 3970X at 2.2 GHz with 256GB
of RAM, running the Ubuntu 20.04 operating system.

#### State-of-the-art privacy-preserving neural networks.

  * •

FCryptoNets [8]: A privacy-preserving neural network that leverages sparse
representations in the underlying cryptosystem to accelerate inference. It
develops a pruning and quantization approach that achieves maximally-sparse
encodings and minimizes approximation error. Such approach can reduce the
number of HE operations, and achieve short inference latency.

  * •

CryptoDL [20]: A privacy-preserving neural network with polynomial
activations. It use low degree polynomials to approximate ReLU activations,
and implement deeper networks, achieving better performance in accuracy.

  * •

LoLa [4]: A privacy-preserving neural network with well-designed packing
methods. It can pack one image into several ciphertext, and achieve fast
inference for one single image with much fewer HE operations. On the other
hand, it can only perform inference for one image every time.

  * •

SHE [27]: A privacy-preserving neural network implemented with TFHE scheme. It
use boolean circuit to implement neural network by quantizing network weights
into powers of $2$, and it can support ReLU activation and max pooling.
Therefore, it can reach higher accuracy.

  * •

EVA [9]: A privacy-preserving neural network that implemented by a compiler
for HE with CKKS scheme. The compiler can optimize the hyperparameters and the
computation graph for HE. Therefore, it can decrease the HE computation depth
and shorten the inference latency for private-preserving neural networks.

  * •

VDSCNN [25]: A privacy-preserving neural network implemented with CKKS scheme.
It uses polynomial activations and it also packs multiple channels of the
image into one ciphertext. Therefore, it can perform inference with fewer HE
additions and multiplications.

Figure 6: The structure of our proposed bi-CryptoNets taking 11-layer CNN as
backbone. Figure 7: The structure of our proposed bi-CryptoNets taking
ResNet-18 as backbone.

##  Appendix 0.C Network Architectures

In this section, we will present the structure for other variants of our bi-
CryptoNets in details.

Figure 6 presents the overview structure of our proposed bi-CryptoNets that
takes 11-layer CNN as backbone. Each branch has the following layout: (i) 2
layers of $3\times 3$ convolution with stride of $(1,1)$, padding of $(1,1)$
and 32 output maps; (ii) $2\times 2$ average pooling with $(2,2)$ stride;
(iii) 2 layers of $3\times 3$ convolution with stride of $(1,1)$, padding of
$(1,1)$ and 64 output maps; (iv) $2\times 2$ average pooling with $(2,2)$
stride; (v) 2 layers of $3\times 3$ convolution with stride of $(1,1)$,
padding of $(1,1)$ and 128 output maps; (vi) $2\times 2$ average pooling with
$(2,2)$ stride. We build unidirectional connections after each convolutional
layers in the plaintext branch. Following two branches, we have a 2-layer
feature integration: In the first layer, we have two fully connected layers
with 128 plaintext outputs and 128 ciphertext outputs, respectively; in the
second layer, we have fully connected layer with 10 ciphertext outputs.

Figure 7 presents the overview structure of our proposed bi-CryptoNets that
takes ResNet-18 as backbone. Each branch has the following layout: (i)
$3\times 3$ convolution with stride of $(1,1)$, padding of $(1,1)$ and 64
output maps; (ii) 2 layers of $3\times 3$ convolution with stride of $(1,1)$,
padding of $(1,1)$ and 64 output maps; (iii) skip connection by adding the
outputs from (i) and (ii) together; (iv) $3\times 3$ convolution with stride
of $(2,2)$ and 128 output maps; (v) $3\times 3$ convolution with stride of
$(1,1)$, padding of $(1,1)$ and 128 output maps; (vi) skip connection by a
$3\times 3$ convolution with stride of $(2,2)$ and 128 output maps with (iii)
as input, and adding the results with (v); (vii) $3\times 3$ convolution with
stride of $(2,2)$ and 256 output maps; (viii) $3\times 3$ convolution with
stride of $(1,1)$, padding of $(1,1)$ and 256 output maps; (ix) skip
connection by a $3\times 3$ convolution with stride of $(2,2)$ and 256 output
maps with (vi) as input, and adding the results with (viii); (x) $3\times 3$
convolution with stride of $(2,2)$ and 512 output maps; (xi) $3\times 3$
convolution with stride of $(1,1)$, padding of $(1,1)$ and 512 output maps;
(xii) skip connection by a $3\times 3$ convolution with stride of $(2,2)$ and
512 output maps with (viii) as input, and adding the results with (xi). We
build unidirectional connections after each convolutional layers in the
plaintext branch. After two branches, we have a 2-layer feature integration:
In the first layer, we have two fully connected layers with 256 plaintext
outputs and 256 ciphertext outputs, respectively; in the second layer, we have
fully connected layer with 10 ciphertext outputs.

Figure 8: Homomorphic vector-matrix multiplication.

##  Appendix 0.D Implementation Details

In this section, we will introduce our implementation for bi-CryptoNets with
CKKS scheme in more details. A privacy-preserving neural network mainly
consists of three types of layers: fully connected layer, convolutional layer
and pooling layer.

### Homomorphic fully connected layer

For an input $\bm{x}\in\mathbb{R}^{n_{1}}$, weight matrix
$W\in\mathbb{R}^{n_{1}\times n_{2}}$ and bias vector
$\bm{k}\in\mathbb{R}^{n_{2}}$, the fully connected layer can be written as

$y=\sigma(\bm{x}^{T}W+\bm{k})\ ,$

where $\sigma(\cdot)$ is the activation function.

As shown in Figure 8, we can implement vector-matrix multiplication by
homomorphic rotations and multiplications. The multiplication between $\bm{x}$
and $W$ can be written as

$b_{j}=\sum_{i=1}^{n_{1}}a_{i}w_{i,j}\ \text{ for }\ j\in[n_{2}]\ .$

First, we transform the plaintext weight matrix $W$ into a group of vectors
$w_{i}$, for $i\in[n_{1}+n_{2}-1]$. Then we perform rotations on $\bm{x}$ from
$n_{2}-1$ to $1-n_{1}$ as

$\bm{x}_{i}=Rot(x,n_{2}-i)\ \text{ for }\ i\in[n_{1}+n_{2}-1]\ .$

Next, we homomorphically multiply $x_{i}$ with $w_{i}$ respectively, and sum
the results together. To save calculation depth, we can perform summation in
pairs. This would only lead to $\lceil\log(n_{2})\rceil$ of operation depth.

Finally, after adding bias $\bm{k}$ with prior result and perform activation
function, we can get the output ciphertext of fully connected layers.

Figure 9: Homomorphic convolution of one channel by HW packing with a 2x2
filter.

### Homomorphic convolutional layer

Similar to homomorphic fully connected layer, we can implement the homomorphic
convolutional layer by rotations and multiplications. As shown in Figure 9,
given an input channel $A\in\mathbb{R}^{h\times w}$ and convolution kernel
$f\in\mathbb{R}^{h_{c}\times w_{c}}$, the convolution can be written as

$b_{x,y}=\sum_{i,j}a_{x+i,y+j}f_{i,j}\ \text{ for }\ i\in[h],\ j\in[w]\ .$

For each input channel, it will be flattened into a one-dimensional vector and
packed as a ciphertext. To perform the convolution on ciphertext, we
recursively rotate it and multiply it by corresponding plaintext weight in the
convolution kernel respectively. After adding them together, it will finally
be multiplied by a mask vector, to only keep the values in the slots we need.
We also can compute multiple convolution kernels for multiple input channels
in parallel.

### Homomorphic pooling layer

Similar to prior works in private inference, we adopt sum pooling in our
network. The implementation of pooling layer is similar to that of homomorphic
convolutional layer. Nevertheless, we do not need to multiply weights in
convolution kernels.

### BHW Packing

For inference, we could implement our bi-CryptoNets by packing method for
speed on multiple images simultaneously, motivated by [10]. We introduce the
new BHW packing for our bi-CryptoNets without extra costs, and the basic idea
is to pack multiple segments into one ciphertext for decomposed images.
Specifically, we pack $n$ of $h\times w$ matrices into one ciphertext for a
batch of $n$ images and their sensitive segments with channel $c$, height $h$
and width $w$. It requires $c$ ciphertext for $n$ images with our BHW packing.

Figure 10: A simple demonstration for three packing methods.

Batch packing [14, 8] presents an efficient method for a large number of
images, to pack the same pixels in a batch of images into one ciphertext.
Another relevant HW packing tries to pack one channel of pixels in an image
into one ciphertext [10, 25], which could greatly reduce HE computations and
inference latency for single image.

Figure 10 presents a simple demonstration for three packing methods. Our BHW
packing could achieve low inference latency as that of HW packing over one
single image, and take comparable inference latency as that of batch packing
on multiple images of smaller batch size. This is because our BHW packing
method could pack more segments into one ciphertext for the decomposed images,
and only small sensitive segments are required to be encrypted.

Table 5: The experimental comparisons on CIFAR-100, and abbreviations are similar to Table 3. Scheme | HEOPs | Add${}_{\text{CC}}$ | Mul${}_{\text{PC}}$ | Act${}_{\text{C}}$ | Latency(s) | Amortized Latency(s) | Acc(%)
---|---|---|---|---|---|---|---
VDSCNN [25] | 18K | 8K | 9K | 752 | 3942 | 3942 | 69.43
Backbone CNN-11 | 1.0M | 493K | 521K | 246 | 1829 | 229 | 66.30
bi-CryptoNets with CNN-11 | 709K | 341K | 368K | 246 | 1588 | 49 | 68.78
bi-CryptoNets with VGG-16 | 3.4M | 1.5M | 1.9M | 1.1K | 2969 | 93 | 72.35
bi-CryptoNets with ResNet-18 | 15.5M | 6.9M | 8.6M | 2.8K | 6765 | 212 | 73.33

##  Appendix 0.E Results on CIFAR-100

In this section, we will present our experiment results on CIFAR-100 dataset.
As shown in Table 5, our bi-CryptoNets can achieve similar results on
CIFAR-100 as on CIFAR-10 dataset, since the network structure are similar to
each other. Our bi-CryptoNets with CNN as backbone can could also decrease the
amortized latency by $4.67\times$ and improve accuracy by $2.48\%$ in
comparison with backbone network. Our bi-CryptoNets with VGG-16 and ResNet-18
as backbones still can achieve better inference accuracy, comparable inference
latency and smaller amortized latency.

Table 6: The accuracies(%) on MNIST, CIFAR-10 and CIFAR-100 datasets. Models | MNIST | CIFAR-10 | CIFAR-100
---|---|---|---
CNN-3 | CNN-11 | VGG-16 | ResNet-18 | VGG-16 | ResNet-18
Backbone network without decomposition | $99.21$ | $90.99$ | $93.42$ | $94.30$ | $72.35$ | $74.00$
bi-CryptoNets (Convolution resizing) | $98.96$ | $89.69$ | $92.24$ | $92.05$ | $71.51$ | $70.79$
bi-CryptoNets (Cropping resizing) | $\mathbf{99.15}$ | $\mathbf{90.30}$ | $\mathbf{93.27}$ | $\mathbf{93.91}$ | $\mathbf{72.23}$ | $\mathbf{73.33}$

##  Appendix 0.F Unidirectional Connections

In Section 3.2, we use cropping as resizing function for simplicity. Another
way is to use a convolutional layer with strides as resizing function. In this
section, we will show that cropping is a more effective way.

Similar to the skip connections of ResNet, we can simply use a convolutional
layer as resizing functions. For example, if both the height and width of the
sensitive segment is a half of that of insensitive segment, we can use a
$3\times 3$ convolution with stride of $(2,2)$ as resizing functions. However,
such approach has following disadvantages.

First, extra convolutional layers would introduce more parameters, which would
make the network harder to train, and it would also lead to larger computation
overhead. Second, when using cropping as resizing functions, it can bring
representation from the plaintext branch at similar depth to the corresponding
layers in ciphertext branch, whereas convolutions will bring higher orders
representation to the layers in ciphertext branch. Intuitively, it is more
natural to adding representations from similar depth together, compared with
adding a high-order representation with low-order representation. Finally,
cropping is an easier and more flexible way for resizing feature maps with
various shapes, compared with convolution. Therefore, we simply use cropping
as resizing functions in this paper.

Moreover, to compare the effectiveness of two resizing functions, we conduct
experiments on MNIST, CIFAR-10 and CIFAR-100 with different network
structures. We replace the cropping resizing function in our bi-CryptoNets
with $3\times 3$ convolution by stride of $(2,2)$. We train both networks with
feature-based knowledge distillation, and compare their accuracy. As shown in
table 6, using cropping as resizing function can reach better accuracies in
all datasets and with all variants of bi-CryptoNets structures, which is
consistent with our analysis.

##  Appendix 0.G Visualization for the effectiveness of feature-based
knowledge distillation

In this section, we will show the effectiveness of feature-based knowledge
distillation for bi-CryptoNets by drawing the attention maps at each layer. We
compare our bi-CryptoNets trained by feature-based knowledge distillation with
the teacher network and the bi-CryptoNets trained without knowledge
distillation. Figure 11 presents the attention maps of each layer for bi-
CryptoNets that takes 11-layer CNN as backbone on CIFAR-10 images, and Figure
11 presents the attention maps of each layer for bi-CryptoNets that takes
VGG-16 as backbone. We can observe that the attention maps of bi-CryptoNets
with feature-based knowledge distillation is very close to those of teachers,
whereas bi-CryptoNets without knowledge distillation fails to capture the
important patterns in the images, resulting the wrong predictions. Therefore,
our feature-based knowledge distillation is an effective way to improve the
performance of bi-CryptoNets, so that our bi-CryptoNets can achieve comparable
performance as teacher network.

Figure 11: Attention maps in different layers of teacher network (CNN-11), bi-
CryptoNets with feature-based knowledge distillation and bi-CryptoNets without
knowledge distillation on CIFAR-10 images. Figure 12: Attention maps in
different layers of teacher network (VGG-16), bi-CryptoNets with feature-based
knowledge distillation and bi-CryptoNets without knowledge distillation on
CIFAR-10 images.