Geometry of Secure Computation
summary
Presents a geometric characterization of information‑theoretic two‑party secure computation that encodes every b‑bit protocol as a point and reduces existence to a membership test in a new generalized convex hull (lamination convex hull) built with tools from real algebraic geometry and tropical algebra. Produces a constructive embedding and an automated verification procedure, and exhibits a surprising optimal counterexample: a randomized task with 5 outputs that forces statistical but not perfect security.
AI-written summary · about
chapters (22)
- 0:00Intro
- 1:04Cryptographic Context
- 1:37Research Team
- 2:12Security & Application Domains
- 2:42Efficiency of Secure Computation
- 3:09Today's Talk: A Summary
- 5:39Revisit: Convex Hull
- 10:55Sneak Peek: Generalized Convex Hulls
- 15:38Wormhole
- 18:46Connection: Relative Convex Hull
- 20:06Connection: Lamination Convex Hull
- 23:21Problem: Communication Complexity of Secure Computation
- 25:33Kushilevitz's Characterization: Illustrative Example (Auction Functionality)
- 26:07Kushilevitz's Characterization: Illustrative Example (Dutch Auction - Secure Protocol for the Auction Functionality)
- 27:10Kushilevitz's Characterization: What is not Secure?
- 27:46Kushilevitz's Characterization: Decomposable Functions
- 29:36Interlude: Markov Constraint
- 31:59Inspiration: Our Reinvention of Kushilevitz's Characterization
- 34:08Our New Perspective on Security
- 35:47Our Mathematical Solution: High-level Overview
- 37:49A Discussion: Similar Interdisciplinary Research
- 38:34A Randomized Output Function Example
related talks
33mGeometry of Secure Computation
01h 00mSecure Computation 3
12mOne-Way Functions Imply Secure Computation in a Quantum World
58mSecure Multiparty Computation I
01h 06mSecure Computation and Low-Complexity Cryptography
01h 08mSecure Computation 1
01h 04mHow to Encrypt a Functionality
10mCryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation