mirror of
https://github.com/lux-apps/papers.git
synced 2026-11-03 05:07:46 +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.
30 lines
1.5 KiB
TeX
30 lines
1.5 KiB
TeX
\section{FHE Background: TFHE}
|
|
|
|
|
|
TFHE operates on the torus $\mathbb{T} = \mathbb{R}/\mathbb{Z}$. A single bit $m \in \{0,1\}$ is encrypted as an LWE sample:
|
|
|
|
$$\text{ct} = (\mathbf{a}, b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q \quad \text{where} \quad b = \langle \mathbf{a}, \mathbf{s} \rangle + m \cdot \lfloor q/2 \rfloor + e$$
|
|
|
|
The secret key $\mathbf{s} \in \{0,1\}^n$ and noise $e$ drawn from a discrete Gaussian with standard deviation $\sigma$.
|
|
|
|
\subsection{Gate Evaluation}
|
|
|
|
Boolean gates are evaluated via programmable bootstrapping:
|
|
|
|
\begin{enumerate}[leftmargin=2em]
|
|
\item \textbf{Homomorphic gate}: Compute $\text{ct}_{\text{out}} = f(\text{ct}_1, \text{ct}_2)$ for gate $f$ (AND, OR, XOR, etc.) via lookup table encoded in the bootstrapping key.
|
|
\item \textbf{Blind rotation}: Rotate a test polynomial by the phase of the input ciphertext using RGSW ciphertexts of the key bits.
|
|
\item \textbf{Sample extraction}: Extract a fresh LWE ciphertext from the rotated polynomial.
|
|
\end{enumerate}
|
|
|
|
Each bootstrapped gate costs approximately 12ms on a single core (benchmarked on the \texttt{luxfi/lattice} library with $n=1024$, $q \approx 2^{27}$).
|
|
|
|
\subsection{The Key Trust Problem}
|
|
|
|
Standard TFHE decryption recovers the plaintext as:
|
|
|
|
$$m = \text{round}\left(\frac{b - \langle \mathbf{a}, \mathbf{s} \rangle}{q/2}\right)$$
|
|
|
|
Whoever holds $\mathbf{s}$ can decrypt any ciphertext---including intermediate computation results, cancelled orders, private balances, and rejected transactions. In a blockchain deployment, this is unacceptable.
|
|
|