When Cryptography Meets Modern Channel Coding
summary
Constructive families of lattices (Construction A with LDPC/GLD codes) reach the Poltyrev threshold, with Sigma_max = V^{2/n}/(2πe), by letting the alphabet size P grow like P = (log n)^a under a mild constraint on a and the code rate. Analysis uses sphere hardening, integer-point counting and a saddle-point/buckets estimate to upper-bound error. An iterative local decoder corrects errors in practice in ~40 iterations with complexity roughly linear in n; simulations reach dimension 1,000,000 within 0.3 dB of the limit and SER→0.
AI-written summary · about
chapters (11)
- 0:00Intro
- 3:15Noise
- 11:08Construction of Lattices
- 15:45Algebraic Constructions
- 20:53Sigma Max
- 25:33Sphere Hardening
- 27:29Decoding
- 32:37Counting
- 44:55LDPC
- 46:14GLD lattice
- 47:28Example
related talks
41mHigh-Rate Fair-Density Parity-Check Codes
46mCodes with the multiplication property
44mCoding Theory in Almost Linear Time and Sublinear Space
01h 08mCryptography from Ideal Lattices
37mRelaxed Local Correctability from Local Testing
48mList Decoding of Tanner and Expander Amplified Codes...
39mGilbert and Varshamov meet Johnson: List Decoding Nearly-Optimal Binary Codes
39mLattice Based Cryptography Primer