Paper 2025/858

Encrypted Matrix-Vector Products from Secret Dual Codes

Caicai Chen, Bocconi University

Shai Halevi, AWS

Yuval Ishai, Technion – Israel Institute of Technology, AWS

Hugo Krawczyk, AWS

Tamer Mour, Bocconi University

Tal Rabin, AWS

Alon Rosen, Bocconi University

Abstract

Motivated by applications to efficient secure computation, we consider the following problem of encrypted matrix–vector product (EMVP). Let $\mathbb F$ be a finite field. In an offline phase, a client uploads an encryption of a matrix $M \in \mathbb F^{m\times \ell}$ to a server, keeping only a short secret key. The server stores the encrypted matrix \(\hat{M}\). In the online phase, the client may repeatedly send encryptions \(\hat{ q}_i\) of query vectors \(q_i \in \mathbb F^\ell\), which enables the client and the server to locally compute compact shares of the matrix–vector product \(Mq_i\). The server learns nothing about \(M\) or \(q_i\). The shared output can either be revealed to the client or processed by another protocol. We present efficient EMVP protocols based on variants of the learning parity with noise (LPN) assumption and the related learning subspace with noise (LSN) assumption. Our EMVP protocols are field-agnostic in the sense that the parties only perform arithmetic operations over \(\mathbb F\), and are close to optimal with respect to both communication and computation. In fact, for sufficiently large \(\ell\) (typically a few hundreds), the online computation and communication costs of our LSN-based EMVP can be \emph{less than twice} the costs of computing \(Mq_i\) in the clear. Combined with suitable secure post-processing protocols on the secret-shared output, our EMVP protocols are useful for a variety of secure computation tasks, including encrypted fuzzy search and secure ML. Our technical approach builds on recent techniques for private information retrieval in the secret-key setting. The core idea is to encode the matrix \(M\) and the queries \(q_i\) using a pair of secret dual linear codes, while defeating algebraic attacks by adding noise.

Note: Added Appendix G with a degree lower bound on algebraic attacks against 1D-SLSN, as well as experiments over small fields in Section 7.2.1.

@misc{cryptoeprint:2025/858,
      author = {Fabrice Benhamouda and Caicai Chen and Shai Halevi and Yuval Ishai and Hugo Krawczyk and Tamer Mour and Tal Rabin and Alon Rosen},
      title = {Encrypted Matrix-Vector Products from Secret Dual Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/858},
      year = {2025},
      url = {https://eprint.iacr.org/2025/858}
}