Jiatu Li | How to build cryptography from proof complexity
Keywords
Summary
185 words
Critical Evaluation
Value of the Information & Strength of the Argument
The value of the information is high: it outlines a genuinely novel link between two deep areas of theoretical computer science and presents a concrete theorem with a proof sketch. The argumentation is solid but relies on a rather non-standard assumption (that proving extended Frege lower bounds is itself unprovable in a weak theory), which is non-falsifiable in the usual cryptographic sense. The speaker is careful to define all terms and engages productively with audience questions, clarifying subtle points about the strength of the assumption and the role of the proof system. The reasoning is incremental and builds on prior work (Jain et al.), showing how formalisation in bounded arithmetic is the key step. Overall, the argument is compelling within the formal framework, though the ultimate cryptographic relevance depends on the plausibility of the non-falsifiable assumption.
Scientific Rigor, Source Quality, Title Accuracy
The rigor is high: the talk is given at the Isaac Newton Institute, and the speaker explicitly cites prior work (Ilango 2025, Jain et al. 2021, JKL 2024, Krajíček & Pudlák, Razborov, Kilian & Micali, Sahai & Waters). The formal definitions are precise, and the notation is consistent. The title accurately matches the content, and the slides/blackboard appear well-organised. However, the talk is a research seminar, not a peer-reviewed publication, and some statements are presented as intuitive sketches rather than fully rigorous proofs. The description provides links to the institute and the seminar page, which serve as verifiable references for the event. No inconsistencies or unsupported claims were noticed, aside from the inherent reliance on unproven assumptions typical of research-level talks.
272 words
Title / Content Match
The title accurately reflects the seminar content: the speaker explains how to build cryptographic constructions starting from assumptions about the unprovability of proof complexity lower bounds.
Quality & Reliability
8/10
The talk presents rigorous mathematical definitions and proofs, given by a specialist at a recognized research institution. However, the results are not yet peer-reviewed and the presentation is informal with many audience interruptions.
Key Moments
Markers derived by PSI from the transcript: the creator did not define chapters.
- Introduction and motivation from recent work by Rahul Ilango on zero-knowledge proofs and trusted setup.
- Discussion of the open problem in proof complexity: proving extended Frege lower bounds from computational assumptions, with references to Krajíček and Pudlák.
- Formal definition of SNARKs, including completeness, succinctness, and soundness, and the role of a trusted setup.
- Presentation of the main assumption about the unprovability of extended Frege lower bounds, and clarification of its non-falsifiable nature.
- Sketch of the reduction: formalising the JKL scheme in a weak bounded arithmetic theory and using the assumed unprovability to conclude soundness.
- Follow-up work on proof complexity generators and connections to the hardness of proving incompressibility.
- Conclusion and open questions; mention of future work.
Cited Sources
- Isaac Newton Institute for Mathematical Sciences — General institutional homepage.
- Seminar: How to build cryptography from proof complexity — Event page with programme information.
Contribution & Novelties
The talk introduces a novel bridge between proof complexity and cryptography, showing that a specific non-falsifiable assumption about the unprovability of extended Frege lower bounds can be used to construct SNARKs for NP. This is a significant conceptual contribution, as it suggests a new route to bypass known barriers in cryptography. The work also demonstrates that complex cryptographic security proofs can be formalised in very weak logical theories, which may have broader implications.
Pour aller plus loin :
- Proof complexity — Foundational area discussed; key to the talk’s main question.
- Extended Frege system — The proof system whose lower bounds are central to the assumption.
- Zero-knowledge proof — Related to the cryptographic motivation mentioned at the start.
- Learning with errors — A standard cryptographic assumption referenced as part of the base assumptions.
132 words
Radar Profile
The radar profile shows very high technical level and information quality, with slightly lower quantitative breadth and reliability scores. This is expected for a specialised research seminar where depth is prioritised over breadth and where assumptions are non-verifiable.