We have developed a framework for efficient privacy preserving multi-party querying (PPMQ) over federated graph databases, leveraging Secure Multi-Party Computation (SMPC) protocols to enhance data security. The system offers two distinct security protocols: a client-based protocol and a server-based protocol. In the client-based protocol, standard SMPC techniques are employed, allowing computations to be performed on data without exposing the data itself. The server-based protocol employs SMPC to facilitate secure data processing and is further enhanced by encrypted hashing, which adds an additional layer of security to prevent data exposure. We conducted experiments comparing PPMQ with Neo4j Fabric and two previous systems, SMPQ and Conclave. The results indicate that PPMQ’s execution times and overheads are comparable to those of Neo4j Fabric, while outperforming both SMPQ and Conclave, demonstrating its superior efficiency. Additionally, PPMQ, like SMPQ and Conclave, utilises an honest but curious security model. However, it enhances the security of the server protocol, making it more robust against brute force attacks and providing stronger privacy guarantees than previous solutions.