Secure Computation and Low-Complexity Cryptography
summary
Claims that semi-honest two‑party computation attains constant overhead for semi-honest 2PC by reducing general Boolean circuits to long‑string OTs and unbalanced NC0 garbling; an EMVP/semantic‑search functionality achieves asymptotic overhead 1 for encrypted matrix‑vector product under plausible assumptions; practical estimates put AES and SHA‑256 at ~100× amortized circuit cost, FHE at ~10,000×, and local PRGs with output locality 4, degree‑3 randomized encoding (NC0) compile many primitives into low‑complexity forms; AMD circuits and MRE give degree‑2 encodings with preprocessing.
AI-written summary · about
chapters (18)
- 0:00Workshop introduction
- 2:33Secure computation basics
- 8:46Optimizing metrics
- 13:13Circuit models and cost
- 17:35Overhead in cryptographic primitives
- 22:33Efficiency estimates
- 30:02Hash functions and complexity
- 32:55Two-party computation optimizations
- 37:17Constant overhead techniques
- 40:32Minimizing rounds
- 43:29Round complexity open questions
- 47:14Reducing to simple functions
- 51:12Randomized encodings
- 55:34Beyond NC1 encodings
- 58:25Practical MPC with many parties
- 1:00:38Low-complexity open problems
- 1:03:35Sublinear secure computation
- 1:04:41Concluding remarks
related talks
01h 08mSecure Computation 1
58mObfuscation 2
01h 00mSecure Computation 3
01h 03mSecure Computation 2
25mFaster Malicious 2-Party Secure Computation with Online/Offline Dual Execution
01h 04mHow to Encrypt a Functionality
10mCryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation
53mLPN Based IO Part 2