Paper 2024/1676

The Sting Framework: Proving the Existence of Superclass Adversaries

Abstract

We introduce superclass accountability, a new notion of accountability for security protocols. Classical notions of accountability typically aim to identify specific adversarial players whose violation of adversarial assumptions has caused a security failure. Superclass accountability describes a different goal: to prove the existence of adversaries capable of violating security assumptions. We develop a protocol design approach for realizing superclass accountability called the sting framework (SF). Unlike classical accountability, SF can be used for a broad range of applications without making protocol modifications and even when security failures aren’t attributable to particular players. SF generates proofs of existence for superclass adversaries that are publicly verifiable, making SF a promising springboard for reporting by whistleblowers, high-trust bug-bounty programs, and so forth. We describe how to use SF to prove the existence of adversaries capable of breaching the confidentiality of practical applications that include Tor, block-building infrastructure in web3, ad auctions, and private contact discovery---as well as the integrity of fair-transaction-ordering systems. We report on two end-to-end SF systems we have constructed---for Tor and block-building---and on experiments with those systems.