Information- and Coding-Theoretic Analysis of the RLWE Channel. (arXiv:2009.08681v2 [cs.IT] UPDATED)

Several cryptosystems based on the emph{Ring Learning with Errors} (RLWE)
problem have been proposed within the NIST post-quantum cryptography
standardization process, e.g. NewHope. Furthermore, there are systems like
Kyber which are based on the closely related MLWE assumption. Both previously
mentioned schemes feature a non-zero decryption failure rate (DFR). The
combination of encryption and decryption for these kinds of algorithms can be
interpreted as data transmission over noisy channels. To the best of our
knowledge this paper is the first work that analyzes the capacity of this
channel. We show how to modify the encryption schemes such that the input
alphabets of the corresponding channels are increased. In particular, we
present lower bounds on their capacities which show that the transmission rate
can be significantly increased compared to standard proposals in the
literature. Furthermore, under the common assumption of stochastically
independent coefficient failures, we give lower bounds on achievable rates
based on both the Gilbert-Varshamov bound and concrete code constructions using
BCH codes. By means of our constructions, we can either increase the total
bitrate (by a factor of $1.84$ for Kyber and by factor of $7$ for NewHope)
while guaranteeing the same emph{decryption failure rate} (DFR). Moreover, for
the same bitrate, we can significantly reduce the DFR for all schemes
considered in this work (e.g., for NewHope from $2^{-216}$ to $2^{-12769}$).