Towards more Practical Secure Computation: Efficient Protocols for Secure Linear Algebra

“Secure Computation” has been a classic and central question in modern cryptography with a large set of potential applications.
Mining large genomic databases, private scientific computation, and studying properties of shared networks are just a few examples.
Unfortunately, the majority of the constructions in this area have not made their way into practice, primarily due to their inefficiency.

In this talk, I first outline three different approaches toward designing more practical protocols, and briefly describe some of our results in each direction. I will then focus on one approach and the problem of “Secure Linear Algebra”. In a distributed system, linear constraints might reveal sensitive information and therefore, the involved parties want to reveal as little information as possible about their private inputs. I consider this problem in multiple distributed settings and adversarial environments. In each case, I will describe protocols that are nearly optimal in terms of round, computation, and communication efficiency.