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.