SaTC: CORE: Small: Optimal Coin-flipping Protocols

Achieving optimal robustness against adversarial behavior using minimum resources is central to all information sciences. However, the understanding of the impact of adversarial behavior in distributed protocols and the optimal defense against them is far from complete. Collective coin-flipping is an elegant functionality providing uncluttered access to the primary bottlenecks of achieving security in any adversarial model.

The project's novelties are to simultaneously bound the insecurity of any coin-flipping protocol against adversaries and characterize the protocol that achieves maximum security.

Typically, establishing lower bounds for insecurity and constructing protocols with high security require different analysis tools and techniques. The project's innovation is an inherently constructive inductive approach that unifies these two aspects of protocol design and analysis. Accomplishing the technical goals outlined in this project requires several specific contributions: modeling coin-tossing protocols as tree traversals, characterizing the susceptibility of a protocol to adversarial attacks, creating potential functions to estimate the susceptibility accurately, and completing an inductive argument that constructs the optimal protocols.

The project's impacts are widespread, spanning distributed protocol design and cryptographic protocol design.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.