Fast Homomorphic Linear Algebra with BLAS

• URL: http://arxiv.org/abs/2503.16080v1
• Date: Thu, 20 Mar 2025 12:19:47 GMT
• Title: Fast Homomorphic Linear Algebra with BLAS
• Authors: Youngjin Bae, Jung Hee Cheon, Guillaume Hanrot, Jai Hyun Park, Damien Stehlé,
• Abstract summary: Homomorphic encryption opens a wide range of applications in privacy-preserving data manipulation, notably in AI.<n>Many of those applications require significant linear algebra computations (matrix x vector products, and matrix x matrix products).<n>This central role of linear algebra computations goes far beyond homomorphic algebra and applies to most areas of scientific computing.<n>We show that the efficiency loss between CKKS-based encrypted square matrix multiplication and double-precision floating-point square matrix multiplication is a mere 4-12 factor, depending on the precise situation.
• Score: 11.269481520748839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Homomorphic encryption is a cryptographic paradigm allowing to compute on encrypted data, opening a wide range of applications in privacy-preserving data manipulation, notably in AI. Many of those applications require significant linear algebra computations (matrix x vector products, and matrix x matrix products). This central role of linear algebra computations goes far beyond homomorphic algebra and applies to most areas of scientific computing. This high versatility led, over time, to the development of a set of highly optimized routines, specified in 1979 under the name BLAS (basic linear algebra subroutines). Motivated both by the applicative importance of homomorphic linear algebra and the access to highly efficient implementations of cleartext linear algebra able to draw the most out of available hardware, we explore the connections between CKKS-based homomorphic linear algebra and floating-point plaintext linear algebra. The CKKS homomorphic encryption system is the most natural choice in this setting, as it natively handles real numbers and offers a large SIMD parallelism. We provide reductions for matrix-vector products, vector-vector products for moderate-sized to large matrices to their plaintext equivalents. Combined with BLAS, we demonstrate that the efficiency loss between CKKS-based encrypted square matrix multiplication and double-precision floating-point square matrix multiplication is a mere 4-12 factor, depending on the precise situation.

Related papers

• Sublinear-Overhead Secure Linear Algebra on a Dishonest Server [3.8105803634609483]
  We state the natural efficiency and security desiderata for fast, remote, and data-oblivious linear algebra.<n>We conjecture the existence of matrix and vector families implying satisfactory algorithms, and provide such an algorithm contingent on common cryptographic assumptions.
  arXiv  Detail & Related papers  (2025-02-18T17:05:17Z)
• Position: Curvature Matrices Should Be Democratized via Linear Operators [6.946287154076936]
  Linear operators provide a general, scalable, and user-friendly abstraction to handle curvature matrices.<n>$textitcurvlinops$ is a library that provides curvature matrices through a unified linear operator interface.<n>We demonstrate with $textitcurvlinops$ how this interface can hide complexity, simplify applications, be interoperable with other libraries, and scale to large NNs.
  arXiv  Detail & Related papers  (2025-01-31T14:46:30Z)
• 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)
• Large-scale gradient-based training of Mixtures of Factor Analyzers [67.21722742907981]
  This article contributes both a theoretical analysis as well as a new method for efficient high-dimensional training by gradient descent. We prove that MFA training and inference/sampling can be performed based on precision matrices, which does not require matrix inversions after training is completed. Besides the theoretical analysis and matrices, we apply MFA to typical image datasets such as SVHN and MNIST, and demonstrate the ability to perform sample generation and outlier detection.
  arXiv  Detail & Related papers  (2023-08-26T06:12:33Z)
• Multiresolution kernel matrix algebra [0.0]
  We show the compression of kernel matrices by means of samplets produces optimally sparse matrices in a certain S-format. The inverse of a kernel matrix (if it exists) is compressible in the S-format as well. The matrix algebra is justified mathematically by pseudo differential calculus.
  arXiv  Detail & Related papers  (2022-11-21T17:50:22Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
  arXiv  Detail & Related papers  (2020-02-23T03:07:31Z)

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.