Optimizing Pseudorandom Correlation Generators from LPN
summary
Describes concrete PCG constructions that expand tiny setup keys into millions of correlated values by building VOLE→OT via hash from sparse secret-shared unit vectors, then compressing with dual LPN compression (generator G chosen as a high‑distance code). Reports code families (quasi‑cyclic, expand‑accumulate, expand‑convolute, block‑accumulate), warns one fast Silver design is broken, gives performance targets: about 160s → 33s → 10s → <1s per million OT-equivalents on CPU and 3 ms on GPU for the expansion.
AI-written summary · about
chapters (8)
- 0:00Introduction and motivation for VOLE
- 3:42VOLE’s role in generating Beaver triples
- 8:08Silent property and PCG framework
- 13:33Generating sparse vectors with punctured PRFs
- 17:27Optimizing matrix-vector multiplication for LPN
- 24:54Arithmetic circuits and OLE correlations
- 27:06Polynomial-based optimizations for OLE
- 31:37Performance comparison and Q&A
related talks
01h 06mOn the Assumptions Used for Obfuscation
23mGenerating Programs for Polynomial Multiplication with Correctness Assurance
40mImplementation
25mThe Whole is Greater than the Sum of its Parts: Linear Garbling and Applications
57mPseudorandom Hashing for Space-bounded Computation with Applications in Streaming
58mFast Cryptographic Code via Partial Evaluation
01h 00mA Brief History of Practical Garbled Circuit Optimizations
30mKEYNOTE Building Succinct Arguments from Ideal Hash Functions