Maozhi Xu

Quantum fully homomorphic encryption (QFHE) enables arbitrary quantum computations on encrypted data, but existing constructions require prohibitive quantum resources—specifically, O($\lambda^{2}$) EPR pairs per $\mathsf{T}$-gate evaluation using the Barrington based approach of Dulek-Schaffner-Speelman (CRYPTO 2016). This paper introduces a unified framework achieving exponential improvement over the generic Barrington-based approach in terms of program length (from $O(\lambda^2)$ to $O(\lambda \log ^2\lambda)$). The central innovation of this paper is a novel modular arithmetic program(MA-Program) tailored to the algebraic structure of LWE decryption. We demonstrate that LWE decryption computes $⟨sk,ct⟩$ mod $q$—a modular inner product that is \textbf{NOT} a symmetric function. Consequently, prior symmetric-function optimizations (Sinha's $O(n)$-state-count branching programs) do not apply. Our MA-Program tracks partial sums modulus $q$ with state space $\mathbb{Z}_q$ requiring $O(\log q)$ bits, yielding programs of state count $O(\lambda)$ with binary encoding $O(\log \lambda)$ and length $O(\lambda \log \lambda)$. This reduces the quantum gadget size from $O(\lambda^{2})$ to $O(\lambda \log^2 \lambda)$ EPR pairs. To achieve a \textbf{fully classical client}, we transfer all quantum resource requirements (EPR pair preparation, Bell measurements, adaptive error correction) to the server via the MA‑Program gadget framework, requiring clients only to perform classical LWE key generation, Pauli key encryption/decryption under classical FHE, and no quantum operations; a layered key structure where gadget information is encrypted under fresh public keys further eliminates circular security assumptions. For \textbf{parallel computation}, we adopt the MBQC framework with flow functions, which supports up to $O(\log\lambda)$ parallel measurements per layer (matching the binary encoding width of our MA‑Program), and separates offline resource preparation (batch EPR pair generation) from online adaptive measurement, enabling parallel processing of measurement tasks while maintaining deterministic evaluation.