A central insight of modern cryptography is that to guarantee the security and integrity of a task, it often suffices to defend against computationally bounded adversaries. This perspective aligns with how we model real world attackers and can enable outcomes that are provably impossible against unbounded adversaries. Although this idea has long been a driving force in cryptography and complexity theory, it has not been fully exploited in several natural and fundamental problems that have traditionally been studied in the unbounded adversary model.
In this talk, we show that adopting this computational perspective enables us to surpass information theoretic limits in three classic settings: communication, randomness, and privacy.
Communication: We construct efficient error correcting codes for computationally bounded adversaries that achieve information rates provably higher than those possible against unbounded adversaries.
Randomness: While seedless deterministic extraction is impossible for general sources, we show that it is possible to deterministically extract and condense randomness from low-entropy efficiently samplable sources.
Privacy: We consider two party differential privacy and show that achieving accuracy beyond information theoretic limits is tightly connected to cryptographic power, yielding a characterization of the computational assumptions that are necessary.
