papers/zoo-ai-memory/sections/06-fhe-encrypted-memory.tex

\section{FHE-Encrypted Memory}

\label{sec:fhe}
%----------------------------------------------------------------------

\subsection{Motivation}

Standard encrypted memory requires decryption before use. This creates a vulnerability window: during inference, memory is plaintext in the agent's address space. For high-sensitivity applications (medical, legal, financial), even this transient exposure is unacceptable.

Fully homomorphic encryption allows computation on encrypted data without decryption. We use \CKKS{} (approximate arithmetic over encrypted real numbers) for memory operations because memory recall is fundamentally a similarity-search problem over real-valued embeddings.

\subsection{CKKS-Encrypted Embeddings}

Each memory entry's embedding vector $\mathbf{v} \in \mathbb{R}^d$ is encrypted under \CKKS{}:

\begin{equation}
\hat{\mathbf{v}} = \text{CKKS.Encrypt}(pk, \mathbf{v})
\end{equation}

where $pk$ is the collective public key generated by \TChain{} validators via distributed key generation.

\subsection{Homomorphic Similarity Search}

Given a query embedding $\hat{\mathbf{q}}$ (also encrypted), the agent computes encrypted cosine similarity against all stored embeddings:

\begin{equation}
\widehat{\textit{sim}}_i = \frac{\hat{\mathbf{q}} \odot \hat{\mathbf{v}}_i}{\|\hat{\mathbf{q}}\| \cdot \|\hat{\mathbf{v}}_i\|}
\end{equation}

where $\odot$ denotes the \CKKS{} homomorphic inner product. The result $\widehat{\textit{sim}}_i$ is an encrypted similarity score. The agent can rank results by encrypted comparison (via \TFHE{} boolean circuits for the comparison operation) and retrieve the top-$k$ entries---all without decrypting any embedding.

\subsection{Encrypted Recall Protocol}

\begin{algorithm}
\caption{FHE-Encrypted Memory Recall}
\begin{algorithmic}[1]
\REQUIRE Query embedding $\mathbf{q}$, capsule $\mathcal{C}$, threshold $k$
\STATE $\hat{\mathbf{q}} \leftarrow \text{CKKS.Encrypt}(pk, \mathbf{q})$
\FOR{each entry $i$ in $\mathcal{C}.\textit{vault}$}
    \STATE $\hat{s}_i \leftarrow \text{CKKS.InnerProduct}(\hat{\mathbf{q}}, \hat{\mathbf{v}}_i)$
\ENDFOR
\STATE $\hat{\textit{top}} \leftarrow \text{TFHE.TopK}(\{\hat{s}_i\}, k)$ \COMMENT{encrypted argmax via boolean circuit}
\STATE Submit $\hat{\textit{top}}$ indices to \TChain{} for threshold decryption
\STATE \TChain{} validators contribute shares; reconstruct indices
\STATE Retrieve and decrypt entries at revealed indices
\RETURN Decrypted top-$k$ memory entries
\end{algorithmic}
\end{algorithm}

\subsection{Noise Budget and Precision}

\CKKS{} introduces approximation error that accumulates with each homomorphic operation. For memory recall, the critical constraint is that similarity rankings must be preserved despite noise.

\begin{proposition}
For embeddings of dimension $d = 768$ and \CKKS{} parameters $(N = 2^{15}, \Delta = 2^{40})$, the probability that noise flips a top-$k$ ranking for $k \leq 20$ is bounded by:
\begin{equation}
\Pr[\textit{rank flip}] < 2^{-40}
\end{equation}
when the minimum similarity gap between the $k$-th and $(k+1)$-th entries exceeds $\epsilon = 10^{-4}$.
\end{proposition}

This precision is sufficient for practical memory recall, where the similarity gap between relevant and irrelevant entries typically exceeds $0.01$.

\subsection{Third-Party Verification}

A key property of \FHE{}-encrypted memory is that third parties can verify reasoning traces without observing content. An auditor can confirm:
\begin{enumerate}
    \item The agent queried its capsule (the encrypted query is on-chain).
    \item The capsule returned specific indices (the encrypted result is on-chain).
    \item The agent used those entries in its response (the reasoning trace references the indices).
\end{enumerate}

All of this is verifiable without the auditor ever seeing the memory content.

%----------------------------------------------------------------------