In multi-agent planning, agents jointly compute a plan that achieves mutual goals, keeping certain information private to the individual agents. Agents’ coordination is achieved through the transmission of messages, but they can be a source of privacy leakage as they can permit a malicious agent to collect information about other agents’ search processes and states. In this paper, we investigate the usage of novelty techniques in the context of (decentralised) multi-agent privacy preserving planning, addressing the challenges related to the agents’ privacy and performance. In particular, we show that novelty based techniques allow a significant reduction on the number of messages transmitted among agents, increasing their privacy levels and also their performances. An experimental study analyses the effectiveness of our techniques and compares them with the state of-the-art. Finally, we examine the robustness of our approach considering different delays in the messages transmission as would occur in overloaded networks, due for example to massive attacks or critical situations.