  In privacy-preserving multi-agent planning, a group of agents attempt to
cooperatively solve a multi-agent planning problem while maintaining private
their data and actions. Although much work was carried out in this area in past
years, its theoretical foundations have not been fully worked out.
Specifically, although algorithms with precise privacy guarantees exist, even
their most efficient implementations are not fast enough on realistic
instances, whereas for practical algorithms no meaningful privacy guarantees
exist. Secure-MAFS, a variant of the multi-agent forward search algorithm
(MAFS) is the only practical algorithm to attempt to offer more precise
guarantees, but only in very limited settings and with proof sketches only. In
this paper we formulate a precise notion of secure computation for search-based
algorithms and prove that Secure MAFS has this property in all domains.
