\section{Introduction}\label{sec:intro}

Deep Neural Networks (DNNs) have achieved remarkable results in various fields, including image recognition, natural language processing or medical diagnostics.
``Machine Learning as a Service'' (MLaaS) is a recent and popular DNN-based business use-case~\citep{philipp2020machine, li2017scaling, ribeiro2015mlaas},
where clients pay for predictions from a service provider.
However, this approach requires trust between the client and the service provider. In cases where the data is sensitive, such as military, financial, or health information, clients may be hesitant (or are simply not allowed) to share their data with the service provider for privacy reasons. On the service provider's side, training DNNs requires large amounts of data, technical expertise, and computer resources, which can be expensive and time-consuming. As a result, service providers may hesitate to give the model directly to the client, as it may be easily reverse-engineered (or at least make the attacker's task much easier), hindering the growth of MLaaS activity. Allowing the clients to perform the inference locally is also not very practical as any model update would have to be pushed to all clients, not to mention the complex support of the various client hardware/software configurations, etc.

HE/FHE~\cite{gentry2009fully} is an ideal technology to address Privacy-Preserving in Machine Learning (PPML) as it allows the computations to be performed directly on encrypted data. By encrypting its data before sharing it with the service provider, the client ensures that it remains private while the service provider can still provide accurate predictions. This solves the trust issue and also gives a competitive advantage in regions where data regulations are stricter, such as Europe's General Data Protection Regulation (GDPR)~\citep{regulation2016regulation}. The most popular HE schemes are BGV/BFV~\cite{brakerski2014leveled,Brakerski12,FanV12}, CKKS~\cite{cheon2017homomorphic} and Torus-FHE (TFHE)~\cite{chillotti2016faster, chillotti2020tfhe} and this paper presents our proposed solution that utilizes TFHE to provide a privacy-preserving MLaaS framework for DNNs. TFHE enables very fast gate bootstrapping as well as circuit bootstapping and operations over Boolean gates. Moreover, extended versions of TFHE, such as Concrete~\cite{chillotti2020concrete} allows programmable bootstrapping enabling evaluation of certain functions during the bootstrapping step itself.

The security and flexibility provided by HE come at a cost, as the computation, communication, and memory overheads are significant, especially for complex functions such as DNNs:
\vspace*{-0.3cm}
\setlength{\leftmargin}{0cm}
\begin{itemize}
\setlength\itemsep{-0.1em}
    \item Time overhead:
    on server side, an FHE logic gate computation within a TFHE scheme takes milliseconds ~\cite{chillotti2016faster}, compared to nanoseconds for a standard logic gate. On client side the overhead for encryption/decryption of the data is usually not an issue, as milliseconds are enough for those operations.

    \item Communication overhead:
    an MNIST image sent in clear represents a few kBs, while encrypted within any HE scheme it is of the order of a few MBs (excluding the public key which typically requires hundred(s) of MBs)~\cite{clet2021bfv}. Moreover, PPML schemes not based on TFHE, such as those based on CKKS, require a significant communication overhead due to the need for multiple exchanges between the client and the cloud ~\cite{clet2021bfv}.

    \item Memory overhead: TFHE-based schemes typically require a few of MBs of RAM on server side, while those based on CKKS need several GBs per image~\cite{gilad2016cryptonets, brutzkus2019low}, even up to hundreds of GBs for the most time-efficient solutions~\cite{lee2022low} (384GB of RAM usage to infer a single CIFAR-10 image using {\tt ResNet}\xspace).

    \item Technical difficulties and associated portability issues: mastering an HE/FHE framework requires highly technical and rare expertise.

\end{itemize}

These challenges can be approached from different directions, but only a few works have considered designing DNNs models that are compatible/efficient with state-of-the-art HE frameworks in a flexible and portable manner. This paper focuses on the integration of the recent FHE scheme, Torus-FHE (TFHE), with DNNs.

\myparagraph{Our contributions.} To address the above issue, we propose a DNN design framework called {\tt {TT-TFHE}}\xspace that effectively scales TFHE usage to tabular and large datasets using a new family of Convolutional Neural Networks (CNNs) called Truth-Table Neural Networks ({\tt TTnet}\xspace). Our proposed framework provides an easy-to-implement, automated {\tt TTnet}\xspace-based design toolbox that utilizes the Pytorch and Concrete (python-based) open-source libraries for state-of-the-art deployment of DNN models on CPU, leading to fast and accurate inference over encrypted data. The {\tt TTnet}\xspace architecture, being lightweight and differentiable, allows for the implementation of CNNs with direct expressions as truth tables, making it easy to use in conjunction with the TFHE open-source library (specifically the Concrete implementation) for automated operation on lookup tables. Therefore, in this paper, we try to tackle the TFHE efficiency overhead as well as the technical/portability issue.

\myparagraph{Our experimental results.} Evaluation on three tabular datasets (Cancer, Diabetes, Adult) shows that our proposed {\tt {TT-TFHE}}\xspace framework outperforms in terms of accuracy (by up to $+3\%$) and time (by a factor $7$x to $1200$x) any state-of-the-art DNN \& HE set-up. For all these datasets, our inference time runs in a few seconds, with very small memory and communication requirements, enabling for the first time a fully practical deployment in industrial/real-world scenarios, where tabular datasets are prevalent~\cite{cartella2021adversarial,buczak2015survey,clements2020sequential,ulmer2020trust,evans2009online}.

For MNIST and CIFAR-10 image benchmarks, we further explore an approach for private inference proposed by LoLa~\cite{brutzkus2019low}, in which the user/client side is able to compute a first layer and send the encrypted results to the cloud. In this real-world scenario, the user/client performs the computation of a standard public layer (such as the first block of the open-source {\tt VGG16}\xspace model) and sends the encrypted results to the cloud for further computation using HE. Through experimental evaluation, we demonstrate that our proposed framework greatly outperforms all previous TFHE set-ups~\cite{sanyal2018tapas, fu2021gatenet, chillotti2021programmable} in terms of inference time. Specifically, we show that {\tt {TT-TFHE}}\xspace can infer one MNIST image in 7 seconds with an accuracy of 98.1\% or one CIFAR-10 image in 570 seconds with an accuracy of 74\%, which is from one to several orders of magnitude faster than previous TFHE schemes, and even comparable to the fastest state-of-the-art HE set-ups (that do not benefit from the TFHE advantages) while maintaining the same 128-bit security level.

Our solutions represent a significant step towards practical privacy-preserving inference, as they offer fast inference with limited requirements in terms of memory on server side (only a few MBs, in contrary to other non-TFHE-based schemes),  and thus can easily be scaled to multiple users.
In addition, they benefit from lower communication overhead. In other words, this is the first work presenting a fully practical solution of private inference (\textit{i.e.} a few seconds for inference time and a few MBs of memory/communication) on both tabular datasets and MNIST.

\myparagraph{Outline.} In Section~\ref{sec:related}, we present related works in the field of HE and HE-friendly neural networks. In Section~\ref{sec:TT-THE_framewroks}, we introduce our proposed {\tt {TT-TFHE}}\xspace framework, while in Section~\ref{sec:Results} we provide an evaluation of the performance of our framework on various datasets and various privacy settings. Finally, in Section~\ref{sec:Conclusion}, we discuss the limitations of the proposed framework and present our conclusions.

\section{Related Works}\label{sec:related}

A lot of interest has been observed in PPML in the recent past, especially for implementing DNNs. Most of these efforts assume that the (unencrypted) model is deployed in the cloud, and the encrypted inputs are sent from the client side for processing. Inference timing of HE-enabled DNN models is the key parameter, but other factors, such as ease of automation and simplicity of such transformation have also attracted some attention~\cite{nGraph,chet,armadillo}.

Broadly, the problem can be approached from four complementary directions: 1) Optimizing the implementation of some DNN building blocks, such as the activation layers, using HE operations~\cite{jovanovic2022private,lee2022low}; 2) Parallelizing the computation and batching of images~\cite{gilad2016cryptonets,chou2018faster,brutzkus2019low} (this is aided by the ring encoding of HE in certain cases). Such efforts also include implementing a hybrid client-server protocol for computation~\cite{juvekar2018gazelle, mishra2020delphi}; 3) Optimizing the underlying HE operations~\cite{chillotti2016faster, chillotti2021programmable,ducas2015fhew}; 4) Designing a HE-friendly DNN~\cite{sanyal2018tapas,lou2019she,fu2021gatenet}. This fourth category has been relatively less explored and is the main focus of this work.

To the best of our knowledge, the FHE-DiNN paper~\cite{bourse2018fast} was the first to propose a quantified DNN to facilitate FHE operations. Then, the TAPAS framework~\cite{sanyal2018tapas} pushed this strategy further by identifying Binary Neural Networks (BNNs) as effective DNN modeling techniques for HE-enabled inference. This direction has been enhanced later by GateNet~\cite{fu2021gatenet}, which optimizes the BNN models by grouping the channels to reduce the number of gates.

Yet, none of these works actually explored the automation perspectives for optimizing a model itself for HE inference, as they still heavily leverage some manual optimizations concerning the underlying FHE library. {\tt {TT-TFHE}}\xspace, however, is fully automated.
Moreover, compared to previously proposed automated approaches, the translation from non-HE model to HE-enabled model is much simpler as all optimizations are handled during the design phase of the model, making {\tt {TT-TFHE}}\xspace much more amenable for typical machine learning experts with little knowledge of FHE.

\section{{\tt {TT-TFHE}}\xspace Framework}\label{sec:TT-THE_framewroks}

\subsection{Threat model}\label{subsec:TT-THE_Threat}

PPML methods are designed to protect against a variety of adversaries, including malicious insiders and external attackers who may have access to the neural network's inputs, outputs, or internal parameters. The level of secrecy required depends on the specific application and the potential impact of a successful attack. Common secrecy goals include protecting the input to the inference, ensuring that only authorized parties know the result of the inference, and keeping the weights and biases of the neural network secret from unauthorized parties. Some PPML approaches also aim to keep the architecture of the neural network
confidential from unauthorized parties. However, most PPML methods do not address this last point, and some interactive approaches assume that the architecture of the neural network is known to all parties. Moreover, attacks on MLaaS settings exist and are very tricky to defend against ~\cite{tramer2016stealing, juuti2019prada}. Thus, in this paper, we assume that an attacker can access the neural network and only the client's data privacy matters.

\subsection{FHE general set-up}\label{subsec:TT-THE_set-up}

In this paper, the client $\mathcal{C}$ will encrypt its data locally and send it along with its public key to the server $\mathcal{S}$ (there is no need to send it again once it is pre-shared). The server will compute its algorithm on the encrypted data and send the encrypted result to $\mathcal{C}$, who will decrypt its result locally. The server will have no access to the data in clear.

\begin{figure*}[htb!]
    \centering
    \includegraphics[scale=0.50]{fig/FigureICML_v7.pdf}
    \caption{The $N_1/{\tt TT}\xspace$ setting. The client computes locally a layer $N_1$, encrypts the obtained output, and sends it to the server/cloud with the public key (which can be pre-shared). The server will compute through FHE the {\tt TTnet}\xspace layer with the linear regression and send the result to the client. The client can decrypt this output and make a few last computations to obtain the result of the inference. When $N_1$ is identity ($\emptyset/{\tt TT}\xspace$ or more generally $\emptyset/N_2$ for some neural network $N_2$), we denote the setting as Fully Private (Full-Pr).
    }

    \label{fig:global_schema}
\end{figure*}

The classical configuration is that the entire model is computed privately on server side and we call this configuration Fully Private (Full-Pr). However, as it is anyway quite hard to defend against model weight-stealing attacks (our threat model does not include model privacy) and as already proposed by the LoLa team ~\cite{brutzkus2019low}, we also consider situations where the client can perform some local pre-processing (\textit{i.e.} a first layer or block of the neural network) to speed up the server computation without compromising its data security. This setting helps the user to perform its inference faster than in a Full-Pr situation with little memory cost on their side. Such pre-computation would usually be from a public architecture such as {\tt VGG}\xspace, {\tt AlexNet}\xspace or a {\tt ResNet}\xspace~\cite{simonyan2014very,krizhevsky2017imagenet, he2016deep} which are fully available online. In our case, this layer will then typically be followed by a {\tt TTnet}\xspace model and a linear regression that will be computed through FHE on server side. This is a common approach in deep learning, where most models are fine-tuned from one of these three, or with fixed first layers followed by a shallow network.

We will denote $N_1/N_2$ a configuration where the client performs the computation of the neural network $N_1$ locally and the remaining part $N_2$ is performed privately on server side. The final linear regression after $N_2$ is always performed privately on server side, but some of the last few computations can be done by the client (for example a part of the sum and the final $ArgMax$ ~\cite{podschwadt2022survey}). The general setup $N_1/{\tt TT}\xspace$ (where the part performed on server is a {\tt TTnet}\xspace) is depicted in Figure~\ref{fig:global_schema}. $\emptyset/{\tt TT}\xspace$ will represent one extreme case where the entire {\tt TTnet}\xspace neural network is performed privately (Full-Pr) and $N/\emptyset$ will represent the other extreme case where the entire neural network $N$ is performed on client side, except the final linear regression. We will denote ${\tt VGG}\xspace_{1L}$ the first layer of ${\tt VGG16}\xspace$ (the first convolution), and ${\tt VGG}\xspace_{1B}$ its first block (the first two convolutions and the pooling layer afterwards).

\subsection{Truth-table DCNN ({\tt TTnet}\xspace)}\label{subsec:TTmodel}

\begin{figure*}[htb!]
    \centering
\begin{subfigure}[t]{0.55\textwidth}
\scalebox{0.9}{
\begin{tikzpicture}
\foreach \x in {0,...,9}
    \draw[gray, thick] (0 + \x*0.5,0.5) rectangle (0.5 + \x*0.5,1);

\foreach \y in {0,...,3}
    \foreach \x in {0,...,3}
        \draw[gray, thick] (5.5 + \x*0.5,1 - \y) rectangle (6+ \x*0.5,1.5- \y);

\foreach \x in {0,1}
    \draw[gray,thick] (8.5+\x*0.5,0.9) rectangle (9+\x*0.5,1.4);

\draw[darkseagreen2, thick] (5.35 + 0*0.5,1-3.15) rectangle (6.65,1.65);

\draw[green, thick] (8.35+0*0.5,1.5) rectangle (9.15+0*0.5,0.8);
\draw[darkseagreen2, densely dashed] (5.5 + 1*0.5,1.65+0.0) -- (8.5+0*0.5,0.6+0.9);
\draw[darkseagreen2, densely dashed] (5.5 + 1*0.5,1-3.15) -- (8.5+0*0.5,-0.1+0.9);
\draw[darkseagreen2, densely dashed] (-0.1+ 3*0.5,0.6+0.5) -- (5.5,1.65);
\draw[darkseagreen2, densely dashed] (0.1 + 3*0.5,-0.1+0.5) -- (5.35+0*0.5,1-3.15);
\draw[darkseagreen2, thick] (-0.1,0.65-0.2) rectangle (0.1 + 6*0.5,1.1);

\draw [decorate,decoration={brace,amplitude=5pt,raise=1ex}]
  (-0.1,0.9) -- (0.1 + 6*0.5,0.9) node[midway,yshift= 2em]{Patch Size};

\draw[orange, thick] (0 + 0*0.5,0.55) rectangle (0.5 + 3*0.5,1.05);
\draw[orange, thick] (5.45 + 0*0.5,1 - 0.05) rectangle (6.05+ 0*0.5,1.5+ 0.05);
\draw[orange, densely dashed] (0,0.25+0.5) -- (5.5,1.25);
\draw[orange, densely dashed] (0+4*0.5,0.25+0.5) -- (5.5+0.5,1.25);

\draw[blue, thick] (1 + 0*0.5,0.5-0.1) rectangle (1.5 + 3*0.5,1.0);
\draw[blue, thick] (6 + 0*0.5,1 - 0) rectangle (6.5+ 0*0.5,1.5+0.07);
\draw[blue, densely dotted] (1,0.25+0.5) -- (6,1.25);
\draw[blue, densely dotted] (1+4*0.5,0.25+0.5) -- (6+0.5,1.25);

\draw[black, fill=black] (0, -0.5) rectangle (0 + 6*0.5,0) node[pos=0.5,text=white] {Truth Table, x};

\foreach \x in {0,...,5}
    \draw[gray, thick] (0 + \x*0.5,-0.5-1*0.5) rectangle (0.5 + \x*0.5,-0.-1*0.5) node[pos = 0.5, black] {0};
\foreach \x in {1,...,5}
    \draw[gray, thick] (0 + \x*0.5,-0.5-2*0.5) rectangle (0.5 + \x*0.5,-0.-2*0.5) node[pos = 0.5, black] {0};
\draw[gray, thick] (0 + 0*0.5,-0.5-2*0.5) rectangle (0.5 + 0*0.5,-0.-2*0.5) node[pos = 0.5, black] {1};
\draw[gray, thick] (0 + 0*0.5,-0.5-3*0.5) rectangle (0.5 + 0*0.5,-0.-3*0.5) node[pos = 0.5, black] {0};
\foreach \x in {2,...,5}
    \draw[gray, thick] (0 + \x*0.5,-0.5-3*0.5) rectangle (0.5 + \x*0.5,-0.-3*0.5) node[pos = 0.5, black] {0};
\draw[gray, thick] (0 + 1*0.5,-0.5-3*0.5) rectangle (0.5 + 1*0.5,-0.-3*0.5) node[pos = 0.5, black] {1};
\foreach \y in {4}
\foreach \x in {0,...,5}
    \draw[gray, thick] (0 + \x*0.5,-0.5-\y*0.5) rectangle (0.5 + \x*0.5,-0.-\y*0.5) node[pos = 0.5, black] {...};
\foreach \y in {5,6}
    \foreach \x in {0,...,4}
        \draw[gray, thick] (0 + \x*0.5,-0.5-\y*0.5) rectangle (0.5 + \x*0.5,-0.-\y*0.5) node[pos = 0.5, black] {1};
\draw[gray, thick] (0 + 5*0.5,-0.5-5*0.5) rectangle (0.5 + 5*0.5,-0.-5*0.5) node[pos = 0.5, black] {0};
\draw[gray, thick] (0 + 5*0.5,-0.5-6*0.5) rectangle (0.5 + 5*0.5,-0.-6*0.5) node[pos = 0.5, black] {1};

\draw[black, fill=black] (8.35, -0.5) rectangle (9.15,0.0) node[pos=0.5,text=white] {$\Phi_F$};
\draw[gray, thick] (8.35,-0.5-1*0.5) rectangle (9.15,-0-1*0.5) node[pos = 0.5, black] {1};
\draw[gray, thick] (8.35,-0.5-2*0.5) rectangle (9.15,-0.-2*0.5) node[pos = 0.5, black] {1};
\draw[gray, thick] (8.35,-0.5-3*0.5) rectangle (9.15,-0.-3*0.5) node[pos = 0.5, black] {0};
\draw[gray, thick] (8.35,-0.5-4*0.5) rectangle (9.15,-0.-4*0.5) node[pos = 0.5, black] {...};
\draw[gray, thick] (8.35,-0.5-5*0.5) rectangle (9.15,-0.-5*0.5) node[pos = 0.5, black] {0};
\draw[gray, thick] (8.35,-0.5-6*0.5) rectangle (9.15,-0.-6*0.5) node[pos = 0.5, black] {1};
\end{tikzpicture}
}
    \caption{Converting a function $\Phi_F$ into a truth table. The above example has two layers: the first one has parameters (input channel, output channel, kernel size, stride) = $(1,4,4,2)$, while the second $(4,1,2,2)$. The patch size (the patch being the region of the input that produces the feature, which is commonly referred to as the receptive field~\cite{araujo2019computing}) of $\Phi_F$ is $6$ (i.e., \textcolor{darkseagreen2}{green} box) since the output feature (i.e., \textcolor{green}{light green} box) requires $6$ input entries (i.e., \textcolor{orange}{orange} and \textcolor{blue}{blue} box).}
    \label{fig: Amplification Layer}
\end{subfigure}
\hspace{0.8cm}
\begin{subfigure}[t]{0.35\textwidth}
\begin{tikzpicture}
\foreach \x in {0,...,5} {
    \draw[rounded corners] (0+ \x, 0) rectangle (0.5+\x, 4);
    \draw[->] (0.5+ \x -1, 2) -- (1+\x-1, 2); }
\path (0, 0) -- node[rotate=90,anchor=center] {Conv1D}(0.5, 4);
\path (0+1, 0) -- node[rotate=90,anchor=center] {Batch Normalization 1D}(0.5 + 1, 4);
\path (0+2, 0) -- node[rotate=90,anchor=center] {SeLU}(0.5+2, 4);
\path (0+3, 0) -- node[rotate=90,anchor=center] {Conv1D (kernel size = 1)}(0.5+3, 4);
\path (0+4, 0) -- node[rotate=90,anchor=center] {Batch Normalization 1D}(0.5+4, 4);
\path (0+5, 0) -- node[rotate=90,anchor=center] {$bin_{act}$}(0.5+5, 4);
\end{tikzpicture}
    \caption{LTT overview of a Expanding AutoEncoder LTT in 1 dimension: the Conv1D with kernel size = 1 is the amplification layer. The intermediate values are real and the input/output values are binary.}
    \label{fig:LTTAutoEncoder}
\end{subfigure}
\caption{A Learning Truth Table (LTT) block. The intermediate values and weights are floating points, input/output values are binary.
}
\label{fig: inner and outer Learning Truth Table Block}
\end{figure*}

Truth Table Deep Convolutional Neural Networks ({\tt TTnet}\xspace) were proposed in~\cite{https://doi.org/10.48550/arxiv.2208.08609} as DCNNs convertible into truth tables by design, with security applications (a companion video is provided by the authors \href{https://youtu.be/loGlpVcy0AI}{https://youtu.be/loGlpVcy0AI}). While recent developments in DNN architecture have focused on improving performance, the resulting models have become increasingly complex and difficult to verify, interpret and implement. Thus, the authors focused on CNNs, which are widely used in the field, and tried to transform them into tractable Boolean functions. A depiction of the general architecture of {\tt TTnet}\xspace can be found in Figure~\ref{fig:General_archi} of Appendix~\ref{appendix:architecture}.

\myparagraph{CNN filter as a tractable Boolean function.} Their proposed method converts CNN filters into binary truth tables by 1) decreasing the input size (noted as $n$ in the rest of the paper) which reduces the complexity of the CNN filter function, 2) using the Heaviside step function denoted as $bin_{act}=(1+sgn(x))/2$ to transform the inputs and outputs into binary values. This results in a tractable Boolean function (for $n$ not too large) that can be stored as a truth table, as seen in Figure~\ref{fig: Amplification Layer}. To achieve high accuracy, the CNN filter must also be non-linear before the step function. Then, the CNN filter becomes a tractable non-linear truth table, which is referred to as a Learning Truth Table (LTT) block.

\myparagraph{Description of an LTT block.} Among all the families of LTT blocks possible - we represent in Figure~\ref{fig:LTTAutoEncoder} an Expanding Auto-Encoder LTT block (E-AE LTT). An E-AE LTT block is composed of two layers of grouped CNN with an expanding factor. Figure~\ref{fig: Amplification Layer} shows a computation of E-AE 1D LTT block. We can observe that the input size is small ($n =6$), the input/output values are binary and SeLU is an activation function. Note that the inputs are binary but the weights and the intermediate values are real. We integrated LTT blocks into $\mathcal{TT}$net as CNN filters are integrated into DCNNs: each LTT layer is composed of multiple LTT blocks and there are multiple LTT layers in total.

\subsection{Challenges and optimizations for integrating {\tt TTnet}\xspace with TFHE-Concrete}\label{subsec:Challenges}

The Concrete library~\cite{chillotti2020concrete} is a software implementation of TFHE. It is designed to provide a highly efficient and secure platform for performing mathematical operations on Boolean encrypted data. The library utilizes automated operations on lookup tables (concrete-numpy) to achieve high performance while maintaining a high level of security. The library is also designed to be very user-friendly, with simple and intuitive interfaces for performing encryption and decryption operations. The Concrete library has been shown to provide significant improvements in terms of memory and communication overheads compared to other HE schemes. Furthermore, it is open source, which allows researchers and practitioners to easily integrate it into their projects and benefit from its advanced features.

The use of {\tt TTnet}\xspace architecture in combination with TFHE (and more specifically with Concrete) naturally provides a number of advantages. Firstly, the lightweight and differentiable nature of {\tt TTnet}\xspace allows for the implementation of CNNs with direct expressions as truth tables, which is well-suited for Concrete. Additionally, the reduced complexity of the {\tt TTnet}\xspace architecture leads to reduced computations and good scalability. Yet, the integration of {\tt TTnet}\xspace into the TFHE framework presents several challenges that need to be addressed in order to achieve high performance. We detail below the constraints imposed by FHE libraries and the optimizations implemented to overcome these limitations and achieve state-of-the-art performance on various datasets.

\myparagraph{Constraints imposed by Concrete.} The Concrete implementation of the TFHE library, which utilizes automated operations on lookup tables, imposes a maximum limit of $16$ on the input bit size $n$ of the truth table. However, $n$ has a strong impact on efficiency (cf Appendix~\ref{appendix:concrete}) and our tests show that $n=4$ or $n=6$ seem to offer the best trade-offs. Indeed, since we learn kernels of convolutional layers of size $(3,2)$ or $(2,3)$, it is convenient to use $n$ a multiple of $2$ and/or $3$. Moreover, input sizes larger than $n=8$ lead to a prohibitive average time per call.

Concrete proposes a built-in linear regression feature, but we tested that it performs not as well as an ad-hoc linear regression with multiplications and additions.

Finally, a very important limitation is that Concrete does not support multi-precision table lookups: the call time of each table lookup (even the small ones) will be equal to the call time of the largest bitwidth operations in the whole circuit. For example, if one of the computations operates on 16 bits, all lookup tables, even small, will require the call time of a 16-bit table lookup. This can be problematic when handling the final linear regression as we will have to sum many Boolean values and the sum result bitwidth might be larger than our planned table lookup size, therefore slowing down our entire implementation. If the sum result of our linear regression requires 16 bits, all our $4$-bit lookup tables call time will be on par with $16$-bit table lookups, going from $75$ms to almost $5$s per call. For now, the computation time is too slow for results that require a sum on more than 4 bits. To overcome this limitation, we implemented several optimizations to improve the accuracy of the model, particularly for image datasets (see below).

\myparagraph{Limitations imposed by {\tt TTnet}\xspace.} The original {\tt TTnet}\xspace paper proposed a training method that is not suitable for high  accuracy performance as it was trained to resist PGD attacks~\citep{madry2017towards}, which reduces accuracy. Additionally, the pre-processing and final sparse layers in {\tt TTnet}\xspace being binary, this also leads to a significant decrease in accuracy. To address these limitations, we replace the final sparse binary linear regression with a linear layer with floating point weights (later quantified on 4 bits not to deteriorate too much the performances on Concrete) and propose a new training method that emphasizes accuracy (see below). We also propose to use a setting $N_1/{\tt TT}\xspace$, where a first layer $N_1$ (a layer or block of a general open-source model) is applied to overcome the loss of information due to the first binarization. This is for example a standard method used in BNNs.

\myparagraph{Training optimizations.} To improve the accuracy of our model, we took several steps to optimize the training process. First, we removed the use of PGD attacks during training, as they have been shown to reduce accuracy. Next, we employed the DoReFa-Net method~\cite{zhou2016dorefa} for CIFAR-10, a technique for training convolutional neural networks with low-bitwidth activations and gradients. Finally, to overcome the limitations of the {\tt TTnet}\xspace grouping method, we extended the training to 500 epochs, resulting in a more accurate model.

\myparagraph{Architectural optimizations.} For tabular datasets, the straightforward enhancements proposed in the previous sections are sufficient to achieve high accuracy. However, this is not the case for image datasets such as MNIST, CIFAR-10, and ImageNet. Therefore, we modify the general architecture of our model. Specifically, we use an architecture similar to the one presented for ImageNet in the original {\tt TTnet}\xspace paper. The limitation of our model is that it can see far in the spatial dimension but has limited representation in the channel dimension. To balance this property, we use three techniques: multi-headers
, residual connections~\cite{he2016deep}, and channel shuffling~\cite{zhang2018shufflenet}. We have a single layer composed of four different functions in parallel: one LTT block with a kernel size of (3,2) and group 1 (to see far in space and low in channel), one LTT block with a kernel size of (2,3) and group 1, one LTT block with a kernel size of 1 and 6 groups (to see low in space but high in channel representation), and an identity function (as a residual connection for stability). We tried with a second layer to increase accuracy, but with the current version of Concrete (without the support of multi-precision table lookups), this led to sub-optimal performance/accuracy trade-offs with a drastic increase in FHE inference time.

\myparagraph{Client server usage as optimizations.} We describe here a solution to the issue of Concrete not supporting the results of linear regression that would be on more than 4 bits: we utilize the client's computing resources not only to prepare the input to the server, but also to post-process the server's output. Namely, the client will compute a small part of the final linear regression. Indeed, we quantify the weights of the final linear regression of {\tt TTnet}\xspace to 4 bits, which we divide into 4 binary matrices. Then, the server performs partial sums on each of these 4 matrices. Since the outputs of {\tt TTnet}\xspace are binary, the weights are binary, and the maximum number input bitwidth for our lookup tables is 4 bits. For optimal performance, we perform sub-sums of size 16 to ensure that the result of each sub-sum is always lesser than $2^4$ as proposed by Zama's team\footnote{\href{https://community.zama.ai/t/load-model-complex-circuit/369/4}{https://community.zama.ai/t/load-model-complex-circuit/369/4}}. It is important to note that by doing this, we maintain the privacy of the weights of the linear regression as they remain unknown to the client. Additionally, the function computation by the client is very light, for example in the case of the MNIST dataset in the ${\tt VGG}\xspace_{1B}$/${\tt TT}\xspace$ setting, it will represent at most $\frac{N_\text{features}}{N_{bits}} = \frac{576}{16} = 12$ sums of 4-bit integers to be performed for each $4$ weight matrices. The client will eventually add these four outputs to obtain its final result, \textit{i.e.} computing $\sum_{i=0}^{3}{2^i*w_i * \text{output}_i}$. Also, note that this client computation is fixed and will remain the same even if the model needs to be updated. Finally, this limitation is due to Concrete and likely temporary as Concrete identified lookup tables multi-precision as an ``important feature to come''\footnote{\href{https://community.zama.ai/t/load-model-complex-circuit/369/4}{https://community.zama.ai/t/load-model-complex-circuit/369/4}}.

\myparagraph{Patching optimizations.} Due to its highly decoupled nature, our model performance is dependent on the number of patches. The classification of an image can be viewed as $N$ independent computations, where $N$ is the number of patches of the original image. This is a unique property and is highly useful for addressing the issue of Concrete requiring a lot of RAM when compiling complex circuits, especially when one will have to scale to larger datasets. For example on MNIST, we have a patch of size (8x8x1) instead of an entire image of size (28x28x1).

\section{Results}
\label{sec:Results}

The project implementation was done in Python, with the PyTorch library~\cite{paszke2019pytorch} for training, in numpy for testing in clear, and the Concrete-numpy library for FHE inference.
Our workstation consists of 4 Nvidia GeForce 3090 GPUs (only for training) with 24576 MiB memory and eight cores Intel(R) Core(TM) i7-8650U CPU clocked at 1.90 GHz, 16 GB RAM. For all experiments, the CPU Turbo Boost is deactivated and the processes were limited to using four cores.

The details of all our models' architecture can be found in Appendix~\ref{appendix:models_architecture}.

\subsection{Tabular datasets}
\label{subsec:Tabular}

\begin{table}[htb!]
\medskip
\caption{\label{table:Results_tabular} Tabular dataset results for {\tt {TT-TFHE}}\xspace and competitors. All results are in Full-Pr setting. All our models use a table lookup bitwidth of $n=5$, except for Diabetes where we use $n=6$. \strut}
\resizebox{\columnwidth}{!}{
\begin{tabular}{|l|c|c|cc|cc|cc|}
\cline{2-9}
       \multicolumn{1}{c|}{}  & \textbf{FHE}   & \#CPU        & \multicolumn{2}{c|}{\textbf{Adult}} & \multicolumn{2}{c|}{\textbf{Cancer}} & \multicolumn{2}{c|}{\textbf{Diabetes}} \\ \cline{4-9}
                     \multicolumn{1}{c|}{}   &  \textbf{family} &  \textbf{cores}                       & Acc. & Time & Acc.  & Time  & Acc.  & Time  \\ \midrule
                    ETHZ/CCS22 & CKKS   & 64               & 81.6\%           & 420s      & -              & -         & -               & -          \\ \hline
TAPAS & \multirow{2}{*}{TFHE} & 16 & -              & -        & 97.1\%           & 3.5s       & 54.9\%            & 250s        \\
\textbf{Ours}              &                    & 4   & 85.3\%           & 5.6s      & 97.1\%           & 1.9s       & 57.0\%            & 1.2s        \\  \bottomrule
\end{tabular}}
\end{table}

Our experimental results shown in Table~\ref{table:Results_tabular} (in Table~\ref{table:Results_tabular_normalized} of Appendix~\ref{appendix:singleCPU} for results normalized to a single CPU) demonstrate the superior performance of the proposed {\tt {TT-TFHE}}\xspace framework on three tabular datasets (Cancer, Diabetes, Adult) in terms of both accuracy and computational efficiency. The framework achieved an increase in accuracy of up to $+3\%$ compared to state-of-the-art DNN \& HE set-ups based on TFHE such as TAPAS~\cite{sanyal2018tapas} or on CKKS such as the recent work from the ETHZ team~\cite{jovanovic2022private}. More impressively, the inference time per CPU was significantly reduced by a factor $1205$x, $7$x, and $825$x on Adult, Cancer, and Diabetes datasets respectively.

This enables the practical deployment of our framework in industrial and real-world scenarios where tabular datasets are prevalent ~\cite{cartella2021adversarial,buczak2015survey,clements2020sequential,ulmer2020trust,evans2009online}, with low memory and communication overhead (see Table~\ref{table:Results_Memory} in Appendix~\ref{appendix:RAM_usage}). Note that these results are in the Full-Pr setting, as the binarization process in {\tt {TT-TFHE}}\xspace does not lead to any particular issue for tabular datasets.

\subsection{Image datasets}
\label{subsec:Image}

Our experimental results and comparisons for image datasets are given in Table~\ref{table:Results_image} (in Table~\ref{table:Results_image_normalized} of Appendix~\ref{appendix:singleCPU} for all results normalized to a single CPU).

\begin{table}[htb!]
\vspace*{-0.3cm}
\caption{\label{table:Results_image} Image dataset results for {\tt {TT-TFHE}}\xspace and competitors. Results denoted with * are estimated by the original authors, not measured. All our models use a table lookup bitwidth of $n=4$, except the underlined ones that use $n=6$. \strut}

\medskip

\resizebox{\columnwidth}{!}{
\begin{tabular}{ll|cccc|c|cc|c|}
\cline{3-10}
\multicolumn{2}{c|}{}   &                                  \multicolumn{4}{c|}{Full-Pr ($\emptyset$/$N$)} & ${\tt VGG}\xspace_{1B}$/$\emptyset$ & \multicolumn{2}{c|}{${\tt VGG}\xspace_{1L}$/$N$} & ${\tt VGG}\xspace_{1B}$/$N$ \\ \cline{3-10}
\multicolumn{2}{c|}{\textbf{TFHE-based schemes}}  & TAPAS & GateNet & Zama & \textbf{Ours} & \textbf{Ours} & Zama & \textbf{Ours} & \textbf{Ours} \\
\multicolumn{2}{c|}{\#CPU cores}  & 16 & 2 & 6 & 4 & 4 & 128 & 4 & 4 \\\hline
\multicolumn{1}{|l}{\multirow{2}{*}{\textbf{MNIST}}}    & Acc. (\%) &  98.6 & 98.8* & 97.1 & \underline{97.2} &  97.5  & -   & 98.2 & 98.1 \\
\multicolumn{1}{|l}{}                          & Time      &  37h & 44h* & 115s & \underline{83.6s} & 0.04s  & - & 8.7s   & 7s \\ \hline
\multicolumn{1}{|l}{\multirow{2}{*}{\textbf{CIFAR-10}}} & Acc. (\%) & - & 80.5* & - & - & 70.4  & 62.3   & 69.4/\underline{72.1}  & 74.1/\underline{75.3}  \\
\multicolumn{1}{|l}{}                          & Time      & - & 3920h* & - & - & 0.4s & 29m & 9.5m/\underline{6.2h} & 9.5m/\underline{6.2h} \\ \hline
\end{tabular}}

\medskip

\resizebox{\columnwidth}{!}{
\begin{tabular}{ll|ccccc|}
\cline{3-7}
\multicolumn{2}{c|}{}                                     & \multicolumn{5}{c|}{Full-Pr ($\emptyset$/$N$)} \\ \cline{3-7}
\multicolumn{2}{c|}{\textbf{non-TFHE-based schemes}}  & CryptoNets & Fast CryptoNets & \:\:\:\: SHE \:\:\:\:           & \:\:\:\: Lola \:\:\:\:       &  Lee \textit{et. al.} \\
\multicolumn{2}{c|}{\#CPU cores}  & 4 & 6 & 10           & 8       &  1 \\\hline
\multicolumn{1}{|l}{\multirow{2}{*}{\textbf{MNIST}}}    & Acc. (\%) & 99          & 98.7            & 99.5          & 99.0        & -             \\
\multicolumn{1}{|l}{}                          & Time      & 4.2m  & 39s      & 9.3s   & 2.2s  & -     \\ \hline
\multicolumn{1}{|l}{\multirow{2}{*}{\textbf{CIFAR-10}}} & Acc. (\%) & -           & 76.7            & 92.5          & 74.1        & 91.3  \\
\multicolumn{1}{|l}{}                          & Time      &  -           & 11h      & 37.6m  & 12.2m & 37.8m   \\ \hline
\end{tabular}}

\end{table}

\subsubsection{Fully private (Full-Pr) setting}
\label{subsubsec:Fullyprivate}

In the Full-Pr configuration, we focused on the performance of our method on the MNIST dataset, as the binarization process in {\tt {TT-TFHE}}\xspace resulted in a significant loss of accuracy for CIFAR-10 or an increase in inference time. {\tt {TT-TFHE}}\xspace offers a competitive trade-off compared to other TFHE-based methods, such as TAPAS~\cite{sanyal2018tapas}, GateNet~\cite{fu2021gatenet} or Zama~\cite{chillotti2021programmable}. It is three orders of magnitude faster than TAPAS or GateNet, while showing only a slightly lower accuracy of 1.4\%. In comparison to Zama, our method is $2$x faster per CPU for the same level of accuracy. Additionally, we highlight that for our single layer LTT block of size $n=6$, we require 1600 calls to $6$-bit lookup tables, which leads to an inference time of only 83 seconds on four CPU cores.

{\tt {TT-TFHE}}\xspace is even competitive in terms of inference time with some non-TFHE-based schemes such as (Fast) CryptoNets~\cite{gilad2016cryptonets}, but can be one order of magnitude slower with slightly lower accuracy. Therefore, one can observe that the Full-Pr setting of TFHE implemented in our framework generally underperforms compared to the very latest Full-Pr CKKS or BFV setups. This is explained by the first binarization process in {\tt {TT-TFHE}}\xspace, which compresses too much information embedded in the input image. Yet, we again emphasize the many advantages of TFHE-based solutions compared to non-TFHE-based ones: little memory required allowing easy/efficient multi-client inference, low communication overhead, no security warning on TFHE while CKKS secret key can be recovered in polynomial time~\cite{li2021security} (a fix was proposed afterward ~\cite{li2022securing} but not yet implemented in SEAL for example), etc. We will see in the next sub-section that the performance situation is very different in the setting where the client can perform some pre-computation layer.

\subsubsection{Other settings}
\label{subsubsec:PublicLayer}

We first observe that when allowing the client to apply a simple pre-processing layer, the performance increases drastically for {\tt {TT-TFHE}}\xspace. We have implemented and benchmarked both ${\tt VGG}\xspace_{1L}/{\tt TT}\xspace$ and ${\tt VGG}\xspace_{1B}/{\tt TT}\xspace$ settings, both with {\tt TTnet}\xspace models with $n=6$ and $n=4$ and we obtained a $10$x performance improvement, with an increase in accuracy. For reference, we have also tested the ${\tt VGG}\xspace_{1B}/\emptyset$ setting where only a linear regression is computed privately on server: we remark that adding a {\tt TTnet}\xspace in the server computation indeed improves accuracy by about 4\%.

One could argue that more {\tt VGG}\xspace blocks could be computed on client side to further increase the accuracy, but this would reduce the generality of the first layers and lead to PPML solutions that would not adapt very well to multiple use cases. We have tried blocks of other more recent CNNs than {\tt VGG}\xspace, such as {\tt DenseNet}\xspace ~\cite{huang2017densely}, but the results remain very similar.

We can compare the {\tt {TT-TFHE}}\xspace results to some TFHE-based competitors, as Zama proposed a similar setting \footnote{\url{https://github.com/zama-ai/concrete-ml/tree/release/0.6.x/use_case_examples/cifar_10_with_model_splitting}} with ${\tt VGG}\xspace_{1L}$ pre-computed by the client for CIFAR-10, and against which we infer $100$x faster per CPU and with a $10\%$ increase in accuracy.

Our {\tt {TT-TFHE}}\xspace results are now even competitive against non-TFHE-based solutions (even though they miss many of TFHE advantages), being faster than (Fast) CryptoNets~\cite{gilad2016cryptonets} and SHE~\cite{lou2019she}, and on par with Lola~\cite{brutzkus2019low} and Lee \textit{et. al.}~\cite{lee2022low} per CPU. We note that SHE and Lee \textit{et. al.} have better accuracy than our model.

\subsection{Memory/communication cost of {\tt {TT-TFHE}}\xspace}
\label{subsubsec:Memory}

In Table~\ref{table:Results_Memory} from Appendix~\ref{appendix:RAM_usage}, we compare the memory and communication needs for all our settings. We can observe that the deeper the representation, the smaller the communication needs: the inputs to the server become smaller as we go deeper into the neural network (there are also fewer computations to do in the server). Some settings do not need public keys as only a linear regression is done, and thus no programmable bootstrapping is involved~\cite{chillotti2021programmable}. Then, the largest the lookup tables (in terms of the number of features and size), the larger will be the public keys as there will be more bootstrapping. Also, the optimization proposed in Section~\ref{subsec:Challenges} to ease the linear regression comes with a cost: it increases the size of the outputs. Indeed, only the ${\tt VGG}\xspace_{1B}$/$\emptyset$ setting does not use this optimization as there is no lookup-table involved and thus no bootstrapping. Finally, the encrypted inputs size increases with the number of features.

\myparagraph{Comparison with other methods.} As stated in~\cite{clet2021bfv}, CKKS is more memory greedy than TFHE for communication. In Table~\ref{table:RAM_methods} of Appendix~\ref{appendix:RAM_usage}, we compare between each method the amount of RAM needed on server side for CIFAR-10 dataset. The best accuracy is the {\tt ResNet}\xspace proposed by~\cite{lee2022low}, but it also leads to the highest consumption in RAM. With LoLa setting, the accuracy is indeed lower but it requires $32$x lesser RAM. Then, our method reduces again the memory on server by almost a factor of $15$x for the same accuracy. RAM size on server matters for cloud computing as pricing increases along with memory needs\footnote{\label{azurepricing}\href{https://azure.microsoft.com/en-us/pricing/details/virtual-machines/windows/}{https://azure.microsoft.com/en-us/pricing/}}, thus low-memory solutions help the scalability of the MLaaS.

\section{Limitations and Conclusion}
\label{sec:Conclusion}

\myparagraph{Limitations.} Our proposed framework is still not as performant as the latest non-TFHE-based solutions with regard to running time and accuracy. Moreover, CIFAR-10 and larger datasets remain out of reach for industrial use. Finally, {\tt {TT-TFHE}}\xspace is for the moment limited by the constraints of the Concrete library.

\myparagraph{Conclusion.} In this paper, we presented a new framework, {\tt {TT-TFHE}}\xspace, which greatly outperforms all TFHE-based PPML solutions in terms of inference time, while maintaining acceptable accuracy. Our proposed framework is a practical solution for real-world applications, particularly for tabular data and small image datasets like MNIST, as it requires minimal memory/communication cost, provides strong security for the client's data, and is easy to deploy. We believe that this research will spark further investigations into the utilization of truth tables for privacy-preserving data usage, emphasized by the recently NIST Artificial Intelligence Risk Management Framework~\cite{ai2023artificial}.

\newpage