MPC with Silent Preprocessing via Pseuodorandom Correlation Generators

on YouTube ↗01h 01m

" summary

Shows how to build pseudorandom correlation generators from LPN (and ring/dual-LPN) plus compressed primitives—distributed point functions and puncturable PRFs—so the expensive pre-processing is silent preprocessing: short seeds (sublinear storage/communication) locally expand into long correlated OT/OLE randomness. Gives a practical plug‑in for MPC with two‑round OT extension, near‑zero per‑OT communication (around 0.1 bits per OT claimed, ≈1000× reduction vs prior), concrete implementations generating millions of random OTs in seconds, and malicious security with only small extra setup cost.

AI-written summary · about

" chapters (23)

1. 0:00Secure multi-party computation (MPC)
2. 0:46Secure MPC with preprocessing
3. 2:02Pseudorandom correlation generator (PCG)
4. 9:00Secure MPC with silent preprocessing
5. 10:09Generic construction of PCGS General additive correlations
6. 12:37Landscape of PCGS
7. 15:42Learning with errors vs. learning parity with noise
8. 16:47Cryptography from LWE vs. LPN
9. 18:15A simple PRG from LPN
10. 19:44Why LPN is a perfect match for PCGS
11. 20:50How to distribute a sparse vector efficiently
12. 24:26Oblivious transfer (OT)
13. 26:21Comparison of OT extension protocols 128-bit security Reference
14. 32:471b. Puncturable pseudorandom function
15. 34:171c. PCG for unit vector via PPRF
16. 37:281d. 2-Round setup for unit vector
17. 38:07From unit to sparse vectors
18. 38:47From sparse to pseudorandom vectors
19. 40:13PCG for correlated OT from LPN - Recap
20. 45:51Oblivious linear evaluation (OLE)
21. 48:02PCG for OLE via LPN
22. 50:58More efficient PCG for OLE from ring-LPN
23. 56:14Conclusion

" related talks

• 01h 03mSecure Computation 2Elette Boyle · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 40mApplied MPCNigel Smart · RSAC 2021
• 01h 08mSecure Computation 1Peter Scholl · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 35mOblivious RAM for MPCStanislaw Jarecki · Securing Computation (Simons Institute, June 2015)
• 29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round CollapsingVipul Goyal · Secure Computation 2025
• 57mIndistinguishability Obfuscation from Well-Founded AssumptionsAayush Jain · Simons Institute Workshop: New Developments in Obfuscation
• 44mLPN Based IO Part 1Amit Sahai · Simons Institute Workshop: New Developments in Obfuscation
• 30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain ModelLuisa Siniscalchi · Secure Computation 2025