Minimizing Operational Cost for Zero Information Leakage

While proper encryption can protect the confidentiality of messages in network protocols and distributed systems, private contents of messages may still leak from metadata, such as communication paths or message lengths. Many privacy strategies seal leakages by introducing noise into the system, e.g., by injecting dummy messages into the system. These solutions achieve a degree of privacy while introducing an overhead in operational cost, e.g., by transmitting information-less messages. In this paper, we show that randomization is never required for minimizing the operational cost of perfectly secure privacy strategies. While this result is surprising and counterintuitive, it allows for a simplification in the search for optimal solutions and in the analysis of the performance of the selected solutions.