Tight Bounds on Information Leakage from Repeated Independent Runs
David M. Smith, Geoffrey Smith · 2017
We investigate a problem in quantitative information flow, namely to find the maximum information leakage caused by n repeated independent runs of a channel C with b columns. While this scenario is of general interest, it is particularly motivated by the study of timing attacks on cryptography implemented using the countermeasures known as blinding and bucketing. We measure leakage in terms of multiplicative Bayes capacity (also known as min-capacity) and we prove tight bounds that greatly improve the previously-known ones. To enable efficient computation of our new bounds, we investigate them using techniques of analytic combinatorics, proving that they satisfy a useful recurrence and (when b = 2) a close connection to Ramanujan's Q-function.