Conditional Sampling and Property Testing of Probability Distributions for Cryptographic Applications

Hypothesis testing on probability distributions has a wide range of applications, including Statistical Learning Theory and Cryptography. The problem asks to determine, with some “confidence”, whether an unknown probability distribution D over a domain S satisfies certain property (null hypothesis) or it is statistically far from any distribution having that property (alternate hypothesis). Traditional statistical tests follow the standard sampling model, where the tester can draw independent samples following D. Efficiency of statistical or algorithmic testers is measured by the sample complexity. For testing whether a distribution is uniform, information-theoretic lower bounds force any algorithm or statistical test to draw at least √|S| samples from D. If S is the set of 256-bit binary strings, the above bound translates to requiring 2^128 many samples! Security of cryptographic constructions, in particular candidate pseudorandom functions and permutations, is crucially reliant on the infeasibility of efficient testing of probability distributions.

The recently introduced framework of Conditional Sampling surprisingly allows efficient testing with sample complexity of O(log |S|) and sometimes even independent of |S|. In this framework, the tester is allowed to draw samples from D conditioned on an arbitrary subset of S. The specific topic of interest is the subcube conditional framework, where the conditioning is done by fixing some bits of the output and studying the residual distribution.

The aim of the project is to develop algorithms in the subcube conditioning framework [1] and analyse the security of modern cryptosystems in this framework. The existing results in testing with subcube conditional samples only work when the null hypothesis assumes the underlying distribution to satisfy the target property. However, the distributions are often statistically close to one satisfying the property. The first objective of this project would be to develop algorithms to test the closeness of distributions using subcube conditional samples. The second objective of the project would be to develop a new cryptanalysis technique using these algorithms and analyse the security of popular cryptographic constructions.