Secure aggregation is the distributed task of securely computing a sum of values (or a vector of values) held by a set of parties, revealing only the output (i.e., the sum) in the computation. Existing protocols, such as Prio (NDSI’17), Prio+ (SCN’22), Elsa (S&P’23), and Whisper (S&P’24), support secure aggregation with input validation to ensure inputs belong to a specified domain. However, when malicious servers are present, these protocols primarily guarantee privacy but not input validity. Also, malicious server(s) can cause the protocol to abort. We introduce SCIF, a novel multi-server secure aggregation protocol with input validation, that remains secure even in the presence of malicious actors, provided fewer than one-third of the servers are malicious. Our protocol overcomes previous limitations by providing two key properties: (1) guaranteed output delivery, ensuring malicious parties cannot prevent the protocol from completing, and (2) guaranteed input inclusion, ensuring no malicious party can prevent an honest party’s input from being included in the computation. Together, these guarantees provide strong resilience against denial-of-service attacks. Moreover, SCIF offers these guarantees without increasing client costs over Prio and keeps server costs moderate. We present a robust end-to-end implementation of SCIF and demonstrate the ease with which it can be instrumented by integrating it in a simulated Tor network for privacy-preserving measurement.

In this work, we introduce a lightweight secure aggregation protocol that guarantees liveness (i.e., guaranteed output delivery), robust against faulty inputs and security against malicious clients. First, we improve upon prior works in the “star”-like topology network with a central coordinating (also output) party, Bonawitz et al. (ACM CCS 2017) and Bell et al. (ACM CCS 2020), which are not robust against faulty inputs. Recent works, RoFL (Burkhalter et al.) and (concurrent work) ACORN (Bell et al.) show how to rely on zero-knowledge proofs to address such attacks at expense of significantly high computation costs. We also compare our protocol against the PRIO system by Gibbs and Boneh (USENIX 2017) which achieves the same task in an incomparable security model. We benchmark our protocol with implementation and demonstrate its concrete efficiency. Our solution scales to 1000s of clients, requires only a constant number of rounds, outperforms prior work in computational cost, and has competitive communication cost.

The problem of Byzantine Agreement (BA) is of interest to both the distributed computing and cryptography communities. Following well-known results from distributed computing literature, the BA problem in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavors of termination guarantee—with overwhelming probability and with probability one. The latter type, termed as almost-surely terminating BA, is the main focus of this article. An eluding problem in the domain of almost-surely terminating BA is achieving a constant expected running time. Our primary contribution in this work makes significant progress in this direction. In a setting with n parties and an adversary with unbounded computing power controlling at most t parties in a Byzantine fashion, we present two almost-surely terminating BA protocols in the asynchronous setting: ○ With the optimal resilience of t < n /3, our first protocol runs for an expected O ( n ) time. The existing protocols in the same setting either run for an expected O ( n 2 ) time (Abraham et al., PODC 2008) or require exponential computing power from the honest parties (Wang, CoRR 2015). In terms of communication complexity, our construction outperforms all the known constructions with t < n /3 that offer almost-surely terminating feature. ○ With the resilience of t < n /3 + ϵ for any ϵ > 0, our second protocol runs for an expected O (1/ϵ) time. The expected running time of our protocol turns constant when ϵ is a constant fraction. The known constructions with a constant expected running time either require ϵ to be at least 1 (Feldman-Micali, STOC 1988 and Patra-Pandu Rangan, PODC 2010), implying t < n /4, or call for exponential computing power from the parties (Wang, CoRR 2015). We follow the traditional route of building BA via common coin protocol that in turn reduces to Asynchronous Verifiable Secret-Sharing (AVSS). Our constructions are built on a variant of AVSS that is termed as shunning . A shunning AVSS fails to offer the properties of AVSS when the corrupt parties strike, but allows the honest parties to locally detect and shun a set of corrupt parties for any future communication. Our shunning AVSS with t < n /3 and t < n /3 + ϵ guarantee Ω( n ) and, respectively, Ω(ϵ t 2 ) conflicts to be revealed when failure occurs. Turning this shunning AVSS to a common coin protocol efficiently constitutes yet another contribution of this work. As a secondary contribution, we show the power of the shunning technique and present a highly efficient cryptographically secure shunning AVSS, which is used further to design an asynchronous BA protocol with the optimal resilience of t < n /3 in the cryptographic setting. Our construct achieves an amortized expected communication complexity of O ( n 2 ) bits for reaching agreement on a single bit while consuming a constant expected running time. This property has been achieved for the first time in the cryptographic setting and that, too, with standard cryptographic assumptions. The best-known existing construction (Cachin et al., CCS 2002), while still needing more communication complexity than ours, is proven secure only in the Random-Oracle Model (ROM).