Privacy Challenge #1

Suppose there are a number of space agencies that either have or are launching several satellites into orbit. Naturally, these agencies would like to ensure their satellites do not collide with each other. At the same time, each agency would like to protect the planned orbits.

Now, suppose a technique like multi-party computation is used whereby an orbit intersection function is calculated whereby the function takes as input each planned orbit and only reveals if there is an intersection.

Since space agencies might be competing countries that are malicious, a space agency might create false orbits to eventually deduce the actual orbits of another space agency. While commitments and non-malleable commitments might ensure that an adversary agency is unable to change their answer once submitted, nothing prevents an adversary probing by submitting careful orbits to try and deduce another space agencies orbits.

Question. Given polynomial number of queries by the competing space agency, what is the expected number of queries that needs to be run to deduce at least one competing orbit?