Two Private Secure Distributed Coded Computation Schemes Using Extension Fields
Anjana A. Mahesh, Tushara Swapna Malladi, Balaji Sundar Rajan · 2020
Stragglers, adversaries and colluding workers are some of the key problems affecting the performance of a distributed computing system. There have been many works in reducing the recovery threshold (i.e. minimum number of workers the master needs to wait, to compute the final output), while tackling adversaries and colluding workers for providing security and data privacy. These works generally consider datasets over arbitrary fields i.e. fields of characteristic both zero and prime. In this paper, we show that, for distributed computing problems over finite fields, performing the computations over an appropriately-sized extension field can improve the recovery threshold with a trade off only in computational complexity while preserving the privacy and security parameters. We show this for two schemes: (i) Lagrange coded computing scheme for evaluating an arbitrary multivariate polynomial over a dataset over finite fields, proposed in [Q. Yu, N. Raviv, J. So, and A. S. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security and privacy,” arXiv:1806.00939v3] and (ii) private secure matrix multiplication discussed in [M. Kim, and J. Lee, “Private Secure Coded Computation,” arXiv:1902.00167]. When a proper degree of field extension is chosen, the proposed coding schemes is applicable even in cases where the original schemes are not applicable because of insufficient number of workers or insufficient field size.