A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

Explore a comprehensive analysis of adaptively secure full-information coin flip protocols in this 18-minute IEEE conference talk. Delve into the tight lower bound presented by Iftach Haitner and Yonatan Karidi-Heller from Tel Aviv University. Examine key concepts such as coin-flipping protocols, full-information coin flip, and adaptive adversaries. Investigate the expected outcome martingale, protocol jumps, and techniques for exploiting variance for biasing. Learn about attacking robust single-turn protocols and the challenges faced in non-robust protocols. Gain insights into the analysis, attack approach, and potential future works in this field of cryptography.

Syllabus

Coin Flipping
Coin-Flipping Protocols [Blum '82]
Full-Information Coin Flip [Ben-Or and Linial 85]
Adaptive Adversaries
Our Result
Talk Outline
The Expected Outcome Martingale
Protocol Jumps - A Closer Look Fix n-party single-turn (n-round) protocol II, and try biasing it.
Exploiting Variance for Biasing
Attacking Robust (Single-Turn) Protocols Fix some small function (1), we will usually ignore it.
Analysis
Non-Robust Protocols
Main obstacles
Attack Approach
Summary, Future Works and Open Questions