论文标题
来自拉格朗日编码的对称私人多项式计算
Symmetric Private Polynomial Computation From Lagrange Encoding
论文作者
论文摘要
本文研究了$ x $ -secure $ t $ -secure $ t $ - colluding对称的私人多项式计算（PPC），来自$ b $ byzantine的编码存储系统和$ u $ byzantine和$ u $ byersponsive服务器。具体来说，根据$ N $分布式服务器存储的数据集，该数据集根据$（N，K+X）$最大距离可分离（MDS）代码，以使任何最多$ x $ colluding服务器的组都无法学习任何有关数据文件的信息。 A user wishes to privately evaluate one out of a set of candidate polynomial functions over the $M$ files from the system, while guaranteeing that any $T$ colluding servers can not learn anything about the identity of the desired function and the user can not learn anything about the $M$ data files more than the desired polynomial function evaluations, in the presence of $B$ Byzantine servers that can send arbitrary responses maliciously to confuse the user and $ U $无反应的服务器根本不会响应任何信息。提出了一种使用拉格朗日编码的新型对称PPC方案。该方案的PPC利率为$ 1- \ frac {g（k+x-1）+t+t+2b} {n-u} $，带有保密率$ \ frac {g（k+x-1）+t} {n-（g（k+x-1） $ n+\ max \ {k，n-（g（k+x-1）+t+2b+u）\} $，其中$ g $是所有候选多项式功能的最高学位。此外，分析了进一步衡量PPC方案的效率，上传成本，查询复杂性，服务器计算复杂性和实施该方案所需的解码复杂性。值得注意的是，本文研究的PPC设置概括了所有先前的MDS编码的PPC设置，并且在（渐近）PPC速率方面，降级方案严格优于最著名的方案，这是PPC方案的主要关注点。
The problem of $X$-secure $T$-colluding symmetric Private Polynomial Computation (PPC) from coded storage system with $B$ Byzantine and $U$ unresponsive servers is studied in this paper. Specifically, a dataset consisting of $M$ files is stored across $N$ distributed servers according to $(N,K+X)$ Maximum Distance Separable (MDS) codes such that any group of up to $X$ colluding servers can not learn anything about the data files. A user wishes to privately evaluate one out of a set of candidate polynomial functions over the $M$ files from the system, while guaranteeing that any $T$ colluding servers can not learn anything about the identity of the desired function and the user can not learn anything about the $M$ data files more than the desired polynomial function evaluations, in the presence of $B$ Byzantine servers that can send arbitrary responses maliciously to confuse the user and $U$ unresponsive servers that will not respond any information at all. A novel symmetric PPC scheme using Lagrange encoding is proposed. This scheme achieves a PPC rate of $1-\frac{G(K+X-1)+T+2B}{N-U}$ with secrecy rate $\frac{G(K+X-1)+T}{N-(G(K+X-1)+T+2B+U)}$ and finite field size $N+\max\{K,N-(G(K+X-1)+T+2B+U)\}$, where $G$ is the maximum degree over all the candidate polynomial functions. Moreover, to further measure the efficiency of PPC schemes, upload cost, query complexity, server computation complexity and decoding complexity required to implement the scheme are analyzed. Remarkably, the PPC setup studied in this paper generalizes all the previous MDS coded PPC setups and the degraded schemes strictly outperform the best known schemes in terms of (asymptotical) PPC rate, which is the main concern of the PPC schemes.
