Collision Based Uniformity Checking via Model Counting

Konstantinos Athanasiou

26 March 2019 at 01:30PM WVH 362

Abstract

Reasoning about security often entails reasoning about properties of distributions. In Hypothesis Testing, given sample access to a distribution q, we wish to test whether q satisfies a property p. In this work we investigate whether and how formal reasoning tools can be used to perform uniformity testing [1], i.e. to determine whether a given distribution is ε-close to the uniform distribution. We show that model counting can be used to perform uniformity testing and we present two uniformity testers that make use of both exact and approximate model counters.

  1. https://arxiv.org/abs/1611.03579