On the Capacity of Secure Distributed Batch Matrix Multiplication
On the Capacity of Secure Distributed Batch Matrix Multiplication
复制标题
DOI：
10.1109/tit.2021.3112952
复制
发表时间：
2019-08
影响因子：
2.5
通讯作者：
Zhuqing Jia;S. Jafar
中科院分区：
文献类型：
--
作者：
Zhuqing Jia;S. Jafar
安全分布式批处理矩阵乘法（SDBMM）问题研究了从$N$分布式服务器中检索所需矩阵乘积序列${\mathbf{AB}} =({\mathbf{a}}_{1}{\mathbf{B}}_{1},\,\,{\mathbf{a}}_{2}{\mathbf{B}}_{2},\,\,\cdots,\,\,{\mathbf{a}}_ S}}{\mathbf{a}}_{1}, {\mathbf{a}}_{2},\ cdots, {\mathbf{a}}}_ S})$和${\mathbf{B}}=({\mathbf{B}} {1}，{\mathbf{B}}_{2},\cdots,{\mathbf{B}}_{S})$以$X$安全编码形式存储，也就是说，任何多达$X$的串通服务器组对$\mathbf{A, B}$一无所知。假设${\mathbf{A}}_{s}\in \mathbb {F}_{q}^{L\乘以K}， {\mathbf{B}}_{s}\in \mathbb {F}_{q}^{K\乘以M}， s\in \{1,2,\cdots, s\}$是均匀独立分布的，$\mathbb {F}_{q}$是一个大有限域。SDBMM方案的速率定义为检索到的所需信息的位数与平均下载的总位数之比。可实现速率的最大值称为SDBMM容量。在这项工作中，我们探讨了SDBMM的容量，以及它的几个变体，例如，在用户可能已经有${\mathbf{A}}$或${\mathbf{B}}$作为副信息可用的情况下，以及/或者在${\mathbf{A}}$或${\mathbf{B}}$的安全约束可以放松的情况下。我们根据$L， K， M， N， X$参数获得了SDBMM的逆界，以及各种情况下的可实现方案，并确定了这些界匹配的参数区域。特别是，安全计算一批两个向量的外积的容量为$(1-X/N)^{+}$，对于一批两个（长）向量的内积，随着向量的长度趋近于$(1-2X/N)^{+}$，一般来说，对于足够大的$K$（例如，$K > 2\min (L，M)$），容量$C$有界为$(1-2X/N)^{+}\leq C。我们的上界的一个值得注意的方面是SDBMM与私有信息检索（PIR）问题的一种形式之间的联系，称为多消息$X$ -安全$T$ -私有信息检索（MM-XSTPIR）。我们的可实现方案的显著特征包括使用跨子空间对齐和转换参数，将标量乘法问题转换为标量加法问题，从而实现令人惊讶的高效解决方案。
The problem of secure distributed batch matrix multiplication (SDBMM) studies the communication efficiency of retrieving a sequence of desired matrix products ${\mathbf{AB}} = ({\mathbf{A}}_{1}{\mathbf{B}}_{1},\,\,{\mathbf{A}}_{2}{\mathbf{B}}_{2},\,\,\cdots,\,\,{\mathbf{A}}_{S}{\mathbf{B}}_{S})$ from $N$ distributed servers where the constituent matrices ${\mathbf{A}}=({\mathbf{A}}_{1}, {\mathbf{A}}_{2}, \cdots, {\mathbf{A}}_{S})$ and ${\mathbf{B}}=({\mathbf{B}}_{1}, {\mathbf{B}}_{2},\cdots,{\mathbf{B}}_{S})$ are stored in $X$ -secure coded form, i.e., any group of up to $X$ colluding servers learn nothing about $\mathbf{ A, B}$ . It is assumed that ${\mathbf{A}}_{s}\in \mathbb {F}_{q}^{L\times K}, {\mathbf{B}}_{s}\in \mathbb {F}_{q}^{K\times M}, s\in \{1,2,\cdots, S\}$ 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 ${\mathbf{A}}$ or ${\mathbf{B}}$ available as side-information, and/or where the security constraint for either ${\mathbf{A}}$ or ${\mathbf{B}}$ 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. In particular, the capacity for securely computing a batch of outer products of two vectors is $(1-X/N)^{+}$ , for a batch of inner products of two (long) vectors the capacity approaches $(1-2X/N)^{+}$ as the length of the vectors approaches infinity, and in general for sufficiently large $K$ (e.g., $K > 2\min (L,M)$ ), the capacity $C$ is bounded as $(1-2X/N)^{+}\leq C . 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.