Higher Rates and Information-Theoretic Analysis for the RLWE Channel
Georg Maringer, Sven Puchinger, Antonia Wachter-Zeh · 2021
TheLearningwithErrors(LWE) problem is considered to be a hard problem and lies the foundation of various cryptographic algorithms. Several cryptosystems based on the closely relatedRingLearningwithErrors(RLWE) problem have been proposed within the NIST PQC standardization process, e.g., the systems LAC and NewHope. 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 extend this channel from binary toq-ary alphabets and show that this does not compromise the security of the related RLWE-based schemes if appropriate error correcting codes are used to prevent thedecryptionfailurerate(DFR) from increasing. We give a lower bound on the capacity of this channel showing that the achievable asymptotic rates are substantially (5.7 times for LAC and 10.7 times for NewHope) higher than the currently deployed ones for the finite length regime. Furthermore, under the assumption of stochastically independent coefficient failures, we show that substantially higher rates can also be achieved in the finite length setting by using the Gilbert-Varshamov bound. Moreover, we give explicit code constructions increasing the achievable rate by a factor of 2 for LAC and a factor of 7 for NewHope without increasing the DFR for the respective parameter sets achieving a security level equivalent to AES256.