Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 68, Issue 4, Pages 2704-2718Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2022.3140890
Keywords
Private computation; symmetric private polynomial computation; Lagrange encoding; computation complexity
Funding
- National Natural Science Foundation of China [61941106, 61871331, 62101464]
Ask authors/readers for more resources
This paper studies the problem of X-secure T-colluding symmetric Private Polynomial Computation (PPC) in a coded storage system with Byzantine and unresponsive servers. It proposes a novel symmetric PPC scheme using Lagrange encoding, which achieves efficient computation while ensuring security.
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 - G(K+X-1)+T +2B/N-U with secrecy rate 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available