pith. sign in

arxiv: 2604.23490 · v1 · submitted 2026-04-26 · 🪐 quant-ph · cs.CR

Efficient Quantum Fully Homomorphic Encryption

Fengxia Liu , Zixian Gong , Kun Tian , Yi Zhang , Zhiming Zheng , Maozhi Xu This is my paper

Pith reviewed 2026-05-08 06:31 UTC · model grok-4.3

classification 🪐 quant-ph cs.CR
keywords quantum fully homomorphic encryptionlearning with errorsmodular arithmetic programsgarden-hose modelmeasurement-based quantum computationbranching programsEPR pairsLWE decryption
0
0 comments X

The pith

A novel modular arithmetic program for LWE decryption reduces the quantum resource cost of fully homomorphic encryption to near-linear in the security parameter.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops a framework for quantum fully homomorphic encryption that achieves an exponential improvement in efficiency. The key step is designing a modular arithmetic program specifically for the decryption function in LWE-based schemes, which tracks partial sums to keep state small. This produces compact branching programs that translate into much smaller quantum gadgets using the garden-hose model and measurement-based quantum computation. The result is a scheme that uses only classical clients and the standard LWE assumption, lowering the barrier to practical delegated quantum computation.

Core claim

The central discovery is a modular arithmetic program that computes the inner product of the secret key and ciphertext modulo q by maintaining a partial sum, requiring only O(log q) bits of state. This yields branching programs with width O(log λ) and length O(λ log λ), which in turn allow the essential quantum gadget to be implemented with O(λ log² λ) EPR pairs rather than the previous O(λ^{2.58}). The framework maps this directly to homomorphic evaluation via garden-hose and MBQC while preserving compactness and relying solely on classical LWE security.

What carries the argument

The novel modular arithmetic program (MAP) tailored to LWE decryption that tracks partial sums modulo q to compute the inner product with O(log q) state width.

If this is right

  • The resulting QFHE scheme requires far fewer EPR pairs for the quantum gadget.
  • It supports fully classical clients without quantum capabilities.
  • The security rests only on the classical Learning-with-Errors assumption.
  • The scheme remains compact, with ciphertext size independent of the computation size.
  • MBQC provides deterministic control flow for the evaluation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This reduction in resource requirements could make experimental demonstrations of QFHE more accessible with current quantum hardware.
  • The distinction drawn between symmetric and non-symmetric functions may guide optimizations for other LWE-based primitives.
  • Similar MAP constructions could be tested on related algebraic computations to check for comparable state-width reductions.

Load-bearing premise

The assumption that the new modular arithmetic program computes the required inner product modulo q using only O(log q) bits of state width without introducing extra exponential costs in the garden-hose mapping.

What would settle it

An explicit construction or simulation showing that the MAP requires more than O(log q) state width or that the resulting gadget exceeds O(λ log² λ) EPR pairs would falsify the efficiency claim.

Figures

Figures reproduced from arXiv: 2604.23490 by Fengxia Liu, Kun Tian, Maozhi Xu, Yi Zhang, Zhiming Zheng, Zixian Gong.

Figure 1
Figure 1. Figure 1: QFHE Quantum Circuit: T-gate Evaluation. view at source ↗
Figure 2
Figure 2. Figure 2: MBQC Dependency Flow - Adaptive Control via Flow Functions view at source ↗
read the original abstract

Quantum fully homomorphic encryption (QFHE) promises secure delegated quantum computation but has been impeded by the prohibitive quantum resource demands of existing constructions. This paper introduces a unified framework that achieves an \textbf{exponential improvement} in efficiency by synergistically integrating three theoretical tools: \textbf{modular arithmetic programs (MAP)}, the \textbf{garden-hose model}, and \textbf{measurement-based quantum computation (MBQC)}. Our central innovation is a novel MAP tailored to the algebraic structure of Learning-with-Errors (LWE) decryption. Unlike generic approaches that incur exponential overhead, our MAP computes the inner product $\langle \boldsymbol{sk}, \boldsymbol{c} \rangle \bmod q$ by tracking a partial sum modulo $q$, requiring only $O(\log q)$ bits of state width. This yields branching programs of width $O(\log \lambda)$ and length $O(\lambda \log \lambda)$, thereby reducing the size of the essential quantum gadget from $O(\lambda^{2.58})$ to $O(\lambda \log^2 \lambda)$ EPR pairs -- a concrete improvement factor of $2^{15}$ to $2^{18}$ for standard security parameters. Critically, we demonstrate that LWE decryption is not a \textbf{symmetric function}, necessitating our specialized MAP design beyond prior symmetric-function optimizations. The framework provides a direct mapping from the MAP to an efficient gadget via the garden-hose model, with MBQC furnishing the deterministic control flow for homomorphic evaluation. The resulting QFHE scheme supports \textbf{fully classical clients}, relies solely on the \textbf{classical LWE assumption} (avoiding circular security or quantum hardness assumptions), and maintains compactness. This work dramatically lowers the quantum resource barrier for practical QFHE, paving the way for realistic privacy-preserving quantum cloud computing.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper claims to introduce a unified framework for quantum fully homomorphic encryption (QFHE) by combining a novel modular arithmetic program (MAP) tailored to LWE decryption, the garden-hose model, and measurement-based quantum computation (MBQC). This yields branching programs of width O(log λ) and length O(λ log λ), reducing the essential quantum gadget from O(λ^{2.58}) to O(λ log² λ) EPR pairs (an improvement of 2^{15}–2^{18} for standard parameters), while supporting fully classical clients under the classical LWE assumption without circular security or quantum hardness assumptions.

Significance. If the MAP construction and its mappings are correct, the work would constitute a substantial advance in QFHE efficiency, lowering quantum resource barriers enough to make delegated quantum computation with privacy guarantees more realistic. The explicit avoidance of non-standard assumptions and the focus on classical clients are notable strengths.

major comments (1)
  1. [Abstract] Abstract (central innovation paragraph): The claim that the MAP computes ⟨sk, c⟩ mod q by tracking a partial sum with only O(log q) bits of state width, thereby producing branching programs of width O(log λ), is internally inconsistent with standard branching-program definitions. A state of O(log q) bits permits up to q^{O(1)} distinct states per layer; for typical LWE parameters (q = poly(λ)), this yields width poly(λ) rather than O(log λ). The garden-hose/MBQC mapping is asserted to add no exponential overhead, but any width mismatch directly scales the EPR-pair count and invalidates the O(λ log² λ) bound and the stated improvement factor.
minor comments (1)
  1. The abstract uses both 'O(λ log² λ)' and 'O(λ log^2 λ)'; consistent LaTeX notation should be used throughout.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We are grateful to the referee for their thorough review and for highlighting an important point regarding the terminology used in the abstract. We address this below and will make the necessary revisions to clarify the presentation.

read point-by-point responses

  1. Referee: [Abstract] Abstract (central innovation paragraph): The claim that the MAP computes ⟨sk, c⟩ mod q by tracking a partial sum with only O(log q) bits of state width, thereby producing branching programs of width O(log λ), is internally inconsistent with standard branching-program definitions. A state of O(log q) bits permits up to q^{O(1)} distinct states per layer; for typical LWE parameters (q = poly(λ)), this yields width poly(λ) rather than O(log λ). The garden-hose/MBQC mapping is asserted to add no exponential overhead, but any width mismatch directly scales the EPR-pair count and invalidates the O(λ log² λ) bound and the stated improvement factor.

    Authors: We thank the referee for identifying this inconsistency in our abstract. We agree that, according to standard definitions, a branching program whose state is described by O(log q) bits has width 2^{O(log q)} = poly(λ). The phrase 'width O(log λ)' was a misstatement; we meant that the state can be represented using O(log λ) bits (since log q = O(log λ)). We will revise the abstract to correctly state that the branching programs have width poly(λ) and length O(λ log λ). Regarding the EPR pair count, the garden-hose model construction maps the program such that the quantum resources scale with the length of the program and the bit-length of the state rather than the full state space size, because the model allows for a direct encoding of the modular arithmetic without enumerating all states explicitly. Thus, the O(λ log² λ) bound holds as the effective overhead is logarithmic in the state space size. We will add a clarifying paragraph in the main text explaining this mapping to avoid any ambiguity. revision: yes

Circularity Check

0 steps flagged

No significant circularity; novel MAP construction presented as independent contribution

full rationale

The paper's central derivation introduces a novel modular arithmetic program (MAP) tailored to LWE decryption that tracks partial sums modulo q using O(log q) bits of state width, yielding branching programs of width O(log λ) and length O(λ log λ). This is explicitly framed as a new design necessitated by LWE decryption not being symmetric, going beyond prior symmetric-function optimizations. No steps reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the efficiency bounds are asserted as outputs of the new MAP rather than inputs renamed as predictions. The framework maps the MAP to gadgets via garden-hose and MBQC without circular reduction. The derivation is self-contained against the classical LWE assumption and the claimed properties of the specialized MAP.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard LWE hardness assumption and the correctness of the new MAP construction, which is presented as a theoretical innovation without additional free parameters beyond standard security parameters like λ and q.

axioms (1)
  • domain assumption The hardness of the Learning with Errors (LWE) problem
    The scheme relies on classical LWE assumption for security.

pith-pipeline@v0.9.0 · 5645 in / 1512 out tokens · 43071 ms · 2026-05-08T06:31:50.826809+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Aharonov, M

    D. Aharonov, M. Ben-Or, E. Eban. Interactive proofs for quantum computations. arXiv:0810.5375, 2008

    work page arXiv 2008

  2. [2]

    Ambainis, M

    A. Ambainis, M. Mosca, A. Tapp, R. de Wolf. Private quantum channels. FOCS 2000, 2000: 547--556

    work page 2000

  3. [3]

    Broadbent, S

    A. Broadbent, S. Jeffery. Quantum homomorphic encryption for circuits of low T-gate complexity. CRYPTO 2015, 2015: 609--629

    work page 2015

  4. [4]

    Brakerski, V

    Z. Brakerski, V. Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. FOCS 2011, 2011: 97--106

    work page 2011

  5. [5]

    Buhrman, S

    H. Buhrman, S. Fehr, C. Schaffner, F. Speelman. The garden-hose model. ITCS 2013, 2013: 145--158

    work page 2013

  6. [6]

    D. A. M. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci., 1989, 38(1): 150--164

    work page 1989

  7. [7]

    Beigel, J

    R. Beigel, J. Tarui. On ACC. Computational Complexity, 1994: 350--366

    work page 1994

  8. [8]

    Brakerski

    Z. Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. CRYPTO 2012, 2012: 868--886

    work page 2012

  9. [9]

    Brakerski

    Z. Brakerski. Quantum FHE (almost) as secure as classical. CRYPTO 2018, 2018: 67--95

    work page 2018

  10. [10]

    Bartusek, A

    J. Bartusek, A. Gupte, S. Mutreja, O. Shmuel. Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE. e-Print: 2510.08400, 2025

    work page arXiv 2025

  11. [11]

    A. M. Chiu. A garden-hose model for secure multiparty computation. PhD Thesis, University of Toronto, 2014

    work page 2014

  12. [12]

    Dulek, C

    Y. Dulek, C. Schaffner, F. Speelman. Quantum homomorphic encryption for polynomial-sized circuits. CRYPTO 2016, 2016: 3--32

    work page 2016

  13. [13]

    Danos, E

    V. Danos, E. Kashefi. Determinism in the one-way model. Phys. Rev. A, 2006, 74: 052310

    work page 2006

  14. [14]

    van Dijk, C

    M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan. Fully homomorphic encryption over the integers. EUROCRYPT 2010, 2010: 24--43

    work page 2010

  15. [15]

    Gorbunov, V

    S. Gorbunov, V. Vaikuntanathan, H. Wee. Attribute based encryption for circuits. STOC 2013, 2013: 545--554

    work page 2013

  16. [16]

    Gupte, V

    A. Gupte, V. Vaikuntanathan, C. Wee. On the hardness of learning with errors with binary secrets. Theory of Cryptography, 2022: 1--22

    work page 2022

  17. [17]

    Gentry, A

    C. Gentry, A. Sahai, B. Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. CRYPTO 2013, 2013: 75--92

    work page 2013

  18. [18]

    Goldwasser, Y

    S. Goldwasser, Y. Kalai, R. A. Popa, V. Vaikuntanathan, N. Zeldovich. How to run Turing machines on encrypted data. CRYPTO 2013, 2013: 536--553

    work page 2013

  19. [19]

    Hoffstein, J

    J. Hoffstein, J. Pipher, J. H. Silverman. NTRU: A ring-based public key cryptosystem. ANTS III, 1998: 267--288

    work page 1998

  20. [20]

    Lyubashevsky, C

    V. Lyubashevsky, C. Peikert, O. Regev. On ideal lattices and learning with errors over rings. EUROCRYPT 2010, 2010: 1--23

    work page 2010

  21. [21]

    M. Liang. Symmetric quantum fully homomorphic encryption with perfect security. Quantum Inf. Process. 2013: 12:3675–3687

    work page 2013

  22. [22]

    U. Mahadev. Classical homomorphic encryption for quantum circuits. FOCS 2018, 2018: 332--338

    work page 2018

  23. [23]

    Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions

    GS Ma, HB Li. Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions. 2022,6,866

    work page 2022

  24. [24]

    O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 2009, 56(6): 1--40

    work page 2009

  25. [25]

    Raussendorf, H

    R. Raussendorf, H. J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 2001, 86: 5188--5191

    work page 2001

  26. [26]

    Raussendorf, D

    R. Raussendorf, D. E. Browne, H. J. Briegel. Measurement-based quantum computation on cluster states. Phys. Rev. A, 2003, 68: 022312

    work page 2003

  27. [27]

    R. K. Sinha. Some Topics in Parallel Computation and Branching Programs. PhD Thesis, 1995

    work page 1995

  28. [28]

    Sahai, B

    A. Sahai, B. Waters. How to use indistinguishability obfuscation: Deniable encryption, and more. STOC 2014, 2014: 475--484

    work page 2014

  29. [29]

    Speelman

    F. Speelman. Non-local computation of low T-depth quantum circuits. TQC 2016, 2016

    work page 2016

  30. [30]

    B. Yu, C. A. P \'e rez-Delgado, J. F. Fitzsimons. Limitations on information-theoretically secure quantum homomorphic encryption. Phys. Rev. A, 2014, 90: 050303

    work page 2014