  Interpretability is often pointed out as a key requirement for trustworthy
machine learning. However, learning and releasing models that are inherently
interpretable leaks information regarding the underlying training data. As such
disclosure may directly conflict with privacy, a precise quantification of the
privacy impact of such breach is a fundamental problem. For instance, previous
work have shown that the structure of a decision tree can be leveraged to build
a probabilistic reconstruction of its training dataset, with the uncertainty of
the reconstruction being a relevant metric for the information leak. In this
paper, we propose of a novel framework generalizing these probabilistic
reconstructions in the sense that it can handle other forms of interpretable
models and more generic types of knowledge. In addition, we demonstrate that
under realistic assumptions regarding the interpretable models' structure, the
uncertainty of the reconstruction can be computed efficiently. Finally, we
illustrate the applicability of our approach on both decision trees and rule
lists, by comparing the theoretical information leak associated to either exact
or heuristic learning algorithms. Our results suggest that optimal
interpretable models are often more compact and leak less information regarding
their training data than greedily-built ones, for a given accuracy level.
