PPP-completeness with connections to Cryptography
summary
Shows a reduction from Minkowski-style lattice search to PPP and proves a constrained SIS variant (solutions x in {−1,0,1}^n or infinity-norm ≤1 with m slightly larger than the image size) is WPP-complete by encoding NAND-circuit evaluation into an upper-triangular binary-invertible T matrix, using Smith normal form and modular parallelepiped maps. Builds a worst-case-to-collision construction — a key is a random A and T and the evaluator extends short seeds to solutions — yielding collision-resistant hash from constrained SIS and Minkowski → PPP.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:30DECISION PROBLEMS: P vs. NP
- 1:51COMPLEXITY OF TOTAL SEARCH PROBLEMS
- 2:53A COMPLEXITY THEORY OF TOTAL SEARCH PROBLEMS?
- 4:20NATURAL PROBLEMS
- 6:51POLYNOMIAL PIGEONHOLE PRINCIPLE
- 7:25POLYNOMIAL WEAK PIGEONHOLE PRINCIPLE
- 7:38PPP/PWPP AND CRYPTOGRAPHY
- 8:01PPP & LATTICES
- 11:34SHORT INTEGER SOLUTION (SIS) PROBLEM
- 14:28PWPP-COMPLETE PROBLEM: CONSTRAINED SIS
- 15:15BINARY INVERTIBLE MATRIX
- 18:41CONSTRAINED SIS IS PWPP-HARD
- 25:35POLYNOMIAL PARITY ARGUMENT
- 25:59POLYNOMIAL MODULO p ARGUMENT
- 26:55STRUCTURAL PROPERTIES
- 27:09CHEVALLEY-WARNING THEOREM
- 29:46FUTURE DIRECTIONS - INCLUSIONS
- 31:35FUTURE DIRECTIONS - HARDNESS
related talks
01h 04mThe Mathematics of Lattices II
58mSNARGs for P/poly from SIS
51mWhat Can and What Cannot Be Done by LP and SDP (An Incomplete Overview)
01h 08mTutorial on Proof Systems
01h 08mIncrementally Verifiable Computation for NP from Standard Assumptions
01h 40mHistorical Talk on Lattice-Based Cryptography
01h 08mThe Mathematics of Lattices I
40mPost-Quantum