There is an increasing need for financial institutions to be able to detect illicit activities such as money laundering. While these institutions currently rely on graph-based analytics or machine learning algorithms for such detection, inter-bank collaboration is hindered by privacy concerns and regulations. In this paper, we introduce a new protocol for computing simple fundamental graph features (specifically fan-in and fan-out degrees) directly on encrypted transaction data using the advantages of additive homomorphic encryption schemes, especially the Paillier cryptosystem. Our algorithm allows a semi-trusted third party to perform computations without accessing plaintext data, enabling privacy-preserving collaboration between banks. Through the paper, we detail the protocol design, analyze its complexity, security and correctness, and demonstrate how it reduces the gap between utility and privacy. While the protocol currently supports only basic graph metrics and assumes a common normalized currency, it offers a scalable and practical foundation for future privacy-preserving financial crime analytics.