Count-then-Permute: A Precision-Free Alternative to Inversion Sampling

摘要

The sampling from a discrete probability distribution on computers is an old problem having a wide variety of applications. The inversion sampling which uses the cumulative probability table is quite popular method for discrete distribution sampling. One drawback of inversion sampling (and most of other generic methods) is that it's table size and sampling time depends on the precision we require. This can be problematic, since the precision can be quite high, e.g., 256 bits or even more, in particular for cryptographic purpose. In this paper, we present a novel sampling method which we call counter-then-permute (CP) sampler. Our proposal has a unique feature that its time and memory for on-line sampling phase does not depend on the precision, and can be faster and smaller than inversion sampling, which was often the most efficient one, depending on the relationship between the precision and the number of samples we want. Our proposal uses a block cipher as an efficient, computationally-secure instantiation of uniform sampling without replacement, also known as a pseudorandom permutation (PRP) in the cryptographic terminology, and pre-processing based on a recent polynomial-time exact sampling for binomial distribution. We also show some experimental results of CP sampler for discrete Gaussian distributions, which are typically used by lattice-based cryptographic schemes.