Minimizing latency for secure distributed computing

By Rawad Bitar, Parimal Parag, Salim el Rouayheb. 2017

78 citations recorded by the source corpus.

We consider the setting of a master server who possesses confidential data (genomic, medical data, etc.) and wants to run intensive computations on it, as part of a machine learning algorithm for example. The master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private (in an information theoretic sense) and not revealed to the individual workers. The workers may be busy and will take a random time to finish the task assigned to them. We are interested in reducing the aggregate delay experienced by the master. We focus on linear computations as an essential operation in many iterative algorithms. A known solution is to use a linear secret sharing scheme to divide the data into secret shares on which the workers can compute. We propose to use instead new secure codes, called Staircase codes, introduced previously by two of the authors. We study the delay induced by Staircase codes which is always less than that of secret sharing. The reason is that secret sharing schemes need to wait for the responses of a fixed fraction of the workers, whereas Staircase codes offer more flexibility in this respect. For instance, for codes with rate R = 1/2 Staircase codes can lead to up to 40% reduction in delay compared to secret sharing.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Information Systems

Citations in the corpus

On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, neutral): “Secure matrix-vector multiplication was considered in [3].”
On the Capacity of Secure Distributed Matrix Multiplication (2018, neutral): “Several other recent works that studied secure distributed computing problems that are similar to ours include [12]–[14].”
Speeding Up Distributed Machine Learning Using Codes (2015, background): “[46] consider a secure coded computation problem where the input data matrices need to be secured from the workers.”
ON THE CAPACITY OF SECURE DISTRIBUTED FAST FOURIER TRANSFORM (2018, background): “A few works that do take security into account include [14, 15] where both works used secret sharing scheme along with different encoding strategies to make sure that the computations are secure, and [16] proposed a novel coded computing strat-”
Secure Distributed Computing With Straggling Servers Using Polynomial Codes (2019, background): “Secure distributed computing schemes that address straggling effects have been proposed using secret sharing [21], [22] or staircase codes [7], [23] ensuring information-theoretic security on input data.”
GASP Codes for Secure Distributed Matrix Multiplication (2018, methodology): “In this case, one can use methods like Shamir’s secret sharing [3] or Staircase codes [4], if one is also interested in straggler mitigation.”