GraphAce: Secure Two-Party Graph Analysis Achieving Communication Efficiency
summary
Claims a secure two-party graph analysis framework that removes any network traffic tied to edges and achieves Theta(|V|) communication per iteration while keeping Theta(|V|+|E|) computation. It uses a mixed primitives approach (homomorphic encryption plus secret sharing) and a novel ChaosTable position-mapping data structure to hide vertex sets, supports end-to-end conversion from local subgraphs without a helper, targets semi-honest security, and processes >1M vertices/132M edges with up to 10k× speedups and up to 99.99% communication savings.
AI-written summary · about
chapters (9)
- 0:00GraphAce project
- 2:40Secure graph analysis
- 5:33Problem and security goals
- 7:19Insecure two-party analysis
- 9:50Protecting weights with crypto
- 11:37Ensuring obliviousness
- 13:27Full workflow and proof
- 14:33Experimental results
- 18:10Conclusion and future
related talks
01h 06mSecure Computation and Low-Complexity Cryptography
35mDistributed Models for Private Analysis of Graph Data
01h 08mSecure Computation 1
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...
48mGeometry of Secure Computation
25mErasure-Resilient Sublinear-Time Graph Algorithms
27mMetadata-private data transfer
12mTEGRA: Efficient Ad-Hoc Analytics on Evolving Graphs