Paper 2024/1117
Oryx: Private detection of cycles in federated graphs
, University of PennsylvaniaAbstract
This paper proposes Oryx, a system for efficiently detecting cycles in federated graphs where parts of the graph are held by different parties and are private. Cycle detection is an important building block in designing fraud detection algorithms that operate on confidential transaction data held by different financial institutions. Oryx allows detecting cycles of various length while keeping the topology of the graphs secret, and it does so efficiently; Oryx achieves quasilinear computational complexity and scales well with more machines thanks to a parallel design. Our implementation of Oryx running on a single 32-core AWS machine (for each party) can detect cycles of up to length 6 in under 5 hours in a financial transaction graph that consists of tens of millions of nodes and edges. While the costs are high, Oryx’s protocol parallelizes well and can use additional hardware resources. Furthermore, Oryx is, to our knowledge, the first and only system that can handle this task
Note: Fixed many typos.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- private cycle detection; private graph
- Contact author(s)
-
kezhong @ seas upenn edu
sebastian angel @ cis upenn edu - History
- 2024-09-05: last of 3 revisions
- 2024-07-09: received
- See all versions
- Short URL
- https://ia.cr/2024/1117
- License
-
CC BY-SA
BibTeX
@misc{cryptoeprint:2024/1117,
author = {Ke Zhong and Sebastian Angel},
title = {Oryx: Private detection of cycles in federated graphs},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1117},
year = {2024},
url = {https://eprint.iacr.org/2024/1117}
}
