On the Capacity of Secure Distributed Batch Matrix Multiplication

DOI10.1109/TIT.2021.3112952MaRDI QIDQ5032584zbMATH OpenOpenAlexWikidataFDO

Authors Zhuqing Jia, Syed A. Jafar

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.06957

zbMATH Keywords

achievable ratescapacity of SDBMM

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The problem of secure distributed batch matrix multiplication (SDBMM) studies the communication efficiency of retrieving a sequence of desired matrix products $$ $=$ $$ $$ $cdots,$ $$ from $N$ distributed servers where the constituent matrices $$ and $$ are stored in $X$-secure coded form, i.e., any group of up to $X$ colluding servers learn nothing about $$. It is assumed that $$ are uniformly and independently distributed and $mathbb{F}_q$ is a large finite field. The rate of an SDBMM scheme is defined as the ratio of the number of bits of desired information that is retrieved, to the total number of bits downloaded on average. The supremum of achievable rates is called the capacity of SDBMM. In this work we explore the capacity of SDBMM, as well as several of its variants, e.g., where the user may already have either $$ or $$ available as side-information, and/or where the security constraint for either $$ or $$ may be relaxed. We obtain converse bounds, as well as achievable schemes for various cases of SDBMM, depending on the $L,K,M,N,X$ parameters, and identify parameter regimes where these bounds match. A remarkable aspect of our upper bounds is a connection between SDBMM and a form of private information retrieval (PIR) problem, known as multi-message $X$-secure $T$-private information retrieval (MM-XSTPIR). Notable features of our achievable schemes include the use of cross-subspace alignment and a transformation argument that converts a scalar multiplication problem into a scalar addition problem, allowing a surprisingly efficient solution.

Cited in

(3)

• Maliciously secure matrix multiplication with applications to private deep learning
• Secure Tensor Decomposition for Big Data Using Transparent Computing Paradigm
• Near-optimal fault tolerance for efficient batch matrix multiplication via an additive combinatorics lens

This page was built for publication: On the Capacity of Secure Distributed Batch Matrix Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032584)