Theory Seminar

Computational Hardness of Optimal Fair Computation

Hemanta K. MajiAssistant ProfessorPurdue University

(Click “Event Website” above to access the zoom link.)

Abstract: Characterizing the limits of achievable security using the most conservative hardness of computation assumptions is one of the fundamental principles of cryptographic research. For instance, guaranteeing output delivery to honest parties when adversarial parties may abort prematurely during the protocol execution is significantly challenging. Against such powerful adversaries, the hardness of computation assumptions necessary and sufficient to achieve various security levels is relatively not well understood.

In the early 1980s, groundbreaking research introduced coin-tossing protocols using private-key cryptographic primitives to ensure that an adversary can change the honest party’s output distribution by at most 1/sqrt(r) in r-round protocols. Two decades later, a sequence of seminal results, relying on strong public-key cryptographic primitives, constructed protocols where an adversary can change the output distribution only by 1/r, which coincides with the optimal achievable security.

In light of these results, it is natural to wonder whether public-key cryptographic primitives are necessary to achieve this higher security threshold. Furthermore, do the coin-tossing protocols from the 1980s achieve the best possible security relying on private-key cryptographic primitives? This talk shall present recent results resolving these long-standing foundational problems in cryptography.

The key technical innovation is a potential-based proof-technique introduced in a sequence of our recent works.


Greg Bodwin


Euiwoong Lee