Secure Distributed Network Optimization Against Eavesdroppers
summary
Claims an f-secure CONGEST framework that protects against an oblivious, computationally unbounded eavesdropper who sees all messages on up to f edges, with statistical security holding w.h.p. Key tool is a congestion-sensitive compiler that converts any algorithm with edge congestion C into an equivalent secure one with additive round overhead about D + f·√(C·n) + C·f (polylog factors suppressed). Also gives a bespoke secure MST: Boruvka-based, produces basic trees of diameter O(√n log n), uses ~√n landmarks, runs in ~log n phases and matches non-secure bounds for f up to polylog(n).
AI-written summary · about
chapters (9)
- 0:00Introduction
- 0:13Distributed model
- 1:07Goal
- 2:18Previous work
- 3:34Minimum Spinning
- 4:13Security
- 5:08General Compiler
- 12:52Secure MST
- 18:16Summary
related talks
33mInteraction Preserving Compilers for Secure Computation
30mRethinking Secure Computation - A Greedy Approach
19mDefending against Traffic Analysis Attacks with Flexible In-Network Obfuscation
33mError Correction for Streaming Messages
25mHardening Confidential Federated Computations against Side-Channel Attacks
40mSymmetric Design
01h 03mAdversarially Robust Streaming Algorithms
31mCommSec D1 - Steganography Ante Portas