← All AI/ML open problems

Privacy & encrypted learning · Neural architecture & complexity / Open question

Reasoning Without Decrypting the Prompt

Encrypted linear algebra is established, but nonlinear layers and autoregressive feedback can make a long private reasoning trace much more costly than one forward pass. Efficiency payoff: Co-design approximation, packing and decoding to reduce ciphertext work while preserving the complete generated answer.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-20

Seed catalog · Showing the bundled record.

Problem statement

For a public depth-LL, width-dd causal transformer with bounded weights, context length nn and generation horizon HH, compile greedy decoding into homomorphic computation over an encrypted prompt. Assume plaintext intermediate values lie in known bounded intervals and every reached top-two logit gap is at least γ>0\gamma>0. Determine the ciphertext memory, rotations, multiplications and bootstraps needed to return the same HH tokens with probability at least 1−ν1-\nu, under a fixed cryptographic security target and memory cap.

Assumptions and scope

  • Use a single client holding the secret key and an honest-but-curious evaluator; only the final encrypted output is returned for decryption. Prompt length, model, horizon and circuit layout are public. No intermediate decryptions, plaintext client-side layers or hidden interactive MPC are free operations.
  • Specify the HE scheme/parameters and security assumption, polynomial approximations, rescaling, bootstrapping and encrypted comparisons/token selection. Bound approximation and cryptographic arithmetic error separately, including their propagation through the generated prefix and KV state.
  • The logit-gap and range promises must hold on every plaintext prefix generated from admissible inputs. Charge verification or training used to enforce them. Confidentiality of encrypted inputs does not imply differential privacy of a released model, malicious-server correctness or secrecy of already public weights.

What would settle it?

An end-to-end generation-correctness and resource bound with a concrete compiler/schedule and matched baseline; derive a circuit/resource lower bound within the stated scheme or layout class where possible. Per-layer approximation error and amortized batch throughput alone do not settle it.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

CryptoNets, CKKS and MOAI establish inference building blocks and implementations; HEAT already co-adapts approximation and weights. CipherFlow optimizes hybrid HE/MPC placement. The retained target is a costed pure-HE autoregressive guarantee, not encrypted inference feasibility or a claim that nonlinear functions are impossible under FHE. This is an editorial, source-motivated research target. The preliminary review through 2026-11-20 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Gilad-Bachrach et al. — CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy ↗related algorithm · source checked 2026-11-20

    Primary proceedings abstract checked: homomorphic neural inference and encrypted predictions were demonstrated in 2016. Basic feasibility is not an open target.

  2. Cheon, Kim, Kim and Song — Homomorphic Encryption for Arithmetic of Approximate Numbers ↗partial theory · source checked 2026-11-20

    Primary IACR abstract checked: approximate SIMD arithmetic, rescaling and precision management under an RLWE-based construction. Numerical approximation and cryptographic confidentiality are distinct guarantees.

  3. Zhang et al. — MOAI: Module-Optimizing Architecture for Non-Interactive Secure Transformer Inference ↗related algorithm · source checked 2026-11-20

    Primary search abstract checked: packing, rotation reduction, Softmax/LayerNorm algorithms and non-interactive transformer inference with measured acceleration. Encrypted transformer inference is already implemented.

  4. Zirilli et al. — HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation ↗partial theory · source checked 2026-11-20

    Primary search abstract checked: trainable nonlinearity iteration counts, fixed-weight comparison to quantization-aware training and encrypted GPT-2 experiments. Approximation/weight co-design already exists; uniform full-trajectory guarantees are separate.

  5. Zhang, Zheng and Lou — CipherFlow: Compiling AI Programs for Efficient Cryptographically Secure Inference ↗related algorithm · source checked 2026-11-20

    Primary search abstract checked: cost-profiled joint HE/MPC placement, conversion and ciphertext-state planning. A hybrid interactive compiler is an existing baseline, but differs from a pure-HE no-intermediate-decryption interface.