Geometry of Secure Computation
summary
Answers whether a two‑party randomized function is information‑theoretically securely computable by giving a finite procedure that reduces the problem to geometry, translates protocols to constrained optimization, and maps those constraints to lamination hull membership; it proves lamination hulls are semi‑algebraic and builds algebraic/algorithmic tools to test membership and extract a protocol when one exists. Works under perfect security in the plain model, handles infinite protocols, yields a decidable membership test; decision algorithms are effective but heavy (doubly‑exponential / a tower≈5 in the worst analysis), and 5‑output examples show arbitrarily large communication may be required.
AI-written summary · about
chapters (10)
- 0:00Introduction to the problem
- 1:52Research motivation
- 4:25Framework overview
- 8:39Understanding lamination hulls
- 12:23Geometric research problems
- 17:06Translation and application
- 20:53Revisiting Kushilevitz's work
- 23:37The Markov constraint
- 26:53Decidability and complexity
- 29:09Conclusion and Q&A
related talks
48mGeometry of Secure Computation
38mAdvisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
01h 00mSecure Computation 3
01h 08mSecure Computation 1
58mSecure Multiparty Computation I
01h 04mHow to Encrypt a Functionality
01h 09mCrypto + ML 1
22mComputational-Bounded Robust Compilation and Universally Composable Security