@inproceedings{071dad5c7e294ab9b71655f07a39e6bc,
title = "Practical Secure Delegated Linear Algebra with Trapdoored Matrices",
abstract = "Most heavy computation occurs on servers owned by a second party. This reduces data privacy, resulting in interest in data-oblivious computation, which typically severely degrades performance. Secure and fast delegated computation is particularly important for linear algebra, which comprises a large fraction of total computation and is best run on highly specialized hardware often accessible only through the cloud. We state the natural efficiency and security desiderata for fast and data-oblivious delegated linear algebra. We demonstrate the existence of Trapdoored-Matrix families based on an LPN assumption, and provide a scheme for secure delegated matrix-matrix and matrix-vector multiplication based on the existence of trapdoored matrices. We achieve sublinear overhead for the server, dramatically reduced computation for the client, and various practical advantages over previous protocols.",
keywords = "Cloud Computing, Data Privacy, Data-Oblivious Computation, Delegation, Homomorphic Encryption, LPN, Matrix Multiplication, Sublinear Overhead, Trapdoored Matrix",
author = "Mark Braverman and Stephen Newman",
note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2026.; 23rd International Conference on Theory of Cryptography, TCC 2025 ; Conference date: 01-12-2025 Through 05-12-2025",
year = "2026",
doi = "10.1007/978-3-032-12287-2\_4",
language = "English (US)",
isbn = "9783032122865",
series = "Lecture Notes in Computer Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "97--118",
editor = "Benny Applebaum and Lin, \{Huijia (Rachel)\}",
booktitle = "Theory of Cryptography - 23rd International Conference, TCC 2025, Proceedings",
address = "Germany",
}