Secure Distributed Systems at Scale: From the Internet to Cyber-Physical Environments

Abstract

Secure distributed systems offer reliability and privacy guarantees that are crucial across applications ranging from blockchains and cloud computing to fault-tolerant distributed Cyber-Physical Systems (CPS). These protocols enable groups of mutually distrusting parties to collaborate and execute tasks at scale while maintaining robust security guarantees against faulty and adversarial behavior. Blockchains demonstrate that the reliability half of this promise is achievable in practice, with deployments spanning hundreds of parties over geo-distributed testbeds. The privacy half has {\it not} kept pace: despite rapidly growing demand from applications such as anonymous networks and privacy-preserving AI, systems at blockchain scale have been unable to offer privacy guarantees. At the other end of the spectrum, the reliability techniques that succeeded in the blockchain setting are far too expensive for emerging distributed CPS applications, where hardware and network conditions are substantially weaker. In both settings, existing solutions are too slow and resource-intensive to be deployed in practice. This thesis asks whether both guarantees can be delivered at the scale their applications demand, on the hardware those applications actually run on.The first half of this thesis builds Multi-Party Computation (MPC) protocols for systems with a hundred or more parties over real-world geo-distributed networks, motivated by modern blockchains. MPC enables $n$ mutually distrusting parties to jointly compute any function over their private inputs. We identify computationally expensive heavyweight cryptography based on number-theoretic hardness assumptions as the central scalability bottleneck and address it by designing protocols entirely using \emph{lightweight} cryptography such as symmetric-key encryption and cryptographic Hash functions. These tools are two orders of magnitude cheaper than heavyweight operations and additionally offer post-quantum security. We present three works in this line: HashRand, a random beacon protocol, Velox, an MPC protocol achieving fairness, and Aeternum, a framework for guaranteed output delivery in asynchronous MPC and dynamic proactive secret sharing. We implement and evaluate all three, showing that they outperform prior work by two orders of magnitude and scale to $100$ or more parties on geo-distributed testbeds with practical latency and communication costs.The second half turns to Asynchronous Approximate Agreement (AAA) for distributed CPS with a hundred or more parties, motivated by robot and drone swarms. Unlike randomized Byzantine Agreement (BA) protocols, which depend on expensive heavyweight cryptography to produce common coins, AAA protocols are deterministic and avoid these tools. These protocols still have a high cubic communication cost, which is unaffordable in the low-bandwidth CPS setting. We introduce \emph{Relaxed Validity}, an approximate validity property that allows nodes to trade the accuracy of the protocol's output for sub-cubic communication.Leveraging this property, we design SensorBFT and Delphi, both AAA protocols with sub-cubic communication overhead. We apply both to agreement problems in the CPS domain and experimentally demonstrate their scalability relative to prior works. Both consume an order of magnitude less energy than prior protocols based on randomized BA, a decisive metric on resource- and power-constrained sensor devices.