Interleaved Codes For Cryptography
summary
Interleaving increases decoding radius: vertical interleaving gives guaranteed unique decoding when the interleaving order l ≥ error rank t, turning many random vertically interleaved codes into an easy decoding problem; failure rates for probabilistic decoders sit around ~1/(q−1). Horizontal arrangements map to the rank support learning problem, which remains hard and underpins compact-key schemes. Classic GPT Gabidulin keys are broken by a q‑sum distinguisher; Loidreau’s subspace scrambler repair resists known attacks and vertical or horizontal interleaving trades smaller public keys against nonzero decryption-failure probabilities.
AI-written summary · about
chapters (21)
- 0:00Introduction
- 0:21Talk overview
- 1:52Post-quantum motivation
- 2:34Hamming metric codes basics
- 6:19Decoding Reed-Solomon codes
- 7:43McEliece cryptosystem
- 9:33Interleaved codes in McEliece
- 10:58Rank-metric codes intro
- 12:19Rank syndrome decoding
- 14:48Interleaved rank-metric types
- 17:38Horizontal interleaving challenges
- 19:07GPT cryptosystem vulnerabilities
- 21:42Loidreau’s scrambler repair
- 22:50Vertical interleaving in Loidreau’s
- 23:32Horizontal interleaving benefits
- 23:52Interleaving in cryptography
- 24:35Open problems
- 25:42Future directions
- 26:04Conclusion
- 26:51Q&A
- 29:22Q&A
related talks
01h 06mObfuscation: Past, Present, and Possible Futures
57mCoding for Interactive Communication
25mThe Whole is Greater than the Sum of its Parts: Linear Garbling and Applications
01h 00mA Brief History of Practical Garbled Circuit Optimizations
15mLESS is More for I/O-Efficient Repairs in Erasure-Coded Storage
01h 07mLattices and Encrypted Computation
01h 09mNew Developments in Multilinear Maps: Zeroizing Attacks, Defenses, and Post-Zeroizing Obfuscation
31mMulti-version Coding and Shared Memory Emulation