Abstract

In this chapter we focus on the nearest neighbor methods, because: (a) they are simple to reason about, and (b) we can identify the class of systems for which they will excel, which happens whenever the distribution is smooth with respect to a metric on the output, in the sense that it does not change too abruptly between two neighboring points. This is the case, for example, for time side channels, traffic analysis, and most mechanisms used for privacy.