SaTC: CORE: Small: Optimal Coin-flipping Protocols

使用最少的资源实现对抗性行为的最佳鲁棒性是所有信息科学的核心。然而，对分布式协议中对抗行为的影响以及对它们的最佳防御的理解还远远没有完成。集体抛硬币是一个优雅的功能，它提供了对任何对抗模型中实现安全性的主要瓶颈的整洁访问。该项目的新颖之处在于同时限制任何硬币翻转协议对对手的不安全性，并描述实现最大安全性的协议。通常，建立不安全性的下限和构建具有高安全性的协议需要不同的分析工具和技术。该项目的创新是一个内在的建设性归纳方法，统一了这两个方面的协议设计和分析。实现该项目中概述的技术目标需要几个具体的贡献：将抛硬币协议建模为树遍历，描述协议对对抗性攻击的敏感性，创建潜在函数以准确估计敏感性，并完成构建最佳协议的归纳论证。 该项目的影响是广泛的，跨越分布式协议设计和加密协议设计。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.