Assumptions in cryptography and complexity theory
summary
Panelists debate concrete examples: reductions matter more than vague claims, and Strong ETH is treated as a research muse because attempts to refute it spur CNF-SAT algorithms aiming for ~1.9^n time; indistinguishability obfuscation (IO) repeatedly appears as a powerful but nonfalsifiable assumption that yields many cryptographic primitives and some unconditional consequences in oracle models; range-avoidance and randomness/derandomization conjectures are suggested as target assumptions whose truth or falsity would produce broadly useful explicit constructions.
AI-written summary · about
chapters (10)
- 0:00Philosophy of assumptions
- 2:14Reductions vs assumptions
- 4:33Cultural differences in research
- 5:36Refutation and progress
- 12:41Good vs bad assumptions
- 15:37Evaluating assumptions
- 17:44Historical context and simplicity
- 20:44Future research directions
- 23:28Hardness and derandomization
- 25:56Exotic models and conclusions
related talks
49mPanel Discussion: Computational Assumptions
44mThe Cryptographers' Panel
10mCryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation
01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristic
01h 01mThe Gospel According to TCS
59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-Versa
35mCryptographic Agents: Towards a Unified Theory of Computing on Encrypted Data
01h 09mCrypto + ML 1