Paper 2024/1117

Oryx: Private detection of cycles in federated graphs

Ke Zhong, University of Pennsylvania
Sebastian Angel, University of Pennsylvania
Abstract

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, adding more machines further reduces the completion time. Furthermore, Oryx is, to our knowledge, the first and only system that can handle this task.

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-07-10: revised
2024-07-09: received
See all versions
Short URL
https://ia.cr/2024/1117
License
Creative Commons Attribution-ShareAlike
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},
      note = {\url{https://eprint.iacr.org/2024/1117}},
      url = {https://eprint.iacr.org/2024/1117}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.