The reviewed record of science sign in
Pith

arxiv: 2604.23490 · v2 · pith:XXRX6B4A · 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

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-07-01 09:51 UTCgrok-4.3pith:XXRX6B4Arecord.jsonopen to challenge →

classification quant-ph cs.CR
keywords quantum fully homomorphic encryptionLWE decryptionmodular arithmetic programMBQC frameworkEPR pairsclassical clientparallel measurementsT-gate evaluation
0
0 comments X

The pith

A modular arithmetic program for LWE decryption reduces EPR pairs in quantum fully homomorphic encryption from O(lambda squared) to O(lambda log squared lambda).

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

The paper establishes a framework for quantum fully homomorphic encryption that improves on prior Barrington-based methods by introducing a modular arithmetic program tailored to LWE decryption. Because LWE decryption computes a modular inner product that is not symmetric, existing symmetric-function optimizations cannot be used directly. The new program tracks partial sums modulo q in a state space of size q, producing programs with O(lambda) states, binary encoding of O(log lambda), and length O(lambda log lambda). This construction transfers all quantum operations to the server, leaving the client with only classical operations, while supporting parallel measurements through the MBQC framework.

Core claim

LWE decryption is realized as a modular inner product via an MA-Program whose state space is Z_q, yielding programs of state count O(lambda) and length O(lambda log lambda) that reduce the required EPR pairs from O(lambda squared) to O(lambda log squared lambda) while enabling a fully classical client and parallel evaluation.

What carries the argument

The MA-Program, which tracks partial sums modulus q with state space Z_q to produce short programs for non-symmetric modular inner products.

If this is right

  • QFHE evaluation of each T-gate now consumes only O(lambda log squared lambda) EPR pairs instead of O(lambda squared).
  • The client performs solely classical LWE key generation and encryption under classical FHE, with no quantum operations required.
  • A layered key structure removes the need for circular security assumptions.
  • Up to O(log lambda) parallel measurements per layer are supported while keeping evaluation deterministic.
  • Offline EPR preparation is separated from online adaptive measurements.

Where Pith is reading between the lines

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

  • The same modular-tracking idea might apply to other lattice-based schemes whose decryption involves non-symmetric modular arithmetic.
  • If the offline EPR preparation can be made reusable across multiple evaluations, the amortized cost per computation could drop further.
  • The reduction in per-gate quantum resources could be combined with classical FHE batching techniques to handle larger circuits.
  • Testing whether the MBQC flow functions preserve the exact O(lambda) state count under realistic noise models would be a direct next measurement.

Load-bearing premise

The MA-Program can be embedded in the MBQC framework without increasing the stated state-space size or breaking correctness, and LWE decryption cannot exploit prior symmetric-function shortcuts.

What would settle it

A concrete construction or lower-bound proof showing that any correct MA-Program for LWE decryption requires length omega(lambda log lambda) or that the resulting gadget uses more than O(lambda log squared lambda) 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) enables arbitrary quantum computations on encrypted data, but prior constructions require prohibitive quantum resources--specifically, O(lambda^2) EPR pairs per T-gate evaluation using the Barrington-based approach (DSS16). This paper introduces a unified framework achieving exponential improvement over the generic Barrington-based approach in program length. The central innovation is a novel modular arithmetic program (MA-Program) tailored to learning with errors (LWE) decryption. We show that LWE decryption computes the inner product <sk,ct> mod q, a modular inner product that is NOT a symmetric function. Thus, prior symmetric-function optimizations (Sinha's O(n)-state branching programs) do not apply. Our MA-Program tracks partial sums modulus q with state space 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 fully classical client, we transfer all quantum resources (EPR preparation, Bell measurements, adaptive error correction) to the server via the MA-Program gadget framework. Clients only perform classical LWE key generation, Pauli key encryption under classical FHE, and no quantum operations; a layered key structure further eliminates circular security assumptions. For parallel computation, we adopt the MBQC framework with flow functions, supporting up to O(log lambda) parallel measurements per layer. This separates offline resource preparation from online adaptive measurement, enabling parallel processing while maintaining deterministic evaluation.

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 manuscript claims to introduce a modular arithmetic program (MA-Program) for LWE decryption in QFHE. By treating LWE decryption as a non-symmetric modular inner product (unlike prior symmetric-function optimizations), it constructs programs with state count O(λ), binary encoding O(log λ), and length O(λ log λ). This purportedly reduces the quantum gadget size from O(λ²) to O(λ log² λ) EPR pairs per T-gate, transfers all quantum resources to the server for a fully classical client, and uses MBQC with flow functions for O(log λ) parallel measurements per layer.

Significance. If the claimed resource reduction and MA-Program construction hold without hidden assumptions on q or the MBQC embedding, the result would constitute a substantial efficiency gain over Barrington-based QFHE, moving the field closer to practical quantum homomorphic encryption with classical clients and no circular security assumptions.

major comments (1)
  1. [Abstract] Abstract: The central efficiency claim rests on the MA-Program having 'state count O(λ)' while 'tracks partial sums modulus q with state space Z_q'. A state space Z_q requires q states, yet the text asserts state count O(λ) and derives O(λ log² λ) EPR pairs from program length O(λ log λ). Standard LWE parameters set q polynomial or superpolynomial in λ for security, creating an internal inconsistency that prevents the stated reduction from following. This is load-bearing for the main result.
minor comments (1)
  1. The abstract uses 'lambda' inline without consistent mathematical formatting; ensure uniform notation (e.g., λ) throughout the manuscript.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying the potential inconsistency in the abstract. We respond point-by-point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The central efficiency claim rests on the MA-Program having 'state count O(λ)' while 'tracks partial sums modulus q with state space Z_q'. A state space Z_q requires q states, yet the text asserts state count O(λ) and derives O(λ log² λ) EPR pairs from program length O(λ log λ). Standard LWE parameters set q polynomial or superpolynomial in λ for security, creating an internal inconsistency that prevents the stated reduction from following. This is load-bearing for the main result.

    Authors: We acknowledge that the abstract phrasing creates an ambiguity. The full manuscript constructs an MA-Program specifically for the non-symmetric modular inner product <sk, ct> mod q. This construction achieves O(λ) states (not q states) by using a binary-encoded representation and a sequence of modular additions tailored to the LWE structure, resulting in program length O(λ log λ) and binary encoding O(log λ) per state. The reference to 'state space Z_q requiring O(log q) bits' describes the per-state encoding size under standard LWE parameters where log q = O(log λ), but does not imply the program maintains q distinct states. Nevertheless, the wording is imprecise and risks misinterpretation. We will revise the abstract and introduction to explicitly state that the MA-Program uses O(λ) states via its non-symmetric structure, independent of q's magnitude, and will add a clarifying sentence on how the state count is derived. This is a presentation issue only; the underlying gadget size claim remains as stated. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation chain is self-contained with no reductions to inputs by construction

full rationale

The paper asserts an MA-Program construction for LWE decryption that tracks partial sums in Z_q, states a resulting state count of O(lambda), program length O(lambda log lambda), and consequent gadget-size reduction to O(lambda log^2 lambda) EPR pairs. No quoted step equates a claimed output to an input parameter by definition, renames a fitted value as a prediction, or relies on a load-bearing self-citation whose content reduces to the present claim. The non-symmetric-function premise and MBQC embedding are presented as independent justifications. The derivation therefore stands as self-contained against external benchmarks; any inconsistency in state-space accounting is a potential correctness issue, not circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The abstract introduces the MA-Program as the central new object; no explicit fitted numerical parameters are mentioned. The key domain assumption is that LWE decryption equals a modular inner product.

axioms (1)
  • domain assumption LWE decryption computes the inner product <sk,ct> mod q and is not a symmetric function
    Stated explicitly in the abstract as the reason prior optimizations do not apply.
invented entities (1)
  • MA-Program no independent evidence
    purpose: Compact representation of modular inner-product computation with state space Z_q
    New construct introduced to achieve the stated program length and EPR-pair reduction.

pith-pipeline@v0.9.1-grok · 5828 in / 1221 out tokens · 28510 ms · 2026-07-01T09:51:52.294396+00:00 · methodology

Review history (2 revisions) →

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 internal anchor

  1. [1]

    Interactive Proofs For Quantum Computations

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

    work page internal anchor Pith review Pith/arXiv 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