Higher rates and information-theoretic analysis for the RLWE channel

Georg Maringer, Sven Puchinger, Antonia Wachter-Zeh

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


The Learning with Errors (LWE) problem is considered to be a hard problem and lies the foundation of various cryptographic algorithms. Several cryptosystems based on the closely related Ring Learning with Errors (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 to q-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 the decryption failure rate (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.
Original languageEnglish
Title of host publicationProceedings of 2020 IEEE Information Theory Workshop
Number of pages5
Publication date2021
Article number9457595
ISBN (Print)978-1-7281-5963-8
Publication statusPublished - 2021
Event2020 IEEE Information Theory Workshop - Virtual Event, Riva del Garda, Italy
Duration: 11 Apr 202115 Apr 2021


Workshop2020 IEEE Information Theory Workshop
LocationVirtual Event
CityRiva del Garda
Internet address


Dive into the research topics of 'Higher rates and information-theoretic analysis for the RLWE channel'. Together they form a unique fingerprint.

Cite this