Coding techniques in lattice-based cryptography

Abstract

Cryptographic constructions based on hard lattice problems have emerged as a front runner for the standardization of post quantum public key cryptography. The work done in this thesis introduces source and channel coding techniques to optimize specific parts of lattice-based cryptographic schemes from an information theoretic standpoint, with a particular focus on Gaussian sampling over the integers and ring-LWE-based public key encryption.

In the first part, we propose a new integer Gaussian sampler based on polar codes, dubbed ``polar sampler''. Gaussian sampling over the integers is one of the fundamental building blocks of latticed-based cryptography. 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 Reny\'i 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.

In the second part, we for the first time formulate the ring-LWE based public key encryption as an i.i.d. fading channel and construct polar codes for it. RLWE-based public key encryption and the key encapsulation schemes built on it have received ample attention. The well-designed ring structure enables smaller ciphertext sizes as well as fast NTT computations. The decryption failure rate is a significant factor affecting the security level especially in the conversion from a CPA-secure PKE to a CCA-secure one by FO transform. Modern error-correcting codes and soft-decision decoders show great advantages in improving DFR but how to deal with the ``dependency'' existing in the ``channel noise'' is challenging. We completely resolve the ``dependency'' by mapping the noise term of the polynomial RLWE-based PKE to its image in canonical basis where polynomial convolutions are converted to point-wise multiplications. Further, some knowledge about the noise term, namely ``channel state information'', is exploited by the decoder to improve the DFR. Then, we build a new modulation scheme in canonical basis and demonstrate how to construct polar codes for this i.i.d. fading channel with CSI available to decoder.

In the third part, we proposed concrete and practical solutions to improve the DFR performance using polar codes and Reed-Muller codes. To make the proposed methods perfectly fit in with the RLWE-based PKE standard, both encoding and decoding routines are carried out in polynomial basis. Theoretical analysis of the DFR is given under an independence assumption and reasonably small DFRs are verified by simulations. In addition, both polar codes and Reed-Muller codes feature constant-time encoding and decoding algorithms, enabling safe implementations against timing-based side channel attacks.