Optimal Mechanisms Under Maximal Leakage
Benjamin V. Wu, Aaron B. Wagner, G. Edward Suh · 2020
Side channels represent a broad class of security vulnerabilities in practical systems. Because completely eliminating side channels often leads to prohibitively high overhead, there is a need for principled techniques that trade off cost and leakage. Maximal leakage (MaxL) has been introduced as an operationally-interpretable leakage metric well-suited to side channels. We study the optimal trade-off between MaxL and expected costs. We demonstrate that for an important class of cost functions, optimal protection can be achieved using a combination of at most two deterministic schemes. We discuss the implications of this result for practical implementation and provide a fast heuristic algorithm for finding the best deterministic mechanism, which has a bounded suboptimality guarantee.