A cryptographic protocol for secure and efficient remote linear algebra computations with sublinear overhead

Background

The field of secure delegated computation has grown increasingly important as organizations rely on remote servers to run modern AI workloads. Neural network inference — overwhelmingly composed of matrix-matrix and matrix-vector multiplications — is too compute-intensive for most client devices and is typically offloaded to GPU- or TPU-equipped cloud servers. But many of the most valuable inference workloads involve sensitive inputs (medical images, financial transactions, private documents, biometric data, proprietary content), and sending that data to a third-party server in plaintext is often unacceptable on legal, regulatory, or commercial grounds. Existing cryptographic alternatives — fully or partially homomorphic encryption — close the privacy gap but impose 100×–1000× server-side overhead, making secure cloud inference economically infeasible at scale. This technology removes that tradeoff: it lets a client delegate the matrix multiplications underlying neural network inference to an untrusted server with cryptographic confidentiality of the client’s data and sublinear server overhead, using only operations that run natively on existing AI hardware.

Technology

This technology is a cryptographic protocol for delegating matrix multiplication — and therefore neural network evaluation — from a client device to a remote server, without revealing the client’s input data to that server. The client performs lightweight preprocessing that disguises its inputs as pseudorandom vectors with a hidden algebraic structure; the server performs the requested multiplication on the disguised inputs using ordinary linear algebra; the client cheaply recovers the true result. Because the protocol exposes only standard ring operations to the server, it runs on the same GPU and TPU hardware already deployed for AI inference. Off-the-shelf neural networks can be served under the protocol with no architectural modifications beyond standard quantization. The construction combines two new cryptographic primitives — trapdoored matrices and trapdoored vectors — with a modified Beaver’s-triples protocol, and its security reduces to the Learning Parity with Noise (LPN) problem, in the same family of hardness assumptions used in NIST-standardized post-quantum cryptography.

Benefits

• Sublinear cryptographic overhead on the server — well under a few percent of native compute cost in realistic regimes, versus 100×–1000× for FHE-based approaches
• Efficiency and generality — order-of-magnitude reduction in client cost compared to running the model locally, making large-model inference feasible from phones, embedded systems, and other constrained clients
• Cryptographic confidentiality — client data protected against a curious or compromised server, based on the hardness of the Learning Parity with Noise (LPN) problem
• Post-quantum security posture — draws on the same family of hardness assumptions as NIST-standardized post-quantum cryptography
• Runs natively on existing GPU and TPU hardware — uses only standard ring operations
• Drop-in compatibility with existing neural networks — no architectural modifications beyond standard quantization

Applications

• Privacy-preserving cloud inference for large neural networks — serving analysis systems from centralized GPU/TPU clusters while client inputs remain cryptographically hidden from the operator
• Edge and mobile AI offload — running large models on behalf of phones, vehicles, and IoT devices that cannot host the model locally and cannot expose user data to the cloud
• Regulated-industry inference — healthcare (radiology, pathology, clinical decision support), financial services (fraud detection, underwriting, KYC), and legal applications subject to HIPAA, GDPR, or contractual confidentiality requirements
• Confidential model serving — deployments in which the model owner wants to serve inference without exposing weights to the host infrastructure
• Secure data-science pipelines — analytics workloads whose dominant cost is large matrix multiplication and whose inputs are sensitive

Additional info

The protocol delegates the matrix multiplications that dominate the cost of neural network inference to an untrusted remote server, while keeping the client’s input data — and, optionally, the model weights — cryptographically hidden. Two new cryptographic primitives, trapdoored matrices and trapdoored vectors, are used as additive masks to produce a single-round-trip delegated multiplication with sublinear server overhead and dramatically reduced client cost. Security reduces to the Learning Parity with Noise assumption, placing the scheme in the same hardness family as NIST-standardized post-quantum cryptography. Because all server-side operations are standard ring operations, the protocol runs natively on existing GPU and TPU hardware and is compatible with off-the-shelf quantized neural networks.