Sublinear-Overhead Secure Linear Algebra on a Dishonest Server

• URL: http://arxiv.org/abs/2502.13060v1
• Date: Tue, 18 Feb 2025 17:05:17 GMT
• Title: Sublinear-Overhead Secure Linear Algebra on a Dishonest Server
• Authors: Mark Braverman, Stephen Newman,
• Abstract summary: We state the natural efficiency and security desiderata for fast, remote, and data-oblivious linear algebra. We conjecture the existence of matrix and vector families implying satisfactory algorithms, and provide such an algorithm contingent on common cryptographic assumptions.
• Score: 3.8105803634609483
• License:
• 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 remote computation is particularly important for linear algebra, which comprises a large fraction of total computation and is best run on highly specialized hardware often only accessible through the cloud. We state the natural efficiency and security desiderata for fast, remote, and data-oblivious linear algebra, conjecture the existence of matrix and vector families implying satisfactory algorithms, and provide such an algorithm contingent on common cryptographic assumptions. We achieve sublinear overhead for the server, dramatically reduced computation cost for the client, and various other practical advantages over previous algorithms. Keywords: Data Privacy, Data-Oblivious Computation, Delegation, Homomorphic Encryption, Cloud Computing, Algorithm Efficiency, Sublinear Overhead, LPN, Matrix Multiplication.

Related papers

• Optimal Oblivious Algorithms for Multi-way Joins [2.8151472703172398]
  We propose a novel sorting-based algorithm for multi-way join processing that operates without relying on ORAM simulations or other security assumptions. Our algorithm is a non-trivial, provably oblivious composition of basic primitives, with time complexity matching the insecure worst-case optimal join algorithm, up to a logarithmic factor.
  arXiv  Detail & Related papers  (2025-01-08T01:23:29Z)
• Online Nonparametric Supervised Learning for Massive Data [0.0]
  We develop a fast algorithm adapted to the real-time calculation of the nonparametric classifier in massive as well as streaming data frameworks. The proposed methods are evaluated and compared to some commonly used machine learning algorithms for real-time fetal well-being monitoring.
  arXiv  Detail & Related papers  (2024-05-29T20:04:23Z)
• Secure and Efficient General Matrix Multiplication On Cloud Using Homomorphic Encryption [21.253885519048016]
  Homomorphic Encryption (HE) has emerged as an effective tool in assuring privacy and security for sensitive applications. One major obstacle to employing HE-based computation is its excessive computational cost.
  arXiv  Detail & Related papers  (2024-05-03T16:50:02Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization.
  arXiv  Detail & Related papers  (2023-09-01T18:02:04Z)
• Hyperdimensional Computing as a Rescue for Efficient Privacy-Preserving Machine Learning-as-a-Service [9.773163665697057]
  Homomorphic encryption (HE) is a promising technique to address this adversity. With HE, the service provider can take encrypted data as a query and run the model without decrypting it. We show hyperdimensional computing can be a rescue for privacy-preserving machine learning over encrypted data.
  arXiv  Detail & Related papers  (2023-08-17T00:25:17Z)
• RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations [56.59168541623729]
  Training graph neural networks (GNNs) is time consuming because sparse graph-based operations are hard to be accelerated by hardware. We explore trading off the computational precision to reduce the time complexity via sampling-based approximation. We propose Randomized Sparse Computation, which for the first time demonstrate the potential of training GNNs with approximated operations.
  arXiv  Detail & Related papers  (2022-10-19T17:25:33Z)
• Photonic co-processors in HPC: using LightOn OPUs for Randomized Numerical Linear Algebra [53.13961454500934]
  We show that the randomization step for dimensionality reduction may itself become the computational bottleneck on traditional hardware. We show that randomization can be significantly accelerated, at negligible precision loss, in a wide range of important RandNLA algorithms.
  arXiv  Detail & Related papers  (2021-04-29T15:48:52Z)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  We propose Berrut Approximated Coded Computing (BACC) as an alternative approach to deal with stragglers effect. BACC is proven to be numerically stable with low computational complexity. In particular, BACC is used to train a deep neural network on a cluster of servers.
  arXiv  Detail & Related papers  (2020-09-17T14:23:38Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  We present three new algorithms for constructing differentially private synthetic data. The algorithms satisfy differential privacy even in the worst case. Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload.
  arXiv  Detail & Related papers  (2020-07-10T15:46:05Z)
• Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
  Homomorphic Encryption (HE) is receiving more and more attention recently for its capability to do computations over the encrypted field. We propose a novel general distributed HE-based data mining framework towards one step of solving the scaling problem. We verify the efficiency and effectiveness of our new framework by testing over various data mining algorithms and benchmark data-sets.
  arXiv  Detail & Related papers  (2020-06-17T18:14:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.