论文标题
RLWE渠道的信息和编码理论分析
Information- and Coding-Theoretic Analysis of the RLWE Channel
论文作者
论文摘要
基于\ emph {带错误}（rlwe）问题的几个密码系统已在NIST后Quantum加密标准化过程中提出，例如NewHope。此外，像Kyber这样的系统基于密切相关的MLWE假设。前面提到的方案都导致非零解密失败率（DFR）。这些类型算法的加密和解密的结合可以解释为嘈杂通道上的数据传输。据我们所知，本文是分析该渠道能力的第一本作品。我们展示了如何修改加密方案，以便增加相应通道的输入字母。特别是，我们介绍了其容量的下限，这表明与文献中的标准建议相比，传输速率可以显着提高。此外，在随机独立系数失败的常见假设下，我们基于使用BCH代码的Gilbert-Varshamov界限和具体代码构建的可实现速率给出了下限。 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 DFR or 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}$).
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 result in 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 a noisy channel. 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 DFR or 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}$).
