Hemanta Maji: Computational Hardness of Optimal Fair Computation

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.