International Association
for Cryptologic Research

This talk presents Argos: a viable path to make fully homomorphic encryption (FHE) deployable in real world scenarios where attackers cannot be assumed to be semi-honest. We demonstrate that trusted hardware can be securely used to provide integrity for FHE and other FHE-based protocols that implement functionalities such as private information retrieval (PIR) or private set intersection (PSI). We show that the major security pitfall of trusted hardware, \emph{microarchitectural} side channels, can be completely mitigated by excluding any secrets from the CPU and the memory hierarchy. This is made possible by focusing on building a platform that only enforces program and data \emph{integrity} and \emph{not} confidentiality (all that is required for verifiable FHE). All secrets can be kept in a separate co-processor (e.g., a TPM) inaccessible to an attacker. While relying on an off-CPU chip for attestation typically incurs significant performance overheads, our modified protocol turns it into a fixed-cost. Argos requires no dedicated hardware extensions and is supported on commodity processors from 2008 onward. Our hardware prototype executes 80 times faster than state-of-the-art on SGX, while introducing only 7\% overhead for FHE evaluation and 22\% for more complex protocols. By demonstrating how to combine cryptography with trusted hardware, Argos paves the way for widespread deployment of FHE-based protocols beyond the semi-honest setting.

Byzantine Broadcast (BB) is a central question in distributed systems, and an important challenge is to understand its round complexity. Under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant rounds, regardless of the number of nodes $n$. However, whether we can match the expected constant round complexity in the corrupt majority setting --- or more precisely, when $f \geq n/2 + \omega(1)$ --- remains unknown, where $f$ denotes the number of corrupt nodes. In this paper, we are the first to resolve this long-standing question. We show how to achieve BB in expected $O((n/(n-f))^2)$ rounds. In particular, even when 99\% of the nodes are corrupt we can achieve expected constant rounds. Our results hold under both a static adversary and a weakly adaptive adversary who cannot perform ``after-the-fact removal'' of messages already sent by a node before it becomes corrupt.