mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +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.
88 lines
3.0 KiB
TeX
88 lines
3.0 KiB
TeX
\section{Fully Homomorphic Encryption}
|
|
|
|
|
|
\subsection{Homomorphic Property}
|
|
|
|
The defining property of FHE is that it supports both addition and
|
|
multiplication on ciphertexts. Formally, an FHE scheme
|
|
$(\mathsf{KeyGen}, \mathsf{Enc}, \mathsf{Dec}, \mathsf{Eval})$
|
|
satisfies~\cite{gentry2009}:
|
|
|
|
\begin{theorem}[Homomorphic Correctness]
|
|
For any circuit $C$ of depth $d$, keys $(pk, sk) \leftarrow
|
|
\mathsf{KeyGen}(1^\lambda)$, and plaintexts $x, y$:
|
|
\begin{align}
|
|
\mathsf{Dec}(sk, \mathsf{Eval}(pk, +, \mathsf{Enc}(pk,x),
|
|
\mathsf{Enc}(pk,y))) &= x + y \\
|
|
\mathsf{Dec}(sk, \mathsf{Eval}(pk, \times, \mathsf{Enc}(pk,x),
|
|
\mathsf{Enc}(pk,y))) &= x \cdot y
|
|
\end{align}
|
|
provided the accumulated noise does not exceed the modulus bound.
|
|
\end{theorem}
|
|
|
|
The noise growth per operation is the fundamental obstacle. For
|
|
LWE-based schemes~\cite{gsw2013}, multiplication increases noise
|
|
quadratically. Gentry's bootstrapping technique~\cite{gentry2009}
|
|
resets noise by homomorphically evaluating the decryption circuit,
|
|
enabling unbounded computation depth at the cost of one bootstrapping
|
|
operation per gate.
|
|
|
|
TFHE~\cite{tfhe2016} achieves gate-by-gate bootstrapping: each
|
|
boolean gate evaluation simultaneously computes the gate and refreshes
|
|
the ciphertext noise in a single operation, avoiding noise
|
|
accumulation entirely.
|
|
|
|
\subsection{TFHE Gate-by-Gate Bootstrapping}
|
|
|
|
Each boolean gate $G \in \{\text{AND}, \text{OR}, \text{XOR}, \ldots\}$
|
|
is evaluated via a single bootstrapping operation that simultaneously
|
|
computes the gate and refreshes the noise:
|
|
|
|
\[
|
|
\text{Bootstrap}(c, G) = \text{BlindRotate}(c) \cdot G_{\text{LUT}}
|
|
\]
|
|
|
|
where $G_{\text{LUT}}$ encodes the gate's truth table as a test
|
|
polynomial in $R_q$.
|
|
|
|
\subsection{Encrypted CRDT Merge}
|
|
|
|
CRDT merge under FHE enables conflict-free replication without
|
|
decryption. The LWW-Register merge circuit compares encrypted
|
|
timestamps MSB-to-LSB:
|
|
|
|
\begin{algorithmic}[1]
|
|
\State $\mathit{bGtA} \gets \bot$; $\mathit{eqSoFar} \gets \top$
|
|
\For{$i = \text{MSB}$ \textbf{downto} $0$}
|
|
\State $\mathit{bitGt} \gets \text{ANDNY}(a_i, b_i)$
|
|
\State $\mathit{bitEq} \gets \text{XNOR}(a_i, b_i)$
|
|
\State $\mathit{bGtA} \gets \text{OR}(\mathit{bGtA},
|
|
\text{AND}(\mathit{eqSoFar}, \mathit{bitGt}))$
|
|
\State $\mathit{eqSoFar} \gets \text{AND}(\mathit{eqSoFar},
|
|
\mathit{bitEq})$
|
|
\EndFor
|
|
\For{each bit $i$}
|
|
\State $\mathit{result}_i \gets \text{MUX}(\mathit{bGtA}, b_i, a_i)$
|
|
\EndFor
|
|
\end{algorithmic}
|
|
|
|
Gate count: $O(\text{bitsTS})$ comparisons + $O(\text{bitsVal} +
|
|
\text{bitsTS})$ MUX selections. At PN10QP27 with 8-bit timestamps
|
|
and 8-bit values: $\sim$40 bootstraps $\approx$ 4 seconds.
|
|
|
|
\subsection{Performance Budget}
|
|
|
|
\begin{center}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Operation} & \textbf{Gates} & \textbf{Time (PN10QP27)} & \textbf{Ciphertext} \\
|
|
\midrule
|
|
LWW Merge (8+8 bit) & 40 & 4\,s & 136\,KB \\
|
|
GCounter Max (32 bit/node) & 128 & 13\,s & 544\,KB \\
|
|
OR-Set Merge & 0 (tag union) & $<$1\,ms & tags only \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
%% ============================================================
|