Abstract:
Scaling secure computation to very large numbers of parties introduces multiple interesting challenges, most obviously in designing efficient protocols that scale, but also in how we model the network and reason about its guarantees. In this talk we will cover 3 recent results. In the honest (super-)majority setting, we present a protocol for which the per-party cost of communication decreases as the number of parties increases (*). We then present a protocol where up to n-1 parties might be malicious, and the per-party communication is O(n + |C|). To the best of our knowledge, this is the first construction achieving better than O(n + n|C|) communication, among protocols whose communication depends on |C| (i.e. avoiding fully homomorphic encryption, which has a high computational cost). Finally, the two protocols described above do not provide any output guarantees, which is a serious concern when dealing with large numbers of parties. The classical definition for guaranteeing output in cryptographic protocols is very strong, and protocols that satisfy this definition tend to have very high costs. We will end the talk by describing some on-going work in which we offer a new, relaxed definition, which we call churn-resilience. Time permitting, we will describe several protocols that realize this definition, even when the vast majority of parties are malicious, while maintaining the asymptotic complexity of O(n + |C|).
(*) The per-party cost is O(n + |C|/n), where n is the number of parties, and |C| is the size of the circuit being computed. So, the claim of decreasing communication as n increases is really only true if a) |C| is independent of n, and b) |C| > n. For example, if training a large ML model, on some fixed-sized data set, among a few tens of thousands of parties; in this setting, adding more parties will help reduce the load on each participant.
Bio:
Dov is currently the Cryptography Architect at TripleBlind, while on a two year leave of absence from George Mason University, where he is an associate professor of computer science. His research is in cryptography, primarily in secure computation. His contributions have improved both the theory and practice of the field, with a particular focus on making secure computation practical. Prior to George Mason, Dov spent three years doing cryptographic research at Applied Communication Sciences, and two years as a postdoc at Columbia University, as a recipient of the Computing Innovations Fellowship. He received his PhD from the University of Maryland in 2010.
Galois was pleased to host this tech talk via live-stream for the public on March 29, 2023 from 12:30 pm to 1:30 pm Pacific Time. Please see above for the video recording of this talk.