Average-case structure
Use planted problems and high-dimensional inference to formulate hardness conjectures that are natural, simple to state, and open to meaningful attack.
- Low-degree methods
- Sum-of-squares
- Statistical-query lower bounds
STOC TheoryFest 2026
Two-morning workshop
Building New Algorithmic Foundations for Cryptography
What new average-case problems could power the next generation of cryptography—and what new algorithms will we discover by trying to break them?
- Date
- June 25–26, 2026
- Time
- 8:30–11:00 a.m.
- Organizers
- Aayush Jain · Amit Sahai
Why this workshop, why now
Cryptography is at an algorithmic crossroads.
Theoretical cryptography has achieved a remarkable sequence of feasibility results—from public-key encryption and zero knowledge to fully homomorphic encryption and indistinguishability obfuscation.
Yet much of that progress rests on a surprisingly small set of hard-on-average problems. In the post-quantum setting, the concentration is sharper still: basic public-key tasks are dominated by noisy linear algebra, especially lattices and codes.
This workshop asks where the next generation of useful hardness conjectures should come from—and invites the algorithms community to help answer.
Either new hardness conjectures lead to new constructions, or their cryptanalysis produces algorithms and structural insight of independent interest.
The research agenda
A broader search space for hardness.
Post-quantum diversity
Explore hardness conjectures from codes, multivariate methods, combinatorial structures, and other underused sources of computational hardness.
Cryptographic usefulness
Ask which kinds of structure can plausibly support trapdoors, succinct proofs, homomorphism, obfuscation, and other central capabilities.
Win–win cryptanalysis
Treat failed hardness conjectures as progress: new attacks can expose decisive structure, sharpen conjectures, and reveal algorithms worth knowing in their own right.
Invited speakers
Five perspectives on the frontier.
Talk titles and the detailed program will be announced as they are finalized.
Average-case algorithms
Pravesh Kothari
Assistant Professor at Princeton University working on average-case complexity, high-dimensional statistics, and the sum-of-squares method.
Official profileComplexity & quantum
Ryan O’Donnell
Professor at Carnegie Mellon University whose research spans complexity theory, algorithms, analysis of Boolean functions, and quantum information.
Official profileQuantum algorithms
Noah Shutty
A researcher at Google Quantum AI focused on quantum algorithms, quantum error correction, fault tolerance, and the coding-theoretic ideas connecting them.
Research profileFoundational cryptography
Amit Sahai
Symantec Endowed Chair at UCLA whose work has shaped foundational cryptography, including attribute-based encryption, functional encryption, and obfuscation.
Official profileCombinatorial hardness
Isaac Hair
A theoretical computer scientist exploring cryptography from combinatorial average-case hardness conjectures, including public-key encryption based on planted clique and high-error CSPs.
Join the conversation
Help build what comes after today’s cryptographic foundations.
For algorithms researchers, cryptographers, complexity theorists, students, and anyone curious about the hardness—and easiness—of average-case problems.
Date
June 25–26
Thursday & Friday
Time
8:30–11:00
Each morning
Venue
STOC 2026
TheoryFest workshop