Rethinking Secure Computation - A Greedy Approach
summary
Proposes that many graph and geometric problems (median, convex hull, MST, job scheduling, single‑source shortest paths approximations) are computable securely by a greedy protocol that uses only secure comparisons, gives the median in O(log n) rounds with per‑round secure comparisons, and achieves communication proportional to output size rather than input size. Requires unique solution, unique greedy order, and local updateability. Extends median to malicious via input extraction, gives covert security with commitments, signatures and O(1) witnesses (triangle for convex hull); open: malicious, OT‑hybrid, communication‑optimal construction.
AI-written summary · about
chapters (6)
- 0:00Start
- 2:03SECURE COMPUTATION OF MEDIAN
- 4:35WALK THROUGH
- 5:15PROVING SECURITY (honest-but-curious case)
- 15:25Matroid Set Systems
- 18:57SECURE MEDIAN COMPUTATION
related talks
19mSecure Distributed Network Optimization Against Eavesdroppers
33mInteraction Preserving Compilers for Secure Computation
01h 31mIntroduction to Secure Multi-Party Computation
14mDivide and Conquer: A Compositional Approach to Game-Theoretic Security
52mGame-Theoretically Secure Protocols Inspired by Blockchains
22mNext-Gen PeT: the Future of Multi-Party Computation Software
37mFrontiers in Cryptography
27mComputation Over the Noisy Broadcast Channel with Malicious Parties