Paper 2024/1117

Oryx: Private detection of cycles in federated graphs

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

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.

Available format(s)
Cryptographic protocols
Publication info
private cycle detection; private graph
Contact author(s)
kezhong @ seas upenn edu
sebastian angel @ cis upenn edu
2024-07-10: revised
2024-07-09: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.