The Short Integer Solutions Problem and Cryptographic Applications
summary
Defines SIS as solving A·x ≡ y (mod q) for short x (typically n, m, q matrix A and x in {0,1}^m), proves average-case hardness by reducing worst-case lattice problems (SIVP/CVP, approx factor ≈ n) to random SIS keys using worst-case to average-case reduction via smoothing and discrete Gaussian, shows q can be pushed down toward √n, notes structured rings (negacyclic/power‑of‑two) for linear-time keys but warns simple cyclic matrices admit easy collisions, and derives collision‑resistant hashes, commitments and one‑time signatures.
AI-written summary · about
chapters (11)
- 0:00Start
- 2:02Outline
- 5:51CVP and dual lattice
- 8:05SIS/LWE as CVP
- 15:10Ajtai's one-way function (SIS)
- 23:47Ajtai's function and lattice problems Cryptanalysis (Inversion)
- 29:58Ajtai's function: collision resistance
- 35:25Provable security (from average case hardness)
- 40:47Provable security (from worst case hardness)
- 55:34Ajtai's connection
- 58:02Reducing g in SIS (proof sketch, toy version)
related talks
01h 08mThe Mathematics of Lattices I
01h 04mThe Mathematics of Lattices II
01h 08mCryptography from Ideal Lattices
58mSNARGs for P/poly from SIS
01h 40mHistorical Talk on Lattice-Based Cryptography
39mLattice Based Cryptography Primer
37mPPP-completeness with connections to Cryptography
01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a Survey