Cryptology ePrint Archive: Report 2019/674

Polar Sampler: Discrete Gaussian Sampling over the Integers Using Polar Codes

Jiabo Wang and Cong Ling

Abstract: Cryptographic constructions based on hard lattice problems have emerged as a front runner for the standardization of post quantum public key cryptography. As the standardization process takes place, optimizing specific parts of proposed schemes becomes a worthwhile endeavor. Gaussian sampling over the integers is one of the fundamental building blocks of latticed-based cryptography. In this work, we propose a new integer Gaussian sampler based on polar codes, dubbed ``polar sampler". The polar sampler is asymptotically information theoretically optimum in the sense that the number of uniformly random bits it uses approaches the entropy bound. It also features quasi-linear complexity and constant-time implementation. Our algorithm becomes effective when sufficiently many samples are required at each query to the sampler. Security analysis is given based on the statistical distance, Kullback-Leibler divergence and Rényi divergence. A comparison between the polar sampler and the Knuth-Yao sampler verifies its time efficiency and the memory cost can be further optimized if space-efficient successive-cancellation decoding is adopted.

Category / Keywords: applications / Discrete Gaussian sampling, Polar codes, Integer lattice, Kullback-Leibler divergence, Constant-time implementation

Date: received 6 Jun 2019

Contact author: j wang16 at imperial ac uk, c ling@imperial ac uk

Available format(s): PDF | BibTeX Citation

Version: 20190606:171354 (All versions of this report)

Short URL: ia.cr/2019/674


[ Cryptology ePrint archive ]