Lattice Trapdoors
summary
Constructs practical lattice trapdoors by fixing a gadget matrix G (powers-of-two), showing how small Gaussian R yields a randomized public matrix A = [B | G − B·R] that is indistinguishable from uniform (leftover-hash lemma), and reducing inversion on A to inversion on G. Implements preimage sampling via discrete Gaussians (randomized nearest-plane) and a perturbation step that fixes leaked covariance, so type-two trapdoor R implies a short-basis type-one trapdoor and supports IBE/functional-encryption-style schemes.
AI-written summary · about
chapters (8)
- 0:00Start
- 3:10Access Control on Encrypted Data
- 5:30Trapdoor Functions
- 6:19Short Integer Solution Problem
- 8:12Lattice Based One Way Functions
- 9:44Inverting functions for Crypto
- 27:08Randomize G to A
- 29:04Leftover Hash Lemma (oversimplified)
related talks
01h 04mThe Mathematics of Lattices II
57mLattice Assumptions with Hints: Succinct LWE and its Applications
57mTutorial: Encrypted Computation from Lattices
54mGraph-Induced Multilinear Maps from Lattices
31mIdentity-Based Encryption
01h 03mLockable Obfuscation
33mA New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
44mLattices with Symmetry