mirror of
https://github.com/lux-apps/papers.git
synced 2026-11-02 11:39:52 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
61 lines
2.3 KiB
TeX
61 lines
2.3 KiB
TeX
\section{FHE Compute Cost}
|
|
|
|
|
|
Fully Homomorphic Encryption enables computation on encrypted data at the cost of a massive slowdown factor relative to cleartext computation.
|
|
|
|
\subsection{TFHE Gate Benchmarks}
|
|
|
|
Measured on Apple M4 Max (single core, \texttt{luxfi/lattice} library, $n=1024$, $q \approx 2^{27}$):
|
|
|
|
\begin{center}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Operation} & \textbf{Cleartext} & \textbf{Encrypted (TFHE)} & \textbf{Slowdown} \\
|
|
\midrule
|
|
Boolean AND & $<$1ns & 12ms & $1.2 \times 10^7$ \\
|
|
Boolean OR & $<$1ns & 12ms & $1.2 \times 10^7$ \\
|
|
Boolean XOR & $<$1ns & 11ms & $1.1 \times 10^7$ \\
|
|
8-bit addition & 1ns & 210ms & $2.1 \times 10^8$ \\
|
|
16-bit comparison & 1ns & 380ms & $3.8 \times 10^8$ \\
|
|
16-bit minimum & 1ns & 410ms & $4.1 \times 10^8$ \\
|
|
32-bit multiplication & 2ns & 3.8s & $1.9 \times 10^9$ \\
|
|
AES-128 round & 5ns & 48s & $9.6 \times 10^9$ \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\begin{observation}[FHE Overhead]
|
|
The bootstrapping operation dominates: each gate evaluation requires one programmable bootstrap at $\sim$12ms. Complex operations (multiplication, AES) are expensive because they decompose into hundreds or thousands of bootstrapped gates.
|
|
\end{observation}
|
|
|
|
\subsection{Parallelism}
|
|
|
|
TFHE gate evaluations within the same circuit level are independent and parallelizable:
|
|
|
|
\begin{center}
|
|
\begin{tabular}{lrrrr}
|
|
\toprule
|
|
\textbf{Cores} & \textbf{1} & \textbf{4} & \textbf{8} & \textbf{16} \\
|
|
\midrule
|
|
Gate throughput (/s) & 83 & 312 & 605 & 1,140 \\
|
|
16-bit compare & 380ms & 105ms & 58ms & 34ms \\
|
|
Order match (compare + min) & 790ms & 215ms & 118ms & 67ms \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
With 16 cores, a private orderbook match completes in 67ms---within the latency budget for financial applications.
|
|
|
|
\subsection{When FHE is Practical}
|
|
|
|
FHE is practical when:
|
|
\begin{enumerate}[leftmargin=2em]
|
|
\item The circuit depth is shallow (fewer sequential bootstraps).
|
|
\item Parallelism is available (independent gates at each level).
|
|
\item The computation is infrequent relative to its latency (e.g., one match per 100ms, not one per 1ms).
|
|
\item The alternative (revealing private data) is unacceptable.
|
|
\end{enumerate}
|
|
|
|
FHE is not practical for general-purpose computation. It is practical for targeted private operations: comparisons, minimum/maximum, boolean predicates, and simple arithmetic on small integers.
|
|
|